Matlab and Ptolemy/Matlab Interface

by Brian L. Evans and Praveen K. Murthy

November 9, 1995, DSP Design Group Meeting

Introduction - Demonstrations - Testing Schedulers - Ptolemy/Matlab Interface - Conclusion

Nov. 16th Talk: Filter Design with Matlab

Nov. 30th Talk: Tool Collaboration with Matlab in Design



For Praveen's demonstrations, you will need to set the Matlab path. In Unix, evaluate the following before running "matlab":
setenv MATLABPATH /users/murthy/matlab:/users/murthy/matlab/graphAlgs
setenv MATLABPATH ${MATLABPATH}:/users/murthy/matlab/numberAlgs
setenv MATLABPATH ${MATLABPATH}:/users/murthy/matlab/maxAlgebra
setenv MATLABPATH ${MATLABPATH}:/users/murthy/matlab/dagMinbufS

Testing Schedulers (Praveen Murthy)

I have used Matlab for a lot of scheduling related prototyping. It is the language I use most often because it is a) interpreted, not compiled, and b) has extensive plotting and visualization tools making it unnecessary to hack anything on your own. While Matlab's use in signal processing and controls is well known (because of the extensive toolboxes that are available), it is perhaps surprising that it should be useful for graph-theoretic algorithms and such but it is really a simple programming language that is useful for prototyping for me. In fact, Friedlander at UC-Davis has been prototyping a compiler using Matlab!

Most schedulers are rather boring since they take graph incidence matrices as input and return...a list containing when nodes should be fired.

However, I had an idea one morning, prototyped it one afternoon, and forgot about pursuing it that night after it became apparent that the problem was too hard. Anyway, this scheduler just does a dynamic multiprocessor schedule for an HSDF graph greedily (assign tasks to processors when they become available, break ties using some reasonable criterion which escapes me now). The point though was to see how the dynamic schedule evolves, and what its steady state period is, and whether it is possible to predict theoretically, what the optimum "blocking factor" is when the number of processors is restricted. The idea then would be to take as the schedule, the periodic pattern that emerges. An attraction of this approach is that IPC cost can also be taken into account, and as long as the procedure is deterministic (i.e, it doesn't start flipping coins anywhere), the periodic steady state behavior holds. It would be interesting to see how this periodic pattern compares to, say, Sih's heuristic which only takes one iteration into account. The Matlab prototype showed that some very interesting patterns do emerge, but they do not seem to correspond in any way to the graphs (or max-algebra matrices) that arise in my blocking factor paper where the question was explored for the case of an unrestricted number of processors.

In Matlab, I invoke:

>> help asap

function schedule=asap(A0,A1,execTimes,m,numTicks)
Generate an ASAP schedule for a graph G given m processors.
G is a unirate, SDF graph.
Inputs: A0 = G with 0 delay arcs
	A1 = G with 1 delay arcs
	execTimes = execution times of nodes
	m = # procs
	numTicks = number of clock ticks to simulate

>> a0=randdag(6);  % Create a random 6-node acyclic graph
>> a1=zeros(6,6);  % For simplicity, this graph does not have any delay edges
>> et=[1,3,2,1,2,3]; % Arbitrarily chosen execTimes
>> s=asap(a0,a1,et,2,70) % Simulate for 70 ticks, on 3 processors

s =
 1b  ac e f  b  ac e f  b  dac e f  b  dac e f  b  dac e f  b  dac e f  b  
 2db  dac e f  db  dac e f  b  dac e f  b  dac e f  b  dac e f  b  dac e 

The crude gantt chart shows that a cyclostatic pattern emerges after a short transient.

Ptolemy Interface to Matlab


Last modified 04/10/97.