article

Open access

Postpass Code Optimization of Pipeline Constraints

Editor: Susan L. Graham Authors:

John L. Hennessy,

Thomas GrossAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 5, Issue 3

Pages 422 - 448

https://doi.org/10.1145/2166.357217

Published: 01 July 1983 Publication History

PDF eReader

References

[1]

AHO, A.V., JOHNSON, J.C., AND ULLMAN, J.D. Code generation for expressions with common subexpressions, j. ACM 24, 1 (Jan. 1977), 146-160.

Crossref

Google Scholar

[2]

AHO, A.V., AND ULLMAN, J.D. Principles of Compiler Design. Addison-Wesley, Reading, Mass., 1977.

Crossref

Google Scholar

[3]

ALLEN, F.E., AND COCKE, J. A catalogue of optimizing transformations, in Design and Optimization of Compilers, R. Rustin (Ed.). Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 1-30.

Google Scholar

[4]

ANDERSON, D.W., SPARACIO, F.J., AND TOMASULO, R.M. The IBM System/360 Model 91: Machine philosophy and instruction handling. IBM J. Res. Dev. 11, 1 (Jan. 1967), 8-24.

Google Scholar

[5]

AUSLANDER, M., AND HOPKINS, M. An overview of the PL.8 compiler. In Proceedings of the SIGPLAN '82 Sym~)osium on Compiler Construction, Boston, June 23-25, 1982, pp. 22-31.

Crossref

Google Scholar

[6]

BASKETT, F. Puzzle: An informal compute bound benchmark. Unpublished.

Google Scholar

[7]

BEATTY, J. An axiomatic approach to code optimization for expressions. J. ACM 19, 4 (Oct. 1972), 613-640; errata, J. ACM 20, 1 (Jan. 1973), 188; erratum, j. ACM 20, 3 (July 1973), 538.

Crossref

Google Scholar

[8]

DAVIDSON, S., LANDSKOV, D., SHRIVER, B.D., AND MALLETT, P.W. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Comput. C-30, 7 (July 1981), 460-477.

Google Scholar

[9]

DAVIES, K., ANO RIs, F. Real-time signal processor support software. IBM J. Res. Dev. 26, 4 (July 1982), 431-439.

Google Scholar

[10]

DENNINO, P.J. Computer architecture: Some old ideas that haven't quite made it yet. Commun. ACM 24, 9 (Sept. 1981), 553-554.

Crossref

Google Scholar

[11]

FISHER, J.A. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July 1981), 478-490.

Google Scholar

[12]

FISHER, J.A. The optimization of horizontal microcode within and beyond basic blocks. Tech. Rep. COO-3077-161, Courant Mathematics and Computing Laboratory, New York Univ., New York, Oct. 1979.

Google Scholar

[13]

GAREY, M.R., ANO JOHNSON, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979.

Crossref

Google Scholar

[14]

HENNESSY, J. Symbolic debugging of optimized code. ACM Trans. Program. Lang. Syst. 4, 3 (July 1982), 323-344.

Crossref

Google Scholar

[15]

HENNESSY, J.L., ANO GROSS, T.R. Code generation and reorganization in the presence of pipeline constraints. In Conference Record of the 9th Annual ACM Symposium on Principles of Programming Languages, Albuquerque, N.M., Jan. 25-27, 1982, pp. 120-127.

Crossref

Google Scholar

[16]

HENNESSY, J.L., JouPPI, N., GILL, J., BASKETT, F., STRONG, A., GROSS, T.R., ROWEN, C., AND LEONARD, J. The MIPS machine. In Proceedings, IEEE Compcon, San Francisco, Feb. 1982, pp. 2-7.

Google Scholar

[17]

JOHNSON, S.C. A portable compiler: Theory and practice. In Conference Record of the 5th Annual ACM Symposium on Principles of Programming Languages, Tucson, Ariz., Jan. 23-25, 1978, pp. 97-104.

Crossref

Google Scholar

[18]

KOGGE, P.M. The Architecture of Pipelined Computers. McGraw-Hill, New York, 1981.

Google Scholar

[19]

LAMPSON, B.W., MCDANIEL, G.A., AND ORNSTEIN, S.M. An instruction fetch unit for a high performance personal computer. Tech. Rep. CSL-81-1, Xerox PARC, Palo Alto, Calif., Jan. 1981.

Google Scholar

[20]

PATTERSON, D.A., AND DITZEL, D.R. The case for the reduced instruction set computer. Comput. Archit. News (ACM SIGARCH) 8, 6 (Oct. 1980), 25-33.

Crossref

Google Scholar

[21]

PATTERSON, D.A., AND SEQUIN, C.H. RISC I: A reduced instruction set VLSI computer. In Conference Proceedings, The 8th Annual Symposium on Computer Architecture, Minneapolis, Minn., May 12-14, 1981. Comput. Archit. News (ACM SIGARCH) 9, 3 (May 1981), 443-457.

Crossref

Google Scholar

[22]

RADIN, G. The 801 minicomputer. In Proceedings, Symposium on Architectural Support for Programming Languages and Operating Systems, Palo Alto, Calif., Mar. 1-3, 1982. Published as combined issue: Comput. Archit. News (ACM SIGARCH) 10, 2 (Mar. 1982), and SIGPLAN Notices (ACM) 17, 4 (Apr. 1982), 39-47.

