고속 회로를 위한 비트 단위의 연산 최적화

엄준형(Junhyung Um),김영태(Youngtae Kim),김태환(Taewhan Kim),여준기(Chungi Lyuh),홍성백(Sungpack Hong) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1A

고속 회로 합성에 있어서, Wallace 트리 스타일은 연산을 위한 가장 효율적인 수행 방식의 하나로 인식되어 졌다. 그러나, 이러한 방법은 빠른 곱셈기의 수행이나 여러가지 연산수행에 있어, 입력 시그널을 고려하지 않은 일반적인 구조로 수행되어졌다. 본 논문은 연산기에 있어서 이러한 제한점을 극복하는 문제를 다룬다. 우리는 캐리-세이브 방법을 덧셈, 뺄셈, 곱셈이 혼합되어 있는 일반적인 연산 회로에 적용한다. 그 결과 효율적인 회로를 생성하며, 시그널들의 임의의 도달시간에 대해 회로의 도달시간을 최적화 한다. 또한, 우리는 최적 지연시간의 캐리-세이브 가산 회로를 생성하는 효율적인 알고리즘을 제안하였다. 우리는 이러한 최적화 방법을 여러 고속 디지털 필터에 적용시켜 보았고 이는 기존의 비트 단위가 아닌 캐리-세이브 수행방법보다 5%에서 30%사이의 수행시간 향상을 가져왔다.

저전력 회로를 위한 비트 단위의 연산 최적화

엄준형(Junhyung Um),김태환(Taewhan Kim) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

고속 회로 합성에 있어서, Wallace 트리 스타일은 연산을 위한 가장 효율적인 수행 방식의 하나로 인식 되어졌다. 그러나, 이러한 방법을 빠른 곱셈기의 수행이나 여러가지 연산수행에 있어, 입력 시그널을 고려하지 않은 일반적인 구조로 수행되어졌다. 본 논문은 연산기에 있어서 이러한 제한점을 극복하는 문제를 다룬다. 우리는 캐리-세이브 방법을 덧셈, 뺄셈, 곱셈이 혼합되어 있는 일반적인 연산 회로에 적용한다. 그 결과 효율적인 회로를 생성하며, 시그널들의 임의의 시그널 스위칭 변화에 대해 회로의 전력 소모를 최적화 한다. 우리는 이러한 최적화 방법을 여러 디지털 필터에 적용시켜 보았고 이는 기존의 비트 단위가 아닌 캐리-세이브 수행방법보다 상당한 양의 전력 소모의 향상을 보였다.

최종 배선을 고려한 연산 회로 합성

엄준형(Junhyung Um),김태환(Taewhan Kim) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

현대의 Deep-Submicron Technology(DSM)에서 배선은 논리 구성요소들보다 더욱 중요한 위치를 차지하게 되었다. 최근에, [2]는 연산 회로를 합성하기 위해 비트 단위의 최적 지연시간의 partial product reduction tree(PPRT)를 생성하는 방법을 제시하였고, 이는 현재의 최적 지연시간을 갖는 회로를 능가한다. 그러나, [2]를 포함하는 기존의 합성방법에서는, 합성의 복잡함이나, 배선에서 발생하는 여러가지 예상치 못하는 문제등으로 인하여 최종 배선을 고려하지 못하는 회로를 생성하며, 이는 길고 복잡하며, 특정한 부분에 밀집 되어 있는 배선을 형성하는 결과를 낳게 된다. 이러한 제한점을 극복하기 위하여, 우리는 carry-save-adder(CSA)를 이용한 새로운 모듈 합성 알고리즘을 제시한다. 이는 단지 상위 단계에서의 회로의 지연시간만을 고려한 알고리즘이 아니라, 이후의 배선을 고려하여 최종 배선에서 규칙적인 배선 토폴로지를 생성한다.

WFA를 이용한 이미지 압축 알고리즘에 대한 분석

엄준형(Junhyung Um),김태환(Taewhan Kim) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

본 논문에서 우리는 grey scale 영상을 weighted finite automata(WFA)로써 기술하는 두개의 알고리즘[2, 4]을 분석하였다. 또한, 원영상과 WFA를 이용하여 압축된 영상간의 error를 분석하고 그 결과를 제시하였다. 구체적으로, 영상복원 tolerance δ를 이용하여 찾아진 automaton에 의해 복원된 영상과 원영상의l²-norm의 차이가 δ보다 작거나 같음을 증명하였다.

연산회로 최적화를 위한 배선의 재배열

엄준형(Junhyung Um),김태환(Taewhan Kim) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1A

