TY - GEN
T1 - On the synthesis of parallel programs from tensor product formulas for block recursive algorithms
AU - Gupta, S.
AU - Huang, C. H.
AU - Sadayappan, P.
AU - Johnson, R.
N1 - Funding Information:
1This work was supported in part by DARPA,o rder number 7898, monitored by NIST under grant number 60NANB1D1151, DARPA, order number 7899, monitored by NIST under grant number 60NANB1D1150, and Ohio State UniversityS eed Grant, No. 221337.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - This paper presents a methodology for synthesizing parallel programs for block recursive algorithms such as fast Fourier transforms and Strassen’s matrix multiplication algorithm. A block recursive algorithm is expressed as a tensor product formula which consists of matrix sums, matrix products, direct sums, tensor products, componentwise matrix operations, and stride permutations. These mathematical operations can be mapped to high-level programming language constructs such as iteration, sequential composition, parallel composition, vector operations, and index computation. Translation of a tensor product formula consisting of these primitives into a parallel program involves determination of the proper indexing schemes for the arrays. This paper gives an algorithm to determine the indexing scheme and the code required for the index computation. Various parallel programs can be synthesized by manipulating tensor product formulas to exploit different computational structures. In this paper, we discuss some issues involved in formula manipulation for a particular target machine, the Cray Y-MP.
AB - This paper presents a methodology for synthesizing parallel programs for block recursive algorithms such as fast Fourier transforms and Strassen’s matrix multiplication algorithm. A block recursive algorithm is expressed as a tensor product formula which consists of matrix sums, matrix products, direct sums, tensor products, componentwise matrix operations, and stride permutations. These mathematical operations can be mapped to high-level programming language constructs such as iteration, sequential composition, parallel composition, vector operations, and index computation. Translation of a tensor product formula consisting of these primitives into a parallel program involves determination of the proper indexing schemes for the arrays. This paper gives an algorithm to determine the indexing scheme and the code required for the index computation. Various parallel programs can be synthesized by manipulating tensor product formulas to exploit different computational structures. In this paper, we discuss some issues involved in formula manipulation for a particular target machine, the Cray Y-MP.
UR - http://www.scopus.com/inward/record.url?scp=84888604621&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84888604621&partnerID=8YFLogxK
U2 - 10.1007/3-540-57502-2_52
DO - 10.1007/3-540-57502-2_52
M3 - Conference contribution
AN - SCOPUS:84888604621
SN - 9783540575023
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 264
EP - 280
BT - Languages and Compilers for Parallel Computing - 5th International Workshop, Proceedings
A2 - Banerjee, Utpal
A2 - Gelernter, David
A2 - Nicolau, Alex
A2 - Padua, David
PB - Springer Verlag
T2 - IFIP WG 5.7 International Conference on Advances in Production Management Systems, APMS 2017
Y2 - 3 September 2017 through 7 September 2017
ER -