|
Vol: 60(74) No: 1 / March 2015 Analyzing the Effect of Decomposition Algorithms on the Heterogeneous Multiprocessing Architectures in System Level Synthesis Péter Arató Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Budapest, Hungary Dániel András Drexler Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Budapest, Hungary, e-mail: drexler@iit.bme.hu György Rácz Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Budapest, Hungary, e-mail: gyuriracz@iit.bme.hu Keywords: loop-free graph decomposition, inertial method, directed acyclic graph, heterogeneous multiprocessing systems. Abstract The decomposition algorithms influence essentially the resulting architecture of heterogeneous multiprocessing systems. By assigning a task-segment to each of the mostly different types of component processors (CPUs, DSPs, GPUs, FPGAs, etc.), the decomposition algorithm should try to fulfill several system requirements, parameters and their priority order during the system level synthesis phase. We compare two decomposition algorithms that preserve the loop-free property of the initial task graph. The first algorithm begins with generating the list of those possible cuts in the task graph that do not create segment-cycles. Thereafter, the proper cuts are selected from the list based on a global cost function. Although this algorithm may generate all the possible results, the list generation is not unique, and its optimality cannot be guaranteed. The second algorithm generates segments based on the distance of the vertices from the input nodes of the task graph. This algorithm can incorporate local cost functions; however it can not generate all the possible loop-free results. Thus, the second algorithm can be parameterized more effectively, but its search space is smaller than that of the first one. We analyze, evaluate and compare the effects of both types of decomposition algorithms by redesigning two existing heterogeneous multiprocessing architectures according to various requirements. References [1] S. Deniziak, “Cost-efficient synthesis of multiprocessor heterogeneous systems,” Control and Cybernetics, vol. 33, no. 2, pp. 341–355, 2004. [2] A. A. Jerraya and W. Wolf, Multiprocessor Systems-on Chip, ser. Systems on Silicon. Morgan Kaufmann Publishers (Elsevier), 2005. [3] S. Arumugam, I. S. Hamid, and V. Abraham, “Decomposition of graphs into paths and cycles,” Journal of Discrete Mathematics, pp. 1–6, 2013. [4] Z. A. Mann, A. Orbán, and P. Arató, “Finding optimal hardware/software partitions,” Formal Methods in System Design, vol. 31, no. 3, pp. 241–263, December 2007. [5] P. Arató, Z. Ádám Mann, and A. Orbán, “Extending component-based design with hardware components,” Science of Computer Programming, vol. 56, no. 1 - 2, pp. 23 – 39, 2005. [6] M. Abdelhalim, A. Salama, and S. Habib, “Hardware software partitioning using particle swarm optimization technique,” in Proceedings of 6th International Workshop on System-on-Chip for Real-Time Applications, December 2006, pp. 189 –194. [7] W. Wolf, “A decade of hardware/software codesign,” Computer, vol. 36, no. 4, pp. 38 – 43, April 2003. [8] S. Sasaki, T. Nishihara, D. Ando, and M. Fujita, “Hardware/software codesign and verification methodology from system level based on system dependence graph,” Journal of Universal Computer Science, vol. 13, no. 13, pp. 1972–2001, 2007. [9] M. Purnaprajna, M. Reformat, and W. Pedrycz, “Genetic algorithms for hardware-software partitioning and optimal resource allocation,” Journal of Systems Architecture, vol. 53, no. 7, pp. 339–354, July 2007. [10] P. Arató, T. Visegrády, and I. Jankovits, High-level Synthesis of Pipelined Datapaths. John Wiley & Sons, 2001. [11] B. Hendrickson and R. Leland, “The chaco user’s guide: Version 2.0,” 1994. [12] G. Karypis and V. Kumar, “hmetis a hypergraph partitioning package, version 1.5.3,” 1998. [13] P. Arató, D. A. Drexler, and G. Kocza, “A method for avoiding loops while decomposing the task description graph in system-level synthesis,” in Proceedings of the 2014 IEEE 9th International Symposium on Applied Computational Intelligence and Informatics (SACI 2014), Timisoara, Romania, 2014, pp. 231–235. [14] P. Arató, D. A. Drexler, and G. Kocza, ”Loop-free Decomposition in High-Level Synthesis”, Scientific Bulletin of the Politehnica University of Timisoara, Transactions on Automatic Control and Computer Science, vol. 59(73), no . 2, pp. 99-104, Dec. 2014. [15] D. A. Drexler and P. Arató, “A modified inertial method for loopfree decomposition of acyclic directed graphs,” in Proceedings of 5th International Conference on Recent Achievements in Mechatronics, Automation, Computer Science and Robotics, 2015, pp. 63–74. [16] D. A. Drexler and P. Arató, “Comparison of two loop free decomposition methods”, in Proceedings of IEEE 10th Jubilee International Symposium on, Applied Computational Intelligence and Informatics (SACI 2015), Timisoara, Romania, 2015, pp. 477–481. [17] György Rácz and Péter Arató, “A Method for Generating, Evaluating and Comparing Various System-level Synthesis Results in Designing Multiprocessing Systems”, Submitted to Design Automation for Embedded Systems (under review). |