TORSCHE Scheduling
Toolbox for Matlab

List of the supplementary algorithms is summarized in the following table.

Lot of scheduling algorithms require extra parameters, e.g. parameters of external solvers. To create Scheduling Toolbox structure containing option parameters use

schoptions=schoptionsset('keyword1',value1,'keyword2',value2,...)

The function specifies values (V1, V2, ...) of the specific parameters (C1, C2, ...). To change particular parameters use

schoptions=schoptionsset(schoptions,'keyword1',value1,...)

Parameters of Scheduling Toolbox options are summarized in Table 10.2, “List of the toolbox options parameters”. Defauld values of single parameters are typed in italics.

This supplementary function allows to generate random Data Flow Graph (DFG). It is appointed for benchmarking of scheduling algorithms.

g=randdfg(n,m,degmax,ne)

The function generates Data Flow Graph g, where relation of node (task) to a dedicated processor is stored in g.N(i).UserParam. The first parameter n is the number of nodes in the DFG, m is the number of dedicated processors. Parameter degmax restricts upper bound of outdegree of vertices. Parameter ne is the number of edges.

g=randdfg(n,m,degmax,ne,neh,hmax)

The function with this parameters generates cyclic DFG (CDFG), where neh is number of edges with user parameter 0 < g.E(i).UserParam <= hmax. Other edges has user parameter g.E(i).UserParam=0.

Universal interface for Integer Linear Programming (ILP) allows to call different ILP solvers from Matlab.

[xmin,fmin,status,extra] = ...
   ilinprog(schoptions,sense,c,A,b,ctype,lb,ub,vartype)

Function ilinprog has the following parameters. Parameter schoptions is Scheduling Toolbox Options structure (see Scheduling Toolbox Options). The next parameter sense indicates whether the problem is a minimization=1 or a maximization=-1. ILP model is specified with column vector c containing the objective function coefficients, matrix A representing linear constraints and column vector b of right sides for the inequality constraints. Column vector ctype determines the sense of the inequalities as is shown in Table 10.3, “Type of constraints - ctype.”.

Further, column vector lb (ub) contains lower (upper) bounds of variables in specified ILP model. The last parameter is column vector vartype containing the types of the variables (vartype(i) = 'C' indicates continuous variable and vartype(i) = 'I' indicates integer variable).

A nonempty output is returned if a solution is found. Afterwards xmin contains optimal values of variables. Scalar fmin is optimal value of the objective function. Value status indicates the status of the optimization (1-solution is optimal) and structure extra consisting of fields time and lambda. Field time contains time (in seconds) used for solving and field lambda contains solution of the dual problem.

Universal interface for Mixed Integer Quadratic Programming (MIQP) allows to call different MIQP solvers from Matlab. This function is very similar to function 'ilinprog', described in section Section 4, “Universal interface for ILP”.

[xmin,fmin,status,extra] = ...
   iquadprog(schoptions,sense,H,c,A,b,ctype,lb,ub,vartype)

Function iquadprog has the following parameters. Parameter schoptions is Scheduling Toolbox Options structure (see Scheduling Toolbox Options). The next parameter sense indicates whether the problem is a minimization=1 or maximization=-1. ILP model is specified with column vector c and square matrix H containing the objective function coefficients, matrix A representing linear constraints and column vector b of right sides for the inequality constraints. Column vector ctype determines the sense of the inequalities as is shown in Table 10.4, “Type of constraints - ctype.”.

Further, column vector lb (ub) contains lower (upper) bounds of variables in specified MIQP model. The last parameter is column vector vartype containing the types of the variables (vartype(i) = 'C' indicates continuous variable and vartype(i) = 'I' indicates integer variable).

A nonempty output is returned if a solution is found. Afterwards xmin contains optimal values of variables. Scalar fmin is optimal value of the objective function. Value status indicates the status of the optimization (1-solution is optimal) and structure extra consisting of fields time and lambda contains time (in seconds) used for solving and optimal values of dual variables respectively.

CSSIM (Cyclic Scheduling Simulator) is a tool allowing to simulate iterative loops in Matlab Simulink using TrueTime tool [Cervin06]. The loop described in a language compatible with Matlab can be transformed into the toolbox structures. In the toolbox the input iterative loop is scheduled using cyclic scheduling (see Cyclic scheduling (General)) and optimized iterative algorithm is transformed into TrueTime code for real-time simulation. The CSSIM operates in three steps: input file parsing (function cssimin), cyclic scheduling (see Cyclic scheduling (General)) and True-Time code generation (function cssimout).

[T,m]=cssimin('dsvf.m');                      %input file parsing

TS=cycsch(T, problem('CSCH'), m, schoptions); %cyclic scheduling

cssimout(TS,'simple_init.m','code.m');        %TrueTime code generation

