[논문]다중 디지털 신호의 비교를 위한 병렬 기법의 VLSI 설계

서영호; 이용석; 김동욱

doi:10.6109/jkiice.2017.21.4.781

다중 디지털 신호의 비교를 위한 병렬 기법의 VLSI 설계
VLSI Design of Parallel Scheme for Comparison of Multiple Digital Signals 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.21 no.4, 2017년, pp.781 - 788

서영호 (Ingenium College of Liberal Arts, Kwangwoon University) , 이용석 (Korea Electronics Technology Institute) , 김동욱 (Department of Electronic Materials Engineering, Kwangwoon University)

초록
AI-Helper

본 논문에서는 여러 디지털 신호의 크기를 비교하기 위한 알고리즘 및 디지털 회로를 제안한다. 제안하고자 하는 알고리즘은 여러 입력을 동시에 비교한 후에 간단한 디지털 논리 함수를 이용하여 그 입력들 중에서 가장 큰 값(혹은 가장 작은 값)을 검출하는 방법을 제공할 수 있다. 이 방식의 단점은 하드웨어 자원이 증가하는 것인데, 이를 위해 중복된 논리동작을 재사용하는 방법을 제안한다. 제안하고자 하는 방식은 회로 속도의 증가, 즉 지연시간의 감소에 초점을 맞추었다. 제안한 비교 알고리즘은 HDL로 구현한 후에 Altera사의 Cyclone III EP3C40F324A7 FPGA 환경에서 실험하였다. 4입력의 경우에 1.20배의 하드웨어 자원을 사용하면서 1.66배 만큼 동작 속도를 증가시킬 수 있다. 또한 8입력의 경우에는 2.15배의 하드웨어 자원을 사용하면서 2.29배로 동작 속도를 증가시킬 수 있다.

Abstract ▼ AI-Helper

This paper proposes a new algorithm for comparing amplitude between multiple digital input signals and its digital logic architecture. After simultaneously comparing multiple inputs, the proposed algorithm can provide the information of the largest (or smallest) value among them by using a simple digital logic function. The drawback of the method is to increase hardware resource. To overcome this we propose a reuse method of the overlapped logic operation. The proposed method focuses on enhancing the operational clock frequency, in other words decreasing combinational delay time. After implementing the comparing method with HDL (hardware description language), we experiment on it with environment of Cyclone III EP3C40F324A7 FPGA of Altera Inc. In case of 4 input signals, it can increase the operational speed as mush as 1.66 times with 1.20 times the hardware resource. In case of 8, it can also have 2.29 times the clock frequency and 2.15 times the hardware resource.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 다수개의 디지털 신호의 크기를 비교하기 위한 알고리즘과 그에 대한 VLSI 구조를 제안하였다. 제안하고자 하는 알고리즘은 여러 입력을 동시에 비교한 후에 간단한 디지털 논리 함수를 이용하여 그 입력들 중에서 가장 큰 값 혹은 가장 작은 값을 검출하는 방법을 제안하였다.
본 논문에서는 두 가지 비교 방법에 대해 논의하고자 한다. 비교방법1은 제안하는 기본적인 기본 알고리즘으로 가장 큰 값들을 모두 검출 가능하다.
본 논문은 상위수준, 특히 RTL(register transfer level)에서의 설계 방법론을 이용하여 4개 이상의 입력에 대한 비교를 수행할 수 있는 비교 기법 및 그에 대한 VLSI 구조를 제안하고자 한다. 본 논문은 다음과 같이 구성된다.
지금까지의 디지털 비교기에 대한 연구를 2가지 측면에서 고려해 보고자 한다. 첫 번째는 비교기의 구현 수준이다.

제안 방법

