시분할 FPGA 합성에서 마이크로 레지스터 개수에 대한 하한 추정 기법

엄성용(Seong-Yong Ohm) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.9·10

시분할 FPGA는 회로가 동작하는 중 회로의 기능을 재구성할 수 있는 동적 재구성 기능을 갖춘 FPGA 칩이다. 따라서 이러한 칩을 위한 회로 합성 기법에서는 주어진 논리 회로를 각각 다른 시간대에 수행할 여러 개의 부분회로로 분할한 후, 동일한 하드웨어 회로를 시간차를 두고 공유하도록 해야 한다. 기존의 연구에서는, 칩의 제한된 용량 문제를 해결하기 위해, 동일 시간대에 필요한 자원으로서 각 세부 함수를 수행하는 LUT(Look-Up Table)의 개수와 LUT의 출력 결과를 다른 시간대에 사용하기 위해 그 결과를 임시 저장하는데 필요한 마이크로 레지스터(micro register)의 개수를 최소화하는 데 중점을 두고 있다. 본 논문에서는 시분할 FPGA 합성용 도구 중의 하나로서 회로 구현에 필요한 메모리 원소, 즉 마이크로 레지스터의 개수에 대한 하한(lower bound)을 추정하는 기법에 대해 설명한다. 이 방법에서는 입력되는 논리 회로를 직접 합성하지 않고서도 그 회로가 필요로 하는 전체 마이크로 레지스터 개수에 대한 하한을 각각 추정함으로써 특정한 합성 기법에 관계없이 회로 구현에 필요한 최소한의 마이크로 레지스터의 개수에 대한 정보를 추출한다. 만일, 기존의 합성 결과가 본 연구에서 추정된 하한과 일치할 경우, 그 결과는 최적의 결과를 의미한다. 반면에, 하한과의 차이가 있는 경우에는 기존의 연구 결과에 비해 더 좋은 합성 결과가 존재하거나, 또는 본 연구에서 추정한 하한보다 더 좋은(큰, 정확한) 하한이 실제 존재함을 의미한다. 따라서 이러한 비교 분석을 통해, 기존 연구는 물론, 향후에 개발할 새로운 합성 방법의 결과가 최적인지, 또는 개선의 여지가 있는지를 판단하는 좋은 지표를 얻을 수 있다. 실험 결과, 추정된 하한은 기존 연구의 합성 결과와 다소 차이가 있었다. 이러한 차이는 우선, 기존의 합성 결과는 LUT 개수를 적절히 유지하는 가운데 마이크로 레지스터를 최소화한 결과인 반면, 본 하한 추정에서는 합성 가능한 모든 결과 중, LUT 개수와는 전혀 무관하게, 마이크로 레지스터 개수를 최대한 작게 사용할 합성 예를 추정하기 때문이라고 판단된다. 또 한편으로는 마이크로 레지스터 개수에 대한 하한 추정 문제 자체가 갖는 거대한 변동성과 복잡성으로 인해 제안한 추정 기법이 정밀도에 한계를 가지는 것으로 해석할 수 있으며, 다른 한편으로는 기존 연구 결과보다 더 좋은 합성 결과가 존재할 가능성이 높음을 의미하는 것으로 해석될 수 있다. For a time-multiplexed FPGA, a circuit is partitioned into several subcircuits, so that they temporally share the same physical FPGA device by hardware reconfiguration. In these architectures, all the hardware reconfiguration information called contexts are generated and downloaded into the chip, and then the pre-scheduled context switches occur properly and timely. Typically, the size of the chip required to implement the circuit depends on both the maximum number of the LUT blocks required to implement the function of each subcircuit and the maximum number of micro-registers to store results over context switches in the same time. Therefore, many partitioning or synthesis methods try to minimize these two factors. In this paper, we present a new estimation technique to find the lower bound on the number of micro-registers which can be obtained by any synthesis methods, respectively, without performing any actual synthesis and/or design space exploration. The lower bound estimation is very important in sense that it greatly helps to evaluate the results of the previous work and even the future work. If the estimated lower bound exactly matches the actual number in the actual design result, we can say that the result is guaranteed to be optimal. In contrast, if they do not match, the following two cases are expected: we might estimate a better (more exact) lower bound or we find a new synthesis result better than those of the previous work. Our experimental results show that there are some differences between the numbers of micro-registers and our estimated lower bounds. One reason for these differences seems that our estimation tries to estimate the result with the minimum micro-registers among all the possible candidates, regardless of usage of other resources such as LUTs, while the previous work takes into account both LUTs and micro-registers. In addition, it implies that our method may have some limitation on exact estimation due to the complexity of the problem itself in sense that it is much more complicated than LUT estimation and thus needs more improvement, and/or there may exist some other synthesis results better than those of the previous work.

