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

7.4 THE CONCEPT OF THE CA-BASED SCHEDULER

I outline the concept of a CA-based scheduler in the following way. An elementary automaton is associated with each task of the program graph. The topology of the program graph defines the structure of the CA. Therefore, the structure of the CA is not regular. However, each elementary automaton is binary; since we consider two-processor architectures, we use state 0 (1) of a cell to indicate that the corresponding task is allocated to processor P0(P1).

The concept of a CA-based scheduler is illustrated in Fig. 7.5. Initially, the program tasks are randomly allocated to the processors. For example, task allocation (0, 1, 1,0) indicates allocation of tasks 0 and 3 to processor P0, and tasks 1 and 2 to processor P1. Also, an elementary automaton is associated with each node of the program graph. Next, the CA starts to evolve according to some predefined rule. Changing the states of the evolving CA corresponds to changing the allocation of tasks in the system graph, which results in changing the response time T (see, Eq. 7.3). The final state of the CA corresponds to the final allocation of tasks in the system [Fig. 7.5 (lower-right)].

To design the architecture of a CA-based scheduler, some essential questions must be considered. For example, how to define a local neighborhood, and what transition function to use. I would like to use a generic definition of neighborhood, that is the same for various kinds, sizes, and shapes of potential program ...