[논문]SIMD 구조를 갖는 프로세서에서 FFT 연산 가속화

이주영; 홍용근; 이현석

doi:10.5573/ieie.2015.52.2.097

SIMD 구조를 갖는 프로세서에서 FFT 연산 가속화
Acceleration of FFT on a SIMD Processor 원문보기

Journal of the Institute of Electronics and Information Engineers = 전자공학회논문지, v.52 no.2, 2015년, pp.97 - 105

이주영 (광운대학교 전자통신공학과) , 홍용근 (광운대학교 전자통신공학과) , 이현석 (광운대학교 전자통신공학과)

초록
AI-Helper

이 논문은 SIMD 구조를 갖는 프로세서에서 FFT 연산을 효과적으로 처리하는 방법에 대한 것이다. FFT는 디지털 신호처리 분야에서 널리 사용되는 범용 알고리즘으로 이의 효과적인 처리는 성능 향상에 있어서 매우 중요하다. Bruun 알고리즘은 반복적인 인수분해를 통해 구현되는 FFT 알고리즘으로, 널리 사용되는 Cooley-Tukey 알고리즘에 비해 복소수 곱셈이 아닌 실수 곱셈으로 대부분의 동작을 수행하는 장점을 가지고 있으나, SIMD 프로세서에서 구현하는 데는 벡터 데이터의 정렬 형태가 복잡하고 연산에 필요한 계수들을 저장할 메모리를 더 필요로 하는 단점이 있다. 실험 결과에 따르면 길이 1024인 FFT 연산을 SIMD 프로세서에서 수행하는데 있어서 Bruun 알고리즘은 Cooley-Tukey 알고리즘에 비해서 약 1.2배의 더 높은 처리성능을 보이지만, 약 4 배 더 큰 데이터 메모리를 필요로 한다. 따라서 데이터 메모리에 대한 제약이 큰 경우가 아니라면 SIMD 프로세서에서 Bruun 알고리즘이 FFT 연산에 적합하다.

Abstract ▼ AI-Helper

This paper discusses the implementation of Bruun's FFT on a SIMD processor. FFT is an algorithm used in digital signal processing area and its effective processing is important in the enhancement of signal processing performance. Bruun's FFT algorithm is one of fast Fourier transform algorithms based on recursive factorization. Compared to popular Cooley-Tukey algorithm, it is advantageous in computations because most of its operations are based on real number multiplications instead of complex ones. However it shows more complicated data alignment patterns and requires a larger memory for storing coefficient data in its implementation on a SIMD processor. According to our experiment result, in the processing of the FFT with 1024 complex input data on a SIMD processor, The Bruun's algorithm shows approximately 1.2 times higher throughput but uses approximately 4 times more memory (20 Kbyte) than the Cooley-Tukey algorithm. Therefore, in the case with loose constraints on silicon area, the Bruun's algorithm is proper for the processing of FFT on a SIMD processor.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 Bruun 알고리즘을 SIMD 구조를 갖는 프로세서에서 구현하기 위한 방법과 그 결과에 대해 살펴보았다. Bruun 알고리즘은 복잡한 복소수 곱셈 대신 간단한 실수 곱셈으로 FFT 동작을 처리하기 위해 고안된 알고리즘이다.
따라서 순차적으로 작업을 처리하는 구조에서 Bruun 알고리즘이 효율적이라고 알려져왔다^[12]. 본 논문에서는 Bruun 알고리즘을 SIMD 구조의 프로세서에 적용하는데 있어 주요한 제약요소인 높은 계수 생성과 데이터 정렬의 복잡도를 메모리 추가 사용으로 해결하고자 한다. 연산에 필요한 계수와 데이터 정렬 형태는 메모리에 사전 계산하여 저장할 수 있다.
DSP는 ASIC에 비하여 그 처리 성능이 상대적으로 낮기 때문에 DSP의 FFT 알고리즘 처리 성능을 높이는 연구가 계속되어 왔다. 본 논문은 벡터 형태의 연산에 적합한 SIMD 구조의 DSP를 이용해서 FFT 연산을 효과적으로 처리하는 방법에 대해 논한다.
이 논문에서는 이전의 연구들과는 달리 SIMD 구조의 프로세서에서 Bruun 알고리즘을 구현하여 성능을 높이는 방안에 대해 논한다. Bruun 알고리즘은 실수 곱셈이 주를 이루므로 Cooley-Tukey 알고리즘에 비해 곱셈 연산 횟수가 적은 특징을 나타낸다.