시분할 FPGA 합성에서 LUT 개수에 대한 하한 추정 기법

엄성용(Seong Yong Ohm) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.7·8

주어진 논리 회로를 시분할 FPGA 칩으로 효과적으로 합성하기 위해서는 전체 회로를 여러개의 부분회로로 나눈 후, 각 부분 회로가 동일한 하드웨어 회로를 시간차를 두고 공유하도록 하여야 한다. 이를 위해 칩에 대한 시간별 재구성 정보를 미리 만들어, 칩 내부의 특정 메모리 영역에 저장하여 두었다가 정해진 시간대가 되면 칩 전체를 재구성하도록 하여야 한다. 그런데, 시분할 FPGA 합성에서 사용하는 세부적인 재구성 기법(일반적으로 스케쥴링이나 다중 회로 분할 기법을 사용)에 따라 동일 시간대에 필요한 LUT의 개수, 즉 FPGA의 용량이 달라질 수 있다. 본 논문에서는 입력되는 논리 회로를 직접 합성하지 않고서도 그 회로가 필요로 하는 전체 LUT 개수에 대한 하한을 추정함으로써 재구성 기법에 관계없이 필요한 최소한의 LUT 개수를 파악한다. 만일, 기존의 재구성 결과가 본 연구에서 추정된 하한과 일치할 경우, 그 결과는 최적의 결과를 의미한다. 반면에, 하한과의 차이가 있는 경우에는 기존의 연구 결과에 비해 더 좋은 재구성 결과가 존재하거나, 또는 본 연구에서 추정한 하한보다 더 좋은(큰, 정확한) 하한이 실제 존재함을 의미한다. 따라서 이러한 비교 분석을 통해, 기존 연구의 결과가 최적인지, 또는 개선의 여지가 있는지를 판단하는 좋은 지표를 제공할 수 있다. 실험 결과, 실험한 대부분의 예제에서, 기존의 연구 결과에서 출력한 결과와 본 논문에서 제안한 방법으로 추정한 하한이 정확히 일치하는 것을 발견할 수 있었는데, 이는 기존의 합성 시스템에서 생성한 결과의 최적성을 확인하게 하는 한편, 본 논문에서 제안한 하한 추정의 정확성을 반증하는 것으로 해석될 수 있다. For a time-multiplexed FPGA, a circuit is partitioned into several subcircuits, so that they temporally share the same physical FPGA device by hardware reconfiguration. In these architectures, all the hardware reconfiguration information called contexts are generated and downloaded into the chip, and then the pre-scheduled context switches occur properly and timely. Since the maximum number of the LUT's required in the same time determines the size of the chip used in the synthesis, it needs to be minimized, if possible. Many previous work use their own approaches, which are very similar to either scheduling method in high level synthesis or multi-way circuit partitioning method, to solve the problem. In this paper, we propose a method which estimates the lower bound on the number of LUT's without performing any actual synthesis. The estimated lower bounds help to evaluate the results of the previous work. If the estimated lower bound on the number of LUT's exactly matches the number of LUT's of the result from the previous work, the result must be optimal. In contrast, if they do not match, the following two cases are expected : the more exact lower bound may exist, or we might find the new synthesis result better than the result from the previous work. Experimental results show that our lower bound estimation method is very accurate. In almost all cases experimented, the estimated lower bounds on the number of LUT's exactly match those of the previous synthesis results respectively, implying that the best results from the previous work are optimal as well as our method predicted the exact lower bound for those examples.

상위 단계 합성에서 결함 복구 기준점 설정을 위한 하한 추정 기법

엄성용(Seong Yong Ohm),전주식(Chu Shik Jhon) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.1

