[Multi-Core & GPU Programming] Thread Programming

"Thread Programming"

[Programming Model]

· 병렬 프로그래밍은 여러 실행 주체가 아래와 같은 협력 방법을 통해 서로 협력해야 함

> Shared Memory Model

· 모든 Thread가 같은 메모리 공간을 공유

→ 어떤 Thread가 변수 x를 바꾸면, 다른 Thread도 해당 x를 확인 가능

> Message-Passing Model

· 각 실행 주체가 자기 메모리를 따로 가지고, 서로 메세지를 주고 받으면서 통신

→ A Process가 B Process에게 "이 데이터 사용해"라고 메세지를 전송

[Memory]

※ Byte-Addressable : 1-Byte 단위로 직접 접근 가능한 메모리 (Ex. 0x1000, 0x1001, 0x1002, …)

· HDD/SSD는 CPU처럼 1-Byte씩 직접 접근하지 못하고, 덩어리로 Read/Write (보조기억장치) (HDD : Block / SSD : Page, Block)

· Flash Memory는 비휘발성 메모리로 SSD의 핵심 (읽기 : Page / 쓰기 : Page / 삭제 : Block)

· DRAM(Dynamic RAM)은 휘발성 메모리로 싸고 용랑이 크며 Cache보다 느림 (Main Memory 역할)

· SRAM(Static RAM)은 휘발성 메모리로 빠르고 비쌈 (Cache 또는 Register에 사용)

· CPU는 DRAM 주소만 사용 → Cache는 해당 주소를 복사해서 저장

    = Cache는 자기만의 주소는 없고 Main Memory 주소를 기반으로 자동 Mapping

[Shared Memory Model]

· 모든 Thread는 같은 Address Space를 공유

→ 같은 주소에 접근하면 같은 값을 확인 = 어떤 Thread가 값을 쓰면, 다른 Thread도 해당 값을 확인 가능

△ 데이터 전달이 쉬움 & 같은 배열, 같은 객체를 같이 사용 가능

▼ 동시에 건드리면 충돌 가능 & Race Condition 같은 문제 발생 가능

▣ Single-Core CPU

· Von Neumann 구조

① CPU가 명령어를 실행

② 필요한 데이터를 메모리에서 Read

③ 계산한 결과를 다시 메모리에 Write

▣ Multi-Core CPU

· CPU 여러 개(또는 여러 Core)가 하나의 Memory를 공유

△ Core 0에서 Thread A 실행 / Core 1에서 Thread B 실행 → 둘 다 같은 메모리를 Read/Write 가능

▼ 동시에 같은 데이터에 접근 시 순서가 꼬임 → 데이터 일관성 문제 발생

▣ Reality

· 메인 메모리(RAM)는 CPU보다 느려서 CPU 근처에 작은 고속 메모리인 Cache를 두어서 자주 쓰는 데이터를 빨리 접근하도록 함

· L1 Cache : 가장 작고 가장 빠름 / L2 Cache : 중간 / L3 Cache : 더 크지만 더 느림 / Main Memory : 더 크지만 훨씬 느림

· Thread 2개가 같은 메모리를 본다고 했지만, 실제로는 각 Core가 자기 Cache에 복사본을 갖고 있을 수 있음

· 실제 HW는 계층적

→ 어떤 Cache는 Core마다 따로 존재 / 어떤 Cache는 여러 Core가 같이 사용 / Main Memory는 모든 Core가 공유

> SW 관점 : 같은 주소를 보면 같은 데이터야 함

> HW 관점 : 실제 데이터는 여러 Cache와 Memory 계층에 흩어져 있으며 이를 일관되게 유지해야 함

▣ UMA(Uniform Memory Access)

· 모든 CPU가 메모리에 접근할 때 대략 같은 비용이 드는 구조

▣ NUMA(Non-Uniform Memory Access)

· 메모리가 논리적으로는 공유되지만, 물리적으로는 여러 Node에 나뉘어 있어 어느 메모리를 읽느냐에 따라 접근 시간이 다른 구조

· 각 Node에 자기 메모리(memory0/memory1)가 붙어있고, Node끼리는 Interconnect로 연결

