Multiple, out-of-order, instruction issuing system for superscalar processors
Harry A. Dwyer · 1992
Superscalar processors increase the number of executions per cycle (throughput) by issuing multiple instructions to functional units each cycle when possible. Instructions may be scheduled in hardware at run time (dynamic scheduling), enabling multiple, out-of-order, instructions to be issued that are difficult or impossible to schedule at compile time. Problems with this scheduling approach include complex hardware (and subsequent slow operation), the scheduling of multiple out-of-order storage and condition code dependent instructions, and achieving fast precise interrupts and multiple levels of branch predictions. We study and present solutions to these problems through the development, study, and evaluation of the Fast Dispatch Stack (FDS), a dynamic instruction scheduling system that may issue multiple, out-of-order, instructions each cycle to functional units as dependencies and resources allow. The basic issuing mechanism supporting a short cycle time is studied and then its capabilities are augmented incrementally, examining tradeoffs and performance implications at each step. The structures and cycle time necessary to schedule storage, branch, and register-to-register instructions and assign them to functional units are studied in detail. A technique is presented that enables condition code dependent instructions to issue in multiples and out-of-order. A fast register renaming scheme is presented and evaluated. An instruction squashing technique is presented that enables fast precise interrupts and branch predictions. Instructions preceding and following one or more predicted conditional branch instructions may issue out-of-order and concurrently. The effects of executed instructions following an incorrectly predicted branch instruction or an instruction that causes a precise interrupt are undone in one machine cycle. FDS systems are evaluated via simulations of the 14 Lawrence Livermore loops and the Dhrystone benchmarks. The effects of storage instruction scheduling methods, register renaming, precise interrupts, and branch prediction on throughput are studied. Throughputs are compared with those measured on sequentially issuing machines.