[논문]GPU 기반 행렬 곱셈 병렬처리 알고리즘

박상근

doi:10.22710/jict.2019.9.1.001

GPU 기반 행렬 곱셈 병렬처리 알고리즘
Parallel Algorithm for Matrix-Matrix Multiplication on the GPU 원문보기

융ㆍ복합기술연구소 논문집 = Journal of institute of convergence technology, v.9 no.1, 2019년, pp.1 - 6

박상근 (한국교통대학교 기계공학)

Abstract ▼ AI-Helper

Matrix multiplication is a fundamental mathematical operation that has numerous applications across most scientific fields. In this paper, we presents a parallel GPU computation algorithm for dense matrix-matrix multiplication using OpenGL compute shader, which can play a very important role as a fundamental building block for many high-performance computing applications. Experimental results on NVIDIA Quad 4000 show that the proposed algorithm runs about 208 times faster than previous CPU algorithm and achieves performance of 75 GFLOPS in single precision for dense matrices with matrix size 4,096. Such performance proves that our algorithm is practical for real applications.

주제어

표/그림 (4)

그림 Fig. 1 Compute work group and invocations
그림 Fig. 2 Parallel computing using shared memory: As & Bs represent the shared memory for matrix A & B, respectively, (x0, y0) denotes the starting indices of R-submatrix.
표 Table 1 Performance comparison of CPU and GPUalgorithm (GFLOPS : Giga-sized floating point operations per second)
그림 Fig. 3 Performance comparison of CPU-algorithm and GPU-algorithm

AI 본문요약
AI-Helper

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

문제 정의

본 연구는 GPU 상에서 병렬 처리에 의해 수행되는 OpenGL 컴퓨터 쉐이더 행렬 곱셈 알고리즘을 상세히 서술하였고, 수치 실험을 통하여 본 연구 알고리즘의 계산 성능을 기술하였다. 또한 알고리즘 구현에 필요한 GPU 메모리 구조 및 쉐이더 invocation, barrier 동기화 등에 관해 기술하였다.
본 연구는 이러한 GPU을 활용하여 공학 및 과학 분야에서 컴퓨팅 연산을 위해 가장 많이 사용되고 있는 행렬 연산을 신속히 수행할 수 있는 병렬처리 행렬 곱셈 알고리즘 및 그 계산 성능을 소개하고자 한다. 행렬 곱셈은 수많은 수치 알고리즘을 위한 필수 구성요소 로서 계산량 측면에서 상당 부분을 차지하고 있기 때문에 해당 수치 알고리즘의 성능을 좌우한다.

제안 방법

본 연구는 GPU 상에서 병렬 처리에 의해 수행되는 OpenGL 컴퓨터 쉐이더 행렬 곱셈 알고리즘을 상세히 서술하였고, 수치 실험을 통하여 본 연구 알고리즘의 계산 성능을 기술하였다. 또한 알고리즘 구현에 필요한 GPU 메모리 구조 및 쉐이더 invocation, barrier 동기화 등에 관해 기술하였다.
본 연구에서 사용한 그래픽 카드의invocation 최대값이 1024이므로 32 × 32 × 1의 shader invocation 개수 (wsize)를 사용하였고, local work group 개수 (gsize)는 Microsoft TDR (Timeout Detection & Recovery) 문제를 피하기 위해 최대 64 × 64 × 1로 설정 하였다.
본 연구에서 제안하는 GPU 병렬처리 행렬 곱셈 알고리즘은 크게 CPU 상에서 OpenGL에게 데이터를 전송하고 병렬 계산을 명령하는 병렬 설정 프로그램 (Algorithm 1)과 명령에 의한 병렬 계산을 수행하는 병렬 계산 프로그램(Algorithm 2)으로 구성된다.
결국 다수의 측정을 통한 평균값 계산이 필요하다. 본 연구의 경우는 10회 측정하여 평균하였다.
비교에 사용된 행렬은 정방 행렬로써 그 크기가 N = 128, 256, 512, 1024, 2048, 4096일 때 각 경우에 대해 CPU-알고리즘과 GPU-알고리즘의 GFLOPS 값을 측정하였고, 상대적 비교를 위해 CPU 대비 GPU 의 GFLOPS 값을 속도비로 표시하였다. Fig.
2) 메모리 쓰기/읽기 동기화 : 메모리 쓰기 작업이 완료 되지 않은 상태에서 읽기 작업이 시작될 수 있다. 쓰기 작업이 완료된 데이터만이 읽혀지도록 보장하기 위해 OpenGL 컴퓨터 쉐이더의 memoryBarrier() 함수를 사용하여 메모리 쓰기와 읽기 순서를 조정하는 메카니즘을 구현하였다.
1) 계산 작업 순서 동기화 : 수행속도가 느린 어떤 invocation이 memory의 특정 주소에 접근하여 데이터를 읽을 때 수행속도가 빠른 invocation 이 수정해 놓은 상태라면 수행속도가 느린 invocation 은 잘못된 데이터를 가지고 계산을 하게 된다. 이와 같은 상황을 막기 위해 OpenGL 컴퓨터 쉐이더의 barrier() 함수를 사용하여 작업 수행의 동기화 메커니즘을 구현하였다.
한편 본 연구에서는 구현한 GPU 알고리즘의 성능을 비교 평가하기 위해, 일반적으로 CPU 메인 메모리를 가지고 수행되는 CPU 행렬 곱셈 프로그램을 Algorithm 3과같이 구현하였고, Table 1과 같이 본 연구 병렬 계산 알고리즘과 비교하였다.

대상 데이터

본 연구에서 사용한 그래픽 카드는 엔디비아 Quadro 4000이고, 비디오 메모리 크기는 2,048 MB, 블록 당 스레드 개수는 1024개이다. 본 연구에서 사용한 병렬 계산 평가지표는 유효(effective) GFLOPS이다.

이론/모형

본 연구에서 사용한 그래픽 카드는 엔디비아 Quadro 4000이고, 비디오 메모리 크기는 2,048 MB, 블록 당 스레드 개수는 1024개이다. 본 연구에서 사용한 병렬 계산 평가지표는 유효(effective) GFLOPS이다. 즉 알고리즘 계산 성능을 수치로 나타내기 위해 초당 부동소수점 연산 회수를 기가 단위로 표시하는 GFLOPS를 주요 지표로 사용 하는데, 본 연구 행렬 곱셉의 경우, 곱셈 연산 횟수가 (m x n x l)이고 덧셈 연산 횟수가 (m x n x l)이므로 다음과 같이 나타낼 수 있다.

성능/효과

1) 계산 작업 순서 동기화 : 수행속도가 느린 어떤 invocation이 memory의 특정 주소에 접근하여 데이터를 읽을 때 수행속도가 빠른 invocation 이 수정해 놓은 상태라면 수행속도가 느린 invocation 은 잘못된 데이터를 가지고 계산을 하게 된다. 이와 같은 상황을 막기 위해 OpenGL 컴퓨터 쉐이더의 barrier() 함수를 사용하여 작업 수행의 동기화 메커니즘을 구현하였다.
2) 메모리 쓰기/읽기 동기화 : 메모리 쓰기 작업이 완료 되지 않은 상태에서 읽기 작업이 시작될 수 있다. 쓰기 작업이 완료된 데이터만이 읽혀지도록 보장하기 위해 OpenGL 컴퓨터 쉐이더의 memoryBarrier() 함수를 사용하여 메모리 쓰기와 읽기 순서를 조정하는 메카니즘을 구현하였다.
3의 왼쪽 축은 GFLOPS 축이고, 오른쪽 축은 속도비 축이다. 예상대로 GPU-알고리즘이 상당히 빠르며, n = 4096일 때 대략 208배의 속도 차이가 나타냄을 확인할 수 있다.

후속연구

