제약 조건 그래프(레이아웃)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Constraint graph" 레이아웃 – 뉴스 · 신문 · 책 · 학자 · JSTOR(2011년 4월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

집적회로 배치 설계의 일부 작업에서는 겹치지 않는 물체의 평면 배치를 최적화할 필요가 있다.일반적으로 이 문제는 매우 어려우며, 컴퓨터 알고리즘으로 이를 다루기 위해 허용 가능한 배치와 배치 변경에 허용되는 작동에 대해 특정한 가정을 한다.구속조건 그래프는 평면에 배치된 객체의 상대적 이동 제한을 포착한다.이러한 그래프는 공통 아이디어를 공유하면서도 특정 설계 작업 또는 그 모델에 따라 정의가 다르다.

플로어플래닝

평면도에서, 집적 회로의 평면 모형은 "경계"(예: "칩 경계", "세포 경계")라고 불리는 더 큰 직사각형 안에 "블록"이라고 불리는 동위원소 직사각형의 집합이다.

제약 조건 그래프의 가능한 정의는 다음과 같다.특정 평면도에 대한 제약 조건 그래프는 꼭지점이 평면 블록 집합이고 b1이 완전히 b2의 왼쪽에 있고 b1이 완전히 b2보다 아래인 경우 b1에서 b2까지의 가장자리(수평 구속조건이라고 함)가 있으면 b1에서 b2까지의 가장자리(수평 구속조건이라고 함)가 있는 방향 그래프다.

수평 구속조건만 고려되면 수평 구속조건 그래프를 얻는다.수직 구속조건만 고려한다면 수직 구속조건 그래프를 얻는다.

이 정의에서 제약 조건 그래프는 최대 $O{\displaystyle ({}^{}}$ $){\displaystyle O(n^{2})$ 엣지를$$ 가질 수 있으며 여기서 n은 블럭 수입니다.따라서 다른, 밀도가 낮은 제약 조건 그래프를 고려한다.수평 가시성 그래프는 두 블록을 연결하고 다른 블록과 교차하지 않는 수평선 세그먼트가 있는 경우에만 두 블록 사이의 수평 구속조건이 존재하는 수평 구속조건 그래프다.한 블록은 다른 블록을 수평으로 이동시킬 수 있는 잠재적 '즉시 장애물'인 셈이다.수직 가시성 그래프는 유사한 방식으로 정의된다.

채널 라우팅

채널 라우팅 예제

채널 라우팅은 사각형의 두 반대편에 고정된 단자("채널")가 있는 그물 N 집합의 라우팅의 문제다.이 맥락에서 수평 구속조건 그래프는 정점이 N인 비방향 그래프로, 라우팅의 수평 세그먼트가 중첩되어야 하는 경우에만 두 개의 그물이 에지로 연결된다.주어진 예에서, 오직 그물 5와 6만이 그들 사이에 수평적 제약조건을 가지고 있지 않다.수직 구속조건 그래프는 정점이 N인 방향 그래프로, 동일한 수직선에 서로 다른 그물에서 두 개의 핀이 있고 가장자리가 채널 상단 가장자리의 핀으로 그물에서 방향을 잡은 경우에만 엣지로 연결된다.이 방향은 이 네트가 두 번째 네트의 수평 트랙 위의 수평 트랙에 배선되어야 함을 의미한다.주어진 예에서, 오직 그물 1과 3만이 수직적 제약을 가지고 있다.^[1]

참조