코드를 가져옵니다.

git clone https://github.com/UCLA-VAST/minimap2-acceleration.git

테스트베드를 빌드합니다.

...

Vitis HLS 환경을 설정합니다.

source /opt/tools/xilinx/Vitis/2024.1/settings64.sh

소프트웨어 에뮬레이션을 위한 TAPA 커널을 빌드합니다.

...

Xilinx SDx 환경을 설정합니다.

source /opt/tools/xilinx/SDx/2018.3/settings64.sh
ulimit -s unlimited
...

CUDA 커널을 빌드합니다.

(cd kernel/cuda/ && make);

커널 벤치마크를 실행합니다.

...

Intel Parallel Studio XE 환경을 설정합니다.

source /opt/tools/intel/parallel-studio/parallel_studio_xe_2019/psxevars.sh

SIMD 커널을 빌드합니다.

...

• Getting Started (시작하기)
• General Information (일반 정보)
• Users' Guide (사용자 가이드)
• Developers' Guide (개발자 가이드)
• Limitations and Notes (제한 사항 및 참고 사항)
• Acknowledgement (감사의 글)

게놈 시퀀싱(genome sequencing)에서, 입력 리드 쌍 간의 잠재적 오버랩을 감지하는 것은 매우 중요하지만 시간이 많이 소요되는 작업입니다. 특히 초장거리(ultra-long)인 경우 더욱 그렇습니다. 최신 기술이 적용된 오버래핑 툴 Minimap2는 속도와 정확성 면에서 다른 인기 있는 툴들을 능가합니다. 이 툴은 '체이닝(chaining)'이라는 단일 컴퓨팅 병목 지점을 가지고 있으며, 전체 시간의 70%를 차지하므로 가속화가 필요합니다.

우리는 체이닝 알고리즘을 수정하여 연산 순서를 재배열함으로써 해당 알고리즘을 하드웨어 친화적인 등가물로 변환합니다. 우리는 온칩 메모리 제약을 만족시키면서 병렬 PEs(Processing Elements)를 바쁘게 유지할 수 있는 세밀한 태스크 디스패칭 스킴(task dispatching scheme)을 맞춤 구현했습니다. 더욱이, HLS(High-Level Synthesis)를 사용하여 알고리즘을 FPGA 상의 완전 파이프라인 스트리밍 아키텍처로 매핑함으로써 상당한 성능 향상을 달성합니다. 동일한 방법론은 GPU 및 CPU SIMD 구현에도 적용되며, 우리는 또한 준수한 속도 향상(speedups)을 달성했습니다.

이 오픈 소스 저장소에서 우리는 다음 세 가지를 공개합니다. 첫째, FPGA용 HLS 체이닝 알고리즘 구현체, 둘째, GPU용 CUDA 체이닝 알고리즘 커널, 그리고 셋째, 체이닝을 위한 최적화된 CPU 코드를 제공합니다. 이들은 동일한 벤치마킹 입력/출력 인터페이스와 테스트베드를 공유하므로 공정한 비교가 가능하며 정확성 검증도 할 수 있습니다. 해당 코드는 추가적인 학술 연구 및 통합을 위해 MIT 라이선스 하에 공개됩니다.

자세한 내용을 확인하거나 작업에 우리의 가속 기능을 사용하고 싶다면, 저희 논문을 참고하고 인용해 주십시오:

L. Guo, J. Lau, Z. Ruan, P. Wei, and J. Cong, “Hardware Acceleration of Long Read Pairwise Overlapping in Genome Sequencing: A Race Between FPGA and GPU,” in 2019 IEEE 27th International Symposium On Field-Programmable Custom Computing Machines (FCCM), April 2019.

제3세대 시퀀싱(third-generation sequencing)의 긴 리드(long reads)를 참조 전체 유전체(reference whole genome) 없이 원래 서열로 조립하는 과정은 일반적으로 세 단계, 즉 오버랩(Overlap), 레이아웃(Layout), 그리고 컨센서스(Consensus) (OLC)를 사용합니다. 오버랩 단계는 리드 쌍이 공통으로 가지고 있는 부분을 확인합니다. 레이아웃 단계는 오버랩을 가진 연속적인 리드를 사용하여 결과 서열을 구축합니다. 컨센서스 단계는 가장 가능성이 높은 뉴클레오타이드 서열을 선택합니다.

