We believe that the common hardware organization described in Figure 1 will dominate commercial MPPs at least for the rest of this decade, for reasons d~cussed in Section 2 of this paper. of-the-art memory systems to remain competitive. Since dte parallel machine nodes are very similar to the core of a workstation, the cost of a node is comparable to the cost of a workstation. As the most expensive sttpercomputer costs less than 25 M$ for the processors and memory, and since the price of workstations have remained at about 5-10 K$, the largest parallel machines will have a few thousand nodes. This economic observation is valid today, with no vendor producing a system with more than two thousand nodes. Summarizing, we can expect that the nodes of parallel machines of the 1990s will be capable of computing hundreds of Mflops and capable of storing hundreds of megabytes. The number of such nodes will not scale into the millions, so parallel algorithms will need to be developed under the assumption of a large number of data elements per processor. This has significant impact on the kinds of algorithms that are effective in practice. Network technology is advancing as well, but it is not driven by the same volume market forces as microprocessors and memory. While new media offer much higher network bandwidth, their Although the interface is improving, processors are improving in performance even faster, so we must assume that high [atency and overhead of communication, as well as limited bandwidth will continue to be problems. There appears to be no consensus emerging on interconnection topology: the networks of new commercial machmes are typically different from their predecessors and different horn each other. Operating in the presence of network faults is becoming extremely important as parallel machines go into production use, whtch suggests that the physical intercomect on a single system will vary over time to avoid broken components. 1': the number of processor/memory modules. We assume unit time for local operations and call it a cycle. Furthermore, it is assumed that the network haa ajnite capacity, such that at most [L/gl messages can be in transit from any processor or to any processor at any time. If a processor attempts to transmit a message that would exceed this limig it stalls until the message can be sent without exceeding the capacity limit. The parameters L, o and g are measured as multiples of the processor cycle. The model is asynchronous, i.e., processors work asynchronously and the latency experienced by any message is pre~lc~ble> but is bounded above by~in the absence of stalls. Because of variations in latency, the messages directed to a given target module may not arrive in the same order as they are sent. The basic model assumes that all messages are of a small size (a simple extension deals with longer messages). In analyzing an algorithm, the key metrics are the maximum time and the maximum space used by any processor. hr order to be is the time at which it has received the datum and can begin sending it on. 7he last value is received at time 24. The computation schedule for our summation algorithm can also be represented as a tree with a node for each computation step.  Our first example, the fast Fourier transform, illustrates these ideas in a concrete setting. We discuss the key aspects of the algorithm and then an implementation that achieves near peak performance on the Thinking Machines CM-5. We focus on the "butterfly" algorithm [8] for the discrete FIT problem, most easily described in terms of its computation graph. The n-input (n a power of 2) butterfly is a directed acyclic graph with n(log n + 1) nodes viewed as n rows of (log n + 1) columns each. For O s r < n and O s c < log n, the node (r, c) has directed edges to nodes (r, c There is a vast body of work on this structure as an interconnection topology, as well as on efficient embeddmgs of the butterfly on hypercubes, shuffle-exchange networks, etc. This has led many researchers to feel that algorithms must be designed to match the interconnection topology of the target machine. In real machines, however, the n data inputs and then log n computation nodes must be laid out across P processors and typically P << n. The nature of this layou~and the fact that each processor holds many data elements has a profound effect on the communication structure, as shown below. A natural layout is to assign the first row of the butterfly to the first processor, the second row to the second processor and so on. We refer to this as the cyclic layout. Under this layou~the first log~columns of computation require only local data, whereas the 5 last log P columns require a remote reference for each node. An alternative layout is to place the first~rows on the first processor, the next # rows on the second processor, and so on. With this blocked layou~each of the nodes in the first log P cohumts requires a remote datum for its computation, while the last log~columns require only local data. Under either layou~each processor spends # log n time computing and (g: + L) log P time communicating, assuming g~20. Since the initial computation of the cyclic layout and the final computation of the blocked layout are completely local, one is led to consider hybrid layouts that are cyclic on the first log P columns and blocked on the last log P. Indeed, switching from cyclic to blocked layout at any column between the log P-th and the log~-th (assuming that n > Pz) leads to an algorithm which has a single "all-to-all" communication step between two entirely local computation phases. Figure 5 highlights the node assigmnent for processor O for an 8-input FIT with P = 2 under the hybrid layout remapping occurs between cohtmna 2 and 3. 'J3e bad remap curve shows the time spent remapping the data ftvm a cyclic Jayout te a blocked layout ifa naive communication schedule is used. 'he good remap curve shows the time for the same remapping} but with a contcrrtion-fm communication schedule, which is en onfer of magnitude fastrx 'Rre X axis scale refers to the entire PPT size. takes only~th as long. The two computation phases involve purely local operations and are standard FFI's. From the computational performance in Figure 7 we can calibrate the "cycle time" for the FFT as the time for the set of complex The analysis does not predict the gradual performance drop for large FITs. In realhy, processors execute asynchronously due to cache effects, network collisions, etc. It appears that they gradually drift out of sync during the remap phase, disturbing the communication schedule. To reduce this effect we added a barrier synchronizing all processors after every~messages. 5 Figure 8 shows that this eliminates the performance drop. We can test the effect of reducing g by improving the implementation to use both fat-tree networks present in the machine, thereby doubling the available network bandwidth. The result shown in Figure 8 is that the performance increases by only 15% because the network interface overhead (o) and the loop processing dominate. 4~e bisection bsndwidth is the minimum bandwidth through any cut of the network that separates the set of processors into halves. 5For s~PlicitY, tie fiplemenmtion uses the hardware barri.r avaitable on the CM-5. llte same effect could have been achieved using explicit acknowledgement messages.
The LogP model REF predicts the time of network communication for small fixed-sized messages in terms of the latency, L, the overhead, o, the gap per message, g, and the number of processors, P .
LogP: towards a realistic model of parallel computation
PPOPP '93
Computer Science