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-0656