네트워크 - 플로우 방법을 기반으로 한 통합적 데이타 - 경로 합성 알고리즘

김태환(Taewhan Kim) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.12

이 논문은 상위 단계 데이타-경로 합성에서 연산 스케쥴링과 자원 할당 및 배정을 동시에 고려한 통합적 접근 방법을 제시한다. 제안한 방법은 스케쥴링 되어있지 않은 데이타-플로우 그래프에 대해서 수행에 필요한 총 clock 스텝 수와 필요한 회로 면적을 동시에 최소화하는 데이타-경로 생성에 특징이 있다. 일반적으로, 연결선의 결정이 합성의 마지막 단계에서 이루어지는 기존의 방법과는 다르게, 우리의 접근 방법은 연산 스케쥴링과 연산의 연산 모듈 배정 그리고 변수의 레지스터 배정 작업을 동시에 수행하여 추가적인 연결선의 수를 매 clock 스텝마다 최적화(optimal) 시킨다. 본 논문은, 이 문제를 최소-비용의 최대-플로우 문제로 변형하여 minimum cost augmentation 방법으로 polynomial time안에 해결하는 알고리즘을 제안한다. We present an integrated approach to the problems of the scheduling, allocation (register and interconnections), and binding in high-level synthesis. Our algorithm synthesizes a data path from an unscheduled dataflow graph with an objective of minimizing both the number of control steps and total design area. Unlike most of the prior approaches in which interconnections are determined only in the final step of the synthesis process, in our approach, scheduling of operations, binding of operations to functional units, and binding of variables to registers are performed simultaneously so that interconnections are determined optimally for each clock step. The problem is formulated as a minimum cost maximum flow problem in a network which can be solved in polynomial time using the minimum cost augmentation method.

개선된 테스트 용이화를 위한 점진적 개선 방식의 데이타 경로 합성 알고리즘

김태환(Taewhan Kim),정기석(Ki-Seok Chung) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5·6

본 논문은 세 가지 중요한 설계 기준인 테스트 용이화, 설계 면적, 및 전체 수행 시간을 동시에 고려한 새로운 데이터 경로 합성 알고리즘을 제시한다. 우리는 테스트 용이화를 위한 선행 연구들에서 제시한 세 가지 기초적 척도들에 근거하여 새로운 테스트 용이화의 우수성에 대한 척도를 정의한다. 이 척도를 이용하여, 스케쥴링과 할당의 통합된 형태의, 단계식이며 점진적 개선을 통한, 합성 알고리즘을 제시한다. 벤치마크 설계와 다른 회로의 예를 통한 실험에서, 우리는 설계 면적과 수행 시간에 대해 매우 적은 추가 부담으로, 회로의 테스트 용이화가 향상됨을 보인다. This paper presents a new data path synthesis algorithm which takes into account simultaneously three important design criteria: testability, design area, and total execution time. We define a goodness measure on the testability of a circuit based on three rules of thumb introduced in prior work on synthesis for testability. We then develop a stepwise refinement synthesis algorithm which carries out the scheduling and allocation tasks in an integrated fashion. Experimental results for benchmark and other circuit examples show that we are able to enhance the testability of circuits with very little overheads on design area and execution time.

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

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

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

Pendent S-1708

김태환(Taewhan Kim) 한국디자인학회 2017 한국디자인학회 국제초대전도록 Vol.2017 No.12

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.

타이밍과 면적 제약 조건을 고려한 클럭게이팅 로직 추출과 배치

김태환(Taehwan Kim),김태환(Taewhan Kim) 대한전자공학회 2016 대한전자공학회 학술대회 Vol.2016 No.11

조건부 분기를 가진 데이타-흐름 그래프 스케쥴링 알고리즘

김태환(Taewhan Kim) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.1·2

이 논문에서는 중첩된 조건부 분기를 가진 데이타-흐름 그래프에 대한 효과적인 스케쥴링 알고리즘을 제안한다. 이러한 그래프의 스케쥴링은 조건부 자원 공유 문제를 추가적으로 고려해야 하기 때문에 상당히 복잡하게 된다. 이 논문은 이를 적절히 해결하기 위한 방법을 제시하고 있는데 그 핵심은 조건부 분기가 있는 데이타-흐름 그래프를 조건부 분기가 없는 동일한 기능의 그래프로 변형시키는데 있다. 이렇게 함으로서, 변형된 그래프에 설계자의 관심에 맞는 기존의 스케쥴링 알고리즘을 선택 적용하여 스케쥴을 얻을 수 있고, 이것에서부터 원래 그래프의 스케쥴을 생성 할 수 있다. 실험 결과로부터 우리는 이러한 접근 방식이 매우 효과적임을 입증한다. An effective scheduling algorithm for dataflow graphs with conditional branches is presented. Since such data-flow graphs entail the problem of conditional resource sharing additionally, the scheduling problem becomes more complicated. To resolve this problem, we propose a new algorithm whose main role is to transform a data-flow graph with conditional branches into a functionally equivalent one that has no conditional branches. A schedule is then obtained for the transformed one by using an existing scheduling algorithm, from which a schedule for the original data-flow graph is obtained. Experimental results show that the proposed approach is quite effective.

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

김태환(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),홍성백(Sung-Pack Hong) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.9

상위단계 합성에서 데이타 저장을 위한 메모리 할당 문제는 중요하게 다루어지는 영역의 하나이다. 이 논문에서는, 다중포트(multiport) 메모리 할당 문제에 대한 새로운 방법을 제안한다. 문제의 복잡도를 줄이기 위해, 기존의 연구들은 요약하면, 두 단계의 과정으로 이루어지고 있다. 첫 번째 단계에서는 변수들을 몇 개씩 묶어서 하나의 메모리를 형성한다. (즉, 메모리 최적화 문제를 푼다.) 두 번째 단계에서는, 메모리들과 기능모듈들 간의 연결선을 최적화시킨다. (즉, 연결선 최적화 문제를 푼다.) 이 경우 심각한 단점은 연결선의 비용을 최소화하는 데는 한계가 있다는 것이다. 다시 말해, 연결선의 비중이 점점 중요하게 되어지는 설계 추세에서 기존의 방법은 다중포트 메모리 사용을 통해 얻을 수 있는 연결선 최소화를 극대화하는데 한계가 있음을 뜻한다. 이를 극복하기 위해, 우리는 새로운 할당 방법을 제시한다. 구체적으로 먼저, 연결선 최소화를 해결하고, 그 다음에, 메모리 최적화를 시도한다. 또한, 제안한 알고리즘은 연결선 최소화 과정 동안 다음 단계에서 결정될 메모리 비용도 적절히 고려한다. 우리는 다양한 실험을 통해, 우리의 제안한 방법이 기존의 연구보다 상당히 효율적인 것임을 보인다. Memory allocation is one of the most important areas in high-level synthesis. In this paper, a new approach to the problem of allocation of multiport memories for data storage is presented. To reduce the complexity of the problem, previous approaches solve the problem in two steps; First, the variables are grouped to form memories (i.e., optimizing memories). Then, the interconnections between the memories and functional units are determined (i.e., optimizing connections). One serious limitation of the approaches is that there is no easy way to predict the result of the second step during the first step. The situation is becoming worse since the importance of interconnections is increasing today. To overcome the limitation, we propose a new approach. Specifically, we minimize the cost of interconnections first and then group the variables to form memories later. In addition, we take into account the results of memory allocation during the connection minimization step in a proper way. From experimentations using a set of benchmark designs, we show that the proposed approach outperforms the pervious ones in reducing both interconnections and memories.