Software pipelining a hyperblock loop

Details Software pipelining a hyperblock loop Software pipelining a hyperblock loop

1998-12-16

2000-01-18

Hafiz, Tariq R.

Electrical computers and digital processing systems: processing

Processing architecture

Distributed processing system

395706, 712241, G06F 945, G06F 944

Patent

active

060163992

ABSTRACT:
An iterative software pipelining method promotes instructions of a program loop to previous loop iterations and then reschedules the instructions until either 1) the resultant schedule is optimal (i.e., the initiation interval is equal to the minimal initiation interval) or 2) the resultant schedule is not an improvement over the previous schedule generated. The method is applicable to a sequence of instructions within a program loop having a single control flow entry and one or more control flow exit points. First, a minimum initiation interval of the program loop is computed. Second, instruction level parallelism transformations are applied on the program loop. Third, a single iteration schedule is determined for the program loop. Fourth, selected instructions are percolated to a prior iteration of the program loop to generate a new instruction order for the program loop. Each of steps two through four is performed as long as a previous length of the program loop exceeds a single iteration schedule length and the single iteration schedule length exceeds the minimum initiation interval.

REFERENCES:
patent: 5265253 (1993-11-01), Yamada
patent: 5303357 (1994-04-01), Inoue et al.
patent: 5317743 (1994-05-01), Imai et al.
patent: 5367651 (1994-11-01), Smith et al.
patent: 5375238 (1994-12-01), Ooi
patent: 5386562 (1995-01-01), Jain et al.
patent: 5920724 (1999-07-01), Chang
Aiken et al., "Optimal Loop Parallelization", Proc. of the SIGPLAN '88 Conf. on Programming Language Design and Implementation, SIGPLAN Notices, vol. 23, No. 7, Jul. 1988,pp. 308-327.
Bernstein et al., Code Duplication: An Assist for Global Instruction Scheduling, MICRO 24, Nov. 1991, pp. 103-113.
Bernstein et al., "Performance Evaluation of Instruction Scheduling on the IBM RISC System/6000", MICRO 25, Dec. 1992, pp. 226-235.
Bernstein et al., "A Software Pipelining Algorithm based on Global Instruction Scheduling", Technical Report 88.338, IBM Israel, Science and Technology, Sep. 1993, pp. 1-18.
"Global Instruction Scheduling for Superscalar Machines", Proc. of the ACM SIGPLAN '91 Conf. Progr. Language Design and Implementation, SIGPLAN Notices.vol. 26,No. 6, Jun. 1991, pp. 241-255.
Dehnert et al., "overlapped Loop Support in the Cydra 5", ASPLOS-III, 1989, pp. 26-38.
Eblcioglu, "A Compilation Technique for Software Pipelining of Loops with Conditional Jumps", MICRO 20,Dec. 1987, pp. 69-79.
Eichenberger et al., "Minimum Register Requirement for a Modulo Schedule", MICRO 27, 1994, pp. 75-84.
Gupta et al., "Region Scheduling: An Approach for directing and redistributing parallelism", IEEE Transactions on Software Engineering, vol. 16, No. 4, Apr. 1990, pp. 421-431.
Johnson, "Superscalar microprocessor design", Prentice-Hall inc., 1991,pp. 9-28, 177-199,203-235.
Lam, "Software pipelining: an effective scheduling technique for VLIW machines", Proc. of the SIGPLAN '88, SIGPLAN Notices, vol. 23, No. 7, Jul. 1988,pp. 318-328.
Moon et al., "An Efficient Resource--Constrained global scheduling technique for Superscalar and VLIW processors", MICRO 25, Dec. 1992, pp. 55-71.
Ning et al., "A Novel framework of register allocation for software pipelining", CONf. record of the 20th Annual ACM SIGPLAN--SIGACT Symp. on POPL, Jan. 1993, pp. 29-42.
Rau et al. , "Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing" MICRO 14, Oct. 1981,pp. 183-198.
Rau et al., "Register allocation for software pipelined loops", Proc. of the ACM SIGPLAN Conf. on Progr. Lang. and design and implementation, Jul. 1992, pp. 283-299.
Tirumalai et al., "Paralleliozation of loops with exits on pipelined architectures", Proc. of the Supercomputing , Nov. 1990, pp. 200-212.
Touzeau et al., A Fortran compiler for the FPS-164 Scientific computer, Proc. of the ACM SIGPLAN Symp. on Compiler Construction, SIGPLAN Notices, Jun. 1984, pp. 48-57.
Warter et al., "Enhanced Modulo Scheduling for Loops with Conditional Branches", MICRO 25, Dec. 1992, pp. 170-179.
Tirumalai et al. "Parallelization of WHILE Loops on pipelined Architectures", Journal of Supercomputing, 1991, pp. 119-136.
Ramanujam, "Non-Unimodular Transformations of nested Loops", Supercomputing 1992, pp. 214-223.
Rau et al., "Code generation Scema for Modulo Scheduled Loops", 1992, pp. 158-169.
Mahlke et al., "Compiler code transformation for superscalar-based High-Performance systems", Supercomputing 1992, pp. 808-817.

Affiliated with

Also associated with

Rating

Software pipelining a hyperblock loop does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Software pipelining a hyperblock loop, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Software pipelining a hyperblock loop will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-568941