article

ILP-based Instruction Scheduling for IA-64

Authors:

Daniel Kästner,

Sebastian WinkelAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 8

Pages 145 - 154

https://doi.org/10.1145/384196.384217

Published: 01 August 2001 Publication History

Abstract

The IA-64 architecture has been designed as a synthesis of VLIW and superscalar design principles. It incorporates typical functionality known from embedded processors as multiply/accumulate units and SIMD operations for 3D graphics operations. In this paper we present an ILP formulation for the problem of instruction scheduling for IA-64. In order to obtain a feasible schedule it is necessary to model the data dependences, resource constraints as well as additional encoding restrictions—the bundling mechanism. These different aspects represent subproblems that are closely coupled which gives the motivation for a modeling based on integer linear programming. The presented approach is divided in to two phases which allows us to compute mostly optimal solutions with acceptable computation time.

References

[1]

D. K.astner, Retargetable Code Optimisation by Integer Linear Programming. PhD thesis, Saarland University, 2000.

[2]

E. Johnson, G. Nemhauser, and M. Savelsbergh, "Progress in Integer Programming: An Exposition," Tech. Rep. LEC-97-02, Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta, CA 30332-0205, Jan. 1997. http://tli.isye.gatech.edu/reports.html.

[3]

M. Garey and D. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann and Company, 1979.

Digital Library

[4]

S. Chaudhuri, R. Walker, and J. Mitchell, "Analyzing and Exploiting the Structure of the Constraints in the ILP-Approach to the Scheduling Problem," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 2, pp. 456-471, Dec. 1994.

Digital Library

[5]

F. Eisenbrand, Gomory-Chvatal Cutting Planes and the Elementary Closure of Polyhedra. PhD thesis, Saarland University, 2000.

[6]

C. Gebotys and M. Elmasry, "Global Optimization Approach for Architectural Synthesis," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 1266-1278, 1993.

Digital Library

[7]

C. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Algorithms and Complexity. Englewood Cliffs: Prentice-Hall, 1982.

Digital Library

[8]

G. Nemhauser and L. Wolsey, "Integer Programming," in Handbooks in Operations Research and Management Science (G. Nemhauser, A. R. Kan, and M. Todd, eds.), ch. VI, pp. 447-527, Amsterdam; New York; Oxford: North-Holland, 1989.

Digital Library

[9]

D. K.astner and R. Wilhelm, "Operations Research Methods in Compiler Backends," Journal of Mathematical Communications, 1999.

[10]

Intel, http://www.intel.com/ia64, IA-64 Architecture Software Developer's Manual, Volume 1: IA-64 Application Architecture, Revision 1.1, July 2000.

[11]

Intel, http://www.intel.com/ia64, Itanium Processor Microarchitecture Reference for Software Optimization, Aug. 2000.

[12]

H. Sharangpani, "Itanium Processor Microarchitecture Overview," Microprocessor Forum (Slides), Oct. 1999.

[13]

C. Hwang, J. Lee, and Y. Hsu, "A Formal Approach tothe Scheduling Problem in High Level Synthesis," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, no. 4, pp. 464-475, 1991.

[14]

A. Bachmann, M. Sch.obinger, and L. Thiele, "Synthesis of Domain Specific Multiprocessor Systems including Memory Design," in VLSI Signal Processing VI, (New York), pp. 417-425, IEEE Press, 1993.

[15]

C. Gebotys and M. Elmasry, Optimal VLSI Architectural Synthesis. Kluwer Academic, 1992.

Digital Library

[16]

L. Zhang, SILP. Scheduling and Allocating with Integer Linear Programming. PhD thesis, Saarland University, 1996.

[17]

S. Arya, "An Optimal Instruction Scheduling Model for a Class of Vector Processors," IEEE Transactions on Computers, vol. C-34, Nov. 1985.

[18]

R. Leupers, Retargetable Code Generation for Digital Signal Processors. Kluwer Academic Publishers, 1997.

Digital Library

[19]

P. Marwedel and G. Goossens, Code Generation for Embedded Processors. Boston; London; Dortrecht: Kluwer, 1995.

Digital Library

[20]

M. Heffernan, J. Liu, and K. Wilken, "Optimal Instruction Scheduling Using Integer Programming," Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pp. 121-133, June 2000.

Digital Library

[21]

J. Bharadwaj and C. McKinsey, "Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs," Journal of Instruction-Level Parallelism, vol. 1, no. 6, pp. 1-6, 2000.

[22]

C. Ferdinand, Cache Behavior Prediction for Real-Time Systems. PhD thesis, Saarland University, 1997.

