Class 1: More on Models

A classification of parallel machine models that is orthogonal to Flynn's Taxonomy is based on how data is stored on the machine:

• Shared memory machines: These machines use one global memory that all the processors can access. Examples are the multiprocessor Cray Y-MP and C90, the SGI Power Challenge, the Sequent machines, and the Convex machines. Processors under this model communicate using common memory locations-one processing element (PE) writes to a location, and the other reads from it.

  What kind of memory access issues do you have to deal with here?

  • Memory access conflicts.
  • Interconnection networks.
  • Synchronization (how do you make sure that the consumer comes into the memory after the producer?).
• Distributed memory machines: Processors on these machines have their own local memory, and communicate information with each other through messages (the machines are therefore often referred to as distributed memory, message passing machines). One PE will create and send a message, while another will receive and use the message. Examples are the nCUBE and the transputer machines in the PPL. What kind of memory-related issues arise here?
  • Size of messages.
  • How they get routed.
  • Global operations like broadcasts.
  • Interconnection networks.
  • Blocking/non-blocking primitives.

Since this classification is orthogonal to Flynn's classification, one can have shared memory MIMD machines (Power Challenge), as well as distributed memory MIMD machines (transputer machines).

The above aren't the only ways to talk about machine models. The Text discusses a parallel machine model in Section 1.2. The discussion starts off with a description of the von Neumann model of sequential computers. This model abstracts a sequential computer as being a CPU that accesses instructions and data from a memory, and executes instructions one after another. This model has two characteristics that we want to have in our models of parallel machines too:

1. simplicity-the models should be simple to understand.
2. realism-the models should allow realistic development of programs.

A straightforward extension of the von Neumann model is the PRAM (Parallel Random Access Machine) model-the Random Access Machine model is a variant of the von Neumann model. The PRAM model is an abstraction where a number of PEs can access any element of a globally shared memory. This turns out to be a good model for the design of parallel algorithms for shared memory MIMD computers. An implementation of a PRAM is also called a multiprocessor.

The text describes the multicomputer model where a number of von Neumann nodes are connected together by an interconnection network. As is clear from the preceding discussion, this model captures the distributed memory, message passing MIMD machine better than the PRAM. However, since this is an abstraction, it assumes that communication between any two nodes takes the same amount of time-this is obviously not the case for real machines. Distributed systems, where the (machine) nodes are connected by some sort of a network (either a LAN or a WAN) can also be modeled by the multicomputer model. Please see the discussion in Section 1.2.1 for details about the multicomputer model.

Once we have looked at the various models of parallel machines that are available, we also need to look at the various programming models that could get used. Section 1.3 talks about some relevant parallel programming models.

The task and channel model is most appropriate for the multicomputer model, and hence, transputer machines. A parallel computation is broken down into tasks that execute concurrently. Tasks are connected to each other with channels, and tasks send and receive messages on these channels. These tasks and channels can then be mapped onto a real machine.

Other parallel programming models include:

• Message Passing.
• SPMD.
• Data parallelism.
• Shared memory.

Chapter 1 of the text has pointed out four important facets of parallel problem solving:

1. Concurrency: doing many things at the same time.
2. Scalability: how the solution changes as the number of PEs is changed.
3. Locality: try to minimize memory accesses from levels of hierarchy that are further away.
4. Modularity: solve the larger problem by putting together solutions to smaller sub-problems.

There is one more issue that needs to be discussed before we can embark on a debate of what kind of machine and programming model is best suited for solving our finite difference heat flow problem-the granularity of parallelism in a problem. The granularity of parallelism in a task is defined by how much work each sub-task involves when the large task is broken up into sub-tasks. If one is breaking down a large problem into many small subproblems that require a small amount of computational power each, one is dealing with a fine grain of parallelism. On the other hand, if one is splitting up a problem into a few large subtasks that can be solved concurrently using a large amount of computing power each, we are exploiting coarse grain parallelism. Different parallel machines are better suited to solve a given problem depending on the granularity of parallelism that can be exploited. Loosely speaking, an SIMD model is better suited for exploiting fine grained parallelism, while MIMD machines are often more suited for coarse grained parallelism.

Think about which of the models that we have looked at are most appropriate for the steady state heat flow problem that we are investigating.

Reading: Read all of Chapter 1, including the parallel algorithm examples in Section 1.4.