· 어떤 주소는 Node 0의 메모리에 존재하고, 어떤 주소는 Node 1의 메모리에 존재

    ∴ Thread가 자기 Node 메모리에 접근하면 빠르고 다른 Node 메모리에 접근하면 Interconnect를 거쳐야 해서 느려짐

Ex. Thread 0은 0x0500 접근 시 100ns / Thread 1은 0x0500 접근 시 (100+50)ns

▣ 메모리 배치 방법 in NUMA

· First Touch : alloc( )으로 메모리 접근 시 처음 접근한 CPU/NUMA Node의 로컬 메모리에 할당

▣ 수동 제어 방법 방법 in NUMA

· --membind : 어느 NUMA Node 메모리에 둘지 지정

· --cpunodeind : 어느 Node의 CPU를 사용할지 지정

· --physcpubind : 특정 CPU 지정

· --interleave : 메모리를 여러 Node에 분산 배치

→ NUMA 성능 최적화는 Thread 배치 + Memory 배치를 같이 봐야 함

** Shared Address Space 주의

· Mutual Exclusion : 동시에 같은 데이터 수정 금지

· Interconnect : Core와 메모리, Core와 Core 사이의 연결 필요

· Scalability : Core 수가 많아질수록 관리 어려움

· Cache Coherence : 여러 Cache의 데이터가 일관되게 보여야 함

[Programming with Threads]

· 과거에는 Thread 사용 시 "pthread_create", "pthread_join" 사용 → C Style

· C++11부터는 "#include <thread>, std::thread t(…)" 사용

① 길이가 100인 배열 a, b, k, c 생성 후 초기화

② 각 원소마다 c[i] = k[i] * a[i], c[i] += k[i] * b[i] 실행 → c[i] = (k[i] * a[i]) + (k[i] * b[i])

** 각 i에 대한 계산이 서로 독립적 → 배열의 구간을 나눠 병렬화 가능

· mac 함수 : 전체 배열을 num_threads개로 나누고, 현재 Thread가 담당할 Index를 계산
· sdt::thread : Thread를 생성하며, 생성하는 순간 새 Thread가 바로 실행

· thread.join( ) : Main Thread가 자식 Thread의 작업이 끝날 때까지 대기

· thread.detach( ) : thread.join( ) 대신 사용 시, Thread를 부모 Thread와 분리해서, 독립적으로 실행되게 함

    → 결과를 나중에 꼭 회수할 필요가 없고, 독립적으로 돌아가도 되는 작업에 사용

    → 현재 예제는 배열 a, b, k, c가 같은 공유 데이터를 사용하므로 detach 위험

▣ Create & Join

① Main Thread가 "std::thread(…)"로 새 Thread 생성

② 새 Thread가 "mac( )" 함수 실행

③ Main Thread는 "join( )"에서 대기

④ 자식 Thread가 끝나면 Main Thread가 다시 진행
→ "join( )"은 Main Thread와 자식 Thread의 실행 시점을 맞추는 동기화 지점

▣ Create & Detach

① Main Thread가 "std::thread(…)"로 새 Thread 생성

② 새 Thread가 "mac( )" 함수 실행
③ Main Thread가 "detach( )" 실행 시 생성된 Thread는 독립적으로 실행

▣ Join vs Detach

· 끝까지 기다릴 거면 "join( )", 독립적으로 실행시킬 거면 "detach( )" 둘 중 하나는 필수로 실행

→ 아무것도 지정하지 않으면 "malloc" 후, "free"를 안하는 것과 비슷 = Resource Leak(자원 누수)

[Callable]

· Function Pointer / Function Object / Lambda Expression

→ 호출할 수 있는 것 = "( )"를 붙여 실행할 수 있는 대상

▣ Function Pointer

· Thread 생성 시, "mac" 함수를 새 Thread가 실행

△ 단순 & 함수가 명확히 분리 & 입문 단계에서 가장 이해하기 쉬움

▼ 주변 지역 변수를 자연스럽게 캡처하기 어려움 & 상태를 담아두려면 인자를 많이 넘겨야 함

∴ 간단하지만 유연성 부족

▣ Function Object

· "target"이 가리키는 값을 1로 변경 = Thread가 실행되면 어떤 변수에 1을 저장

