GTX 1080

• 각 네모가 sm이기에 32개의 sm이 있다는 것을 알 수 있음
  • 32개의 sm은 L2 cache를 공유

각 sm안에는 저렇게 생김

• 4개의 warp executor이 있고 각 executor에는 warp selector가 존재
  • 우리는 4개의 Warp을 동시에 동작할 수 있음
• cpu는 메모리에 가져오는데 시간이 오래걸리기에 캐시가 엄청 컸었음
• gpu는 fetching memory to sm 시간이 오래걸리니까 구냥 context switching!
• 너무 cache miss가 일어난다면 context switching
  • run 4 warp을 동시에 돌려도 easy to switch 해야 함
  • register file을 보면 warp 64개까지 status를 저장할 수 있음
  • register를 메모리에 옮겨야해서 cpu에 시간이 오래걸렸었음.. 여기는 고려할 필요가 없음 레지스터가 넘넘많아서
  • cpu - context switch의 경우 레지스터를 메모리에 저장하고 load해서 백업했기에 오래걸렸지만 여기는 필요없음. register file에 저장해놓으면 되니까!

cf. 캐시미스가 나면 와프가 바꾸는데 마크해놓고 로드가 끝나면 마킹해서 알려주고..뭐..그런식

cpu에서는 instruction 차례대로 실행안함 왜냐면 차례대로 실행하면 느리니까

ld r2
add r1 r2 //로드될 동안 기다리고
mult r3 r4 // 얘는 안기다려도 되니까 바로 실행

→ cpu는 그래서 복잡해지는 거임

• warp executor에는 2 fetch decode이기에 두개의 instruction을 받을 수 있기에 두번째는 dependency가 있어서 그 다음거를 실행. cpu에는 이거보다 더 많지만 gpu는 두개밖에 없음
• 한 개만 있으면 context switching이 너무 많이 일어나니까 뭐 2개정도로 가진거임. 여러개 더 가질 수도 있지만 비용 trade off 때문
• shared memory, L1 cache는 사실 같은 캐시 하드웨어를 쓰기에 크기를 자유롭게 바꿀 수 있음

Running a Thread block on SM

• 4개의 와프를 동시에 같이 돌리고 64 wrap은 waiting to scedule

Scheduling thread blocks

• kernel을 런치하면 kernel code를 cpu → gpu로 옮김
• 그 후에 kernel code에는 thread configuration, grid configuration이 정해져있으니까 그걸로 런타임에 thread block을 만들어서 hardware queue에 넣음
• warp selector은 각 sm에 있고 thread block schedulor에서 fetch thread block하고 그다음 애 실행…등등으로 진행 주로 round robin으로 진행됨 until SM run out of resource
  • 여기서 resource는 register, shared memory
  • kernel code는 thread가 많은 레지스터를 쓸 수도 있음
    • thread가 많은 수의 레지스터를 가지게 되면 register가 limiting factor를 가지게 됨
    • single thread block에 모든 레지스터를 쓰게 되면 더 이상 thread block을 쓸 수 없음
    • thread block이 많은 shared memory를 쓴다면 다른 thread block을 쓸 수 없음

→ 각 thread block이 사용하는 register과 shared memory 사이에 limited factor

maximum hardware thread assign to single thread block 또한 limited factor임

today 배울 거는

• some of gpu hardware architecture
• mapping grid, thread blocks to 1d,2d arrays
• atomic operation

Scheduling thread block

커널은 gpu memory에 복사되면서 thread, block configuration을 생성

• gpu는 thread block을 만들어서 gpu hardware에 있는 스케줄러가 thread block queue을 관리
  • 앞에 있는 거를 할당해서 assign in sm

Warps

• cpu, gpu 효율이 어떻게 다른지
• gpu는 instruction이 빠르고 multiple alu,core에서 같은 instruction을 실행

Running a CUDA Kernel(registerfile,shared memory)

