Computing

BLAS 란 BLAS는 Basic Linear Algebra Subprograms(BLAS)의 약자[1]로, 한국어로 해석하자면 기본 선형 대수 함수(subprogram을 어떻게 번역하는 게 좋을 지 모르겠다.)이다. 말 그대로 선형 대수 분야에서 사용되는 기본적인 연산자들의 일반화된 형태들의 집합을 나타낸다. High performance computing (HPC) 분야에서 성능을 측정하는 도구로도 사용되며, 기본적으로 선형 대수가 많은 산업 분야에서 사용되기에 최고의 성능을 내는 것을 목적으로 많은 연구가 진행되고 있다. 특히 SIMD 연산자를 이용한 병렬처리가 BLAS 연산 최적화에 많이 사용된다. 대표적으로 NVIDIA는 자신의 GPU에 최적화된 cuBLAS[2] library를, INTEL은 ..

문제 소개 Matrix transpose는 행렬의 행과 열을 교환하여 새로운 행렬을 얻는 operation[2]이다. 주대각축을 중심으로 반사 대칭을 하는 연산으로 Eq 1.과 같은 특징을 만족한다. Matrix transpose는 더하기, 곱하기와 같은 수 계산이 필요없는 operation으로, 단순히 원하는 위치의 데이터를 읽어와 원하는 위치에 쓰기만 하면 된다. 즉 memory operation이 대부분을 차지한다. Matrix transpose를 병렬화할 경우, matrix의 각 element는 다른 element와 관계 없이 독립적으로 읽고 쓰기가 되기에 쉽게 병렬화할 수 있다. 하나의 work-item은 [i,j]-번째 input 행렬의 element를 읽어와 [j,i]-번째 output 행렬..

Compressed Sparse Row Format SpMM - 2 : Sparse Matrix Representation 이전 포스터에서 sparse matrix가 무엇인지를 정의하고 왜 필요한지를 알아보았다. SpMM - 1 : Introduction Sparse Matrix Multiplication Matrix multiplication은 우리가 흔히 아는 다음 그림과 같은 행렬곱.. computing-jhson.tistory.com 저번 포스팅을 통해 sparse matrix를 저장하기 위한 다양한 형식을 배웠으며, 오늘은 CSR, Compressed Sparse Row format을 어떻게 구현하는 지에 대하여 정리할 것이다. 특히 [1]를 참고하여, GPU 디바이스를 통한 CSR 변환 가속화..

이전 포스터에서 sparse matrix가 무엇인지를 정의하고 왜 필요한지를 알아보았다. SpMM - 1 : Introduction Sparse Matrix Multiplication Matrix multiplication은 우리가 흔히 아는 다음 그림과 같은 행렬곱을 의미한다. Matrix multiplication(MM) 연산은 기존의 선형대수 관련 문제 계산, 3D graphics 뿐만 아니라.. computing-jhson.tistory.com Matrix Representation in Memory 메모리에 행렬을 저장할 시, 행렬을 2차원 array로 저장하면 array의 인덱스가 각 행렬성분의 위치, array의 값이 각 행렬성분의 값을 나타낼 수 있어서 편리하다. 이때 sparsity가 0..

Sparse Matrix Multiplication Matrix multiplication은 우리가 흔히 아는 다음 그림과 같은 행렬곱을 의미한다. Matrix multiplication(MM) 연산은 기존의 선형대수 관련 문제 계산, 3D graphics 뿐만 아니라 딥러닝에서도 활발하게 사용되고 있는 중요한 연산이다. 특히 딥러닝에서 convolution layer나 fully connect layer 연산을 MM 연산으로 변환하여 계산하고 있으며, 매우 많은 성능상의 이점을 보이고 있다. MM 연산은 operand인 행렬이 dense인지, sparse 인지에 따라 dense matrix multiplication 또는 sparse matrix multiplication으로 나뉜다. Dense vs...

Merge sort 개념 다음 그림과 같이 Two pass (그림 상의 빨간색 과정과 초록색 과정)로 진행됩니다. 빨간색 과정을 Divide path, 초록색 과정을 combine path라고 하겠습니다. [Divide path] Divide path의 경우 Recursively 현재 array를 두개의 연속된 half-arrays로 분할합니다. half-array의 크기가 1이 될때까지 분할합니다. [Combine paht] Combine path의 경우 Recursively 두개의 half-arrays를 합쳐서 하나의 arrays로 정렬합니다. 이때 두 개의 half-arrays는 항상 정렬되어 있기에 두개의 half-arrays를 쉽게 정렬할 수 있습니다. (항상 정렬되어있는 이유는 귀납적으로, h..