[Parallel Computing] (9) Parallelism

Parallelism을 수행할 수는 종류는 크게 Intruction 기반인 ILP(Instruction Level Parallelism), 실행하는 Task 기반인 Task Parallelism, 데이터를 기반으로 수행하는 Data Parallelism으로 나눌 수 있다.
Task Parallelism 부터 살펴보면 Task Parallelism은 하나의 큰 테스크를 작은 테스크로 나눈 다면, 각 테스크를 병렬적으로 수행하여, 성능을 향상 시키는 방법이다. 그런데, 하나의 테스크를 동시에 수행할 수 있는 작은 테스크들로 나누는 것이 쉽지 않다. 그 이유는 각 동작들이 Dependences를 가지고 있기 때문이다. 예를 들어 'A' Task는 'B' Task가 완료되어야만 수행할 수 있는 경우, 'A'와 'B'는 병렬적으로 수행하기 어렵다. 많은 Application들이 병렬적으로 수행할 수 있는 Task들이 많지 않다.
Data Parallelism은 데이터 연산을 수행할 때, 데이터의 양이 많다면 이를 나눠서 처리하는 것이다.
예를 들어 크기가 8인 배열 'A'와 'B'의 합을 구하는 과정이라면, 8번의 합 연산이 이뤄진다. 이 때,  2개의 Core가 존재한다면 각 Core가 4번의 연산을 나눠서 수행하는 것이다. Task Paralleism과 달리 데이터 연산에서 데이터의 크기가 크다면 더 많이 병렬화를 수행할 수 있다.
4번의 연산은 동일한 종류와 크기를 가지는 데이터에 대한 연산을 수행하는 것이다. 예를 들어 이러한 연산이 덧셈이었다면, 4번의 덧셈 Instruction이 생성되어 수행된다. 벡터 관점에서 보면 이는 4번의 Scalar 덧셈 연산이다. 그런데 동일한 종류과 크기를 가지므로 Vector로 생각할 수 있고, 이는 1번의 Vector 덧셈 연산으로 치환된다. 그러므로 한 개의 Instruction으로 vector의 연산을 표현할 수 있다.  한 개의 Instruction으로 여러 데이터를 처리한다고 하여 SIMD(Single Instruction Multiple Data)라고 표현한다. 일반적으로 컴파일러가 코드를 해석하여 자동으로 vector로 만들어 준다. Hardware적으로 vector로 수행하기 위한 vector register가 구비되어야 한다.
실제로 연산을 Core에 나눠주려면 각 Core에 어떤 연산을 해야하는 지 알려줘야 한다. 예를 들어 8번의 연산을 수행하는 Loop문이 있다면, 0,1,2,3은 Core1에 4,5,6,7은 Core2에 할당해야 한다. 이 때, 각 Core마다 다른 영역의 연산을 수행할 수 있도록 Code를 작성해야 한다. 가장 쉬운 방법은 Loop문의 Range를 0~3, 4~7과 같이 숫자로 명기하는 것이다. 그런데 이 방법을 사용하면 Core마다 다른 프로그램을 작성해야 하므로 번거롭다. 이를 해결하기 위한 방법으로 Core를 식별할 수 있는 ID를 활용하는 것이다. 예를 들어 Core1의 ID는 0, Core2의 ID는 1이라 하고, Core ID는 C_id의 변수로 나타낼 수 있다면, Loop의 범위를 C_id*4 < xx < (C_id+1)*4로 표현할 수 있다. 그러면 Core1은 0~3, Cire2는 4~7로 표현할 수 있다. 이렇게 동일한 프로그램으로 여러 데이터를 처리하는 것을 SPMD(Single Program Multiple Data)라 한다.
ILP(instruction Level Paralleism)은 병렬적으로 수행할 수 있는 Instruction을 찾아 동시에 수행하는 것이다. 이를 지원하기 위한 대표적인 방법이 Superscalar 이다. Superscalar는 동시에 여러 Instruction을 Fetch 및 Decoding 할 수 있다. (동시에 수행할 수 있는 Instruction의 개수를 issue-width라 한다.) 그런데, 일반적으로 하나의 application에서 병렬적으로 수행할 수 있는 Intruction의 개수는 크지 않다. 그래서 하나의 Application에서의 ILP로 인한 성능 향상이 크지 않았다. 그렇다면 '하나가 아니라 여러 Application을 동시에 수행하면 이 부족한 ILP를 채울 수 있지 않을 까'라는 고민에서 나온 것이 TLP(Thread-Level Parallelism)이다. 각 Thread 마다 동시에 수행할 수 있는 Instruction들 모아서 동시에 실행하여 처리량(Throguthput)을 높이는 것이다. 각 Thread들로부터 나온 Instruction들은 서로 dependences가 없다는 것이 보장되어야 한다.
Superscalar와 같은 ILP 방식은 Fetch/Decode가 동시에 수행되므로, 여러 개의 동일한 하드웨어가 필요하다. 그러나 TLP는 Thread관리를 위한 Hardware가 추가 될 뿐, Functional Unit는 기존과 동일하게 사용가능하다.  
TLP 방식을 살펴보면, 예를 들어 여기에 'A'와 'B' 쓰레드가 동시에 수행된다고 하자. 먼저 'A'를 수행하는 데,  'A'가 특정 시점에 dependences 제약으로 더 이상 Instruction을 수행할 수 없었다. 그래서 특정 시점에 'A'로는 더이상 Instruction slop을 채우지 못하는 데, 'B'에는 수행 가능한 Instruction이 있다면 이를 수행한다. 시간(혹은 Cycle)에 따른 Thread Paralleism을 Vertical Multithreading이라고 한다. 각 시간(혹은 Cycle)마다 서로 다른 Thread 전환을 통해서 가능한 많은 lnstruction slot을 채우는 방법이다. 특정 Thread가 긴 시간동안 Instruction을 수행하지 못할 때, 다른 Thread가 Instruction을 수행하므로 처리량을 높인다. Thread 전환을 수행하는 시점에 따라 2가지 방법으로 나뉜다. 하나(Fine-grained mutlithreading)는 매 Cycle마다 Thread 전환을 수행하는 것이고, 다른 하나(Coarse-grained multithreading)는 특정 Thread가 긴 시간동안 더 이상 수행될 수 없는 상황에서 전환하는 것이다.  Thread switch는 os가 수행하며, 추가적인 memory 접근이 필요하다.
Superscalar 방식에 TLP를 적용하면 더 효율적인 처리가 가능하다. 예를 들어, 동시에 4개를 처리할 수 있는 Superscalar 방식이 있다고 가정하자. 이 때,  'A'와 'B' 쓰레드가 동시에 수행되고 있고, Vertical Multithreading 방식을 사용한다고 가정하자. 이 때, 현재 시간(Cycle)에 'A'가 4개의 Instruction slop 중 2개를 채우고,  다음 시간(Cycle)에 'B'가 4개 중 2개를 채웠다. 이런 경우, 현재 시점의 2개, 다음 시점에 2개의 Instruction slot이 비게 된다. 이를 더 효율적으로 사용하기 위하여 'B'의 2개를 앞당겨 현재 시점에 'A'와 동시에 수행할 수 있다면 4개의 Slot을 모두 채울 수 있을 것이다. 이러한 방법은 SMT(Simultaneous Multithreading) 방식이라고 한다. 위의 Vertical Multithreading은 시간 관점에서 vertical waste를 줄이는 것이라고 하면, SMT는 vertical waste 뿐만아니라 instruction slot 관점에서의 horizontal waste도 줄일 수 있다. Superscalar에 존재하는 Hardware를 사용하면 적은 양의 Hardware 추가만으로 SMT를 지원할 수 있다. 또한 SMT는 TLP를 활용하므로 Data Parallelism을 활용한 테스크에는 적합하지 않다. 그 이유는 Data Paralleism은 동일한 연산을 다른 데이터로 수행하므로 서로 수행하는 Function Unit이 같다. TLP의 컨셉 자체가 이 Function Unit을 활용하지 못할 때, 다른 Thread에서 사용하여 속도를 높이는 것이 때문이다.