• core == alu
• 노랑이는 코어고 회색은 sm
• 각 sm에 single block executor가 있음
• 오른쪽은 cuda kernel이 쓸 수 있는 share memory
• 왼쪽은 register file

• thread scheduler는 하나의 thread block을 fetch해서 first sm에 할당

• thread schdeuler가 두번째 fetch해서 두번째 sm에 할당
  • Roundrobin형태로 가는 거 같대

• 5번째 안됨 왜냐면 register file은 자리는 있지만 shared memory가 자리가 모잘라서 더 할당 못함

→ wait sm to finish execution at least one of block

• 첫번째 칭구가 끝났으니까 이제 할당 가능

• 모든 block이 다할당되고 끝날 때까지 반복

가장 중요한 cuda programing

1. thread structure을 task에 어떻게 할당할지(데이터에 잘 맵핑할지),
2. 두번째는 well assign to sm and gpu hardware resource(너무 share memory를 쓰면 register 자리나 alu가 있어도 할당 못함…)
3. 마지막은 데이터를 잘 가져와서 shared memory에 잘 저장하자…(shared memory를 잘 사용하자…)

⇒ thread block assign에 대해서 알아봤었는데 하나의 block은 128개의 thread, 즉 4개의 warp인데 그럼 warp는 어떻게 돌아갈까??

Thread scheduling example

• 시간순으로 어떻게 warp이 스케줄되는지를 보여주는 도표, gpu clock 기준
  • multiple thread block이 돌릴 수 있고 multiple warp도 동시에 돌아갈 수 있음
  • 3개가 thread block assign한다고 가정
  • 그림에는 one warp exeutor를 가짐(실제로는 sm에는 여러개의 warp executor를 가지는 편)
• 첫번째 warp을 6클럭동안 하고나서 명령어가 오는데 메모리 가져오라고 하는데 캐시에 없네?? → switch warp(같은 thread block이든 아니든 상관없음, 여기서는 다른 애를 고름 ) → 2클럭 돌리고 switch …
• 그러다가 tb1,w1에서 로드가 끝나면 switch back해서 이어서 연산

context switching in warp은 대부분 1~2클락 전에 해결

More on GTX 1080

• sm이 16개밖에 안보이지만 사실 20 sm가짐
• gpu 클럭 frequeny가 cpu보다 느린 편
  • 하지만 병렬적이고 확장가능성 있음
• 각 sm은 4 warp executor(==execution unit, 총 128 thread)를 가지고 각 한개의 warp을 고름
  • 20개의 sm * 4개의 warp(128개의 thread)
  • 하나의 클럭으로 mul,add alu을 할 수 있음
    • 즉, perform 2 floating computation
  • 1초에 8.1* 10^12 floating 연산을 할 수 있다는 말
• 각 20개의 sm은 64개의 runnable warp이고 동시에 돌릴 수 있는 건 실질적으로 4개뿐 → 40960 쓰레드를 하드웨어 칩에 할당 가능
  • 40960 * 4/64를 하면 그 개수만큼의 thread를 동시에 돌린다는 말임
  • cpu의 경우, 10몇개정도만 돌릴 수 있다니까 gpu core가 훨씬 동시에 많이 돌릴 수 있는 거!

Some Example Kernel

• 각 kernel에서 thread index를 계산하고 다른 값을 할당
• local map to global map structure

More example- shuffling data

old array와 index를 이용해서 new array를 생성

• _ind는 해당 이전 배열이 어느 위치에 저장되어야하는지를 의미
• 여러가지 방법 존재

뒤의 방식대로 한다면??

• d_new에 할당해야하니까 new_array[i]에 할당
• condiiton이 있는 이유는 more thread > array의 길이 일 수 있어서 조건이 있는 거래

d_old를 이용해서 한다면???

→ 이건 간단한데 복잡한 연산의 경우 다양한 방법이 존재

Inc.by 1(2D)

• 2d array가 있다면 실질적으로 저장된 후의 메모리는 그냥 주루룩 행별로 쭈루룩 저장됨

→ compute 중간을 한다면 저기까지 가서 계산해야함

여기까지는 maping thread to array였음

이제 atomic에 대해서 알아보자!

Communication among threads

• how do you do global communication?
  • 다른 thread communicate을 어떻게 해야할까??
  • 어느 쓰레드에서 써서 그 결과를 다른 쓰레드가 봐야한다면?
• 쉬운방법: finish a grid and start a new one
  • all writes from all threads complete before a kernel finishes

• sequential하게 해서 첫번째 계산 다하고 그값 글로벌 dram에 저장하고 두번째 커널이 시작할 때 dram에서 읽어와서 진행하는 그런 방식

• 다른 방법: write to a predefined memory location

  • thread이 같은 processor안에 있다면 memory location을 공유할 수 있으니까!!
    • cpu multithread programming처럼 해보자. thread in same processor shared memory space를 쓴다면 다른 쓰레드가 읽게해보자~
  • 문제점
    • race condition!! updates can be lost
    • 더 심각

Race condition

• 두개의 thread는 같은 혹은 다른 thread block에 있음
• 둘 다 같은 배열을 접근 == write and read predefine definition, 두번째와 같은 예시

→ 같은 sm, 다른 sm 등등 다르게 되기에 값이 다르게 될거임….

temp = v[0]
v[0] = temp + 5

• 문제점

  사실 이렇게 돌아갈건데 read value 한 후에 다른 쓰레드가 더하고 다시 원래에 할당하고 막 이런 식이면 연산이 사라지게 될 수 있음….

  • thread 0 could have finished execution before 1917 started
    • or the other way around
    • or both are executing at the same time

• value vector[0] 값이 well defined되지 않게 됨!

  • 쿠다가 order of execution을 보장하지 않기 때문
  • 다른 sm일 경우 다른 private cache를 쓰기에 cache coheriecne가 보장되지 않음

→ atomic operation을 쓰자!

Atomics

• CUDA는 atomic operation을 제공

• single thread만 해당 연산을 접근하도록!
• order of calculate는 보장하지 않지만(1더하고 5더하고 그 순서는 보장 x) 접근은 atomic이라는 거임

Example histogram

image를 1d array에 맵핑했다라고 가정 = color

colors [i]는 0~255 사이의 값이고 얘는 흑백 이미지라고 가정, 0이면 검정 255이면 하양

• 우리는 각 숫자의 횟수를 알고 싶어서 255 길이의 bucket 배열에 숫자를 증가해서 보장
• atomicAdd부분에서 하나의 thread만 접근할 수 있게 됨!

Example workqueue

많은 게 생략되어서 좀 무슨말인지 모르겠다망….구냥 간단히 맵핑하려고 했다만 알면 될 듯..

• ouput 어디에 저장될지를 결정하는 i
• queue가 있는데 각 쓰레드는 queue에서 fetch해서 task를 진행하는 것
• queue_counter는 특정 queue의 위치를 가리킴
• 다른 쓰레드는 다른 task를 받아야 하기에 atomicInc으로 index를 가져오고 incremen함

fetch the index and increment index at the same time

• atomicInc는 해당 어드레스에 있는 값이 다른 애보다 크다면 0을 저장하고 아니라면 1증가하고 저장하게 됨
• 메모리 주소에 있는 값이 가져와서 1만큼 increment해서 저장하는 거임. 근데 val이 max여서 가져와서 max보다 크다면 0으로 가는 거임 : circular queue를 의미

Atomics

• atomic은 normal load, store보다 느린 편
• old gpu에서 사용불가
• 무작정 atomic을 쓰면 parallel hardware를 효율적으로 쓰는게 아님
• 좀 더 빠르게 돌릴려면 two level aggregation을 해야함!!