본 연구에서 제시한 GPU 행렬 곱셈 알고리즘은 OpenGL 라이브러리를 사용하기 때문에 특정 그래픽 카드에 대한 의존성이 전혀 없다. 또한 그래픽 렌더링에 바로 사용될 수 있으며, 나아가 게임분야의 물리 엔진에도 기반 기술로서 활용도가 높을 것으로 기대된다. 추후 연구 과제로 본 연구에서 개발한 병렬 처리 방식을 바탕으로, 전치행렬 및 역행렬을 병렬 계산하는 프로그램을 개발할 예정이며, 수치해석 기법인 PCG, GMRES 등에 관해 GPU 가속화 프로그램을 개발할 예정이다.
또한 그래픽 렌더링에 바로 사용될 수 있으며, 나아가 게임분야의 물리 엔진에도 기반 기술로서 활용도가 높을 것으로 기대된다. 추후 연구 과제로 본 연구에서 개발한 병렬 처리 방식을 바탕으로, 전치행렬 및 역행렬을 병렬 계산하는 프로그램을 개발할 예정이며, 수치해석 기법인 PCG, GMRES 등에 관해 GPU 가속화 프로그램을 개발할 예정이다. 현재 방대한 계산량을 요구하는 FFT 및 합성곱(convolution) 등을 개발 중에 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	행렬 곱셈이 알고리즘의 성능을 좌우하는 이유는 무엇인가?	본 연구는 이러한 GPU을 활용하여 공학 및 과학 분야에서 컴퓨팅 연산을 위해 가장 많이 사용되고 있는 행렬 연산을 신속히 수행할 수 있는 병렬처리 행렬 곱셈 알고리즘 및 그 계산 성능을 소개하고자 한다. 행렬 곱셈은 수많은 수치 알고리즘을 위한 필수 구성요소 로서 계산량 측면에서 상당 부분을 차지하고 있기 때문에 해당 수치 알고리즘의 성능을 좌우한다. 이러한 이유로 대부분의 수치 라이브러리는 보다 빠른 행렬 곱셈을 구현하기 위해 적잖은 시간과 노력을 경주한다.
	CUDA와 비교되는 컴뷰터쉐이더의 장점은 무엇인가?	참고로 CUDA의 경우 병렬처리 계산만을 위한 용도로 사용될 수 있고 엔디비아사의 그래픽 카드에서만 작동 하는 단점을 가지고 있다. 이것과 비교하여 컴퓨터 쉐이더는 일반적인 그래픽 렌더링 및 이미지 프로세싱 등의 작업에서도 사용 가능하며 이들이 사용하는 데이터 및 관련 리소스(resources) 등을 공유할 수 있기 때문에 대규모 실시간 계산 작업을 가능토록 지원할수 있다. 또한 특정 그래픽 카드의 의존성이 없고, 컴퓨터 OS에 무관하며, 모바일(mobile) 환경에서도 큰어려움 없이 사용 가능하다는 특징을 가지고 있어 점차 그 응용 분야가 늘어나고 있다.
	컴퓨터 쉐이더는 무엇인가?	OpenGL이 제공하는 shader 중의 하나인 컴퓨터 쉐이더(compute shader) 6) 는 일반적인 그래픽 렌더링 이외의 병렬처리 계산 작업을 위해 GPU가 사용될 수 있도록 GPGPU(General-Purpose computing on Graphics Processing Units) 프로그래밍을 지원하는 범용 shader 이다. 현재 GPGPU 프로그래밍을 지원하는 가장 알려진 기술로 엔디비아사의 CUDA 및 AMD에서 추진하는 OpenCL이 있는데, 이들 모두 GPU기반 병렬처리 부동 소수점 계산을 위한 개발 환경을 지원한다.

참고문헌 (6)

http://www.netlib.org/blas.
https://software.intel.com/en-us/mkl.
http://developer.amd.com/tools-and-sdks/archive/acml-product-features/.
https://developer.nvidia.com/cublas.
https://docs.nvidia.com/cuda/nvblas/index.html.
G. Sellers, R. S. Wright, and N. Haemel, OpenGL SuperBible (7th ed.), Addison-Wesley, 2015.

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

연합인증