Input parametr of function cssimin is a string specifying input file to be parsed. The function returns a taskset representing the input algorithm. Extra information about algorithm structure are available in CodeGenerationData structure contained in TSUserParam of the taskset T. Further, the function returns the number of processors, contained in vector m. Function cssimout generates two files, which are used for simulation in TrueTime. The first input parameter specifies a taskset generated using function cssimin, extended with cyclic schedule. The second parameter specifies name of output TrueTime initialization file. The third one specifies name of output TrueTime code of simulated loop.

The language structure of input files is described in the following subsection.

6.2. TrueTime

For time-exact simulation of schedules of iterative loops TrueTime is used. The scheduled algorithm is simulated using TrueTime Kernels. The CSSIM generates two M-files. First one is an initialization code (simple_init.m) which creates a task for the simulation and initialize variables used in the scheduled algorithm. The second one is a code function (code.m) where each code segment corresponds to a task from the schedule. Lets consider an example of digital state variable filter DSVF06, shown as CSSIM code below

function L=dsvf(I)

%Arithmetic Units Declaration
struct('operator','+','number',1,'proctime',1,'latency',1);
struct('operator','*','number',1,'proctime',3,'latency',3);

struct('frequency',220000);

%Variables Declaration
f = 50;
fs = 40000;
Q = 2;
K = 1000;

F1 = 0.0079;   %2*pi*f/fs  ||| ??? 2*sin(pi*f/fs)
Q1 = 0.5;      %1/Q;


%I = num2cell(simout);
I = ones(1,K);

L = zeros(1,K);
B = zeros(1,K);
H = zeros(1,K);
N = zeros(1,K);
FB = zeros(1,K);
QB = zeros(1,K);
IL = zeros(1,K);
FH = zeros(1,K);


%Iterative Algorithm
for k=2:K
    FB(k) = F1 * B(k-1);
    L(k)  = L(k-1) + FB(k);     %L = L + F1 * B
    QB(k) = Q1 * B(k-1);
    IL(k) = I(k) - L(k);
    H(k)  = IL(k) - QB(k);      %H = I - L -Q1*B
    FH(k) = F1 * H(k);
    B(k)  = FH(k) + B(k-1);     %B = F1 * H +B
    N(k)  = H(k) + L(k);        %N = H + L
end


L

After processing in CSSIM, as shown above, generated files (simple_init.m and code.m shown bellow) are used in simulation scheme shown in Figure 10.1, “Simulation scheme with TrueTime Kernel block”. Parameter Name of init function is set to simple_init (initialization code).

function simple_init
% 
% This file was automatically generated by CSSIM 
% 

ttInitKernel(1,1,'prioFP');% nbrOfInputs, nbrOfOutputs, fixed priority

data.frequency=220000;    %simulation frequency 
data.reg1=0;    % initialization of variable B
data.reg2=0;    % initialization of variable H
data.reg3=0;    % initialization of variable N
data.reg4=0;    % initialization of variable FB
data.reg5=0;    % initialization of variable QB
data.reg6=0;    % initialization of variable IL
data.reg7=0;    % initialization of variable FH
data.reg8=0;    % initialization of variable L
data.const1=50;    % initialization of constant f
data.const2=40000;    % initialization of constant fs
data.const3=2;    % initialization of constant Q
data.const4=1000;    % initialization of constant K
data.const5=0.007900000000000001;    % initialization of constant F1
data.const6=0.5;    % initialization of constant Q1
w=11;
period = w/data.frequency;
deadline = period;
offset = 0;
prio = 1;
ttCreatePeriodictask('task1', offset, period, prio, 'code', data);

function [exectime,data] = code(seg,data) 
% 
% This file was automatically generated by CSSIM 
% 

 i=floor(ttCurrentTime/ttGetPeriod); 
 
switch(seg) 
case 1
data.reg4 = data.const5*data.reg1;     % T1
exectime = 3/data.frequency;
case 2
data.reg8 = data.reg8+data.reg4;
ttAnalogOut(1,data.reg8);              % T2
exectime = 0/data.frequency;
case 3
data.reg5 = data.const6*data.reg1;     % T3
exectime = 1/data.frequency;
case 4
data.reg6 = ttAnalogIn(1)-data.reg8;   % T4
exectime = 2/data.frequency;
case 5
data.reg2 = data.reg6-data.reg5;       % T5
exectime = 1/data.frequency;
case 6
data.reg7 = data.const5*data.reg2;     % T6
exectime = 0/data.frequency;
case 7
data.reg3 = data.reg2+data.reg8;       % T8
exectime = 3/data.frequency;
case 8
data.reg1 = data.reg7+data.reg1;       % T7
exectime = 1/data.frequency;
case 9
exectime = -1;
end

Figure 10.1. Simulation scheme with TrueTime Kernel block

Result of the simulation is shown in Figure 10.2, “Result of simulation”.

Figure 10.2. Result of simulation

For more details see CSSIM TrueTime demo in the toolbox. For the simulation the TrueTime tool must be installed.

All main objects in TORSCHE can be exported to the XML file format. XML format includes all important information about one or more objects.

XMLSAVE command is used for export to XML for more details see to xmlsave.m.