Synthesis of algorithms on processor arrays

✍ Scribed by Gen-Huey Chen; Maw-Sheng Chern

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 289 KB
• Volume: 17
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(05)80113-9

✦ Synopsis

Chen, G.-H. and M.-S. Chern, Synthesis of algorithms on processor arrays, Parallel Computing 17 (1991)

279-284

The data dependence graph is very useful to parallel algorithm design. In this paper, approaches are introduced to map two classes of data dependence graphs, the regular graphs and the semi-regular graphs, onto processor arrays. The arcs of the regular graphs can be specified by a set of deterministic dependence vectors; the arcs of the semi-regular graphs can be specified by a set of nondeterministic dependence vectors. The regular graphs are a restricted class of the semi-regular graphs, while the data dependence graphs of the nested loop statements dealt with by Moldovan and Fortes fall into the class of the regular graphs. The proposed approaches design parallel algorithms directly from deterministic dependence vectors and nondeterministic dependence vectors.