Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Recent superscalar processors issue four instructions per cycle. These processors are also powered by highly-parallel superscalar cores. The potential performance can only be exploited when fed by high instruction bandwidth. This task is the responsibility of the instruction fetch unit. Accurate branch prediction and low I-cache miss ratios are essential for the efficient operation of the fetch unit. Several studies on cache design and branch prediction address this problem. However, these techniques are not sufficient. Even in the presence of efficient cache designs and branch prediction, the fetch unit must continuously extract multiple, non-sequential instructions from the instruction cache, realign these in the proper order, and supply them to the decoder. This paper explores solutions to this problem and presents several schemes with varying degrees of performance and cost. The most-general scheme, the collapsing buffer, achieves near-perfect performance and consistently aligns instructions in excess of 90% of the time, over a wide range of issue rates. The performance boost provided by compiler optimization techniques is also investigated. Results show that compiler optimization can significantly enhance performance across all schemes. The collapsing buffer supplemented by compiler techniques remains the best-performing mechanism. The paper closes with recommendations and suggestions for future.

REFERENCES

• 1: L. Gwennap, "MIPS RI0000 uses decoupled architecture," Microprocessor Report, Oct. 1994.
• 2: A. Agarwal, "UltraSPARC: A new era in SPARC performance," in 1994 M, croprocessor Forum Pro. ceedings, Oct. 1994.
• 3: M. Slater, "AMD's K5 designed to outrun Pentium," Microprocessor Report, Oct. 1994.
• 4: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 5: David B. Whalley, Fast instruction cache performance evaluation using compile-time analysis, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.13-22, June 01-05, 1992, Newport, Rhode Island, United States
• 6: Chad L. Mitchell , Michael J. Flynn, The effects of processor architecture on instruction memory traffic, ACM Transactions on Computer Systems (TOCS), v.8 n.3, p.230-250, Aug. 1990 [doi>10.1145/99926.99933]
• 7: W. W. Hwu , P. P. Chang, Achieving high instruction cache performance with an optimizing compiler, Proceedings of the 16th annual international symposium on Computer architecture, p.242-251, April 1989, Jerusalem, Israel
• 8: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 9: Tse-Yu Yeh, Two-level adaptive branch prediction and instruction fetch mechanisms for high performance superscalar processors, University of Michigan, Ann Arbor, MI, 1993
• 10: B. Calder , D. Grunwald, Fast and accurate instruction fetch and branch prediction, Proceedings of the 21ST annual international symposium on Computer architecture, p.2-11, April 18-21, 1994, Chicago, Illinois, United States
• 11: S. McFarling, "Combining branch predictors," WRL Technical Note TN-36, Digital Equipment Corporation, 1993.
• 12: L. Gwennap, "PA-8000 combines complexity and speed," Microprocessor Report, Nov. 1994.
• 13: Shlomo Weiss , James E. Smith, IBM Power and PowerPC, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 14: Donald Alpert , Dror Avnon, Architecture of the Pentium Microprocessor, IEEE Micro, v.13 n.3, p.11-21, May 1993 [doi>10.1109/40.216745]
• 15: S. P. Song and M. Denman, "The PowerPC 604 RISC microprocessor," tech. rep., Somerset Design Center, Austin, TX, Apr. 1994.
• 16: M. Johnson, Superscalar microprocessor design. Englewood Cliffs, NJ: Prentice-Hail, 1991.
• 17: J. A. Fisher, "Trace scheduling: A technique for global microcode compaction," IEEE Trans. Cornput., vol. C-30, no. 7, pp. 478-490, July 1981.
• 18: 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]
• 19: Pohua P. Chang , Scott A. Mahlke , Wen-mei W. Hwu, Using profile information to assist classic code optimizations, Software—Practice & Experience, v.21 n.12, p.1301-1321, Dec. 1991 [doi>10.1002/spe.4380211204]
• 20: Mark Smotherman , Shuchi Chawla , Stan Cox , Brian Malloy, Instruction scheduling for the Motorola 88110, Proceedings of the 26th annual international symposium on Microarchitecture, p.257-262, December 01-03, 1993, Austin, Texas, United States
• 21: Thomas M. Conte , Burzin A. Patel , J. Stan Cox, Using branch handling hardware to support profile-driven optimization, Proceedings of the 27th annual international symposium on Microarchitecture, p.12-21, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192726]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Design, Experimentation, Measurement, Performance