회로의 빠른 결함 복구를 위한 방안의 하나는 복구 기준점이라는 별도의 클럭 주기를 추가하고, 결함 발생 여부의 검사 등과 같은 결함 복구용 작업을 하드웨어적으로 수행하는 방법이다. 본 논문에서는 스케쥴링이 되지 않은 입력 정보로부터, 회로의 기능을 수행하기 위한 연산용 하드웨어 자원 및 결함의 검사와 복구용으로 필요한 하드웨어 자원의 전체 개수에 대한 하한값을 추정하는 새로운 기법을 제안한다. 이 방법에서는 임의의 복구 기준점 쌍에 대해, 그 두 복구 기준점이 연속된 기준점으로 선택될 경우에 필요한 연산자와 레지스터 등의 개수에 대한 하한을 각각 추정하고, 이를 바탕으로 필요한 하드웨어 자원의 비용이 최소화되는 복구 기준점들의 집합을 선택한다. 이 경우, 최소화된 하드웨어 자원의 개수는 임의의 스케쥴링이나 복구 기준점 설정 기법을 통해 얻을 수 있는 개수에 대한 하한 추정값이 된다. 실험 결과, 제안된 방법은 최적의 스케쥴링과 최적의 복구 기준점 설정을 동시에 고려할 경우에 얻을 수 있는 최적의 결과를 정확하게 예측하였다. One common technique for fast recovery from the faults is to insert some additional clocks called recovery points and to perform fault-detection and recovery using additional hardware. In this paper, we present a new technique which estimates lower bounds on the number of hardware resources required to implement both the given behavior and the fault-recovery from the unscheduled input graph. In this method, for each pair of recovery points, we estimate lower bounds on the number of operators and registers required if those two points are selected as the contiguous recovery points. After that, we find a set of recovery points based on the estimates so that the total number of resources are minimized. In that case, such the minimum number of hardware resources of a type represents a lower bound on the number of the hardware resources of the type that could be obtained by any kind of scheduling and/or recovery point insertion techniques. Our experimental results show that our method predicts accurately the globally optimal results which could be obtained by considering scheduling and recovery point insertion concurrently.

SEED 블록 암호 알고리즘의 파이프라인 하드웨어 설계

엄성용(Seong Yong Ohm),이규원(Kyu-Won Lee),박선화(Sun-Hwa Park) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.3·4

최근 들어, 정보 보호의 필요성이 높아지면서, 암호화 및 복호화에 관한 관심이 커지고 있다. 특히, 대용량 정보의 실시간 고속 전송에 사용되기 위해서는 매우 빠른 암호화 및 복호화 기법이 요구되었다. 이를 위한 방안중의 하나로서 기존의 암호화 알고리즘을 하드웨어 회로로 구현하는 연구가 진행되어 왔다. 하지만, 기존 연구의 경우, 구현되는 회로 크기를 최소화하기 위해, 암호화 알고리즘들의 주요 특성인 병렬 수행 가능성을 무시한 채, 동일 회로를 여러 번 반복 수행시키는 방법으로 설계하였다. 이에 본 논문에서는 1998년 한국정보보호센터에서 개발한 국내 표준 암호화 알고리즘 SEED의 병렬 특성을 충분히 활용하는 새로운 회로 설계 방법을 제안한다. 이 방법에서는 암호 연산부의 획기적인 속도 개선을 위해 암호 블록의 16 라운드 각각을 하나의 단계로 하는 16 단계의 파이프라인 방식으로 회로를 구성한다. 설계된 회로 정보는 VHDL로 작성되었으며, VHDL 기능 시뮬레이션 검증 결과, 정확하게 동작함을 확인하였다. 또한 FPGA용 회로 합성 도구를 이용하여, 회로 구현시 필요한 회로 크기에 대한 검증을 실시한 결과, 하나의 FPGA 칩 안에 구현 가능함을 확인하였다. 이는 단일 FPGA 칩에 내장될 수 있는 고속, 고성능의 암호화 회로 구현이 가능함을 의미한다. The need for information security increases interests on cipher algorithms recently. Especially, a large volume of data transmission over high-band communication network requires faster encryption and decryption techniques for real-time processing. It would be a good solution for this problem that we implement the cipher algorithm in forms of hardware circuits. Though some previous researches use this approach, they focus only on repeatedly executing the core part of the algorithm to minimize the hardware chip size, while most cipher algorithms are inherently parallel. In this paper, we propose a new design for the SEED block cipher algorithm developed by KISA (Korea Information Security Agency) in 1998 as Korean standard cipher algorithm. It exploits the parallelism of the algorithm basically and implements it in a pipelined fashion. We described the design in VHDL program and performed functional simulations on the program, and then found that it worked correctly. In addition, we synthesized it and verified that it could be implemented in a single FPGA chip, implying that the new design can be practically used for the actual hardware implementation of a high-speed and high-performance cipher system.

