Das Partitionierungsproblem ist an sich sehr schwer zugänglich (NP-Hart), da es sehr viele Möglichkeiten der Zuordnung der Knoten zu den Partitionen gibt. Allerdings können wir es heuristisch effizient lösen. Dazu betrachten wir ein einfacheres Problem der balanzierten Bi-Partitionierung eines Graphen. Balanziert meint, das die Partitionen des Ergebnisses annähernd gleich groß sein müssen. Die Kanten seien einfach und haben alle das Gewicht 1. Die zusätzlichen Bedingungen wie kritischer Pfad in einer Partition und Sodnerbehandlung von Ein- und Ausgängen sowie Netze (Kanten) mit mehr als 2 angeschlossenen Knoten können dem Problem hinzugefügt werden, ohne das Problem stark zu beeinflussen. Des weiteren können wir auch mehr als 2 Partitionen für mehr als 2 FPGAs durch rekursive BiPartitionierung erreichen.
Für die balanzierte Bi-Partitionierung gibt es eine guten Algorithmus, den Fiduccia Matheyses Algorithmus, der von einer zufälligen Startpartitionierung ausgeht und dann in mehreren Durchläufen jeweils eine Liste von gains bestimmt, die aussagt, was es bringen würde, einen Knoten in die andere Partition zu verschieben. Diese Liste wird absteigend abgearbeitet und jeweils immer wieder upgedated, so dass jeder Knoten einmal verschoben wurde. Letztlich merkt sich der Algorithmus dann die beste Lösung jedes der ca. 10 Durchläufe und gibt diese zurück.
Es handelt sich um einen heuristischen Algorithmus mit keiner Garantie auf ein Optimum. Diese Eigenschaft ist für unser Problem akzeptabel denn letzlich müssen die Partitionen in die FPGAs passen und es müssen nicht zu viele Kanten für die IOs beschnitten werden. Wenn es ein paar mehr als das Optimum sind stört das nicht weiter.
Der Fiduccia-Mattheyses-Algorithmus hat eine nahezu lineare Laufzeit in der Kantenzahl des Graphen. Was deutlich besser ist als der Vorgänger, der Kerninghan-Lin-Algorithmus, der eine Laufzeit von O(n^2 * log(n)) für n Knoten aufweist. Moderne Partitionierungsalgorithmen arbeiten teilweise konstruktiv durch Lösen eines Eigenwert Problems auf eine modifizierten Adjazenzmatrix.