Modifying Min-Cut for Hardware and Software Functional Partitioning

ABSTRACT

The Kernighan/Lin heuristic, also known as min-cut, has been extended very successfully for circuit partitioning over several decades. Those extensions customized the heuristic and its associated data structure to rapidly compute the minimum-cut metric required during circuit partitioning; thus, those extensions are not applicable to problems requiring other metrics. In this paper, we extend the heuristic for functional partitioning in a manner applicable to the codesign problem of hardware/software partitioning as well as to hardware/hardware partitioning. The extension customizes the heuristic and data structure to rapidly compute execution-time and communication metrics, crucial to hardware and software partitioning, and leads to near-linear time-complexity and excellent results. Our experiments demonstrate extremely fast execution times (just a few seconds) with results matched only by the much slower simulated annealing heuristic, meaning that the extended Kernighan/Lin heuristic will likely prove hard to beat for hardware and software functional partitioning.

REFERENCES

• 1: Peter M. Athanas , Harvey F. Silverman, Processor reconfiguration through instruction-set metamorphosis, Computer, v.26 n.3, p.11-18, March 1993 [doi>10.1109/2.204677]
• 2: Reiner W. Hartenstein , Juergen Becker , Rainer Kress, Two-level Partitioning of Image Processing Algorithms for the Parallel Map-oriented Machine, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.77, March 18-20, 1996
• 3: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 4: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 5: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 6: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• 7: A. Balboni , W. Fornaciari , D. Sciuto, Partitioning and Exploration Strategies in the TOSCA Co-Design Flow, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.62, March 18-20, 1996
• 8: Asawaree Kalavade , Edward A. Lee, A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 9: Petru Eles , Zebo Peng1 , Krzysztof Kuchcinski , Alexa Doboli, Hardware/Software Partitioning with Iterative Improvement Heuristics, Proceedings of the 9th international symposium on System synthesis, p.71, November 06-08, 1996
• 10: Peter Voigt Knudsen , Jan Madsen, PACE: A Dynamic Programming Algorithm for Hardware/Software Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.85, March 18-20, 1996
• 11: Vahid , Le , Hsu, A Comparison of Functional and Structural Partitioning, Proceedings of the 9th international symposium on System synthesis, p.121, November 06-08, 1996
• 12: [12] B. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," Bell System Technical Journal, February 1970.
• 13: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 14: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 15: F. Vahid , D. D. Gajski, SLIF: a specification-level intermediate format for system design, Proceedings of the 1995 European conference on Design and Test, p.185, March 06-09, 1995
• 16: Frank Vahid, Procedure exlining: a transformation for improved system and behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.84-89, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224506]
• 17: Jie Gong , D. D. Gajski , S. Narayan, Software estimation using a generic-processor model, Proceedings of the 1995 European conference on Design and Test, p.498, March 06-09, 1995
• 18: Frank Vahid , Daniel D. Gajski, Incremental hardware estimation during hardware/software functional partitioning, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.459-464, Sept. 1995 [doi>10.1109/92.407006]
• 19: Frank Vahid , Thuy DM Le, Towards a Model for Hardware and Software Functional Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.116, March 18-20, 1996
• 20: [20] B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI networks," IEEE Transactions on Computers , May 1984.
• 21: L. A. Sanchis, Multiple-Way Network Partitioning, IEEE Transactions on Computers, v.38 n.1, p.62-81, January 1989 [doi>10.1109/12.8730]

INDEX TERMS

Keywords:
Functional partitioning, Kernighan/Lin, min-cut