Benes 네트워크 제어 신호 최적화를 이용한 WiMAX QC-LDPC 복호기용 저면적/고속 Multi-Size Circular Shifter

강형주,Kang, Hyeong-Ju 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.10

탁월한 에러 정정 능력으로 인해 최근 통신 표준에서 많이 채택되고 있는 low-density parity-check(LDPC) 코드중, quasi-cyclic LDPC(QC-LDPC) 코드는 복호기 복잡도가 비교적 낮아서 많이 사용되고 있다. QC-LDPC 코드의 복호기 설계에 있어서 중요한 블록 중 하나가 여러 가지 크기의 rotation을 수행할 수 있는 multi-size circular shifter(MSCS)이다. MSCS의 여러 구현 방법 중 많이 사용되는 Benes 네트워크는 일반적인 MSCS 동작에는 효율적이나 rotation 크기 등의 특징을 이용할 수 없는 단점이 있다. 이 논문에서는 Benes 네트워크의 제어 신호 생성을 수정하여서 rotation 크기 특징을 이용할 수 있는 방법을 제시한다. 제안된 제어 신호 생성법을 IEEE 802.16e WiMAX 표준의 QC-LDPC 코드 복호기에 적용하여, MUX의 개수를 줄이고 지연 시간을 단축하였다. One of various low-density parity-check(LDPC) codes that has been adopted in many communication standards due to its error correction ability is a quasi-cyclic LDPC(QC-LDPC) code, which leads to comparable decoder complexity. One of the main blocks in the QC-LCDC code decoder is a multi-size circular shifter(MSCS) that can perform various size rotation. The MSCS can be implemented with many structures, one of which is based on Banes network. The Benes network structure can perform the normal MSCS operation efficiently, but it cannot use the properties coming from specifications like rotation sizes. This paper proposesd a scheme where the Benes network structure can use the rotation size property with the modification of the control signal generation. The proposed scheme is applied to the MSCS of IEEE 802.16e WiMAX QC-LDPC decoder to reduce the number of MUXes and the critical path delay.

두 개의 직렬 Barrel-Rotator를 이용한 QC-LDPC 복호기용 저면적 Multi-Size Circular Shifter

강형주,Kang, Hyeong-Ju 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.8

Low-density parity-check(LDPC) 코드는 우수한 에러 정정 능력으로 인해 점점 많은 통신 표준에서 채택되고 있으며 그 중 구현이 용이한 quasi-cyclic LDPC(QC-LDPC)가 많이 사용되고 있다. QC-LDPC 복호기에서는 데이터들을 rotation할 수 있는 cyclic-shifter가 필요하며, 이 cyclic-shifter는 다양한 크기의 rotation을 수행할 수 있어야 한다. 이러한 cyclic-shifter를 multi-size circular shifter(MSCS)라고 부르며, 이 논문에서는 MSCS를 적은 면적으로 구현한 구조를 제안한다. 기존의 직렬로 배치된 barrel-rotator 구조에서 rotation의 성질을 이용하여 필요 없는 멀티플렉서를 가려내고 이들을 제거함으로써 저면적을 구현하였다. 실험 결과 면적을 약 12% 줄일 수 있었다. The low-density parity-check(LDPC) code has been adopted in many communication standards due to its error correcting performance, and the quasi-cyclic LDPC(QC-LDPC) is widely used because of implementation easiness. In the QC-LDPC decoder, a cyclic-shifter is required to rotate data in various sizes. This kind of cyclic-shifters are called multi-size circular shifter(MSCS), and this paper proposes a low-complexity structure for MSCS. In the conventional serially-placed two barrel-rotators, the unnecessary multiplexers are revealed and removed, leading to low-complexity. The experimental results show that the area is reduced by about 12%.

ResNet-50 합성곱 신경망을 위한 고정 소수점 표현 방법

강형주,Kang, Hyeong-Ju 한국정보통신학회 2018 한국정보통신학회논문지 Vol.22 No.1