※ 함수 객체 : Class인데, "operator( )"를 정의해서 함수처럼 호출할 수 있게 만든 객체
→ "set_object obj; obj(&a);"처럼 작성할 수 있고, "std::thread"의 Callable 자리에 사용할 수 있음

△ 함수 객체는 상태를 가질 수 있어, 단순 함수보다 더 유연

▼ 코드 길이 증가

∴ 유연하지만 코드 길이 증가

▣ Lambda Expression

· [캡처] (매개변수) {실행 코드} 형태

· Lambda는 주변 변수들을 가져와서 사용 가능

∴ 짧고 직관적 + 유연

[Race Condition & Locks]

※ Race Condition : 여러 Thread가 같은 변수나 자료 구조를 동시에 접근 할 때, 실행 순서에 따라 결과가 달라지는 문제

※ Lock : Race Condition을 방지하기 위해 어떤 구역에 한 번에 한 Thread만 들어가게 만드는 장치

▣ Single Thread

① 크기가 N인 배열 생성

② 배열을 전부 0으로 초기화

③ 배열을 처음부터 끝까지 읽으면서 값이 0인 경우 "count" 1씩 증가

④ 마지막에 0의 개수 출력

▣ Multi Thread

① "main" 함수에서 "Command-Line Arguments"로 배열의 전체 크기(N)와 생성할 Thread의 개수(NT)를 입력 받음

② 크기가 N인 배열을 동적 할당받고 모든 원소를 0으로 초기화

③ 각 Thread는 "worker" 함수 실행하여, 자신이 할당받은 구간을 반복문으로 탐색하며, 값이 0인 경우 공유 변수인 "count" 1씩 증가

④ 모든 Thread의 작업이 끝날 때까지 기다린 후, 마지막에 0의 개수인 "count" 출력

· 예상 결과 값 : 0의 개수 = 10,000,000개 / 실행 결과 : 0의 개수 = 5,028,741개

∵ 공유 변수 "count"를 여러 Thread가 동시에 증가시킴

① Thread 0이 0을 Read

② Thread 1도 거의 동시에 0을 Read

③ 둘 다 자기 내부 계산으로 "count" 증가로 1을 생성
④ 둘 다 1을 Write

→ 실제로는 2번 증가해야 하는데 결과는 1만 반영

∴ Thread 0가 Write가 끝날 때까지 다른 Thread의 Access를 Block해야 함

** Core ≥ Thread : 각 Thread가 Core 하나씩 사용 → 병렬 실행

** Core < Thread : 한 Core가 여러 Thread를 번갈아 실행 → 빠르게 Switching해서 동시에 실행하는 것처럼 보임

→ 두 경우 모두 Race Condition 발생 가능

▣ Race Condition

· "Read-Add-Write"는 시간이 걸리고, 다른 Thread가 사이에 끼어들어 중간에 끊길 가능성 존재

· 공유 데이터에 대해 여러 Thread가 동시에 접근해서, 어떤 순서로 실행되느냐에 따라 결과가 달라짐

▣ Mutex

· Race Condition을 막기 위한 도구로, 잠금을 사용하여 어떤 Code 구간을 한 번에 하나의 Thread만 실행하게 함

· 한 Thread가 Lock을 잡으면, 다른 Thread는 Unlock될 때까지 대기

→ Critical Section을 직렬화해서 올바른 결과 보장

※ Critical Section : 공유 데이터를 Read/Write하므로, 동시에 실행되면 안되는 Code 구간 (Ex. count++)

<Mutex 사용>

· "global_mutex" 선언 후, inc( ) 함수 안에서 lock( ) → (*output)++ → unlock( )

    = Count를 증가시키는 부분만 Lock → 한 번에 하나의 Thread만 증가할 수 있게 함

· 10,000,000 전부 Count 완료

△ Count 증가가 겹치지 않으므로 Race Condition이 사라져 정확성↑

▼ Thread가 많아도 Count++ 할 때마다 순서를 기다려야 하므로 해당 부분은 병렬 불가 → Lock Overhead와 대기 시간 등장

<unlock( ) 누락>

· 1번째 Thread가 Mutex를 잡고 작업 수행 후, unlock 누락 → 다른 모든 Thread는 영원히 Lock 차례 대기 = Deadlock