OLC 조립의 첫 번째 단계인 오버랩 탐지(overlap detection)는 조립 과정의 성능 병목 지점입니다. 단편 리드(short-read) 조립에서 흔히 사용되는 리드 대 리드(read-to-read) 또는 리드 대 참조(read-to-reference) 정렬 문제와 유사하지만, 오버랩 탐지는 다른 문제입니다. 높은 오류율을 가진 긴 리드에 효율적이고 견고하게 작동하는 특수 알고리즘의 이점을 얻을 수 있습니다.

오버랩 탐지 단계에는 시딩(seeding)과 체이닝(chaining)이 포함됩니다:

• 시딩(Seeding): (1) 주어진 리드 세트에서 각 리드의 특징을 추출하고, (2) 의미 있게 씨앗(seeds)을 공유하는 리드를 식별합니다.
• 체이닝(Chaining): (3) 두 리드에서 일관된 거리를 공유하는 시드 매치(seed matches)의 직렬 연결(serials)을 찾습니다:

우리는 Minimap2가 장거리 읽기 오버래퍼(long-read overlapper)로 작동할 때 체이닝(chaining) 과정이 전체 실행 시간의 약 70%를 차지한다는 것을 발견했습니다. 게다가, 다른 프로파일링 결과들은 참조 기반 어셈블리(reference-based assembly)와 같은 다른 경우에도 체이닝이 상당한 시간을 소요함을 보여줍니다 (예: 전체 시간의 30%). 이는 저희가 체이닝 알고리즘을 가속화하도록 동기를 부여했습니다.

전체 저장소는 다음 명령어로 다운로드할 수 있습니다:

git clone https://github.com/UCLA-VAST/minimap2-acceleration.git

다음 텍스트에서는 클론된 디렉토리에서 작업한다고 가정합니다. 예를 들어, 위 명령어를 실행한 후 다음 명령어로 작업 경로를 변경할 수 있습니다:

cd minimap2-acceleration

테스트베드 소프트웨어(testbed software)를 빌드하려면 C 컴파일러, GNU make 및 zlib 개발 파일이 설치되어 있어야 합니다. 다음 명령어로 테스트베드를 빌드할 수 있습니다:

(cd testbed/ && make);

SDAccel, Vivado HLS 및 Vivado가 설치되어 있어야 합니다. 저희는 커널(kernel)이 호스트(host)와 통신하는 인터페이스로 SDAccel을 사용합니다. 시작하기 전에 도구에서 제공하는 환경 파일을 소싱(source)해야 할 수도 있습니다. 예를 들면:

source /opt/tools/xilinx/SDx/2018.3/settings64.sh
ulimit -s unlimited

소프트웨어 에뮬레이션(Software emulation)의 경우 다음 명령어로 커널을 빌드할 수 있습니다:

(cd kernel/hls/ && make csim-target);

하드웨어 에뮬레이션(Hardware emulation)의 경우:

(cd kernel/hls/ && make cosim-target);

그리고 비트스트림 생성(bitstream generation)을 위해:

(cd kernel/hls/ && make bitstream);

C 컴파일러와 CUDA 10이 설치되어 있어야 합니다. 다음 명령어로 GPU 커널 벤치마크를 빌드할 수 있습니다:

(cd kernel/cuda/ && make);

Intel Parallel Studio XE가 설치되어 있어야 합니다. 이 코드는 Intel Parallel Studio XE 2019로 테스트되었습니다. 먼저 다음 명령어로 컴파일 환경을 설정해야 합니다:

source /opt/tools/intel/parallel-studio/parallel_studio_xe_2019/psxevars.sh

경로는 사용자의 환경에 따라 다를 수 있습니다. 위치는 시스템 관리자에게 문의하십시오.

CPU SIMD 커널은 다음 명령어로 빌드할 수 있습니다:

(cd kernel/simd/ && make);

저희는 PacBio 시퀀서에서 얻은 공개 Caenorhabditis Elegans 40x Sequence Coverage 데이터셋으로 구현을 테스트했습니다. 먼저 여기에서 데이터셋을 얻으시는 것이 좋을 수 있습니다. 페이지에 추천된 다운로드 도구 중 아무거나 사용하여 .fastq 파일을 얻고, cat 명령어로 결합할 수 있습니다. 다음 내용에서는 결합된 게놈 리드 파일이 ~/c_elegans40x.fastq에 있다고 가정합니다.

참고: C. Elegans 데이터셋은 링크에서 제거되었습니다. 백업본이 있다면 그것을 사용하실 수 있습니다. 그렇지 않다면 가지고 계신 다른 어떤 데이터셋을 사용하셔도 됩니다. 한 가지 옵션으로는 PacBio 웹사이트의 Sunflower 데이터셋이 있습니다.

나중에 벤치마킹을 위한 테스트 데이터를 생성하려면 다음 명령어를 실행할 수 있습니다:

