Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

7.7 EXPERIMENTS

In the experiments reported in this section it is assumed that the CA works asynchronously, i.e., at a given moment of time only one cell updates its state. The states are updated by the order of the states, which is defined by the order of the state as it corresponds to the tasks in the task precedence graph. The single step of running the CA is completed in N_p units of time (N_p—the number of tasks).

A number of the experiments with program graphs that are available in the literature have been conducted. The first program graph, referred to as gauss 18 [8, 16], is shown in Fig. 7.14a. It represents the parallel Gaussian elimination algorithm, which consists of 18 tasks. The next program graph (g18) is shown in Fig. 7.14b [10]. The computational costs of the tasks are shown in the figure. All the communication costs are the same and equal to 1. Figure 7.14c presents a program graph g40 [19], with computational and communication costs equal to 4 and 1, respectively. Figure 7.14d shows a binary out-tree program graph. We refer to it as tree15. We also use binary out-trees tree63 and tree127. The computation and communication weights of the out-trees are equal to 1.

Figure 7.14 Program graphs: (a) gauss 18; (b) g18; (c) g40; and (d) tree 15.

Experiment 1: Program Graph gauss18

The CA neighborhood was created using the idea of the selected neighborhood. In the learning ...