최근 합성곱 신경망은 컴퓨터 비전에 관련된 여러 분야에서 높은 성능을 보여 주고 있으나 합성곱 신경망이 요구하는 많은 연산양은 임베디드 환경에 도입되는 것을 어렵게 하고 있다. 이를 해결하기 위해 ASIC이나 FPGA를 통한 합성곱 신경망의 구현에 많은 관심이 모이고 있고, 이러한 구현을 위해서는 효율적인 고정 소수점 표현이 필요하다. 고정 소수점 표현은 ASIC이나 FPGA에서의 구현에 적합하나 합성곱 신경망의 성능이 저하될 수 있는 문제가 있다. 이 논문에서는 합성곱 계층과 배치(batch) 정규화 계층에 대해 고정 소수점 표현을 분리해서, ResNet-50 합성곱 신경망의 합성곱 계층을 표현하기 위해 필요한 비트 수를 16비트에서 10비트로 줄일 수 있게 하였다. 연산이 집중되는 합성곱 계층이 더 간단하게 표현되므로 합성곱 신경망 구현이 전체적으로 더 효율적으로 될 것이다. Recently, the convolutional neural network shows high performance in many computer vision tasks. However, convolutional neural networks require enormous amount of operation, so it is difficult to adopt them in the embedded environments. To solve this problem, many studies are performed on the ASIC or FPGA implementation, where an efficient representation method is required. The fixed-point representation is adequate for the ASIC or FPGA implementation but causes a performance degradation. This paper proposes a separate optimization of representations for the convolutional layers and the batch normalization layers. With the proposed method, the required bit width for the convolutional layers is reduced from 16 bits to 10 bits for the ResNet-50 neural network. Since the computation amount of the convolutional layers occupies the most of the entire computation, the bit width reduction in the convolutional layers enables the efficient implementation of the convolutional neural networks.

Ultra-long FFT를 위한 Radix-2 기반 구조

강형주,Kang, Hyeong-Ju 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.9

This paper compares radix-2 based structures for 32768-point FFT. Radix-$2^k$ structures have been widely used because the butterfly is simple and the number of multipliers can be reduced in those structures. This paper applied various radix-$2^k$ structures to 32768-point FFT that is representing ultra-long FFT. The ultra-long FFT has been studied much recently. This paper shows that the radix-$2^4$ structure is the most adequate because it shows the smallest complexity in the synthesis and the best SQNR performance. should be placed here. 본 논문에서는 32768-point FFT에서 radix-2에 기반한 구조들을 비교한다. Radix-2에 기반한 radix-$2^k$ 구조들은 버터플라이가 단순하면서 곱셈기의 수를 줄일 수 있어서 많이 이용되고 있다. 본 논문에서는 근래에 많이 연구되고 있는 ultra-long FFT 중 대표적인 32768-point FFT에 대해 다양한 radix-$2^k$ 구조를 적용하였다. 합성했을 때의 복잡도와 SQNR 성능을 비교한 결과 radix-$2^4$ 구조가 가장 적합함을 보였다.

전달 루틴의 병렬화를 통한 SAT 알고리즘의 GPGPU 가속화

강형주,Kang, Hyeong-Ju 한국정보통신학회 2016 한국정보통신학회논문지 Vol.20 No.10

대량의 데이터를 병렬적으로 처리할 수 있는 General-Purpose Graphics Processing Unit(GPGPU)가 최근 많은 분야에서 적용되고 있으며, 이는 전자 설계 자동화 분야에서도 예외가 아니다. SAT 알고리즘은 다양한 전자 설계 자동화 문제에 적용되는 대표적인 알고리즘 중 하나이다. GPGPU를 이용해서 SAT 알고리즘을 가속화하기 위해 노력이 이루어져 왔으나, SAT 알고리즘 자체의 특성으로 인해 병렬화에 어려움이 있어왔다. 이 논문에서는 SAT 알고리즘의 내부 과정 중 비교적 병렬화가 용이한 전달 루틴을 병렬화함으로써 GPGPU 가속화를 적용하였다. 전달 루틴이 희소 행렬의 곱셈과 유사한 점에 착안하여 데이터 구조를 구성하고 이에 맞추어서 병렬적인 전달 루틴을 작성하였다. 병렬적으로 동작하는 쓰레드들 사이의 데이터 손실을 방지하기 위해 아토믹(atomic) 연산을 이용하였다. 벤치마크 SAT 문제들에 대해 기존의 GPGPU 기반 SAT solver에 비해 성능이 10배 이상 향상되었음을 확인하였다. Because of the enormous processing ability, General-Purpose Graphics Processing Unit(GPGPU) has been applied to many fields including electronics design automation. The SAT algorithm is one of the core algorithm in many electronics design automation tools. There has been some efforts to apply GPGPU to the SAT algorithm, but it is difficult to parallelize the SAT algorithm because of its characteristics. In this paper, I applied GPGPU to the SAT algorithm by parallelizing the propagation routine that is relatively suitable to parallel processing. On the basis of the similarity of the propagation routine to the sparse matrix multiplication, the data structure for the SAT problem is constituted, and the parallel propagation routine is described. To prevent data loss between paralllel threads, atomic operations are exploited. The experimental results for some benchmark SAT problems show that the proposed algorithm is superior to the previous GPGPU-based SAT solver.