가설 설정

두 FFT 알고리즘의 구현 과정에서 i) 벡터 정렬 정보, ii) 조건부 연산 조건 정보, iii) 계수 정보의 저장에 데이터 메모리가 필요하다.
두 FFT 알고리즘을 SIMD 구조의 프로세서에서 구현하였을 때의 성능과 효율성을 비교하기 위해 과 같은 구조의 실험용 SIMD 프로세서를 기준 하드웨어로 가정하였다.

제안 방법

[13] FFT 프로그램은 에서 보인 SIMD 어셈블리 명령어와 스칼라 어셈블리 명령어를 이용하여 구현하였다.
본 논문은 다음과 같은 형태로 기술된다. Ⅱ.1에서는 Cooley-Tukey 알고리즘과 Bruun 알고리즘의 연산 특성을 비교한다. Ⅱ.
Bruun 알고리즘을 순차적으로 작업을 진행시키는 스칼라 프로세서에서 활용할 경우 감소된 복소수 곱셈의 수 때문에 Cooley-Tukey 알고리즘에 비해 성능이 향상되는 이점이 있으나, SIMD 구조를 갖는 프로세서에서 수행시킬 경우는 그 효율성이 입증되지 않았다. 본 논문에서는 SIMD 구조를 갖는 프로세서에서 Bruun 알고리즘을 수행하기 위한 프로그래밍 방법을 제안하고, 동일한 조건에서 Cooley-Tukey 알고리즘을 수행한 결과와 비교하였다. 결과를 살펴보면 1024개의 복소수 입력 데이터에 대한 FFT 연산에서 Bruun 알고리즘은 Cooley-Tukey 알고리즘에 비하여 약 4 배의 (약 20Kbyte)의 메모리를 필요로 하지만 처리 성능은 약 20% 높다.
이 논문에서는 성능 평가를 위해 동일한 구조의 실험용 SIMD 프로세서에서 Cooley-Tukey 알고리즘과 Bruun 알고리즘을 구현한 결과를 비교한다. 실험용 SIMD 프로세서는 C++ 언어 기반의 이산 사건 모사 라이브러리인 SSIM을 이용하여 구현하였다.^[13]
이 논문에서는 성능 평가를 위해 동일한 구조의 실험용 SIMD 프로세서에서 Cooley-Tukey 알고리즘과 Bruun 알고리즘을 구현한 결과를 비교한다. 실험용 SIMD 프로세서는 C++ 언어 기반의 이산 사건 모사 라이브러리인 SSIM을 이용하여 구현하였다.
이 장에서는 Bruun 알고리즘과 Cooley-Tukey 알고리즘을 동일한 조건의 SIMD 프로세서에서 수행한 결과를 서로 비교한다. 이를 위해 실험용 SIMD 프로세서를 이산 사건 시뮬레이션 라이브러리인 SSIM을 이용하여 모사하였다.^[13] FFT 프로그램은 <표 2>에서 보인 SIMD 어셈블리 명령어와 스칼라 어셈블리 명령어를 이용하여 구현하였다.

대상 데이터

SIMD 데이터패스는 SIMD 레지스터 파일, 32개의 연산장치로 구성되는 SIMD 연산장치, 벡터 조건 메모리, 벡터 데이터 정렬 장치, 벡터 정렬 메모리로 구성되어 있다. 위 구성 요소들은 병렬로 동작하며 파이프라인을 형성한다.
실험용 SIMD 프로세서는 SIMD 데이터패스, 스칼라 데이터패스, 제어장치, 명령어 메모리, 벡터 메모리, 스칼라 메모리 등 6가지 장치로 구성되어 있다. SIMD 데이터패스는 벡터 연산을 담당하며 스칼라 데이터패스는 병렬처리가 어려운 순차 연산과 프로그램의 흐름 제어 동작을 수행한다.

이론/모형

