Scheduling (Averest)

Scheduling Module

Namespace: Averest.Transform
Assembly: Averest.dll

This module implements scheduling algorithms which are applied to general scheduling problems as described by the data type in this module. Acyclic dataflow graphs and basic blocks can be easily mapped to these problems, which additionally allow to add runtimes and required ressources for each node.

Types

Type	Description
Node
Resource	A scheduling problem sp is given by an acyclic graph that is determined by its set of edges sp.dependences that represent dependencies. For each node, sp.runtime and sp.resType specify its runtime and used resource which is expected to be the kind of a functional unit that will be allocated for executing the operation. Finally, sp.numNodes and sp.numResTypes clearly denote the number of nodes and the number of function units in total. Caution: it is not required that the nodes are 0..sp.numNodes-1 which means that holes in the interval are allowed.
Runtime
Schedule
SchedulingProblem

Functions and values

Function or value	Description
`AllenKennedy rdg` Full Usage: `AllenKennedy rdg` Parameters: rdg : `Set<'a * int list * 'a>`	AllenKennedy algorithm [AlKe87] for loop distribution and parallelization The algorithm considers a loop nesting with loop variables i[1],...,i[n] and a loop body with a sequence of instructions I[1],...,I[m] that have loop-carried and inner loop dependencies which are expressed with their reduced dependency graph (RGD). The problem is given by the RDG whose vertices are the names of the instructions Ik of the loop body and whose edges are the dependencies which are labeled with a vector of length n that denotes the a loop-carried dependency on loop k if entry k is nonzero, and otherwise the dependency is an inner loop dependency. rdg : `Set<'a * int list * 'a>`
`ForceDirectedScheduling beQuiet sp` Full Usage: `ForceDirectedScheduling beQuiet sp` Parameters: beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`	Force directed scheduling generates a schedule with the minimal runtime as determined by ASAP and ALAP scheduling, but then schedules the instructions such that the use of the resources is as much as possible evenly distributed over the runtime to heuristically minimize the resources. beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`
`GenerateScheduleILP sp maxRes` Full Usage: `GenerateScheduleILP sp maxRes` Parameters: sp : `SchedulingProblem` maxRes : `int[]` Returns: `string[] * string[] * string[] * string[]`	compute an ILP problem for minimal time resource aware scheduling sp : `SchedulingProblem` maxRes : `int[]` Returns: `string[] * string[] * string[] * string[]`
`LinearSchedule beQuiet sp maxRes` Full Usage: `LinearSchedule beQuiet sp maxRes` Parameters: beQuiet : `bool` sp : `SchedulingProblem` maxRes : `int[]` Returns: `Schedule`	Linear scheduling is guaranteed to generate a schedule that does not use more than the given upper bounds of the resources beQuiet : `bool` sp : `SchedulingProblem` maxRes : `int[]` Returns: `Schedule`
`ListSchedule beQuiet sp maxRes` Full Usage: `ListSchedule beQuiet sp maxRes` Parameters: beQuiet : `bool` sp : `SchedulingProblem` maxRes : `int[]` Returns: `Schedule`	List scheduling is guaranteed to generate a schedule that does not use more than the given upper bounds of the resources beQuiet : `bool` sp : `SchedulingProblem` maxRes : `int[]` Returns: `Schedule`
`PrintSchedule s` Full Usage: `PrintSchedule s` Parameters: s : `Schedule`	print a schedule s : `Schedule`
`PriorityBasedScheduling pL` Full Usage: `PriorityBasedScheduling pL` Parameters: pL : `(int * int) list` Returns: `int * (bool * (int * int) * (int * int) list) list`	PriorityBasedScheduling implements a preemptive priority-based scheduler. The processes are given in a sorted list pL where processes with higher priority occur first. Each process is described by a pair (c,p) where c is the number of cycles required by this process within each period p. It is known that a schedule exists if and only if the priorities are determined such that processes with lesser period have higher priority. The function returns a pair (period,schedules) such that period is the least common multiple of the periods of the processes and schedules contains for each process a tuple (f,(c,p),psched) where f is true if the deadlines are met for the process, (c,p) is the definition of the process, and psched defines the intervals where the process owns the CPU. pL : `(int * int) list` Returns: `int * (bool * (int * int) * (int * int) list) list`
`ScheduleALAP beQuiet sp` Full Usage: `ScheduleALAP beQuiet sp` Parameters: beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`	compute an ALAP schedule by scheduling nodes as late as possible within the minimal runtime of an ASAP schedule (assuming infinite resources) beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`
`ScheduleASAP beQuiet sp` Full Usage: `ScheduleASAP beQuiet sp` Parameters: beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`	compute an ASAP schedule by scheduling nodes as soon as the input values are available for them assuming infinite resources beQuiet : `bool` sp : `SchedulingProblem` Returns: `Schedule`
`example1` Full Usage: `example1` Returns: `SchedulingProblem`	Returns: `SchedulingProblem`
`example2` Full Usage: `example2` Returns: `SchedulingProblem`	Returns: `SchedulingProblem`