현대의 Deep-Submicron Technology(DSM)에선 배선에 관련된 문제, 예를 들어 crosstalk이나 노이즈 등이 큰 문제가 된다. 그리하여, 배선은 논리 구성요소들보다 더욱 중요한 위치를 차지하게 되었다. 우리는 이러한 배선을 고려하여 연산식을 최적화 하기 위해 carry-save-adder(CSA)를 이용한 모듈 합성 알고리즘을 제시한다. 즉, 상위 단계에서 생성된 규칙적인 배선 토폴로지를 유지하며 CSA간의 배선을 좀더 향상시키는 최적의 알고리즘을 제안한다. 우리는 우리의 이러한 방법으로 생성된 지연시간이 [l]에 가깝거나 거의 근접하는 것을 많은 testcase에서 보이며(배선을 포함하지 않은 상태에서), 그리고 그와 동시에 최종 배선의 길이가 짧고 규칙적인 구조를 갖는것을 보인다.

캐리-세이브 가산기를 이용한 연산 최적화 알고리즘

엄준형(Junhyung Um),김태환(Taewhan Kim) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.12

캐리-세이브 가산기 (CSA)는 회로 설계 과정에서 빠른 연산 수행을 위해 가장 널리 이용되는 연산기 중의 하나이다. 그러나, 현재까지 산업체에서 CSA를 이용한 설계는 설계자의 경험에 따른 수작업에 의존하고 있고 그 결과 최적의 회로를 만들기 위해 매우 많은 시간과 노력이 소비되고 있다. 이에 따라 최근 CSA를 기초로 하는 회로 합성 자동화 기법에 대한 연구의 필요성이 대두되고 있는 상황에서, 본 논문은 연산 속도를 최적화하는 효율적인 CSA 할당 알고리즘을 제안한다. 우리는 CSA 할당 문제를 2단계로 접근한다. (1) 연산식의 멀티 비트 입력들만을 고려하여 최소 수행 속도 (optimal-delay)의 CSA 트리를 할당한다; (2) (1)에서 구한 CSA 트리의 수행 속도 증가가 최소화 (minimal increase of delay) 되는 방향으로 CSA들의 캐리 입력 포트들에 나머지 싱글 비트 입력들을 배정한다. 실제 실험에서 우리의 제안된 알고리즘을 적용하여 연산식들의 회로 속도를 회로 면적의 증가 없이 상당한 수준까지 줄일 수 있었다. Carry-save-adder (CSA) is one of the most widely used implementations for fast arithmetics in industry However, optimizing arithmetic circuits using CSAs is mostly carried out by the designer manually based On his/her design experience, which is a very time-consuming and error-prone task To overcome this limitation, in this paper we propose an effective synthesis algorithm for solving the problem of finding an allocation of CSAs with a minimal timing for an arithmetic expression Specifically, we propose a two step approach (1) allocating a delay-optimal CSA tree for the multi-bit inputs of the arithmetic expression and (2) determining the assignment of the single-bit inputs to carry inputs of the CSAs which leads to a minimal increase of delay of the CSA tree obtained in step (1). For a number of arithmetic expressions, we found that our approach is very effective, reducing the timing of the circuits significantly without increasing the circuit area.

VLSI 설계에서 캐리-세이브 가산기를 이용한 설계 블록들 간의 최적화

김태환(Taewhan Kim),엄준형(Junhyung Um) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.5

캐리-세이브 가산기(CSA)는 실제 산업체에서 회로를 설계할 때 연산 수식의 계산을 빠르게 처리하기 위해 가장 많이 사용되는 구성 요소들 가운데 하나이다. [3]의 자료에 의하면, 실제 회로 설계에서 나오는 전형적인 연산식에 CSA를 이용했을 때 그렇지 않은 경우보다 최대 54%의 연산 처리 속도와 42%의 회로 면적 향상을 갖는다고 보고하고 있다. 그러나, 이는 그 연산식이 하나의 설계 블록(sub-design)에 포함되어 있다는 전제하에 도출된 것이었다. 회로 설계 규모와 복잡도가 큰 응용이 많아지는 상황에서 설계 블록 단위의 계층적(level of hierarchy) 설계는 필수적인 추세이므로, CSA를 이용한 회로 최적화를 실현하기 위해서는 설계 블록들 간에 걸쳐 있는 연산식에 대한 CSA 최적화 또한 매우 중요한 문제이다. 이를 해결하기 위해 이 논문에서는 auxiliary port라는 개념을 이용하여 설계 블록들간의 연산식에 대한 CSA 최적화 방법을 제안한다. 실제 실험에서 우리가 제안한 기법은 회로의 전체적인 영역에 걸쳐 CSA를 적용하는데 매우 효과적이었으며, 이 기법을 적용하지 않고 얻은 CSA 최적화 회로와 비교했을 때 회로에서의 연산식 계산 속도와 그 회로 면적이 상당히 향상되었음을 확인하였다. Carry-gave-adder (CSA) is the most often used type of component in implementing a fast computation of arithmetics in industry. It was reported in [3] that typical arithmetic computations found in industry designs were optimized using CSAs, producing designs with upto 54% faster timing and 42% smaller area. However, These results are based on the assumption that the arithmetic expression to be optimized must entirely be placed in one sub-design. As the demand of applications with high complexity of circuits increases, CSA optimization across boundary of design hierarchy is becoming more important. In this paper, we present an effective algorithm to solve the problem of CSA optimization across boundary of design hierarchy. Specifically, we present an optimization technique using a concept of auxiliary ports to solve the problem of CSA transformation for operation in different levels of design hierarchy. In fact, our experimentations indicate that our algorithm incorporating the concept was able to extensively utilize CSAs throughout the whole circuit, and as a result, it produces designs with significantly faster timing and less area.

캐리 - 세이브 가산기를 이용한 지연시간 최적화를 위한 연산기 합성

김태환(Taewhan Kim),엄준형(Junhyung Um),김영태(Youngtae kim),여준기(Chungi Lyuh),홍성백(Sungpack Hong) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1A

캐리-세이브 가산기(CSA)는 연산식의 빠른 수행을 위해 가장 일반적으로 쓰이는 연산기중에 하나이다. 일반적인 CSA 적용의 근본적인 한계로는, 연산 회로중에 바로 덧셈 연산으로 변환되는 부분만이 적용이 가능하다는 사실이다. 이러한 제한점을 극복하기 위하여, 우리는 간단하고도, 효율적인 CSA 변환 방법을 제시한다. 이들은 (1)멀티플렉서를 포함한 최적화, (2)회로 경계를 포함한 최적화, (3)곱셈기를 포함한 최적화이다. 이러한 방법을 포함하여, 우리는 전체적인 회로에서 CSA를 충분히 사용할 수 있는 새로운 지연시간 최적화를 목표로 하는 CSA 변환 방법을 만들어 내었다. 실험에서는 실제적인 여러 회로에 대해 제시된 방법이 효율적임을 보였다.

캐리 - 세이브 가산기에 기초한 연산 하드웨어 최적화를 위한 실질적 합성 기법

김태환(Taewhan Kim),엄준형(Junhyung Um) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.9·10

캐리-세이브 가산기 (CSA)는 빠른 수행과 작은 면적을 가지는 연산 하드웨어 구현에서 가장 효과적으로 사용되는 연산 셀들 중의 하나이다. 현재 CSA 적용기술의 근본적인 약점은, 그 적용이 덧셈식으로 직접 변환되는 부분에 해당하는 회로에만 가능하다는 것이다. 이러한 제한점을 극복하기 위하여, 우리는새로운 몇가지 CSA 변환 기법들을 제안한다. 구체적으로 멀티플렉서를 포함한 연산에서의 CSA 변환, 다수 회로를 포함한 연산에서의 CSA 변환, 곱셈연산을 내포한 연산에서의 CSA 변환을 제안한다. 또한, 이러한 기법들을 실제의 회로 합성에서 효과적으로 적용하는 통합 알고리즘을 제안한다. 우리는 다양한 실험을 통하여, 제시된 기법들에 기반한 우리의 알고리즘이 기존의 CSA 방법들과 비교하여 실제적인 회로 합성에서 매우 효율적임을 보인다. Carry-save-adder (CSA) is one of the most effective operation cells in implementing an arithmetic hardware with high performace and small circuit area. An fundamental drawback of the existing CSA applications is that the applications are limited to the local parts of arithmetic circuit that are directly converted to additions. To resolve the limitation, we propose a set of new CSA transformation techniques: optimizing arithmetics with multiplexors, optimizing arithmetics in multiple designs, and optimizing arithmetics with multiplications. We then design a new CSA transformation algorithm which integrates the proposed techniques, so that we are able to utilize CSAs more globally. An extensive experimentation for practical designs are provided to show the effectiveness of our proposed algorithm over the conventional CSA techniques.

저전력 회로 설계를 위한 분할 버스 - 인버트 코딩 기법

김태환(Taewhan kim),홍성백(SungPack Hong),엄준형(Junhyung Um),김영태(Youngtae kim),여준기(Chungi Lyuh) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1A

버스-인버트 코딩 기법은 버스에서의 연속된 데이터 전송시 발생하는 데이터 값의 천이를 줄이는 기법이다. 기존의 방식에서는 전에 버스 라인이나 그중의 한 일부분만 에 버스-인버트 코딩을 적용했었던 것과는 달리, 우리의 기법은 버스 라인들을 몇개의 묶음으로 분할하여, 각 묶음에 대해 독립적으로 버스-인 버트 코딩을 적용하여 데이터 값의 천이를 최소화 하려고 한다. 실험을 통해서 우리의 기법은 데이터 값의 천이를 전체적으로 10-50% 감소시킬 수 있음이 나타났다.