Table size reduction for data value predictors by exploiting narrow width values

ABSTRACT

Recently, the practice of speculation in resolving data dependences has been studied as a means of extracting more instruction level parallelism (ILP). An outcome of an instruction is predicted by value predictors. The instruction and its dependent instructions can be executed simultaneously, thereby exploiting ILP aggressively. One of the serious hurdles for realizing data speculation is huge hardware budget of the predictors. In this paper, we propose a technique reducing the budget by exploiting narrow width values. The hardware budget of value predictors is reduced by up to 45.1%. Simulation results show that the technique, called 2-mode scheme, maintains processor performance with slight decrease of the value prediction accuracy.

REFERENCES

• 1: David Brooks , Margaret Martonosi, Dynamically Exploiting Narrow Width Operands to Improve Processor Power and Performance, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.13, January 09-12, 1999
• 2: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 3: Brad Calder , Glenn Reinman , Dean M. Tullsen, Selective value prediction, Proceedings of the 26th annual international symposium on Computer architecture, p.64-74, May 01-04, 1999, Atlanta, Georgia, United States
• 4: Karel Driesen , Urs Hölzle, The cascaded predictor: economical and adaptive branch target prediction, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.249-258, November 1998, Dallas, Texas, United States
• 5: Barry Fagin, Partial Resolution in Branch Target Buffers, IEEE Transactions on Computers, v.46 n.10, p.1142-1145, October 1997 [doi>10.1109/12.628399]
• 6: Gabbay, F.: Speculative execution based on value prediction, Technical Report #1080, Department of Electrical Engineering, Technion (1996).
• 7: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 8: 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
• 9: Enric Morancho , José María Llabería , Angel Olivé, Split Last-Address Predictor, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.230, October 12-18, 1998
• 10: 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
• 11: Alex Peleg , Sam Wilkie , Uri Weiser, Intel MMX for multimedia PCs, Communications of the ACM, v.40 n.1, p.24-38, Jan. 1997 [doi>10.1145/242857.242865]
• 12: Rychlik,B., Faistl,J.W., Krug,B.P., Kurland, A.Y., Sung,J.J., Velev,M.N., Shen, J.P.: Efficient and accurate value prediction using dynamic classification, Technical Report CMuART- 98-01, Department of Electrical Computer Engineering, Carnegie Mellon University (1998).
• 13: Sato,T., Arita,I.: Reducing hardware budget of data value predictors using partial resolution, Technical Report of IEICE, CPSY-2000 (2000) (in Japanese).
• 14: Sazeides,Y., Smith,J.E.: Implementations of context based value predictors, Technical Report TR- ECE-97-8, Department of Electrical Computer Engineering, University of Wisconsin-Madison (1997).
• 15: Dean M. Tullsen , John S. Seng, Storageless value prediction using prior register values, Proceedings of the 26th annual international symposium on Computer architecture, p.270-279, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Hong Wang , Tong Sun , Qing Yang, CAT—caching address tags: a technique for reducing area cost of on-chip caches, Proceedings of the 22nd annual international symposium on Computer architecture, p.381-390, June 22-24, 1995, S. Margherita Ligure, Italy
• 17: 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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Measurement, Performance, Theory

Keywords:
data speculation, hardware implementation, instruction level parallelism, narrow width operands, value prediction