Global min max - naive

• value를 저장해서 gl_max와 val을 비교해서 val이 클 때만 val 값을 gl_max에 저장
• 이 전체 atomicMax는 예전 max값을 리턴
• atomicMax를 하게 된다면 전체 쓰레드가 접근하면 serial하게 접근하니까 병렬성이 낮아짐 ㅠㅠ

→ local max, global max(two level aggregation)로 속도를 높여보자!

Global min/max - better

• 기존
  • 아주아주 긴 배열이 있고 하나의 쓰레드는 하나의 값을 접근 → fetch해서 gl_max와 비교해서 update했었음
• 개선한 코드
  • divide the array해서 small number of region으로 변경
  • 그다음에 small array를 만들어서 각 region의 맥스값을 저장
    • i를 region 개수와 나머지 연산해서 region을 결정
    • region수가 7개라면 이렇게라면 배열의 요소마다 접근하는 region은 01234560123456… 이렇게 됨!!
  • reg_max에 있는 값과 현재값을 비교했을 때 크다면 reg_max가 업데이트되었다는 거니까 global max인 max를 업데이트
• 더 개선할 수 있는 코드
  • 두개의 atomic max이 있는데 둘 다 atomicMax는 비쌈..왜냐면 fetch data in array compare이고 udpate하니까 좀 비쌈!!

  → 그냥 위의 atomicMax안써도 됨….region max는 상관없음!!

  • atomicMax를 쓰는 것 보다는 그냥 코드로 저 값을 비교해서 업데이트하자
  • 하나의 문제점: gpu는 cache cohereince between different SM!
    • cache coherion은 core만 접근한는 캐시가 있는데 마치 그 캐시가 없는 거처럼 동작하도록 하는 걸 말함!! 두개의 core가 private data를 가지고 있다면 한쪽에만 업데이트하고나서 반영이 안되면 업데이트된 게 잃어버릴 수 있기 때문에 주로 coherion protocl이 invaliadate나 update를 해줌
    • gpu는 그런 cache coherion을 지원하지 않음.. 왜냐면 아주 비싼 연산이기 때문!!
    • if에 있는 atomicMax를 쓰지 않으면 하나의 sm은 100으로 다른 sm은 200으로 바꾸면 이 두개의 update는 서로 invalidate되지 않음… 200이지만 100이 저장될 수 있음.. 근데 얘는 문제가 되지 않대… 왜냐면 atomicMax에서 글로벌 max이 여전히 200이기 때문!!!
    • 8바이트 array이라고 가정한다면 많은 cpu에서는 8b를 2 load operation으로 진행됨 그러면 첫번째는 100인 애로 뒤는 200인 애로 될 수도 있지만 array가 4바이트니까 여기서는 문제가 되지 않긴 함…

→ 이렇게 local max, global max로 한다면 첫번째 업데이트로 Parallel하게 만들 수 있어서 좀 더 성능이 나아짐

• size of regoin는 역시 우리가 신경써야하는 값임. 너무 작게 만들면 병렬을 많이 안쓰고 많이 쓰면 병렬처리는 잘되지만 l1,l2 cache로 쓰기 어렵게 될 수도 있음

Global Min/max

• single value causes serial bottleneck
  • 원래라면 전체 배열이 atomicAdd를 부르니까 만약에 동시에 여러개가 부르면 serial하게 기다려야 하는데 좀 짤라서 하면 동시에 여러개 부를 일이 줄고 기다리는 시간도 줄어드니까!!
• create hierarchy of value for more parallelism
• performance will still be slow so use judiciously
• even better version in the future!

Summary on atomic operation

• thread끼리 읽고 업데이트할 수 있는 거는 Race conditon이 일어나니까 쓰면 안된다!!!
• atomic을 써서 해결할 수 있음!!!!
• data를 나눠서 two level로 바꾸면 좀 더 병렬성이 확보될 수 있다!!