회로지연을 최소화하는 회로집단화 알고리즘 개발 = Circuit Clustering Algorithm Development for Delay Minimization

국문 초록 (Abstract)

본 논문에서는 다중칩을 구현하기 위한 회로 분할 문제를 다룬다. 본 논문에서는 회로지연을 감소시킬 수 있는 논리 게이트의 복제를 허용한다. 논리 게이트의 복제를 허용하는 회로 분할을 회로 집단화라고 한다. 본 논문에서는 일반적 지연 모델을 사용해서 영역 및 핀수 제한을 모두 만족하면서 회로지연을 최소화하는 회로 집단화 알고리즘을 제안한다. 이 알고리즘은 영역 제한 혹은 핀수 제한만 있을 때는 최적의 회로지연을 실현하지만, 영역 및 핀수 제한이 모두 주어질 때는 대부분의 경우에 최적의 회로 지연을 실현한다. 제안 알고리즘을 벤치마크회로들에 대해 시험하여 최적 혹은 거의 최적의 회로지연을 가짐을 확인했다.

다국어 초록 (Multilingual Abstract)

We consider the problem of circuit paritioning for multiple-chip implementation. We allow duplication of logic gates as it would reduce circuit delay. Circuit partitioning with duplication of logic gates is also called circuit clustering. In this paper, we present a circuit clustering algorithm that minimizes circuit delay subject to both area and pm constraints on each chip, using the general delay model. We develop a repeated network cut technique for finding a cluster that is bounded by both area and pin constraints. Our algorithm achieves optimal delay under either the area constraint only or the pm constraint only. Under both area and pin constraints, our algorithm achieves optimal delay m most cases. We tested our algorithm on a set of benchmark circuits and consistently obtained optimal or near-optimal delays.

목차 (Table of Contents)

• 목차
• 요약, Abstract = 405
• Ⅰ. 서론 = 406
• Ⅱ. 문제의 정형화 = 407
• Ⅲ. 최적의 집단화 알고리즘 = 408
• Ⅳ. C_(k)를 포함하는 적절한 C_(v) 찾기 = 410
• Ⅴ. 실험결과 = 412
• Ⅵ. 결론 = 412
• 참고문헌 = 414