[MPC] 0. GPU Architecture

0. GPU Arhitecture

0.1 Parallel Execution in Modern Processors

0.1.1 Pre multi-core era

• 멀티코어 프로세서를 만들기 전에는 대부분이 슈퍼스칼라 형태였다.
• 단일 명령어를 빠르게 실행시키기 위해 여러 로직을 넣어주었다.
  (ex: Out of order control logic, Fancy branch predictor, Memory prefecher)
• 무어의 법칙에 따라 많은 트랜지스터를 사용할 수 있게 되어, 캐시를 키우고 좋은 OO logic, branch predictor를 추가시켰다.
  -> 근본적으로 한계가 있었다.
  1. Power wall: clock frequency를 높임 -> power consumption 증가 -> 온도 증가
  2. Diminishing gain ILP

0.1.2 Multi-core

• 여러 개의 독립적인 명령어 흐름을 실행할 수 있게끔 프로세서에 코어를 추가했다.

• 각 코어는 싱글코어 프로세서의 성능보다는 낮지만 두 개를 동시에 사용하기 때문에 전체 성능은 향상됐다.
  (ex: 듀얼코어의 각 코어 성능이 싱글코어의 0.75배라고 하면, 전체 성능은 0.75*2 = 1.5로 개선된다.)

• 코어가 많아질수록 코어의 갯수만큼 독립적인 명령어 흐름을 처리할 수 있게된다.

  Q. 어떻게 모든 코어를 실행할 수 있게 할 것인가? 즉, 명령어를 제공해줄 수 있을 것인가.
  Ans. Data-level parallelism

  void mul(int N, float *x, float *result)
  {
      for(int i=0; i<N; i++)
    {
      float value=0;
      for(int j=0; j<N; j++) value += x[i] * j;
      result[i]= value;
    }
  }

  • 각 iteration에서 데이터만 달라지고 동일한 연산을 수행하고 있다. 즉, 동일한 명령어를 실행하고 있다.

  • 동일한 명령어를 실행할 것인데, 모든 코어가 instruction fetch/decode unit이 필요한가?라는 질문이 생긴다.

    Ans. SIMD Processing

0.1.3 SIMD Processing (Single Instruction Multiple Data Processing)

• 많은 ALUs가 fetch/decode unit을 공유한다.
• 서로 다른 데이터에 대해 동일한 명령어를 실행한다.
• 분기문 처리는 어떻게 하는가?
  • 'False'가 날 때 연산하지 않고, 'True'일 때만 연산한다.
  • 전체 성능 저하의 원인이 될 수 있다.

Summary

• Multi-core: 여러 프로세싱 코어를 사용한다.
  1. 스레드 레벨 병렬성을 제공: 각 코어에서 동시에 독립적인 명령어 흐름을 실행한다.
  2. 소프트웨어가 스레드 생성 시기를 결정한다. (e.g., via pthread API)
• SIMD: 동일한 명령어를 실행하는 여러 개의 ALU를 사용한다.
  1. 데이터간 병렬성이 있는 워크로드에 효율적
  2. 컴파일러나 하드웨어에 의해 병렬처리가 되도록 만들어 줄 수 있다. (Vectorization)
  3. 데이터나 명령어간 디펜던시가 코드상에 표시가 되어있어야 한다.
• Superscalar: 명령어 흐름 내에서 ILP를 사용한다.
  1. 동일한 명령어 흐름에서 서로 다른 명령어를 병렬적으로 처리한다.
  2. 실행 중에 하드웨어가 병렬성을 동적으로 찾아준다.

0.2 Multi-threading for hiding memory latency

• 오프칩 메모리에 저장되어 있는 데이터를 읽어올 때까지 걸리는 시간을 숨기기 위한 멀티 스레딩 방법
  -> GPU는 기본적으로 멀티 스레딩 방식으로 레이턴시를 숨긴다.

0.2.1 Terminology

• Memory Latency: 메모리에서 데이터를 읽거나 쓸 때까지 걸리는 시간 (e.g. 100 cycles, 100nsec)

• Memory Bandwidth: 단위 시간당 메모리에서부터 데이터를 읽거나 쓸 수 있는 양 (e.g. 20 GB/s)

• Stall: 프로세서가 더이상 다음 명령어를 실행시키지 못할 때 'stall' 됐다고 한다.

  • 명령어를 처리할 데이터가 없어서 프로세서가 stall되는 것이 대부분이다. -> 디펜던시

  # 디펜던시 예시
  ld r0 mem[r2]
  ld r1 mem[r3]
  add r0, r0, r1

  • Memory Latency: more than 100 cycles (가장 큰 오버헤드)

0.2.2 Hiding stalls with multi-threading

