A MODEL FOR ASYNCHRONOUS SHARED-MEMORY PARALLEL COMPUTATION

Traditional theoretical shared memory parallel models have been based on a number of assumptions which simultaneously simplify solutions to problems and distance the models from actual parallel machines. One su ch assumption is that processors work together in a synchronous fashio n. Recent work has focused on finding a model that captures the essenc e of computation by processors communicating asynchronously through sh ared memory. In this paper, a general framework and set of criteria us ed to analyze these models, including the complexity analysis of sever al fundamental algorithmic paradigms, are considered. A general asynch ronous model is introduced and how it satisfies these criteria is demo nstrated. In this model, O(log p) algorithms are demonstrated for solv ing p-input versions of the problems of AND, OR, parity, maximum, mini mum, and list ranking. To handle list ranking, a technique of analyzin g algorithms is developed in which the set of tasks that are to be exe cuted depends on the processor schedules.