[GPGPU Series 7] Warp Execution

지난 글에서 Thread Block (TB)에서 Warp를 생성하는 방법에 관해서 설명하였다. 이번 글에서는 Warp가 실행되는 방법(?)에 대한 설명이다.

Warp는 GPU Instruction을 실행하는 가장 기본 단위이다. Warp의 모든 Thread는 하나의 같은 Instruction을 실행한다. 하지만, Warp의 각 Thread는 서로 다른 Data 값을 읽을 수 있다. 결과적으로 Warp의 각 Thread는 같은 Instruction을 다른 Data 값을 사용하여 연산을 수행한다고 생각하면 된다. 이러한 연산방법을 SIMD (Single Instruction Multiple Data) 또는 SIMT (Single Instruction Multiple Thread)라고 한다.

  • SIMD와 SIMT는 조금 차이가 있다. SIMD의 경우 Vector 연산을 수행한다고 보면 된다. SIMD 연산을 위해서는 Vector 연산을 수행하기 위한 Instruction이 필요하다. 반면 SIMT의 경우 프로그램을 작성하는 당시에는 하나의 Thread를 기준으로 코드를 작성하면 된다. 그리고 하드웨어가 여러 개의 Thread를 그룹화하여서 연산을 수행하는 것이다.
  • Volta Architecture부터 Warp의 Thread가 서로 독립된 연산을 수행할 수 있다고 한다. Volta Architecture에 대해서 상세히 읽어보지 않아서 동작 방법은 잘 모른다. 다음에 Volta 또는 Turing Architecture에 대해서 한번 정리할 계획이다. (출처 1, 2)

그림 1: SIMT ADD 연산

그림 1은 SIMT 연산 방법으로 ADD 연산을 수행하는 그림이다. 32개의 Thread는 독립된 저장 공간 (Register)을 가지고 있다. ADD 연산을 수행하기 위해서 각 Thread는 2개의 Source Register에서 Data 값을 Loading 한다. ADD 연산을 수행 후 얻은 결과를 32개 다른 Destination Register에 저장한다. 결과적으로 하나의 Warp는 64개의 Source Register를 Access 하게 되며, 연산 결과값을 32개의 Register에 저장하게 된다. Warp의 모든 Thread는 같은 연산을 수행하기 위해 하나의 Instruction만 Loading 한다. 정확히 말하면 Scheduling 될 때 같은 연산을 수행하라는 Instruction을 Broadcasting 하게 되며 하나의 Warp의 모든 Thread는 Broadcasting 된 하나의 Instruction 수행하게 된다.

보통 한 SM (Streaming Multiprocessor)에 48개~64개의 Warp가 존재한다. 각 SM은 보통 수십~수백 개의 연산기 (ALU) 를 가지고 있으며, 동시에 2~4개의 Warp Instruction을 Scheduling 할 수 있다. SM 당 총 Warp 개수, ALU 개수 등은 GPU Architecture마다 조금씩 차이가 있다. GPU는 CPU와 비슷하게 Pipeline을 사용하여 Instruction을 수행한다. 보통 GPU는 Instruction Fetch, Decode, Issue, ALU&Memory, Writeback 형태로 5개의 Pipeline Stage로 구성되어 있다 (출처 3).

  • Turing GPU Architecture부터는 Integer, Floating 연산기가 분리되었다고 한다. 이전 Architecture의 경우 Integer, Floating Point 연산을 하나의 ALU에서 모두 수행하였다.
  • GPGPU-Sim은 NVIDIA GPU를 모델링하여 만든 컴퓨터 Architecture 시뮬레이터이다. C, C++로 작성되어 있다. 워낙 오래된 시뮬레이터이지만 이보다 나은 선택지가 없어서 많은 연구실에서 해당 시뮬레이터를 사용해서 논문을 작성하고 있다.

그림 2: GPU Pipeline Stages