1 버전이 다. HDL을 이용하여 구현한 이후에 구현된 하드웨어의 속도와 자원량(셀 개수)를 측정하였다. 그 결과를 그림 6과 7에 나타냈다.
두 개의 이진수를 비교하기 위한 Look-Ahead Logic을 고안하여 비교기의 속도를 향상시켰다[22]. Sachdev는 2의 최대 스택 높이를 구성하기 위해 전-인코딩 특징을 가지는 새로운 트리 구조의 비교기를 제안한다. 이 설계는 특히 저전력을 이루기 위해 패스 트랜지스터 및/혹은 정적 로직의 구현에 적합하다[23].
Chaudhury는 2개의 수를 비교할 수 있는 디지털 이진 비교기를 제안하고 있다. 두 개의 이진수를 비교하기 위한 Look-Ahead Logic을 고안하여 비교기의 속도를 향상시켰다[22]. Sachdev는 2의 최대 스택 높이를 구성하기 위해 전-인코딩 특징을 가지는 새로운 트리 구조의 비교기를 제안한다.
또한 전통적인 방식(Traditional), 방법1(Method 1), 그리고 방법2(Method 2)에 대해서 각각 구현하였다. 따라서 총 18가지 조건에 대해 각각 하드웨어를 HDL로 구현하고, 실험을 수행하였다.
실험에서는 입력의 개수를 4개와 8 개로 정하여 구현하였고, 입력의 비트너비는 8, 16, 32 비트로 수행하였다. 또한 전통적인 방식(Traditional), 방법1(Method 1), 그리고 방법2(Method 2)에 대해서 각각 구현하였다. 따라서 총 18가지 조건에 대해 각각 하드웨어를 HDL로 구현하고, 실험을 수행하였다.
그 결과를 그림 6과 7에 나타냈다. 실험에서는 입력의 개수를 4개와 8 개로 정하여 구현하였고, 입력의 비트너비는 8, 16, 32 비트로 수행하였다. 또한 전통적인 방식(Traditional), 방법1(Method 1), 그리고 방법2(Method 2)에 대해서 각각 구현하였다.
다음으로 가장 큰 결과가 여러 개일 경우에 약속된 위치의 데이터를 검출할 수 있도록 한다. 여러개의 큰 값이 입력될 경우에 가장 왼쪽에 입력된 하나의 값을 가장 큰 값으로 검출하도록 하였다. 가장 오른쪽 값을 검출하고자 할 경우에는 비교하는 방향을 바꾸면 가능하다.
[19]에서는 고성능 및 저면적 디지털 비교기를 위한 비트단위 경쟁논리회로(bitwise competition logic, BCL)가 제안되었다. 이 회로는 산술 연산을 사용하지 않고 MSB로부터 첫 번째 1의 위치를 이용하여 두 정수를 비교한다. Corsonello는 트리-기반 비교기를 제안하였는데, 비교 과정을 용이하게 하기 위해 다이나믹 맨체스터 구조를 이용한다[20,21].
본 논문에서는 다수개의 디지털 신호의 크기를 비교하기 위한 알고리즘과 그에 대한 VLSI 구조를 제안하였다. 제안하고자 하는 알고리즘은 여러 입력을 동시에 비교한 후에 간단한 디지털 논리 함수를 이용하여 그 입력들 중에서 가장 큰 값 혹은 가장 작은 값을 검출하는 방법을 제안하였다. 제안한 비교 알고리즘은 HDL로 구현한 후에 알테라사의 Cyclone III EP3C40F324A7 FPGA 에 맵핑하여 실험하였다.
제안한 구조는 FPGA 환경에서 구현하여 특성을 검증하였다. 사용한 FPGA는 Altera사의 Cyclone III EP3C40F324A7이고, 사용한 툴은 Quatus II 9.
제안하고자 하는 알고리즘은 여러 입력을 동시에 비교한 후에 간단한 디지털 논리 함수를 이용하여 그 입력들 중에서 가장 큰 값 혹은 가장 작은 값을 검출하는 방법을 제안하였다. 제안한 비교 알고리즘은 HDL로 구현한 후에 알테라사의 Cyclone III EP3C40F324A7 FPGA 에 맵핑하여 실험하였다. 입력의 개수가 증가할수록 병렬적인 비교로 인한 하드웨어 자원의 사용율은 증가하지만 그에 따라 동작 주파수도 증가함을 확인할 수 있었다.

대상 데이터

제안한 구조는 FPGA 환경에서 구현하여 특성을 검증하였다. 사용한 FPGA는 Altera사의 Cyclone III EP3C40F324A7이고, 사용한 툴은 Quatus II 9.1 버전이 다. HDL을 이용하여 구현한 이후에 구현된 하드웨어의 속도와 자원량(셀 개수)를 측정하였다.

성능/효과

