Access Restriction

Author Ramamoorthy, C. V. ♦ Gonzalez, M. J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Arithmetic expressions ♦ Subexpression ordering ♦ Parallel processing ♦ Computational trees ♦ Cache ♦ Compilers
Abstract An arithmetic expression can often be broken down into its component subexpressions. Depending on the hardware environment in which the expression is to be executed, these subexpressions can be evaluated in serials, in parallel, or in a combination of these modes. This paper shows that expression execution time can be minimized only if consideration is given to the ordering of the subexpressions. In particular, subexpressions should be executed in order of decreasing memory and processor time requirements. This observation is valid for configurations ranging from a uniprocessor with an unbuffered main memory to a multiprocessor with a “cache” buffer memory. If the number of subexpressions which can be executed in parallel exceeds the number of available processors, then execution of some of these subexpressions must be postponed. A procedure is given which combines this requirement with the earlier ordering considerations to provide an optimal execution sequence.
Description Affiliation: Univ. of Texas at Austin (Ramamoorthy, C. V.; Gonzalez, M. J.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 14
Issue Number 7
Page Count 7
Starting Page 479
Ending Page 485

Open content in new tab

   Open content in new tab
Source: ACM Digital Library