Exploring parallel algorithms having no serial analogues
Robert E. Hiromoto · University of North Texas Digital Library (University of North Texas) · 1988
The ordering of data acquisitions in many computational problems is an artifact of algorithms developed for serial computers. Often these serial algorithms are highly parallel and thus are mapped directly onto a parallel processing system. This technique, however, does not fully exploit the additional opportunities provided by the system's parallelism. The design of optimal parallel algorithms requires new and different techniques and insights. Unfortunately, parallel performance can still be degraded even with optimal parallel algorithms that preserve the ordering of data access (that is, the data dependences between different computational code blocks) by synchronization primitives, such as locks, events, and barriers. Furthermore, additional decreases in performance are introduced by the various hardware/software components integrated to coordinate the particular parallel processing system. An alternative approach to the class of parallel iterative algorithms is to ignore the ordering of data accesses and allow the computational algorithm to execute asynchronously. These algorithms are referred to as chaotic algorithms and provide programming strategies that would otherwise be too cumbersome to implement and too inefficient to execute on a sequential processor. Although chaotic algorithms are difficult to analyze formally, the comparisons of their observed performance could lead to improved serial and deterministic (nonchaotic) parallel schemes. This paper will examine several chaotic iteration schemes and, based on their results, offer an alternative scheme that substantially improves the serial time to execute this algorithm. 11 refs., 11 figs.