[논문]데이터 재구성 기법을 이용한 고성능 FFT

박능수; 최영호

doi:10.3745/kipsta.2005.12a.3.215

문제 정의

2절 에서는 동적 데이터 재구성 기법을 적용한 FFT 트리에 대하여 논하였다. 그리고 43절에서 동적 데이터 재구성 기법을 사용한 최적화 FFT 트리를 찾는 탐색 알고리즘에 관하여 설명하였다.
하지만, 큰 규모의 DFT 계산에서는 데이터 재구성을 포함한 트리에서 신속한 처리를 할 수가 있다. 따라서 본 탐색 알고리즘은 이러한 데이터 재구성을 고려한 최적 실행시간을 가지는 트리를 제시하게 된다. (그림 6)은 이러한 동적 데이터 재구성과 dynamic programming을 이용한 탐색 알고리즘을 간략하게 나타낸 것이다.
본 논문에서 캐시를 기반으로 하는 메모리 계층구조를 가진 플랫폼 상에서 인수분해된 트리구조 DFT의 성능을 최적 화 시킬 수 있는 효과적인 방법을 개발하였다. 제안된 방법은 캐시 성능을 향상시키기 위해 stride를 가지는 계산 단계 사이에 데이터를 동적으로 데이터 배열을 재구성하는 방법으로 이를 DDL 방법이라 한다.
따라서 트리구조 FFT에서 어느 시점에 데이터를 재배열하여 데이터 액세스 에 변화를 줄지 결정하는 것은 전체적인 성능 향상을 이루 기 위하여 중요하다. 본 논문에서는 데이터 재구성을 포함 하는 최적의 트리구조를 찾기 위하여 dynamic programming 기법을 이용한 탐색 알고리즘을 개발하였다. 성능 향 상을 확인하기 위하여 제시된 DDL 방법과 탐색 알고리즘을 기존의 FFT 알고리즘에 적용하여 FFT 패키지를 개발하여 Alpha 21264, Pentium 4, Athlon™ 64, UltraSPARC U[에서 실험하였다.
따라서 제 시한 알고리즘은 DFT] 크기뿐만 아니라 노드 계산의 데이터 액세스 stride도 고려하기 때문에 그 탐색공간은 기존의 것에 비하여 더 크게 되므로 전수 탐색 (exhaustive search) 으로 찾는 것은 비현실적이다. 본 논문에서는 이를 효과적으로 찾기 위하여 dynamic programming기법을 이용하고자 한다. dynamic programming 기법에서 트리는 bottom-up 방법으로 구현되고, 그 복잡도는 0(^2)가 된다.
본 논문에서는 캐시의 효율을 높이기 위하여 계산 중간에 메모리 안에 데이터를 동적으로 데 구성하는 동적 데이터 재배열(Dynamic Data Layout: DDL) 방법을 제안한다. 일정한 거리를 가지는 비연속적인 데이터 액세스를 연속적인 데이터 액세스로 전환하는 데이터 재구성을 함으로서 응용 프 로그램의 공간적 집약성(spatial locality)을 증가시켜 캐시 적중 실패를 줄일 수 있다.

가설 설정

인수 분해된 DFT의 stride 액세스가 캐시 성능에 미치는 영향을 분석을 하기 위해 먼저 2-level 메모리 계층 구조를 생각하자. C를 캐시 크기 그리고 B를 캐시 라인(cache line) 크기라 가정하자. 최신 컴퓨터가 direct-mapped 또는 작eset-associative 캐시를 가지지만, 동작 분석을 간략하게 하기 위하여 direct-mapped 캐시라 가정흐!.
(그림 3)에서 리프 노드의 stride가 커서 str讯e><N\>C가 되는 경우를 생각해보자. 먼저 캐시 크기 C = 32포인트 이고 캐시 라인 B = 4 포인트인 direct-mapped 캐시를 가정하자. 만약 _站 = 4이고 ?由=16라 가정하면, -point DFT의 데이터가 (그림 4)에서처럼 캐시에 사상하게 된다.
(그림 5)를 보면, 16*16 데이터 포 인트들은 행 중심 순서(row-major order)에 따라서 배열이 된다. 효과적인 설명을 위하여, 캐시의 크기는 64 포인트이 고 캐시 라인의 크기는 4인 direct-mapped 캐시라 가정을 하자. (그림 5) (a)에서처럼 stride가 16인 16-point DFT를 생각해 보자.

