Skewed partition-theory and practice [parallel programming]

Author

King, Chung-Ta

Author_Institution

Dept. of Comput. Sci., Tsing Hua Univ., Hsinchu, Taiwan

fYear

1991

fDate

11-13 Sep 1991

Firstpage

18

Lastpage

23

Abstract

A study is made of strategies for partitioning nested loop programs on distributed-memory multicomputers. A technique called skewed partition is studied. For certain applications the skewed partition will reduce the amount of synchronization and provide a greater control over the granularity than the commonly used block partition method. To illustrate the idea, two examples, one of image distance transformation and another of solving systems of linear equations, are examined. Results obtained from a 32-node Ncube multicomputer show that the skewed partition improves the performance of these programs more than 50% over the block partition method

Keywords

computerised picture processing; linear algebra; parallel algorithms; parallel programming; programming theory; Ncube multicomputer; distributed-memory multicomputers; granularity; image distance transformation; linear equations; nested loop programs; program partitioning; skewed partition; synchronization; Application software; Communication system control; Computer science; Concurrent computing; Equations; Frequency synchronization; Parallel processing; Parallel programming; Programming profession; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Software and Applications Conference, 1991. COMPSAC '91., Proceedings of the Fifteenth Annual International

Conference_Location

Tokyo

Print_ISBN

0-8186-2152-4

Type

conf

DOI

10.1109/CMPSAC.1991.170146

Filename

170146