이 예에서 왼쪽 명령어는 SIMD 데이터 패스에서 실행되며 오른쪽 명령어는 스칼라 데이터패스에서 실행된다. 이 예제에서 r1과 r2는 Bruun 알고리즘에서 나타나는 2가지 데이터 정렬 형태가 저장된 벡터 정렬 메모리의 주소를 가리키는데 사용된다. r1은 <그림 2>의 Bruun 알고리즘 신호 흐름도에서 실선으로 표현된 벡터 데이터 정렬 형태를 가리키며, r2는 점선으로 표현된 벡터 데이터 정렬 형태를 나타내고 있다.
이와 같은 특징은 SIMD 구조의 프로세서를 구현할 때 하드웨어의 복잡도를 급격히 증가시킨다. 이런 문제를 해결하기 위해 본 논문에서는 Bruun 알고리즘의 연산에 사용되는 전체 필터 계수를 미리 계산하여 메모리에 저장하는 방법을 사용한다.

성능/효과

본 논문에서는 SIMD 구조를 갖는 프로세서에서 Bruun 알고리즘을 수행하기 위한 프로그래밍 방법을 제안하고, 동일한 조건에서 Cooley-Tukey 알고리즘을 수행한 결과와 비교하였다. 결과를 살펴보면 1024개의 복소수 입력 데이터에 대한 FFT 연산에서 Bruun 알고리즘은 Cooley-Tukey 알고리즘에 비하여 약 4 배의 (약 20Kbyte)의 메모리를 필요로 하지만 처리 성능은 약 20% 높다. 따라서 사용하려는 SIMD 프로세서가 충분한 메모리를 가진다면 Bruun 알고리즘을 적용하여 성능 향상을 도모할 수 있다.
이와 같은 결과는 <그림 9>에서 보인 것과 같이 Bruun 알고리즘에서 사용하는 실수 곱셈을 포함한 벡터 연산 명령어와 벡터 메모리 명령어의 수가 Cooley-Tukey 알고리즘에 비해 상대적으로 적기 때문이다. 두 FFT 알고리즘의 실행 사이클 수 차이는 FFT의 길이에 비례하여 증가하며, 길이 1024 인 FFT에서는 Bruun 알고리즘이 Cooley-Tukey 알고리즘에 비해약 1200 사이클 빨리 처리함 알 수 있다. 이 수치를 <그림 8>의 비율로 따져보면 약 20%의 성능 향상이 이루어진 것이다.
이 크기의 데이터 메모리는 지금의 반도체 기술을 활용하면 고속의 Onchip 메모리 형태로 구현하는 것이 가능하다. 따라서 SIMD 구조의 프로세서에서 하드웨어 추가없이 Bruun 알고리즘을 적용하여 FFT 처리 성능을 향상시킬 수 있다.
이와 같은 차이는 계수 저장에 필요한 메모리의 크기가 Cooley-Tukey 알고리즘의 경우 SIMD의 폭을 나타내는 W의 함수인 Wlog₂W로 표현되는데 반해, Bruun 알고리즘의 경우 FFT의 길이를 나타내는 N의 함수 Nlog₂N으로 표현되기 때문이다. 따라서 두 FFT 알고리즘이 필요로 하는 메모리 크기의 차이는 FFT의 길이가 증가함에 따라 점차 증가하며, 길이가 1024일 때 Bruun 알고리즘이 Cooley-Tukey 알고리즘에 비해 약 4배의 메모리를 더 필요로 하게 된다.
에서 보인 분석 결과와 과 에서 보인 실험 결과를 종합하면, 구현된 Bruun 알고리즘은 Cooley-Tukey 알고리즘에 비하여 데이터 메모리를 더 필요로 하지만 그 처리 성능은 더 높음을 알수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	디지털 신호처리 기술은 어디에 활용되는가?	디지털 신호처리 기술은 무선통신, 멀티미디어, 영상처리 등 많은 분야에 걸쳐 활용되고 있으며, 그 중요성은 점점 더 높아지고 있다. FFT (Fast Fourier transform)는 이산 신호의 주파수 분석을 위한 디지털 신호처리 알고리즘 가운데 하나로, 스펙트럼 분석기, OFDM 변복조기, MRI와 같은 전자기기에 사용된다.
	FFT란?	디지털 신호처리 기술은 무선통신, 멀티미디어, 영상처리 등 많은 분야에 걸쳐 활용되고 있으며, 그 중요성은 점점 더 높아지고 있다. FFT (Fast Fourier transform)는 이산 신호의 주파수 분석을 위한 디지털 신호처리 알고리즘 가운데 하나로, 스펙트럼 분석기, OFDM 변복조기, MRI와 같은 전자기기에 사용된다.
	Cooley-Tukey 알고리즘과 Bruun 알고리즘이 모두 한단에서 수행되는 연산들을 병렬 처리할 수 있는 이유는?	Cooley-Tukey 알고리즘과 Bruun 알고리즘 모두 한단에서 수행되는 연산들을 병렬 처리할 수 있다. 이는 동일한 단에서 수행되는 연산에서 입력으로 사용하는 모든 데이터들 사이에는 상호 의존성이 없기 때문이다. 그러나 한 단이 연산을 수행하기 위해서는 이전 단의 연산 결과가 입력으로 필요하므로 FFT 연산의 단들 사이에는 종속성이 존재한다.

참고문헌 (16)

James W. Cooley and John W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series, Mathematics of computation 19.90, pp.297-301, 1965.

상세보기
S. C. Chan and K. L. Ho, On Indexing the Prime Factor Fast Fourier Transform Algorithm, IEEE Transactions on Circuits and Systems, Vol. 38, No, 8, pp.951-953, 1991.

상세보기
Georg Bruun, z-Transform DFT Filters and FFT's, IEEE Transactions on Acoustics, Speech, And Signal Processing, Vol. 26, NO. 1, February, 1978.

상세보기
Rader, C.M., Discrete Fourier transforms when the number of data samples is prime, IEEE, Proceedings letters, No. 56, pp.1107-1108, 1968.
Wang Xu, Zhang Yan and Ding Shunying, A High Performance FFT Library with Single Instruction Multiple Data(SIMD) Architecture, IEEE, International Conference on ICECC, pp.630-633, September, 2011.
Ting Chen, Hengzhu Liu and Botao Zhang, A scalable, fixed-shuffling, parallel FFT butterfly processing architecture for SDR environment, IEICE Electronics Express, Vol.11, No.2, pp.1-9, 2014.
T. Chen, X. Pan, H. Liu and T. Wu, Rapid Prototype and Implementation of a High-Throughput and Flexible FFT ASIP Based on LISA 2.0, IEEE, 15th International Symposium on ISQED, 2014.
F. Yu, R. GE and Z. Wang, Efficient Utilization of Vector Registers to Improve FFT Performance on SIMD Microprocessors, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E960A, No.7, July, 2013.
Mittal Shashank. Efficient and High-Speed FFT Architectures for Software Defined Radio, Master Thesis. International Institute of Information Technology Hyderabad, INDIA, 2009.
Yuhang Wu, New FFT Structures Based on the Bruun Algorithm, IEEE Transactions On Acoustics, Speech. And Signal Processing, Vol. 38. No. 1, pp.188-191, January, 1990.

상세보기
Harold S. Stone, Parallel processing with the perfect shuffle, IEEE Transactions on Computers, Vol. 20, No. 2 pp.153-161, 1971.
Mittal, S., Area Efficient High Speed Architecture of Bruun's FFT for Software Defined Radio, IEEE, GLOBECOM '07, Global Telecommunications Conference, 2007.
C. Antonio, SSim - A Simple Discrete-Event Simulation Library(2012), Retrieved Febuary, 2012, from http://www.inf.usi.ch/carzaniga/ssim/index.html
Sehoon Yoo, A Reconfigurable Parallel Processor for Efficient Processing of Mobile Multimedia, Journal of the Institute of Electronics Engineers of Korea SD, Vol. 44, No. 10, pp.23-32, 2007.
Kyeong-Seob Kim, Yun-Sub Lee, Byung-Cheol Yu, Control Unit Design and Implementation for SIMD Programmable Unified Shader, Journal of the Institute of Electronics Engineers of Korea SD, Vol. 48, No. 7, pp.37-47, 2011.
Hillery C. Hunter, A new look at exploiting data parallelism in embedded systems, CASES '03 Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, pp.159-169, 2003.

표제어: 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

연합인증