Loading...
Please wait, while we are loading the content...
Extending the Kernighan/Lin Heuristic for Hardware and . . . (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Vahid, Frank Le, Thuy Dm |
| Abstract | The Kernighan/Lin graph partitioning heuristic, also known as min-cut or group migration, has been extended over several decades very successfully for circuit partitioning. Those extensions customized the heuristic and its associated data structure to rapidly compute the minimum-cut metric central to circuit partitioning; as such, those extensions are not directly applicable to other problems. In this paper, we extend the heuristic for functional partitioning, which in turn can solve the much investigated codesign problem of partitioning a system's coarsegrained functions among hardware and software components. The key 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 resulting quality. Another extension uses a new criteria for terminating the heuristic, eliminating time-consuming and unnecessary fine-tuning of a partition. Our experiments demonstrate extremely fast execution times (just a few seconds) with results matched only by the slower simulated annealing heuristic, meaning that the extended Kernighan/Lin heuristic will likely prove hard to beat for hardware and software functional partitioning. |
| File Format | |
| Volume Number | 2 |
| Journal | JOURNAL OF DESIGN AUTOMATION OF EMBEDDED SYSTEMS, KLUWER |
| Language | English |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Kernighan Lin Heuristic Data Structure Simulated Annealing Key Extension Kernighan Lin Graph Fast Execution Time Codesign Problem Software Partitioning Unnecessary Fine-tuning Software Component Several Decade Software Functional Partitioning New Criterion Near-linear Time-complexity Functional Partitioning Communication Metric Extended Kernighan Lin Heuristic Circuit Partitioning Group Migration |
| Content Type | Text |
| Resource Type | Article |
