Adapting non-numeric, parallel algorithms for diverse models of computation

The simplicity of the PRAM model avoids communication latency, memory lim-itations and other difficult issues. Efforts have been made to develop more real-istic models, especially with respect to communication, yet the restriction of finite memory space on computer architectures remains virtually unaddressed. Models can-not encompass all aspects of the hardware and the programming of parallel machines without losing much of their simplicity and usefulness. However, when implement-ing non-numeric algorithms (e.g., merging, sorting, graph algorithms), efficient use of available memory can be a major design concern. The transport of code from one machine model to a different model presents the programmer with a number of challenges. Parallel numeric computations are generally very regular with respect to memory access, processor cooperation and ordering of computations. The efficient implementation of such algorithms is intimately tied to the executing architecture and, consequently, may require a large amount of redesign when moved to a different machine. Non-numeric computations are typically driven by the values of the data itself. Prediction of memory access patterns and processor cooperation a priori is nearly impossible. The unpredictable nature of non-numeric computations does not often allow one to take advantage of the architectural con-straints. Without such benefits, the design and porting of non-numeric algorithms between machines can be simpler (though less efficient) than for numeric algorithms. Even so, many practical considerations and obstacles cannot be anticipated from models. We investigate the process of transporting non-numeric algorithms between di-verse machine models. For this study we have chosen a time-space optimal paral-lel merge as our prototypical algorithm. This merging strategy possesses many al-gorithmic properties shared by a wide range of other parallel non-numeric algorithms. The merge algorithm has the additional property of requiring only a constant number of auxiliary memory cells beyond that needed to hold the data for merging, effectively addressing the finite bound of memory on practical machines. As a result of the vari-ety of architectures on which the merge algorithm is implemented, we also examine the use of the merge code as a non-numeric parallel benchmark. Based on these ex-periences, we develop improvements to reduce the amount of communication in the merge algorithm. In all cases, actual implementations and executions of programs are described.