그림 2는 5개의 Pipeline Stage를 보여준다. 아래는 각 Stage에 대한 설명이다.

  • Fetch: Fetch 단계에서는 PC (Program Counter)의 값을 사용하여 Instruction을 Loading 한다. 최근 GPU의 경우 CPU와 같이 64-Bit Instruction을 사용한다. Instruction을 Fetch 하는 순서는 Round-Robin 방식이다. Warp 0, 1, 2, …. 순서로 Instruction을 Fetch 한다.
  • Decode: Decode 단계에서는 메모리에서 Loading 한 Instruction을 ALU/Memory 연산 등을 수행하기 위해 연산 Type 및 필요한 Register를 찾는 단계이다. Decode 된 Instruction은 Instruction Buffer에 저장된다. GPU는 Integer, Floating Point, Special Function, Memory 연산 등을 모두 다른 Logic에서 계산한다.
  • Issue: Decode 된 Instruction을 연산기로 보내는 단계이다. 이 단계에서는 연산에 필요한 Data 값은 Source Register에서 읽게 된다. Source Register에서 읽은 값을 ALU로 보내면 ALU는 연산을 수행하게 된다. 보통 Instruction이 Fetch/Decode 되는 속도(?)가 Instruction Issue 되는 속도보다 빠르기 때문에 이 단계에 이르면 Decode 된 (Issue 가능한) Warp의 개수가 많을 확률이 높다. 그렇기 때문에 Warp Scheduler가 Issue 하는 Warp를 선택한다. 많이 알려진 Warp Scheduling 기법은 Round-Robin (RR) 과 Greedy-Then-Oldest (GTO) 방식이 있다. SM은 평균 2~4개의 Warp Scheduler를 가지고 있기 때문에 매 사이클 당 2~8개의 Warp Instruction을 Issue 한다. Issue 된 Instruction은 ALU/LSU 등에서 연산을 수행하게 된다. 각 Instruction은 연산 Type에 따라 수십 사이클에서 수백 사이클의 연산 시간이 필요하다.
    • RR Warp Scheduling은 여러 개의 Warp 중 ALU로 Issue 되는 Warp의 순서를 순차적으로 선택하는 방법이다. 예를 들어 SM에 24개의 Warp가 있다고 가정하고 모든 Warp가 Instruction을 실행할 준비가 되었다고 가정하자. 이 경우 Warp 0, Warp 1, …, Warp 23이 Instruction 1개씩을 순서대로 ALU에 Issue 되는 형태이다.
    • GTO Warp Scheduling 방법은 Warp 0번의 실행 가능한 Instruction을 모두 실행한다. 만약 준비된 Warp 0의 실행 가능한 Instruction이 없으면 (Stall이 발생한 경우) 다음 준비된 Warp를 선택하여 Instruction을 Issue 한다. 다음 선택하는 Warp는 현재 Stall 된 Warp의 다음 ID를 가진 Warp를 선택한다. 예를 들어 Warp 3번이 실행 가능한 Instruction이 없는 경우 Warp 4번의 Instruction을 Issue 하게 된다.
  • ALU&Memory:  Source Register에서 읽은 값을 사용하여 연산을 수행한다. Instruction Type에 따라 Load/Store Unit (LSU), ALU, Special Function Unit (SFU) 연산기를 사용하게 된다. ALU의 경우 Integer, Floating Point 연산을 수행한다. SFU의 경우 Sin, Cos등 연산이 다소 복잡한 Instruction을 수행한다. LSU의 경우 메모리 연산을 수행한다..
  • Writeback: ALU, LSU, SFU에서 연산한 값을 Destination Register에 저장하는 단계이다.

GPU는 위와 같이 5단계로 Warp Instruction을 수행한다. 보통 Computer Architecture 책에서 설명하는 5단계 Pipeline Stage와 거의 동일하다.

출처

  1. https://images.nvidia.com/content/volta-architecture/pdf/volta-architecture-whitepaper.pdf
  2. https://www.nvidia.com/content/dam/en-zz/Solutions/design-visualization/technologies/turing-architecture/NVIDIA-Turing-Architecture-Whitepaper.pdf
  3. http://www.gpgpu-sim.org/