고속 3×3 스위치를 이용한 Benes 네트워크 기반 Multi-Size Circular Shifter

강형주,Kang, Hyeong-Ju 한국정보통신학회 2015 한국정보통신학회논문지 Vol.19 No.11

Low-density parity-check(LDPC) 코드는 그 탁월한 에러 정정 능력으로 인해 많은 통신 표준에서 사용되고 있다. 여러 종류의 LDPC 코드 중 quasi-cyclic LDPC(QC-LDPC) 코드가 많이 사용되는데 QC-LDPC 코드의 복호기에는 여러 크기의 rotation을 수행할 수 있는 multi-size circular shifter(MSCS)가 필요하다. MSCS의 구현 방법 중 Benes 네트워크에 기반한 구조가 많이 사용되는데, rotation할 데이터의 개수가 3의 배수일 경우에는 $3{\times}3$ 스위치가 필요하다. 이 논문에서는 기존의 제어 신호 생성에 비해 복잡도가 줄어든 생성법과 기존의 $3{\times}3$ 스위치 구조 보다 더 빨리 동작할 수 있는 $3{\times}3$ 스위치 구조를 제안한다. IEEE 802.16e WiMAX 표준에서 사용되는 QC-LDPC 코드 복호기의 MSCS 에 적용하여 지연 시간을 8.7% 정도 줄이고 면적도 조금 감소시켰다. The low-density parity check(LDPC) code is being widely used due to its outperformed error-correction ability. The decoder of the quasi-cyclic LDPC(QC-LDPC) codes, a kind of LDPC codes, requires a multi-size cyclic shifter(MSCS) performing rotation of various sizes. The MSCS can be implemented with a Benes network, which requires a $3{\times}3$ switch if the number of data to be rotated is a multiple of 3. This paper proposes a control signal generation with lower complexity and a faster $3{\times}3$ switch. For the experiment, the proposed schemes are applied to the MSCS of an IEEE 802.16e WiMAX QC-LDPC code decoder. The result shows that the delay is reduced by about 8.7%.

Retiming을 이용한 Symbolic Model Checking 성능 향상에 관한 연구

강형주,Kang, Hyeong-Ju 한국정보통신학회 2010 한국정보통신학회논문지 Vol.14 No.10

This paper presents an application of retiming to model checking, a branch of formal verification. Retiming can change the transition relation of a circuit without changing its input-output behaviour by relocating its registers. With the retiming, a given circuit can have a different structure more adequate for model checking. This paper proposes a cost function to reflect the number of registers and the characteristic of its transition relation and develops a heuristic annealing algorithm to search efficiently the circuit structures obtained by retiming. Experimental results show that the proposed method can improve the model checking performance. 이 논문에서는 형식 검증(formal verification)의 한 분야인 모델 검증(model checking)에 재타이밍(retiming) 기법을 적용하는 방법에서 대해 연구하였다. 재타이밍은 주어진 회로의 레지스터들을 재배치함으로써, 입출력 동작을 바꾸지 않으면서 전이 관계(transition relation)을 변환할 수 있는 기법이다. 이러한 재타이밍을 이용하면 모델 검증을 더 효율적으로 수행하도록 회로를 바꿀 수 있다. 이 논문에서는, 레지스터의 개수와 전이 관계의 특성을 반영한 cost 함수를 제안하고, 재타이밍으로 얻을 수 있는 회로 구조들을 효율적으로 탐색하는 heuristic annealing 알고리즘을 개발한다. 제안된 방법이 모델 검증의 성능을 향상시킬 수 있음을 실험 결과를 통해 보여주었다.

버퍼 변환과 단일 위치 레지스터 구조를 이용한 저전력 DTMB 디인터리버 구조