[23]

J. Park and M. Schlansker, "On Predicated Execution," Tech. Rep. HPL-91-58, Hewlett-Packard Laboratories, Palo Alto CA, May 1991.

[24]

J. Dehnert and R. Towle, "Compiling for the Cydra 5," The Journal of Supercomputing, vol. 1/2, pp. 181-228, May 1993.

Digital Library

[25]

J. Harrison, T. Kubaska, S. Story, andP. Tang, "The Computation of Transcendental Functions on the IA-64 Architecture," Intel Technology Journal, vol. Q4, 1999.

Cited By

Zhang LQiu MSha EZhuge Q(2011)Variable assignment and instruction scheduling for processor with multi-module memoryMicroprocessors & Microsystems10.1016/j.micpro.2010.12.00235:3(308-317)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.micpro.2010.12.002
Govindarajan R(2009)Instruction SchedulingThe Compiler Design Handbook10.1201/9781420043839.ch19(19-1-19-57)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch19
Qiu MZhang LSha ERosenstiel WWakabayashi K(2009)ILP optimal scheduling for multi-module memoryProceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1629435.1629473(277-286)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629435.1629473
Show More Cited By

Index Terms

ILP-based Instruction Scheduling for IA-64

Recommendations

ILP-based Instruction Scheduling for IA-64
LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems

The IA-64 architecture has been designed as a synthesis of VLIW and superscalar design principles. It incorporates typical functionality known from embedded processors as multiply/accumulate units and SIMD operations for 3D graphics operations. In this ...
ILP-based Instruction Scheduling for IA-64
OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems

The IA-64 architecture has been designed as a synthesis of VLIW and superscalar design principles. It incorporates typical functionality known from embedded processors as multiply/accumulate units and SIMD operations for 3D graphics operations. In this ...
The IA-64 Architecture at Work

Over the past several years, strategies to increase microprocessor performance have focused on finding more instruction-level parallelism. ILP is basically the idea of finding several instructions to execute at the same time. By providing multiple ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Published in SIGPLAN Volume 36, Issue 8

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
818
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang LQiu MSha EZhuge Q(2011)Variable assignment and instruction scheduling for processor with multi-module memoryMicroprocessors & Microsystems10.1016/j.micpro.2010.12.00235:3(308-317)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.micpro.2010.12.002
Govindarajan R(2009)Instruction SchedulingThe Compiler Design Handbook10.1201/9781420043839.ch19(19-1-19-57)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch19
Qiu MZhang LSha ERosenstiel WWakabayashi K(2009)ILP optimal scheduling for multi-module memoryProceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis10.1145/1629435.1629473(277-286)Online publication date: 11-Oct-2009
https://dl.acm.org/doi/10.1145/1629435.1629473
Malik AChase MRussell TBeek P(2008)An Application of Constraint Programming to Superblock Instruction SchedulingProceedings of the 14th international conference on Principles and Practice of Constraint Programming10.1007/978-3-540-85958-1_7(97-111)Online publication date: 14-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85958-1_7
Anckaert BVandeputte FDe Bus BDe Sutter BDe Bosschere K(2004)Link-Time Optimization of IA64 BinariesEuro-Par 2004 Parallel Processing10.1007/978-3-540-27866-5_37(284-291)Online publication date: 2004
https://doi.org/10.1007/978-3-540-27866-5_37
Kolli APelley SSaidi AChen PWenisch T(2016)High-Performance Transactions for Persistent MemoriesACM SIGPLAN Notices10.1145/2954679.287238151:4(399-411)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2954679.2872381
Zhou MDu YChilders BMosse DMelhem R(2016)Symmetry-Agnostic Coordinated Management of the Memory Hierarchy in Multicore SystemsACM Transactions on Architecture and Code Optimization10.1145/284725412:4(1-26)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1145/2847254
Yazdanbakhsh APekhimenko GThwaites BEsmaeilzadeh HMutlu OMowry T(2016)RFVPACM Transactions on Architecture and Code Optimization10.1145/283616812:4(1-26)Online publication date: 6-Jan-2016
https://dl.acm.org/doi/10.1145/2836168
Perez INilsson H(2015)Bridging the GUI gap with reactive values and relationsACM SIGPLAN Notices10.1145/2887747.280431650:12(47-58)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2887747.2804316
Oliveira BMu SYou S(2015)Modular reifiable matching: a list-of-functors approach to two-level typesACM SIGPLAN Notices10.1145/2887747.280431550:12(82-93)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2887747.2804315
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents