Electrical computers and digital processing systems: processing – Processing architecture – Distributed processing system
Patent
1997-06-23
2000-03-28
Hafiz, Tariq R.
Electrical computers and digital processing systems: processing
Processing architecture
Distributed processing system
395706, 712237, 712207, 712238, 712241, 712233, G06F 944
Patent
active
060442220
ABSTRACT:
Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A start node simulating a previous iteration of the loop may be added to the dependence graph, and an end node simulating a next iteration of the loop may also added to the dependence graph. A loop-independent edge between a source node and the start node is added to the dependence graph, and a loop-independent edge between a sink node and the end node is added to the dependence graph. Loop-carried edges which satisfy a computed lower bound on the time required for a single loop iteration are eliminated from a dependence graph, and loop-carried edges which do not satisfy the computed lower bound are replaced by a pair of loop-independent edges. Instructions may be scheduled for execution based on the dependence graph.
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: 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.
patent: 5867683 (1999-02-01), Witt et al.
patent: 5887174 (1999-03-01), Simons 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.
Ebcioglu, K., "A Compilation Technique for Software Pipelining of Loops with Conditional Jumps", Proc. of the 20th Annual ACM Workshop on Microprocessing, pp. 69-79, Dec. 1987.
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 Trans. on Computers, C-30(7):478-490, Jul. 1981.
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.
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, p. 226-235.
Leung et al, "Run-time versus compile-time instruction scheduling in superscalar (RISC) processors: performance and tradeoffs," Proceedings of the 3rd International Conference on High Performance Computing Dec. 1996, pp. 215-224.
Boo et al, "High-speed Viterbi decoder: an efficient scheduling method to exploit the pipelining," ASAP 96, Proceedings of International Conference on Application Specific Systems, Architectures and Processors, pp. 165-174, Aug. 1996.
Chen et al, "Performance evaluation of buffered multistage interconnection networks with look-ahead contention resolution scheme," ICC '95 Seattle, `Gateway to Globalization`, Jun. 1995 IEEE International Conference on Communications, vol. 2, pp. 1137-1141.
Barrado et al, "An efficient Scheduling for Doacross Loops," Proceedings of the Sixth IASTED/ISMM International Conference on Parallel and Distributed Computing and Systems, Washington DC, USA, Oct. 3-5, 1994, pp. 303-307.
Wang et al, "Decomposed Software Pipelining with Reduced register Requirement," Proceedings of the IFIP WG10.3 Working Conference PACT '95 on Parallel Architecture and Compilation Techniques, Laxenburg, Austria, Jun. 27-29, 1995, pp. 277-280.
Sarkar Vivek
Simons Barbara Bluestein
Dam Tuan Q.
Hafiz Tariq R.
International Business Machines - Corporation
Johnson Prentiss W.
LandOfFree
System, method, and program product for loop instruction schedul 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 loop instruction schedul, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method, and program product for loop instruction schedul will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1333650