Abstract
Instruction scheduling is essential for the efficient operation of today's and tomorrow's processors. It can be stated easily and declaratively as a logic program. Consistency techniques embedded in logic programming enable the efficient solution of this problem.
This paper describes an instruction scheduling program for the Motorola 88100 RISC processor, which minimizes the number of pipeline stalls. The scheduler is written in the constraint logic programming language ARISTO and uses a declarative model of the processor to generate an optimal schedule. The model uses lists of domain variables to represent the pipeline stages and describes the dependencies between instructions by constraints in order to ensure correct scheduling. Although optimal instruction scheduling is NP-complete, the scheduler can be applied to real programs because of the speed gained through consistency techniques.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
David G. Bradlee, Susan J. Eggers, and Robert R. Henry. Integrating register allocation and instruction scheduling for RISCs. In Architectural Support for Programming Languages and Operating Systems, pages 122–131, 1991.
Robert P. Colwell, Robert P. Nix, John J. O'Donnel, David B. Papworth, and Paul K. Rodman. A VLIW architecture for a trace scheduling compiler. IEEE Transactions on Computers, 37(8):318–328, August 1988.
Mehmet Dincbas, Helmut Simonis, and Pascal Van Hentenryck. Solving large combinatorial problems in logic programming. The Journal of Logic Programming, (8):75–93, 1990.
M. Anton Ertl. Coroutining und Constraints in der Logik-Programmierung. Master's thesis, Technische Universität Wien, 1990.
Joseph A. Fischer. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 30(7):478–490, July 1981.
Mahadevan Ganapathi. Prolog based retargetable code generation. Computer Languages, 14(3):193–204, 1989.
J. R. Goodman and W.-C. Hsu. Code scheduling and register allocation in large basic blocks. In International Conference on Supercomputing, 1988.
Phillip B. Gibbons and Steve S. Muchnick. Efficient instruction scheduling for a pipelined architecture. In Proceedings of the SIGPLAN '86 Symposium on Compiler Construction, pages 11–16, 1986.
John Hennessy and Thomas Gross. Postpass code optimization of pipeline constraints. ACM Transactions on Programming Languages and Systems, 5(3):422–448, July 1983.
T. C. Hu. Paralell sequencing and assembly line problems. Operations Research, 9(6):841–848, 1961.
Uwe Kastens. Übersetzerbau. R. Oldenbourg Verlag, München, 1990.
Andreas Krall and Ulrich Neumerkel. The Vienna Abstract Machine. In P. Deransart and J. Maluzyński, editors, Programming Language Implementation and Logic Programming (PLILP'90), pages 121–136. Springer LNCS 456, 1990.
Monica Lam. Software pipelining: An effective scheduling technique for VLIW machines. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation, pages 318–328, 1988.
Roland L. Lee, Alex Y. Kwok, and Fayé A. Briggs. The floating-point performance of a superscalar SPARC processor. In Architectural Support for Programming Languages and Operating Systems, pages 28–37, 1991.
Motorola, Inc. MC88100 RISC Microprocessor User's Manual, second edition edition, 1990.
Bernard Nudel. Consistent labeling problems and their algorithms: Expected complexities and theory-based heuristics. Artificial Intelligence, 21:135–178, 1983.
Pascal Van Hentenryck. Constraint Satisfaction in Logic Programming. Logic Programming Series. The MIT Press, Cambridge, Massachusetts, 1989.
Pascal Van Hentenryck and Mehmet Dincbas. Forward checking in logic programming. In Logic Programming: Proceedings of the Fourth International Conference, pages 229–256, 1987.
D. Waltz. Generating semantic descriptions from drawings of scenes with shadows. Technical report AI271, MIT, 1972.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ertl, M.A., Krall, A. (1991). Optimal instruction scheduling using constraint logic programming. In: Maluszyński, J., Wirsing, M. (eds) Programming Language Implementation and Logic Programming. PLILP 1991. Lecture Notes in Computer Science, vol 528. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54444-5_89
Download citation
DOI: https://doi.org/10.1007/3-540-54444-5_89
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54444-9
Online ISBN: 978-3-540-38362-8
eBook Packages: Springer Book Archive