Crossref

Google Scholar

[23]

RYMARCZYK, J.W. Coding guidelines for pipelined processors. In Proceedings, Symposium on Architectural Support for Programming Languages and Operating Systems, Palo Alto, Calif., Mar. 1-3, 1982. Published as combined issue: Comput. Archit. News (ACM SIGARCH) 10, 2 (Mar. 1982), and SIGPLAN Notices (ACM) 17, 4 (Apr. 1982), 12-19.

Crossref

Google Scholar

[24]

SITES, R. Instruction ordering for the Cray-1 computer. Tech. Rep. 78-CS-023, Dept. of Computer Science, Univ. of California, San Diego, July 1978.

Google Scholar

[25]

TOKORO, M., TAMURA, E., AND TAKIZUKA, T. Optimization of microprograms. IEEE Trans. Comput. C-30, 7 (July 1981), 491-504.

Google Scholar

[26]

ULLMAN, J.D. Complexity of sequencing problems. In Computer and Job-Shop Scheduling Theory, E.G. Coffman, Jr. (Ed.). Wiley, New York, 1976, pp. 139-164.

Google Scholar

[27]

ULLMAN, J.D. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 3 (June 1975), 384-393.

Google Scholar

[28]

VEODAHL, S. Phase coupling and constant generation in an optimizing microcode compiler. In Proceedings of Micro-15, IEEE, Palo Alto, Calif., Oct. 1982, pp. 125-133.

Crossref

Google Scholar

[29]

WIDOOES, L.C. The S-1 project: Developing high performance digital computers. In Proceedings, IEEE Compcon, San Francisco, Feb. 1980, pp. 282-291.

Google Scholar

[30]

WULF, W.A. Compilers and computer architecture. Computer 14, 7 (July 1981), 41-48.

Google Scholar

Cited By

View all

Maroun ESchoeberl MPuschner P(2024)Predictable and optimized single-path code for predicated processorsJournal of Systems Architecture10.1016/j.sysarc.2024.103214154(103214)Online publication date: Sep-2024
https://doi.org/10.1016/j.sysarc.2024.103214
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Instruction SchedulingEngineering a Compiler10.1016/B978-0-12-815412-0.00018-8(617-662)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00018-8
Show More Cited By

Index Terms

Postpass Code Optimization of Pipeline Constraints

Recommendations

Code optimization of pipeline constraints
Code generation and reorganization in the presence of pipeline constraints
Timing optimization via nest-loop pipelining considering code size

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 5, Issue 3

July 1983

244 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/2166

Editor:
Susan L. Graham

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1983

Published in TOPLAS Volume 5, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

271
Total Citations
View Citations
1,484
Total Downloads

Downloads (Last 12 months)128
Downloads (Last 6 weeks)13

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Maroun ESchoeberl MPuschner P(2024)Predictable and optimized single-path code for predicated processorsJournal of Systems Architecture10.1016/j.sysarc.2024.103214154(103214)Online publication date: Sep-2024
https://doi.org/10.1016/j.sysarc.2024.103214
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Instruction SchedulingEngineering a Compiler10.1016/B978-0-12-815412-0.00018-8(617-662)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00018-8
Cao HGuo SHao JXia YXu J(2022)Superblock-based performance optimization for Sunway Math Library on SW26010 many-core processorThe Journal of Supercomputing10.1007/s11227-021-03997-w78:4(4827-4849)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11227-021-03997-w
Mallach S(2021)A note on labeling methods to schedule unit execution time tasks in the presence of delayed precedence constraintsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.05.002156(1-6)Online publication date: Oct-2021
https://doi.org/10.1016/j.jpdc.2021.05.002
Giesemann FGerlach LPayá-Vayá G(2020)Evolutionary Algorithms for Instruction Scheduling, Operation Merging, and Register Allocation in VLIW CompilersJournal of Signal Processing Systems10.1007/s11265-019-01493-292:7(655-678)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s11265-019-01493-2
Niculaescu O(2019)What's formal software verification?XRDS: Crossroads, The ACM Magazine for Students10.1145/334181525:4(64-65)Online publication date: 9-Jul-2019
https://dl.acm.org/doi/10.1145/3341815
Laput G(2019)Play ballXRDS: Crossroads, The ACM Magazine for Students10.1145/333988225:4(5-7)Online publication date: 9-Jul-2019
https://dl.acm.org/doi/10.1145/3339882
Li GDing YXie YBahar IHerlihy MWitchel ELebeck A(2019)Tackling the Qubit Mapping Problem for NISQ-Era Quantum DevicesProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304023(1001-1014)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304023
Jeon MJeong SCha SOh H(2019)A Machine-Learning Algorithm with Disjunctive Model for Data-Driven Program AnalysisACM Transactions on Programming Languages and Systems10.1145/329360741:2(1-41)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3293607
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Code optimization of pipeline constraints

Code generation and reorganization in the presence of pipeline constraints

Timing optimization via nest-loop pipelining considering code size

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations