http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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)
      • F. Wang , C. Nicopoulos , X. Wu , Y. Xie , N. Vijaykrishnan .
        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. 598603.
        . IEEE/ACM Int. Conf. on Computer-Aided Design (ICCAD'07) , 598 - 603
    2. 2)
    3. 3)
      • L. Singhal , S. Oh , E. Bozorgzadeh .
        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. 249254.
        . Sixth IEEE/ACM/IFIP IntConf. on Hardware/Software Codesign and System Synthesis (CODES + ISSS'08) , 249 - 254
    4. 4)
      • D. Mirzoyan , B. Akesson , K. Goossens .
        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. 124.
        . To Appear In: ACM Trans. Embed. Comput. Syst. (TECS) , 1 - 24
    5. 5)
      • H. Chon , T. Kim .
        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. 137142.
        . Asia and South Pacific Design Automation Conf. (ASPDAC'09) , 137 - 142
    6. 6)
      • L. Huang , Q. Xu .
        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. 326331.
        . 47th Design Automation Conf. (DAC'10) , 326 - 331
    7. 7)
    8. 8)
    9. 9)
      • L. Singhal , H. Kooti , E. Bozorgzadeh .
        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. 4449.
        . Electronic System Level Synthesis Conf. (ESLsyn) , 44 - 49
    10. 10)
      • K. Bhardwaj , S. Roy , K. Chakraborty .
        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. 764771.
        . 13th Int. Symp. on Quality Electronic Design , 764 - 771
    11. 11)
      • M. Ghorbani .
        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. 772777.
        . 13th Int. Symp. on Quality Electronic Design , 772 - 777
    12. 12)
    13. 13)
      • O. Assare , H.I. Rad , M. Momtazpour , E. Sanaei , M. Goudarzi .
        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.
        . IEEE/ACM Workshop on Variability Modeling and Characterization (VMC)
    14. 14)
      • O. Assare , M. Momtazpour , M. Goudarzi .
        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.
        . Process of Publication in 15th Euromicro Conf. on Digital System Design (DSD'12)
    15. 15)
      • S. Chandra , K. Lahiri , A. Raghunathan , S. Dey .
        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. 342345.
        . Int. Symp. on Low Power Electronics and Design (ISLPED'06) , 342 - 345
    16. 16)
      • R. Teodorescu , J. Torrellas .
        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. 363374.
        . 35th Int. Symp. on Computer Architecture (ISCA'08) , 363 - 374
    17. 17)
      • T. Karnik , S. Borkar , V. De .
        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.
        . ACM/IEEE TAU Workshop on Timing Issues in the Specification and Synthesis of Digital Systems
    18. 18)
      • (2007)
        18. R Development Core Team: ‘R:A language and environment for statistical computing’ (R Foundation for Statistical Computing, Vienna, Austria, 2007).
        .
    19. 19)
      • A. Schrijver . (1987)
        19. Schrijver, A.: ‘Theory of linear and integer programming’ (Wiley, 1987).
        .
    20. 20)
      • P. Brucker . (2007)
        20. Brucker, P.: ‘Scheduling algorithms’ (Springer, 2007, 5th edn.).
        .
    21. 21)
      • J. Alander .
        21. Alander, J.: ‘On optimal population size of genetic algorithms’. Proc. CompEuro ‘92. ‘Computer Systems and Software Engineering’, May 1992, pp. 6570.
        . Proc. CompEuro ‘92. ‘Computer Systems and Software Engineering’ , 65 - 70
    22. 22)
      • 22. LEON3 multiprocessor: [Online]. Available at http://www.gaisler.com/index.php/products/processors/leon3.
        .
    23. 23)
      • 23. Synopsys Design Compiler: [Online]. Available at http://www.synopsys.com/tools/implementation.
        .
    24. 24)
      • 24. The NanGate 45 nm Open Cell Library: ‘An open source standard cell library’, [Online]. Available at http://www.nangate.com.
        .
    25. 25)
      • 25. Cadence Encounter Digital Implementation System: [Online]. Available at http://www.cadence.com/products/di/edi_system/.
        .
    26. 26)
      • R. Dick .
        26. Dick, R.: ‘Embedded Systems Synthesis Benchmark Suites (E3S)’. [Online]. Available at http://ziyang.eecs.umich.edu/~dickrp/e3s.
        .
    27. 27)
      • 27. MiBench Embedded System Benchmark Suite: [Online]. Available at http://www.eecs.umich.edu/mibench/.
        .
    28. 28)
      • 28. LEON3 Cycle-True Simulator: [Online]. Available at http://www.gaisler.com/index.php/products/simulators/tsim.
        .
    29. 29)
      • 29. MATLAB, The MathWorks Inc.: [Online]. Available at http://www.mathworks.com/products.
        .
    30. 30)
      • 30. CPLEX Optimization software package: [Online]. Available at http://www.cplex.com/.
        .
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2014.0126
Loading

Related content

content/journals/10.1049/iet-cdt.2014.0126
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address