A TaskStealer object is created using TaskStealer_all_create to load balance the tasks shared by a collection of processors. Some initial number of tasks are placed in the TaskStealer object, and the processors use TaskStealer_remove to obtain tasks. More tasks can be added after processing their parent tasks. The user calls TaskStealer_clear to inform the data structure that a task has completed. A TaskStealer object is said to be in the ``terminated'' state when there are no tasks left in the object, and all scheduled tasks have completed execution. Once a TaskStealer object is terminated, it remains terminated.
TaskStealer_all_create, TaskStealer_all_destroy, TaskStealer_remove, TaskStealer_terminate are split-phase operations. A split-phase operation returns OK if it has completed upon return (i.e., no need to create a thread to wait for the the result), and WAIT otherwise. TaskStealer_all_create and TaskStealer_all_destroy must be called by one thread per processor on all processors.
Create a TaskStealer object with id id. A Snapshot object and an integer object are also created internally by the TaskStealer object to perform termination detection. Threads associated with the new TaskStealer object are deposited by scheduler. Each task has size bytes of data, and can be scheduled on processors with id ranging from startProc to endProc. Tasks migrate between neighbor processors with respect to the topology specified in topology, which can be RING, MESH or HCUBE (hypercube). The counter ctr is incremented when the operation completes.
In the current implementation, the topology merely specifies the degree of connectivity among processors. A processor's neighbor may change in a pseudo-random manner during the execution.
Deallocate the TaskStealer object with id id. The Snapshot object and the integer object associated with it are also deallocated.
TaskStealer_all_destroy currently does nothing.
Remove a task from the TaskStealer object id. The task content is copied into the buffer task. Increment the counter ctr upon completion.
The user must call TaskStealer_clear when the task completes.
Add a task to the TaskStealer object id. The task content is copied from the buffer task. The task is stored in the local partition of the TaskStealer object. The user provides the following hints for scheduling the task: priority, comp, and comm. A higher priority values means higher scheduling priority. comp is the estimated computation granularity of the task, and comm the estimated cost for migrating the task (e.g., the cost of accessing data that become remote as a result of migration). The units used for estimating comp and comm must be the same (e.g., cycles, seconds).
The TaskStealer object id must not be in the terminated state.
Same as TaskStealer_addProc, except that the task is initially placed on the processor proc.
proc must be one of the processors sharing tasks of the TaskStealer object. The TaskStealer object id must not be in the terminated state.
Wait until the TaskStealer object id is in the terminated state. Increment the counter ctr upon completion.
Declare that a task removed from the TaskStealer object id has completed.
There should be exactly one TaskStealer_clear call for each task removed, and vice versa.
Set the parameters of the load balancing protocol for the TaskStealer object id. When the number of tasks falls below tasksLB, or the amount of computation falls below compLB, the processor starts to steal tasks from other processors.
Print statistics about the TaskStealer object id.