Under de senaste åren har flera heuristik föreslagits för hårdvaru / programvara partitionering problem. En av de mest lovande riktningarna är anpassningen av Kernighan-Lin algoritmen. Den Kernighan-Lin heuristiska utvecklades ursprungligen för kretspartitionering, men den har anpassats till andra domäner också. Dessutom har många förbättringar föreslagits så att nu flera varianter av den ursprungliga algoritmen finns. Syftet med detta dokument är att systematiskt utvärdera möjligheterna att tillämpa Kernighan-Lin heuristic till hårdvara/programvara partitionering. Det undersöks i detalj vilka versioner av det heuristiska arbetet som är bra i detta sammanhang. Eftersom hårdvara/programvara partitionering också har flera formuleringar, diskuteras det också hur problemformuleringen påverkar tillämpligheten av denna heuristiska. Dessutom presenteras också möjligheter till effektiv implementering av algoritmen genom att använda lämpliga datastrukturer. Dessa undersökningar åtföljs av ett stort antal empiriska testresultat.
I REF utvärderades möjligheterna att tillämpa Kernighan-Lin-algoritmen på HS P-problemet.
Evaluating the Kernighan-Lin Heuristic for Hardware/Software Partitioning
{'venue': 'Int. J. Appl. Math. Comput. Sci.', 'journal': 'Int. J. Appl. Math. Comput. Sci.', 'mag_field_of_study': ['Computer Science']}