Yosi Ben-Asher - Issues in multicore programming using the ParC language

Department of Computer Science, University of Haifa, Haifa, Israel

Yosi Ben-Asher

Email:

Parallel machines can be viewed as a collection of sequential machines (processing elements or processors) that can communicate with one another. The processing elements are also called processors and correspond to a regular computer/CPU capable of executing a sequential program. Thus, from a hardware perspective, a parallel machine is a collection of independent, sequential machines/processors that are capable of communicating with one another. From a software perspective, a parallel machine executes parallel programs which, for the time being, can be regarded as a dynamic set of sequential programs (called threads) that can communicate with one another.

It follows that the most important aspect of both parallel machines and parallel programs is the ability of the processors/threads to communicate. It is this ability that glues a set of sequential-machines or a set of sequential-programs to a single coherent parallel-machine/parallel-program. Thus, from both hardware and software perspective, in order to understand what parallel machines are we need to define what we mean by communication. Basically we first consider the question of what is communication between two entities and consider how to extend to a larger set. In general there can be two forms of communication between two processors/threads: Message passing is a more basic operation than reading/writing to a shared memory. Technically we only need the two processors to be connected by a wire to exchange messages. Basically we can simulate shared memory by message passing. The above example of updating x and y can be simulate if the first processor hold x and executes: while the second processor hold y and executes This is clearly only one possible way to simulate shared memory via message passing and thus our goal is first to show how to build parallel machine with message passing and then to define how shared memory can be used on top of it.

In order for processors to communicate with each other, they must be connected to each other via a communication network that can direct messages from one processor to the other. This configuration is similar to a telephone network that allows users to call each other, or to mail services that allow us to send and receive letters. The performance of the underlying communication network can definitely affect the execution time of a given program on a parallel machine. Obviously, the more the processors need to communicate with each other, the more the performance of the communication network will affect the overall execution time.

It is thus appropriate to consider several types of schematic communication networks to see how they affect performance. In general a communication network is a collection of processors that can be connected via two types of lines: Each processor can be connected via several buses and links but can use only one of them during a given time unit (either to send or to receive a message). Figure depicts a possible configuration for a parallel machine using both buses and point-to-point links.

We consider three possible factors that can be used to compare and classify communication networks: