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.

References

1. 1)
  - 13. Assare, O., Rad, H.I., Momtazpour, M., Sanaei, E., Goudarzi, M.: ‘VAREX: A post-P& R variability modeling framework for multiprocessor SoCs’. IEEE/ACM Workshop on Variability Modeling and Characterization (VMC), November 2011.
2. 2)
  - 25. Cadence Encounter Digital Implementation System: [Online]. Available at http://www.cadence.com/products/di/edi_system/.
3. 3)
  - 11. Ghorbani, M.: ‘A variation and energy aware ILP formulation for task scheduling in MPSoC’. 13th Int. Symp. on Quality Electronic Design, March 2012, pp. 772–777.
4. 4)
  - 14. Assare, O., Momtazpour, M., Goudarzi, M.: ‘Accurate estimation of leakage power variability in sub-micrometer CMOS circuits’. Process of Publication in 15th Euromicro Conf. on Digital System Design (DSD'12), September 2012.
5. 5)
  - 29. MATLAB, The MathWorks Inc.: [Online]. Available at http://www.mathworks.com/products.
6. 6)
  - 30. CPLEX Optimization software package: [Online]. Available at http://www.cplex.com/.
7. 7)
  - 23. Synopsys Design Compiler: [Online]. Available at http://www.synopsys.com/tools/implementation.
8. 8)
  - 20. Brucker, P.: ‘Scheduling algorithms’ (Springer, 2007, 5th edn.).
9. 9)
  - 24. The NanGate 45 nm Open Cell Library: ‘An open source standard cell library’, [Online]. Available at http://www.nangate.com.
10. 10)
  - 5. Chon, H., Kim, T.: ‘Timing variation-aware task scheduling and binding for MPSoC’. Asia and South Pacific Design Automation Conf. (ASPDAC'09), January 2009, pp. 137–142.
11. 11)
  - 10. Bhardwaj, K., Roy, S., Chakraborty, K.: ‘Power-performance yield optimization for MPSoCs using MILP’. 13th Int. Symp. on Quality Electronic Design, March 2012, pp. 764–771.
12. 12)
  - 15. Chandra, S., Lahiri, K., Raghunathan, A., Dey, S.: ‘Considering process variations during system-level power analysis’. Int. Symp. on Low Power Electronics and Design (ISLPED'06), October 2006, pp. 342–345.
13. 13)
  - 22. LEON3 multiprocessor: [Online]. Available at http://www.gaisler.com/index.php/products/processors/leon3.
14. 14)
  - 18. R Development Core Team: ‘R:A language and environment for statistical computing’ (R Foundation for Statistical Computing, Vienna, Austria, 2007).
15. 15)
  - 21. Alander, J.: ‘On optimal population size of genetic algorithms’. Proc. CompEuro ‘92. ‘Computer Systems and Software Engineering’, May 1992, pp. 65–70.
16. 16)
  - 12. Sarangi, S., Greskamp, B., Teodorescu, R., Nakano, J., Tiwari, A., Torrellas, J.: ‘VARIUS: A model of process variation and resulting timing errors for microarchitects’, IEEE Trans. Semicond. Manuf. (SM), 2008, 21, (1), pp. 3–13 (doi: 10.1109/TSM.2007.913186).
17. 17)
  - 7. Momtazpour, M., Goudarzi, M., Sanaei, E.: ‘Variation-aware task and communication scheduling in MPSoCs for power-yield maximization’, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2010, E93.A, (12), pp. 2542–2550 (doi: 10.1587/transfun.E93.A.2542).
18. 18)
  - 16. Teodorescu, R., Torrellas, J.: ‘Variation-aware application scheduling and power management for chip multiprocessors’. 35th Int. Symp. on Computer Architecture (ISCA'08), June 2008, pp. 363–374.
19. 19)
  - 17. Karnik, T., Borkar, S., De, V.: ‘Probabilistic and variation-tolerant design: Key to continued moores law’. ACM/IEEE TAU Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, February 2004.
20. 20)
  - 8. Momtazpour, M., Goudarzi, M., Sanaei, E.: ‘Static statistical MPSoC power optimization by variation-aware task and communication scheduling’, Elsevier J. Microprocess. Microsyst., Spec. Issue Embed. Multicore Syst., 2012, 37, (8), pp. 953–963 (doi: 10.1016/j.micpro.2012.02.008).
21. 21)
  - 28. LEON3 Cycle-True Simulator: [Online]. Available at http://www.gaisler.com/index.php/products/simulators/tsim.
22. 22)
  - 1. Wang, F., Nicopoulos, C., Wu, X., Xie, Y., Vijaykrishnan, N.: ‘Variation-aware task allocation and scheduling for MPSoC’. IEEE/ACM Int. Conf. on Computer-Aided Design (ICCAD'07), November 2007, pp. 598–603.
23. 23)
  - 9. Singhal, L., Kooti, H., Bozorgzadeh, E.: ‘Process variation-aware task replication for throughput optimization in configurable MPSoCS’. Electronic System Level Synthesis Conf. (ESLsyn), June 2012, pp. 44–49.
24. 24)
  - 27. MiBench Embedded System Benchmark Suite: [Online]. Available at http://www.eecs.umich.edu/mibench/.
25. 25)
  - 6. Huang, L., Xu, Q.: ‘Performance yield-driven task allocation and scheduling for MPSoCs under process variation’. 47th Design Automation Conf. (DAC'10), June 2010, pp. 326–331.
26. 26)
  - 19. Schrijver, A.: ‘Theory of linear and integer programming’ (Wiley, 1987).
27. 27)
  - 26. Dick, R.: ‘Embedded Systems Synthesis Benchmark Suites (E3S)’. [Online]. Available at http://ziyang.eecs.umich.edu/~dickrp/e3s.
28. 28)
  - 3. Singhal, L., Oh, S., Bozorgzadeh, E.: ‘Yield maximization for system-level task assignment and configuration selection of configurable multiprocessors’. Sixth IEEE/ACM/IFIP IntConf. on Hardware/Software Codesign and System Synthesis (CODES + ISSS'08), 2008, pp. 249–254.
29. 29)
  - 2. Wang, F., Chen, Y., Nicopoulos, C., Wu, X., Xie, Y., Vijaykrishnan, N.: ‘Variation-aware task and communication mapping for MPSoC architecture’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. (TCAD), 2011, 30, (2), pp. 295–307 (doi: 10.1109/TCAD.2010.2077830).
30. 30)
  - 4. Mirzoyan, D., Akesson, B., Goossens, K.: ‘Process-variation aware mapping of best-effort and real-time streaming applications to MPSoCs’, To Appear In: ACM Trans. Embed. Comput. Syst. (TECS), 2013, 13, (2s), pp. 1–24.

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

References

Related content