Digital Signal Processing, Parallelization

과거에는 신호처리를 아날로그 방식(하드웨어에서 처리)으로 많이 했었으나, 하드웨어의 발달로 빠르고 자유로운 프로그래밍이 가능한 디지털 방식이 선호되고 있다.

물론 디지털 방식은 아날로그 방식에 비해 속도가 느리므로, 아직도 성능이 중요한 부분은 아날로그 방식을 사용하고 있다. 즉 기술이 발달될 수록 기존 기술은 디지털화가 되고, 성능이 중요한 새로 개발된 기술은 아날로그가 담당하게 된다.

Embeded System이란 단일 목적으로 개발된 (일종의 아날로그) 하드웨어이다.

아날로그 방식 : 상대적으로 저전력, 저비용에 고성능이다. 그러나 한번 완성된 제품은 수정이 불가능하고 개발 기간이 매우 길고, 단일 목적만 가능하다.

디지털 방식 : 상대적으로 고전력, 고비용에 저성능이나 반대로 수정이 언제든지 가능하며 개발 기간이 짧고 다목적으로 사용이 가능하다.

컴퓨터의 성능 향상이 80년대까지는 초당 클락수의 증가로 계속 이루어졌으나, 클락수를 높이는 데에는 기술적인 한계가 발생하여 상용화된 컴퓨터는 3Ghz근처에서 10년째 정체되어 있다.(나노 공정의 한계 인듯하다.)

따라서 컴퓨터의 성능 향상을 위해서는 병렬처리 아키텍쳐를 도입하여야 했다.

그래서 1980년대 부터 이런 병렬처리를 위한 많은 연구가 이루어졌다

간단히 생각해보면 CPU를 10개씩 붙이면 10배의 컴퓨팅 파워가 나오기 때문에 병렬화는 아주 손쉬운 성능 향상으로 보일 수 있다.

그러나 병렬화가된 CPU를 활용하기 위해서는 소프트웨어 또한 아주 높은 병렬도를 가져야하기 때문에 이 또한 쉬운일은 아니다.

모바일이나 노트북 등에서 저전력 시스템을 구현하기 위해 Multi-core를 사용한다. 싱글 코어에서 클락 frequency를 높이거나 superscalar방식을 사용할 경우 상대적으로 전력소모가 더 크다.

병렬화 아키텍쳐

SIMD(Single Instruction Multiple Data) 아키텍쳐 : 고정된 연산자에 여러개의 데이터를 동시에 처리하는 구조
모듈의 값이 저렴하고, 벡터 내적등의 연산에 용이함. 또한 디펜던시가 없는 for문도 vectorize하여, 1개씩 실행하는 게아니라 N개씩 실행되어지므로 N배 빠르게 수행이 가능하다.(컴파일러와 하드웨어가 알아서 디펜던시를 체크해서 벡터라이즈 해줌)

그러나 순서가 정렬되지 않은 데이터에 대해서는 처리할 수 없기 때문에, 이 경우 data alignment overhead가 발생한다. 또한 메모리 속도가 빨라야만 최대 성능이 나오므로 cache hit가 높아야 한다.(VLIW처럼 높은 메모리 band width가 필요)

cray 슈퍼컴퓨터에서 지진, 기상 등을 예측하는 데 쓰임.

Partitioned data path SIMD 아키텍쳐 : SIMD 여러 개를 여러 스레드로 동시에 처리하는 것

VLIW : 한 사이클에 실행 시킬 명령어들 컴파일 시점에서 미리 스케쥴링 해놓는 방식.(최대 8개의 명령어를 동시 실행가능. 대신 32*8bytes/cycle을 위해서는 높은 메모리 band width가 필요함.)

(Superscalar의 소프트웨어 버전이라고 생각. 미리 명령어를 스케줄링 해놓는 offline. complier-time scheduling 임)
VLIW는 일반 PC에서는 사용하기가 어렵다. 왜냐하면 PC의 사양이 달라져 버리면 그 프로그램이 작동하지 않아 다시 포팅해야하기 때문이다.

