ಣ ᴄᴏᴍᴘᴜᴛᴇʀ ᴄɪᴛʏ ഒ

Search

SearchSearch

SHPC 06 - Loop-Carried Dependences and Parallelism

Dec 31, 20249 min read

Anti Dependence and Output Dependence

  • False dependence
  • Execution order과는 관계 없이 memory location의 reuse에 의해 발생하는 의존성
  • Variable renaming을 통해 해결될 수 있다.
    • Flow dependence: S1 → S2, S3 → S4
    • Anti dependence: S2 → S3

Loop-Independent Dependences

for (i=0; i<N; i++) {
	A[i] = B[i];
	F[i+1] = A[i];
}
  • 반복문 내에서 발생하는 의존성 중 반복간의 의존성이 없는 경우
  • Iteration 간에 의존성이 없기 때문에 동시에 병렬화가 가능
  • S1과 S2가 루프의 동일한 iteration에서 동일한 위치를 reference하는 경우

Loop-Carried Dependences

  • Iteration 간에 의존성이 있기 때문에 병렬화를 못함
  • S1이 루프의 한 iteration에서 특정 위치를 reference하는데, 후속 iteration에서 S2가 동일한 위치를 reference하는 경우

Fundamental Theorem of Dependence

Dependence를 모두 지키는 reordering transformation이라면, 원본 프로그램의 의미(아웃풋)를 보존해야 한다.

Loop Fusion

  • 두 인접한 루프를 하나로 합치는 것
  • Dependence direction이 바뀌면 illegal한 변경
    • 종류는 상관 X
  • 하는 이유: Branch (loop overhead)를 줄이기 위함
    • Loop overhead
      • Branch가 많으면 control hazard가 생길 수 있음
      • jump가 많아져서 복잡해짐
      • i를 계속 증가시키는 연산, 비교 연산 등이 필요 (Fusion하면 줄어듬)
    • 또한 캐시 미스를 줄일 수도 있음. b 배열의 비슷한 부분을 순서대로 접근하기 때문

Loop Distribution (Fission)

  • Loop를 두개로 나눈다
  • Dependency cycle이 사라지면 illegal한 변경
    • Cycle이 새로 생겨난다면 괜찮다
  • 왼쪽 그래프에 오타가 있는데 둘 다 anti dependence가 있음
    • a가 이전 iteration에서 read한 값을 write함 → WAR
    • b가 이후 Iteration에서 write하는 값을 read함 → WAR
  • 하는 이유: Vectorization
    • SIMD(Single Instruction Multiple Data)와 같은 vector operation을 수행할 때 쉽게 하기 위함이다
    • 병렬처리기가 없는 그냥 최적화 관점에서는 도움이 안됨

DO-ALL loop vs DO-ACROSS loop

DO-ALL : 데이터 의존성이 없어서 각 iteration을 parallel하게 돌릴 수 있는 loop DO-ACROSS : Data hazard가 있지만 여러가지 최적화로 부분적인 parallelism이 가능한 loop (e.g. Reduction, Loop unrolling …)

Reduction

sum = 0;
for (i=0; i<8; i = i+1) {
	sum = sum + x[i];
}
  • n번의 덧셈을 필요로 하는 코드인데, 이를 O(log n)으로 줄일 수 있다.
  • +, *, min, max 등의 특징
    • Associative & Commutative
    • 항등원의 존재
  • 이러한 operation의 loop를 reduction loop라고 한다
    • Fully-parallel은 아니더라도, partially parallel하게 최적화가 가능

Parallel Reduction

  • 트리 구조를 이용
  • 아래 그림과 같이 reduction을 수행하면 된다
  • O(log N)번의 덧셈만 하면 된다

Scan

prefix_sum[0] = a[0];
for(i=1; i<8; i++){
	prefix_sum[i] = prefix_sum[i-1] + a[i];
}
  • N-1 번의 addition이 필요한데, 이를 O(logN)으로 줄일 수 있다.

  • Stride 1씩 높여가면서 옆에서 결과값을 받아오는 것
  • O(logN)

Applications

한번 알고리즘을 생각해 보라 하심

  • Calculation of polynomials
  • Calculation of recurrence relations
  • Sorting
  • Histogram

Types of Parallelism

  1. ILP (Instruction-Level-Parallelism)
    • 파이프라이닝, OoO, Superscalar …
  2. Task Parallelism
  3. Data Parallelism

