Chapter 9

벡터와 행렬

수학 라이브러리

1. 필요성

Example - 행렬의 스칼라 곱

double a[N][M];
for (int i=0;i<N;i++)
	for (int j=0; j<M;j++)
    	a[i][j] *=2.0;
        
for (int j=0; j<M;j++)
	for (int i=0;i<N;i++)
    	a[i][j] /=2.0;

CPU는 메모리에서 직접 값을 가져오지 않음

• 한번에 많은 데이터를 가져와 캐시 메모리에 임시 저장
• 필요한 데이터가 캐시 메모리에 있으면 그 값을 사용
• 필요한 데이터가 캐시 메모리에 없으면 캐시를 비움
• 접근 속도, 용량에 따라 3개의 수준으로 관리

캐시의 종류

• L1: 코어 내부, RAM의 100배 속도
• L2: 코어 내부, RAM의 25배 속도
• L3: 코어 외부 & CPU 내부, RAM의 2배 속도

컴파일러

• 행렬은 메모리에 선형으로 저장되어 있음 -> j가 외부 루프에 있으면 iteration마다 캐시 미스 발생
• 컴파일러가 이를 자동으로 최적화해줄 수 없음 -> 수학 라이브러리의 필요성

기존 방식

• 행렬 A와 B의 곱을 구할 때 A는 행 따라 B는 열 따라 접근
• B 배열이 큰 경우 캐시 미스가 일어남

BLAS

1. 개요

Basic Linear Algebra Subprograms

• FORTRAN 용으로 시작되었으나, C에서도 사용 가능(CBLAS)
• 벡터와 행렬의 계산을 모아 놓은 라이브러리
• 공개된 소스코드를 하드웨어에 맞게 최적화해야 함

FORTRAM 자료형을 고려한 SUBROUTINE이 제공됨

• S: single precision
• D: double precision
• C: single precision complex
• Z: double precision complex

FORTRAN의 배열 저장 방식

• column-major (C는 row-major)
• BLAS는 major 방향 지정 가능 -> C에서도 데이터 변환 없이 사용 가능

2. BLAS의 수준 구성

Level 1

Ax + y -> axpy

• 벡터-벡터 연산
• SAXPY, DAXPY, CAXPY, ZAXPY

Level 2

Generalized Matrix-Vector multiplication -> gemv

• 행렬-벡터 연산
• SGEMV, DGEMV, CGEMV, ZGEMV

Level 3

Generalized Matrix multiplication -> gemm

• 행렬-행렬 연산
• SGEMM, DGEMM, CGEMM, ZGEMM

LAPACK

1. 개요

Linear Algebra PACKage

• FORTRAN으로 작성됨
• 벡터와 행렬은 BLAS를 사용함

최적화된 BLAS를 포함하며 LAPACK과 호환되는 수학 라이브러리

• OpenBLAS
• ATLAS
• 인텔 MKL

2. LAPACK 기능을 제공하는 라이브러리

ATLAS

• Automatically Tuned Linear Algebra Software
• 캐시 메모리와 CPU의 특성을 이용하여 조건을 바꾸며 최적을 조합을 찾는 라이브러리
• 오픈 소스
• 자동 튜닝 시 시간이 오래 걸림

OpenBLAS

• GotoBLAS를 계승하여 각 하드웨어에 맞게 손으로 튜닝하며 최적화한 라이브러리
• 오픈 소스
• ATLAS에 필적하는 성능을 보임

인텔 MKL

• Mathematical Kernel Library
• 인텔 CPU에 맞게 최적화한 라이브러리
• 비공개 소스지만 무료로 전환됨
• LAPACK 이외에도 FFT와 많은 기능 제공