소프트웨어에의해 컴파일 타임에 스케줄링한다.
코드 스케쥴링 범위가 매우 넓다.
HW가 심플하다.(스케줄링 연산자가 필요 없음)
코드 호환성(Compatibility)이 없어서 매번 하드웨어에 맞게 재컴파일 해야한다.

Superscalar 아키텍쳐 : 여러개의 명령어를 한사이클에서 동시에 실행시키는 구조
슈퍼스칼라의 경우 보통 4개의 명령어를 동시에 실행할 수 있다. 그러나 이를 위해서는 명령어간의 dependency가 없어야만 가능하다. 따라서 항상 4개씩 실행할 수 있는 것이 아니고 상황에 따라 다르다.
(명령어의 실행 단계에서 스케줄링 하는 online, run-time scheduling 임)

하드웨어에 의해 실행시간에 스케줄링한다.
코드 스케줄링 범위가 매우 작은 베이직 블록으로 한정되어있다.
복잡한 HW 스케줄 연산자가 필요하다. - speed bottleneck
코드 호환성이 있어서 재컴파일이 필요없다.

http://talkingaboutme.tistory.com/596

Open MP(Multi Programming) : Shared Memory 방식으로, 소규모 병렬화에서 자주 쓰인다.(일반 PC) 그러나 대규모에서는 shared memory가 부족해지기 때문에 MPI방식을 사용한다.
프로그래밍 방법론적으로는 점진적 병렬화(incremental parallelism)로 설명된다.
점진적 병렬화란 기존에 개발된 소스코드에서 작업이 오래걸리는 for문 등을 멀티 쓰레드로 점차 병렬화시키는 방식이다.

Open MP는 for문들위에 #pragma 같은 선언을 해서 멀티 쓰레드로 작업을 수행한다. 이때 for문이 여러개 중첩되어 있는 경우 반드시 바깥쪽 for문을 병렬화 해야한다. 안쪽에 있는 for문을 병렬화 해버리면, 매번 쓰레드를 생성했다가 소멸시키는 과정이 바깥쪽 for문의 횟수만큼 발생하므로 overhead가 매우 크기 때문이다.

MPI(Message Passing Interface) : 슈퍼컴퓨터등에서 쓰이는 방법. 메모리 공유가 아닌, 메시지 전달 방식으로 프로세스간에 통신을 수행한다.
프로그래밍 방법론적으로는 처음부터 병렬화를 염두하는 프로그래밍에 해당한다.(CUDA Programming도 여기에 해당) 일단 GPU 프로그래밍도 MPI라고 배웠으니 그렇게 기억은 하자..(왜냐하면 인크리멘탈 페러렐리즘이 아니니까..?)

요즘에는 Open MP와 MPI를 섞어서 쓰는 경우도 많다고 한다.
CUDA 프로그래밍에서는 open mp 방식과 MPI방식이 섞여있는 것 같다. 쓰레드 블럭 내부에서는 셰어드 메모리를 이용한 통신이 주요하므로 open mp 방식이나, 쓰레드 블럭 사이에서는 글로벌 메모리를 이용한 아마도 명시적인 메시지 패싱이 필요할 것으로 보인다. 물론 이 또한 메모리 공유이기는 하지만................ 헷갈린다....

프로그래밍의 병렬화 방법

Fine Grain(미세 알갱이) Parallel Processing : micro 레벨에서의 하드웨어 아키텍쳐의 병렬화
Ex) SIMD, Superscalar

Coarse Grain(굵은 알갱이) Parallel Processing : core내지는 컴퓨터 단위의 병렬화(프로세서 레벨)
프로그램에서 dependency가 심할 때 사용함
Ex) shared memory Multi-core, Multi-computer, cluster computer
shared memory는 커뮤니케이션 코스트가 적은 반면, cluster 방식은 인터넷을 통한 통신으로, 커뮤니케이션 코스트가 크다.

