Scheduling Arithmetic and Load Operations in Parallel with No Spilling
Authors:
- David BernsteinDBDavid Bernstein
- Jeffrey M. JaffeJJJeffrey M. Jaffe
- Michael RodehMRMichael Rodeh
- 1 December 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (6) , 1098-1127
Abstract
A machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units is considered. For this model, the evaluation of a set of expression trees is discussed. A dynamic programming algorithm for producing an approximate solution is described and analyzed. For binary trees its worse-case cost is at most $\min (1.091,1 + {{(2\log n)} / n})$ times the optimal cost.
Keywords
This publication has 11 references indexed in Scilit:
- Optimal scheduling of arithmetic operations in parallel with memory access (preliminary version)1985
- VLSI Processor ArchitectureIEEE Transactions on Computers, 1984
- The 801 MinicomputerIBM Journal of Research and Development, 1983
- The CRAY-1 computer systemCommunications of the ACM, 1978
- Code Generation for Expressions with Common SubexpressionsJournal of the ACM, 1977
- Optimal Code Generation for Expression TreesJournal of the ACM, 1976
- Code Generation for a One-Register MachineJournal of the ACM, 1976
- The Generation of Optimal Code for Arithmetic ExpressionsJournal of the ACM, 1970
- On arithmetic expressions and treesCommunications of the ACM, 1969
- On compiling algorithms for arithmetic expressionsCommunications of the ACM, 1967