article

Free access

Efficient formulation for optimal modulo schedulers

Authors:

Alexandre E. Eichenberger,

Edward S. DavidsonAuthors Info & Claims

ACM SIGPLAN Notices, Volume 32, Issue 5

Pages 194 - 205

https://doi.org/10.1145/258916.258933

Published: 01 May 1997 Publication History

Abstract

Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach increasingly suffers from large execution times. In this paper, we propose a more efficient formulation of the modulo scheduling space that significantly decreases the execution time of solvers based on integer linear programs. For example, the total execution time is reduced by a factor of 8.6 when 782 loops from the Perfect Club, SPEC, and Livermore Fortran Kernels are scheduled for minimum register requirements using the more efficient formulation instead of the traditional formulation. Experimental evidence further indicates that significantly larger loops can be scheduled under realistic machine constraints.

References

[1]

B. R. Rau and C. D. Glaeser. Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. Fourteenth Annual Workshop on Microprogramming, pages 183- 198, October 1981.

Digital Library

[2]

P. Y. Hsu. Highly Concurrent Scalar Processing. PhD thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, 1986.

Digital Library

[3]

B. R. Rau. Iterative Modulo Scheduling: An algorithm for software pipelining loops. Proceedings of the ~7th Annual International Symposium on Microarchitecture, pages 63-74, November 1994.

Digital Library

[4]

A. E. Eichenberger, E. S. Davidson, and S. G. Abraham. Optimum modulo schedules for minimum register requirements. Proceedings of the international Conference on Superwmputing, pages 31-40, July 1995.

Digital Library

[5]

E. R. Altman, R. Govindarajan, and G. R. Gao. Scheduling and mapping: Software pipelining in the presence of structural hazards. In Proceedings of the A CM SIGPLAN'95 Conference on Programming Language Design and implementation, pages 139-150, 1995.

Digital Library

[6]

J. R. Ruttenberg, G. R. Gao, and A. Stoutchinin. Software pipelining showdown: Optimal vs. heuristic methods in a production compiler. Proceedings of the A CM $IGPLAN'96 Conference on Programming Language Design and implementation, pages 1-11, May 1996.

Digital Library

[7]

R. Govindarajan, E. R. Altman, and G. R. Gao. Minimizing register requirements under resourceconstrained rate-optimal software pipelining. Proceed. ings of the ~Tth Annual International Symposium on Microarchitecture, pages 85-94, November 1994.

Digital Library

[8]

B. R. Rau. Iterative Modulo Scheduling. International Journal of Parallel Programming, 24(1):2-64, 1996.

Digital Library

[9]

A. E. Eichenberger said E. S. Davidson. Stage scheduling: A technique to reduce the register requirements of a modulo schedule. Proceedings of the 28th Annual international Symposium on Microarchitecture, pages 180-191, November 1995.

Digital Library

[10]

A. E. Eichenberger. Modulo Scheduling, Machine Representations, and Register-Sensitive Algorithms. PhD thesis, University of Michigan, Department of Electrical Engineering and Computer Science, Ann Arbor, MI, 1996.

Digital Library

[11]

A. E. Eichenberger, E. S. Davidson, and S. G. Abraham. Minimum register requirements for a modulo schedule. P~ings of the 2Tth Annual International Symposium on Microarehitecture, pages 75-84, November 1994.

Digital Library

[12]

R. A. Huff. Lifetime-sensitive modulo scheduling. Proceedings of the A CM SiGPLAN'93 Conference on Programming Language Design and Implementation, pages 258-267, June 1993.

Digital Library

[13]

G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. Wiley, New York, 1988.

Digital Library

[14]

S. Chaudhuri, R. A. Walker, and J. E. Mitchell. Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem. IEEE Transactions on Very Large Scale Integration Systems, 2(4):456-471, December 1994.

Digital Library

[15]

B. Dupont de Dinechin. Parametric computation of margins and of minimum cumulative register lifetime dates. Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, 1996.

Digital Library

[16]

B. Dupont de Dinechin. Simplex scheduling: More than lifetime-sensitive instruction scheduling. Proceedings of the International Conference on Parallel Architecture and Compiler Techniques, pages 327-330, 1994.

Digital Library

[17]

M. Berry et al. The Perfect Club Benchmarks: Effective performance evaluation of supercomputers. The International Journal of Supercomputer Applications, 3(3):5-40, Fall 1989.

Digital Library

[18]

J. Uniejewski. SPEC Benchmark Suite: Designed for today's advanced system. SPEC Newsletter, Fall 1989.

[19]

F. H. McMahon. The Livermore Fortran Kernels: A computer test of the numerical performance range. Technical Report UCRL-53745, Lawrence Livermore National Laboratory, Livermore, California, 1986.

[20]

J. C. Dehnert and R. A. Towle. Compiling for the Cydra 5. In The Journal of Supercomputing, volume 7, pages 181-227, 1993.

Digital Library

[21]

G. R. Beck, D. W. L. Yen, and T. L. Anderson. The Cydra 5 mini-supercomputer: Architecture and implementation. In The Journal of Supercomputing, volume 7, pages 143-180, 1993.

Digital Library

[22]