Control Level Parallelization : 한 종류의 함수를 1개씩 스레드가 담당함. ex) 덧셈만 하는 쓰레드, 곱셈만 하는 쓰레드
스케일 업이 매우 힘들다.

Data Level Parallelization : 데이터를 쪼개서 1개의 스레드가 같은 함수를 수행함. ex) 100개의 데이터를 100개의 쓰레드가 1개 씩 맡아서 덧셈하고 곱셈함.
스케일 업이 매우 편하다. Massively Parallel Processing에 적합함.

Instruction Level Parallelism : 명령어를 Pipe-line을 이용해 병렬적으로 처리하는 것에서 출발해, VLIW나 superscalar를 통해 명령어를 동시에 처리하는 것까지 포함한다.
특정 application에 상관없이 두루두루 성능향상을 나타낸다. 대신 그만큼 하드웨어적으로 수행할 작업이 많아진다.

http://himskim.egloos.com/viewer/3277331

http://stechstar.tistory.com/9

Micro Level Parallelism : RISC 구조가 아닌 CISC로, FFT나 complex  multiply 같은 작업량이 큰 일을 한 번에 처리해주는 density가 높은 명령어가 포함된 구조.

전용 컴파일러를 개발하기가 매우 어렵다.
해당 연산자를 많이 사용하는 특정 application에서만 성능향상을 나타낸다. 대신 큰 작업에 대해 연산자 하나만 수행하면 되므로, 하드웨어가 수행할 작업량은 적다.

Predicate Instruction : if else나 switch문 같은 분기가 많은 프로그램은 한 사이클에 많은 명령어를 이슈할 수가 없어 성능이 떨어진다. 이때 predicate instruction을 사용하면 분기들을 한번에 이슈시켜 처리가 가능하다. 즉 명령어 레벨에서 if else처리가 가능하다고 생각

Coalesced Memory Access

Coalesce(코얼리스) : GPU는 DRAM 메모리에서 무조건 한 번에 32byte의 메모리를 읽는다. 이 때 필요로하는 메모리가 최대한 붙어있으면 최소한의 사이클로 메모리를 읽을 수 있다. 그러나 만약 4칸씩 떨어진 메모리를 읽을 경우 불필요한 2,3,4 순서의 중간 메모리까지 읽어오므로 훨씬 여러번의 사이클이 필요하다.

http://blog.naver.com/jasoy/110135900435

Bank Conflict : GPU의 Shared Memory는 동시에 여러 스레드에서 엑세스가 가능하도록 보통 16등분이 되어 있다. 각 16조각들을 bank라고 부른다. 이 경우 16개의 스레드가 각각 하나의 bank를 엑세스하면 최대 16개의 쓰레드가 동시에 셰어드 메모리를 엑세스할 수 있다. 그러나 만약 16개의 스레드가 모두 같은 bank를 엑세스 할 경우 시퀀셜한 엑세스가 되어 16배 느려진다. 이를 bank conflict라고 부른다.

http://stackoverflow.com/questions/3841877/what-is-a-bank-conflict-doing-cuda-opencl-programming

http://wiseun.egloos.com/viewer/1615564

http://eaglface.blogspot.kr/2008/09/cuda-shared-memory-bank-conflict.html

병렬화 프레임워크

Map-Reduced : Map형태로 된 데이터를 1개의 속성으로 요약하는 것. 즉 Map을 Reduce해서 1개로 뽑는다.
ex) 사람들의 나이 정보를 Map으로 놓고, 나이의 평균을 구하면 이것이 Map-Reduced

http://blog.naver.com/gkenq/10183561728

http://sqlmvp.kr/140199795866

http://blog.naver.com/gkenq/10183561728

메모리 단편화