** Lock 사용 후 반드시 Unlock해야 하지만 수동으로 Lock/Unlock을 짝지어 관리하면 실수 가능성↑

▣ RAII(Resource Acquisition Is Initialization)

<lock_guard 사용>

① 함수 시작 시 "lock_guard" 객체를 생성

② 객체가 생성되면서 mutex를 자동으로 lock

③ 함수가 끝날 때 객체가 소멸되면서 자동으로 unlock

** "Mutex Lock"을 얻는 순간 객체에 맡기고 객체의 생명 주기에 따라 자동으로 정리 → 사람이 직접 unlock( )을 작성하지 않아도 됨

· 함수 중간에 return이 있어도 자동 해제 가능

· 예외 처리가 발생해도 자동 해제 가능

· Lock/Unlock 짝을 실수할 가능성 대폭 감소

> File에서 RAII의 필요성

<Early Return>

· File Open 후, 함수 중간에서 종료 → 아래에 있는 fclose(f)까지 도달 불가

· Mutex에 비유하자면, Lock한 후 중간에 return해서 unlock을 하지 못하는 상황

<보완된 Early Return>

· Early Return 직전에 직접 fclose(f)를 추가하여, Return 전에 수동으로 File Close → Code가 커질수록 실수 위험↑

∵ Return 지점이 여러 개 있을 수 있는데 모든 경로마다 fclose를 넣는 것은 매우 번거롭고 실수 가능성↑

<Exception>

· 중간에 예외가 발생하는 순간, 함수 아래쪽의 fclose(f)는 실행되지 않을 가능성 존재

** 자원 정리를 수동으로 진행 시 Control Flow가 복잡해질수록 실수 가능성↑    ∴ 자동으로 관리하는 RAII 필요

<RAII 사용하여 File 관리>

· FILE_guard Class를 만들어 생성자에서 fopen, 소멸자에서 fclose

→ {정상 종료 / Early Return / Exception} 상관없이 지역 객체는 Scope를 벗어날 때 소멸자가 호출되므로 자동으로 File Close

> Thread에서 RAII 사용

<RAII 사용하여 Thread 관리>

· thread_guard Class는 "std::thread& t"를 멤버로 들고 있고, 소멸자에서 t.joinable( )이면 join( ) 호출

→ 함수가 끝날 때 Thread를 자동으로 join하게 함 (Thread 생성 후 join( ) 누락 시 문제 발생)

** 아래 2줄은 복사를 금지하는 중요한 Code    ∵ 같은 Thread를 여러 guard가 관리하면 누가 join할지 애매 & 중복 관리 문제 발생

    → 자원 관리 객체는 보통 단일 소유

** RAII는 파일뿐만 아니라 Thread에도 적용 가능하여 Thread 정리도 자동화 가능

▣ Deadlock

· 어떤 작업 진행 시 mutex A와 mutex B 모두 필요

· Thread 0은 A를 먼저 Lock한 후 B를 기다리고, Thread 1은 B를 먼저 Lock한 후 A를 기다림

→ 서로가 서로의 Lock 해제를 기다리게 되어 Unlock까지 진행 불가 = Deadlock

** 각 Thread가 일부 자원을 이미 보유한 상태에서 나머지 자원을 기다림 → 서로가 서로를 기다림

<Deadlock Example Code>

· swap(v1, v2)에서 v1.m.lock( ) → v2.m.lock( ) 순서로 두 Mutex를 Lock

· main 함수에서 한 Thread는 swap(x, a), 다른 Thread는 swap(a, x)를 동시에 실행

    = 한 Thread는 x를 먼저 Lock한 후 a를 기다리고, 다른 Thread는 a를 먼저 Lock 한 후 x를 기다림

→ Deadlock 발생

** std::thread는 기본적으로 인자를 값으로 넘기려 하고, swap은 참조 인자를 원함

    ∴ std::ref(x)처럼 참조 ref로 전달해야 원본 객체를 넘길 수 있음

> Deadlock Solution

· 여러 Mutex를 Lock해야 한다면 항상 같은 순서로 일관된 규칙을 정하여 Lock을 진행

<std::lock( )>

· 직접 "v1.m.lock( ) → v2.m.lock( )"을 작성하는 대신 "std::lock(v1.m, v2.m)" 작성

→ 표준 Library가 안전한 방식으로 둘 다 Lock = Lock 순서 관리 실수↓

→ 여러 Thread가 같은 Mutex 집합을 반대 순서로 요청해도 Deadlock을 피하도록 구현됨

** 이 Code는 Lock만 자동이고, Unlock은 여전히 수동

<std::lock( )>

· swap( ) 안에서 두 Mutex를 Lock할 때 "std::lock(v1.m, v2.m)" 사용

→ swap(x, a)와 swap(a, x)가 동시에 실행돼도 Deadlock 없이 진행 가능

** Lock 자동 / Unlock 수동

<adopt_lock + lock_guard>

· std::lock(v1.m, v2.m)을 통해 두 Mutex를 먼저 안전하게 Lock

· adopt_lock : 이 Mutex는 이미 Lock되어 있으니, lock_guard가 해당 소유권을 넘겨받아 관리
    = lock_guard가 새로 Lock하는 것이 아니라, 이미 잠겨 있는 Mutex를 책임지고 나중에 자동 Unlock

** Deadlock은 std::lock이 방지 / Unlock 누락은 lock_guard가 방지

▣ Wait

· Producer : 1초마다 Shared Queue에 Item을 넣음

· Consumer : Queue가 비어있지 않으면 Item을 꺼냄

** Queue는 공유 자료구조이므로 Mutex로 보호해야 함

→ But, Consumer는 "Queue가 빌 때마다 계속 확인"해야 하는 문제 발생

∴ 어떤 상태가 될 때까지 효율적으로 Wait하는 것이 필요

> Bad Way

<Busy Wait>

· while (shared_queue.empty( )) { … } : 계속 Queue가 비었는지 확인

▼ 데이터가 아직 안 왔는데도 CPU를 계속 사용

▼ 아무 일도 안 하면서 반복적으로 조건만 확인

→ Consumer는 Producer가 1초 후에 Item을 Queue에 넣는 것을 알면서도 1초 내내 CPU 시간 사용 = 자원 낭비↑

∴ 조건을 기다릴 때 단순 반복 확인은 비효율적

> Slightly Better Way

<Busy Wait + Sleep>

· sleep_for : Queue가 비어 있으면 바로 다시 확인하지 않고 100ms 정도 Sleep했다가 다시 Wake-Up해서 확인

▼ 반응 지연 : Producer가 넣은 시점에 Consumer는 다음 Wake-Up 시점까지 확인 불가

▼ Sleep 시간 선택 애매 : 너무 짧으면 여전히 낭비 / 너무 길면 반응 지연

▼ 생산 주기 인지 : 1초마다 생산된다는 생산 주기를 Programmer가 인지 필요

> Preferred Way

<Condition Variables>

· Producer는 Item을 Queue 넣고 "cond.notify_one( )", Consumer는 "cond.wait(…)"
→ Producer가 데이터를 넣으면서 신호를 보내서 "Queue가 비어 있지 않다"는 조건이 만족될 때까지 Sleep하는 Consumer를 깨움

△ 기다리는 동안 CPU를 낭비 X

△ 필요한 순간에만 Wake-Up

△ 생산 주기를 미리 알 필요 X

△ Queue 자체가 공유 자료구조이므로 Producer & Consumer 모두 Push/Pop을 할 때 Mutex를 잡고 있음

→ Condition Variable은 상태 변화 알림, 효율적인 대기를 위한 도구 / Mutex는 여전히 자료 보호용으로 필요

▶ cond.wait(unique_lock, predicate function)

· lock_guard와 비슷하지만, 필요하면 Unlock 가능하여 condition_variable과 함께 쓰기 적합

① Predicate를 먼저 검사 : Queue가 비어있지 않으면 바로 진행

② 비어있는 경우 : Lock을 잠시 풀고 Sleep

③ Signal을 받은 경우 : 다시 Lock을 획득하고 Predicate를 다시 검사

④ Predicate True : 다음 Code 실행

→ 깨웠다고 해서 반드시 조건이 참이라는 보장이 없기 때문에, Signal이 오면 Predicate를 다시 검사하여 조건 다시 확인

▶ notify_one / notify_all

