Scheduling algorithm based on storage capacity of communication in hardware/software integrated system

Abstract

In this paper, the storage capacity of communication among cores and processors is taken into account and a maximum D-value-first algorithm is proposed. By improving the hardware parallelism in the task execution process, the maximum storage requirements for communication are minimized. Experimental results with various directed acyclic graph models showed that compared with the earliest-task-first algorithm, the storage requirements for communication were reduced by 22.46%, on average, while the average of makespan only increased by 0.82%.

Keywords

hardware/software partitioning / scheduling algorithm / storage capacity / communication

References

[1] Monmasson E, Cirstea M N. FPGA design methodology for industrial control systems—A review[J]. IEEE Transactions on Industrial Electronics, 2007, 54(4): 1824-1842.

[2] Cataldi P, Grangetto M, Tillo T, et al. Sliding-window raptor codes for efficient scalable wireless video broadcasting with unequal loss protection[J]. IEEE Transactions on Image Processing, 2010, 19(6): 1491-1503.

[3] Knudsen P V, Madsen J. PACE: A dynamic programming algorithm for hardware/software partitioning[C]. Proceedings of the 4th International Workshop on Hardware/Software Co-Design, 1996.

[4] Purnaprajna M, Reformat M, Pedrycz W. Genetic algorithms for hardware-software partitioning and optimal resource allocation[J]. Journal of Systems Architecture, 2007, 53(7): 339-354.

[5] Li S A, Hsu C C, Wong C C, et al. Hardware/software codesign for particle swarm optimization algorithm[J]. Information Sciences, 2011, 181(20): 4582-4596.

[6] Ferrandi F, Lanzi P L, Pilato C, et al. Ant colony optimization for mapping, scheduling and placing in reconfigurable systems[C]. 2013 NASA/ESA Conference on Adaptive Hardware and Systems (AHS), 2013.

[7] Quan H, Zhang T, Guo Jichang. Hardware/software partitioning method based on improved artificial fish swarm algorithm[J]. Journal of Tianjin University (Science and Technology), 2013, 46(10): 923-928.

[8] Shrivastava A, Kumar H, Kapoor S, et al. Optimal hardware/software partitioning for concurrent specification using dynamic programming[C]. Thirteenth International Conference on VLSI Design, 2000.

[9] Chang J M, Pedram M. Codex-dp: Co-design of communicating systems using dynamic programming[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(7): 732-744.

[10] Wu J G, Srikanthan T. Low-complex dynamic programming algorithm for hardware/software partitioning[J]. Information Processing Letters, 2006, 98(2): 41-46.

[11] Yu S D, Liu L B, Yin S Y, et al. Hardware-software codesign flow for embedded coarse-grained reconfigurable processor[J]. Acta Electronica Sinica, 2009, 37(5): 1136-1140.

[12] Kuang S R, Chen C Y, Liao R Z. Partitioning and pipelined scheduling of embedded system using integer linear programming[C]. 11th International Conference on Parallel and Distributed Systems, 2005.

[13] Sinnen O, Sousa L A. Communication contention in task scheduling[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(6): 503-515.

[14] Sjøberg D I K, Hannay J E, Hansen O, et al. A survey of controlled experiments in software engineering[J]. IEEE Transactions on Software Engineering, 2005, 31(9): 733-753.

[15] Wiangtong T, Cheung P Y K, Luk W. Hardware/software codesign: A systematic approach targeting data-intensive applications[J]. IEEE Signal Processing Magazine, 2005, 22(3): 14-22.

[16] Maylor H. Beyond the Gantt chart: Project management moving on[J]. European Management Journal, 2001, 19(1): 92-100.