Abstract-Alla tidigare Kernighan-Lin-baserade (KL-baserade) kretspartitionering algoritmer använder låsmekanismen, som tvingar varje cell att flytta exakt en gång per pass. I detta dokument föreslår vi två nya metoder för multiway-kretspartitionering för att övervinna denna begränsning. Våra metoder tillåter varje cell att röra sig mer än en gång. Vårt första tillvägagångssätt använder fortfarande låsmekanismen men på ett avslappnat sätt. Den introducerar faskonceptet så att varje pass kan omfatta mer än en fas, och en fas kan omfatta som mest ett drag av varje cell. Vårt andra tillvägagångssätt använder inte låsmekanismen alls. Det introducerar rörlighetskonceptet så att varje cell kan röra sig så fritt som dess rörlighet tillåter. Varje metod leder till KL-baserade generiska algoritmer vars parametrar kan ställas in för att erhålla algoritmer med olika prestandaegenskaper. Vi genererade tre versioner av varje generisk algoritm och utvärderade dem på en undergrupp av gemensamma referenskretsar i jämförelse med Sanchis algoritm (FMS) och den simulerade glödgningsalgoritmen (SA). Experimentella resultat visar att våra algoritmer är effektiva, de överträffar FMS betydligt och de presterar i jämförelse med SA. Våra algoritmer presterar relativt bättre eftersom antalet delar i partitionen ökar liksom densiteten på kretsen minskar. Detta dokument ger också riktlinjer för bra parameterinställningar för de generiska algoritmerna. Index Terms-Iterativ förbättring, Kernighan-Linbaserade algoritmer, flytta-baserad partitionering, multiway kretspartitionering, avslappnad låsning, mycket storskalig integration (VLSI).
Nyligen, Dasdan och Aykanat REF (DA) utvecklat två multiway partitionering algoritmer med hjälp av en avslappnad låsmekanism.
Two Novel Multiway Circuit Partitioning Algorithms Using Relaxed Locking
{'venue': 'IEEE Trans. on CAD of Integrated Circuits and Systems', 'journal': 'IEEE Trans. on CAD of Integrated Circuits and Systems', 'mag_field_of_study': ['Computer Science']}