컴퓨터 구조 6(병렬 프로그래밍, GPU&CPU 비교)

Parallel Programming

• 병렬 프로그래밍은 병렬 소프트웨어 개발 자체가 문제입니다.
• 중요한 성능 향상을 얻기 위해 병렬화된 소프트웨어를 개발해야 합니다.
  • 그렇지 않으면 더 빠른 단일 프로세서를 사용하는 것이 더 쉽기 때문입니다.

병렬 프로그래밍을 만드는 것은 어려운 작업입니다. 주요 어려움은 다음과 같습니다.

1. 분할 (매핑): 병렬화된 작업을 어떻게 나누고 할당할 것인가
   • 작업을 작은 작업 단위로 나누고 병렬로 실행할 수 있는 단위로 할당해야 합니다.
   • 이 단계에서 프로그래머는 작업을 적절히 분할하여 병렬로 실행할 수 있는 부분을 식별해야 합니다.
2. 조정 (로드 밸런싱, 동기화): 작업의 조정과 협업
   • 병렬로 실행되는 작업 간의 균형을 맞추기 위해 작업을 조정해야 합니다.
   • 작업 간의 상호작용이 필요한 경우 동기화를 통해 작업의 순서를 조정하고 충돌을 방지해야 합니다.
3. 통신 부하: 데이터 이동으로 인한 통신 비용
   • 병렬로 실행되는 작업 간에 데이터를 전송해야 하는 경우 통신 비용이 발생합니다.
   • 데이터 이동이 필요한 경우, 데이터 전송 및 동기화에 따른 부하가 발생할 수 있습니다.

이러한 어려움들로 인해 병렬 프로그래밍은 단일 프로세서보다 훨씬 복잡하며, 프로그래머는 이러한 어려움들을 극복하기 위해 전문적인 지식과 기술을 보유해야 합니다.

Amdahl's Law

순차적인 부분이 속도 향상을 제한할 수 있다는 원리입니다.
예를 들어, 100개의 프로세서를 사용하여 90배의 속도 향상을 얻는 경우를 생각해봅시다.

Amdahl의 법칙에 따르면, 전체 실행 시간(Total Time)은 병렬화된 부분과 순차적인 부분으로 나눌 수 있습니다. 병렬화된 부분은 병렬로 실행되어 속도 향상을 가져오는 반면, 순차적인 부분은 병렬화가 불가능하여 원래대로 실행됩니다.

$T_(new) = \frac{T_(parallelizable)}{100 + T_(sequentialO)}$

여기서 $T_{new}$는 새로운 병렬화된 실행 시간, $T_{parallelizable}$은 병렬화 가능한 부분의 실행 시간, $T_{sequential}$은 순차적인 부분의 실행 시간입니다.

위 예시에서 90배의 속도 향상을 얻으려면, 아래 식을 만족해야 합니다:

$Speedup = \frac{1}{((1 - F_{parallelizable}) + (\frac{F_{parallelizable}}{100}))} = 90$

이를 풀면 $F_{parallelizable}$, 즉 병렬화 가능한 부분의 비율은 0.999가 됩니다.

즉, 원래 실행 시간에서 병렬화 가능한 부분은 원래 시간의 0.1%에 해당해야 합니다. 순차적인 부분이 전체 실행 시간의 일부로 작아질수록 병렬화에 의한 속도 향상이 더 크게 나타날 수 있습니다.

Shared Memory

• 하드웨어가 모든 프로세서를 위한 단일 물리적 주소 공간을 제공하는 구조입니다.
• SMP 시스템에서는 모든 프로세서가 동일한 물리적 주소 공간에 접근할 수 있습니다.

공유 변수를 동기화하기 위해 잠금(lock)을 사용하여 공유 메모리에 대한 접근을 동기화합니다. 이렇게 함으로써 여러 프로세서 간의 공유 데이터의 일관성을 유지할 수 있습니다.

공유 메모리 시스템에서는 메모리 접근 시간이 중요한 요소입니다. 메모리에 접근하는 속도는 UMA(Uniform Memory Access)와 NUMA(Non-Uniform Memory Access) 두 가지 형태로 나뉩니다.

• UMA(Uniform Memory Access): 모든 프로세서가 동일한 메모리 액세스 시간을 갖는 형태입니다. 모든 프로세서 간의 메모리 액세스 지연이 동일하며 일관성이 유지됩니다.
• NUMA(Non-Uniform Memory Access): 프로세서 간에 메모리 액세스 지연이 다를 수 있는 형태입니다. 각 프로세서에 지역 메모리가 할당되어 해당 프로세서가 직접 액세스할 수 있는 메모리에 대해서는 지연 시간이 더 짧습니다. 그러나 다른 프로세서의 메모리에 액세스할 때는 지연 시간이 더 길어질 수 있습니다.

공유 메모리 다중 처리기 시스템은 병렬 프로그래밍을 위해 사용되며, 공유 데이터에 대한 효율적인 동시성 제어와 메모리 액세스의 성능을 고려해야 합니다.

장점 : 프로세서간 통신(정보교환)이 빠름
단점 : data race

SMP를 위한 프로그래밍은 주로 스레드 프로그래밍(Thread Programming)을 사용

• 스레드 프로그래밍은 논리적 실행 단위인 스레드(Thread)를 기반
• 스레드는 프로세스보다 작은 단위로, 하나의 프로세스 내에서 여러 개의 스레드를 가질 수 있음
• 또한 스레드는 프로세스의 메모리 공간을 공유합니다.

POSIX 스레드(Pthread)

