열번호, 상위 단말 네트 번호 및 하위 단말 네트 번호로 구성되는 채널의 네트 데이터들과 트랙수, 층갯수를 입력하는 제 1 단계와,

상기 입력된 네트 데이터로부터 수평 잠재 중첩표를 작성하는 제 2 단계와,

상기 입력된 네트 데이터로부터 네트 상하 관계표를 작성하는 제 3 단계와,

각 네트마다 트랙 번호 및 층번호를 선택하여 네트 할당표를 작성하여 이 네트 할당으로 채널 배선의 후보 해답을 발생시키는 제 4 단계와,

상기 수평 잠재 중첩표를 이용하여 상기 후보 해답의 수평 중첩을 탐지하는 제 5 단계와,

상기 네트 상하 관계표를 이용하여 상기 후보 해답의 수직 중첩을 탐지하는 제 6 단계와,

상기 제 5 단계 및 상기 제 6 단계의 탐지 결과 수평 중첩 또는 수직 중첩이 발생된 경우 상기 제 4 단계로 복귀하여 다른 네트에 대해 상기 제 5 단계 및 제 6 단계를 반복하는 제 7 단계와,

상기 후보 해답의 모든 네트에 대해 수평 중첩 또는 수직 중첩이 발생되지 않은 경우 후보 해답을 채널 배선의 해답으로 확정하는 제 8 단계를 포함하여 이루어진 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 수평 잠재 중첩표는 임의의 서로 다른 i네트와 j네트간에 하기의 {수평 중첩 조건 1} 및 {수평 중첩 조건 2}중 어느 하나의 관계가 성립하면 해당 칸을 1로 하고, 성립되지 않으면 해당 칸을 0으로 하여 작성되는 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 네트 상하 관계표는 임의의 서로 다른 i네트와 j네트에 대해 i네트가 j네트보다 같은 열에서 위쪽에 있을 경우 해당 칸의 값을 1로 하고, 그렇지 않을 경우 해당 칸의 값을 0으로 하여 작성되는 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 네트 할당표는 네트 번호, 트랙 번호 및 층번호로 이루어지며, 채널 배선의 해답을 표현하는 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 제 4 단계는 각 네트마다 1에서 트랙수까지의 정수중 난수를 사용하여 트랙 번호를 선택하고, 1부터 {층개수/2}까지의 정수중 난수를 사용하여 층번호를 선택하여 수평 세그먼트가 놓일 트랙과 층을 할당하므로써 네트 할당표를 작성하고, 이 네트 할당으로 후보 해답을 발생시키는 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 제 5 단계는 서로 다른 i네트와 j네트에 대해 i네트와 j네트가 동일하지 않으면서 동시에 수평 잠재 중첩표(i, j) = 1이고, 같은 트랙에 있으며, 같은 층에 있을 경우를 모두 만족하면 수평 중첩이 발생된 것으로 판단하여 새로운 후보 해답을 발생시키는 단계와,

상기 i네트와 j네트가 동일하거나, 수평 잠재 중첩표(i, j) = 1이고, 같은 트랙에 있으며, 같은 층에 있을 경우중 어느 하나라도 만족하지 못할 경우 수평 중첩이 발생되지 않은 것으로 판단하여 i네트 및 j네트를 증가시킨 후 상기 과정을 반복 실시하는 단계를 포함하여 이루어진 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

제 1 항에 있어서, 상기 제 6 단계는 임의의 서로 다른 i네트와 j네트에 대해 i네트와 j네트가 동일하지 않으면서 동시에 네트 상하 관계표(i, j) = 1이고, i네트의 트랙이 j네트의 트랙보다 같거나 아래쪽에 있으며, 같은 층에 있으면 수직 중첩이 발생된 것으로 판단하여 새로운 후보 해답을 발생시키는 단계와,

상기 i네트와 j네트가 동일하거나, 네트 상하 관계표(i, j) = 1이고, i네트의 트랙이 j네트의 트랙보다 같거나 아래쪽에 있으며, 같은 층에 있을 경우중 어느 하나라도 만족하지 못할 경우 수직 중첩이 발생되지 않은 것으로 판단하여 i네트 및 j네트를 증가시킨 후 상기 과정을 반복 실시하는 단계를 포함하여 이루어진 것을 특징으로 하는 수평 잠재 중첩표와 네트 상하 관계표를 이용한 채널 배선 방법

열번호, 상위 단말 네트 번호 및 하위 단말 네트 번호로 구성되는 채널의 네트 데이터들과 트랙수, 층갯수를 입력하기 위한 수단과,

상기 입력된 네트 데이터로부터 수평 잠재 중첩표를 작성하기 위한 수단과,

상기 입력된 네트 데이터로부터 네트 상하 관계표를 작성하기 위한 수단과,

각 네트마다 트랙 번호 및 층번호를 선택하여 네트 할당표를 작성하여 이 네트 할당으로 채널 배선의 후보 해답을 발생시키기 위한 수단과,

상기 수평 잠재 중첩표를 이용하여 상기 후보 해답의 수평 중첩을 탐지하기 위한 수단과,

상기 네트 상하 관계표를 이용하여 상기 후보 해답의 수직 중첩을 탐지하기 위한 수단과,

상기 후보 해답의 모든 네트에 대해 수평 중첩 또는 수직 중첩이 발생되지 않은 경우 후보 해답을 채널 배선의 해답으로 확정하기 위한 수단을 기능시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체