Abstract
The Central Processing Unit (CPU) in a microprocessor is responsible for running machine instructions as fast as possible so that the machine performance is at its maximum level. While simple in design, in-order execution processors provide sub-optimal performance, because any delay in instruction processing blocks the entire instruction stream. To overcome this limitation, modern highperformance designs use out-of-order (OoO) instruction scheduling to better exploit available Instruction-Level Parallelism (ILP), and both static (compilerassisted) and dynamic (hardware-assisted) scheduling solutions are possible. The hardware-assisted scheduling integrates an OoO core that requires a complex dynamic instruction scheduler and additional datapath structures are utilized to hold the in-flight instructions in program order to support the reconstruction of precise program state. The logic becomes even more complex when superscalar (those capable of executing multiple instructions every clock cycle) designs are used. This chapter gives a brief introduction to instruction scheduling on pipelined superscalar architectures, and, then, explains some of the keystone static and dynamic instruction scheduling algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bernstein, D., Cohen, D., Lavon, Y., Rainish, V.: Performance Evaluation of Instruction Scheduling on the IBM RISC System/6000. In: MICRO, vol. 25, pp. 226–235 (1992)
Moon, S.M., Ebcioglu, K.: Parallelizing Nonnumerical Code With Selective Scheduling and Software Pipelining. TOPLAS 19(6), 853–898 (1997)
Mahajan, A., Ali, M.S., Patil, M.: Instruction Scheduling Using Evolutionary Programming. In: ACC 2008, pp. 137–144 (2008)
Weiss, S., Smith, J.E.: Instruction Issue Logic in Pipelined Supercomputers. In: ISCA 1984, pp. 110–118 (1984)
Tomasulo, R.M.: An Efficient Algorithm for Exploiting Multiple Arithmetic Units. IBM J. Res. Development 11(1), 25–33 (1967)
Thornton, J.E.: Parallel Operation in the Control Data 6600. In: AFIPS 1964, Part 2, pp. 33–40 (1964)
Tune, E., Tullsen, D.M., Calder, B.: Quantifying Instruction Criticality. In: PACT 2002, p. 104 (2002)
Lebeck, A.R., Koppanalil, J., Li, T., Patwardhan, J., Rotenberg, E.: A Large, Fast Instruction Window for Tolerating Cache Misses. In: ISCA 2002, pp. 59–70 (2002)
Wang, H., Sangireddy, R.: Streamlining Long Latency Instructions For Seamlessly Combined Out-Of-Order and In-Order Execution. Microprocessors & Microsystems 32, 375–385 (2008)
Sharkey, J.J., Ponomarev, D.V.: Non-Uniform Instruction Scheduling. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol. 3648, pp. 540–549. Springer, Heidelberg (2005)
Ernst, D., Hamel, A., Austin, T.: Cyclone: A Broadcast-Free Dynamic Instruction Scheduler with Selective Replay. In: ISCA 2003, pp. 253–263 (2003)
Buyuktosunoglu, A., Albonesi, D.H., Bose, P., Cook, P.W., Schuster, S.E.: Tradeoffs in Power-Efficient Issue Queue Design. In: ISLPED 2002, pp. 184–189 (2002)
Brown, M.D., Stark, J., Patt, Y.N.: Select-Free Instruction Scheduling Logic. In: MICRO, vol. 34, pp. 204–213 (2001)
Stark, J., Brown, M.D., Patt, Y.N.: On Pipelining Dynamic Instruction Scheduling Logic. In: MICRO, vol. 33, pp. 57–66 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Küçük, G., Güney, İ., Ponomarev, D. (2013). Instruction Scheduling in Microprocessors. In: Uyar, A., Ozcan, E., Urquhart, N. (eds) Automated Scheduling and Planning. Studies in Computational Intelligence, vol 505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39304-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-39304-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39303-7
Online ISBN: 978-3-642-39304-4
eBook Packages: EngineeringEngineering (R0)