Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning

Abdelzaher T.F. and Shin K.G. (2000): Period-based load partitioning and assignment for large real-time applications. — IEEE Trans. Comput., Vol. 49, No. 1, pp. 81-87.10.1109/12.822566Search in Google Scholar

Alpert C.J. and Kahng A.B. (1995): Recent developments in netlist partitioning: A survey.—VLSI J., Vol. 19, No. 1-2, pp. 1-81.Search in Google Scholar

Arató P., Juhász S., Mann Z.Á., Orbán A. and Papp D. (2003a): Hardware/software partitioning in embedded system design. — Proc. IEEE Int. Symp. Intelligent Signal Processing, Budapest, Hungary, pp. 197-202.Search in Google Scholar

Arató P., Mann Z.Á. and Orbán A. (2003b): Hardware-software co-design for Kohonen's self-organizing map. — Proc. IEEE 7th Int. Conf. Intelligent Engineering Systems, Luxor, Egypt, pp. 173-178.Search in Google Scholar

Arató P., Mann Z.Á. and Orbán A. (2005a): Algorithmic aspects of hardware/software partitioning. — ACM Trans. Design Autom. Electron. Syst., Vol. 10, No. 1, pp. 136-156.10.1145/1044111.1044119Search in Google Scholar

Arató P., Mann Z.Á. and Orbán A. (2005b): Time-constrained scheduling of large pipelined datapaths. — J. Syst. Arch. Vol. 51, No. 12, pp. 665-687.10.1016/j.sysarc.2005.02.001Search in Google Scholar

Arató P., Mann Z.Á. and Orbán A. (2007): Finding optimal hardware/software partitions. — Formal Meth. Syst. Design, (submitted).Search in Google Scholar

Barros E., Rosenstiel W. and Xiong X. (1993): Hardware/software partitioning with UNITY. — Proc. 2nd Int. Workshop Hardware-Software Codesign, Cambridge, USA.Search in Google Scholar

Binh N.N., Imai M., Shiomi A. and Hikichi N. (1996): A hardware/software partitioning algorithm for designing pipelined ASIPs with least gate counts. — Proc. 33rd Design Automation Conference, Las Vegas, USA, pp. 527-532.10.1145/240518.240618Search in Google Scholar

Chatha K.S. and Vemuri R. (2001): MAGELLAN: Multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs. — Proc. 9-th Int. Symp. Hardware/Software Codesign, Copenhagen, Denmark, pp. 42-47.10.1145/371636.371671Search in Google Scholar

Cormen Th.H., Leiserson Ch.E., Rivest R.L. and Stein C. (2001): Introduction to Algorithms, 2nd Ed. — Cambridge: MIT Press.Search in Google Scholar

Dasdan A. and Aykanat C. (1997): Two novel multiway circuit partitioning algorithms using relaxed locking. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 16, No. 2, pp. 169-177.10.1109/43.573831Search in Google Scholar

de Berg M., Schwarzkopf O., van Kreveld M. and Overmars M. (2000): Computational Geometry: Algorithms and Applications, 2nd Ed. — Berlin: Springer.10.1007/978-3-662-04245-8Search in Google Scholar

Dick R.P. and Jha N.K. (1998): MOGAC: A multiobjective genetic algorithm for hardware-software co-synthesis of hierarchical heterogeneous distributed embedded systems. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 17, No. 10, pp. 920-935.10.1109/43.728914Search in Google Scholar

Eles P., Peng Z., Kuchcinski K. and Doboli A. (1996): Hardware/software partitioning of VHDL system specifications. — Proc. European Design Automation Conference, Geneva, Switzerland, pp. 434-439.10.1109/EURDAC.1996.558240Search in Google Scholar

Eles P., Peng Z., Kuchcinski K. and Doboli A. (1997): System level hardware/software partitioning based on simulated annealing and tabu search. — Des. Autom. Emb. Syst., Vol. 2, No. 1, pp. 5-32.10.1023/A:1008857008151Search in Google Scholar

