|
Vol: 59(73) No: 2 / December 2014 Loop-free Decomposition in High-Level Synthesis Péter Arató Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Budapest, Hungary, e-mail: arato@iit.bme.hu 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 Gábor Kocza Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Budapest, Hungary, e-mail: gkocza@gmail.com Keywords: system-level synthesis, heterogeneous systems, graph cutting, directed acyclic graph Abstract Decomposition of data flow-like graphs into graphs with smaller number of nodes is a common task in high-level synthesis. However, it is desirable to ensure that a loop-free graph remains loop-free after the decomposition. We propose a decomposition algorithm that generates the set of cuts that define loop-free partitions of the originally loop-free graph. We extend the algorithm to be able to take optimization criteria into consideration. Weights are associated to the edges of the graph, and the decomposition algorithm generates a partitioning of the graph such that the sum of the weights of the edges along the cuts is minimal. The loop-free property of the resulting graph is proved if the initial graph is loop-free. The algorithms are demonstrated on simple examples. References 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, Timisoara, Romania, 2014, pp. 231–235. [2] J. Merrill, “GENERIC and GIMPLE: A New Tree Representation for Entire Functions,” in Proceedings of the 2003 GCC Summit. Red Hat, Inc., 2003. [3] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, “Efficiently computing static single assignment form and the control dependence graph,” ACM Transactions on Programming Languages and Systems, vol. 13, no. 4, pp. 451–490, Oct. 1991. [4] D. W. Watson, J. K. Antonio, H. J. Siegel, and M. J. Atallah, “Static program decomposition among machines in an SIMD/SPMD heterogeneous environment with non-constant mode switching costs,” in Proceedings of the Heterogeneous Computing Workshop, 1994, pp. 58–65. [5] J. Hou and W. Wolf, “Process partitioning for distributed embedded systems,” in Proceedings of the 4th International Workshop on Hardware/Software Co-Design, ser. CODES ’96. Washington, DC, USA: IEEE Computer Society, 1996, pp. 70–76. [6] P. V. Knudsen and J. Madsen, “Pace: A dynamic programming algorithm for hardware/software partitioning,” in Proceedings of the 4th International Workshop on Hardware/Software Co-Design, ser. CODES ’96. Washington, DC, USA: IEEE Computer Society, 1996, pp. 85–92. [7] 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. [8] P. Arató, Z. A. Mann, and A. Orbán, “Algorithmic aspects of hardware/software partitioning,” ACM Transactions on Design Automation Electronic Systems, vol. 10, no. 1, pp. 136–156, January 2005. [9] 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. [10] W. Wolf, “A decade of hardware/software codesign,” Computer, vol. 36, no. 4, pp. 38 – 43, April 2003. [11] P. Arató, S. Juhász, Z. Ádám Mann, and A. Orbán, “Hardware/software partitioning in embedded system design,” in Proceedings of the IEEE International Symposium on Intelligent Signal Processing, 2003, pp. 197–202. [12] M. Abdelhalim, A. Salama, and S. Habib, “Hardware software partitioning using particle swarm optimization technique,” in Proceedings of the 6th International Workshop on System-on-Chip for Real-Time Applications, December 2006, pp. 189 –194. [13] 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. [14] P. Arató, Z. A. Mann, and A. Orbán, “Time-constrained scheduling of large pipelined datapaths,” Journal of Systems Architecture, vol. 51, no. 12, pp. 665–687, December 2005. [15] P. Arató, T. Visegrády, and I. Jankovits, High-level Synthesis of Pipelined Datapaths. John Wiley & Sons, 2001. [16] S. Deniziak, “Cost-efficient synthesis of multiprocessor heterogeneous systems,” Control and Cybernetics, vol. 33, no. 2, pp. 341–355, 2004. [17] A. A. Jerraya and W. Wolf, Multiprocessor Systems-on Chip, ser. Systems on Silicon. Morgan Kaufmann Publishers (Elsevier), 2005. [18] N. Park and A. Parker, “Shewa: A program for synthesis of pipelines,” in Proceedings of 23. Des. Automation Conference, 1986, pp. 454–460. [19] J. C. Huang, “State constraints and pathwise decomposition of programs,” IEEE Transactions on Software Engineering, vol. 16, no. 8, pp. 880–896, 1990. |