8입력의 경우를 종합적으로 고려하면 방법 2는 전통적인 방법에 비해서 2배의 하드웨어 자원 을 사용하면서 2배만큼 동작속도를 증가시킨다. 2배의 자원을 투입해서 2배의 속도 향상을 가져왔다는 것에 대해 VLSI 설계에서 객관적인 효율성으로 이야기할 수는 없지만 상위 수준의 설계 방법론을 이용해서 속도가 중요한 응용분야를 위한 대안을 제시할 수 있다는 점은 충분히 의미가 있을 것으로 사료된다.
또한 각 방법들을 비교하면 방법2가 가장 빠른 동작속도를 갖는다는 것을 확인할 수 있다. 4개의 입력인 경우를 살펴보면 8비트를 제외하고 16비트와 32비트는 거의 5MHz 이내로 속도의 차이가 난다.
8입력의 경우에는 방법1은 전통적인 방식의 약 4배에 해당하는 자원을 사용하고 방법 2는 약 2배에 해당하는 자원을 사용한다. 8입력의 경우를 종합적으로 고려하면 방법 2는 전통적인 방법에 비해서 2배의 하드웨어 자원 을 사용하면서 2배만큼 동작속도를 증가시킨다. 2배의 자원을 투입해서 2배의 속도 향상을 가져왔다는 것에 대해 VLSI 설계에서 객관적인 효율성으로 이야기할 수는 없지만 상위 수준의 설계 방법론을 이용해서 속도가 중요한 응용분야를 위한 대안을 제시할 수 있다는 점은 충분히 의미가 있을 것으로 사료된다.
모든 방식에서 최대 동작 주파수는 8비트의 경우가 가장 빠르고, 16비트의 경우가 가장 느리다. 또한 각 방법들을 비교하면 방법2가 가장 빠른 동작속도를 갖는다는 것을 확인할 수 있다. 4개의 입력인 경우를 살펴보면 8비트를 제외하고 16비트와 32비트는 거의 5MHz 이내로 속도의 차이가 난다.
그림 4에 이와 같이 개선된 방법을 나타내었다. 본 논문에서 제안하고 있는 비교방법은 기본적으로 입력들 간에 병렬 비교를 사용하기 때문에 고성능에는 매우 적합하지만 그에 따른 하드웨어 자원도 증가한다. 따라서 하드웨어 자원을 줄이기 위한 시도가 필요하다.
전통적인 방식에 비해서 방법 1은 평균 약 77MHz, 그리고 방법 2는 평균 약 101MHz의 동작속도가 증가했다. 본 실험을 통해서 제안한 방법은 전통적인 방식에 비해서 매우 효과적으로 동작속도를 증가시킬 수 있다는 것을 확인하였다.
제안한 비교 알고리즘은 HDL로 구현한 후에 알테라사의 Cyclone III EP3C40F324A7 FPGA 에 맵핑하여 실험하였다. 입력의 개수가 증가할수록 병렬적인 비교로 인한 하드웨어 자원의 사용율은 증가하지만 그에 따라 동작 주파수도 증가함을 확인할 수 있었다. 즉, 본 논문이 목표로 하는고속의 비교기 구현이 가능하다는 것을 확인할 수 있었다.
그러나 8입력의 경우에는 전통적인 방식 대비 방법 1은 84%만큼 동작속도가 증가했고, 방법 2는 110%만큼 동작속도가 증가했다. 전통적인 방식에 비해서 방법 1은 평균 약 77MHz, 그리고 방법 2는 평균 약 101MHz의 동작속도가 증가했다. 본 실험을 통해서 제안한 방법은 전통적인 방식에 비해서 매우 효과적으로 동작속도를 증가시킬 수 있다는 것을 확인하였다.
제안한 기본 방법은 병렬적으로 입력값들을 서로 비교하기 때문에 면적이 크게 증가한다. 그림 7에 면적에 대한 결과를 나타냈다.
Yoo는 빠르고 작은 면적을 갖는 64비트 네 개의 이진수를 비교기를 제안하였다. 제안한 비트-단위 비교 논리 체인(bit-wise comparing logic chain, BCLC)과 순차적 스트로브(sequential strobe, SS) 기법은 64비트 네 개의 이진 수를 1.55ns의 지연시간만에 비교할 수 있었다 [25]. 최근의 연구들에서 [22]의 연구를 제외하고는 모두 하위 수준에서의 비교기를 구현한 것들이라서 본 논문의 방향과는 다소 차이를 갖는다.
입력의 개수가 증가할수록 병렬적인 비교로 인한 하드웨어 자원의 사용율은 증가하지만 그에 따라 동작 주파수도 증가함을 확인할 수 있었다. 즉, 본 논문이 목표로 하는고속의 비교기 구현이 가능하다는 것을 확인할 수 있었다. 본 논문에서 제안된 기법은 서론에서 설명한 것과 같이 다양한 응용분야에서 다수의 입력에 대한 비교를 수행할 수 있는 다양한 형태의 비교기로 사용될 수 있을 것으로 사료된다.

