Because a complete performance analysis of the Monte Carlo simulation is
rather lengthy, we provide only a summary of the analysis here. Calculating
the efficiency of the concurrent update algorithm is relatively simple
because it requires only measurements of the time an update takes on one node
and on multiple nodes. A more difficult parameter to calculate is
the load balance of the update procedure. In order to calculate the load
balance, we measured the time required to send each type of message that the
update uses. The total communication overhead is the sum of the overheads
for each type of message, which is the product of the time to send that type
of message and the number of such messages. We calculated the number of each
type of message by assuming a uniform distribution of particles. Because the
update algorithm contains no significant serial components, we attributed to
load imbalance the parallel overhead remaining after accounting for the
communication overhead. The load balance is a factor that can range from
, where N is the number of nodes, to 1, which occurs when the loads
are balanced perfectly. We give the update time in seconds, the efficiency,
and the load balance for several simulations on the 64-node Caltech hypercube
in Table 14.5 ([Johnson:86a] p. 73).
Table 14.5: Simulations on the 64-node Caltech Hypercube