Article

Free access

Scheduling arithmetic and load operations in parallel with no spilling

Authors:

D. Bernstein,

J. M. Jaffe,

M. RodehAuthors Info & Claims

POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Pages 263 - 273

https://doi.org/10.1145/41625.41649

Published: 01 October 1987 Publication History

PDF eReader

Abstract

We consider a machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm to produce an approximate solution is described and analyzed. For binary trees its worse case cost is at most 9.1% worse than the optimal cost.

References

[1]

Aho, A.V., and Johnson, S.C., "Optimal code generation for expression trees", JA CM 23, 3 (Jul. 1976), 488- 501.

Digital Library

Google Scholar

[2]

Aho, A.V., Johnson, S.C., and Ullman, J.D. "Code generation for expression with common subexpressions", JACM 24, 1 (Jan. 1977), 146-160.

Digital Library

Google Scholar

[3]

Aho, A.V., Johnson, S.C., and Ullman, J.D. ~Code generation for machines with multiregister operations", Proceedings of the Fourth A CM S)'mposium on Principles of Programming Languages, (Jan. 1977), 21-28.

Digital Library

Google Scholar

[4]

Bernstein, D., Jaffe, J.M.~ Pinter, R.Y., and Rodeh, M., "Optimal scheduling of arithmetic operations in parallel with memory access~, TR 88.136, IBM-Israel Scientific Center (May 1985). A preliminary version has appeared in the Proceedings of the Twelfth A CM Symposium on Principles of Programming Languages, (Jan. 1985), 325-333.

Digital Library

Google Scholar

[5]

Bruno, J.L., and Sethi, R. "Code generation for a one-register machine", JACM 23.3 (July 1976). 502-510.

Digital Library

Google Scholar

[6]

Hennessy, J.L., "VLSI processor architecture", lEEk," Transactions on Computers, (Dec. 1984), 1221-1246.

Digital Library

Google Scholar

[7]

Hwang, K., and Briggs, F.A., Computer architecture and parallel processing. McGraw'-Hill, New York, 1984.

Digital Library

Google Scholar

[8]

Nakata, I., "On Compiling algorithms for arithmetic expressions", Comm. A CM 18, 8 (Aug. 1967), 492-494.

Digital Library

Google Scholar

[9]

Radin, G., "The 801 minicomputer", IBM J. on R&D 27. 3 (May 1983), 237-246.

Digital Library

Google Scholar

[10]

Redziejowski, R.R. "On Arithmetic expressions and trees", Comm. ACM 12. 2 (Feb. 1969), 81-84.

Digital Library

Google Scholar

[11]

Russell, R.M., "The Cray-I computer system", CoJ~m~. ACM 21, 1 (Jan. 1978), 63-72.

Digital Library

Google Scholar

[12]

Sethi, R., and Ullman, J.D., "The generation of optimal code for arithmetic expressions". JACM 17, 4 (Oct. 1970). 715-728.

Digital Library

Google Scholar

Cited By

View all

Eisenbeis CGasperoni FSchwiegelshohn UBic LEvripidou PBöhm WGaudiot J(1995)Allocating registers in multiple instruction-issuing processorsProceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques10.5555/224659.224948(290-293)Online publication date: 27-Jun-1995
https://dl.acm.org/doi/10.5555/224659.224948
Bernstein DRodeh MGertner I(1989)On the Complexity of Scheduling Problems for Parallel/Pipelined MachinesIEEE Transactions on Computers10.1109/12.2946938:9(1308-1313)Online publication date: 1-Sep-1989
https://dl.acm.org/doi/10.1109/12.29469
Bernstein DBoral HPinter R(1988)Optimal Chaining in Expression TreesIEEE Transactions on Computers10.1109/12.870237:11(1366-1374)Online publication date: 1-Nov-1988
https://dl.acm.org/doi/10.1109/12.8702

Index Terms

Recommendations

Bit-Parallel Arithmetic in a Massively-Parallel Associative Processor

A simple but powerful architecture based on the classical associative processor model is proposed. By distributing logic among slices of storage cells such that a number of bit-planes share a simple logic unit, bit-parallel arithmetic for massively ...
On Runtime Parallel Scheduling for Processor Load Balancing

Parallel scheduling is a new approach for load balancing. In parallel scheduling, all processors cooperate to schedule work. Parallel scheduling is able to accurately balance the load by using global load information at compile-time or runtime. It ...
Load scheduling: reducing pressure on distributed register files for free
ASP-DAC '08: Proceedings of the 2008 Asia and South Pacific Design Automation Conference

In this paper we describe load scheduling, a novel method that balances load among register files by residual resources. Load scheduling can reduce register pressure for clustered VLIW processors with distributed register files while not increasing VLIW ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '87: Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

October 1987

326 pages

ISBN:0897912152

DOI:10.1145/41625

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 October 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL87

Sponsor:

SIGPLAN

POPL87: Fourteenth Annual ACM SIGACT-SIGPLAN Symposium on Prnciples of Programming Languages

January 21 - 23, 1987

Munich, West Germany

Acceptance Rates

POPL '87 Paper Acceptance Rate 29 of 108 submissions, 27%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
259
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Eisenbeis CGasperoni FSchwiegelshohn UBic LEvripidou PBöhm WGaudiot J(1995)Allocating registers in multiple instruction-issuing processorsProceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques10.5555/224659.224948(290-293)Online publication date: 27-Jun-1995
https://dl.acm.org/doi/10.5555/224659.224948
Bernstein DRodeh MGertner I(1989)On the Complexity of Scheduling Problems for Parallel/Pipelined MachinesIEEE Transactions on Computers10.1109/12.2946938:9(1308-1313)Online publication date: 1-Sep-1989
https://dl.acm.org/doi/10.1109/12.29469
Bernstein DBoral HPinter R(1988)Optimal Chaining in Expression TreesIEEE Transactions on Computers10.1109/12.870237:11(1366-1374)Online publication date: 1-Nov-1988
https://dl.acm.org/doi/10.1109/12.8702

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.

Cited By

Index Terms

Recommendations

Bit-Parallel Arithmetic in a Massively-Parallel Associative Processor

On Runtime Parallel Scheduling for Processor Load Balancing

Load scheduling: reducing pressure on distributed register files for free