• Pthread는 Portable Operating System Interface의 스레드 부분을 의미하며, IEEE 표준
• POSIX 스레드는 UNIX, Linux, Solaris, Mac OS X, MS Windows 등 다양한 운영체제에서 지원
• C 언어를 기반으로 하는 API를 제공하며, "pthread_xxx()"와 같은 형태로 스레드의 생성 및 조작을 수행

❗️SMP를 위한 프로그래밍

• 여러 스레드를 활용하여 작업을 동시에 실행
• 스레드 간의 동기화와 메모리 공유를 적절히 관리
  • 이를 통해 병렬성을 활용하여 SMP 시스템에서 효율적인 프로그램을 개발

tlp : thread

• c는 라이브러리를 통해 멀티쓰레드 지원
• function은 caller와 callee가 부름(싱글쓰레드 내에서 동작)
  • calller와 callee가 병렬적으로 동작할 수 없음
• 멀티쓰레드: 동작을 할때 논리적으로 concurrent(병행 처리), 동작이 거의 동시에 일어난다 봄

위 코드는 pthread를 사용하여 병렬적으로 작업을 수행하는 예제입니다. 주어진 배열 A와 B의 요소를 스레드를 통해 합산하여 배열 S에 저장하는 작업을 수행합니다.

• 코드 설명:

