Abstract
Performing runtime parallelization on general networks of workstations (NOWs) without special hardware or system software supports is very difficult, especially for DOACROSS loops. With the high communication overhead on NOWs, there is hardly any performance gain for runtime parallelization, due to the latter's large amount of messages for dependence detection, data accesses, and computation scheduling. In this paper, we introduce the EXPLORER system for runtime parallelization of DOACROSS and DOALL loops on general NOWs. EXPLORER hides the communication overhead on NOWs through multithreading — a facility supported in almost all workstations. A preliminary version of EXPLORER was implemented on a NOW consisting of eight DEC Alpha workstations connected through an Ethernet. The Pthread package was used to support multithreading. Experiments on synthetic loops showed speedups of up to 6.5 in DOACROSS loops and 7 in DOALL Loops.