• Idea: 여러 개의 스레드를 만들어 번갈아가며 코어에서 실행되게 만들어줘서 레이턴시를 감춰준다.

  • Benefits
    1. 메모리 레이턴시를 숨겨 코어의 ALU 자원을 효율적으로 사용할 수 있게 된다.
  • Costs
    1. 스레드의 컨텍스트를 저장하기 위한 스토리지가 필요하다.
    2. memory bandwidth에 높게 의존한다.
       • More threads -> Larger working set -> less cache space per thread
       • 메인 메모리에 자주 접근해야하지만, 레이턴시를 숨길 수 있다.

• Concurrency: 하나의 코어에서 하나의 스레드를 실행하다 다른 스레드를 코어에서 실행하고 이를 반복하는 것.

0.3 GPU Architecture

• CPU와 GPU는 다른 목적을 이루기 위해 설계됐다.
  • CPU는 싱글 스레드의 레이턴시를 줄이기 위해 설계됐다.
  • GPU는 연산량을 극대화하기 위해 설계됐다.
    • GPU는 CPU보다 칩 영역에 연산을 위해 많은 부분 할당했다.
    • GPU는 CPU보다 연산당 에너지 소모가 적다. (복잡한 컨트롤 로직이 없기 때문이다.)

0.3.1 Inside a GPU

• SPA (Streaming Processor Array)
• TPC (Texture Processor Cluster)
  • Multiple SMs + TEX
  • TEX: texture processor for graphics purpose
• SM (Streaming Multiprocessor)
  • Multiple Processors (SPs)
  • 멀티 스레드 프로세서 코어
  • 스레드 블록을 위한 프로세싱 유닛
    • 스레드 블록: GPU에서 스레드를 처리할 때, 스레드를 묶는 단위
• SP (or CUDA core)
  • 하나의 스레드를 실행하기 위한 ALU로 구성되어 있다.
• SFU (Special Function Unit)
  • 복잡한 수학 함수를 실행하기 위해 넣은 하드웨어

• GPU는 여러 개의 SMs을 갖는다.

  • 각 SM은 여러 개의 프로세서로 구성되어 있지만 하나의 명령어 유닛은 공유한다.
  • 즉, SM 내의 SP는 프로그램 카운터를 공유한다.
  • 그래서 모든 SP들은 동일한 명령어 집합을 실행한다.

• 커널이 실행될 때, 태스크가 여러 개의 스레드로 나눠진다.

  • 각 스레드는 서로 다른 데이터를 갖고서 주어진 태스크를 실행한다.
  • 모든 스레드는 동일한 커널 코드를 실행한다.

• 모든 스레드는 블록으로 나누어진다.

• 각 블록은 SM에 할당되고, SM 내에서 각 블록은 Warps라는 단위로 나뉜다. -> Warp단위로 실행한다.

  • 하나의 Warps는 32개의 스레드로 구성된다.
  • 모든 스레드들은 동일한 명령어를 실행한다. -> SIMT
  • 워프들은 SM내에서 동시적으로 실행된다.
    1. 첫 번째 워프를 SM에서 실행시킨다.
    2. 첫 번째 워프를 실행할 수 없으면 두 번째 워프를 SM에서 실행시킨다.
    3. 이를 반복한다.

0.3.2 Thread Scheduling/Execution

• 스레드는 동시적으로 실행된다.
  • SM은 각 스레드에 id를 할당하고 관리해준다.
  • SM은 스레드 실행을 관리하고 스케쥴링해준다.
• 각 스레드 블록은 32-thread Warps로 나뉜다.
• 워프는 SM에서 스케쥴링 유닛이다.
  • 세개의 블록이 SM에 할당됐고, 각 블록이 256개의 스레드를 갖고 있다고 해보자.
  • 각 블록은 256 / 32 = 8개의 워프를 갖고 있고, SM은 총 3 * 8 = 24개의 워프를 갖게 된다.
• 하나의 워프에 모든 스레드는 동일한 명령어를 실행하게 된다.
• memory access -> latency problem -> scheduling required !
  • 하나의 워프가 stall되면 다른 워프를 스케쥴링해서 그 워프가 SM에서 실행되게끔 만들어 주어야 한다.
• SM 하드웨어는 zero-overhead Warp scheduling을 구현한다.
  • 다음 명령어에 사용할 데이터가 있는 워프는 실행할 수 있다.
  • 스케쥴링 폴리시에 따라 실행 가능한 워프가 선택된다.

0.3.3 CPU vs GPU memory hierarchies

• CPU
  • 레이턴시를 감추기 위해 캐시 계층을 갖고 있다.
  • 큰 캐시를 갖고 있다.
  • 메모리 prefetching 테크닉을 사용한다.
• GPU
  • 캐시는 조금만 사용한다.
  • memory bandwidth
    • 캐시가 매우 작기 때문에 대부분 메인 메모리에서 데이터를 읽어온다.
  • 멀티 스레딩에 의존한다.