후속연구

즉, 본 논문이 목표로 하는고속의 비교기 구현이 가능하다는 것을 확인할 수 있었다. 본 논문에서 제안된 기법은 서론에서 설명한 것과 같이 다양한 응용분야에서 다수의 입력에 대한 비교를 수행할 수 있는 다양한 형태의 비교기로 사용될 수 있을 것으로 사료된다.
상위 수준 설계 방법론을 이용해서 RTL(register transfer level)에서 다수 개의 입력에 대한 비교기를 설계한 다른 연구가 없기 때문에 실험결과를 다른 연구사례와 비교하기는 어렵다는 점은 본 논문의 실험결과를 정리하는데 있어서 다소 아쉬운 부분으로 볼 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	정렬 연산은 어떤 연산을 하는가?	비교기는 두 개의 숫자의 크기를 비교하는데 사용되는 기본적이고 본질적인 연산 유닛으로 회로에서 매우 중요한 조합회로 요소이다[1,2]. 정렬 연산은 본질적으로는 많은 양의 데이터를 오름차순 혹은 내림차순으로 정렬하기 위해서 수많은 비교 연산을 수행한다[3]. 특히 비교함수는 디지털신호 처리와 영상 및 음성처리와 같은 영역들에서 많이 사용된다[4,5].
	비교기란 무엇인가?	비교기는 두 개의 숫자의 크기를 비교하는데 사용되는 기본적이고 본질적인 연산 유닛으로 회로에서 매우 중요한 조합회로 요소이다[1,2]. 정렬 연산은 본질적으로는 많은 양의 데이터를 오름차순 혹은 내림차순으로 정렬하기 위해서 수많은 비교 연산을 수행한다[3].
	병렬 덧셈기의 단점은 무엇인가?	다른 방법은 직접적으로 비교 함수를 전개하는 방정식에 기초하여 구현될 수 있다. 이런 방식들은 전통적인 방식이라 할 수 있고, 면적의 효율성과 전력 소모의 측면에서 많은 단점을 가지고 있다. 이를 극복하기 위해 지금까지 여러 연구가 진행되었다 [13-25].

참고문헌 (26)

R. J. Tocci, N. Widmer, and G. Moss, Digital Systems: Principles and Applications, 11th ed. London, Pearson, 2010.
I. Koren, Computer Arithmetic Algorithms, 2nd ed, Florida, A K Peters/CRC Press, 2001.
K. Mehlhorn, Sorting and Searching, 1st ed. Springer- Verlag, Berlin, 1984.
W. Alexander, C and M Williams, Digital Signal Processing: Principles, Algorithms and System Design, 1st ed, Massachusetts, Academic Press, 2017.
J.W. Kang, "Disparity Vector Derivation Method for Texture-Video-First-Coding Modes of 3D Video Coding Standards," Journal of The Korean Institute of Communication Sciences, vol. 40. no. 10, pp. 2080-2089, Oct. 2015.

원문보기 상세보기
S.B. Yoon, S.H. B, H.J. Park, and J.H. Yi, "Probabilistic Graph Based Object Category Recognition Using the Context of Object-Action Interaction," Journal of The Korean Institute of Communication Sciences, vol. 40, no. 11, pp. 2284-2290, Nov. 2015.

원문보기 상세보기
H. Lee, K. Cho, H. Kim, S. Choi, J. Lim and J. Kim, "Electrical performance of high bandwidth memory (HBM) interposer channel in terabyte/s bandwidth graphics module," 2015 International 3D Systems Integration Conference (3DIC), Sendai, pp. TS2.2.1-TS2.2.4, 2015.
M. K. Jaiswal, B. S. C. Varma, H. K. H. So, M. Balakrishnan, K. Paul, and R. C. C. Cheung, "Configurable Architectures for Multi-Mode Floating Point Adders," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, no. 8, pp. 2079-2090, Aug. 2015.