1. pthread.h와 다른 필요한 헤더 파일들을 포함합니다.
2. 배열 S, A, B를` 외부에서 선언합니다.
3. TaskCode라는 함수는 스레드에서 실행되는 작업을 정의합니다. 인자로 받은 tid 값을 기반으로 배열 A와 B의 일부 요소를 합산하여 배열 S에 저장합니다.
4. main 함수에서는 4개의 스레드를 생성하고 실행합니다.
5. 스레드 생성 시에는 TaskCode 함수를 실행하는 스레드를 생성하고, 인자로는 스레드의 인덱스를 전달합니다.
6. 모든 스레드가 작업을 완료할 때까지 기다립니다.
7. 작업이 완료되면 프로그램을 종료합니다.

이 예제는 4개의 스레드를 사용하여 작업을 병렬적으로 처리하며, 각 스레드는 배열 A와 B의 일부 요소를 합산하여 배열 S에 저장합니다. 스레드 간의 작업은 동시에 수행되며, 결과는 배열 S에 저장됩니다. 추가적으로 TaskCode는 매개변수를 받아 25개씩 돌립니다. 이를 통해 4개의 workerthread가 25개씩 for문을 병렬로 수행하게 됩니다.

예시: 합 구하기 (Sum Reduction)

• 여러 개의 부분 문제 또는 데이터를 조합하여 더 큰 문제 또는 결과를 생성하는 과정을 의미
  100,000개의 수를 100개의 프로세서 UMA(모든 프로세서 동일 시간 할당)에서 합산합니다.
• 각 프로세서는 ID로 구분됩니다: 0 ≤ myid ≤ 99
• 각 프로세서당 1,000개의 수를 할당받습니다.

단계 1: 각 프로세서에서 초기 합 구하기
sum[myid] = 0;
for (i = 1000_myid; i<1000_(myid+1); i++)
sum[myid] = sum[myid] + totalData[i];

단계 2: 부분 합을 더합니다.

• Reduction: 분할 정복 방법 사용
• 반의 프로세서는 짝을 이루어 더하고, 그 다음에는 4분의 1, ...
• 감소하는 단계마다 동기화가 필요합니다.

for(int stride=8/2; stride>0; stride/=2) { 
    if (myid < stride) 
        sum[myid] += sum[myid + stride]; 
    synch();
}

위 사진의 step과 현재 설명되는 단계는 다른 이야기임. 여기서 step은 시간의 흐름을 나타냄

이 코드는 프로세서들이 부분 합을 서로 더해나가는 과정을 구현합니다.
stride라는 변수는 반씩 줄어들며 각 Reduction 단계의 크기를 결정합니다.
반복문은 stride의 초기값을 전체 프로세서 수의 절반으로 설정하고, stride이 0보다 큰 동안 반복됩니다.
반복할 때마다 현재 프로세서의 ID(myid)가 stride보다 작은 경우에만 다음 프로세서와의 합을 구해 현재 부분 합에 더합니다.
그리고 synch() 함수를 호출하여 동기화를 수행합니다. synch를 통해 값을 보장할 수 있습니다.
이렇게 반복문이 진행되면서 프로세서들은 짝을 이루어 부분 합을 더해가며 Reduction을 수행하게 됩니다. stride 값이 절반씩 줄어들면서 Reduction의 크기가 점차 감소하게 됩니다.

❓N개의 프로세서가 있다면 위의 분할정복을 사용했을때 결과가 나올때까지 걸리는 시간 복잡도?
$$log_2 N$$

Message Passing

Message Passing는 병렬 컴퓨팅에서 사용되는 방법 중 하나로, 다른 프로세서들 간에 메시지를 주고받는 방식을 의미합니다.

• 메시지 패싱은 각 프로세서가 독립적인 개별 물리적 주소 공간을 가짐
• 하드웨어적으로 프로세서들 간에 메시지를 송수신할 수 있는 기능을 제공
• 메모리가 share되지는 않음

Loosely Coupled Clusters

Loosely Coupled Clusters (느슨하게 결합된 클러스터)는 독립적인 컴퓨터들의 네트워크로 구성된 시스템입니다. 각각의 컴퓨터는 개별적인 메모리와 운영체제를 가지고 있으며, I/O 시스템을 통해 연결됩니다. 이러한 연결은 이더넷/스위치, 인터넷과 같은 기술을 사용할 수 있습니다.

• 느슨하게 결합된 클러스터는 독립적인 작업을 수행하는 애플리케이션에 적합합니다.
  • 예를 들어 웹 서버, 데이터베이스 등이 해당됩니다. 각 컴퓨터는 독립적으로 작업을 수행하며, 필요한 경우에만 통신하여 데이터를 교환할 수 있습니다.

장점

• 높은 가용성, 확장성 및 저렴한 비용
  • 각 컴퓨터는 독립적으로 운영되기 때문에 하나의 컴퓨터가 장애가 발생하더라도 전체 시스템이 계속 작동할 수 있습니다.
  • 필요에 따라 클러스터를 확장할 수 있으며, 비용면에서도 비교적 저렴한 솔루션입니다.

단점

• 클러스터의 관리 비용이 증가할 수 있으며, 상대적으로 연결 대역폭이 낮을 수 있습니다.
  • 이는 클러스터 내부의 프로세서와 메모리 간의 대역폭에 비해 상대적으로 작은 데이터 교환 대역폭을 의미합니다.
  • 이로 인해 일부 작업에서는 성능 저하가 발생할 수 있습니다.

MPI (Message Passing Interface)

분산 메모리 시스템에서 병렬 프로그래밍을 지원하기 위한 통신 프로토콜입니다.
MPI는 고성능 컴퓨팅(High-Performance Computing) 분야에서 널리 사용됩니다.

MPI는 병렬 컴퓨팅 환경에서 다수의 프로세서 간에 메시지를 주고받을 수 있도록 하는 통신 인터페이스를 제공합니다. MPI를 사용하면 프로세서들 간에 데이터를 교환하고 작업을 동기화할 수 있습니다.

MPI는 다양한 통신 함수를 제공하는데, 그 중 일부는 다음과 같습니다:

• MPI_Send(): 메시지를 다른 프로세서로 전송합니다.
• MPI_Recv(): 다른 프로세서로부터 메시지를 수신합니다.
• MPI_Broadcast(): 하나의 프로세서가 보낸 메시지를 모든 프로세서에게 전달합니다.

이 외에도 MPI는 수신 대기, 동기화, 동적 프로세스 관리 등 다양한 기능을 제공합니다. MPI를 사용하면 병렬 알고리즘과 응용 프로그램을 개발하고 분산 메모리 시스템에서 효율적으로 실행할 수 있습니다.

#include <mpi.h>
#include <stdio.h>
#include <string.h>
#define TAG 0

int main(int argc, char *argv[]) {
    int buff[25], numprocs, myid;
    int i;
    MPI_Status stat;
    MPI_Init(&argc, &argv);

    // numprocs in our example = 4
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

    // gets processor id, which is called 'rank'
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);

    // Usually, processor 0 plays the role of master
    if (myid == 0) {
        int S[100], A[100], B[100];

        /* assume A and B are already initialized before sending */
        for (i = 1; i < numprocs; i++) {
            MPI_Send(A, 25, MPI_INT, i, TAG, MPI_COMM_WORLD);
            MPI_Send(B, 25, MPI_INT, i, TAG, MPI_COMM_WORLD);
        }

        int offset = 0;
        for (i = 1; i < numprocs; i++) {
            MPI_Recv(&S[offset], 25, MPI_INT, i, TAG, MPI_COMM_WORLD, &stat);
            offset = offset + 25;
        }
    } else {
        int Sum[25];
        int A[25], B[25]; // Local arrays for each processor

        MPI_Recv(A, 25, MPI_INT, 0, TAG, MPI_COMM_WORLD, &stat);
        MPI_Recv(B, 25, MPI_INT, 0, TAG, MPI_COMM_WORLD, &stat);

        for (i = 0; i < 25; i++)
            Sum[i] = A[i] + B[i];

        MPI_Send(Sum, 25, MPI_INT, 0, TAG, MPI_COMM_WORLD);
    }

    MPI_Finalize();
    return 0;
}

코드는 MPI를 사용하여 메시지 패싱을 구현한 예시입니다. 주어진 코드를 설명하겠습니다.

1. MPI 라이브러리를 포함하고 필요한 헤더 파일을 포함합니다.
2. main 함수를 정의하고, MPI 초기화를 수행합니다.
3. MPI_Comm_size 함수를 호출하여 전체 프로세서의 수(numprocs)를 얻습니다.
4. MPI_Comm_rank 함수를 호출하여 현재 프로세서의 ID(myid)를 얻습니다.
5. myid가 0인 경우, 마스터 프로세서(프로세서 0)로 동작합니다.
   • 배열 S, A, B를 초기화하고, A와 B를 다른 프로세서에 전송합니다.(MPI_SEND)
     • 저장소를 공유하지 않기에 타 프로세서가 a,b를 알 수 있도록 전송
   • offset을 사용하여 받은 부분 합 S를 적절한 위치에 저장합니다.
6. myid가 0이 아닌 경우, 일반적인 작업 프로세서로 동작합니다.
   • A와 B를 마스터 프로세서로부터 수신합니다.
   • 받은 A와 B를 이용하여 부분 합 Sum을 계산합니다.
   • 계산한 부분 합 Sum을 마스터 프로세서로 전송합니다.
7. MPI_Finalize 함수를 호출하여 MPI 사용을 종료하고, 프로그램을 종료합니다.

이 코드는 마스터-작업자 모델을 사용하여 부분 합을 계산하는 예시입니다. 마스터 프로세서가 배열 A와 B를 나누어 작업 프로세서들에게 전송하고, 작업 프로세서들은 받은 배열을 이용하여 부분 합을 계산하고 마스터 프로세서에게 전송합니다. 마스터 프로세서는 받은 부분 합들을 모아 최종 합을 계산합니다.

1. MPI_Send:

   • 첫 번째 매개변수: 데이터를 보내는 버퍼의 주소를 지정합니다. 일반적으로 배열이나 포인터를 전달합니다.
   • 두 번째 매개변수: 보내는 데이터의 크기를 지정합니다. 전송하려는 데이터의 요소 수를 기반으로 합니다.
   • 세 번째 매개변수: 데이터의 타입을 지정합니다. MPI_Datatype을 사용하여 지정할 수 있습니다.
   • 네 번째 매개변수: 메시지를 받을 프로세서의 랭크(rank)를 지정합니다.
   • 다섯 번째 매개변수: 메시지의 태그(tag)를 지정합니다. 일반적으로 0으로 지정합니다.
   • 여섯 번째 매개변수: 메시지를 보낼 통신 컨텍스트(context)를 지정합니다. 보통은 MPI_COMM_WORLD를 사용합니다.

2. MPI_Recv:

   • 첫 번째 매개변수: 데이터를 받을 버퍼의 주소를 지정합니다. 일반적으로 배열이나 포인터를 전달합니다.
   • 두 번째 매개변수: 받을 데이터의 크기를 지정합니다. 수신할 데이터의 요소 수를 기반으로 합니다.
   • 세 번째 매개변수: 데이터의 타입을 지정합니다. MPI_Datatype을 사용하여 지정할 수 있습니다.
   • 네 번째 매개변수: 메시지를 보낸 프로세서의 랭크(rank)를 지정합니다.
   • 다섯 번째 매개변수: 메시지의 태그(tag)를 지정합니다. 일반적으로 0으로 지정합니다.
   • 여섯 번째 매개변수: 메시지를 받을 통신 컨텍스트(context)를 지정합니다. 보통은 MPI_COMM_WORLD를 사용합니다.
   • 일곱 번째 매개변수: 수신 상태 정보를 저장하기 위한 MPI_Status 구조체를 전달합니다.

100개의 프로세서에서의 합계 축소(sum reduction) 예시

1단계: 숫자 청크 분배

• 각 프로세서에게 100개의 숫자 청크를 분배합니다. 각 프로세서는 크기가 1000인 청크를 받습니다.
• 각 프로세서는 자신이 받은 숫자 청크에 대해 부분 합계를 계산합니다

int sum = 0;
for (i = 0; i < 1000; i++) //0부터 청크의 크기
    sum = sum + myData[i];

2단계: 축소

• 반의 프로세서는 숫자를 보내고, 나머지 반은 숫자를 받아서 더합니다.
• 프로세서의 수가 절반으로 줄어들 때까지 아래 과정을 반복합니다:
  • 절반의 프로세서는 숫자를 보내고, 나머지 절반의 프로세서는 숫자를 받아서 더합니다

send()와 receive() 연산을 사용하여 수행되는 합계 축소(sum reduction)의 예시입니다:

limit = 100;
half = 100;

do {
    half = (half + 1) / 2; // send와 receive 사이의 분할선

    if (myid >= half && myid < limit)
        send(myid - half, sum);

    if (myid < (limit / 2))
        sum = sum + receive();

    limit = half; // 보내는 프로세서의 상한값 업데이트

} while (half == 1); // 최종 합계로 종료

위 코드는 send()와 receive() 연산을 사용하여 합계 축소를 수행합니다. 반복문을 사용하여 프로세서의 수를 절반으로 줄여가면서 합계를 계산합니다. 코드의 동작은 다음과 같습니다:

1. 초기 설정:
   • limit 변수는 100으로 설정됩니다.
   • half 변수는 100으로 설정됩니다.
2. 반복문 수행:
   • half 변수를 (half + 1) / 2로 업데이트하여 send와 receive 사이의 분할선을 결정합니다.
   • 만약 myid가 half 이상이고 limit 미만인 경우, (myid - half)에게 sum 값을 보냅니다.
     • 반 쪼개서 뒤의 값을 앞의 해당하는 값에 전달
   • 만약 myid가 limit/2보다 작은 경우, receive()를 통해 값을 받아서 sum에 더합니다.
   • limit 변수를 half로 업데이트하여 보내는 프로세서의 상한값을 갱신합니다.
3. 종료 조건:
   • half가 1인 경우, 최종 합계로 종료합니다.

send()와 receive() 연산은 또한 동기화를 제공합니다. 또한, send/receive 연산이 합계 계산과 유사한 시간이 소요된다고 가정합니다. 이를 통해 각 프로세서가 부분 합계를 교환하여 최종적으로 전체 합계를 얻을 수 있습니다.

여기선 shared memory에서 처럼 synch가 필요없음

• send, receive api가 내부적으로 synch를 call하기 떄문

(하드웨어) 멀티스레딩(Multithreading)

멀티스레딩은 동시에 여러 개의 실행 스레드를 수행하는 것을 의미합니다. 이를 위해 레지스터, 프로그램 카운터(PC) 등을 복제하고, 스레드 간에 빠른 전환을 수행합니다.

1. 세부 분류: 세부 분류는 미세 그레인 멀티스레딩(Fine-grain multithreading)과 거친 그레인 멀티스레딩(Coarse-grain multithreading)으로 나눌 수 있습니다.
   (1) 미세 그레인 멀티스레딩(Fine-grain multithreading):

   • 한 사이클마다 스레드 전환을 수행합니다.
   • 명령어 실행을 교차(interleave)하여 실행합니다.
   • 한 스레드가 멈추면 다른 스레드를 실행합니다.

   (2) 거친 그레인 멀티스레딩(Coarse-grain multithreading):

   • 긴 지연(예: L2 캐시 미스(L2-cache miss)) 발생 시에만 스레드를 전환합니다.
   • 하드웨어를 단순화하지만, 짧은 지연(예: 데이터 위험)은 숨기지 못합니다.

미세 그레인 멀티스레딩은 각 사이클마다 스레드를 전환하고 명령어 실행을 교차시키는 방식으로 작동합니다. 한 스레드가 지연되면 다른 스레드를 실행하여 처리 능력을 최대화할 수 있습니다. 그러나 미세 그레인 멀티스레딩은 데이터 위험과 같은 짧은 지연을 숨기지 못합니다.

반면, 거친 그레인 멀티스레딩은 긴 지연이 발생할 때만 스레드를 전환합니다. 이렇게 하면 하드웨어를 단순화할 수 있으며, 주로 오랜 지연이 발생하는 I/O 연산 등에 적합합니다. 그러나 짧은 지연은 숨기지 못합니다.

멀티스레딩은 병렬 처리를 향상시키는 하드웨어 기법 중 하나로 사용되며, 다중 코어 프로세서 및 멀티스레드 프로세서에서 널리 사용됩니다.

동시 멀티스레딩(Simultaneous Multithreading, STM)

여러 개의 명령어가 동적으로 스케줄링되는 다중 발행(dynamically scheduled) 프로세서에서 사용되는 기술

1. 다중 스레드에서 명령어 스케줄링:
   • 여러 스레드로부터의 명령어를 스케줄링합니다.
   • 독립적인 스레드로부터의 명령어는 함수 유닛(function units)이 사용 가능한 경우 실행됩니다.
   • 스레드 내의 의존성은 스케줄링과 레지스터 이름 변경(register renaming)을 통해 처리됩니다.
2. 예시: Intel Pentium-4 HT
   • 두 개의 하드웨어 스레드:
     • 복제된 레지스터를 가지고 있습니다.
     • 함수 유닛과 캐시는 공유됩니다.

STM은 동시에 여러 스레드를 실행하여 처리 능력을 향상시키는 기술입니다.
각 스레드는 독립적으로 실행되지만 하드웨어 자원을 공유하므로 효율적인 병렬 처리가 가능합니다.

멀티스레딩의 미래

아직 진화 중이며, 그 생존 여부는 다양한 요인에 달려 있습니다.

멀티스레딩의 미래에 대한 고려 사항과 잠재적인 동향

1. 단순화된 마이크로아키텍처:

   • 전력 소비 고려 사항: 단순화된 마이크로아키텍처가 선호됩니다.
   • 더 단순한 형태의 멀티스레딩: 전력 효율성을 향상시키기 위해 단순한 형태의 멀티스레딩 기술이 발전할 수 있습니다.

2. 캐시 미스 지연 허용:

   • 캐시 미스 지연을 용인하는 방법: 스레드 전환은 가장 효과적인 방법일 수 있습니다. 캐시 미스가 발생하면 스레드를 전환하여 처리 지연을 숨길 수 있습니다.

3. 다중 단순 코어의 자원 공유:

   • 다중 단순 코어의 자원 공유: 여러 개의 단순한 코어가 자원을 더 효과적으로 공유할 수 있습니다. 이를 통해 멀티스레딩의 효율성을 높일 수 있습니다.

멀티스레딩의 미래는 기술의 발전과 시장 요구에 따라 변화할 것으로 예상됩니다. 전력 효율성, 성능 개선, 캐시 미스 처리 등의 측면에서 계속 발전할 것이며, 새로운 형태의 멀티스레딩 기술이 등장할 수도 있습니다.

Instruction and Data Streams (명령어 및 데이터 스트림)

명령어 및 데이터 스트림에 대한 대안적인 분류 방법 중 일부를 살펴보겠습니다.

데이터 병렬성(Data-parallelism)

SPMD: Single Program Multiple Data

• MIMD(Multiple Instruction Multiple Data) 컴퓨터에서의 병렬 프로그램
• 서로 다른 프로세서에 대한 조건부 코드 사용
• 프로세서 또는 스레드의 ID(PID 또는 threadID)를 사용

SPMD는 MIMD 컴퓨터에서 사용되는 병렬 처리를 수행하는 방식 중 하나입니다.

• 프로세서가 동일한 프로그램을 실행하지만, 각각의 프로세서는 다른 데이터를 처리
• SPMD 모델에서는 조건부 코드를 사용하여 각 프로세서가 자신의 데이터를 처리하도록 제어
  • 이를 위해 프로세서 또는 스레드의 ID(PID 또는 threadID)를 사용하여 프로그램 내에서 분기 및 선택을 수행할 수 있습니다.

SIMD (Single Instruction Multiple Data)

데이터의 벡터에 대해 요소별(element-wise) 연산을 수행하는 기술입니다. 주로 x86 아키텍처에서 사용되는 MMX 및 SSE(Streaming SIMD Extensions) 명령어들이 이에 해당합니다.

1. 벡터 단위 연산:

   • 데이터의 벡터에 대해 요소별로 연산을 수행합니다.
   • 128비트 넓이의 레지스터에 여러 데이터 요소를 저장합니다.
     • 즉 큰 길이의 연산을 하는데 128bit 내에는 여러 데이터가 있고 해당 데이터들의 상대적 위치는 같기에 벡터연산을 통해 128bit + 128bit를 수행하면 해당 bit 내의 여러 데이터들이 한번에 덧셈연산을 마치게 됨

2. 모든 프로세서가 동시에 동일한 명령어를 실행:

   • 각각 다른 데이터 주소 등을 가지면서 동일한 명령어를 실행합니다.

장점:

• 명령어 제어 하드웨어가 감소하여 복잡성이 줄어듭니다.
• 프로그램 코드 크기가 줄어듭니다.
• 동기화가 간소화됩니다.

단점:

• 프로그래밍이 다소 어렵습니다.
• 컴파일러 지원이 필요하거나 어셈블리 프로그래밍이 필요할 수 있습니다.

SIMD는 데이터 병렬성이 높은 응용 프로그램에 가장 적합합니다. 이러한 응용 프로그램에서는 SIMD를 통해 성능을 향상시킬 수 있습니다.

벡터 프로세서(Vector Processors) 특징

1. 고도로 파이프라인화된 기능 유닛:

-   벡터 프로세서는 기능 유닛을 고도로 파이프라인화하여 동시에 여러 연산을 수행할 수 있습니다.

2. 벡터 레지스터와 기능 유닛 간의 데이터 스트림:

   • 데이터는 메모리에서 벡터 레지스터로 수집되고, 결과는 벡터 레지스터에서 메모리로 저장됩니다.
   • 벡터 레지스터와 기능 유닛 사이에서 데이터 스트림이 이루어집니다.

3. MIPS의 벡터 확장 예시:

   • MIPS에 벡터 확장이 추가된 예시입니다.
   • 32개의 64-element 레지스터(64비트 요소)를 가지고 있습니다.
   • 벡터 명령어를 사용하여 벡터 로드/스토어, 벡터 덧셈 등의 연산을 수행할 수 있습니다.

벡터 프로세서는 명령어 추출 대역폭을 크게 줄이는 효과를 가져옵니다. 벡터 연산을 통해 한 번의 명령어로 다수의 데이터를 처리할 수 있으므로, 명령어의 수를 줄여서 효율적인 실행을 가능하게 합니다.

GPU

"그래픽 처리 장치"를 의미하는 용어입니다. 일반적으로 컴퓨터의 그래픽 처리를 담당하는 하드웨어입니다. GPU는 3D 그래픽, 비디오 편집, 게임, 가상 현실(VR) 등 다양한 그래픽 관련 작업을 수행하는 데 사용됩니다.

1. GPU는 그래픽 처리에 특화된 구조와 기능을 가지고 있습니다.
   • CPU(중앙 처리 장치)와 달리 병렬 처리 능력이 뛰어나며, 많은 양의 데이터를 동시에 처리
   • 이는 그래픽 작업의 복잡성과 계산량이 큰 작업들을 빠르고 효율적으로 처리할 수 있게 도와줍니다.
2. GPU는 최근에는 그래픽 작업뿐만 아니라 일반적인 병렬 처리 작업에도 사용되고 있습니다.
   • 예를 들면, 인공지능, 데이터 마이닝, 과학 연구 등에서 GPU의 병렬 처리 능력을 활용하여 계산 작업을 가속화할 수 있습니다.

GPU는 CPU만 사용하는 것보다 특정 유형의 계산 작업에서 선호되는 이유

데이터-병렬 처리를 필요로하는 작업에서 GPU가 뛰어납니다.
GPU는 세밀한 데이터-병렬성을 활용하기 위해 최적화된 다른 아키텍처를 가지고 있기 때문에 이러한 계산에서 빠릅니다.

• GPU가 이러한 계산에서 빠른 이유는 그들이 대량의 코어를 갖고 있기 때문입니다.
• GPU는 대량의 병렬 처리를 처리하기 위해 고수준의 코어 수를 가지도록 설계되었습니다.
  • NVIDIA Titan V
    • 5120개의 처리 코어
  • AMD Radeon Vega
    • 4096개의 처리 코어
• 반면에 CPU는 일반적으로 훨씬 적은 수의 코어를 가지고 있습니다.
  • Intel Core i9-7980XE
    • 18개의 코어

CPU와 GPU의 코어는 정확히 같지 않습니다.

• 둘 다 계산을 수행하지만, 다른 아키텍처와 기능을 갖고 있습니다.
• CPU 코어
  • 더 다용도이며, 일반적인 목적의 컴퓨팅이나 순차적 처리와 같은 고성능 단일 스레드 작업에 최적화
• GPU 코어
  • 병렬 처리를 위해 특별히 설계되었으며, 데이터-병렬 작업에 더 효율적입니다.

❓데이터-병렬 작업에서 탁월한 성능을 제공하는 GPU이지만, CPU를 완전히 대체할 수는 없습니다.

• CPU는 여전히 단일 스레드 성능, 복잡한 제어 흐름, 병렬화하기 어려운 작업과 같은 다양한 컴퓨팅 작업에 필수적입니다.
• 많은 시스템에서 CPU와 GPU가 함께 작동하여 CPU가 일반적인 작업을 처리하고 GPU가 그래픽 렌더링, 과학적 시뮬레이션, 기계 학습, 데이터 처리와 같은 특정 작업을 가속화하는 방식으로 사용됩니다.
• CPU와 GPU의 조합은 계산 리소스를 더 균형 있고 효율적으로 활용할 수 있게 합니다.

GPU Example: NVIDIA Tesla

• 16(sm) * 8(cuda core) = 128cores
• sm = 스트림 프로세서
  • GPU 아키텍처에서 계산 작업을 수행하는 핵심 단위
    • 스트림 프로세서는 작은 독립적인 계산 코어들의 그룹입니다.
    • 이 코어들은 데이터를 동시에 처리하고 병렬로 실행함으로써 고성능 계산을 가능하게
    • 합니다.
      GPU Example: NVIDIA Volta in 2017
• 80(sm) * 64(cuda core) = 5120 cores, 13800 GFLOPS

GPU 아키텍처

• 처리는 매우 데이터-병렬적입니다.
  • GPU는 매우 다중 스레드로 구성
  • 스레드 전환을 사용하여 메모리 대기 시간을 숨깁니다.
  • 그래픽 메모리는 넓고 대역폭이 높습니다.
• GPGPU (General Purpose GPUs)
  • 이질적인 CPU/GPU 시스템
  • 순차 코드에는 CPU, 병렬 코드에는 GPU 사용

GPU vs. CPU

1. 많은 코어 GPU:

   • GPU는 많은 수의 코어를 가지고 있습니다. 수백 개의 코어가 GPU에서 동시에 작업을 수행할 수 있습니다.
   • 하지만 GPU는 상대적으로 작은 캐시를 가지고 있습니다. 이는 코어 간의 데이터 공유가 제한적이라는 의미입니다.
   • 코어는 집적 처리량을 최적화하도록 설계
   • 멀티코어 최적화

2. 다중 코어 CPU:

   • CPU는 여러 개의 코어를 가지고 있습니다. 각 코어는 단일 스레드 실행에 최적화되어 있습니다.
   • CPU는 상대적으로 캐시가 더 크고, 데이터 공유 및 캐시 적중률이 높은 구조를 가지고 있습니다.

GPU와 CPU의 차이를 이해하기 위해서는 latency hiding과 throughput computing의 개념을 이해

• Latency Hiding(지연 시간 가리기):

  • GPU 컴퓨팅은 개별 지연 시간을 줄이는 것에 초점을 두지 않습니다. 대신, 지연 시간을 숨기는 방식으로 작업을 처리하여 처리량을 증가시킵니다.
  • GPU는 많은 스레드를 제공하며, 한 스레드가 지연 시간으로 인해 작업을 일시적으로 멈추더라도 다른 스레드가 작업을 처리합니다.
  • 이러한 방식으로 GPU는 작업의 지연 시간을 가릴 수 있습니다. 다수의 스레드가 작업 중인 경우, 일부 스레드의 캐시 미스나 지연 시간을 다른 스레드가 가리게 되어 전체적인 처리량을 향상시킬 수 있습니다.

• Throughput Computing(처리량 컴퓨팅):

  • GPU는 처리량 컴퓨팅에 적합한 구조를 가지고 있습니다.
  • GPU는 많은 수의 코어를 활용하여 동시에 많은 작업을 수행할 수 있습니다. 이는 많은 thread를 제공함으로써 latency를 가릴 수 있습니다.
  • GPU는 작업 중에 발생하는 캐시 미스 등의 지연 시간을 다른 작업이 커버할 수 있도록 함으로써 전체 처리량을 높이는 데 초점을 두고 있습니다.

• 처리량 컴퓨팅

  • GPU 컴퓨팅은 개별 지연 시간을 줄이지는 않지만, 지연 시간을 숨기는 방식으로 처리량을 증가
  • 더 많은 thread를 제공해 latency를 채움(가림)
  • 쓰레드가 작업하다가 cache miss로 인해 버려저도 이를 커버할 쓰레드가 많다면 지연시간을 가릴 수 있음
    • latency hiding = throughput computing

• cpu는 control부분을 통해 latency를 낮춰 연산 속도를 올림
• gpu는 multicore 아키텍처를 집적하여 gpu 커널에 제공되는 쓰레드의 수가 cpu보다 훨씬 많이 제공됨
  • latency hiding
• IPC, flops(unit of throughput)
  • 벡터 에디션 코드가 4개
  • cpu core가 는다고 해서 latency of application이 줄 가능성은 줄지 않음
    • 하나의 작업을 처리하는데 걸리는 시간이 줄진 않지만 쓰레드 수가 많으면 throughput이 증가
    • gpu도 동일
      • 많은 수의 cuda core를 제공해야함

CUDA

Compute Unified Device Architecture

• NVIDIA GPU를 위한 프로그래밍 프레임워크
  • CUDA는 언어, 컴파일러, 런타임, 디바이스 드라이버, 라이브러리 등을 포함한 C/C++ 환경을 제공하여 NVIDIA GPU를 GPGPU(General Purpose GPU)로 활용할 수 있도록 합니다.
• 프로그래밍 모델
  • 호스트와 디바이스 간의 포크-조인(Fork-join) 방식의 프로그래밍
  • 데이터-병렬 프로그래밍 모델을 사용
  • CUDA는 GPU를 활용하여 과학적인 시뮬레이션, 기계 학습, 그래픽 렌더링 등 다양한 일반 목적의 계산 작업에 활용할 수 있도록 해줌

포크-조인 프로그래밍 모델, 호스트 + 디바이스 프로그램

• 호스트 C 코드(컴퓨터의 CPU에서 실행)에서 직렬 또는 적당히 병렬적인 부분 처리
• 디바이스 커널 C 코드(그래픽 카드의 GPU에서 실행)에서 고도로 병렬적인 부분 처리

//호스트에서의 직렬 코드 커널 내에서의 병렬 코드 
...
KernelA<<< nBlk, nThr >>>(args); 
//     |<- gpu program ->|

호스트에서의 직렬 코드 커널 내에서의 병렬 코드 = 커널 (디바이스) 
KernelB<<< nBlk, nThr >>>(args);

CUDA 프로그래밍 모델은 호스트와 디바이스 간의 협력적인 프로그램 구조를 가지고 있습니다.

• 호스트(CPU)에서는 직렬적인 부분이나 적당한 병렬적인 부분을 처리
  • 일반적인 C 코드로 작성
• 디바이스(GPU)에서는 고도로 병렬적인 부분을 처리하는 커널 함수를 작성
  • 커널 호출을 통해 디바이스에서 실행될 병렬 코드를 호출
  • <<< nBlk, nThr >>> 문법을 사용하여 커널 호출 시 실행할 블록 수(nBlk - SM - cuda SM)와 각 블록에서 실행할 스레드 수(nThr - SM 내부의 쓰레드 수 - cuda core)를 지정

따라서 CUDA 프로그래밍 모델은 호스트와 디바이스 간의 협력적인 프로그램 구조를 제공하여, 병렬 처리가 필요한 부분을 디바이스(GPU)에서 처리하고 나머지 부분은 호스트(CPU)에서 처리할 수 있도록 합니다. 이를 통해 GPU의 병렬 컴퓨팅 능력을 활용하면서도 호스트와 디바이스 간의 데이터 전달과 협력을 용이하게 만들어줍니다.

CUDA 프로그래밍 모델은 호스트와 디바이스 간의 협력적인 프로그램 구조를 제공합니다.

• 커널은 함수가 아니며, GPU 커널이 실행되는 동안 CPU 호스트는 차단되지 않습니다.
• 이는 호스트와 디바이스 간의 비동기적 실행을 의미합니다.

CPU와 GPU의 분산 메모리

• CPU와 GPU는 각각 독립적인 메모리를 가지고 있습니다.
  • CPU와 GPU가 서로 다른 메모리를 가지고 있음
• 이는 메시지 패싱과 유사한 분산 메모리 구조를 가집니다.
• 호스트에서 디바이스로 데이터를 전송하거나 결과를 가져오기 위해 데이터 전송을 수행해야 합니다.
  • sending, receiving api를 통해 수행

커널 실행

• 커널은 호스트 코드에서 호출되는 병렬 코드의 일부입니다.
• 커널을 호출하여 GPU에서 병렬적으로 실행됩니다.
• 호스트 코드는 커널 호출 후에도 계속 실행되며, GPU에서 커널이 실행되는 동안 CPU는 다른 작업을 수행할 수 있습니다.

GPU에서의 SMP (Symmetric Multiprocessing)

• GPU 내부에는 SMP(Symmetric Multiprocessing) 구조
• 이는 멀티스레딩과 유사한 구조입니다.
• SMP는 GPU 내에서 여러 스레드가 동시에 실행되며, 각 스레드는 병렬 계산 작업을 처리합니다.

단일 스레드(병렬 계산 작업이 없는) 덧셈

// Sequential C code
// Compute vector sum C = A + B

void vecAdd(float* a, float* b, float* c) {
  for (int i = 0; i < N; i++)
    c[i] = a[i] + b[i];
}

int main() {
  vecAdd(a, b, c);
}

• 순차적으로 실행되는 C 코드로, 벡터 합을 계산하는 예시
• vecAdd 함수는 루프를 통해 a와 b 벡터의 각 항목을 더하여 c 벡터에 저장
• N 개의 항목에 대해 반복문을 실행하여 순차적으로 합을 계산
• main 함수에서는 vecAdd 함수를 호출하여 벡터 합을 계산
• a, b, c는 벡터를 가리키는 포인터
• 이 코드는 순차적으로 실행되므로 병렬 처리가 이루어지지 않고, 각 항목을 순서대로 처리

병렬처리가 들어간 코드

// Parallel version using CUDA
// Compute vector sum C = A + B
// Each thread performs one pairwise addition

__global__ void vecAdd(float* a, float* b, float* c) {
  int i = blockIdx.x * blockDim.x + threadIdx.x;
  c[i] = a[i] + b[i];
}

int main() {
  // Run N/256 blocks of 256 threads each
  vecAdd<<<N/256, 256>>>(d_a, d_b, d_c);
}

• 위의 코드는 CUDA를 사용하여 벡터 합을 병렬적으로 계산하는 예시
• vecAdd 함수는 GPU에서 실행되는 커널 함수
• 각 스레드는 하나의 쌍으로 이루어진 항목을 덧셈하여 결과를 저장
• blockIdx.x, blockDim.x, threadIdx.x를 사용하여 각 스레드의 인덱스를 계산하고, 해당 인덱스에 위치한 a와 b 벡터의 항목을 더하여 c 벡터에 저장합니다.
  • blockIdx.x : 쿠다 블럭(sm)의 인덱스(위 그림에서 6개의 블럭을 0부터 5까지 인덱싱 한것 중 선택)
  • blockDim.x : 쿠다 블럭 내의 쓰레드 수(여기선 256)
  • threadIdx.x : 주어진 블럭 내에서 쓰레드의 인덱스(BLock(2,0) 에서의 10번째 쓰레드 = 10)
• main 함수에서는 vecAdd 커널 함수를 호출
• N 개의 항목을 가진 벡터에 대해 N/256 개의 블록을 생성하고, 각 블록에는 256개의 스레드가 있습니다.
• 이렇게 설정하여 벡터 합을 병렬적으로 계산
  • <<<N/256, 256>>> 구문은 커널 함수 호출을 지정하며, d_a, d_b, d_c는 GPU 메모리에 할당된 벡터를 가리키는 포인터
  • N/256 = 6 -> N = 2*256

• cpu와 gpu가 다른 메모리를 가지기에 연산전에 device메모리(gpu메모리)를 할당
• cudaMemcpy를 통해 host -> device, device -> host로 메모리의 값을 저장하는 연산을 수행
  • 여기서 우선 host의 a와 b값을 device로 받아옴
  • 연산 후 저장값을 device에서 host로 보냄