EXPLORER: Supporting run-time parallelization of DOACROSS loops on generalnetworks of workstations

Performing run-time parallelization on general networks of workstations (NO Ws) without special hardware or system software supports is very difficult, especially for DOACROSS loops. Parallelizing DOACROSS loops at run time im plies complex operations for dependence detection, data accesses, and compu tation scheduling, which is hard to do systematically and could induce a la rge amount of messages. With the high communication overhead on NOWs, there is hardly any performance gain for run-time parallelization of DOACROSS lo ops. This paper proposes a general methodology for run-time parallelization of DOACROSS loops on NOWs, The methodology is realized by a portable run-t ime environment called EXPLORER, which can be implemented entirely at the u ser level. EXPLORER hides the communication overhead as much as possible th rough multithreading - a facility supported in almost all workstations. Con siderations involved in the design of EXPLORER and its general organization will be introduced. Preliminary performance of EXPLORER will be presented and discussed. Performance measured on an implementation of EXPLORER on eig ht DEC Alpha workstations connected through a 10-Mbps Ethernet shows that t he computation to communication ratio plays an important role and the exten t to which multithreading can hide the communication overhead is limited. T hus EXPLORER is more suitable for coarse-grain computations. (C) 2000 Elsev ier Science B.V. All rights reserved.