Parallel Searching and Merging on ZMOB.

Abstract : One of the most difficult issues that must be addressed when studying a class of parallel algorithms is the problem of choosing a model that captures the inherent difficulty of implementing these algorithms on a multiprocessor architecture. Shared memory models have proven to be an effective tool for deriving lower bounds on the complexity of comparison problems. In particular, a speed-up of lg(P) is possible for the problem of finding an element in an N-element sorted list, and speed-ups of PlglgP and P are possible for merging N-element sorted lists of P processors for the cases N=P and PN respectively. In practice, these speed-ups are not attainable since the shared memory models ignore many practical considerations in multiprocessor systems, such as interprocessor communications, distribution of data on local memories and limited fan-out of memory locations. In this paper we introduce a model for parallel computation that is strictly weaker than the shared memory models. The model is based on an actual machine currently being constructed (ZMOB). We examine the communication facilities available in the model and show that lower bounds for merging and searching on shared memory models are attainable (within a constant).