Ernst R., Henkel J. and Benner T. (1993): Hardware/software cosynthesis for microcontrollers. — IEEE Des. Test Comput., Vol. 10, No. 4, pp. 64-75.10.1109/54.245964Search in Google Scholar

Fiduccia C.M. and Mattheyses R.M. (1982): A linear-time heuristic for improving network partitions. — Proc. 19th Design Automation Conference, Piscataway, USA, pp. 175-181.Search in Google Scholar

Grode J., Knudsen P.V. and Madsen J. (1998): Hardware resource allocation for hardware/software partitioning in the LYCOS system. — Proc. Conf. Design Automation and Test in Europe, DATE, Paris, France, pp. 22-27.10.1109/DATE.1998.655832Search in Google Scholar

Gupta R.K. and de Micheli G. (1993): Hardware-software cosynthesis for digital systems. — IEEE Des. Test Comput., Vol. 10, No. 3, pp. 29-41.10.1109/54.232470Search in Google Scholar

Guthaus M.R., Ringenberg J.S., Ernst D., Austin T.M., Mudge T. and Brown R.B. (1997): MiBench: A free, commercially representative embedded benchmark suite. — Proc. IEEE 4th Ann. Workshop Workload Characterization, Austin, USA, pp. 3-14.Search in Google Scholar

Hagen L., Huang J.H. and Kahng A.B. (1997): On implementation choices for iterative improvement partitioning algorithms. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 16, No. 10, pp. 1199-1205.10.1109/43.662682Search in Google Scholar

Henkel J. and Ernst R. (2001): An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. — IEEE Trans. VLSI Syst., Vol. 9, No. 2, pp. 273-289.10.1109/92.924041Search in Google Scholar

Hoffmann A.G. (1994): The dynamic locking heuristic - a new graph partitioning algorithm. — Proc. IEEE Int. Symp. Circuits and Systems, London, UK, pp. 173-176.10.1109/ISCAS.1994.408783Search in Google Scholar

Kalavade A. (1995): System-level codesign of mixed hardware-software systems.—Ph.D. thesis, University of California, Berkeley, CA, USA.Search in Google Scholar

Kalavade A. and Lee E.A. (1997): The extended partitioning problem: hardware/software mapping, scheduling and implementation-bin selection. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 125-164.10.1023/A:1008872518365Search in Google Scholar

Kalavade A. and Subrahmanyam P.A. (1998): Hardware/software partitioning for multifunction systems. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 17, No. 9, pp. 819-837.10.1109/43.720318Search in Google Scholar

Kernighan B.W. and Lin S. (1970): An efficient heuristic procedure for partitioning graphs. — Bell Syst. Techn. J., Vol. 49, No. 2, pp. 291-307.10.1002/j.1538-7305.1970.tb01770.xSearch in Google Scholar

Krishnamurthy B. (1984): An improved min-cut algorithm for partitioning VLSI networks. — IEEE Trans. Comput., Vol. 33, No. 5, pp. 438-446.10.1109/TC.1984.1676460Search in Google Scholar

Lopez-Vallejo M., Grajal J. and Lopez J.C. (2000): Constraint-driven system partitioning. — Proc. Design, Automation and Test in Europe Conference and Exhibition, Paris, France, pp. 411-416.10.1145/343647.343811Search in Google Scholar

Lopez-Vallejo M. and Lopez J.C. (1998): A knowledge based system for hardware-software partitioning. — Proc. Design Automation and Test in Europe, DATE, Paris, France, pp. 914-915.10.1109/DATE.1998.655967Search in Google Scholar

Lopez-Vallejo M. and Lopez J.C. (2003): On the hardware-software partitioning problem: system modeling and partitioning techniques. — ACM Trans. Des. Autom. Electron. Syst., Vol. 8, No. 3, pp. 269-297.10.1145/785411.785412Search in Google Scholar

Madsen J., Grode J., Knudsen P.V., Petersen M.E. and Haxthausen A. (1997): LYCOS: The Lyngby co-synthesis system. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 195-236.10.1023/A:1008884219274Search in Google Scholar

