Browse

디자인 상황인식 고속 캐리 스킵 가산기 합성 알고리즘

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors
김기영
Advisor
김태환
Major
전기·컴퓨터공학부
Issue Date
2012-02
Publisher
서울대학교 대학원
Description
학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2012. 2. 김태환.
Abstract
논리 회로에서 가장 timing critical한 부분은 많은 경우 하나 이상의 산술 연산을 포함하고, 이 산술 연산에는 덧셈이 주로 연관된다. 캐리 스킵 가산기 (carry-skip adder)는 캐리를 그룹 (group)에 대해 건너 뛰게 (skip) 함으로써 캐리 전파 시간을 줄이는 가산기이다. 캐리 스킵 가산기는 캐리 룩어헤드 가산기 (carry look-ahead adder)와 비교할 만큼 속도가 빠르면서도 면적과 전력 소모는 비교적 작다는 장점 이 있다. 본 논문에서는 가산기를 포함한 전체 디지인 상황에서 최소 지연 시간 캐리 스킵 가산기를 합성하는 문제를 다룬다. 가산기의 입력 도착 시간 (arrival time)이 균등 (uniform)한 패턴이거나 정해진 패턴인 것으로 가정한 기존 연구 [1, 2]는 연구 결과를 고립된 단 하나의 가산기 또는 병렬 곱셈기 (parallel multiplier)의 최종 가 산기 (final adder)에만 적용 가능하다는 한계가 있었다. 그러나 본 논문이 제안하는 합성 알고리즘은 주어진 임의의 비트 수준 (bit-level) 도착 시간에 대해 타이밍을 최소화하는 캐리 스킵 가산기 구조를 생성한다. 본 논문은 캐리 스킵 가산기의 그룹 파티션 문제를 다이나믹 프로그래밍 문제로 공식화하고 효율적으로 문제를 해결하 였다.
The most timing critical part of logic design usually contains one or more arithmetic operations, in which addition is commonly involved. The carry-skip adder, which is designed to reduce the time needed to propagate the carry by skipping over groups of consecutive adder stages, is known to be comparable in speed to the carry lookahead technique while it uses less logic area and less power. In this paper, we address the problem of automatic and systematic synthesis of (true) timing minimal carryskip adder in the context of the whole design containing the adder. Precisely, unlike the previous works which invariably assume a uniform or a fixed pattern of input arrival times, thus limiting their application to the optimization of an isolated single addition or additions in specific design structures, e.g., final addition in a parallel multiplier, our synthesis algorithm allows to accept any arbitrary, but known in advance, bit-level arrival times of the addends and generates a structure of carryskip adder that leads to minimize the timing of the whole design. We formulate the carry group (or block) partitioning problem for minimal timing into a dynamic programming problem and solved it effectively.
Language
kor
URI
http://hdl.handle.net/10371/155536

http://dcollection.snu.ac.kr/jsp/common/DcLoOrgPer.jsp?sItemId=000000000756
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Electrical and Computer Engineering (전기·정보공학부)Theses (Master's Degree_전기·정보공학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse