Value prediction in VLIW machines

ABSTRACT

The performance of VLIW architectures is dependent on the capability of the compiler to detect and exploit instruction-level parallelism during instruction scheduling. To exploit the detected parallelism, instructions are reordered to reduce the length of the code schedule and minimize the cycle count for execution. Code reordering is limited by the dependencies among instructions arising from both control flow and data flow. In this paper, we present the design of a VLIW architecture that uses value prediction to remove data dependencies and improve the instruction schedule. Our architecture consists of two execution engines, one for executing the original VLIW code, and the other for executing compensation code after a misprediction. Any code executed due to mispredictions is executed in parallel with the VLIW instructions. The instruction set and hardware of a traditional VLIW machine are modified accordingly to support this type of concurrent execution. The efficacy of the proposed architecture is demonstrated by implementing the prediction model in the Trimaran compiler infrastructure and studying the speedups that result due to the parallel execution of compensation code.

REFERENCES

• 1: The trimaran compiler research infrastructure. Tutorial Notes, November 1997.
• 2: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 3: J. Fisher. Trace scheduling: a technique for global microcode compaction. IEEE Tranactions on Computers, July t981.
• 4: Chao-Ying Fu , Matthew D. Jennings , Sergei Y. Larin , Thomas M. Conte, Value speculation scheduling for high performance processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.262-271, October 02-07, 1998, San Jose, California, United States
• 5: F. Gabbay and A. Mendelson. Speculative execution based on value prediction. EE Department TR# t080, Technion- Israel Institute of Technology, November t996.
• 6: Freddy Gabbay , Avi Mendelson, Can program profiling support value prediction?, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.270-280, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: Wen-Mei W. Hwu , Scott A. Mahlke , William Y. Chen , Pohua P. Chang , Nancy J. Warter , Roger A. Bringmann , Roland G. Ouellette , Richard E. Hank , Tokuzo Kiyohara , Grant E. Haab , John G. Holm , Daniel M. Lavery, The superblock: an effective technique for VLIW and superscalar compilation, The Journal of Supercomputing, v.7 n.1-2, p.229-248, May 1993 [doi>10.1007/BF01205185]
• 8: V. Kathail, M. Schlansker, and B. R. Rau. Hpl playdoh architecture specification: Version 1.0. HewIett- Packard Laboratories Technical Report HPL-93-80, Computer Systems Laboratory, February 1994.
• 9: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 10: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 11: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 12: T. Nakra , R. Gupta , M. L. Soffa, Global Context-Based Value Prediction, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.4, January 09-12, 1999
• 13: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: M. Schlansker, B. R. Ran, S. Mahlke, V. Kathail, R.Johnson, S.Anik, and S. G. Abraham. Achieving high levels of instruction-level parallelism with reduced hardware complexity. Hewtett-Packard Laboratories Technical Report HPL-960120, Hewlett-Packard Laboratories, February 1997.
• 15: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Experimentation, Management, Performance, Reliability