Yield‐driven design‐time task scheduling techniques for multi‐processor system on chips under process variation: a comparative study. Issue 4 (1st July 2015)

• Record Type: Journal Article
• Authors: Momtazpour, Mahmoud; Assare, Omid; Rahmati, Negar; Boroumand, Amirali; Barati, Saeid; Goudarzi, Maziar
• Is Part Of: IET computers & digital techniques. Volume 9:Issue 4(2015)
• Page Start: 221
• Page End: 229
• Publication Date: 2015-07-01
• Subjects: processor scheduling -- system‐on‐chip -- multiprocessing systems -- computational complexity -- integer programming -- linear programming -- graph theory -- microprocessor chips; yield‐driven design‐time task scheduling techniques -- multiprocessor system -- process variation -- multiprocessor system on chips -- MPSoC -- variability awareness -- performance yield -- variation‐aware design‐time task -- communication scheduling techniques -- sign‐off variability modelling framework -- computational complexity -- ILP‐based task scheduling technique -- large application task graphs -- one‐pass heuristic method -- near‐optimal schedules; Computers -- Periodicals; Digital electronics -- Periodicals; Computer engineering -- Periodicals; Computer architecture -- Periodicals; Computer organization -- Periodicals; 621.39
• DOI: 10.1049/iet-cdt.2014.0126
• Languages: English
• ISSNs: 1751-8601

Abstract

Abstract : Process variation has already emerged as a major concern in design of multi‐processor system on chips (MPSoC). In recent years, there have been several attempts to bring variability awareness into the task scheduling process of embedded MPSoCs to improve performance yield. This study attempts to provide a comparative study of the current variation‐aware design‐time task and communication scheduling techniques that target embedded MPSoCs. To this end, the authors first use a sign‐off variability modelling framework to accurately estimate the frequency distribution of MPSoC components. The task scheduling methods are then compared in terms of both the quality of the final solution and the computational complexity of the scheduling algorithm. Experimental results on a wide range of benchmarks show that ILP‐based task scheduling technique, while guaranteeing the optimality of the solution, can be costly for large application task graphs. On the other hand, one‐pass heuristic method is 795 times faster than ILP‐based method on average, but is ineffective to find reasonable solutions in the case of large task graphs. Finally, metaheuristic approaches can produce near‐optimal schedules within 1–2% of the optimal solutions on average, with up to 7.8 times faster execution time compared with ILP‐based approach.