회로를 구성하는 논리 소자가 평면상에서 일정한 간격으로 배치되고, 배치된 논리 소자 사이에 일정한 개수의 배선 트랙이 가로와 세로 방향으로 존재하며, 배선 트랙의 교차점 중에서 대각선 방향의 교차점을 포위하는 일정개의 스위치 소자와, 가로 세로 방향으로 각각 한 개의 스위치 소자로서 스위칭 포인트가 형성되어 있고, 배선 트랙과 논리 소자의 핀이 만나는 모든 위치에는 스위치 소자가 한 개씩 존재하는 베선 구조의 대칭형 FPGA 배선 구조에 있어서,

주어진 배선 요구를 받아들인 후 모든 연결 블록의 배선 제약 조건을 추출하는 제 1 과정과;

상기 모든 연결 블록의 베선 제약 조건 추출 후 동일한 블록에 속한 신호선들 사이에만 에지를 갖는 그래프를 형성하는 제 2 과정과;

에지을 갖는 그래프를 형성한 후 최소의 색상으로 그래프 채색을 수행하는 제 3 과정과;

채색이 이루어지면 색상에 해당하는 배선 트랙을 모든 신호선에 할당하는 제 4 과정을 포함하는 것을 특징으로 하는 대칭형 현장 가공형 반도체(FPGA)의 배선방법

제 1 항에 있어서, 상기 제 3 과정은

연결 블록에서 구한 모든 클릭중에서 신호선을 가장 많이 갖는 클릭의 신호선 수(W), 그래프가 갖는 노드(C[i])의 총 수(N)를 받아들이는 제 1 단계와;

상기 클릭의 신호만 있으면 채색될 수 있는 최대 클릭에 속하는 각 노드를 채색하는 제 2 단계와;

상기 클릭의 신호 수를 하나 증가시키는 임의의 수(i=W+1)를 설정하여 새로운 노드(C[i])를 받아들일 준비를 하는 제 3 단계와;

채색되지 않은 노드에서 사용할 수 있는 색상을 탐색하여 색상 목록을 작성하는 제 4 단계와;

사용할 수 있는 색상의 수가 가장 적은 노드를 선택하여 새로운 노드(C[i])에 저장하는 제 5 단계와;

상기 새로운 노드(C[i]) 색상 목록에서 가장 적은 값의 색상(t)을 선택하는 제 6 단계와;

선택한 색상이 상기 신호선을 가장 많이 갖는 클릭의 신호선 수(W) 이하인지를 판단하여 이하일 경우 새로운 노드를 가장 적은 값의 색상(t)으로 채색하고 색상 목록에서 상기 가장 적은 값의 색상(t)를 삭제하는 제 7 단계와;

상기 가장 적은 값의 색상(t) 삭제 후 상기 클릭의 신호 수를 하나 증가시키는 임의의 수(i)를 하나 증가시킨 후 모든 노드가 채색되었는지 판단하는 제 8 단계와;

상기 판단 후 모든 노드가 채색되었으면 수행을 중지하고, 채색되지 않았으면 채색할 노드를 다음 노드를 선택하는 제 9 단계와;

상기 판단 후 가장 적은 값의 색상(t)이 신호선을 가장 많이 갖는 클릭의 신호선 수(W) 이상일 경우 상기 클릭의 신호 수를 하나 증가시키는 임의의 수(i)를 하나 줄인 후 역탐색이 도달하였는지 판단하는 제 10 단계와;

상기 판단 후 역탐색이 채색의 출발점인 상기 노드수와 신호선을 가장 많이 갖는 클릭의 신호선 수(W)가 같을 때까지 도달해도 채색을 할 수 없는 경우에는 W로서 배선에 사용할 수 있는 색상의 한도를 하나 증가시키는 제 11 단계와;

상기 판단 후 클릭의 신호 수를 하나 증가시키는 임의의 수(i)가 노드수와 신호선을 가장 많이 갖는 클릭의 신호선 수(W)보다 클 경우 노드의 색상(s)을 삭제하고, 인접한 노드들의 색상 목록에 노드의 색상을 하나 증가시키는 제 12 단계로 이루어지는 것을 특징으로 하는 대칭형 현장 가공형 반도체(FPGA)의 배선방법