The Nagurney application uses an iterative algorithm to implement a commodity trade model that handles tariffs and nonlinear supply and demand price functions [Bergmark1995]. The parallel version of Nagurney was developed for the IBM SP2 by Donna Bergmark at the Cornell Theory Center. Here we use WT analysis to examine the tradeoff between communication and replicated computation in Nagurney on the IBM SP2 and the SGI Challenge.
The program receives as input the cost of shipments, tariff structures, and the demand and supply price functions. The goal is to find a stable shipment structure between supply and demand markets. The algorithm is divided into data-independent steps that calculate a new shipment structure from the price functions and the previous shipment structure. Each step consists of eight double-nested loops that access data along alternating supply and demand dimensions. Since all entries in the shipment structure can be calculated simultaneously, each loop can be fully parallelized. However, since demand is the sum across one dimension, supply is the sum across the other dimension, and both are needed to compute a new shipment structure, any straightforward parallelization of the algorithm implies significant communication between successive loops.
One way to avoid excessive communication between the loops is to replicate the computation along one dimension (supply or demand) on each processor, and distribute the data of the other dimension. On the SP2, Bergmark chose this approach and did not parallelize loops that iterate over the demand dimension. In general the merit of this approach depends on the number of processors, the relative cost of communication (including waiting time) and computation on the machine, and the complexity of the price function (which dictates the amount of replicated computation to be performed). We used WT analysis to model this tradeoff as a function of the number of processors and the complexity of the price function.
First, we used WT analysis to confirm that all waiting time in the program is caused by communication operations (since all the loops are balanced). We then developed a performance model of the application by creating separate models for the computation time and waiting time, as was done for Radar in section 4.4.2.
Some results of our modeling effort for the SP2 are presented in figures 4.5 and 4.6. As seen in these figures, whether we fix the number of processors and vary the amount of replicated computation (figure 4.5) or fix the amount of replicated computation and vary the number of processors (figure 4.6), the implementation with replicated computation always performs better than the implementation with fully parallelized loops on the SP2.
Figure 4.5: Communication vs. Replicated Computation on the SP2:
Variable data size.
Figure 4.6: Communication vs. Replicated Computation on the SP2:
Variable number of processors.
We repeated this process on the SGI machine where, due to the lower cost of communication, we observed portions of the experimental space where the fully parallel loop implementation performed better than the implementation with replicated computation. As seen in figures 4.7 and 4.8, for a small number of processors (meaning less communication is required for the fully parallel implementation) and for large data sizes (meaning significant replicated computation), the best implementation parallelizes all the loops.
Figure 4.7: Communication vs. Replicated Computation on the SGI:
Variable data size.
Figure 4.8: Communication vs. Replicated Computation on the SGI:
Variable number of processors.