Patent
1996-06-18
1999-03-23
Kim, Kenneth S.
395706, 395397, 395557, G06F 944
Patent
active
058871748
ABSTRACT:
Instructions are scheduled for execution by a processor having a lookahead buffer by identifying an idle slot in a first instruction schedule of a first basic block of instructions, and by rescheduling the idle slot later in the first instruction schedule. The idle slot is rescheduled by determining if the first basic block of instructions may be rescheduled into a second instruction schedule in which the identified idle slot is scheduled later than in the first instruction schedule. The first basic block of instructions is rescheduled by determining a completion deadline of the first instruction schedule, decreasing the completion deadline, and determining the second instruction schedule based on the decreased completion deadline. Deadlines are determined by computing a rank of each node of a DAG corresponding to the first basic block of instructions; constructing an ordered list of the DAG nodes in nondecreasing rank order; and applying a greedy scheduling heuristic to the ordered list. An instruction in a second subsequent basic block of instructions may be rescheduled to execute in the rescheduled idle slot. This process may be repeated for each idle slot.
REFERENCES:
patent: 4435756 (1984-03-01), Potash
patent: 4714994 (1987-12-01), Oklobdzija et al.
patent: 4894772 (1990-01-01), Langendorf
patent: 4984154 (1991-01-01), Hanatani et al.
patent: 5040107 (1991-08-01), Duxbury et al.
patent: 5121473 (1992-06-01), Hodges
patent: 5127092 (1992-06-01), Gupta et al.
patent: 5127093 (1992-06-01), Moore, Jr.
patent: 5168557 (1992-12-01), Shibuya
patent: 5201057 (1993-04-01), Uht
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5202993 (1993-04-01), Tarsy et al.
patent: 5287466 (1994-02-01), Kodama
patent: 5291615 (1994-03-01), Okamoto
patent: 5307478 (1994-04-01), Rasbold et al.
patent: 5317702 (1994-05-01), Morisada
patent: 5317734 (1994-05-01), Gupta
patent: 5386562 (1995-01-01), Jain et al.
patent: 5394529 (1995-02-01), Brown, III et al.
patent: 5394530 (1995-02-01), Kitta
patent: 5574939 (1996-11-01), Keckler et al.
Coffman, E. G. and Graham, R. L., "Optimal Scheduling for Two-Processor Systems", Acta Informatica, 1:200-213, 1972.
Ullman, J., "NP-Complete Scheduling Problems", J. Comput. System Sci, 10, pp. 384-393, 1975.
Gabow, H., "Scheduling UET Systems on Two Uniform Processors and Length Two Pipelines", SIAM J. Computing, 17:810-829, 1988.
Hu, T. C., "Parallel Sequencing and Assembly Line Operations", Operations Research, 9:841-848, 1961.
Graham, R., "Bounds for Certain Multiprocessor Anomalies", Bell System Technical Journal, 45, pp. 1563-1581, 1966.
Leung, J. Y. T., Vornberger, O., and Witthoff, J., "On Some Variants of the Bandwidth Minimization Problem", SIAM J. Computing, 13:650-667, 1984.
Bruno, J., Jones III, J. W., and So, K., "Deterministic Scheduling with Pipelined Processors", IEEE Trans., pp. 308-316, 1980.
Bernstein, D. and Gertner, I., "Scheduling Expressions on a Pipelined Processor with a Maximal Delay of One Cycle", ACM Trans. on Programming Languages and Systems, 11(1):57-66, Jan. 1989.
Palem, K. V., and Simons, B., "Scheduling Time-Critical Instructions on RISC Machines", Transactions on Programming Languages (TOPLAS), 15, No. 4, pp. 632-658, 1993.
Lawler, E., Lenstra, J. K., Martel, C., Simons, B., and Stockmeyer, L., "Pipeline Scheduling: A Survey", Technical Report RJ 5738, IBM Research, Jul. 1987.
Ebcoiglu, K., "A Compilation Technique for Software Pipelining of Loops with Conditonal Jumps", Proc. of the 20th Annual ACM Workshop on Microprocessing, pp. 69-79, Dec. 1987.
Hennessy, J. and Gross, T., "Postpass Code Optimization of Pipeline Constraints", ACM Trans. on Programming Languages and Systems, 5(3):422-448, Jul. 1983.
Gibbons, P. B. and Muchnick, S. S., "Efficient Instruction Scheduling for a Pipelined Architecture", Proc. SIGPLAN'86 Symp. on Compiler Construction, pp. 11-16, Jun. 1986, Published as SIGPLAN Notices vol. 21, No. 7.
Auslander, M. and Hopkins, M., "An Overview of the PL.8 Compiler", Proc. SIGPLAN'82 Symp. on Compiler Construction, pp. 22-31, Jun. 1982, Published as SIGPLAN Notices vol. 17, No. 6.
Warren, H., "Instruction Scheduling for the IBM RISC System/6000 Processor", IBM J. Research and Development, pp. 85-92, 1990.
Bernstein, D. and Rodeh, M., "Global Instruction Scheduling for Superscalar Machines", SIGPLAN91, pp. 241-255, 1991.
Fisher, J. A., "Trace Scheduling: a Technique for Global Microcode Compaction", IEEE Tran. on Computers, C-30 (7):478-490, Jul. 1981.
Palem, K. V., and Simons, B., "Instruction Scheduling for Compilers", IBM Research Report 8535, Dec., 1991.
Bernstein, D., Rodeh, M. and Gertner, I., "Approximation Algorithms for Scheduling Arithmetic Expressions on Pipelined Machines", J. of Algorithms, 10:120-139, Mar. 1989.
Bernstein, D., Cohen D., Lavon, Y. and Raimish V., Performance Evaluation of Instruction Scheduling on the IBM RISC System/6000, SIGMICRO Newsl. (USA), vol. 23, No. 1-2, Dec. 1992, pp. 226-235.
Sarkar Vivek
Simons Barbara Bluestein
International Business Machines - Corporation
Johnson Prentiss W.
Kim Kenneth S.
LandOfFree
System, method, and program product for instruction scheduling i does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method, and program product for instruction scheduling i, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and program product for instruction scheduling i will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2135581