Dynamic vectorization: a mechanism for exploiting far-flung ILP in ordinary programs

ABSTRACT

Several ILP limit studies indicate the presence of considerable ILP across dynamically far-apart instructions in program execution. This paper proposes a hardware mechanism, dynamic vectorization (DV), as a tool for quickly building up a large logical instruction window. Dynamic vectorization converts repetitive dynamic instruction sequences into vector form, enabling the processing of instructions from beyond the corresponding program loop to be overlapped with the loop. This enables vector-like execution of programs with relatively complex static control flow that may not be amenable to static, compile time vectorization. Experimental evaluation shows that a large fraction of the dynamic instructions of four of the six SPECInt92 programs can be captured in vector form. Three of these programs exhibit significant potential for ILP improvements from dynamic vectorization, with speedups of more than a factor of 2 in a scenario of realistic branch prediction and perfect memory disambiguation. Under perfect branch prediction conditions, a fourth program also shows well over a factor of 2 speedup from DV. The speedups are due to the overlap of post-loop processing with loop processing.

REFERENCES

• 1: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 2: Manoj Franklin, The multiscalar architecture, University of Wisconsin at Madison, Madison, WI, 1993
• 3: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 4: Tulika Mitra, "Performance Evaluation of Improved Superscalar Issue Mechanisms," M.E. Project Report, January 1997.
• 5: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 6: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 7: Matthew A. Postiff, David Greene, Gary Tyson, and Trevor Mudge, "The Limits of Instruction Level Parallelism in SPEC95 Applications," in INTERACT.3: The Third Workshop on Interaction Between Compilers and Computer Architectures, San Jose, CA, October 1998.
• 8: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 10: James E. Smith, Decoupled access/execute computer architectures, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.289-308, Nov. 1984 [doi>10.1145/357401.357403]
• 11: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 12: Augustus K. Uht, Concurrency Extraction Via Hardware Methods Executing the Static Instruction Stream, IEEE Transactions on Computers, v.41 n.7, p.826-841, July 1992 [doi>10.1109/12.256451]
• 13: Sriram Vajapeyam , Tulika Mitra, Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences, Proceedings of the 24th annual international symposium on Computer architecture, p.1-12, June 01-04, 1997, Denver, Colorado, United States
• 14: H.C. Young and J. R. Goodman, "The Design of a Queue-Based Vector Supercomputer," Int'i Conf. on Parallel Processing, 1986.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

General Terms:
Design, Management, Measurement, Theory