A performance analysis of automatically managed top of stack buffers

ABSTRACT

In this paper, the feasibility of using register banks as a top of stack (TOS) buffer is demonstrated. A quantitative performance evaluation is made of three automatic TOS buffer management algorithms: a simple single pointer algorithm, an intelligent single pointer algorithm, and a sophisticated double pointer algorithm. An automatically managed TOS buffer can effectively cache local data accesses resulting in a large memory traffic reduction. Results demonstrate that a small (with respect to the size of the benchmark data set) TOS buffer provides a very high data reference hit ratio and requires minimal processor intervention for TOS buffer management. The simple single pointer algorithm is shown to provide the best overall performance for various metrics including memory bandwidth, TOS buffer hit ratio, processor intervention, and processor execution speed.

REFERENCES

• 1: David R. Ditzel , H. R. McLellan, Register allocation for free: The C machine stack cache, ACM SIGPLAN Notices, v.17 n.4, p.48-56, April 1982
• 2: Reinhold P. Weicker, Dhrystone: a synthetic systems programming benchmark, Communications of the ACM, v.27 n.10, p.1013-1030, Oct 1984 [doi>10.1145/358274.358283]
• 3: D. A. Patterson and C. H. Sequin. A VLSI RISC. Computer, 8-21, September 1982.
• 4: R. P. Blake. Exploring a Stack Architecture. Computer, May 1977.
• 5: R. W. Doran, Computer Architecture: A Structured Approach, Academic Press, Inc., Orlando, FL, 1979
• 6: 3600 Technical Summary. Symbolics, Inc., 1983.
• 7: Richard L. Sites. How to Use 1000 Registers. CalTech Conference on VLSI, January 1979.
• 8: Yuval Tamir and Carlo H. Sequin. Strategies for Managing the Register File in RISC. IEEE Transactions on Computere, 32(11), November 1983.
• 9: Timothy J. Stanley. A Performance Evaluation of Automatically Managed Top of Stack Buffers. Master's thesis, Carnegie-Mellon University, 1985.
• 10: Robert G. Wedig. Software and Hardware Techniques for Stack Management. Hawaii International Conference on System Sciences, January 1987.
• 11: Makoto Hasegawa , Yoshiharu Shigei, High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis, Proceedings of the 12th annual international symposium on Computer architecture, p.48-54, June 17-19, 1985, Boston, Massachusetts, United States
• 12: Charles Y. Hitchcock, III , H. M. Brinkley Sprunt, Analyzing multiple register sets, Proceedings of the 12th annual international symposium on Computer architecture, p.55-63, June 17-19, 1985, Boston, Massachusetts, United States
• 13: CORPORATE Motorola, M68000: 16/32-bit microprocessor: programmer's reference manual (4th ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1984

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Control design

Additional Classification:
  C. Computer Systems Organization

General Terms:
Algorithms, Design, Management, Measurement, Performance