하한 추정을 이용한 휴리스틱 스케쥴링 기법

엄성용(Seong Yong Ohm),전주식(Chu Shik Jhon) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.5

본 논문에서는 ASAP(As Soon As Possible) 스케쥴링 결과를 초기 상태로 하고, 각 상태에서 한 제어스텝씩 지연할 연산의 선택을 하나의 분기로 하는 탐색 공간을 분기와 한계 방식으로 탐색하면서, 최소의 면적 비용을 갖는 스케쥴링 결과를 찾는 새로운 스케쥴링 기법에 대해 설명한다. 이 방법에서는 각 상태에서 면적 비용이 줄어들기 위해 반드시 지연되어야 할 연산을 적어도 하나 포함하는 최소한의 연산 집합을 추출함으로써 탐색 공간을 축소하는 한편, 하한 추정 기법을 도입하여 불필요한 탐색을 효과적으로 방지함으로써 탐색의 효율을 높인다. 이와 더불어, 최적의 결과를 항상 보장하지는 못하지만 탐색 속도를 더욱 향상시키는 휴리스틱 기법을 사용한다. 새로운 방법의 효율성을 보이기 위해 기존의 연구에서 주로 사용된 몇가지 예에 대한 실험 결과를 제시한다. This paper describes a new approach to the scheduling problem in high level synthesis. In this approach, iterative rescheduling processes starting with ASAP scheduling result are performed in a branch-and-bound manner, finding a scheduling result of the lowest hardware cost under the given timing constraint. At each iteration step, only well-selected operations are considered for rescheduling and the lower bound estimation is performed to avoid unnecessary searches effectively, and thus reducing run time considerably in many cases. In addition, heuristics are utilized so as to further improve search speed at the price of optimality in the scheduling result. Some experimental results are given to show the efficiency of the method.

영상의 밝기 평균과 분산을 이용한 엔트로피 최대화 영상 향상 기법

유지현 ( Ji Hyun Yoo ),엄성용 ( Seong Yong Ohm ),정민교 ( Min Gyo Chung ) 한국인터넷정보학회 2012 인터넷정보학회논문지 Vol.13 No.3

본 논문에서는 영상의 밝기 평균과 분산을 이용하여 영상의 엔트로피를 최대화하는 히스토그램 명세화 기반의 영상 향상 기법을 제안한다. 제안 방법은 히스토그램 명세화 과정에서 입력 히스토그램과 목적 히스토그램 모두를 가우시안 분포로 모델링한다. 이 과정에서 입력 가우시안 분포의 평균과 분산은 입력영상의 밝기 평균값과 분산을 각각 그대로 사용한다. 목적 가우시안 분포의 평균도 입력영상의 밝기 평균값을 사용하지만, 분산은 출력 영상의 엔트로피가 최대화되는 분산을 결정하여 사용한다. 다양한 영상에 대한 실험 결과에 의하면, 기존 방법들에 비해 제안 방법은 영상의 평균 밝기를 잘 유지하면서 자연스러운 개선 결과를 보여준다. This paper proposes a histogram specification based image enhancement method, which uses the brightness mean and variance of an image to maximize the entropy of the image. In our histogram specification step, the Gaussian distribution is used to fit the input histogram as well as produce the target histogram. Specifically, the input histogram is fitted with the Gaussian distribution whose mean and variance are equal to the brightness mean(μ) and variance(σ2) of the input image, respectively; and the target Gaussian distribution also has the mean of the value μ, but takes as the variance the value which is determined such that the output image has the maximum entropy. Experimental results show that compared to the existing methods, the proposed method preserves the mean brightness well and generates more natural looking images.

SEED 블록 암호 알고리즘의 파이프라인 칩 설계에 관한 연구

이규원(Kyu-Won Lee),엄성용(Seong-Yong Ohm) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅲ

