Multi-processor system on chip (MPSoC) consists of multiple cores communicating via an on-chip communication backplane. An application to be executed on an MPSoC is represented using a task graph where a node represents an operation to be scheduled on a core and the edges represent the communication between these operations. Typically task graph scheduling on MPSoC is done statically during hardware–software co-design, based on estimated execution times. Static scheduling makes a program non-portable, hence dynamic scheduling is preferred. In this study, the authors present hardware-based dynamic feedback-driven task rescheduling heuristic that executes in real time. This task scheduling heuristic is based on the observation that during the course of execution, an application goes through a phase where a sub-graph (phase graph) of the application task graph repeatedly executes for a very large number of times. The proposed approach is iterative, where the schedule length of a phase graph converges to a smaller value in subsequent iterations. Experimental results show (i) real-time scheduling can be performed using proposed game theoretic approach which converges to a minimum in fewer than 100 iterations (ii) reducing the schedule length ranging 3–16% as compared with greedy heuristic.

References

1. 1)
  - 19. Chen, Y., Shih, C., Kuo, T.: ‘Dynamic task scheduling and processing element allocation for multi-function SoCs’. Real Time and Embedded Technology and Applications Symp., 2007, pp. 81–90.
2. 2)
  - 1. Vallerio, K.S., Jha, N.K.: ‘Task graph extraction for embedded system synthesis’. 16th Int. Conf. VLSI Design, 2003, pp. 480–486.
3. 3)
  - 30. Sun, F., Ravi, S., Raghunathan, A., Jha, N.K.: ‘Application-specific heterogeneous multiprocessor synthesis using extensible processors’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.,2006, 25, (9), pp. 1589–1602 (doi: 10.1109/TCAD.2005.858269).
4. 4)
  - 7. Sherwood, T., Perelman, E., Calder, B.: ‘Basic block distribution analysis to find periodic behavior and simulation points in applications’. Int. Conf. on Parallel Architectures and Compilation Techniques, 2001, pp. 3–14.
5. 5)
  - 11. Isci, C., Buyuktosunoglu, A., Martonosi, M.: ‘Long-term workload phases: duration predictions and applications to DVFS’, Micro, IEEE, 2005, 25, (5), pp. 39–51 (doi: 10.1109/MM.2005.93).
6. 6)
  - 8. Denning, P.J.: ‘The working set model for program behavior’, Commun. ACM, 1968, 11, (5), pp. 323–333 (doi: 10.1145/363095.363141).
7. 7)
  - 14. Dhodapkar, A.S., Smith, J.E.: ‘Managing multi-configuration hardware via dynamic working set analysis’, SIGARCH Comput. Archit. News, 2002, 30, (2), pp. 233–244 (doi: 10.1145/545214.545241).
8. 8)
  - 16. Theocharides, T., Michael, M.K., Polycarpou, M., Dingankar, A.: ‘Towards embedded runtime system level optimization for MPSoCs: On-chip task allocation’. Proc. 19th ACM Great Lakes Symp. VLSI ACM, New York, NY, USA, 2009, pp. 121–124.
9. 9)
  - 4. Khan, O., Kundu, S.: ‘Microvisor: a runtime architecture for thermal management in chip multiprocessors’, In Stenström, P. (Ed.): ‘Transactions on high-performance embedded architectures and Compilers IV’ (Springer-Verlag, Berlin, Heidelberg84–110, 2011) .
10. 10)
  - 6. Sherwood, T., Sair, S., Calder, B.: ‘Phase tracking and prediction’. Proc. 30th Annual Int. Symp. on Computer Architecture, New York, NY, USA, 2003, pp. 336–349.
11. 11)
  - 27. Krishnan, V., Katkoori, S.: ‘TABS: temperature-aware layout-driven behavioral synthesis’, IEEE Trans. Very Large Scale Integr. Syst., 2010, 18, (12), pp. 1649–1659 (doi: 10.1109/TVLSI.2009.2026047).
12. 12)
  - 29. Goh, L.K., Veeravalli, B., Viswanathan, S.: ‘Design of fast and efficient energy-aware gradient-based scheduling algorithms heterogeneous embedded multiprocessor systems’, IEEE Trans. Parallel Distrib. Syst.,2009, 20, (1), pp. 1–12 (doi: 10.1109/TPDS.2008.55).
13. 13)
  - 26. Ferrandi, F., Lanzi, P.L., Pilato, C., Sciuto, D., Tumeo, A.: ‘Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.,2010, 29, (6), pp. 9110–924 (doi: 10.1109/TCAD.2010.2048354).
