FoMR: Collaborative Research: Dependent ILP: Dynamic Hoisting and Eager Scheduling of Dependent Instructions

Florida State University, Tallahassee FL

Investigators

Abstract

Instruction-level parallelism (ILP) in computing allows different machine-level instructions within an application to execute in parallel within a micro-processor. Exploitation of ILP has provided significant performance benefits in computing, but there has been little improvement in ILP in recent years. This project proposes a new approach called "eager execution" that could significantly increase ILP. The success of many applications depends on how efficiently they can be executed. The proposed eager execution technique will benefit applications that span those running on mobile devices to large data applications running on the ever-growing number of data centers. Enabling better systems at all scales will further enable the ubiquitous computing that continues to pervade lives. The project's approach includes the following advantages: (1) immediately-dependent consumer instructions can be more quickly delivered to functional units for execution; (2) the execution of instructions whose source register values have not changed since its last execution can be detected and redundant computation can be avoided; (3) the dependency between a producer/consumer pair of instructions can sometimes be collapsed so they can be simultaneously dispatched for execution; (4) consumer instructions from multiple paths may be speculatively executed and their results can be naturally retained in the paradigm to avoid re-execution after a branch misprediction; and (5) critical instructions can be eagerly executed to improve performance, which include loads to prefetch cache lines and pre-computation of branch results to avoid branch misprediction delays. 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.