Title :
Incorporation of reservation stations into the scheduling of DSP graphs onto heterogeneous multiprocessors
Author :
Itradat, Awni ; Ahmad, M.O. ; Shatnawi, Ali
Author_Institution :
Dept. of Electr. & Comput. Eng., Concordia Univ., Montreal, Que.
Abstract :
This paper proposes a novel technique for the scheduling of DSP applications onto a nonfully-connected heterogeneous multiprocessor system by incorporating the concept of reservation stations. In this technique, a rate optimal schedule and a processor optimal assignment of DSP data flow graphs (DFG) are obtained at the compile time, the firing times of the nodes in the DFG are then discarded, and only the processor assignment and the sequence of the nodes assigned to a certain processor are retained. At the run-time a processor begins the execution of the node only after the data needed by that node becomes available in its reservation stations. Every processor in the multiprocessor system has its own reservation stations which are employed at the run-time to hold the token data and also to store control flags used for the task of synchronization between the processors. The proposed technique can not only efficiently consider variable inter-processor communication delays but also can provide time and processor optimal schedules as well
Keywords :
data flow graphs; digital signal processing chips; multiprocessing systems; processor scheduling; synchronisation; DSP data flow graphs; DSP graph scheduling; compile time; control flags; firing time; heterogeneous multiprocessor system; processor optimal assignment; rate optimal schedule; reservation stations; token data; variable inter-processor communication delays; Application software; Communication system control; Delay effects; Digital signal processing; Multiprocessing systems; Optimal scheduling; Paper technology; Processor scheduling; Runtime; Scheduling algorithm;
Conference_Titel :
Circuits and Systems, 2005. 48th Midwest Symposium on
Conference_Location :
Covington, KY
Print_ISBN :
0-7803-9197-7
DOI :
10.1109/MWSCAS.2005.1594137