Next: , Previous: , Up: Other statements   [Contents][Index]


4.8.4 Reordering task IDs

coNCePTuaL distinguishes between “task IDs”, which are used in task descriptions (see Task descriptions) and “processor IDs”, which are assigned by the underlying communication layer. As stated in Running coNCePTuaL programs, a coNCePTuaL program has no control over how processor IDs map to physical processors. It therefore has no way to specify, for instance, that a set of tasks must run on the same multiprocessor node (or on different nodes, for that matter). Initially, every task’s task ID is set equal to its processor ID. However, while processor IDs are immutable, task IDs can be changed dynamically during the execution of a program. Altering task IDs can simplify coNCePTuaL programs that might otherwise need to evaluate complex expressions to determine peer tasks. coNCePTuaL enables either a specific or a randomly selected task to be assigned to a given processor:

<processor_stmt> ::= <source_task>
IS ASSIGNED TO
PROCESSOR <expr> | A RANDOM PROCESSOR

In addition to performing the specified processor assignment, coNCePTuaL will perform an additional, implicit processor assignment in order to maintain a bijection between task IDs and processor IDs (i.e., every task ID corresponds to exactly one processor ID and every processor ID corresponds to exactly one task ID). Consider the following statement:

TASK n SUCH THAT n<(num_tasks+1)/2 IS ASSIGNED TO PROCESSOR n*2

If num_tasks is ‘8’ the preceding statement will cause ‘TASK 0 to refer to processor 0,TASK 1 to refer to processor processor 2,TASK 2 to refer to processor 4, and ‘TASK 3 to refer to processor 6. What may be unintuitive is that the remaining tasks will not map to their original processors, as doing so would violate the bijection invariant. To clarify coNCePTuaL’s implicit processor assignments the following timeline illustrates the execution of ‘TASK n SUCH THAT n<(num_tasks+1)/2 IS ASSIGNED TO PROCESSOR n*2’ when num_tasks is ‘8’:

n TASK 0 TASK 1 TASK 2 TASK 3 TASK 4 TASK 5 TASK 6 TASK 7
0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 0 2 1 3 4 5 6 7
2 0 2 4 3 1 5 6 7
3 0 2 4 6 1 5 3 7

Initially, task and processor IDs are equal. When n takes on the value 0, coNCePTuaL performs the equivalent of ‘TASK 0 IS ASSIGNED TO PROCESSOR 0’, which does not change the task ID to processor ID mapping. When n is 1, coNCePTuaL performs the equivalent of ‘TASK 1 IS ASSIGNED TO PROCESSOR 2’, which sets task 1’s processor to 2. However, because task 2 also has processor 2, coNCePTuaL implicitly performs the equivalent of ‘TASK 2 IS ASSIGNED TO PROCESSOR 1’ in order to preserve the unique task ID to processor ID mapping. When n is 2, coNCePTuaL performs the equivalent of ‘TASK 2 IS ASSIGNED TO PROCESSOR 4’ and, because task 4 also has processor 4 , the equivalent of ‘TASK 4 IS ASSIGNED TO PROCESSOR 1’. Finally, when n is 3, coNCePTuaL performs the equivalent of ‘TASK 3 IS ASSIGNED TO PROCESSOR 6’ and, because task 6 also has processor 6, the equivalent of ‘TASK 6 IS ASSIGNED TO PROCESSOR 3’. Thus, coNCePTuaL maintains the invariant that after any processor assignment every task corresponds to a unique processor and every processor corresponds to a unique task.


Next: , Previous: , Up: Other statements   [Contents][Index]

Scott Pakin, pakin@lanl.gov