내부 단편화 : 메모리를 사용하기 위해 페이징 방식으로 100짜리 메모리를 20짜리로 5등분하여 사용한다. 이때 19짜리를 5개 넣게 되면 5의 공간이 남아있음에도 5짜리 메모리를 할당할 수 없는 현상. 이것은 5등분으로 쪼개어있기 때문에 발생한다

외부 단편화 : 그래서 내부 단편화를 막기위해 간격을 N등분하지 않고, 그때 그때 필요한 만큼만 할당하는 segmentation을 하게된다. 그래서 19씩 5번 할당하고 남는 5의 메모리를 다 쓸 수 있다. 그러나 만약 첫 번째 19짜리 메모리 작업이 끝나서 비어있는 경우 남은 메모리는 19+5이나, 이 역시 붙어있지 않기 때문에 24짜리를 담을 수 없다. 이것이 외부 단편화

이러한 문제를 해결하기위해 집약(Compaction)과 통합(Coalescing)을 해야한다

통합(Coalescing) : 붙어 있는 메모리 조각끼리 합쳐서 1개로 만드는 것

집약(Compaction) : 떨어진 메모리 조각들을 한군데로 모으는 것. 가비지 컬렉션

집약의 경우 수행속도가 상당히 오래걸린다. 따라서 실제 리눅스나 윈도우에서는 페이징과 세그멘테이션을 혼합에서 적절히 사용한다고 한다.

http://abyofasha.blog.me/95480470

http://blog.naver.com/znfgkro1/220039425279

SMP(symmetric multi-processing) 시스템 : 하나의 메모리를 여러개의 프로세서가 공유하는 시스템. 일반적인 PC에서 4개의 cpu가 1개의 메모리를 공유하는 구조이다. 또한 GPU에서 shared 메모리를 여러개의 코어가 공유하는 것도 이에 해당한다.

단, 메모리를 모든 프로세서가 동시에 엑세스 할 수 없기 때문에 병목현상이 생기나, SMP 시스템은 보통 MPP 시스템에 비하여 병렬 프로그래밍이 훨씬 쉽고, 프로세서간 작업 분산(workload balance)을 시키기가 훨씬 용이하지만, 확장성은 MPP에 비하여 취약하다. 또한 많은 사용자가 동시에 데이터베이스에 접근하여 일을 처리하는 OLTP 작업에서도 강점을 보인다.

http://ko.wikipedia.org/wiki/대칭형_다중_처리

Pipe-line Hazrd : 간단히 말해 파이프라인을 수행하다가 발생하는 예외상황을 의미한다.
첫 번째는 동시에 파이프라인에서 메모리 엑세스를 해야할 때,
두 번째는 전단계에서 실행한 명령어와 지금 실행하는 명령어가 디펜던시가 있어 전단계에 의해 데이터가 변해버릴 때,
세 번째는 if else같은 branch 명령어를 처리할 경우 program counter가 점프해야하는데, 그러면 그 다음 명령어를 실행하는게 무의미해질 때

http://talkingaboutme.tistory.com/477

GPU pipe-line Hazard 와 Cache miss

그러나 GPU에서는 pipe-line을 병렬적으로 massively parallel 하게 돌아가므로 파이프라인 해저드가 거의 없다.(쓰레드가 충분히 많아야 함.) 또한 캐시 미스가 발생해도 다른 쓰레드를 돌리면 그만이므로 이 역시 쓰레드가 많으면 문제가 거의 없다.

암달의 법칙 : 프로그램의 병렬화 정도에 따라, 멀티프로세서를 사용하더라도 넘을 수 없는 한계에 대한 법칙.
간단히 말해, 내가 50%의 프로그램을 병렬화 했을 때, 아무리 많은 프로세서를 쓰더라도 약 1.3배이상의 성능 향상이 최대치라는 법칙.

http://himskim.egloos.com/viewer/3277331