재구성가능 수퍼컴퓨팅 플랫폼을 이용한 스미스-워터맨 알고리즘의 구현

FPGA

자료제공 : 알테라www.altera.comXtremeData는 FPGA 기술의 급속한 발전과 하이퍼트랜스포트(HyperTransport) 인터커넥션의 높은 성능을 활용할 수 있도록 XD1000이라고 하는 혁신적인 재구성가능 수퍼컴퓨팅 플랫폼을 개발 중이다. 이 글에서는 이 플랫폼으로 DNA 및 단백질 서열을 위한 스미스-워터맨(Smith-Waterman) 알고리즘을 구현하는 것에 대해 살펴본다. 주요 항목으로서 FPGA 자원 활용을 대폭적으로 감소시키고 더 높은 정도의 병렬처리를 가능하게 하는 멀티스테이지 프로세싱 엘리먼트(PE) 디자인, 전체적인 PE 파이프라인 사이클 시간을 최소화하기 위해 중요한 특징으로서 불규칙적 스테이지 지연시간의 파이프라인 제어 메커니즘, 온칩 SRAM 활용을 대폭적으로 감소시키는 압축적 치환 행렬 저장 구조에 대해 설명한다. 마지막으로는 66.7MHz로 실행되며 25.6GCUPS 피크 성능을 달성할 수 있는 384개 PE 시스톨릭 어레이를 구현하는 것에 대해 살펴본다. 2.2GHz AMD 옵테론 호스트 프로세서와 비교해서 이 FPGA 코프로세서는 각각 185배 및 250배의 가속화를 달성한다.XD1000은 XtremeData에서 개발한 혁신적인 재구성가능 수퍼컴퓨팅 플랫폼이다[20]. FPGA 기술의 급속한 발전과 메인 프로세서와 FPGA 코프로세서 사이에 효율적인 링크를 제공하는 하이퍼트랜스포트 인터커넥션의 높은 성능을 활용한 XD1000은 다양한 알고리즘을 위해서 이상적이고 경제성 뛰어난 가속화 알고리즘을 제공한다.그림 1에서 보듯이 XD1000은 듀얼 옵테론 기반 시스템으로 첨단의 알테라 Stratix II FPGA를 통합했다. 이 FPGA 코프로세서 모듈을 곧바로 옵테론 940 소켓에 삽입할 수 있으며 이 마더보드의 기존 CPU 인프라를 이용해서 FPGA 기반 재구성가능 컴퓨팅 코프로세서 기능을 위한 포괄적인 환경을 구축할 수 있다. 이 FPGA 코프로세서가 마더보드 상의 CPU의 하이퍼트랜스포트 버스 및 DIMM 슬롯으로 곧바로 연결될 뿐만 아니라 CPU를 위한 기존의 전원장치 및 히트 싱크 솔루션을 이용한다. XD1000 코프로세서와 옵테론 CPU 사이의 고대역폭 저지연 하이퍼트랜스포트 링크는 이전에 기존의 PIC 버스 기반 솔루션을 이용해서 불가능했던 X86 애플리케이션의 고도로 결합적인 FPGA 가속화를 가능하게 한다[9].이 글에서는 XD1000 플랫폼을 이용해서 DNA 및 단백질 서열을 위한 스미스-워터맨 알고리즘을 구현하는 것에 대해 설명한다. 우리는 FPGA로부터 최대의 성능을 끌어내기 위해서 멀티스테이지 PE 디자인을 도입하고 있는데 이는 FPGA 자원 활용을 대폭적으로 감소시키며 그러므로 더 높은 병렬처리를 가능하게 한다.뿐만 아니라 이 디자인은 불규칙적 스테이지 지연시간의 파이프라인 제어 메커니즘을 특징으로 한다. 이 점은 전체적인 PE 파이프라인 사이클 시간을 최소화하기 위해서 중요하다. 뿐만 아니라 온칩 SRAM 활용을 현저히 감소시키는 압축적 치환 행렬 저장 구조에 대해 설명한다. 이들 기법을 이용해서 66.7MHz로 작동하며 25.6 GCUPS의 피크 성능을 달성할 수 있는 384개 PE 시스톨릭 PE 어레이를 구현하고 있다. 2.20GHz AMD 옵테론 호스트 프로세서와 비교해서 이 FPGA가 각기 185배 및 250배의 가속화를 달성할 수 있다.스미스-워터맨 알고리즘과 시스톨릭 PE 어레이스미스-워터맨(Smith-Waterman) 알고리즘은 2개 DNA 또는 단백질 서열 간에 유사한 구역을 판단하기 위해 국소 서열 정렬을 수행하기 위한 널리 알려진 동적 프로그래밍 알고리즘이다. 이 알고리즘은 1981년에 T. Smith 및 M. Waterman에 의해서 제안되었다. 지금도 여전히 이 알고리즘이 많은 애플리케이션의 코어 알고리즘으로 이용되고 있다[18].이 알고리즘은 2단계로 이루어진다.1. 유사성 행렬 점수를 계산한다.2. 동적 프로그래밍 기법에 따라서 유사성 행렬을 역추적해서 최적의 정렬을 탐색한다. 이 알고리즘은 앞 단계에서 전체 계산 시간의 상당 부분을 소비한다. 스미스-워터맨 알고리즘은 다음과 같이 정의할 수 있다.2개 서열 S 및 T의 경우에, S의 길이는 n이므로 |S|=n이고, T의 길이는 m이므로 |T|=m이다. V(i,j)는 2개 하위서열 S[1]…[i]와 T[1]…[j]의 최적 정렬 점수이고, V(i,j)의 계산은 공식 1 및 공식 2로 정의할 수 있다.초기화: { V(i,0)=0, 0 ≤ i ≤ n V(0,j)=0, 0 ≤ j ≤ m (공식 1)회귀 관계식: 0V(i,j)=max{ V(i-1,j-1)+σ(S[i],T[j]), 1≤i≤n, 1≤j≤n V(i-1,j)+σ(S[i],-) V(i,j-1)+σ(-,T[j]) (공식 2)이들 공식에서 ‘-’는 널 문자 또는 공백을 의미하며, V(i,0)은 S의 각 문자를 T의 공백과 비교한 결과를 나타내고, V(0,j)는 T의 각 문자를 S의 공백과 비교한 결과를 나타내며, (S[i],T[j])는 치환 행렬의 값이다.유사성 행렬을 계산할 때 특정한 행렬 요소의 점수 V(i,j)는 언제나 다음의 다른 3개 요소의 점수에 따라 달라진다.■ 왼쪽 상단 인접 요소 V(i-1,j-1)■ 왼쪽 인접 요소 V(i,j-1)■ 상단 인접 요소 V(i-1,j)그러므로 유사성 행렬의 계산 순서는 그림 2와 같다. 화살표가 가리키는 방향에서 알 수 있듯이 상단 왼쪽 요소에서 시작해서 하단 오른쪽 요소로 이어진다. 유사성 행렬 계산 프로세스를 살펴봄으로써 매 클록 사이클에 역사선 상에 동일한 숫자로 표시된 모든 요소를 동시에 계산할 수 있다는 것을 깨달았다. 예를 들어 첫 번째 사이클에는 (1)로 표시된 한 요소만 계산할 수 있다. 두 번째 사이클에는 (2)로 표시된 2개 요소를 계산할 수 있다. 세 번째 사이클에는 (3)으로 표시된 3개 요소를 계산할 수 있는 식이다. 그러므로 이러한 특성은 이 알고리즘이 병렬처리의 가능성이 매우 높다는 것을 의미한다.1982년에는 O. Gotoh가 2개의 실제 생명정보 서열 간의 유사성의 정도를 추가적으로 기술하기 위해서 스미스-워터맨 알고리즘에 아핀 갭(affine gap) 모델을 도입했다[4]. 아핀 갭 모델은 예상되는 모델을 충족함에 있어서 정렬이 더 압축적이 되도록 하기 위해서 갭을 이용해서 삽입이나 삭제에 대해 보상한다.보통 이 갭이 서열에서 연속적 널 문자열이며 되도록 길어야 한다. 아핀 갭 모델에서는 첫 번째 갭의 패널티 점수(또는 비용)를 gap_open이라 하고, 그 이후의 갭의 비용을 gap_extension이라고 한다. 아핀 갭 모델에서는 유사성 행렬을 계산하기 위한 공식들을 다음과 같이 나타낼 수 있다.초기화: { V(i,0)=E(i,0)=0, 0 ≤ i ≤ n V(0,j)=F(0,j)=0, 0 ≤ j ≤ m (공식 3)회귀 관계식: 0V(i,j)=max{ E(i,j) ,1≤i≤n, 1≤j≤m F(i,j) V(i-1,j-1)+σ(S[i],T[j]) (공식 4)E(i,j)=max{ V(i,j-1)-α, 1≤i≤n, 1≤j≤m E(i.j-1)-β (공식 5)F(i,j)=max{ V(i-1,j)-α, 1≤i≤n, 1≤j≤m F(i-1,j)-β (공식 6)이들 공식에서 α는 gap_open을 의미하며, β는gap_extension을 의미한다. E(i,j) 및 F(i,j)는 새로운 갭을 열거나 또는 기존 공백을 계속해서 확대하는 2개 항목의 최대값이다.시스톨릭 어레이는 H. T. Kung 및 C. E. Leiserson이 자신들의 논문에서 처음으로 소개했으며[10][11], 행렬 곱셈이나 LU 분해를 계산하는 데 있어서 매우 효율적인 것으로 입증되었다. 이후의 연구에서는 또한 동적 프로그래밍 알고리즘이 병렬처리의 가능성이 높기 때문에 시스톨릭 어레이로 매우 잘 맵핑되는 것으로 밝혀졌다[12].1985년에는 R. J. Lipton 및 D. P. Lopresti가 nMOS 프로토타입 칩을 구현함으로써 DNA 서열의 전역 정렬에 이용되는 일반적인 동적 프로그래밍 알고리즘인 편집 거리(edit distance) 알고리즘을 시스톨릭 어레이로 맵핑했다[13]. 이 프로토타입의 초기 결과가 상보형 미니컴퓨터보다 수백 배에서 수천 배 더 빠르게 실행되었다.1987년에는 D. P. Lopresti가 핵산 서열을 비교하기 위한 최초의 시스톨릭 어레이 시스템으로서 P-NAC이라고 하는 시스템을 구축했다[14]. 이러한 연구들을 토대로 해서 캘리포니아 공과대학의 BISP[3], 노스캐롤라이나대학의 BioSCAN[21], 브라운대학의 B-SYS 및 Splash/Splash-2[8][6][7], 캘리포니아 산타크루즈 대학의 Kestrel[5] 등의 다수의 시스톨릭 어레이 시스템이 개발되었다.최근에는 생명정보학 및 FPGA 기술이 빠른 속도로 발전함에 따라서 상용 및 연구 목적으로 TimeLogic DeCypher[19], CLC Bioinformatics Cube[2], NTU 대학의 유전자 서열 데이터베이스 스캐닝을 위한 고도로 최적화된 프로세서(Hyper Customized Processors for Bio-Seqence Database Scanning)[16][17] 등의 새로운 시스템들이 개발되었다.이러한 연구들을 토대로 이 글에서는 XD1000이라고 하는 혁신적인 재구성가능 수퍼컴퓨팅 플랫폼으로 DNA 및 단백질 서열을 위한 스미스-워터맨 알고리즘의 구현에 대해 살펴본다. 이들 연구와 비교해서 애플리케이션의 관점에서 우리 디자인은 서열 길이를 64KBp로 확장하므로 다양한 애플리케이션의 요구를 충족할 수 있을 것이다. DNA 서열을 위한 스미스-워터맨 알고리즘 디자인의 경우에는 4개의 소프트웨어 프로그래머블 파라미터가 하드웨어 구현을 선형 및 아핀 갭 모델 알고리즘을 비롯한 기존의 소프트웨어 프로그램과 호환이 가능하도록 한다. 단백질 서열을 위한 스미스-워터맨 알고리즘 디자인 역시 치환 행렬이 재구성가능하며 사용자가 각기 다른 진화 모델 중에서 선택하거나 아니면 자체적인 진화 모델을 개발할 수 있다. 하드웨어 아키텍처의 측면에서는 새로운 멀티스테이지 PE 디자인 및 압축적 치환 행렬 저장 기법을 도입하고 있는데 이들 기법은 FPGA 자원 활용을 대폭적으로 감소시키고 그럼으로써 FPGA로부터 더 높은 병렬처리를 가능하도록 한다.이 디자인에서는 그림 3에서 보듯이 시스톨릭 PE 어레이를 점수 행렬의 역사선으로 맵핑한다. 예를 들어 다섯 번째 클록 사이클에는 PE 어레이가 (5)로 표시된 요소들을 계산하도록 맵핑되고, 다음 사이클에는 PE 어레이가 (6)으로 표시된 요소들을 계산하도록 맵핑된다. 그러면 지금부터는 PE를 구현하는 방법에 대해 자세히 살펴보도록 하자.하드웨어 자원의 제한 때문에 FPGA로 제한적인 숫자의 PE만을 구현할 수 있다. 그러므로 유사성 행렬의 계산을 위해서는 행렬을 하위 행렬로 분할해야 한다. 각각의 실행 시에 PE 어레이가 하나의 하위 행렬을 계산하고 중간 결과를 다음 실행을 위해 메모리에 저장한다.그림 4에서 보듯이 시스톨릭 PE 어레이는 다수의 동일한 연결 PE로 이루어진다. 계산을 시작하기 위해서는 서열 S를 Move_in_S 신호의 제어 하에 어레이로 쉬프트인해야 한다. 각 PE에 대한 init_in 신호가 이 PE가 계산에 합류할지 말지를 결정한다. 서열 T는 PE 어레이로 입력될 때 init_in와 동기이다. 다중 반복 계산이 필요할 때는 mid_in을 이용해서 임시 중간 데이터를 PE 어레이로 피드백한다.이 디자인은 서열 S의 쉬프트인 방향이 서열 T의 것과 반대가 되도록 구축되었다. 이 구성은 서열 S가 PE 어레이에 원래의 서열대로 저장되도록 한다. 다시 말해서 서열의 끝이 언제나 마지막 PE에 저장된다. 이 기법은 데이터를 준비하는 소프트웨어 프로세스를 가능하게 할 뿐만 아니라 다중 반복이 필요할 때 점수 행렬의 계산이 연속적이도록 한다.스미스-워터맨 알고리즘 PE 디자인공식 3, 공식 4, 공식 5, 공식 6은 간단한 PE 배선도(그림 5)를 제안하는 것으로서[16][17], 각각의 DFF(D-type 플립플롭)의 기능을 다음과 같이 설명할 수 있다.■ S-Out 및 T-out DFF는 S[i] 및 T[j]를 저장한다.■ E-out DFF는 E(i,j)를 저장하고 다음 클록 사이클에 동일한 PE가 이를 이용한다. 이의 입력은 동일한 PE에서 이전 클록 사이클에 생성되었던 것이며, 상단 인접 요소의 값을 나타낸다.■ F-out DFF는 F(i,j)를 저장하는 데 이용되며, 다음 PE가 이를 이용한다. 이의 입력은 이전 PE로부터 오며 왼쪽 인접 요소의 값을 나타낸다.■ V-diag DFF의 입력은 이전 PE로부터 오며 PE가 이용하기에 앞서 한 사이클에 대해서 기록된다. 그러므로 왼쪽 상단 인접 요소의 값을 나타낸다.■ V-out DFF는 V(i,j)를 저장하는 데 이용된다.■ Max_out DFF는 유사성 행렬의 최대값을 저장하는 데 이용된다. 이는 3개 입력을 갖는다. - 이전 PE로부터의 최대값 - 현재 PE로부터의 V(i,j) - 자신에 저장된 최대값하드웨어 구현에 앞서 이 PE 디자인에 이용되는 FPGA 자원을 계산해야 한다. 최대 서열 길이와 치환 행렬의 최대값에 따라서 PE 데이터 폭을 결정해야 한다. 예를 들어서 이 길이가 64KBp이고 최대값이 11이라면 PE 데이터 폭이 최소한 20비트여야 하므로 220>64K*11이다. 이 간단한 PE 디자인은 5개의 덧셈/뺄셈 연산 및 6개의 max 연산을 포함한다. 각각의 max 연산은 뺄셈 및 2:1 다중화 연산으로 이루어지므로 PE 전체로는 11개 덧셈/뺄셈 및 6개 2:1 다중화 연산이다. 데이터 폭을 20비트로 설정하면 PE가 약 340개 적응식 룩업 테이블(ALUT)을 필요로 한다.이 연구에서 FPGA 코프로세서로 이용된 알테라 Stratix II EP2S180 FPGA는 총 143,520개의 ALUT를 제공한다. 하이퍼트랜스포트 인터페이스 및 기타 로직이 8퍼센트의 자원을 필요로 하므로(정상적으로 최대의 FPGA 자원 활용율은 90퍼센트 미만) 많아야 340개 PE를 수용할 수 있다. 다른 필요한 제어 로직 모듈을 고려했을 때 간단한 PE 디자인을 채택한다 하더라도 구현할 수 있는 PE의 숫자는 270개 미만이 될 것이다. 그러므로 PE의 자원 비용을 낮추도록 해야 한다. 그래야 FPGA 상에 되도록 많은 PE를 구현할 수 있다.V(i,j)의 Max-Out 연산 간소화이 PE 디자인은 Max-out DFF를 이용해서 유사성 행렬의 최대값을 저장한다. 최대값을 얻기 위해서는 첫 번째 단계에 이전 PE의 최대 출력을 현재 PE의 V(i,j)와 비교해야 한다. 이는 수평적 인접 행렬 요소 사이의 비교에 해당된다. 두 번째 단계에는 첫 번째 단계의 출력을 Max-out DFF 자신에 저장된 값과 비교해야 한다. 이는 수직적 인접 행렬 요소 사이의 비교에 해당된다. 이 두 단계 후에 결과가 다시 Max-out DFF에 저장된다.계산이 완료되었을 때 각각의 Max-out DFF에 저장된 모든 최대 값이 어레이로부터 쉬프트 아웃된다는 것을 감안했을 때 두 번째 비교 단계를 어레이 외부로 옮기고 첫 번째 단계는 각각의 PE로 유지할 수 있다. 이렇게 함으로써 PE로부터 max 연산을 제거할 수 있다(그림 5의 보라색 Max 블록).V(i,j) - α 연산의 간소화그림 6에서처럼 다중의 PE를 연결해서 PE 어레이를 형성할 때 왼쪽 PE(빨간색 하위 블록)의 V-out - α의 출력이 오른쪽 PE(파란색 하위 블록)의 V-in - α와 동일하다는 것을 알 수 있다. 그러므로 이 PE 디자인으로부터 V-in -α 를 제거할 수 있다. 이를 위해서는 V-out-Alpha라고 하는 V-out - α의 새로운 출력과 V-in-Alpha라고 하는 V-in - α의 새로운 입력을 추가해야 한다. PE를 연결해서 PE 어레이를 형성할 때는 왼쪽 PE의 V-out-Alpha 신호를 오른쪽 PE의 V-in-Alpha 신호로 연결해야 한다.Max 연산의 압축Max 연산은 뺄셈 및 2:1 다중화 연산으로 이루어진다. 예를 들어서 R=(X < Y)? Y : X는 FPGA로 합성했을 때 Temp=X - Y와 R = Sing_Bit_Temp? Y : X의 2개의 공식으로 변환할 수 있다. 그러므로 2개 20비트 데이터의 max 연산을 위해서는 40개의 ALUT를 필요로 한다. 20개 ALUT는 뺄셈에 이용되고 다른 20개 ALUT는 2:1 다중화 연산에 이용되어서 ALUT에 의해서 두 연산이 구현된다. 하지만 실제로는 이 결과의 부호 비트만 2:1 다중화 연산을 위한 선택 제어 신호로 이용된다. 그 차이는 폐기된다. 하드웨어 구현에 있어서는 이 부호 비트가 뺄셈의 최상위 비트(MSB)의 carry_out과 동일하다.이전 세대 FPGA와 비교해서 Stratix II FPGA는 적응식 로직 모듈(ALM) 설계에 있어서 현저한 향상을 이루었다[1]. ALM은 산술 모드로 동작했을 때 가산기의 캐리 출력과 복합 로직 출력을 동시에 이용할 수 있다. 이 모드일 때는 가산기의 출력이 무시된다.이와 같이 가산기를 복합 로직 출력과 함께 이용하는 것은 이를 이용할 수 있는 기능에 있어서 최대 50퍼센트의 자원 절약을 가능하게 한다. 그림 7에서 보듯이 max 연산 R = (X < Y)? Y : X 같은 조건부 연산은 ALM의 이러한 점을 최대한 활용할 수 있다.이 기능을 구현하려면 가산기를 이용해서 X에서 Y를 뺀다. 그런 다음 carry-out 신호를 로직 어레이 블록(LAB) 차원의 sync-load 신호로 전달한다. X가 Y보다 낮으면 carry-out 신호가 1이다. sync-load가 어서트되고 sync-data를 입력으로 선택한다. 이 경우에서는 데이터 Y가 sync-data 입력을 레지스터로 구동한다. X가 Y보다 크거나 같으면 sync-load 신호가 해제되고 X가 레지스터의 데이터 포트를 구동한다.비교 연산과 2:1 다중화 연산을 ALM으로 압축하기 위해서는 2:1 다중화의 출력만 DFF로 전달해야 한다. 다시 말해서 max 연산 후에 곧바로 DFF가 필요하다. 그렇게 함으로써 추가적인 로직 자원 활용이 유발될 것으로 보인다. 하지만 각각의 ALM의 활용 비율을 향상시키므로 전반적인 FPGA 자원을 절약할 수 있다.이와 같이 유발되는 DFF로 인한 문제는 한 행렬 요소의 계산을 완료하기 위해서 PE가 하나 이상의 클록 사이클을 필요로 함으로써 성능을 크게 저하시킬 수 있다는 것이다.음의 수의 처리V(i-1,j-1) +σ(S[j],T[j])를 계산할 때는 S[j]가 T[j]와 같지 않을 때 (S[j],T[j])가 음이므로 이 결과가 음일 수 있다. 모든 max 연산은 비부호 숫자를 기반으로 하므로 max 기능에 도달하기에 앞서 음의 숫자를 처리해야 한다.공식 4에 의하면 모든 음의 숫자가 0으로 리셋된다. 이는 다시 말해서 덧셈/뺄셈 연산으로부터 음의 숫자가 생성될 때마다 이를 무조건적으로 0으로 리셋할 수 있다는 것이다. 그러므로 이 PE 디자인에서는 DFF를 도입해서 덧셈/뺄셈 연산으로부터의 결과를 저장하고 덧셈/뺄셈 결과의 MSB(부호 비트)를 DFF에 대한 동기 소거 신호로 이용한다. 그러므로 덧셈/뺄셈 기능으로부터 양의 수가 도출될 때는 DFF에 그 값 그대로 저장된다. 그렇지 않고 덧셈/뺄셈 기능으로부터 음의 수가 도출되면 DFF에 0이 저장된다.멀티스테이지 PE 디자인앞에서는 면적 비용을 낮추고 음의 숫자를 처리하기 위한 DFF에 대해 소개했는데 이는 행렬 요소의 계산을 완료하기 위해서 더 많은 클록 사이클을 발생시켰다. 이 문제를 해결하기 위해서 우리 디자인은 불규칙 스테이지 지연시간의 파이프라인 제어 메커니즘을 이용한다. 이 점은 전반적인 PE 파이프라인 사이클 시간을 최소화하기 위해서 중요하다.그림 8에서 보듯이 FPGA 내부 위상 동기화 루프(PLL)를 이용해서 클록 주파수는 동일하나 위상 관계가 다른 4개의 클록을 발생시킨다. 이들 클록을 그림 9에서 보듯이 멀티스테이지 PE 디자인의 요구에 따라 DFF로 연결한다.위상 지연은 PE 디자인의 타이밍 시뮬레이션에 의해 결정된다. 예를 들어서 클록에서 클록-d2로의 지연을 6.3ns로 설정한다. 이 간격에 뺄셈 연산과 max 연산을 완료해야 하며 가장 긴 데이터 경로가 약 6ns이기 때문이다. 클록-d2에서 클록-d3로의 지연은 4.5ns로 설정한다. 이 간격에 맥시멈 연산만 수행하면 되고 가장 긴 데이터 경로가 약 4ns이기 때문이다.그림 9는 멀티스테이지를 이용한 PE 디자인의 블록도이다(LUT 로직에 대해서는 뒤에서 다룬다). 이 디자인에서는 α 및 β가 소프트웨어 프로그래머블 파라미터이며, σ(S[i],T[j])의 값이 또한 2개의 소프트웨어 프로그래머블 파라미터이다. 이들 파라미터를 적절히 설정함으로써 하드웨어 구현이 선형 및 아핀 갭 모델 알고리즘을 비롯한 기존의 소프트웨어 프로그램과 호환이 가능하다.알테라 Stratix II FPGA로 구현했을 때 이 디자인은 약 180개 ALUT가 필요할 것이다. 이와 비교해서 최적화되지 않은 간단한 PE 디자인의 경우에는 max 연산을 (V-out 및 Max-out을 위한) 출력 레지스터와 통합하는 기법을 고려한다고 하더라도 여전히 300개의 ALUT가 필요할 것이다. 그러므로 우리는 아래에서 설명하고 있는 최적화를 통해서 PE의 ALUT 활용을 약 40퍼센트 낮출 수 있었다. 이는 다시 말해서 FPGA로 더 많은 PE를 구현할 수 있고 결과적으로 이로부터 더 높은 병렬처리가 가능하다는 뜻이다. 한편 불규칙 스테이지 지연시간 제어 메커니즘은 PE가 적절하게 높은 주파수로 동작할 수 있도록 한다. 우리의 최종적인 구현의 경우에는 PE의 메인 클록 주파수가 66.7MHz이다.단백질 서열을 위한 스미스-워터맨 PE의 LUT 디자인DNA 서열과 단백질 서열의 차이점은 DNA 서열은 뉴클레오티드 유형이 4개(A, G, C, T)에 불과한 반면에 단백질 서열은 아미노산 유형이 20개에 달한다는 것이다. 그러므로 DNA 서열을 인코딩할 때는 4개 문자를 나타내기 위해서 2개 비트만 필요한 반면에 아미노산 서열을 위해서는 최소한 5개 비트가 필요하다. 이는 PE 디자인에 서열을 저장하기 위해서 좀더 많은 DFF를 필요로 하나 PE 디자인의 구조에는 영향을 미치지 않는다.중요한 점은 뉴클레오티드와 아미노산을 위한 패널티 점수 치환 행렬이 전적으로 다르다는 것이다. DNA 서열을 위해서는 치환 행렬의 값이 2개에 불과하다. 이는 S[i] 및 T[j]가 같거나 같지 않을 때의 값이다. 하지만 단백질 서열의 경우에는 한 문자를 다른 문자로 치환하기 위한 패널티 점수가 생물학적인 의미에서 각각의 문자가 다르다. 그러므로 치환 행렬이 보통 20*20 패널티 점수 행렬로 구성된다. 그림 10은 널리 이용되는 점수 행렬인 Blosum62이다[15].당연히 PE의 LUT로서 치환 행렬을 RAM 블록에 저장해야 한다. Blosum62에서는 최대 점수가 11이며 최소 점수가 -4이다. 하지만 다른 유형의 치환 행렬에서는 이 데이터가 큰 폭으로 다를 수 있다. 보편성을 고려해서 우리는 이 데이터 폭을 9비트로 설정했으며 MSB가 부호 비트이므로 데이터 범위가 -255~+255이다. 이는 대다수 경우를 위해서 충분히 넓은 것이다.앞서 언급했듯이 PE에 S[i] 및 T[j]를 저장하기 위해서는 각각 5비트씩 10비트가 필요하다. 어떠한 최적화를 거치지 않고 LUT를 구현한다면 RAM의 깊이는 210=1024가 되어야 하므로 하나의 LUT를 저장하기 위해서 2개의 M4k RAM 블록이 필요하다.실제로 이 치환 행렬에 이용된 표는 400개 항목에 불과하다. 나머지는 공백이며 비존재 인코딩 위치이다. 한편 이 치환 행렬은 사선으로 대칭적이어서 210개 요소만 필요하므로 어떠한 최적화를 이용하지 않고 LUT를 구현한다면 메모리 공간의 거의 80퍼센트가 불필요한 정보를 저장하는 데 낭비될 것이다. 그래서 우리는 치환 행렬을 RAM 블록에 더 효율적으로 저장하기 위해서 행렬을 4개의 작은 행렬로 분할하고 이중 3개만을 저장하는 새로운 저장 기법을 도입했다. 하위 행렬 분할은 그림 11에서 보는 바와 같다.그림 11에서 보듯이 전체적인 20*20 행렬을 S[i] 및 T[j]의 MSB의 가능한 4개 조합에 따라서 4개의 하위 행렬로 분할할 수 있다. 노란색 부분은 16*16 행렬이고, 파란색 부분은 4*4 행렬이고, 분홍색 부분은 2개의 대칭적 4*16 행렬이다. 이러한 분할을 바탕으로 그림 12 및 그림 13의 규칙에 따라서 이들 하위 행렬을 RAM 블록에 저장할 수 있다.그림 12는 어떻게 이들 하위 행렬을 RAM 블록의 각기 다른 위치로 맵핑하는지 또는 행렬 요소로 주소를 지정하는지 보여준다. 우리는 알파벳 순서에 따라서 S[i] 및 T[j]를 각각 Ds[4:0] 및 Dt[4:0]으로 인코딩했다.■ Ds[4] = 0이고 Dt[4] = 0이면 Addr[8] = 0, Addr[7:4] = Ds[4:0], Addr[3:0] = Dt[4:0]으로 한다. 그러면 이 주소 범위에는 256개 항목이 들어가고 노란색 부분이 여기에 저장된다.■ Ds[4] = 0이고 Dt[4] = 1이면 Addr[8:6] = 3’b100, Addr[5:4] = Dt[1:0], Addr[3:0] = Ds[4:0]으로 한다. 그러면 이 주소 범위에는 64개 항목이 들어가고 분홍색 부분이 이 구역에 저장된다.■ Ds[4] = 1이고 Dt[4] = 0이면 Ds와 Dt를 맞바꿀 수 있으므로 동일한 주소 범위에 두 번째 분홍색 부분을 저장할 수 있다. 다시 말해서 2개의 분홍색 부분이 대칭적이므로 이 중 하나만 RAM 블록으로 저장할 수 있다.■ Ds[4] = 1이고 Dt[4] = 1이면 Addr[8:4] = 5’b10100, Addr[3:2] = Ds[1:0], Addr[1:0] = Dt[1:0]로 한다. 그러면 이 주소 범위에 16개 항목이 들어가고 파란색 부분이 이 구역에 저장된다.이 기법에 의하면 각기 다른 3개의 부분만 9’b0_0000_ 0000에서부터 9’b1_0100_1111에 이르는 연속적 주소 범위에 저장할 수 있으며 전체적인 치환 행렬을 저장하기 위해서 336개 항목만 필요하다. 실제 FPGA에서는 M4k 블록을 이용해서 이 구현을 달성할 수 있다.그림 13은 이 치환 행렬의 메모리 저장 구조를 보여준다. 왼쪽의 9개 열은 메모리 주소이고, 오른쪽 9개 열은 메모리에 저장된 데이터이다. 이 데이터의 MSB는 부호 비트이고, 이것이 0이면 값이 음의 수가 아니며, 이 값이 1이면 이 값이 음의 수이다.스미스-워터맨 알고리즘의 코어 로직 디자인전체적인 계산 프로세스를 구현하기 위해서는 시스톨릭 PE 어레이 외부에서 카운터, FIFO, 시프터, 계산기, 일부 레지스터를 포함하는 보조적인 모듈들을 설계해야 한다. 코어 로직의 블록도는 그림 14에서 보는 것과 같다.그림 14에서 각 모듈의 기능은 아래와 같이 설명할 수 있다.■ S 및 T 카운터를 이용해서는 S/T의 길이에 따라서 PE 어레이 프로세스로 시프트인되는 서열을 제어한다. ■ S/T FIFO를 이용해서는 하이퍼트랜스포트 버스 인터페이스로부터 들어오는 입력 데이터를 버퍼링한다.■ S/T 시프터를 이용해서는 매 클록 사이클에 64비트 입력 데이터를 인코딩된 서열 문자로 쉬프트하고 인코딩된 서열 문자는 PE 어레이로 전달된다.■ Mid-data FIFO를 이용해서는 다중 반복 계산이 필요할 때 PE 어레이의 임시 중간 데이터를 저장한다.■ Mid-in Generator 모듈을 이용해서는 첫 번째 PE의 V-in - α를 계산하며, 이는 또한 멀티스테이지 클록의 요구에 따라서 PE 어레이의 중간 데이터를 버퍼링하는 데 이용된다.■ Mid-out Combination 모듈을 이용해서는 PE 어레이로부터의 출력을 결합하고 이를 Mid-data FIFO로 쓴다.■ Max Comparator 모듈을 이용해서는 PE 어레이로부터의 Max-out 및 V-out을 비교하고 이의 최대값을 저장한다. 이 부분은 그림 5의 두 번째 비교 단계(보라색 max 블록)에 해당되며 수직적 인접 행렬 요소 사이의 비교에 해당된다.■ Control/Result Registers 모듈은 호스트가 파라미터를 쓰고, 레지스터를 제어하고, 상태 및 결과를 읽는 데 이용된다.성능 평가이 FPGA의 성능을 평가하기 위해서 2.2GHz AMD64 옵테론 프로세서와 8GB DDR2 SDRAM 메모리를 이용한 XD1000 플랫폼의 호스트 시스템과 비교했다. XD1000의 운영체계는 리눅스 2.6.16.14이며 모든 소프트웨어는 GCC 4.1.1을 이용해서 ‘-O3’ 최적화 옵션으로 컴파일했다.DNA 스미스-워터맨 알고리즘의 가속화 테스트DNA의 스미스-워터맨 알고리즘을 위해서 우리는 이FPGA로 384개 PE를 구현했다. 이는 121,836 ALUT(총 143,520 ALUT의 85퍼센트)와 3,587,296 메모리 비트(총 9,383,040비트의 38퍼센트)를 필요로 한다. 이 연구에서는 PE 어레이 동작 주파수가 66.7MHz였으며 PE 어레이의 피크 성능은 25.6GCUPS였다. 이의 테스트 결과는 그림 15와 같다.서열이 짧을 때는 가속화가 매우 낮다는 것을 볼 수 있다. 예를 들어서 S/T 서열의 길이가 모두 256Bp일 때 소프트웨어 상의 가속화는 다음과 같은 이유에서 2.04에 불과하다.PE 어레이가 계산에 최대한 합류하지 않는다. 어떤 클록 사이클에 PE의 일부만이 효율적으로 실행된다. 실제로 384개의 PE 중에서 256개만이(서열 S로부터의) 질의 문자를 가지고 있어서 유효하며 앞의 128개 PE는 무효하다. 시스톨릭 PE 어레이의 작동 원리에 따라서 서열 T의 모든 문자가 먼저 처음 128개 PE를 통해 전달되어야 유효한 계산이 이루어질 수 있다.그러므로 처음 128개 사이클을 이용해서 서열 T를 첫 번째 유효한 PE로 전달한다. 이후의 129번째 사이클에는 하나의 PE만이 계산에 참여한다. 이후의 매 클록 사이클에는 또 다른 PE가 계산에 참여하며 384번째 사이클에 도달하면 256개 PE가 작동된다. 이 시점을 지나서는 이후의 매 클록 사이클에 PE가 계산에서 빠지고 640번째 사이클에 도달하면 마지막 PE만 작동한다. 그러므로 계산을 위해서 총 640 사이클이 소요되며 평균적으로 매 사이클에 102개 PE가 작동한 셈이다.또 다른 중요한 이유는 서열이 매우 짧을 때 FPGA 초기화 시간이 상수라는 점이다. PE 어레이로 서열을 전달하기에 앞서서 각각의 뉴클레오티드 문자가 2비트 데이터로 인코딩되며 예를 들어서 256Bp는 512비트 또는 64바이트 데이터로 디코딩된다. 그런데 하이퍼트랜스포트 직접 메모리 액세스(DMA) 전송 요구에 의해서 최소 전송 블록이 4KB이다. 그러므로 호스트 CPU에서 PE 어레이로 256Bp 서열을 전송하기 위해서 16KBp 서열을 전송할 때와 동일한 시간이 소요된다. 그러므로 이는 XD1000 플랫폼을 위해서는 소형 데이터 블록을 전송하는 것의 성능을 향상시켜야 한다는 뜻이기도 하다.계산이 이루어지는 동안에는 PE 어레이가 실행하는 병렬 부분을 제외하고 예를 들면 데이터를 준비하거나 FPGA를 초기화하는 등의 기능을 위해서 직렬 부분은 계속해서 호스트 CPU에 의해서 실행되어야 한다. 암달의 법칙에 따르면 작업 규모가 작으면 이 직렬 부분이 소요 시간의 상당 부분을 차지한다. 따라서 병렬 부분을 몇 배 가속화할 수 있느냐에 상관없이 병렬 부분 대 직렬 부분의 비율에 의해서 전체적인 작업 향상이 제한된다.단백질 스미스-워터맨 알고리즘의 가속화 테스트단백질을 위한 스미스-워터맨 알고리즘을 위해서도 역시 FPGA로 384개 PE를 구현했다. 이는 111,574 ALUT(총 143,520 ALUT의 78퍼센트)와 5,348,320 메모리 비트(총 9,383,040 비트의 57퍼센트)를 필요로 한다. 이 연구에서는 PE 어레이 동작 주파수가 66.7MHz였으며 PE 어레이의 피크 성능은 25.6GCUPS였다. 이 테스트 결과는 그림 16과 같다.DNA 스미스-워터맨 알고리즘과 비교해서 단백질 테스트는 동일한 하드웨어 피크 성능으로 훨씬 더 높은 가속화를 나타냈다. 이는 소프트웨어로 계산을 수행할 때 소프트웨어가 치환 행렬 값을 얻기 위해서 대형 테이블을 탐색해야 하고 2개의 문자를 비교해서 같은지 검사하는 것에 비해서 더 많은 시간을 소비하기 때문이다.Blosum62 치환 행렬(그림 10)의 소프트웨어 구현의 경우에는 행렬이 2차원 어레이에 저장된다. 이 어레이의 요소를 액세스하기 위해서는 소프트웨어가 그 요소의 인덱스를 계산해야 한다. 불행히도 아미노산 문자는 알파벳처럼 연속적이지 않다. 마지막 문자 ‘Y’ 전에 5개의 문자가 빠졌다. 그러므로 소프트웨어 프로그램이 ‘case’ 문을 이용해서 문자를 인덱스로 맵핑해야 한다. 단백질 서열에는 20개 유형의 문자가 있으므로 소프트웨어 프로그램이 매우 긴 case 문이 필요하다. 최적화를 이용하지 않으면 그림 16에서 보듯이 소프트웨어 프로그램이 최고 2배의 시간을 필요로 할 수 있다.향상 기법으로서 우리는 이 치환 행렬을 20*20에서 25*25로 확장하고, 빠진 5개 문자를 행렬에 포함시키고, 행렬을 알파벳순으로 재정렬했다. 유효 문자에서 무효 문자로의 치환 점수를 0으로 설정했다. 이 기법을 이용함으로써 한 문장만으로 인덱스를 계산할 수 있었다. 문자의 ASCII 값 빼기 0x41을 이용하는 것이다(0x41은 ‘A’의 ASCII이다). 이 기법은 소프트웨어가 비최적화 소프트웨어 버전보다 100퍼센트 더 신속하게 실행되도록 한다.결론 및 향후 연구이 글에서는 XD1000 재구성가능 수퍼컴퓨팅 플랫폼을 기반으로 DNA 및 단백질 서열을 위한 스미스-워터맨 알고리즘의 구현에 대해 살펴보았다. FPGA로부터 더 높은 병렬처리를 활용할 수 있도록 불규칙 스테이지 지연시간 제어 메커니즘과 압축적 치환 행렬 저장 기법을 이용해서 FPGA 자원 활용을 대폭적으로 감소시키는 멀티스테이지 PE 디자인을 선보였다. 이들 기법을 이용해서 66.7MHz로 동작하고 25.6GCUPS 피크 성능을 달성할 수 있는 384개 PE 시스톨릭 어레이를 구현했다. XD1000 플랫폼의 2.2GHz AMD64 옵테론 호스트 프로세서와 비교해서 이 FPGA가 각각 185배 및 250배의 가속화를 달성할 수 있었다.한편 우리 디자인은 서열 길이 제한을 64KBp로 확대함으로써 다양한 애플리케이션의 요구를 충족한다. DNA 서열을 위한 스미스-워터맨 알고리즘 디자인의 경우에는 4개의 소프트웨어 프로그래머블 파라미터를 이용해서 하드웨어 구현을 선형 및 아핀 갭 모델 알고리즘 등의 기존의 소프트웨어 프로그램과 호환이 가능하도록 한다. 단백질 서열을 위한 스미스-워터맨 알고리즘 디자인의 경우에는 역시 치환 행렬을 재구성 가능하며 사용자가 각기 다른 진화 모델 중에서 선택하거나 아니면 자체적인 진화 모델을 개발할 수 있다. 이러한 점들로 인해서 우리 디자인은 실제 애플리케이션을 위해서 매우 실용적이다.향후의 연구는 멀티 패턴 및 멀티 규칙을 위해 근접한 문자열이나 네트워크 침입 탐지 등과 같이 네트워크 콘텐츠 프로세싱을 가속화하도록 디자인을 확장하는 것을 포함한다. 일차적인 시험에서 이 디자인이 범용 CPU에 비해서 100배 이상의 가속화를 달성할 수 있을 것으로 나타났다. 이와 함께 몬테 카를로 알고리즘, BLAS, FFT, FIR 등의 프로세싱을 포함해서 연구용 컴퓨팅 분야의 부동소수점 애플리케이션을 위한 재구성가능 컴퓨팅 플랫폼을 구현함으로써 옵테론 프로세서의 성능을 대폭적으로 향상시킬 수 있기를 원한다.

회원가입 후 이용바랍니다.

개의 댓글

회원로그인

작성자 비밀번호

댓글 내용입력

댓글 정렬

최신순 추천순 답글순

BEST댓글

BEST 댓글 답글과 추천수를 합산하여 자동으로 노출됩니다. 닫기

더보기

김의겸 (webmaster@techworld.co.kr)

기자의 다른기사 보기

저작권자 © 테크월드뉴스 무단전재 및 재배포 금지