제안 방법

, , ctddl[s[nl], s[2]]"는 2 nlx2 脸로 인 수분해 된 FFT로 DDL 방법의 Cooley-Tukey 알고리즘이다. Athlon™ 64 플랫폼에서는 FFT 크기가 L2 캐시보다 작은 경우에는 데이터 재구성 오버헤드가 상대적으로 커서 기존의 SDL 방식 트리보다 계산 성능이 낮아서 제시된 탐색 알고리즘은 자동적으로 FFT_SDL 트리를 최적화 트리로 선택하도록 고안하였다. 하지만, FFT 크기가 커져서 L2 캐시 크기보다 커지면, 제시한 탐색 알고리즘은 자동적으로 데이터 재구성을 하는 FFT_DDL 트리를 최적화 트리로 결정하 게 된다.
본 실험에서 모든 DFT의 데이터 포인트는 double-precision의 복소수로 나타낸다. DDL 방법을 이용한 성능 향상을 나타내기 위하여 FFTW와 FFT_SDL의 성능 과 비교하였다. 제시된 DDL 방법이 플랫폼에 상관없이 유 용함을 보이기 위하여 최신의 다양한 플랫폼에서 실험을 진행하였다.
제시된 DDL 방법을 사용하여 캐시 적중 실패를 줄임으로서 전체적인 성능향상을 얻을 수가 있다. 또한 트리 구조 FFT 계산 방법에서 FFT 크기 와 데이터 stride 액세스를 기초로 하여 가능한 모든 인수분 해 트리 중에서 최소 실행시간을 가지는 최적의 인수 분해 트리를 찾아내는 탐색 알고리즘을 개발하였다. 제시된 DDL 방법은 최적화 방법으로 신호 변환 패키지의 상위 알고리즘 레벨에 적용될 수 있다.
본 논문에서 제시된 DDL 방법을 사용하여 성능 향상됨 을 보이기 위해, 카네기멜론 대학교(CMU)에서 개발된 FFT 패키지를 사용하였고, 이를 FFT-SDLD으로 명하였다. 이것은 [3]에 제시된 FFT 패키지를 기초로 하였다.
제시된 DDL 방법은 최적화 방법으로 신호 변환 패키지의 상위 알고리즘 레벨에 적용될 수 있다. 본 논문에서는, 제시된 방법으로 계 산 성능이 향상됨을 보이기 위하여 FFT 패키지에 적용시켜 다. 본 논문에서 제시한 방법의 범용성을 확인하기 위하여 Pentium 4, Alpha 21264, Athlon™ 64, UltraSPARC II 등에서 실험하였다.
본 논문에서는 데이터 재구성을 포함 하는 최적의 트리구조를 찾기 위하여 dynamic programming 기법을 이용한 탐색 알고리즘을 개발하였다. 성능 향 상을 확인하기 위하여 제시된 DDL 방법과 탐색 알고리즘을 기존의 FFT 알고리즘에 적용하여 FFT 패키지를 개발하여 Alpha 21264, Pentium 4, Athlon™ 64, UltraSPARC U[에서 실험하였다. 실험을 통하여 새로 구현된 FFT 패키지로 최대 3.
시간 측정은 wall clock방법으로 clockO 함수를 사용하였다. 실험에서 정확한 실행 시간을 얻기 위 하여, 전체 실행시간이 1초 이상 될 때까지 계산을 반복 수행하였다. 전체 실행시간에서 loop overhead 부분은 빼고 남 은 시간의 평균을 각 계산의 실행시간으로 하였다.
인수 분해된 DFT의 stride 액세스가 캐시 성능에 미치는 영향을 분석을 하기 위해 먼저 2-level 메모리 계층 구조를 생각하자. C를 캐시 크기 그리고 B를 캐시 라인(cache line) 크기라 가정하자.
인수 분해된 DFT의 스트라이드 데이터 액세스가 캐시 성능에 미치는 영향을 이해하기 위한 간략한 분석을 하였다. 먼저, 식 (1)와 같이 JV-point DFT를 Cooley-Tukey 알고리즘을 이용하여 N、><N%로 분해하자.
DDL 방법을 이용한 성능 향상을 나타내기 위하여 FFTW와 FFT_SDL의 성능 과 비교하였다. 제시된 DDL 방법이 플랫폼에 상관없이 유 용함을 보이기 위하여 최신의 다양한 플랫폼에서 실험을 진행하였다.<표 1>과<표 2>는 실험에 사용된 플랫폼에 대한 아키텍처 구성 요소, 컴파일러, 그리고 최적화 옵션 등을 요약한 것이다.

대상 데이터

본 논문에서는, 제시된 방법으로 계 산 성능이 향상됨을 보이기 위하여 FFT 패키지에 적용시켜 다. 본 논문에서 제시한 방법의 범용성을 확인하기 위하여 Pentium 4, Alpha 21264, Athlon™ 64, UltraSPARC II 등에서 실험하였다. 실험 결과에 나타난 것처럼, 제시된 FFT_ DDL 방법은 FFTW와 FFT_SDL과 비교하여 최대 3.

이론/모형

그러므로 리프 노드 계산에 필요한 데이터가 캐시 안에 다 올라올 수 있어, 그 계산 성능 향상에 도움을 준다. MIT 의 FFTW[4]와 CMU의 FFT[6] 패키지가 divide-and-conquer 특성을 이용하였다. 이러한 알고리즘은 캐시의 크기만 을 고려하고 캐시 구조의 특징을 고려하지 않았다.
인수 분해된 DFT의 스트라이드 데이터 액세스가 캐시 성능에 미치는 영향을 이해하기 위한 간략한 분석을 하였다. 먼저, 식 (1)와 같이 JV-point DFT를 Cooley-Tukey 알고리즘을 이용하여 N、><N%로 분해하자. 이때 계산은 먼저 M 개의 N广point DFT를 계산한다.
우리는 FFT_ SDL 패키지에 DDL 방법을 적용하였고 이를 FFT_DDL이 라 명하였다. 본 실험에서 모든 DFT의 데이터 포인트는 double-precision의 복소수로 나타낸다. DDL 방법을 이용한 성능 향상을 나타내기 위하여 FFTW와 FFT_SDL의 성능 과 비교하였다.
<표 1>과<표 2>는 실험에 사용된 플랫폼에 대한 아키텍처 구성 요소, 컴파일러, 그리고 최적화 옵션 등을 요약한 것이다. 시간 측정은 wall clock방법으로 clockO 함수를 사용하였다. 실험에서 정확한 실행 시간을 얻기 위 하여, 전체 실행시간이 1초 이상 될 때까지 계산을 반복 수행하였다.
다음에 twiddle 곱셈을 한 후에, M개의 stride가 1인 Ar2-point DFT를 계산한다. 이러한 Cooley-Tukey 알고리즘을 자식 노드에 반복적으로 적 용함으로써 divide-and-conquer 방법의 트리구조 계산을 하 게 된다. 이러한 트리구조 계산에서는 리프 노드 크기가 점 점 작아져서 캐시 크기보다 작게 되고 (그림 3)에서와 같이 리프 노드 계산에 stride 액세스가 포함된다.
DDL방법의 효과를 설명하기 위하여, 256-point DFT의 간단한 예를 보자. 이를 Cooley-Tukey 알고리즘을 사용하여 16시6으로 분해하였다. (그림 5)를 보면, 16*16 데이터 포 인트들은 행 중심 순서(row-major order)에 따라서 배열이 된다.

성능/효과

FFTW와의 비교에서도 유사한 결과를 얻을 수 있었다. FFTW와 비교하여 FFT_DDL이 최대 2배 정도의 성능 향상을 얻을 수 있었다.
따라서 FFT 크기가 L1 캐시 크기와 L2 캐시 크기 사이에서는 상대적으로 성능 향상이 이전에 비하여 크지는 않았다. 그러나 L2 캐시 보다 큰 경우에는 FFT_DDL이 FFT_SDL 보다 최대 3.37배 그리고 FFTW와 비교하여 최대 2.23배 까지 성능향상을 얻을 수 있었다. (그림 10)은 UltraSPARC HI에서 의 DDL 방법에 이용하여 L2 보다 큰 경우에 성능 향상을 얻을 수 있음을 보여주고 있다.
기존의 탐색 알고리즘은 DFT의 크기만 을 고려하였고 그 탐색 공간은 0(5«/w 溢)이다. 따라서 제 시한 알고리즘은 DFT] 크기뿐만 아니라 노드 계산의 데이터 액세스 stride도 고려하기 때문에 그 탐색공간은 기존의 것에 비하여 더 크게 되므로 전수 탐색 (exhaustive search) 으로 찾는 것은 비현실적이다. 본 논문에서는 이를 효과적으로 찾기 위하여 dynamic programming기법을 이용하고자 한다.
일정한 거리를 가지는 비연속적인 데이터 액세스를 연속적인 데이터 액세스로 전환하는 데이터 재구성을 함으로서 응용 프 로그램의 공간적 집약성(spatial locality)을 증가시켜 캐시 적중 실패를 줄일 수 있다. 따라서 트리구조의 FFT 계산 단계 중간에 이러한 데이터 재구성을 적용하여 프로세서와 메모리 사이의 캐시를 효율적으로 이용하여 전체적인 성능 향상을 얻을 수 있다. 하지만 데이터 재구성 자체는 메모리 안에 데이터를 처리하는 연산이므로 하나의 연산 오버헤드 가된다.
본 논문에서 제시한 방법의 범용성을 확인하기 위하여 Pentium 4, Alpha 21264, Athlon™ 64, UltraSPARC II 등에서 실험하였다. 실험 결과에 나타난 것처럼, 제시된 FFT_ DDL 방법은 FFTW와 FFT_SDL과 비교하여 최대 3.37배의 상당한 성능 향상을 얻을 수 있었다. 또한 이러한 동적 데이터 배열 방법을 이용하여 선형대수나 다른 신호변환 알고 리즘에도 적용을 시킬 수 있음을 다른 논문[12, 13]을 통하여 보였다.
성능 향 상을 확인하기 위하여 제시된 DDL 방법과 탐색 알고리즘을 기존의 FFT 알고리즘에 적용하여 FFT 패키지를 개발하여 Alpha 21264, Pentium 4, Athlon™ 64, UltraSPARC U[에서 실험하였다. 실험을 통하여 새로 구현된 FFT 패키지로 최대 3.37배의 성능 향상을 얻을 수 있었다.
FFT 크기가 2 13보다 크고 2 确보다 작은 경우, 필요한 모든 데이터 포인터들은 L2 캐시에는 있을 수 있으니 L1 캐시에는 그 일부만이 있게 된다. 이런 경우에 제안되 DDL 방법은 L1 캐시 적중 실패의 수를 줄여 약간의 성능 향상을 얻을 수 있었다. 그러나 FFT] 크기가 L2 캐시의 크기를 넘는 경우, FFT_DDLe FFT_SDL과 비교하여 최대 2.
또한 DFT 계산 특징과 현대 시스템의 메모리 구조 특성을 고려하여 계산 성능을 향상시키고 자 노력을 해오고 있다[4, 5, 11], 최근에는 카네기멜론대학 교(CMU)와 MIT에 의해 FFT를 트리 구조로 표현하여 구 현된 소프트웨어 패키지들이 개발 되었다[4, 6], 이러한 트리 구조 FFT는 트리의 말단 노드 (leaf node) 계산을 조건 분 기문(conditional branch)-S- 사용하지 않은 직선 코드(straight line unrolled code)로 이루어져 상당히 높은 최적화를 얻었 다. 전체적으로 작은 크기의 FFT에서는 좋은 성능 향상을 얻어 내었다. 하지만, FFT의 크기가 켜져 갈수록 계산 성능 이 급격히 떨어졌다.
제안된 방법은 캐시 성능을 향상시키기 위해 stride를 가지는 계산 단계 사이에 데이터를 동적으로 데이터 배열을 재구성하는 방법으로 이를 DDL 방법이라 한다. 제시된 DDL 방법을 사용하여 캐시 적중 실패를 줄임으로서 전체적인 성능향상을 얻을 수가 있다. 또한 트리 구조 FFT 계산 방법에서 FFT 크기 와 데이터 stride 액세스를 기초로 하여 가능한 모든 인수분 해 트리 중에서 최소 실행시간을 가지는 최적의 인수 분해 트리를 찾아내는 탐색 알고리즘을 개발하였다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

데이터 재구성 기법을 이용한 고성능 FFT
High-Performance FFT Using Data Reorganization 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

데이터 재구성 기법을 이용한 고성능 FFT High-Performance FFT Using Data Reorganization 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

박능수 (10)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

데이터 재구성 기법을 이용한 고성능 FFT
High-Performance FFT Using Data Reorganization 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper