Increasing the instruction fetch rate via multiple branch prediction and a branch address cache

Reviewer: Mihail Sadeanu

The authors present a hardware mechanism to predict multiple branches (MBs) and fetch multiple nonconsecutive basic blocks (MNC BB) simultaneously in each clock cycle (CC), which is viable and effective. The proposed solution fully utilizes the fetch and execution bandwidth (bypassing the execution bandwidth wasted on instructions whose results are discarded, and instruction fetch bandwidth wasted on instructions that will not be executed). It introduces a highly accurate branch prediction algorithm, a branch address cache, and an instruction cache, all of which are hardware intensive but not excessively so for the newest and upcoming generations of MIMD computer designs. The authors describe mechanisms for fetching two and three basic blocks each clock cycle based on an “MB two-level adaptive branch predictor” algorithm. This algorithm provides highly accurate predictions of MB paths. Also, the procedure makes it possible to fetch MNC BB each clock cycle, the MB paths being predicted. The instruction cache is designed with a large bandwidth in order to supply MNC BB of instructions in a single CC. For simulation purposes, the team used a trace-driven simulator to evaluate the performance of a machine front end and a new performance metric “IPC f,” defined as the number of effective instructions fetched per CC by an instruction fetch mechanism. A comparison of various instruction cache schemes shows that the IPC f is greater for a higher set associativity level. The advanced branch address cache and instruction cache proposed design with interleaved banks are the ultimate schemes proposed for increasing the IPC f, for both integer and floating-point benchmarks, without compiler optimization or the hardware cost of multiple read ports. These solutions are considered for hardware designs in order to speed up the rate of extracting instruction parallelism from sequential program structures. Simulation results are presented in tables, graphs, and histograms, and are explained in detail in the text. The benchmarks should have been selected from the SPEC92 instead of the SPEC89 benchmark test set, which is already obsolete. The results are of interest for hardware chip set designers and manufacturers. They might also be used to extend new parallel structures and architectures of multiprocessor MIMD computers.