• Article
  • | |
  • Metrics
  • |
  • Reference [14]
  • |
  • Related [20]
  • |
  • Cited by [1]
  • | |
  • Comments
    Abstract:

    Software pipelining is a loop scheduling technique that extracts instruction level parallelism by overlapping the execution of several consecutive iterations. One of its drawbacks is the high register requirements, which may lead to software pipelining failure due to insufficient static general registers in Itanium. This paper evaluates the register requirements of software-pipelined loops and presents three new methods for software pipelining loops that require more static general registers than those available in Itanium processor. They reduce register pressure by either reducing instructions in the loop body or allocating stacked non-rotating registers or rotating register in register stack to serve as static registers. These methods are better than the existing techniques in that they further improve performance gain from software pipelining by increasing software-pipelined loops. These methods have been implemented in open research compiler (ORC) targeted for Itanium processor, and they perform well on loops of the programs in NAS Benchmarks. For some benchmarks, the performance is improved by more than 21%.

    Reference
    [1]Allen VH, Jones RB, Lee RM, Allan SJ. Software pipelining. ACM Computing Surveys, 1995,27(3):367-432.
    [2]Huff RA. Lifetime-Sensitive modulo scheduling. In: Budd TA, ed. Proc. of the ACM SIGPLAN'93 Conf. on Programming Language Design and Implementation. New York: ACM Press, 1993. 258-267.
    [3]Dehnert JC, Towle RA. Compiling for the Cydra 5. Journal of Supercomputing, 1993,7(1-2):181-228.
    [4]Dulong C, Krishnaiyer R, Kulkarni D, Lavery D, Li W, Ng J, Sehr D. An overview of the Intel IA-64 compiler. Intel Technology Journal, 1999.
    [5]Rau BR, Lee M, Tirumalai PP, Schlansker MS. Register allocation for software pipelined loops. In: Allen R, ed. Proc. of the ACM SIGPLAN'92 Conf. on Programming Language Design and Implementation. New York: ACM Press, 1992. 283-299.
    [6]Dehnert JC, Hsu PY, Bratt JP. Overlapped loop support in the Cydra 5. In: Hennessy J, ed. Proc. of the 3rd Int'l Conf. on Architectural Support for Programming Languages and System. New York: ACM Press, 1989.26-38.
    [7]Intel Corporation. Intel ItaniumTM Architecture Software Developer's Manual. Volume 1: Application Architecture. Intel Corp.,2001.
    [8]Roy J, Sun C, Wu CY. Tutorial: Open research compiler for Itanium processor family (IPF). In: Proc. of the 34th Annual Int'l Symp. on Microarchitecture. New York: ACM Press, 2001.
    [9]Intel Corporation. Intel ItaniumTM Architecture Software Developer's Manual. Volume 3: Instruction Set Reference. Intel Corp,2001.
    [10]Mangione SW, Abraham SG, Davidson ES. Register requirements of pipelined processors. In: Kennedy K, Polychronopoulos CD,ed. Proc of Int'l Conf. on Supercomputing. New York: ACM Press, 1992.260-271.
    [11]Josep L, Eduard A, Mateo V. Quantitative evaluation of register pressure on software pipelined loops. Int'l Journal of Parallel Programming, 1998,26(2):121-142.
    [12]Smelyanskiy M, Tyson GS, Davidson ES. Register Queues: A new hardware/software approach to efficient software pipelining. In:Hurson AR, ed. Proc. of the 2000 Int'l Conf. on Parallel Architecture and Compilation Techniques. IEEE Press, 2000.
    [13]Akturan C, Jacome MF. RS-FDRA: A register sensitive software pipelining algorithm for embedded VLIW processors. In: Madson J, Henkel J, Hu XBS, eds. Proc. of the 9th Int'l Symp. on Hardware/Software Codesigh. New York: ACM Press, 2001.
    [14]Altemos G, Norris C. Register pressure responsive software pipelining. In: Lamont GB, ed. Proc. of the 2001 ACM Symp. on Applied Computing. ACM Press, 2001.
Get Citation

李文龙,陈彧,林海波,汤志忠.3种提高软件流水有效性的算法:比较和结合.软件学报,2005,16(10):1822-1832

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:April 16,2004
  • Revised:November 22,2004
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063