초록

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

본 논문은 기존의 O-tree 표현법을 이용한 플로어플랜 알고리즘의 결점을 보완한 새로운 알고리즘을 제안한다. 기존의 방법에선 플로어플랜의 변형을 처리하는 과정에서 몇 가지 변형을 간과하기 때문에 좋은 해를 놓치는 경우가 발생한다. 본 논문에서는 기존의 방법을 수정하여 변형을 처리하는 과정에서 블록이 들어갈 수 있는 모든 위치를 고려하였다. 그 결과 MCNC 밴치마크 회로를 이용한 실험에서 총면적이 이전의 방법에 비해 평균 3% 개선되었다.

본 논문은 기존의 O-tree 표현법을 이용한 플로어플랜 알고리즘의 결점을 보완한 새로운 알고리즘을 제안한다. 기존의 방법에선 플로어플랜의 변형을 처리하는 과정에서 몇 가지 변형을 간과하기 때문에 좋은 해를 놓치는 경우가 발생한다. 본 논문에서는 기존의 방법을 수정하여 변형을 처리하는 과정에서 블록이 들어갈 수 있는 모든 위치를 고려하였다. 그 결과 MCNC 밴치마크 회로를 이용한 실험에서 총면적이 이전의 방법에 비해 평균 3% 개선되었다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

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

문제 정의

• 본 논문에서는。너「ee를 이용한 결정적 알고리즘[1]에서 탐색하지 못하는 해 공간을 찾아보는 보다 개선된 알고리즘을 소개한다.
• 본 논문에서는 2.4절에서 말한 바와 같이 삽입되려는 노드가 단말이 되지 않는 경우도 고려하는, 즉 모든 경우를 고려하여 삽입하는 방법을 제안한다. 기존의 방법에서는 O-t「ee의 T에 모든 원소사이에 새로운 노드의 '01'을 넣어보았다.
• 3의 과정을 반복 실행함으로써 배치를 수용할 만하게 만든다. 이 과정을 반복함으로써 이 과정 중에 생성된 배치 중 최소 면적을 가지는 배치를 발견하는 것이 결정적 알고리즘의 최종 목표이다.

가설 설정

• 정리 1: O-t「ee의 T에서 1번째 지점까지 '0'의 개수는 i 번째 지점까지 T'의 개수보다 반드시 크거나 같다. 증명: O-t「ee의 丁는「oot부터 시작하여「oot로 끝나는 노드들의 부모 자식 관계를 나타내는 정보이다.
• 정리 2: O-t「ee의 丁에서 임의의 노드 [에 대응하는 '0' 과 T'이 사이에 있는 O과 T'의 개수는 같다.

제안 방법

• 2.2절과 2.3절에서 O-t「ee를 배치하는 과정과 특정 배치에 대해 다시 O-t「ee로 만드는 과정을 살펴보았다. 이 과정을 반복함으로써 수용할 만한 배치를 만들 수 있다.
• MCNC 밴치마크 회로의 각각에 대해 100번의 랜덤한 초기 배치에 대해 기존의 방법과 본 논문에서 제안된 방법을 실험했다. 표1의 실험결과가 보여 주듯이 기존의 방법에 비해 본 논문에서 제안된 방법은 전체적으로 3%정도 개선되었다.
• O-t「ee 의 「oot 노드를 최초의 노드로 보고 DFS(Depth—First—Search)순서에 따라 방문을 하며 노드를 선택한다, 「oot노드를 기점으로 시작하여 다시 root노드로 돌아오기까지 DFS순서로 방문을 하는데 이 과정에서 노드들 사이의 관계를 조사하여 T에 저장한다. 다음 순서의 간선이 자식 노드를 가리킬 경우 '0'을 부모 노드를 가리킬 경우 ‘1, 을 저장한다.
• 기존의 방법에서는 O-t「ee의 T에 모든 원소사이에 새로운 노드의 '01'을 넣어보았다. 모든 경우에 대해 노드를 삽입시켜 보기 위해 새로운 노드의 '0'과 T'을 분리하여 넣는 방법을 소개한다.

성능/효과

• 표1의 실험결과가 보여 주듯이 기존의 방법에 비해 본 논문에서 제안된 방법은 전체적으로 3%정도 개선되었다. hp를 제외한 나머지 회로에 대해 최대면적, 최소면적, 평균면적은 본 논문에서 제안된 방법이 기존의 방법보다 좋은 결과를 보였다.
• 최적화 성능이 뛰어나다. 대부분의 데이터에서 본 논문에서 제안된 방법은 기존의 방법 보다 좋은 결과를 보여주고 있다. 특히 블록의 개수가 많은 회로의 경우 기존의 방법에서 많은 경우를 간과 하는데 비해 본 논문에서 제시한 방법은 그런 경우를 모두 고려하기 때문에 해의 질이 높아질 가능성이 커지는 장점이 있다.
• 본 논문에서 제안된 방법은 기존의 방법에 비해 회로 면적의 최적화 성능이 뛰어나다. 대부분의 데이터에서 본 논문에서 제안된 방법은 기존의 방법 보다 좋은 결과를 보여주고 있다.
• 실험했다. 표1의 실험결과가 보여 주듯이 기존의 방법에 비해 본 논문에서 제안된 방법은 전체적으로 3%정도 개선되었다. hp를 제외한 나머지 회로에 대해 최대면적, 최소면적, 평균면적은 본 논문에서 제안된 방법이 기존의 방법보다 좋은 결과를 보였다.

후속연구

• 본 논문에서 제안된 방법의 단점인 CPU 시간을 많이 사용하는 문제를 ENPA[2]에서 사용했던 기법을 응용할 수 있다면 연산시간을 줄일 수 있을 것으로 보인다.

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

이 논문을 인용한 문헌

더보기