Mann Z.Á. and Orbán A. (2003): Optimization problems in system-level synthesis. — Proc. 3rd Hungarian-Japanese Symp. Discrete Mathematics and Its Applications, Tokyo, Japan, pp. 222-231.Search in Google Scholar

Mei B., Schaumont P. and Vernalde S. (2000): A hardware/software partitioning and scheduling algorithm for dynamically reconfigurable embedded systems. — Proc. 11-th ProRISC Workshop Circuits, Systems and Signal Processing, Veldhoven, Netherlands, pp. 405-411.Search in Google Scholar

Niemann R. (1998): Hardware/Software Co-Design for Data Flow Dominated Embedded Systems. — Norwell: Kluwer.10.1007/978-1-4757-2803-3Search in Google Scholar

Niemann R. and Marwedel P. (1997): An algorithm for hardware/software partitioning using mixed integer linear programming. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 165-193.10.1023/A:1008832202436Search in Google Scholar

O'Nils M., Jantsch A., Hemani A. and Tenhunen H. (1995): Interactive hardware-software partitioning and memory allocation based on data transfer profiling. — Proc. Int. Conf. Recent Advances in Mechatronics, Istanbul, Turkey, pp. 447-452.Search in Google Scholar

Qin S. and He J. (2000): An algebraic approach to hardware/software partitioning. — Tech. Rep., No. 206, The United Nations University, International Institute for Software Technology.Search in Google Scholar

Quan G., Hu X. and Greenwood G. (1999): Preference-driven hierarchical hardware/software partitioning. — Proc. IEEE/ACM Int. Conf. Computer Design, Austin, USA, pp. 652-657.Search in Google Scholar

Sanchis L.A. (1989): Multiple-way network partitioning. — IEEE Trans. Comp. Vol. 38, No. 1, pp. 62-81.10.1109/12.8730Search in Google Scholar

Srinivasan V., Radhakrishnan S. and Vemuri R. (1998): Hardware software partitioning with integrated hardware design space exploration. — Proc. Design Automation and Test in Europe, DATE, Paris, France, pp. 28-35.10.1109/DATE.1998.655833Search in Google Scholar

Stitt G., Lysecky R. and Vahid F. (2003): Dynamic hardware/software partitioning: A first approach. — Proc. IEEE/ACM 40th Design Automation Conference, Anaheim, USA, pp. 250-255.10.1145/775832.775896Search in Google Scholar

Vahid F. (1997): Modifying min-cut for hardware and software functional partitioning. — Proc. Int. Workshop Hardware-Software Codesign, Braunschweig, Germany, pp. 43-48.10.1109/HSC.1997.584577Search in Google Scholar

Vahid F. (2002): Partitioning sequential programs for CAD using a three-step approach. — ACM Trans. Des. Autom. Electron. Syst., Vol. 7, No. 3, pp. 413-429.10.1145/567270.567273Search in Google Scholar

Vahid F. and Gajski D. (1995): Clustering for improved system-level functional partitioning. — Proc. 8th Int. Symp. System Synthesis, Cannes, France, pp. 28-33.10.1109/ISSS.1995.520609Search in Google Scholar

Vahid F. and Le T.D. (1997): Extending the Kernighan/Linheuristic for hardware and software functional partitioning. — Des. Autom. Emb. Syst., Vol. 2, No. 2, pp. 237-261.10.1023/A:1008836303344Search in Google Scholar

Wolf W.H. (1997): An architectural co-synthesis algorithm for distributed embedded computing systems. — IEEE Trans. VLSI Syst., Vol. 5, No. 2, pp. 218-229.10.1109/92.585225Search in Google Scholar

Wolf W. (2003): A decade of hardware/software codesign. — IEEE Comp., Vol. 36, No. 4, pp. 38-43.10.1109/MC.2003.1193227Search in Google Scholar

Yeh C.W., Cheng C.-K. and Lin T.-T.Y. (1994): A general purpose, multiple-way partitioning algorithm. — IEEE Trans. Comput. Aided Des. Integ. Circ. Syst., Vol. 13, No. 12, pp. 1480-1487.Search in Google Scholar