Name
Abstract | ||
|---|---|---|
This paper addresses the compile-time optimization of a class of nested-loop computations that arise in some computational physics applications. The computations involve summations over products of array terms in order to compute multi-dimensional surface and volume integrals. Reordering additions and multiplications and applying the distributive law can significantly reduce the number of operations required in evaluating these summations. In a multiprocessor environment, proper distribution of the arrays among processors will reduce the inter-processor communication time. We present a formal description of the operation minimization problem, a proof of its NP- completeness, and a pruning strategy for finding the optimal solution in small cases. We also give an algorithm for determining the optimal distribution of the arrays among processors in a multiprocessor environment. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/BFb0017261 | LCPC |
Keywords | Field | DocType |
optimal reordering,parallel execution,distributive law,nested loops | Minimization problem,Distributive property,Volume integral,Computer science,Formal description,Theoretical computer science,Optimizing compiler,Distributed computing,Computation,Parallel computing,Algorithm,Multiprocessing,Nested loop join | Conference |
ISBN | Citations | PageRank |
3-540-63091-0 | 5 | 0.62 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chi-Chung Lam | 1 | 172 | 12.67 |
| P. Sadayappan | 2 | 4821 | 344.32 |
| Rephael Wenger | 3 | 441 | 43.54 |