-
Notifications
You must be signed in to change notification settings - Fork 4
Algorithms: Allocation Ordering
Instead of the standard exhaustive list scheduling (ELS) search space, the use of an allocation ordering (AO) search space prevents duplicate schedules being formed without the need for duplicate detection. It has been shown to run better than standard ELS on branch-and-bound and A* algorithms in some research papers (see here).
The search space has 2 parts. First, the tasks are allocated to a processor. Then each processor is ordered.
In this phase, tasks are only assigned the processor that they will be scheduled on. As the processors are identical, by always allocating in a fixed order onto processors, we can ensure no duplicate allocations are produced (e.g. for 2 tasks on 2 processors, whether task 1 and 2 are on the first processor is a duplicate of task 1 and 2 being on the second processor).
There are 2 heuristics used for allocation: the maximum time needed for any processor to run its tasks and the max of the known critical path (top level + communication costs + bottom level) for any task.
The ordering phase takes the complete allocations from above and produces a complete schedule by ordering the tasks on each processor. This is done processor by processor to ensure no duplication. Bitfields are used to represent when tasks are ready to be ordered on a processor due to their local dependencies being satisfied. This section can get a bit complicated so refer to the paper for more specifics.
The heuristics used are the estimated earliest start time + bottom levels of nodes and the latest finish time of any processor (accounting for known idle times) + the weight of unassigned tasks on that processor.
Search spaces implement SolutionSpace so that the algorithm can get the root node for this search space. Then, it calls expand on PartialSolutions from this search space until we arrive at a complete schedule. APartialSolution and OPartialSolution implement PartialSolution to handle expanding (and heuristic calculation) of each of these distinct parts in the search space.