· notify_one( ) : 기다리는 Thread 중 하나를 깨움

· notify_all( ) : 기다리는 모든 Thread를 깨움

→ 여러 Consumer가 있는 경우

· 하나의 Item만 생긴 경우 : notify_one( ) / 상태 변화가 모든 대기 Thread에 중요한 경우 : notify_all( )

> Atomics

· Lock/Unlock 사이의 일이 아주 단순하면 Atomic 사용 가능

→ 특별한 HW 명령으로 구현되며 Mutex보다 훨씬 빠를 수 있음 (But, 일반 연산보다는 훨씬 느림)

Ex. "output += 1"과 같은 단순 증가를 Mutex로 감싸지 않고 "std::atmic<int>output;"으로 선언

→ 증가 자체를 원자적으로 처리 가능

△ Mutex처럼 Lock 경쟁이 덜함

△ 아주 짧은 연산에서 효율적

▼ 복잡한 자료구조 조작이나 여러 변수의 일관성을 동시에 맞춰야 하는 경우에는 Mutex 또는 더 복잡한 동기화 필요

∴ 단순 Counter/Flag 같은 것은 Atomic 매우 유용, But, 복잡한 Critical Section 전체를 Atomic 하나로 대체 불가

▣ Barrier

· 모든 Thread가 특정 단계인 Barrier에 도달할 때까지 아무도 다음으로 넘어갈 수 없음

· join( )은 Thread가 끝날 때까지 Wait & Thread 종료 ≠ barrier는 Thread가 중간 지점에 도달할 때까지 Wait

· C++ 표준에 없어서 boost Library 사용

· boost::barrier bar(NT) : NT개 Thread가 도착해야 다음으로 갈 수 있는 Barrier 생성

· Worker 안에서 반복하다가 if (i % 1000 == 0) bar.wait( ); → 1000번마다 모든 Thread가 동기화

    = 각 Thread가 자기 구간을 처리하다가 매 1000번째마다 한 번씩 집합하는 구조

∴ barrier는 반복문 중간중간 진행 속도를 맞추는 장치

    → 어떤 Thread가 너무 빨리 앞서가면 기다리게 하여 모든 Thread가 특정 단계까지 계산을 끝냈는지 보장 가능

▣ Implement a Barrier with Mutexes & Conditional Variables

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <mutex> #include <condition_variable>   class MyBarrier { private:     std::mutex mtx;     std::condition_variable cv;     int target_count;     int count;     int generation;   public:     // 생성자: 목표 쓰레드 수를 받아서 초기화     explicit MyBarrier(int n) : target_count(n), count(0), generation(0) {}       void wait() {         // 1. Mutex 잠금 (공유 변수 보호)         std::unique_lock<std::mutex> lock(mtx);                  // 2. 현재 진입한 쓰레드의 세대 기억         int current_generation = generation;           // 3. 도착한 쓰레드 카운트 증가         count++;           // 4. 자신이 마지막으로 도착한 쓰레드인지 확인         if (count == target_count) {             // 모든 쓰레드가 도착함             generation++;    // 다음 세대로 업데이트 (재사용을 위함)             count = 0;       // 다음 번 사용을 위해 카운터 초기화             cv.notify_all(); // 대기 중인 모든 쓰레드를 깨움         } else {             // 아직 모든 쓰레드가 도착하지 않음             // Spurious wakeup(가짜 깨어남)을 방지하기 위해 람다 함수로 조건(Predicate) 확인             cv.wait(lock, [this, current_generation] {                 // 세대가 바뀌었으면(마지막 쓰레드가 도착해 generation을 증가시켰으면) true를 반환하여 루프 탈출                 return current_generation != generation;             });         }     } }; Colored by Color Scripter

cs

① Thread가 wait 함수 호출 시 Mutex Lock 진행

② count를 증가시켜 도착했음을 알림

③ count가 target_count와 같다면, 마지막 Thread 도착

    → count를 0으로 초기화하고 대기중이던 모든 Thread를 깨움

④ count가 target_count보다 작다면, 아직 도착하지 않은 Thread 존재

    → cv.wait( )을 호출하여 대기 상태 진입

· generation을 교체하는 이유는 모든 Thread들이 notify_all에 의해 깨어나면 cv.wait( )의 두 번째 인자인 Lambda 함수를 검사