14. 14)
  - 28. Mukherjee, R., Memik, S.O.: ‘An integrated approach to thermal management in high-level synthesis’, , IEEE Trans. Very Large Scale Integr. Syst., 2006, 14, (11), pp. 1165–1174 (doi: 10.1109/TVLSI.2006.886408).
15. 15)
  - 5. http://www.android.com/.
16. 16)
  - 18. Rao, V., Navet, N., Singhal, G., Kumar, A., Visweswaran, G.S.: ‘Battery aware dynamic scheduling for periodic task graphs’. 20th Int. Parallel and Distributed Processing Symp., 2006, pp. 25–29.
17. 17)
  - 21. Cong, J., Liu, B., Zhang, Z.: ‘Scheduling with soft constraints’. Proc. Int. Conf. Computer-Aided Design, 2009, pp. 47–54.
18. 18)
  - 12. Mogul, J.C., Mudigonda, J., Binkert, N., Ranganathan, P., Talwar, V.: ‘Using asymmetric single-ISA CMPs to save energy on operating systems’, Micro, IEEE, 2008, 28, (3), pp. 26–41 (doi: 10.1109/MM.2008.47).
19. 19)
  - 15. Smith, J.E., Dhodapkar, A.S.: ‘Dynamic microarchitecture adaptation via co-designed virtual machines’. Solid-State Circuits Conf., IEEE Int., 2002, Vol. 1, pp. 198–199.
20. 20)
  - 3. Ganeshpure, K., Kundu, S.: ‘On run-time task graph extraction in MPSoC’. Int. Symp. VLSI. ISVLSI, 2013.
21. 21)
  - 32. Sengupta, D., Saleh, R.A.: ‘Application-driven voltage-island partitioning for low-power system-on-chip design’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst.2009, 28, (3), pp. 316–326 (doi: 10.1109/TCAD.2009.2013270).
22. 22)
  - 24. Nash, J.: ‘Non cooperative games’, Ann. Math., 1951, 54, pp. 286–295 (doi: 10.2307/1969529).
23. 23)
  - 2. Ganeshpure, K., Kundu, S.: ‘On run time task graph extraction of SoC’. SoC Design Conf. (ISOCC), Int., 2010, pp. 380–383.
24. 24)
  - 31. Dick, R.P., Rhodes, D.L., Wolf, W.: ‘TGFF: task graphs for free’. Proc. Sixth Int. Workshop on Hardware/Software Codesign, 1998, pp. 97–101.
25. 25)
  - 22. Ahmad, I., Ranka, S., Khan, S.U.: ‘Using game theory for scheduling tasks on multi-core processors for simultaneous optimization of performance and energy’. IEEE Int. Symp. on Parallel and Distributed Processing, 2008, pp. 1–6.
26. 26)
  - 25. Khan, O., Kundu, S.: ‘Run-time reconfiguration for performance and power optimizations in heterogeneous chip multiprocessors’. Third HiPEAC Workshop on Reconfigurable Computing, January 2009.
27. 27)
  - 13. Chakraborty, K., Wells, P.M., Sohi, G.S.: ‘Computation spreading: employing hardware migration to specialize CMP cores on-the-fly’. Proc. 12th Int. Conf. on Architectural Support for Programming Languages and Operating Systems ACM, New York, NY, USA, 2006, pp. 283–292.
28. 28)
  - 9. Klaiber, A.: ‘The technology behind crusoe™ processors’, Transmeta white paper, 2000.
29. 29)
  - 23. Tannenbaum, A., Steen, M.: ‘Distributed operating systems: principles and paradgims’, (Prentice Hall, 2nd edn.).
30. 30)
  - 10. Tosun, S., Mansouri, N., Kandemir, M., Ozturk, O.: ‘An ILP formulation for task scheduling on heterogeneous chip multiprocessors’. Computer and Information Sciences, 21st Int. Symp. on, 2006, pp. 267–276.
31. 31)
  - 17. Puschini, D., Clermidy, F., Benoit, P., Sassatelli, G., Torres, L.: ‘Game-theoretic approach for temperature-aware frequency assignment with task synchronization on MP-SoC’. Int. Conf. on Reconfigurable Computing and FPGAs, 2008, pp. 235–240.
32. 32)
  - 20. Wang, Y., Liu, D., Wang, M., Qin, Z., Shao, Z.: ‘Optimal task scheduling by removing inter-core communication overhead for streaming applications on MPSoC’. Real-Time and Embedded Technology and Applications Symp., 2010, pp. 195–204.

Game theoretic approach for run-time task scheduling on an multi-processor system on chip

References

Related content