./testbed/minimap2 -ax map-pb \
~/c_elegans40x.fastq ~/c_elegans40x.fastq \
--chain-dump-in in-30k.txt \
...

이 명령어는 벤치마크 섹션에서 나중에 사용하는 30,000개 리드의 체이닝 함수 입력 파일인 in-30k.txt와 해당 체이닝 작업의 예상 출력 파일인 out-30k.txt를 생성합니다. 이 파일을 커널 실행 결과와 비교할 수 있습니다.

'테스트 데이터 생성(Generate Test Data)' 섹션에서 생성된 테스트 데이터를 사용하여 다음 명령어로 CPU에서 빌드된 HLS 커널을 시뮬레이션할 수 있습니다:

# 소프트웨어에서 커널 벤치마크를 시뮬레이션합니다.
XCL_EMULATION_MODE=sw_emu kernel/hls/bin/2018.3/vcu1525/kernel \
kernel/hls/bit/2018.3/vcu1525/kernel-csim.xclbin \
...

이 명령어는 파일 in-30k.txt에서 입력 앵커를 호스트 메모리로 읽어와, PCIe를 통해 FPGA 온보드 메모리로 데이터 전송을 시뮬레이션하고, 계산을 위한 커널을 시뮬레이션한 후, 이를 다시 호스트 메모리로 전송하여 계산된 점수(scores)와 선행 요소(predecessors)를 파일 kernel-30k.txt에 기록합니다.

하드웨어 에뮬레이션은 내부적으로 시뮬레이션을 실행하기 때문에 더 작은 데이터를 생성해야 할 수도 있습니다. 대용량 데이터셋을 사용하면 긴 시뮬레이션 시간이 발생할 수 있습니다. 다음으로 에뮬레이션을 수행할 수 있습니다:

온보드(onboard) 실행을 위해서는 다음 명령어를 사용할 수 있습니다:

XCL_EMULATION_MODE=hw_emu kernel/hls/bin/2018.3/vcu1525/kernel \
kernel/hls/bit/2018.3/vcu1525/kernel-cosim.xclbin \
in-small.txt kernel-small.txt

kernel/hls/bin/2018.3/vcu1525/kernel \
kernel/hls/bit/2018.3/vcu1525/kernel-hw.xclbin \
in-30k.txt kernel-30k.txt

FPGA 커널에서 얻은 결과는 파일 테스트베드(file testbed)가 생성한 결과와 약간 다릅니다. 저희는 주파수 최적화(frequency optimizations)를 적용했기 때문에 수치적으로는 다르지만 기능적으로는 동등합니다. 정확한 결과를 기대하신다면, kernel/hls/src/device_kernel.cpp 파일에서 코드를 수정하고 OPTIMIZE_DSP를 주석 처리할 수 있습니다.

'Generate Test Data' 섹션에서 생성된 테스트 데이터를 사용하여 다음 명령어로 빌드된 GPU 커널을 실행할 수 있습니다:

kernel/cuda/kernel in-30k.txt kernel-30k.txt

이 명령어는 입력 앵커(input anchors)를 파일 in-30k.txt에서 호스트 메모리(host memory)로 읽어 들인 후, PCIe를 통해 데이터를 GPU 전역 메모리(GPU global memory)로 전송하고, GPU 커널을 실행하여 계산한 다음, 결과를 다시 호스트 메모리로 전송하고 계산된 점수(scores)와 선행 요소(predecessors)를 파일 kernel-30k.txt에 작성합니다.

이 명령어는 표준 출력(standard output)에 세 가지 측정 지표(metrics)를 출력합니다. 첫 번째는 호스트 메모리에서 GPU 전역 메모리로 PCIe를 통해 데이터를 전송하는 시간입니다. 두 번째는 전송 시간과 GPU 커널의 총 실행 시간을 합한 것입니다. 세 번째는 GPU/호스트 통신 및 GPU 실행을 포함한 전체 종단 간(end-to-end) 시간입니다.

예를 들어, NVIDIA Tesla P100 GPU를 사용했을 경우 출력은 다음과 같습니다:

****** kernel took 0.834192 seconds to transfer in data
***** kernel took 2.032814 seconds to transfer in and execute
***** kernel took 2.688967 seconds for end-to-end

참고: NVIDIA Tesla P100 GPU가 아닌 다른 GPU를 사용하는 경우, GPU별 매개변수(GPU specific parameters)를 조정하고 싶을 수 있습니다. 자세한 내용은 kernel/cuda/include/common.h 및 'GPU Kernel' 섹션을 참조하십시오.

