Parallel programming52 CUDA Dynamic Parallelism (동적 병렬) References https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html Programming Massively Parallel Processors Contents Dynamic Parallelism Overview Memory Data Visibility Execution Environment Synchronization, Streams, and Events CUDA Dynamic Parallelism(동적 병렬)은 CUDA 프로그래밍 모델의 확장이며, CUDA 커널이 새로운 커널을 launch함으로써 새로운 스레드 그리드를 만들 수 있게 해줍니다. 동적 병렬은 Kepler 아키텍처에서 도입되었고, GK110 칩에서 처음 선보였습니다. 과거.. 2022. 1. 1. Graph Search (Breadth-First Search) References Programming Massively Parallel Processors Contents Breadth-First Search (BFS) A Sequential BFS Function A Parallel BFS Function Optimization 이번에 살펴 볼 병렬 패턴은 Graph Search입니다. 그래프는 개체(entity)간의 관계(relation)를 나타내는 자료구조이며, 이 개체(entity)는 vertices(정점)으로 표현하고 관계는 edges(간선)으로 표현합니다. 세상의 많은 중요한 문제들은 아주 큰 스케일의 그래프 문제로 볼 수 있습니다. 예를 들면, 소셜 네트워크나 네비게이션 등이 있습니다. 그래프는 알고보면 희소 행렬(sparse matrix)와도 관련이.. 2021. 12. 30. 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. 리소스 동적 분할 및 제한 사항 (+ 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. 이전 1 2 3 4 5 6 다음