FoMR: Microarchitecture mechanisms for handling conditional branches that are (a) very hard to predict accurately or (b) impossible to predict accurately

University Of Texas At Austin, Austin TX

Investigators

Abstract

Computers are playing a continually increasing role in supporting a better quality of life, including targeted health care, autonomous vehicles, and weather prediction. Their effectiveness in doing so, however, depends on how fast these computers can execute the programs that do more accurate and quicker decisions and predictions. A computer program that predicts a tsunami will hit tomorrow is of no value if the computer produces its result three days from now. This speed and accuracy are tightly coupled with a basic logical step: How fast can a computer process conditional branch instruction, such as an if-then-else. Conditional branch instructions are commands in a computer program that direct the computer to choose between executing alternate tasks. This basic function can end up being a bottleneck in modern systems that have to make millions of decisions as part of complex models. This research addresses that bottleneck, and can greatly improve the capabilities of modern computer processors. To improve performance of the microarchitecture, assembly lines (aka pipelines) were introduced long ago to process each instruction. Like all assembly lines, most instructions benefit greatly from this assembly line. However, not so with conditional branch instructions, since they require the computer to decide at the front of the assembly line what to do next (aka branch prediction). The problem is that a wrong guess means trashing everything on the assembly line, which degrades performance enormously. This research minimizes that from happening by recognizing that conditional branches are of three types: those predicted accurately, those not predicted well today, but can benefit significantly from some the first type, by using the well-known Tagged Geometric history length branch predictor (TAGE). For the second type, TAGE is augmented with the results of information learned from machine learning. For the third type, not predict at all, but perform other tasks while waiting for the necessary information to reach the end of the assembly line instead of guessing incorrectly and then trashing all the useless work already performed as a result of the wrong guess. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.