본 논문에서는 IC(Integrated Circuits) 칩들간의 배선 위상(topology)이 정해진 재구성 가능한(reconfigurable) FPGA(Field Programmable Gate Array) 기반 보드로의 회로 분할 문제로써 새로운 quadratic boolean programming 수식(formulation)을 제안한다. 본 수식의 목적은 회로 분할 시 사용하는 핀수와 네트들의 배선 길이의 합을 최소화하는 것이며 기존의 분할 방법에서 고려하는 제약조건 외에 서로 인접하지 않은 IC 칩들을 연결하기 위하여 다른 IC 칩을 통과(pass through)하는 네트들에 의해 사용되는 핀수도 고려한다. 또한 본 논문에서는 제안한 분할 문제를 효율적으로 해결하기 위하여 모듈 할당 방법으로 구성되어 있는 휴리스틱(heuristic) 분할 방법을 제안한다. 입력된 회로에 대하여 다른 분할 방법과 비교하여 실험한 결과 분할 문제의 주어진 제한들을 모두 만족하였다. 대부분의 배선된 회로에 대하여 핀 사용률이 적게 나타났으며 네트들의 사용한 배선 길이의 합은 최대 34.7% 적게 나타났다.
We propose a new formulation by quadratic boolean programming to partition circuits for FPGA based reconfigurable circuit boards, in which the routing topology among IC chips are predetermined. The formulation is to minimize the sum of the wire length by considering the nets passing through IC chips for the interconnections between chips which are not adjacent, in addition to the constraints considered by the previous partition methods. We also describe a heuristic method, which consist of module assignment method to efficiently solve the problem. Experimental results show that our method generates the partitions in which the given constraints are all satisfied for all the benchmark circuits tested. The pin utilization are reduced for the most of the circuits and the total wire length of the routed nets are improved up to 34.7% compared to the previous method.
