NVIDIA48 Parallel Merge Sort (merge operation) References Programming Massively Parallel Processors Contents A Sequential Merge Algorithm A Parallelization Approach : co-rank CO-RANK function Implementation A Basic Parallel Merge Kernel A Tiled Merge Kernel A Circular-Buffer Merge Kernel 이번 포스팅에서 살펴 볼 병렬 패턴은 ordered merge operation 입니다. 이는 두 개의 정렬된 리스트를 받아서 하나의 정렬된 리스트를 생성합니다. Ordered merge operation은 정렬 알고리즘으로 사용될 수 있습니다. 정렬은 컴퓨터 공학의 수 많은 분.. 2021. 12. 24. Sparse Matrix Computation References Programming Massively Parallel Processors Contents Sparse Matrix, CSR Parallel SpMV Using CSR ELL Format Hybrid Approach to Regulate Padding 본문에 사용된 코드는 아래 링크에서 확인하실 수 있습니다. https://github.com/junstar92/parallel_programming_study/blob/master/CUDA/sparseMatrixVectorMul/SpMV.cu GitHub - junstar92/parallel_programming_study: Study parallel programming - CUDA, OpenMP, MPI, Pthread Study p.. 2021. 12. 21. Parallel Histogram References Programming Massively Parallel Processors Contents Histogram atomicAdd의 사용 Memory Coalescing을 고려한 Histogram 커널 Atomic 연산에 의한 시간지연 문제 Privatized Histogram Kernel 히스토그램(histogram)은 데이터 항목의 빈도를 연속적인 숫자 간격으로 표시하는 것입니다. 히스토그램의 일반적인 형태에 데이터 항목의 빈도는 수평축에 상승하는 직사각형 또는 막대의 높이로 표시됩니다. 예를 들어, "programming massively parallel processors"라는 문장에서 알파벳의 빈도를 표시하기 위해서 히스토그램이 사용될 수 있습니다. 간단하게 살펴보기 위해서 문장.. 2021. 12. 18. Parallel Prefix Sum (2) References Programming Massively Parallel Processors Contents Brent-Kung adder Algorithm A More Work-Efficient Parallel Scan Parallel Prefix Sum (1) 이전 포스팅에서 살펴본 Kogge-Stone 커널은 단순하고, 실제 어플리케이션에서의 효율성이 상당히 낮습니다. 위에서 살펴봤듯이, 어떠한 값들의 집합의 합을 계산하는 가장 빠른 병렬 방법은 reduction tree입니다. 충분한 execution units이 있다면, reduction tree는 \(log_2 N\)의 time unit으로 N개의 값에 대한 합을 계산할 수 있습니다. Tree는 출력값 계산에 사용할 수 있는 여러 개의 su.. 2021. 12. 17. Parallel Prefix Sum (1) References Programming Massively Parallel Processors Contents Kogge-Stone Scan 알고리즘 Background 수학적으로 inclusive scan 연산은 binary associative operator \(\oplus\)와 n개의 input 배열 \([ x_0, x_1, \cdots, x_{n-1} ]\)을 취해서 아래의 output 배열을 반환하는 연산입니다. \[ [x_0, (x_0 \oplus x_1), \cdots, (x_0 \oplus x_1 \oplus \cdots x_{n-1}) ] \] 만약 \(\oplus\)가 덧셈 연산이라면 [3 1 7 0 4 1 6 3]의 input 배열에 대한 inclusive scan 연산은 [3 4 .. 2021. 12. 15. Tiled 2D Convolution References Programming Massively Parallel Processors Contents Tiled 2D Convolution with Halo Cells 1D Convolution (CUDA Constant Memory) 이전 포스팅 1D 컨볼루션에 이어서 이번 포스팅에서는 2D 컨볼루션에 대해 알아보겠습니다. 기본적인 2D 컨볼루션에 관한 것은 이전 포스팅 참조 부탁드립니다. 아래 포스팅에서의 이미지 Blur 처리 예제도 도움이 될 듯 합니다.. ! CUDA Thread 구조와 Data Mapping (예제 : 이미지 흑백, Blur 처리) 실제 이미지를 표현할 때 보통 2D-행렬로 표현됩니다. 이미지 처리 라이브러리는 일반적으로 이미지를 메모리로 읽을 때, row-major 형.. 2021. 12. 14. 1D Convolution (CUDA Constant Memory) References Programming Massively Parallel Processors Contents 1D, 2D Convolution 1D Parallel Convolution (Basic) Constant Memory and Caching Tiled 1D Convolution with Halo cells(ghost cells) Convolution(컨볼루션)은 signal processing(신호 처리), digital recoding, image/video processing(이미지/영상 처리), computer vision 등에서 다양한 형태로 사용되는 배열 연산(array operation)입니다. 아마도 딥러닝의 CNN에 대해서 공부를 했다면 조금 더 쉽게 다가올 수 있을 것 같습니다.. 2021. 12. 13. 부동소수점 (Floating-Point) References Programming Massively Parallel Processors Contents 부동소수점(Floating-Point) 표현, 표기법 특별한 비트 패턴과 정밀도(in IEEE Format) 산술 정확도와 자리맞춤(Rounding) 부동소수점 주의사항 Floating-point Data Representation (부동소수점 표현) IEEE-754 부동소수점 표준은 컴퓨터 제조업에서 부동소수점데이터를 공통되게 표현하고 산술 연산하기 위한 노력으로 만들어졌습니다. 거의 대부분의 컴퓨터 제조업체에서 이 표준을 수용하고 사용하고 있습니다. 따라서 개발자들은 이 표준의 개념과 현실적인 고려사항들을 이해하는 것이 중요합니다. 부동소수점 수 체계는 어떤 수를 비트 패턴으로 표현하는 것부.. 2021. 12. 11. 리소스 동적 분할 및 제한 사항 (+ device query) References Programming Massively Parallel Processors Contents SM 리소스의 동적 분할 (Dynamic Partitioning) 리소스 간의 제한사항 (limitations) CUDA Device Query SM(Streaming multiprocessor)의 실행 리소스는 레지스터(registers), 공유 메모리(shared memory), 스레드 블록 슬롯(thread block slots), 스레드 슬롯(thread slot)을 포함합니다. 이 리소스들은 동적으로 분할되고 스레드에게 할당되어 수행될 때 사용됩니다. 스레드 슬롯과 블록 슬롯 Fermi 아키텍처의 경우에는 1536개의 스레드 슬롯이 있습니다. 이 스레드 슬롯은 분할되어 런타임에 스레드 .. 2021. 12. 10. Divergent Wraps (예제 : Sum Reduction) References Programming Massively Parallel Processors https://developer.download.nvidia.com/assets/cuda/files/reduction.pdf Contents Warp Partioning Divergence Branch (Divergent Warps) Sum Reduction ( + 최적화 버전) 지난 포스팅에서 리소스 측면에서 CUDA의 성능을 제한하는 것을 살펴봤습니다. 이번에는 스레드 실행 측면에서 성능을 제한하는 것에 대해서 살펴보도록 하겠습니다. CUDA 커널을 실행하면 2-level 계층으로 구성된 스레드들의 그리드가 생성됩니다. Top-level에서 그리드는 1,2, or 3차원 배열의 블록으로 구성됩니다. Bott.. 2021. 12. 9. 이전 1 2 3 4 5 다음
