Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents a new approach to local instruction scheduling based on integer programming that produces optimal instruction schedules in a reasonable time, even for very large basic blocks. The new approach first uses a set of graph transformations to simplify the data-dependency graph while preserving the optimality of the final schedule. The simplified graph results in a simplified integer program which can be solved much faster. A new integer-programming formulation is then applied to the simplified graph. Various techniques are used to simplify the formulation, resulting in fewer integer-program variables, fewer integer-program constraints and fewer terms in some of the remaining constraints, thus reducing integer-program solution time. The new formulation also uses certain adaptively added constraints (cuts) to reduce solution time. The proposed optimal instruction scheduler is built within the Gnu Compiler Collection (GCC) and is evaluated experimentally using the SPEC95 floating point benchmarks. Although optimal scheduling for the target processor is considered intractable, all of the benchmarks' basic blocks are optimally scheduled, including blocks with up to 1000 instructions, while total compile time increases by only 14%.

REFERENCES

• 1: S. Arya. An Optimal Instruction-Scheduling Model for a Class of Vector Processors. IEEE Transactions on Computers, C-34(11):981-995, November 1985.
• 2: David Bernstein , Izidor Gertner, Scheduling expressions on a pipelined processor with a maximal delay of one cycle, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.57-66, Jan. 1989 [doi>10.1145/59287.59291]
• 3: David Bernstein , Michael Rodeh , Izidor Gertner, On the Complexity of Scheduling Problems for Parallel/Pipelined Machines, IEEE Transactions on Computers, v.38 n.9, p.1308-1313, September 1989 [doi>10.1109/12.29469]
• 4: Robert E. Bixby , Ken Kennedy , Ulrich Kremer, Automatic Data Layout Using 0-1 Integer Programming, Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques, p.111-122, August 24-26, 1994
• 5: C-M Chang, C-M Chen, and C-T King. Using Integer Linear Programming for Instruction Scheduling and Register Allocation in Multi-Issue Processors. Computers and Mathematics with Applications, 34(9):1-14, November 1997.
• 6: Hong-Chich Chou , Chung-Ping Chung, An Optimal Instruction Scheduler for Superscalar Processor, IEEE Transactions on Parallel and Distributed Systems, v.6 n.3, p.303-313, March 1995 [doi>10.1109/71.372778]
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: A. Ertl and A. Krall. Optimal Instruction Scheduling Using Constraint Logic Programming. In Programming Language Implementation and Logic Programming (PLILP). Springer-Verlag, 1991.
• 9: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 10: J. Grossman. Discrete Mathematics. Macmillan, 1990.
• 11: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 12: ILOG. ILOG CPLEX 6.5 User's Manual. ILOG, 1999.
• 13: C. Kessler. Scheduling Expression DAGs for Miniml Register Need. Computer Languages, 24(1):33-53, April 1998.
• 14: Rainer Leupers , Peter Marwedel, Time-constrained code compaction for DSP's, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.112-122, March 1997 [doi>10.1109/92.555991]
• 15: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 16: G. Nemhauser. The Age of Optimization: Solving Large-Scale Real-World Problems. Operations Research, 42(1):5-13, Jan.-Feb. 1994.
• 17: Krishna V. Palem , Barbara B. Simons, Scheduling time-critical instructions on RISC machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.632-658, Sept. 1993 [doi>10.1145/155183.155190]
• 18: Keshav Pingali , Gianfranco Bilardi, Optimal control dependence computation and the Roman chariots problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.462-491, May 1997 [doi>10.1145/256167.256217]
• 19: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 20: M. Savelsbergh. Preprocessing and Probing for Mixed Integer Programming Problems. ORSA Journal of Computing, 6(4):445-454, Fall 1994.
• 21: P. Sweany and S. Beaty. Instruction Scheduling Using Simulated Annealing. In Proc. 3rd International Conference on Massively Parallel Computing Systems (MPCS '98), 1998.
• 22: H. Tomiyama, T. Ishihara, A. Inoue, and H. Yasuura. Instruction Scheduling to Reduce Switching Activity of Off-Chip Buses for Low-Power Systems with Caches. IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, E81-A(12):2621- 2629, December 1998.
• 23: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• 24: Laurence A. Wolesey. Integer Programming. John Wiley &; Sons, Inc., 1998.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Design, Management