초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

BSG(Bounded Sliceline Grid)를 이용한 플로어플랜 기법은 매우 빠르고 효과적이나 모듈 사이에 빈 공간이 존재하여 필요 이상으로 면적을 넓게 차지하는데도 불구하고 그 점을 무시한채 배치 면적을 구하는 문제점이 있다. 본 논문에서는 BSG 구조를 이용한 플로어플랜 과정 중 빈 공간이 생기는 문제점을 해결하기 위해 모듈들을 좌측 또는 아래로 옮길 수 있는데 까지 옮기는 압축 기법을 추가하여 필요한 면적이 최소가 되도록 하였다. 실험 결과는 압축 기법을 사용하는 것이 사용하지 않을 때보다 최소 면적과 평균 면적 면에서 모두 개선되는 것을 보여 준다.

BSG(Bounded Sliceline Grid)를 이용한 플로어플랜 기법은 매우 빠르고 효과적이나 모듈 사이에 빈 공간이 존재하여 필요 이상으로 면적을 넓게 차지하는데도 불구하고 그 점을 무시한채 배치 면적을 구하는 문제점이 있다. 본 논문에서는 BSG 구조를 이용한 플로어플랜 과정 중 빈 공간이 생기는 문제점을 해결하기 위해 모듈들을 좌측 또는 아래로 옮길 수 있는데 까지 옮기는 압축 기법을 추가하여 필요한 면적이 최소가 되도록 하였다. 실험 결과는 압축 기법을 사용하는 것이 사용하지 않을 때보다 최소 면적과 평균 면적 면에서 모두 개선되는 것을 보여 준다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• BSG 구조의 또 다른 문제는 격자의 경계 간에 미리 설정된 상관관계 때문에 BSG 구조의 격자 내에 할당된 모듈들 사이에 불필요한 빈 공간이 있게 되는 문제점이 있다. 본 논문에서는 BSG 구조에서 이런 불필요한 빈 공간을 포함하지 않도록 SA 휴리스틱을 적용하는 과정에서 효과적인 압축 기법을 적용하여 배치 영역을 가능한 적게 하도록 한다. 이렇게 함으로써 더 좋은 해를 찾을 수 있게 하였다.
• 본 논문에서는 [4] 에서 제안한 BSG 구조를 이용한 플로어플랜의 단점 즉, 모듈 사이에 없앨 수 있는 빈 공간이 있음에도 불구하고 그것을 그대로 둔 채 면적을 계산하는 문제점을 개선한 기법을 제시하였다. 모듈을 아己H 로 또는 좌측으로 옮길 수 있을 만큼 옮기는 효과적인 Compact 기법을 이용하여 배치의 종 면적을 가능한 줄인 상태에서 플로어플랜의 면적을 계산하였다.

가설 설정

• 1. 모듈들의 y-좌표에 따라 오름차순으로 정렬한다. 동일한 y-좌표를 가지는 모듈들은 X-좌표에 따라 오름차순으로 정렬한다.
• 2. 정렬된 순서대로 모듈을 아래로 이동할 수 있는 만큼 이동한다.

제안 방법

• BSG 구조의 격자 상에서 임의로 모듈을 배치한 후 앞 절에서 설명한 알고리즘 Compacts 이용하여 그에 대응하는 면적을 구한다. 그 면적을 현재의 해로 둔다.
• 모듈의 위치를 바꿀 때 모듈의 방향을 90도 돌리는 것도 같이 고려하여 가능한 모든 변화 각각에 대해 Compact 알고리즘을 이용하여 면적을 구한다. 가능한 모든 변화를 다 고찰한 후 면적이 가장 작게 되는 변화에 대응하는 배치의 결과를 새로운 해로 둔다.
• 실험은 MCNC 회로에 대상으로 하였고, BSG 구조에서 알고리즘 Compact를 적용한 경우와 적용하지 않은 경우를 비교하였다. 각 회로에 대해 100번 씩 실험을 하였고, 초기 배치는 무작위로 구하였다. 표 1에서 두 가지 경우에 대해 가장 좋은 결과를, 표 2에선 평균 결과를 보였고.
• 점이다. 격자 상에 할당된 모듈들을 '아래로' 또는 '좌즉으로' 이동을 반복하여 더 이상 모듈들을 옮길 수 없을 때 까지 옮겨 빈 공간을 없앤 후 모듈들을 둘러싸는 최소 면적을 구하고자 한다. 이처럼 빈 공간을 없애기 위해 모듈을 옮기는 과정을 “압축한다” 라고 표현한다.
• 문제점을 개선한 기법을 제시하였다. 모듈을 아己H 로 또는 좌측으로 옮길 수 있을 만큼 옮기는 효과적인 Compact 기법을 이용하여 배치의 종 면적을 가능한 줄인 상태에서 플로어플랜의 면적을 계산하였다.
• 본 논문에서 제안한 알고리즘은 Pentium IV 2G/Linux 상에서 C로 구현되었다. 실험은 MCNC 회로에 대상으로 하였고, BSG 구조에서 알고리즘 Compact를 적용한 경우와 적용하지 않은 경우를 비교하였다.
• C로 구현되었다. 실험은 MCNC 회로에 대상으로 하였고, BSG 구조에서 알고리즘 Compact를 적용한 경우와 적용하지 않은 경우를 비교하였다. 각 회로에 대해 100번 씩 실험을 하였고, 초기 배치는 무작위로 구하였다.

이론/모형

• 같다. 모듈의 위치를 바꿀 때 모듈의 방향을 90도 돌리는 것도 같이 고려하여 가능한 모든 변화 각각에 대해 Compact 알고리즘을 이용하여 면적을 구한다. 가능한 모든 변화를 다 고찰한 후 면적이 가장 작게 되는 변화에 대응하는 배치의 결과를 새로운 해로 둔다.

성능/효과

• 있다. Compact 기법을 사용함으로써 CPU 시간은 더 필요하지만 절대적인 시간 면에서 Compact 기법을 사용해도중분히 용납할 만하기 때문에 안정적으로 좋은 결과를 얻기 위해선 제시한 Compact 기법을 사용하는 것이 바람직해 보인다.
• 결과에서 보듯이 알고리즘 Compacts 적용한 경우에 최소면적은 동일한 결과를 보이거나 개선되는 것을 보여준다. 또한 평균 면적의 경우는 Compacts 적용한 경우가 항상 개선되는 것을 보여 준다.
• 실험결과에 의하면 최소면적과 평균면적 모두 제시한 기법을 사용하는 경우 개선되는 것을 볼 수 있다. Compact 기법을 사용함으로써 CPU 시간은 더 필요하지만 절대적인 시간 면에서 Compact 기법을 사용해도중분히 용납할 만하기 때문에 안정적으로 좋은 결과를 얻기 위해선 제시한 Compact 기법을 사용하는 것이 바람직해 보인다.

후속연구

• 또한 측정은 하지 않았지만 impact 기법을 사용하는 경우 배선 길이 면에서도 더 좋은 결과를 보일 것으로 기대된다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기