본 논문에서는 한국정보보호 진흥원에서 표준으로 개발한 128비트 블록암호 알고리즘의 표준인 SEED를 하드웨어 칩으로 설계 연구하였다. 설계 연구 방법은 기존 암호 연산부의 속도 개선의 한 방법으로 암호블록의 16 라운드 각각을 하나의 프로세서로 보고, 이를 파이프라인 방식으로 설계하여 암호 연산의 속도를 증진시키는 방법으로 설계하였다. Cadence의 NCVHDL로 Functional Simulation하고, Synopsys의 Compiler Ⅱ로 Optimize 된 Schematic을 검증하였다.

마커셋을 이용한 지문자 인식 기법

조재현(Jae Hyun Cho),엄성용(Seong Yong Ohm) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.1B

몸의 동작이나 수화의 인식은 크게 입력기 등을 이용한 방법과 2차원 영상 인식에 기반한 방법으로 구분된다. 입력기에 의한 방법은 데이터글러브 등의 기구에 의해 손동작에 대한 3차원 좌표값을 직접 입력받는데 반하여, 영상처리에 의한 방법은 손의 윤곽선 추출과 모양을 인식하여 손동작을 구분해 내는 것이다. 본 논문에서 제안하는 수화 인식 방법은 2차원 영상에 의한 방법으로 기존의 윤곽선 추출에 의한 방법이 아니라, 손의 관절부위에 부착된 마커들 중 마커의 종류와 영상에 나타나는 상대적인 위치 그리고 관절구조의 특성을 이용하여 손의 동작을 비교적 빠른 시간에 정확히 이해한다. 새로운 기법의 효율성을 보이기 위해, 몇 가지 제한된 지문자에 대한 실험 결과를 제시한다.

간단한 얼굴 방향성 검출방법

정민교(Min Gyo Chung),박지숙(Jisook Park),엄성용(Seong Yong Ohm),조현희(Hyun Hee Jo) 한국멀티미디어학회 2006 멀티미디어학회논문지 Vol.9 No.2

DirectShow 프로그래밍을 위한 C 소스 코드 자동 생성 기법

동지연(Ji-Youn Dong),박선화(Sun-Hwa Park),엄성용(Seong-Yong Ohm) 한국정보과학회 2004 정보과학회 컴퓨팅의 실제 논문지 Vol.10 No.1

본 논문에서는 DirectShow 프로그래밍의 주요 개발 도구인 그래프 에디터에서 작성된 필터 연결 그래프로부터 C 소스 코드를 자동 생성하는 시스템에 대해 설명한다. 기존의 DirectShow 프로그래밍 환경에서는 그래프 에디터를 이용한 프로그램 설계 및 실행 확인 작업과 실제 프로그램 코드를 작성하는 프로그램 개발 작업이 별도로 이루어진다. 이에 반해, 본 시스템을 사용할 경우, 멀티미디어 응용 프로그램 개발자는 소스 코드를 직접 일일이 수정할 필요 없이, 그래프 에디터를 이용하여 필터 삽입 및 필터 연결을 통한 프로그램 설계 작업을 수행한 다음, GRF 파일로 저장하기만 하면, 원하는 C 소스 프로그램을 자동적으로 얻을 수 있기 때문에 보다 효과적이고 훨씬 신속한 DirectShow 프로그래밍이 가능하다. 더욱이 본 시스템은, 고정된 개수의 매우 제한된 미디어 제어 기능만을 소스 코드에 추가할 수 있는 기존의 시스템과는 달리, 시스템 사용자인 프로그램 개발자로 하여금 자신이 개발하고자 하는 응용 프로그램에 추가할 미디어 제어 기능을 보다 쉽고 다양하게 선택할 수 있도록 지원하기 때문에 보다 실용적인 도구로 활용될 수 있다. In this paper, we present an automatic C source code generation system for DirectShow based multimedia application programming. In this system, C source code is automatically synthesized from the filter connection graph edited with GraphEdit, a utility tool provided with DirectShow SDK package from Microsoft. In traditional DirectShow programming environments, program design and brief testing steps are usually done with GraphEdit tool just by inserting filters and connecting them properly, while actual implementation of the program should be done separately. The filter connection graph information from GraphEdit is used just as a reference in such the implementation step. Therefore, our system which automatically generates C source code directly from the filter connection graph of GraphEdit seems very useful and many programmers can develop DirectShow based multimedia application programs more effectively and quickly using our system. In addition, our system supports more various media stream control functions for the generated application programs than the existing system such as Wizard which supports limited and fixed number of media control functions only. This feature allows more flexibility in the user interface of the generated source program and makes our system more practical for DirectShow based programming.