정확성을 확인하려면 다음 명령어를 실행할 수 있습니다:

cmp out-30k.txt kernel-30k.txt

만약 아무것도 출력되지 않는다면, 이는 가속 커널(acceleration kernel)의 출력이 정확하다는 의미입니다.

Generate Test Data 섹션에서 생성된 테스트 데이터를 사용하여 다음 명령어로 빌드된 CPU SIMD 커널을 실행할 수 있습니다:

kernel/simd/kernel in-30k.txt kernel-30k.txt

이 명령어는 파일 in-30k.txt에서 입력 앵커를 읽어와, CPU SIMD 커널로 계산을 수행하고, 계산된 점수(scores)와 전임자(predecessors)를 파일 kernel-30k.txt에 작성합니다.

이 명령어는 표준 출력에 하나의 메트릭, 즉 CPU에서의 총 커널 실행 시간을 출력합니다. 예를 들어, 14 스레드 Intel Xeon CPU E5-2680에서는 다음과 같은 출력이 나옵니다:

***** kernel took 4.358382 seconds to finish

CPU에서 몇 개의 스레드를 실행할지 제어하고 싶을 수 있습니다. 환경 변수 OMP_NUM_THREADS를 사용하여 지정할 수 있습니다. 게다가, CPU 코어별 스레드 친화도(thread affinity)를 제어하고 싶다면 KMP_AFFINITY를 지정할 수 있습니다. 자세한 내용은 Intel® C++ Compiler 19.0 Developer Guide 및 Reference를 참조하십시오. 예를 들어, 다음 명령어는 커널을 14개 스레드에서 실행하고 스캐터 친화도(scatter affinity)를 사용합니다:

KMP_AFFINITY=granularity=fine,scatter \
OMP_NUM_THREADS=14 \
kernel/simd/kernel \
...

NUMA 친화도를 실험하려면 numactl --cpubind=1을 사용하여 모든 실행을 단일 CPU 코어에 바인딩할 수 있습니다.

정확성을 확인하려면 다음 명령어를 실행할 수 있습니다:

cmp out-30k.txt kernel-30k.txt

만약 예상대로 아무것도 출력되지 않는다면, 이는 가속 커널의 출력이 정확하다는 의미입니다.

README.md: 이 파일은 testbed: 테스트 데이터 생성을 지원하는 Minimap2의 수정 버전입니다. testbed/main.c: 메인 진입 함수와 추가된 명령줄 옵션 정의를 포함합니다. testbed/chain.c: 체이닝 알고리즘의 수정을 담은 소스 파일이며, 입력/출력 파일을 덤프하는 코드 로직도 포함합니다.

kernel/hls: Xilinx FPGA용 Minimap2 체이닝 알고리즘의 HLS 구현체입니다.kernel/cuda: NVIDIA Tesla P100 GPU용 Minimap2 체이닝 알고리즘의 CUDA 구현체입니다. K40c 및 V100 GPU에서도 다른 파라미터로 테스트되었습니다.kernel/cuda/device/device_kernel.cu: 체이닝 알고리즘을 위한 GPU 커널 파일입니다.kernel/cuda/device/device_kernel_wrapper.cu: 데이터 전송, GPU 커널 실행, 그리고 실행 시간 측정을 위한 래퍼(wrapper) 함수입니다.kernel/cuda/include/common.h: CUDA 스트림 수, 블록 크기, 스레드 언롤링 계수(thread unrolling factor), 타일링 크기를 포함하여 GPU 실행을 위한 파라미터들입니다. kernel/simd: Intel C 컴파일러의 프래그마(pragmas)를 사용한 SIMD 구현체입니다.kernel/simd/src/host_kernel.cpp: 체이닝 알고리즘을 위한 CPU SIMD 커널 구현 파일입니다. 테스트베드는 Minimap2 소프트웨어의 수정된 버전이며, Minimap2에서 대부분의 명령줄 옵션을 상속받습니다. 따라서 testbed 프로그램에서 사용할 수 있는 기능은 Minimap2의 매뉴얼 레퍼런스 페이지를 확인하시면 됩니다. 마치 Minimap2 명령줄 도구를 호출하는 것처럼 간단하게 사용할 수 있습니다. 이 수정된 소프트웨어는 세 가지 추가적인 명령줄 옵션을 파싱합니다: --chain-dump-in: 체이닝 알고리즘의 입력을 저장할 출력 파일입니다. mm_chain_dp 함수가 호출될 때, 해당 함수의 인자들을 지정된 파일에 출력합니다. 이 파일의 형식은 나중에 문서화됩니다. --chain-dump-out