A. E. Eichenberger and E. S. Davidson. A reduced mulo tipipeline machine description that preserves scheduling constraints. Proceedings of the A CM SIGPLAN'96 Conference on Programming Language Design and Implementation, pages 12-22, May 1996.

Digital Library

Cited By

Fiege NSittel PZipf P(2022)Optimal Binding and Port Assignment for Loop Pipelining in High-Level Synthesis2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL57034.2022.00047(262-269)Online publication date: Aug-2022
https://doi.org/10.1109/FPL57034.2022.00047
Sittel PWickerson JKuimm MZipf P(2020)Modulo Scheduling with Rational Initiation Intervals in Custom Hardware Design2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC47756.2020.9045616(568-573)Online publication date: Jan-2020
https://doi.org/10.1109/ASP-DAC47756.2020.9045616
Sittel PFiege NKumm MZipf P(2019)Isomorphic Subgraph-based Problem Reduction for Resource Minimal Modulo Scheduling2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig)10.1109/ReConFig48160.2019.8994768(1-8)Online publication date: Dec-2019
https://doi.org/10.1109/ReConFig48160.2019.8994768
Show More Cited By

Index Terms

Efficient formulation for optimal modulo schedulers
1. Mathematics of computing
  1. Mathematical software
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Iterative modulo scheduling: an algorithm for software pipelining loops
MICRO 27: Proceedings of the 27th annual international symposium on Microarchitecture

Modulo scheduling is a framework within which a wide variety of algorithms and heuristics may be defined for software pipelining innermost loops. This paper presents a practical algorithm, iterative modulo scheduling, that is capable of dealing with ...
Efficient formulation for optimal modulo schedulers
PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

Modulo scheduling algorithms based on optimal solvers have been proposed to investigate and tune the performance of modulo scheduling heuristics. While recent advances have broadened the scope for which the optimal approach is applicable, this approach ...
Iterative Modulo Scheduling

Modulo scheduling is a framework within which algorithms for software pipelining innermost loops may be defined. The framework specifies a set of constraints that must be met in order to achieve a legal modulo schedule. A wide variety of algorithms and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 32, Issue 5

May 1997

365 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/258916

Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Marina Chen
Boston Univ., Boston, MA
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Issue’s Table of Contents

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation
May 1997
365 pages
ISBN:0897919076
DOI:10.1145/258915
Chairmen:
Marina Chen
Boston Univ., Boston, MA
,
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

Copyright © 1997 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 May 1997

Published in SIGPLAN Volume 32, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
551
Total Downloads

Downloads (Last 12 months)91
Downloads (Last 6 weeks)22

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fiege NSittel PZipf P(2022)Optimal Binding and Port Assignment for Loop Pipelining in High-Level Synthesis2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL57034.2022.00047(262-269)Online publication date: Aug-2022
https://doi.org/10.1109/FPL57034.2022.00047
Sittel PWickerson JKuimm MZipf P(2020)Modulo Scheduling with Rational Initiation Intervals in Custom Hardware Design2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASP-DAC47756.2020.9045616(568-573)Online publication date: Jan-2020
https://doi.org/10.1109/ASP-DAC47756.2020.9045616
Sittel PFiege NKumm MZipf P(2019)Isomorphic Subgraph-based Problem Reduction for Resource Minimal Modulo Scheduling2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig)10.1109/ReConFig48160.2019.8994768(1-8)Online publication date: Dec-2019
https://doi.org/10.1109/ReConFig48160.2019.8994768
Hanen CMunier-Kordon A(2019)Cyclic Data Flows in Computers and Embedded SystemsModelling and Performance Analysis of Cyclic Systems10.1007/978-3-030-27652-2_1(3-29)Online publication date: 17-Aug-2019
https://doi.org/10.1007/978-3-030-27652-2_1
Sittel PKumm MOppermann JMoller KZipf PKoch A(2018)ILP-Based Modulo Scheduling and Binding for Register Minimization2018 28th International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2018.00053(265-2656)Online publication date: Aug-2018
https://doi.org/10.1109/FPL.2018.00053
Hanzalek ZHanen C(2018)The impact of core precedences in a cyclic RCPSP with precedence delaysJournal of Scheduling10.1007/s10951-014-0399-418:3(275-284)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-014-0399-4
Bonfietti A(2016)A constraint programming scheduling solver for the MPOpt programming environmentIntelligenza Artificiale10.3233/IA-16009510:1(65-77)Online publication date: 4-Jun-2016
https://doi.org/10.3233/IA-160095
Witterauf MTanase AHannig FTeich J(2016)Modulo scheduling of symbolically tiled loops for tightly coupled processor arrays2016 IEEE 27th International Conference on Application-specific Systems, Architectures and Processors (ASAP)10.1109/ASAP.2016.7760773(58-66)Online publication date: Jul-2016
https://doi.org/10.1109/ASAP.2016.7760773
Bonfietti ALombardi MBenini LMilano M(2014)CROSS cyclic resource-constrained scheduling solverArtificial Intelligence10.1016/j.artint.2013.09.006206(25-52)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.artint.2013.09.006
Touati SDinechin B(2014)BibliographyAdvanced Backend Code Optimization10.1002/9781118625446.biblio(327-343)Online publication date: 3-Jun-2014
https://doi.org/10.1002/9781118625446.biblio
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents