Data Type Implementations for Non-Shared Memory Multiprocessors

Abstract

Having many processing units working cooperatively on a task is one way to get a performance increase from current technology. The hope is that by using machines with many processors it is possible to achieve a execution speedup of a factor of the number of processors working on the task.

The main problem with achieving this speedup is in making effective use of the processors. Theoretically this is achieved by dividing the work equally among the processors and making sure that they don't interfere with other. Communication is identified as the main source of interference. Despite this, communication is essential as it is used to pass information and for synchronisation.

Strategies are described that make effective use of multiprocessors that implement data types. The key to these strategies is the way data is placed among the processors. Communication is minimised where possible.

By comparing the time taken to perform operations in the non-shared memory multiprocessor implementations with the equivalent single processor implementation it was found that the cost of communication is central to the efficiency of the implementations. Even when communication is relatively slow it is can be beneficial to use the multiprocessor implementations.