Yield-driven design-time task scheduling techniques for multi-processor system on chips under process variation: a comparative study

• Published in: Chronic diseases and translational medicine 2015-07, Vol.9 (4), p.221-229
• Main Authors: Momtazpour, Mahmoud, Assare, Omid, Rahmati, Negar, Boroumand, Amirali, Barati, Saeid, Goudarzi, Maziar
• Format: Article
• Language: English
• Subjects: Algorithms; Communication; communication scheduling techniques; computational complexity; Critical path; Frequency distribution; graph theory; Graphs; Heuristic; Heuristic methods; ILP‐based task scheduling technique; integer programming; large application task graphs; Linear programming; Mathematical models; microprocessor chips; MPSoC; multiprocessing systems; multiprocessor system; multiprocessor system on chips; near‐optimal schedules; one‐pass heuristic method; Optimization; performance yield; process variation; Processing speed; processor scheduling; Random variables; Scheduling; sign‐off variability modelling framework; Special Issue: Designing with Uncertainty - Opportunities & Challenges; Statistical analysis; System on chip; Task scheduling; Tasks; Transistors; variability awareness; variation‐aware design‐time task; yield‐driven design‐time task scheduling techniques
• ISSN: 1751-8601; 1751-861X; 2095-882X; 1751-861X; 2589-0514
• DOI: 10.1049/iet-cdt.2014.0126

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.