강형주,Kang, Hyeong-Ju 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.5

본 논문에서는 버퍼 변환과 단일 위치 레지스터 구조를 이용하여 SDRAM에서의 전력 소모를 줄이는 DTMB 디인터리버 구조를 제안하였다. 수신 성능 향상을 위해 인터리빙의 길이가 긴 DTMB의 디인터리버는 그 특성상 SDRAM에 긴 지연버퍼들을 배치하여 구현한다. 그러나 기존의 구조는 데이터를 읽고 쓸 때 마다 거의 매번 새로운 SDRAM row를 활성화하는 단점이 있다. 제안하는 구조에서는 버퍼 변환을 통해 길이가 짧은 여러 개의 지연버퍼로 변환함으로써 row 활성화 수를 줄이고, 단일 위치 레지스터 구조를 도입하여 위치 레지스터의 개수가 늘어나는 문제점을 보완하였다. 실험결과를 통해 면적은 거의 동일하면서 SDRAM에서의 전력 소모는 약 37%로 줄일 수 있음을 확인하였다. This paper proposes a DTMB deinterleaver structure to reduce the SDRAM power consumption with buffer conversion and the single pointer-register structure. The DTMB deinterleaver with deep interleaving for higher performance consists of long delay buffers allocated on SDRAM. The conventional structure activates a new SDRAM row almost everytime when it reads and writes a datum. In the proposed structure, long buffers are transformed into several short buffers so that the number of row activations is reduced. The single pointer-register structure solves the problem of many pointer-registers. The experimental results show that the SDRAM power consumption can be reduced to around 37% with slight logic area reduction.

데이터 페어링을 이용한 SDRAM의 전력 소모를 줄이는 DTMB 디인터리버 구조

강형주 ( Hyeong Ju Kang ) 한국항행학회 2011 韓國航行學會論文誌 Vol.15 No.2

본 논문에서는 SDRAM의 전력 소모를 줄이는 DTMB 디인터리버의 구조를 제안한다. DTMB는 중국의 디지털 TV 표준으로써, 길이가 긴 지연버퍼들로 이루어진 디인터리버를 가지고 있다. 이 디인터리버를 구현하려면 SDRAM이 필요하다. 본 논문에서는 디인터리버에서 데이터를 페어링하여 두 개의 데이터를 한 번에 SDRAM에 읽거나 쓰는 구조를 제안한다. 제안된 구조는 SDRAM을 동작시키는 횟수를 줄임으로써 SDRAM에서 소모되는 전력을 약 35% 줄일 수 있다. This paper presents a DTMB deinterleaver structure to reduce SDRAM power consumption. DTMB, the Chinese digital TV standard, has a deinterleaver that consists of many long delay buffers. SDRAM is used for this deinterleaver. The proposed structure pairs data and transfer a pair with an SDRAM transfer. With the reduction of the SDRAM operation number, the proposed structure can save the SDRAM power consumption by around 35%.

버퍼 변환을 이용한 저면적 ISDB-T 시간 디인터리버 구조

강형주 ( Hyeong Ju Kang ) 한국항행학회 2011 韓國航行學會論文誌 Vol.15 No.2

본 논문에서는 저면적 ISDB-T 시간 디인터리버 구조를 제안하였다. ISDB-T는 일본과 중남미에서 많이 사용되고 있는 이동형 TV 표준으로써 긴 인터리빙을 이용하여 다른 표준에 비해 높은 성능을 보이고 있다. 그러나 긴 인터리빙을 구현하기 위해서는 많은 지연 버퍼가 필요하다. 지연 버퍼들은 주소 레지스터가 있어야 하므로 주소 레지스터의 개수도 많아진다. 본 논문에서는 디인터리버의 등가 변환을 통해 주소 레지스터의 개수를 크게 줄이는 구조를 제안하였다. 실험 결과를 통해 디인터리버의 면적을 줄일 수 있음을 확인할 수 있었다. This paper presents a small-area ISDB-T time deinterleaver structure. ISDB-T is an mobile TV standard that is widely used in Japan and many South American countries. One of the strong points of the standard is the long interleaving depth, which enhance the communication performance. However, long interleaving requires many delay buffers, in other words many pointer registers. This paper reduces the number of pointer registers with the deinterleaver equivalent transformation. The experimental results show that the area is reduced with the proposed structure.