Scheduler - Dispatcher

Next: The Time Source and Up: C++ Environment for Synchronos Previous: The Graph Contents

Subsections

Scheduler - Dispatcher

There is a lot of scheduling algorithm available, but in use of SDF-graphs and single process dispatcher it is quit straight forward to solve. There are several problems which the scheduler has to solve that is:

1.: to test the SDF graph for recursion- or connection failures
2.: to get the execution graph out of the data paths
3.: to test the buffer consistency and optimize buffer usage
4.: assign the data buffers.

The next tasks are to do for the dispatcher, that is:

1.: split the dispatch process as child from main process
2.: assign the shared memory if needed
3.: assign the additional needed memory for the operation
4.: run the execution graph
5.: start/stop execution loop
6.: free resources and terminate the child process

scheduling algorithm

There should be different scheduler algorithms to choose from for specific solutions. One of the is a straight forward one which just makes a execution stack and the dispatcher runs this.

Another one is a conditional scheduler called ´´boolean SDF scheduler´´, where the output of the operation is tested for change and operation are executed only when needed with the overhead of testing (not implemented yet).

The scheduling algorithms may change in future, but here a description the first one implemented to show the problematic of this on an example:

**Figure 1:** Top-Down Schedule of an example graph
$\begin{figure} \epsfig{file=abb/schedulestudie2.eps, width=0.8\textwidth}\end{figure}$

We have a data-flow graph as shown in figure1. The job is now to get the processing order of the operations and the assignment of buffer, so we use as few as possible buffers.

**Figure 2:** Bottom-Up Schedule of an example graph
$\begin{figure} \epsfig{file=abb/schedulestudie1.eps, width=0.8\textwidth}\end{figure}$

The programmer of the graph can think about the graph that a signal at the top is generated and flows trough the operations. So the first idea is to make a Top-Down scheduling. We start with search for the first source and look at the outputs. The left one and the right one points to an object with other inputs, which are not feed. So we cant execute one of this next. Anyway we assign two buffers to the connections. Next we search for a next source to calculate next as 2. We assign a buffer c to output and therefore to two inputs. Next we follow the output to get to an operation with all inputs feed and can assign 3 to it. Now we can reuse the input buffer for the outputs and follow the outputs, so we find 4 and reuse buffer a and b. Following the outputs we find 5 as drain and we can follow the others going back one and than two objects. So we can arrange the others the same way too. But there is a failure since 8 get two input buffers of c. The correct assignment should be buffer d for left input.

The problem arises because more connections are allowed for one output. The better solution is shown in figure 2, which is the same but bottom-up. So we get the reverse computation order. This algorithm also works on independent parallel graphs.

**Figure 3:** Recursion Problem on scheduling algorithm
$\begin{figure} \epsfig{file=abb/schedulestudie3.eps, width=0.8\textwidth}\end{figure}$

Another problem is how to detect a recursion. In figure 3 is shown, that if there is a recursion, the scheduling will stop before all operations are on the operation stack and all operation having something to do with the recursion are not executed.

straight forward scheduler

The scheduler is run every time the DSP-engine is started or a connection is made/changed or a operation is inserted/removed/changed.

Following steps are performed:

1.: The scheduling algorithm is performed to assign buffer numbers and detect recursion and get the order of execution of the operation, putting them in the operation stack.
2.: The scheduler scans the operations for not connected inputs to prepare the Constant Buffers for that.
3.: A algorithm is performed to start with sources and their buffer-Len, and looks for needed buffer sizes in the following operations.
4.: If above is successfully the dispatcher is forked and afterwards, the buffer space is allocated and assigned to the buffer, whereby the buffer size

This is that buffer space is only allocated in the forked process and not doubled. Anyway this does not improve much on Unix machines, because page faults are only produced if memory is accessed by both processes, which should never happen to buffer space, but maybe on some machines or multiprocessor architectures this can be an improvement.

Next: The Time Source and Up: C++ Environment for Synchronos Previous: The Graph Contents

HAss.DI Winfried Ritsch - ritsch@algo.mur.at