Background: I have independent tasks shown as dataflow graphs (which iterate forever). Extremely simple example:
task 1: b1 -> c
task 2: e -> b2
Processor assignment is given. The graph itself explains available processors on which they will be executed. for above example b1 and b2 are executed on processor b, c on c and e on e.
Execution times of all tasks are known at compile time. Since it is round robin modeling, the worst case execution times of each task is modified to capture resource arbitration for round-robin scheduling. Example: lets say originally all tasks in above example had exec time 1. Then we change the timings to b1 and b2 take 2 time units, c and e take 1. This is coz processor b runs following code: while(1) { run_task_b1(); run_task_b2(); } Therefore effectively if we analyze task1 (for throughput, etc) to say task b1 takes 2 time units, suffices the sharing of b1 and b2 on processor b.
My problem: Each tasks uses additional resource (DMAs). Let say we have 2 DMAs. If we naively allot D1 and D2 as follows:
b1 gets D1
c gets D2
e gets D1
b2 gets D2
Then after round-robin modeling b1 and b2 get execution time 3 (coz b1 shares D1 with e and b1,b2 share processor b, 1+1+1 = 3) and c and e get time 2 (coz c shared D2 with b2 and e shares D1 with b1). So times are 3,2,2,3.
But if we give allotment as: b1 gets D1
c gets D2
e gets D2
b2 gets D1
Modeled execution times are 2,2,2,2.
So how to make an algorithm to find the resource (the DMAs) assignment at compile time (static assignment) for given tasks graphs such that modeled RR times are minimum? List scheduling will give inefficient results as explained in above example.
