Flexible Data Dependence and Software Pipelining
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [19]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    For software pipeling of loops with conditional statements, the worst-case path is a great abstacle. In such a loop, some data dependencies called flexible dependencies, may or may not have instances during execution of the loop. From this fact, flexible dependencies that severely limit parallelization of the loop are identified and replaced with less tight virtual dependencies. Then software pipelining is applied. If the schedule does not satisfy the original flexible dependencies, downpush transform is used to rectify. The resulting schedule is partly or completely free of the worst-case effects. This approac is a complement to the classical control speculation. It is characterized by a try-and-catch way: errors are first allowed to be present in the schedule, and then rectified.

    Reference
    [1] Allan, V.H., Jones, R.B., Lee, R.M., et al. Software pi pelining. ACM Computing Surveys, 1995,27(3):367~432.
    [2] Calland, P.Y., Darte. A., Robert, Y.R. Circuit retiming applied to decomposed software pipelining. IEEE Transactions on Parallel and Distributed Sy stems, 1998,9(1):24~35.
    [3] Govindarajan, R., Altman, E.R., Gao, G.R. A framework for resource -constrained rate-optimal software pipelining. IEEE Transactions on Parallel a nd Distributed Systems, 1996,7(11):1133~1149.
    [4] Rau, B.R., Fisher, J.A. Instruction-Level parallel processing: his tory, overview and perspctive. The Journal of Supercomputing, 1993,7(1/2):9~50.
    [5] Dehnert, J.C., Towle, R.A. Compiling for the Cydra-5. The Journal of Supercomputing, 1993,7(1/2):181~227.
    [6] Lam, M. Software pipelining: an effective scheduling technique for VLIW architectures. SIGPLAN Notices, 1988,23(7):318~328.
    [7] Stoodley, M.G., Lee, C.G. Software pipelining loops with conditiona l branches. In: Proceedings of the 29th Symposium on Microarchitecture. 1996. 26 2~273.
    [8] Su, B., Ding, S., Wang, J., et al. GURPR: a method for global s oftware pipelining. In: Proceedings of the 20th Annual Microprogramming Workshop . 1987. 88~96.
    [9] Shim, S.M., Moon, S.M. Split-Path enhanced pipeline scheduling for loops with control flows. In: Proceedings of the 31th Annual ACM/IEEE Internati onal Symposium on Microarchitecture. 1998. 93~102.
    [10] Moon, S.M., Ebcioglu, K. Parallelizing nonnumerical code with selective scheduling and software pipelining. ACM Transactions on Programming Languages an d Systems, 1997,19(6):853~898.
    [11] Ebcioglu, K. A new compilation technique for parallelizing loops with un predictable branches on a VLIW architecture. In: Gelernter, D., Nicolar, A., Pad ua, D., eds. Languages and Compilers for Parallel Computing. London: Pitman/MIT Press, 1989. 213~229.
    [12] Tang, Z., Chen, G., Zhang, C., et al. GPMB——software pipelining br anch-intensive loops. In: Kavanaugh, M.E., ed. Proceedings of the 26th Symposiu m on Microarchitecture. Los Alamitos, CA: IEEE Computer Society Press, 1993. 21~ 29.
    [13] Su, B., Wang, J. GURPR*: a new global software pipelining algorithm. I n: Proceedings of the 24th Symposium on Microarchitecture. 1991. 212~216.
    [14] Lavery, D.M., Hwu, W.W. Modulo scheduling of loops in control-intensive nonnumeric programs. In: Proceedings of the 29th Symposium on Microarchitecture . 1996. 126~137.
    [15] Rong, Hong-bo, Tang, Zhi-zhong. Path grouping and data dependence rela xation for software pipelining. In: Feng, Yu-lin, eds. Proceedings of the World Computer Congress (WCC), Software: Theory and Practice. Beijing: Electronics In dustry Press, 2000. 779~788.
    [16] Chang, P.P., Warter, N.J., Mahlke, S.A., et al. Three architectural models for compiler-controlled speculative execution. IEEE Transactions on Computers, 1995,44(4):481~494.
    [17] Fisher, J.A. Trace scheduling: a technique for global microcode compacti on. IEEE Transactions on Computers, 1981,C-30(7):478~492.
    [18] Rong, Hong-bo. Software pipeling of nested loops [Ph.D. Thesis]. Tsinghua University, 2001 (in Chinese).
    [18]容红波.多重循环软件流水算法研究[博士学位论文].清华大学,2001.
    Related
    Cited by
Get Citation

容红波,汤志忠.弹性数据相关与软件流水.软件学报,2001,12(6):894-906

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 27,1999
  • Revised:March 23,2000
You are the first2032719Visitors
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