Task Parallelism

  • Distinct task를 동시에 수행
  • Application을 서로 다른 병렬가능한 task들의 집합으로 나눈다
    • 대부분 병렬가능한 부분이 적다고 함
    • 리소스가 늘어난다고 해서 병렬화를 더 많이 할 수 있는것도 아닌 것이 단점
  • 그림에서도 볼 수 있듯이 놀고있는 코어가 너무 많아서 좋지 않다
    • 그래서 이 방법을 대부분 사용하지 않음

Data Parallelism

  • Loop-level parallelism이라고도 불림
  • 서로 다른 데이터에 대한 동일한 operation을 수행
  • 더 많은 데이터가 있으면 더 병렬처리가 많이 가능

SIMD

  • Single Instruction Multiple Data
  • 동일한 사이즈와 타입의 서로 다른 데이터에 대한 동일한 operation을 수행하는 Data parallelism
    • Single program counter
    • 여러 처리 유닛이 동일한 코드의 동일한 부분을 수행하므로 pc가 모두 같음
  • 일반적으로 컴파일러가 auto-vectorization을 해준다
  • Multiple parallel execution units are called lanes
    • 아래 그림은 8개 벡터이므로 8개 lane임

SPMD

  • Single Program, Multiple Data
  • 서로 다른 데이터에 대한 같은 코드를 동시에 돌리는 것
    • Conceptually, a single thread of control
  • 코어 아이디에 따라 서로 다른 데이터에 접근하도록 만들어 둠
  • 핵심적인 차이는 granularity
    • SIMD: Fine-grained. 벡터 프로세서나 GPU에서 사용됨 (하드웨어가 따로 있음)
    • SPMD: Coarse-grained. 여러 프로세서가 같은 프로그램을 처리. (프로그램을 저렇게 짜서 같은 프로그램을 처리해도 다른 데이터에 접근하게끔 하는 것)

Multithreaded Processors

  • Multithreading : 여러개의 스레드를 사용하는 것
  • 여러 스레드로부터 명령어를 뽑아 파이프라인에 Issue하게 된다
    • 스레드 각가에서 ILP를 달성
  • Functional unit은 공유한다

Thread-level Parallelism (TLP)

  • TLP는 여러 쓰레드를 사용하는 것 (throughput을 늘리기 위해)
  • ILP보다는 더 cost-effective하다

Issue Width of Superscalar

  • 4개를 한번에 이슈한다 / Issue slot이 4개다 → Issue width == 4

SuperScalar Processors

  • 여러 개의 실행유닛이 병렬로 실행되어 파이프라인에 여러 명령어를 issue할 수 있는 것
    • In-order, out-of-order issue 및 execution이 가능
  • Inefficiency in SuperScalar Processor
    • Vertical waste : 병렬처리 가능성 (하나의 쓰레드에서. 즉 ILP)
    • Horizontal waste : 파이프라인 가능성 (Stall 발생여부)

Issue

  • 한 프로세서에 의해 issue될 수 있는 최대 명령어의 갯수
  • 4개를 한번에 이슈한다 / Issue slot이 4개다 → Issue width == 4

Vertical Multithreading

  • Vertical lanes에 서로 다른 쓰레드의 명령어를 집어넣는 것
  • Context switching이 너무 자주 일어남
    • 하드웨어로 이러한 기능을 구현해서 해결
    • 레지스터를 몇세트 더 만들어 놓든지 해서 context switching을 쉽게 하도록
  • e.g.
    • CDC 6600 (Cray, 1964)
    • HEP (Burton Smith, 1982)
    • Tera MTA (1990)

Simultaneous Multithreading (SMT)

  • 각 사이클마다 모든 쓰레드에서 instruction을 선택
    • 4-way면 4개 쓰레드에서, 2-way면 2개 쓰레드에서
    • 2-way라고 해도 functional unit은 공유하기 때문에 2배 빨라지지는 않고 30%정도? 프로세서가 여러개 있는게 아니니까
  • Logical core 가 늘어난 것처럼 보이게 한다
  • e.g.
    • Intel의 Hyper-threading

  • 단점
    • thread 1과 thread2가 완전 동일한 연산을 수행하는 경우 (symmetric한 thread인 경우)
    • 동일한 functional unit을 이용하므로 스케쥴링 불가능

  • Simultaneous multithreading에는 Processor state를 여러개 두는 걸 알 수 있음
  • 실제 core가 늘어나는건 아니지만 OS 입장에서는 logical core가 늘어나는 것처럼 보인다

Question

여기서 functional unit이 smt에 하나만 있는데, 그럼 걍 vertical multithreading 아닌가? → Functional units 라고 되어 있음

Graph View

Backlinks