6 thoughts on “[GPGPU Series 7] Warp Execution”

  1. 두 세번은 다시 봐야겠지만 덕분에 많은 공부가 됐습니다!
    남은 내용도 꼭 부탁드립니다..ㅎ

    Reply
    • 글 남겨주셔서 감사합니다. 바쁜 일정 마무리되면 계속 글을 작성해서 포스트 할 수 있도록 하겠습니다.

      Reply
  2. 안녕하세요!
    최근 GPU를 공부중인데, 정말 좋은 참고자료가 되고 있습니다. 정말 감사합니다.

    읽으면서 궁금한 것이 있어서 여쭙습니다.
    소개해주신대로 GPU가 실행되면 같은 워프에서 코드가 out-of-order로 실행될 수도 있을 것 같은데요,
    다만, Out-of-order로 excute하면서도 in-order로 수행하기 위해 CPU에서 통상적으로 사용하는 기술을 적용할 경우 GPU에서는 오버헤드가 크지 않을까 생각이 됩니다 (예를들면 warp마다 reorder buffer를 두는 방법 등이 있겠지요).
    혹시 out-of-order excution + in-order commit을 구현하는 GPU만의 하드웨어 구조가 있을까요?

    Reply
    • 안녕하세요. 서툴게 작성한 글도 도움이 되었다니 기쁘네요.
      우선, 제가 질문을 제대로 이해했다면 GPU도 CPU와 같이 Out-of-Order(O3) Exeuction이 가능한지를 문의하는 것 같습니다.
      아마 만들려면 만들 수는 있을 것 같습니다. 하지만 CPU와 같이 완벽한 O3 구현은 사실상 어려울 것 같습니다.
      저도 정확히 기억은 나지 않지만, O3 CPU에서 O3 연산을 위한 Control Logic (Reorder-Buffer, Scheduling Window, etc.)이 차지하는 부분이 상당히 큰 것으로 알고 있습니다.
      해당 Control Logic의 파워 사용량도 엄청 높습니다. 그래서 모바일의 경우 In-Order, O3 CPU를 2개씩 가지고 필요에 따라 Big/Little로 변경해서 사용합니다.
      만약 GPU에 O3를 구현한다고 하면 Re-order Buffer, Scheduling Window 등 O3에 필요한 모든 구조를 Warp 개수만큼 구현해야 합니다.
      각 Warp의 실행 순서가 다를 수 있기 때문에 Rename도 각 Warp 단위로 고려를 해야 하지 않을까요? (맞겠죠??ㅎ)
      단순히 예를 들어서 1 SM에 48개의 Warp가 실행되고, GPU가 12개의 SM만 가지고 있다고 해도 모든 Warp의 Out-of-Order를 유지하기 위해 필요한 로직의 개수가 500개를 넘어가게 됩니다.
      그렇게 되면 GPU Control Logic 자체가 지나치게 커지게 될 것 같습니다. 그 로직만큼 다른 부분을 제거해야 할 텐데 그럼 SM의 개수가 줄어들게 될 것 같습니다. 이런 부분을 고려하면 GPU의 기본적인 Massive Multi-Thread라는 개념이 없어질 것 같은데요….
      예전에 읽은 논문 중에 GPU Compiler가 Instruction 순서를 제대로 정렬하지 못해서 Long-Latency(Memory Operation)로 인해서 Warp의 실행이 멈추는 경우 뒤에 실행되는 Instruction 중 Long-Latency와 Dependency가 존재하지 않는 Instruction을 찾아서 먼저 실행하도록 변경한 구조는 보았던 것 같습니다. 해당 논문이 제가 읽은 논문중 Out-of-Order Execution에 제일 근접한 GPU 구조였던 것 같습니다.
      제가 틀렸을 수도 있습니다. 제가 최근에 발표된 논문은 거의 읽지를 못해서 새로운 구조가 나왔을 수도 있습니다.
      답변이 도움이 되었으면 좋겠습니다.

      Reply

Leave a Reply to Admin Cancel reply