Design Automation for Finite State Machine Predictors

Finite State Machines (FSM) are a fundamental building block in computer architecture, and are used to control and optimize all types of prediction and speculation. These include branch prediction, confidence estimation, value prediction, memory disambiguation, thread speculation, power optimization, and the list goes on. At the heart of all almost all of these techniques is a FSM, such as a two bit saturating counter, which is predicting a sequence given feedback information. In this paper we present a framework for automatically designing FSM predictors. This approach can be used to develop FSM predictors that perform well over a suite of applications, tailored to a specific application, or even a specific instruction. We examine the ability to create FSM predictors optimized for a group of applications for branch prediction and for confidence estimation used in value prediction.Pre-2018 CSE ID: CS2000-065