→ current와 다르면 통과

∴ Thread가 OS에 의해 이유없이 깨어나는 현상을 방어 + Loop 안에서 재사용할 때도 Thread간 실행 순서가 엉키지 않도록 함

[Thread-Safety]

※ Thread-Safe : 공유 데이터를 Multi-Thread로 실행해도 괜찮은 경우

▣ Thread-Safe Queue

· std::queue<T> : C++ 표준 Library에 있는 Queue 자료 구조 (FIFO)

· _queue : 실제 데이터를 저장하는 내부 컨테이너 역할 → 데이터를 순서대로 저장하는 큐

· std::mutex : 한 번에 하나의 Thread만 접근하도록 Lock하는 역할

    ∵ 여러 Thread가 동시에 "_queue"에 접근 시 문제 발생 가능
· public : 접근 지정자 → 이 아래에 오는 함수나 변수는 외부에서 접근 가능

** push( )와 pop( )에서 각각 lock_guard로 Mutex를 Lock = Queue를 건드리는 모든 연산을 하나의 Mutex로 보호

△ 구현이 쉬움

△ Push/Pop이 동시에 들어와도 Queue가 망가지지 않아 안전

▼ Push/Pop이 서로 다른 부분을 건드릴 수 있는데 전부 같은 Lock 하나를 잡아야 해서 한 번에 하나만 작업 가능

∴ 정확도↑, But, 병렬성↓

▣ Linked-List Queue

<Not Thread-Safe Yet>

· push( )는 Tail 사용 / pop( )은 Head 사용

→ 모든 연산이 Queue 전체를 똑같이 건드리는 것이 아니라, 연산에 따라 접근하는 곳이 다름

<Thread-Safe Linked-List Queue>

· std::mutex head_mtx / std::mutex tail_mtx : Queue 전체를 하나로 Lock하지 않고, 앞뒤를 분리해서 Lock

→ Push/Pop이 서로 다른 Lock을 사용하여 어떤 경우에는 동시에 실행 가능

∴ 안정성을 유지하면서 병렬성↑

※ Coarse-Grained Locking : 전체 자료 구조 하나의 큰 Lock

※ Fine-Grained Locking : 자료 구조 일부마다 더 작은 Lock

[Amdahl's Law]

· Speed-Up은 병렬 가능한 부분에 의해 제한되므로, 병렬화로 얻을 수 있는 Speed-Up은 한계 존재

→ Core를 아무리 많이 넣어도 병렬화 불가능한 직렬 부분이 0이 아닌 이상 무한정 빨라질 수 없음

※ Serial Part(T_S) : 병렬화 불가능한 부분 (Ex. Atomic Addition, Dividing Jobs, …)

※ Parallel Part(T_P) : 병렬화 가능한 부분 (Ex. Vector Addition, Matrix Multiplication, …)

※ 1개의 Processor : T(1) = T_S + T_P / P개의 Processor : T(P) = T_S + (T_P / P)

** T_P가 클수록 유리 & T_S가 클수록 불리 → P가 커질수록 병렬 부분 시간은 줄지만, Serial 부분은 그대로 남음

※ 전체 시간 중 T_S의 비율을 f → 전체 시간 중 T_P의 비율은 1 - f

** f↑ = T_S↑ = S↓ & f↓ = T_P↑ = S↑

** P → ∞, S_max = 1/f

Ex 1) Sequential Part = 40%, Parallel Part = 60%, # of Processor = 6 → S = 2

    → Sequential Part가 40% 되는 Program에서 6개의 Processor를 써도 2배 빨라지는 것이 한계

Ex 2) Sequential Part = 10%, Parallel Part = 90%, Get x5 Speed-Up → P = 9

    → Sequential Part가 10% 되는 Program에서 5배의 Speed-Up을 얻으려면 9개의 Processor 필요

Ex 3) Sequential Part = 50%, Parallel Part = 50%, Get x2 Speed-Up → P = ∞

    → Sequential Part가 50% 되는 Program에서 유한한 Processor의 개수로는 2배의 Speed-Up 불가능

[Reference]

· 2_thread_mgp_2026 (MGP) - Yongjun Park