Determining maximum acceptable scheduling load latency using...

Details Determining maximum acceptable scheduling load latency using... Determining maximum acceptable scheduling load latency using...

2003-02-07

2008-11-18

Chavis, John (Department: 2193)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

Reexamination Certificate

active

07454747

ABSTRACT:
The present application describes techniques for determining maximum acceptable modeled load latency (e.g., a model number of clock cycles required between the time a load issues and the time its use can issue) for instruction scheduling which uses less compile time, on the order of log2(Maximum load latency—Minimum load latency). Typically, during instruction scheduling, register pressure is monotonically non-decreasing with respect to the scheduled load latency. Therefore, in some embodiments, a hierarchical search method is used to determine the acceptable schedule with the largest modeled load latency. According to an embodiment, a binary search is employed which reduces the compile time required to determine maximum load latency for which registers can be assigned.

REFERENCES:
patent: 5361357 (1994-11-01), Kionka
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5664193 (1997-09-01), Tirumalai
patent: 5805895 (1998-09-01), Breternitz, Jr. et al.
patent: 5809308 (1998-09-01), Tirumalai
patent: 5835745 (1998-11-01), Sager et al.
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5862384 (1999-01-01), Hirai
patent: 5867711 (1999-02-01), Subramanian et al.
patent: 5930510 (1999-07-01), Beylin et al.
patent: 5964867 (1999-10-01), Anderson et al.
patent: 6035389 (2000-03-01), Grochowski et al.
patent: 6304953 (2001-10-01), Henstrom et al.
patent: 6308261 (2001-10-01), Morris et al.
patent: 6341370 (2002-01-01), Tirumalai et al.
patent: 6438682 (2002-08-01), Morris et al.
patent: 6438747 (2002-08-01), Schreiber et al.
patent: 6460173 (2002-10-01), Schreiber
patent: 6671878 (2003-12-01), Bliss
Eichenberger, Alexandre E. et al., “Minimum Register Requirements for a Modulo Schedule”, Proceedings of the 27thAnnual International Symposium on Microarchitecture, pp. 75-84, Nov. 1994.
Eichenberger, Alexandre E. et al., “Optimum Modulo Schedules for Minimum Register Requirements”, Proceedings of the 1995 International Conference on Supercomputing, pp. 31-40, Jul. 1995.
Huff, Richard A., “Lifetime-Sensitive Modulo Scheduling”, Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pp. 258-267, Jun. 1993.
Lavery, Daniel M. et al., “Unrolling-Based Optimizations for Modulo Scheduling”, IEEE, 1995.
Rau, B. Ramakrishna et al., “Code Generation Schema for Modulo Scheduled Loops”, IEEE, 1992.
Rau, B. Ramakrishna et al, “Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops”, Proceedings of the 27thAnnual International Symposium on Microarchitecture, Nov. 1994.
Schlansker, Michael et al., “Height Reduction of Control Recurrences for ILP Processors”, Proceedings of the 27thAnnual International Symposium on Microarchitecture, pp. 40-51, Nov. 1994.

Affiliated with

Also associated with

Rating

Determining maximum acceptable scheduling load latency using... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining maximum acceptable scheduling load latency using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining maximum acceptable scheduling load latency using... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4045394