Effective Task Scheduling for Embedded Systems Using Iterative Cluster Slack Optimization

Jongdae Kim, Sungchul Lee, Hyunchul Shin

Electrical and Computer Engineering, Hanyang University, Ansan Kyeonggi-do, South Korea.

DOI: 10.4236/cs.2013.48063                

Abstract

To solve computationally expensive problems, multiple processor SoCs (MPSoCs) are frequently used. Mapping of applications to MPSoC architectures and scheduling of tasks are key problems in system level design of embedded systems. In this paper, a cluster slack optimization algorithm is described, in which the tasks in a cluster are simultaneously mapped and scheduled for heterogeneous MPSoC architectures. In our approach, the tasks are iteratively clustered and each cluster is optimized by using the branch and bound technique to capitalize on slack distribution. The proposed static task mapping and scheduling method is applied to pipelined data stream processing as well as for batch processing. In pipelined processing, the tradeoff between throughput and memory cost can be exploited by adjusting a weighting parameter. Furthermore, an energy-aware task mapping and scheduling algorithm based on our cluster slack optimization is developed. Experimental results show improvement in latency, throughput and energy.

Keywords

Multi-Processor; Mapping; Scheduling

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	P. Luh, D. Hoitomt, E. Max and K. Pattipati, “Schedule Generation and Reconfiguration for Parallel Machines,” Robotics and Automation, Vol. 6, No. 6, 1990, pp. 687696. http://dx.doi.org/10.1109/70.63271
[2]	K. Vivekanandarajah and S. Pilakkat, “Task Mapping in Heterogeneous MPSoCs for System Level Design,” 13th IEEE International Conference on Engineering of Complex Computer Systems, Belfast, 31 March 2008-3 April 2008, pp. 56-65.
[3]	T. Adams, K. Chandy and J. Dickson, “A Comparison of List Schedules for Parallel Processing Systems,” Communications of the ACM, Vol. 17, No. 12, 1974, pp. 685690. http://dx.doi.org/10.1145/361604.361619
[4]	H. Topcuoglu, S. Hariri and M. Wu, “Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, 2002, pp. 260274.
[5]	E. Ilavarasan and P. Thambidurai, “Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments,” Journal of Computer Sciences, Vol. 3, 2007, pp. 94-103.
[6]	P. Paulin and J. Knight, “Scheduling and Binding Algorithms for High-Level Synthesis,” 26th Conference on Design Automation, 25-29 June 1989, pp. 1-6. http://dx.doi.org/10.1145/74382.74383
[7]	H. Yang and S. Ha, “Pipelined Data Parallel Task Mapping/Scheduling Technique for MPSoC,” Proceedings of Design, Automation & Test in Europe Conference & Exhibition, Nice, 20-24 April 2009, pp. 69-74.
[8]	A. Wu, H. Yu, S. Jin, L. Kuo-Chi and G. Schiavone, “An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 9, 2004, pp. 824-834. http://dx.doi.org/10.1109/TPDS.2004.38
[9]	T. Tsuchiya, T. Osada and T. Kikuno, “Genetic-Based Multiprocessor Scheduling Using Task Duplication,” Microprocessors and Microsystems, Vol. 22, 1998, pp. 197-207. http://dx.doi.org/10.1016/S0141-9331(98)00079-9
[10]	K. Han and J. Kim, “Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 6, 2002, pp. 580-593. http://dx.doi.org/10.1109/TEVC.2002.804320
[11]	L. Goh, B. Veeravalli and S. Viswanathan, “Design of Fast and Efficient Energy-Aware Gradient-Based Scheduling Algorithms Heterogeneous Embedded Multiprocessor Systems,” IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 1, 2009, pp. 1-12.
[12]	Y. Yu and V. Prasanna, “Energy-Balanced Task Allocation for Collaborative Processing in Wireless Sensor Networks,” Mobile Networks and Applications, Vol. 10, 2005, pp. 115-131. http://dx.doi.org/10.1023/B:MONE.0000048550.31717.c5
[13]	A. Andrei, M. Schmitz, P. Eles, Z. Peng, B. M. AlHashimi, “Overhead-Conscious Voltage Selection for Dynamic and Leakage Energy Reduction of Time-Constrained Systems,” IEE Proceedings on Computers and Digital Techniques, Vol. 152, No. 1, 2005, pp. 28-38. http://dx.doi.org/10.1049/ip-cdt:20045055
[14]	S. Kim and J. Browne, “A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures,” Proceedings of the International Conference on Parallel Processing, 1988, pp. 1-8.
[15]	G. Zeng, T. Yokoyama, H. Tomiyama and H. Takada, “Practical Energy-Aware Scheduling for Real-Time Multiprocessor Systems,” 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Beijing, 24-26 August 2009, pp. 383392.