상세보기
S. Abed, M. Al-Shayeji, S. Sultan, and N. Mohammad, "Hybrid approach based on partial tag comparison technique and search methods to improve cache performance," IET Computers & Digital Techniques, vol. 10, no. 2, pp. 69-76, Nov. 2016.

상세보기
M. Codish, L. Cruz-Filipe, M. Frank, and P. Schneider-Kamp, "Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)," 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, Limassol, pp. 186-193, 2014.
R. Woo, S. Choi, J.H. Sohn, S.J. Song, and H.J. Yoo, "A Low-Power 3-D Rendering Engine With Two Texture Units and 29-Mb Embedded DRAM for 3G Multimedia Terminals," IEEE Journal of Solid-State Circuits, vol. 39, no.7, pp. 1101-1109, Jul. 2004.

상세보기
S. S. Ameer Abbas, S. J. Thiruvengadam, and N. A. R. Kumar, "Realization of receiver architectures using VLSI DSP techniques for broadcast channel in LTE," 2014 International Conference on Embedded Systems (ICES), Coimbatore, pp. 12-17, 2014.
C.C. Wang, C.F. Wu, and K.C. Tsai, "1 GHz 64-Bit high-speed comparator using ANT dynamic logic with two-phase clocking," IEE Proceedings - Computers and Digital Techniques., vol. 145, no. 6, pp. 433-436, Nov. 1998.

상세보기
C.C. Wang, P.M. Lee, C.F. Wu, and H.L. Wu, "High Fan-In Dynamic CMOS Comparators With Low Transistor Count," IEEE Transactions on Circuits and Systems I : Fundamental Theory and Applications, vol. 50, issue 9, pp. 12161-220, Sep. 2003.
C.H. Huang and J.S. Wang, "High-performance and power-efficient CMOS comparators," IEEE Journal of Solid-State Circuits, vol. 38, no. 2, pp. 254-262, Feb. 2003.

상세보기
S.W. Cheng, "A High-Speed Magnitude Comparator With Small Transistor Count," IEEE Proceedings of International Conference on Electronics, Circuits and Systems, vol. 3, pp. 1168-1171, Dec. 2003.
H.M. Lam and C.Y. Tsui, "High-performance single clock cycle CMOS comparator," Electron. Letters., vol. 42, no. 2, pp. 75-77, Jan. 2006.

상세보기
H.M. Lam and C.Y. Tsui, "A MUX-based high-performance single cycle CMOS comparator," IEEE Transactions on Circuits and Systems. II, Exp. Briefs, vol. 54, no. 7, pp. 591-595, Jul. 2007.

상세보기
J.Y. Kim and H.J. Yoo, "Bitwise Competition Logic for Compact Digital Comparator," IEEE Asian Solid Stated Circuits Conference, Jeju, pp. 59-62, Nov. 2007.
S. Perri, and P. Corsonello, "Fast low-cost implementation of single-clock cycle binary comparator," IEEE Transactions on Circuits and Systems II, Exp. Briefs, vol. 55, no. 12, pp. 1239-1243, Dec. 2008.

상세보기
F. Frustaci, S. Perri, M. Lanuzza, and P. Corsonello, "A new low-power high-speed single-clock-cycle binary comparator," Proceedings of 2010 IEEE International Symposium on Circuits and Systems, Paris, pp. 317-320, May 2010.
S. Deb and S. Chaudhury, "High-speed comparator architectures for fast binary comparison," 2012 Third International Conference on Emerging Applications of Information Technology (EAIT), Kolkata, pp. 454-457, Nov. 2012.
P. Chuang, D. Li, and M. Sachdev, "A Low-Power High-Performance Single-Cycle Tree-Based 64-Bit Binary Comparator," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 59, no. 2, pp. 108-112, Feb. 2012.

상세보기
S.C. Hsia, "High-speed multi-input comparator," IEE Proceedings - Circuits, Devices and Systems, vol. 152, no. 3, pp. 210-214, Jun. 2005.

상세보기
M. Kim, J. Y. Kim, and H. J. Yoo, "A 1.55ns 0.015 mm2 64-bit quad number comparator," 2009 International Symposium on VLSI Design, Automation and Test, Hsinchu, pp. 283-286, Apr. 2009.
ARM information center. AMBA [Internet]. Available: http://infocenter.arm.com/help/index.jsp?topic/com.arm.doc.set.amba/index.html.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증