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

7.5 DEFINING LOCAL NEIGHBORHOOD

7.5.1 Selected Neighborhood

Selected neighborhood uses only two representatives of each of the sets of predecessors, brothers, and successors in forming the neighborhood. The representatives are selected on the basis of, respectively, the maximal and minimal values of some attributes of tasks in the given set. As we stated earlier, the following attributes are assigned to task k of the program graph: a_kl, b_k, static level, dynamic level, and static and dynamic colevels. In a given run of the scheduling algorithm, one attribute for each set of predecessors, brothers, and successor is selected. The attributes selected for each set can be different.

The selected neighborhood uses seven cells (including cell k). The part of the neighborhood corresponding to the two associated representatives will be referred as a subneighborhood of the cell k.

Because the structure of a program graph and corresponding CA is irregular, the number of predecessors, brothers, or successors may be less than two, or they may have the same values of attributes, the following solutions for special cases have been accepted:

• If predecessors (brothers or successors) do not exist for a given task, a subneighborhood corresponding to such a situation is created by adding a pair of dummy tasks and associating with them a pair of cells; the states of these cells (denoting processors where the tasks are allocated) are undefined and the state of such a subneighborhood takes a special ...