ෆ Create & Join & Detach

#include <iostream>
#include <thread>
#include <vector>
int *a, *b, *k, *c;

void mac(int tid, int num_threads)
{
    for(int i-0;i<N/num_threads;i++) 
    {
        int idx = tid*(N/num_threads) + i;
        c[idx]  = k[idx] * a[idx];
        c[idx] += k[idx] * b[idx];
    }
    return;
}
int main(int argc, char* argv[])
{
...
    std::vector<std::thread> threads;
    for(int t=0;t<NT;t++) {
        // create thread
        threads.push_back(std::thread(mac, t, NT));
    }
    for(auto& thread: threads) {
        // wait for finish
        thread.join();
        // don't want to wait for finish ..
        //thread.detach();
    }
    return 0;
}

ಌ Create

std::thread(mac, t, NT)

• 새로운 thread를 생성하는 데에 사용되는 코드
  • 새로운 thread 객체 생성
  • 해당 thread에서 실행될 작업 지정 가능
• mac : 호출 가능한 객체 (callable)
  • callable : thread에서 실행될 작업을 정의하는 함수
  • 별도의 thread에서 실행됨
• t, NT : mac에 전달되는 인수

ಌ Join

thread.join();

• thread는 호출 가능한 객체가 반환될 때까지 기다린 뒤 반환

  • 호출 가능한 객체가 실행을 완료하면 해당 thread가 종료

• 위의 코드는 호출한 thread가 대상 thread가 종료될 때까지 기다림

  • 이 method를 호출한 thread는 대상 thread가 종료될 때까지 블록됨

    → 여러 thread간에 작업의 실행 순서 조절, thread들의 실행 동기화

• thread가 이미 join되었는지 여부 확인 : thread.joinable();

  • 부울 값을 반환

• join();

  • 부모 thread가 생성한 자식 thread가 종료될 때까지 대기
    • 부모 thread는 자식 thread의 종료를 기다림
    • 자원을 정리하거나 결과를 처리할 수 있음

ಌ Detach

thread.detach();

• 스레드가 호출 가능한 객체가 반환될 때까지 기다리지 않고, 스레드의 실행을 기다리지 않고 다른 작업을 수행하고 싶다면, 스레드의 실행을 조인하지 않으면 됨

• 스레드가 호출 가능한 객체가 반환될 때까지 기다리지 않고 실행을 계속하면, 스레드의 실행이 끝나지 않았더라도 호출 가능한 객체가 반환될 때까지 기다리지 않고도 다른 작업을 수행할 수 있음

• 호출 가능한 객체가 반환되기 전에 해당 스레드의 리소스가 정리되지 않을 수 있음

  • 메모리 누수나 예기치 않은 동작이 발생할 수 있음

• detach();

  • 부모 thread가 생성한 자식 thread가 독립적으로 실행
    • 부모 thread는 자식 thread의 종료를 기다리지 않음
    • 자원을 자식 thread에게 넘기고 별도의 작업 수행 가능

• 만약 부모 thread가 자식 thread에게 할당한 자원을 정리하지 않고 detach() 를 호출하지 않는다면?

  • 자식 스레드가 종료될 때까지 부모 스레드는 해당 자원을 계속해서 유지

    → 메모리 누수와 같은 문제 발생

ಌ Callable

호출 가능한 객체 : 함수처럼 호출될 수 있는 객체

1. Function pointer

void mac(..params..)
{...}
...
std::thread(mac, ..params..)

• 함수의 memory address를 가리키는 pointer
• 함수의 이름 또는 주소를 가리킴

2. Function object

class set_object
{
    public;
    void operator()(int* target)
    {
        *target = 1;
    }
};

int main()
{
    std::thread t(set_object(), &a);
}

• 클래스 객체로서 operator() 멤버 함수를 구현함으로써 호출 가능한 객체를 만듦
• 함수처럼 호출될 수 있으며, 상태(state)를 유지할 수 있음
• 함수 pointer보다 유연하고 풍부한 기능 제공

3. Lambda expression

int b = 0;
std::thread t2([](int* target) {
    *target = 1;
    }, &b);
t2.join();

• 익명 함수를 생성하는 간결한 방법
• 함수처럼 호출되며, 함수 객체를 만듦
• 주로 간단한 코드 조각 표현 시 사용

❦ Race Condition

동시에 여러 thread나 process가 shared resource에 접근할 때 발생 주로 Read-Modify-Write 연산이 동시에 수행될 때 발생

문제는 Read-Modify-Write 연산이 여러 thread에 의해 동시에 실행될 수 있고, 이들의 실행 순서가 보장되지 않는다는 것 ,,→ 하나의 thread가 Read 연산을 수행하는 동안, 다른 thread가 그 값을 Modify하거나 Write 연산을 수행할 수 있음

#include <iostream>
#include <thread>
#include <vector>

void worker(int* input, int start, int size, int* output)
{
    for(int i=0;i<size;i++) {
        if(input[start+i]==0 {
            (*output)++;
        }
    }
}

int main(int argc, char* argv[])
{
    const int N = atoi(argv[1]);
    const int NT = atoi(argv[2]);
    int *array = new int[N];

    for(int i=0;i<N;i++) {
        array[i] = 0;
    }

    int count=0;
    std::vector<std::thread> threads;
    for(int t=0;t<NT;t++) {
        //assume N is a multiple of NT
        int size=N/NT;
        int start = t*size;
        threads.push_back(std::thread(worker,array,start,size,&count));
    }
    for(auto& thread:threads) {
        thread.join();
    }

    std::cout<<"there are "<<count<<"zeros"<<std::endl;
}

⇒ 결과는 thread들 간의 race condition에 따라 달라지게 됨

(thread가 자원에 접근하는 순서와 타이밍에 따라 결과가 달라질 수 있음)

race condition은 예측할 수 없는 결과를 초래하며, 디버그하기 어렵고 심각한 버그를 유발할 수 있음

→ 적절한 동기화 메커니즘을 사용 ~> 공유 자원에 대한 접근 제어, 경쟁 조건을 회피하거나 방지

ෆ Mutex

상호 배제(mutual exclusion)를 제공하는 동기화 기법 중 하나 여러 thread간에 공유된 resource에 대한 안전한 접근을 보장

• critical section (임계 영역)

  : 상호 배제(mutaual exclusion)를 필요로 하는 코드 영역

  → 여러 thread가 동시에 접근하면 안 되는 공유 자원에 대한 접근을 제한하는 코드 부분

  • 공유된 자원을 업데이트하거나 수정하는 코드 영역

  • 여러 thread가 동시에 critical section에 접근하면, 경쟁상태가 발생할 수 있어 데이터의 일관성이 깨질 수 있음

    → 한 번에 단 하나의 thread만이 critical section에 접근할 수 있도록 상호 배제 매커니즘 사용

• locked 상태

  mutex가 잠겨 있는 상태, 이 때 mutex를 소유한 thread만이 공유 자원에 접근 가능

  • 오직 하나의 thread만이 lock을 획득할 수 있도록 보장
  • 다른 thread가 mutex를 lock하려고 시도하면, 해당 thread는 mutex가 unlock될 때까지 대기해야 함
  • → 여러 thread간에 공유된 자원에 대한 안전한 접근이 보장됨

• unlocked 상태

  mutex가 잠금 해제된 상태, 다른 thread가 mutex를 잠글 수 있게 됨

std::mutex global_mutex;

void inc(int* output)
{
    global_mutex.lock;
    (*output)++; //critical section
    global_mutex.unlock(); //FORGOT TO UNLOCK?
}

void worker(int* input, int start, 
int size, int* output)
{
    for(int i=0;i<size;i++) {
        if(input[start+i]==0) {
            inc(output);
        }
    }
}

unlock하는 것을 잊는 등, mutex를 부주의하게 사용하면 deadlock 상황이 발생할 수 있음

모든 thread가 mutex를 얻지 못해 무한정 기다리는 상황이 발생하여 더 이상 진행이 불가 ,,

std::mutex global_mutex;

void inc(int* output)
{
    std::lock_guard<std::mutex> guard(global_mutex);
    (*output)++;
}

void worker(int* input, int start, 
int size, int* output)
{
    for(int i=0;i<size;i++) {
        if(input[start+i]==0) {
            inc(output);
        }
    }
}

• lock_guard

  RAII(Resource Acquistion Is Initialization) 기법을 활용하여 뮤텍스를 안전하게 관리

  뮤텍스를 자동으로 잠그는 객체

  • 객체가 생성될 때 뮤텍스를 잠금 상태로 만듦
  • 객체가 소멸될 때 뮤텍스를 자동으로 해제
  • lock_guard 객체의 생성자에서 뮤텍스를 잠그고, 소멸자에서 뮤텍스를 해제

• RAII (Resource Acquistion Is Initialization)

  • "자원 할당은 초기화(Initialization)의 책임을 갖는다”

  • 객체의 생성자에서 자원을 할당하고, 소멸자에서 자원을 해제하여 자원 누수를 방지

  • ex. Using RAII for thread join

    class thread_guard
    {
    std::thread& t;
    public:
    
      thread_guard(std::thread& t_):t(t_)
      {}
    
      ~thread_guard()
      {
          if(t.joinable())
          {
              t.join();
          }
      }
      thread_guard(thread_guard const&) = delete; //del copy constructor
      thread_guard& operator=(thread_guard const&) = delete; // del copy operator
    };

    ෆ Deadlock 교착상태

thread 혹은 process가 자원을 얻지 못해 다음 처리를 하지 못하는 상태 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

• 다음 4가지 상황이 동시에 성립할 때 발생

  1. 상호 배제 (Mutual exclustion)

     : 자원은 한 번에 하나만 사용가능

  2. 점유 대기 (Hold and wait)

     : 최소한 하나의 자원을 점유하고 있으면서 다른 process에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 process가 있어야 함

  3. 비선점 (No preemption)

     : 다른 process에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

  4. 순환 대기 (Circular wait)

     : process의 집합 {P0, P1, P2, … ,Pn} 에서 P0은 P1이 점유한 자원을 점유하기 위해 대기하고 P1은 P2가 점유한 자원을 점유하기 위해 대기하고 … Pn-1은 Pn이 점유한 자원을 점유하기 위해 대기하며 Pn은 P0가 점유한 자원을 요구해야 함

     class int_wrapper
     {
     public:
      int_wrapper(int val):val(val){}
      std::mutex m;
      int val;
     };
     void swap(int_wrapper& v1,
                          int_wrapper& v2)
     {
     v1.m.lock();
     v2.m.lock();
     int tmp = v1.val;
     v1.val = v2.val;
     v2.val = tmp;
     v1.m.unlock();
     v2.m.unlock();
     }
     

int main() { int_wrapper a(0); int_wrapper x(1);

for(int i=0;i<10000;i++) {
    std::cout<<"start iteration "<<i<<std::endl;
    std::thread t1(swap, std::ref(x), std::ref(a)) ;
    std::thread t2(swap, std::ref(a), std::ref(x)) ;

    t1.join();
    t2.join();
    std::cout<<"done a: "<<a.val<<", x:
    "<<x.val<<std::endl;
}
    return 0;

}

![](https://velog.velcdn.com/images/ii_seo/post/add31dd8-f274-4f1d-9829-d9000d6a62ab/image.png)
- 두 개의 mutex를 가지고 있음
- 각 mutex를 잠근 후 다른 mutex를 잠그는 swap 함수 정의
- swap함수를 두 thread에서 반복적으로 호출 → deadlock 발생

→ deadlock이 발생하는 이유 ?

- 각 thread가 서로 다른 순서로 mutex를 잠그기 때문,,
- 이러한 상황에서 두 thread는 서로가 가진 mutex를 얻지 못해 무한정 기다리게 되어 deadlock이 발생!
### 해결방법 ?

1. lock multiple mutexes

    `std::lock` 을 사용해 여러 개의 mutex를 한 번에 lock

    → 모든 Mutex를 안전하게 lock 가능, deadlock의 위험을 피할 수 있음

void swap(int_wrapper& v1, int_wrapper& v2) { std::lock(v1.m, v2.m); int tmp = v1.val; v1.val = v2.val; v2.val = tmp; v1.m.unlock(); v2.m.unlock(); }

2. use lock_guard, adopt_lock

    `std::lock`을 사용해 두 개의 mutex를 한 번에 잠그고, 이를 `lock_guard`나 `unique_lock` 객체에 `adopt_lock` 옵션을 주어 넘겨줄 수 있음

    - `adopt_lock` : 이미 잠겨 있는 mutex를 전달할 수 있게 해줌

        → 두 mutex를 안전하게 잠그고 데드락을 피할 수 있음

class int_wrapper { public: int_wrapper(int val):val(val){} std::mutex m; int val; }; void swap(int_wrapper& v1, int_wrapper& v2) { std::lock(v1.m, v2.m); std::lock_guardstd::mutex lock_v1(v1.m, std::adopt_lock); std::lock_guardstd::mutex lock_v2(v2.m, std::adopt_lock); int tmp = v1.val; v1.val = v2.val; v2.val = tmp; }

## ෆ Wait
![](https://velog.velcdn.com/images/ii_seo/post/6d48fe02-8f1e-4b0d-823b-3262c4f687a2/image.png)producer-consumer 문제

: multi-thread 환경에서 공유 자원인 queue를 여러 producer thread가 data를 추가하고, 여러 consumer thread가 data를 소비하는 상황

→ producer thread가 data를 queue에 추가할 때 queue가 가득 차 있는 경우를 처리

→ consumer thread가 queue에서 data를 가져올 때 queue가 비어 있는 경우를 처리

### 1. busy wait

> 자원을 얻기 위해 기다리는 것이 아닌 권한을 얻기 위해 기다리는 것
>

#include #include #include #include

std::mutex m;

std::queue shared_queue; const int N = 10000; void produce() { for(int i=0;i<N;i++) { m.lock(); std::cout<<"i produce"<<i<<std::endl; shared_queue.push(i); m.unlock();

//1sec artificial delay std::this_thread::sleep_for(std::chrono::milliseconds(1000)); } } void busy_consume() { for(int i=0;i<N;i++) { while(shared_queue.empty()) { m.unlock(); m.lock(); } std::cout<<"i read " <<shared_queue.front()<<std::endl; shared_queue.pop(); } } int main() { std::thread t1(produce); std::thread t2(busy_consume); t1.join(); t2.join(); return 0; }

- consumer thread가 계속해서 queue가 비어있는지 확인
- 그러나 queue가 비어있는 경우에도 thread가 계속해서 CPU를 점유하며 queue가 채워질 때까지 대기함

    → CPU 자원 낭비, 비효율적


### 2. busy wait + sleep

- Sleeping

> 권한을 얻기 위해 걸리는 시간을 wait
queue에 실행중인 Thread 정보를 담고 다른 Thread에게 CPU를 양보하는 것
>

#include #include #include #include

std::mutex m;

std::queue shared_queue; const int N = 10000; void produce() { for(int i=0;i<N;i++) { m.lock(); std::cout<<"i produce"<<i<<std::endl; shared_queue.push(i); m.unlock();

//1sec artificial delay std::this_thread::sleep_for(std::chrono::milliseconds(1000)); } } void sleep_consume() { for(int i=0;i<N;i++) { while(shared_queue.empty()) { m.unlock(); std::this_thread::sleep_for(std::chrono::milliseconds(100)); m.lock(); } std::cout<<"i read " <<shared_queue.front()<<std::endl; shared_queue.pop(); } } int main() { std::thread t1(produce); std::thread t2(busy_consume); t1.join(); t2.join(); return 0; }

- consumer thread가 queue가 비어 있는 경우 일정 시간동안 sleep
- 그 후에 다시 queue가 비어 있는지 확인

    → consumer thread가 더 많은 CPU자원을 점유하지 않음

    → queue가 채워질 때까지 기다리는데 도움이 됨

    → but 여전히 일정 시간마다 불필요한 check가 필요 ,,


### 3. condition variables

#include #include #include #include #include

std::mutex m;

std::queue shared_queue; const int N = 10000; std::condition_variable cond; void produce() { for(int i=0;i<N;i++) { std::unique_lockstd::mutex lock(m); std::cout<<"i produce"<<i<<std::endl; shared_queue.push(i); cond.notify_one(); lock.unlock(); std::this_thread::sleep_for(std::chrono::milliseconds(1000)); } } void consume() { for(int i=0;i<N;i++) { std::unique_lockstd::mutex lock(m); cond.wait(lock,[]{return !shared_queue.empty();}); std::cout<<"i read"<<shared_queue.front()<<std::endl; shared_queue.pop(); lock.unlock(); } } int main() { std::thread t1(produce); std::thread t2(consume); t1.join(); t2.join(); return 0; }

- queue가 비어 있는 경우 소비자 thread 대기
- condition variables
    - thread가 특정 조건을 만족할 때까지 대기하도록 함
    - 다른 Thread가 조건을 만족시키면 대기 중인 thread 깨움
    - consumer thread : queue가 비어 있는 동안 조건 변수를 기다림
    - producer thread : 데이터를 queue에 추가한 후 condition variable을 통해 consumer thread를 깨움
- `cond.wait(unique_lock, predicate function)`

    : condition variable을 기다리는 데에 사용

    - `unique_lock`
        - `lock_guard`와 비슷한 용도
        - 사용자가 수동으로 잠금 및 잠금 해제 가능 (`lock()`, `unlock()`)
        - 생성 시 뮤텍스를 잠그거나 해제 가능
    - `predicate function`
        - 조건이 만족되는지 확인하는 함수
        - 조건 함수가 True : thread는 대기 중인 상태를 벗어나 다음 코드를 실행
        - 조건 함수가 False : thread는 대기 상태에 남음, 나중에 조건이 충족될 때까지 기다림
- `notify_one()`
    - 대기 중인 thread 중 하나를 깨우는 역할
    - 조건 변수를 기다리는 thread 중 하나가 신호를 받아 실행 재개
- `notify_all()`
    - 모든 대기 중인 thread 깨움
    - 여러 thread가 동시에 조건 변수를 기다리고 있을 때 사용

## ෆ Atomics

> 동시에 여러 thread에서 공유되는 변수의 안전한 업데이트를 가능하게 하는 기술
> 

→ thread간 동기화가 필요할 때 사용

#include #include #include #include #include <assert.h>

std::atomic output

void worker(int* input, int start, int size) { for(int i=0;i<size;i++) { if(input[start+i]==0) { output+=1; } } }

- All-Or-Nothing : 연산이 완전히 수행되거나, 전혀 수행되지 않아야 함
- 원자적 연산을 제공 → 여러 thread에서 동시에 접근해도 데이터의 일관성을 보장한다는 뜻
- 데이터의 일관성을 보장하기 위한 동기화 과정 때문에 일반적인 연산에 비해 비용이 더 들 수 있다..
- 또한 여러 연산이 함께 동작해야 하는 복잡한 동기화 작업에는 lock과 같은 더 고수준의 동기화 도구가 필요 ..

## ෆ Barrier
![](https://velog.velcdn.com/images/ii_seo/post/30cf9f94-f338-4da4-8924-740a0e1f030b/image.png)
- 전역 동기화(global synchronization)의 한 형태
- 모든 thread가 특정 지점에서 멈추고, 다른 모든 thread가 그 지점에 도달할 때까지 대기하는 동작

    → 여러 thread간의 작업을 동기화할 때 유용

#include #include <boost/thread/barrier.hpp> #include #include

void worker(int* input, int start, int size, int* output, boost::barrier& bar) { for(int i=0;i<size;i++) { if(input[start+i]==0) { (*output)++; } if(i%1000==0) { bar.wait(); std::cout<<"thread starting at "<<start<<" passed bar at i="<<i<<std::endl; } } }

int main(int argc, char* argv[]) { const int N = atoi(argv[1]); const int NT = atoi(argv[2]); boost::barrier bar(NT); for(int t=0;t<NT;t++) { threads.push_back(std::thread(worker, array, start, size, &count, std::ref(bar))); } … }

# ❦ Thread-safety

> 여러 thread가 동시에 코드를 실행할 때 공유된 데이터를 안전하게 조작하는 능력
→ 여러 thread에서 동시에 실행되어도 예상대로 작동, 데이터 무결성을 보존
> 
- 가장 쉽게 thread-safe한 코드를 만드는 법 → add a lock to it

## ෆ Thread-safe queue

template class thread_safe_queue { std::queue _queue; std::mutex mtx; public:

thread_safe_queue()
{}

void push(T value)
{
    std::lock_guard<std::mutex> lock(mtx);
    _queue.push(value);
}

T pop()
{
    std::lock_guard<std::mutex> lock(mtx);
    T res = _queue.front();
    _queue.pop();
    return res;
}

};

→ safe, but inefficient

- queue에 대한 모든 조작(push,pop ..)이 하나의 mutex로 보호

    → queue에 대한 동시 접근을 제어

    → 데이터의 일관성 보장

    → but, queue에 대한 조작이 가능한 thread 수를 제한

    - 뮤텍스는 크리티컬 섹션(critical section)을 보호하기 위해 사용되며, 크리티컬 섹션을 보호하는 동안 다른 스레드는 대기

        → 한 번에 하나의 thread만 queue에 접근

        → 병목현상
## ෆ Linked-list queue

template class linked_list_queue { class node { public: node(T init_value):value(init_value) {} T value; node* next; };

node* head;
node* tail;
public:

linked_list_queue()
{
    head = tail = new node(0); //dummy node
}
void push(T value)
{
    node* tmp = new node(value);
    tmp->value = value;
    tmp->next = nullptr;
    tail->next = tmp;
    tail = tmp;
}

bool pop(T& value)
{
    node* old_head = head;
    node* new_head = old_head->next;
    if(new_head == nullptr) {
        return false;
}
value = new_head->value;
head = new_head;
delete old_head;

return true;
}

};

→ 모든 조작에 대해 mutex를 사용할 필요가 없음

1. `push()`

    tail을 사용하여 새 node를 queue에 추가

    → tail을 변경하는 부분만 lock

2. `pop()`

    head를 사용하여 첫 번째 node를 queue에서 제거

    → head를 변경하는 부분만 lock


⇒ 각각 tail과 head만 잠그면 ok

서로 다른 thread가 동시에 queue에 접근 가능, 성능도 향상
## ෆ Thread-safe Linked-list queue

template class safe_llq { class node { public: node(T init_value):value(init_value) {} T value; node* next; }; node* head; node* tail; std::mutex head_mtx; std::mutex tail_mtx; public:

safe_llq()
{
    head = tail = new node(0); //dummy node
}

void push(T value)
{
    node* tmp = new node(value);
    tmp->value = value;
    tmp->next = nullptr;
    std::lock_guard<std::mutex> tail_lock(tail_mtx);
    tail->next = tmp;
    tail = tmp;
}

bool pop(T& value)
{
    std::lock_guard<std::mutex> head_lock(head_mtx);
    node* old_head = head;
    node* new_head = old_head->next;
    if(new_head == nullptr) {
        return false;
    }
    value = new_head->value;
    head = new_head;
    delete old_head;

    return true;
}

};

```

• 두 가지 mutex를 사용하여 두 가지 종류의 임계 영역 보호

1. tail_mtx

   push() 함수에서 새로운 값을 queue에 추가할 때 tail update

   → tail을 잠그고 새로운 노드 추가

2. head_mtx

   pop() 함수에서 첫 번째 값을 queue에서 제거할 때 head update

   → head를 잠그고 첫 번째 노드 제거

• push(), pop() 함수가 동시에 발생 가능
• 각각의 함수는 서로 다른 mutex를 사용하여 자신의 임계 영역 보호

⇒ fine-grained locking !

1. Lock entire list

• queue의 모든 작업 (push / pop)이 하나의 mutex로 보호
• queue를 변경할 때마다 전체 list가 잠김 → 간단하고 구현이 쉬우나, 동시성이 낮아지고 병목 현상이 발생

2. Node-by-Node lock

• 각 node에 대해 개별적인 mutex를 사용하여 각 node를 개별적으로 보호
• 더 많은 동시성을 제공하지만, error 발생 가능

3. Hand-over-Hand locking

• 노드 사이에서 잠금을 전달
• 첫 번째 node를 잠근 다음, 두 번째 node를 잠금 …
• 구현이 복잡하고 잠금의 overhead 증가

ෆ Thread-safe Hash Table

• 아마도 가장 빠른 data structure ,,
  • O(1) : write, read

1. global lock

• hash table 전체에 대해 하나의 전역 락(mutex)를 사용
• 구현이 간단하고, 이해하기 쉽지만, 동시성이 낮고 병목 현상이 발생할 수 있음

2. fine-grained lock

   • hash table의 각 버킷에 대해 개별적인 락(mutex) 사용
   • 각 버킷에 대한 작업은 해당 버킷에 대한 락을 획득
     • 서로 다른 버킷에 대한 작업은 서로에게 영향을 주지 않아 더 많은 동시성 달성 가능
   • 락 경합이 발생할 수 있음
     • 두 thread가 동일한 버킷을 수정하려고 시도할 때 발생하는 경합 ,,
   • 버킷의 개수가 많아지면 overhead 발생
     • O(B) : B는 버킷의 수

3. lock striping

   • hash table을 여러 개의 더 작은 섹션 또는 스트라이프로 분할
   • 각 섹션에 대해 개별적인 락 사용
   • 락 경합을 줄이고 동시성을 높일 수 있음
     • but 스트라이핑을 어떻게 구현하느냐에 따라 락 경합이 발생 가능

ෆ Other features to look at

• std::this_thread::get_id()
  • 현재 thread의 식별자를 나타내는 std::thread::id 객체를 반환
  • 디버깅이나 로깅과 같은 목적으로 사용, 실행 중에 개별 thread를 식별하는데 유용
• std::move()
  • lvalue를 rvalue로 변환
  • 자원의 소유권을 전달하는 등의 상황에서 자주 사용
    • 데이터 구조의 소유권을 한 thread에서 다른 thread로 전달 ,,
  • std::thread와 함께 사용되면 객체의 소유권을 thread에게 전달 가능
• std::thread::hardware_concurrency()
  • 시스템이 지원하는 hardware thread의 수를 반환
  • 동시에 실행 가능한 thread의 수에 대한 힌트를 제공
    • 성능을 저하시키지 않고 동시성 thread를 실행할 수 있는 최적의 thread 수를 결정
  • 최적의 thread 수를 결정하는데 자주 사용
• std::async, std::promise, std::future
  • std::async : 비동기 작업 실행을 위한 고수준 interface, 계산 결가를 나타내는 std::future 객체 반환
  • std::promise : 값이나 예외를 비동기적으로 저장하기 위해 사용, 이후 std::future 객체를 통해 비동기적으로 사용 가능
  • std::future : 아직 사용 가능하지 않은 값, 나중에 사용 가능하게 됨
• most vexing parse problem
  • 괄호를 사용하여 nop_object의 인스턴스를 생성
  • 이를 std::thread 생성자에 전달하려고 시도
    • 하지만, 이 코드는 가장 먼저 "가장 광범위한 해석" 규칙(most vexing parse)에 의해 문제가 발생
    • 컴파일러는 이것을 함수 선언으로 해석할 수 있으며, 결과적으로 t3를 nop_object 타입의 파라미터를 받고 반환 타입이 std::thread인 함수 선언으로 오해

⇒ 해결 방법: use {} instead of ()

Parallel programming에서 programming model은 프로그래머에게 communication abstraction을 제공

→ 프로그래머가 컴퓨터 시스템의 병렬성을 이해하고 활용할 수 있게 도와줌

• Shared Memory Model
  • 모든 process/thread가 동일한 주소 공간을 공유
    • 데이터를 공유하는 것이 가능
    • process/thread간의 communication은 주로 공유된 변수 또는 데이터 구조를 통해 이루어짐
  • 대부분의 multi processor system/ multi-core processor에서 사용
    • ex. OpenMP : Shared Memory Model을 기반으로 구현되어 있음
  • 프로세스 또는 스레드 간의 데이터 공유를 편리하게 처리
  • 데이터의 일관성과 동기화에 대한 관리가 필요
• Message Passing Model
  • process간 communication을 위해 명시적으로 message를 주고 받는 방식
    • 각 process는 자체적으로 독립적인 주소 공간을 가짐
  • 분산 시스템에서 주로 사용
    • 대규모 cluster 또는 분산 컴퓨팅 환경에서 process간 통신이 필요한 경우 유용
    • ex. MPI (메시지 패싱 라이브러리)
  • 명시적인 통신을 통해 분산 환경에서의 효과적인 상호 작용
  • 통신 비용과 병목 현상에 대한 관리가 필요

ෆ Shared memory model

ಌ Memory

address를 통해서 접근(읽기 및 쓰기)할 수 있는 byte의 집합

데이터와 명령어를 저장하고 접근하는 장치

• 0x8 에 32가 저장되어 있음
• 0x10에 128이 저장되어 있음
• 주로 byte 단위로 주소 지정이 이루어짐

⇒ CPU와 Memory의 구조는?

• Von Neumann 아키텍쳐

  1. Single data bus

     CPU와 memory간에 단일 데이터 버스가 존재

     → 이 bus를 통해 CPU는 memory로부터 명령어와 데이터를 읽거나 쓸 수 있음

  2. Single Storage

     프로그램의 명령어와 데이터는 동일한 메모리에 저장

     프로그램의 구조를 단순화하고 프로그램의 유연성을 높임

  3. Instruction and Data Separation

     프로그램 명령어와 데이터는 동일한 메모리에 저장되나, CPU는 명령어와 데이터를 구분하여 처리

     CPU는 PC를 사용하여 메모리에서 다음에 실행할 명령어의 위치를 추적

  4. Sequential Instruction Execution

     프로그램은 순차적으로 실행

     CPU는 메모리에서 한 번에 하나의 명령어를 가져와 실행

     → 프로그래밍의 단순성을 유지하고 복잡성을 줄임

• 그럼 multi-core CPU는 ??

  ⇒ 하지만 실제로는 ,, : Memory hierarchy

  상위 계층 : 일반적으로 빠른 접근 속도 제공 하위 계층 : 더 큰 용량을 제공

1. Register : cache memory에서 검색된 단어를 저장
2. Cache
   1. L1 : L2 cache에서 검색된 cache line을 저장
   2. L2 : L3 cache에서 검색된 cache line을 저장
   3. L3 : memory에서 검색된 cache line을 저장
3. Main memory : local disk에서 검색된 disk block을 저장
4. Secondary Storage : 원격 network server의 disk에서 검색된 file을 저장

ಌ Shared address space

• 각 thread는 동일한 process 내에서 실행

• memory에 접근 시 동일한 address space를 공유

  → 여러 thread가 동일한 address space를 공유하면 하나의 thread가 해당 address에 쓴 내용을 다른 thread가 볼 수 있음

• 한 thread가 address space에 값을 쓰면, 이 값이 다른 모든 thread에게도 즉시 반영

• mutual exclusion (상호 배제)를 필요로 함

  • 여러 thread가 동시에 memory에 access 하는 것을 방지

    → data의 일관성과 무결성 보장

• Hardware적 지원이 필요

  • core간의 interconnect
  • 시스템이 확장되면서 발생 가능한 확장성 문제
  • 캐시 일관성
  • …

1. “Dance-hall” organization 여러 스레드가 자유롭게 데이터를 교환하고 공유

• 메모리 주소 공간의 각 부분이 다수의 스레드에 의해 공유
• 스레드 간의 데이터 공유와 통신이 쉽게 이루어질 수 있도록 설계

2. Interconnect examples

• 스레드 간 통신을 위한 인터커넥트(Interconnect) 구조
• 인터커넥트는 다수의 프로세서 또는 코어 간의 통신을 지원하기 위한 통신 경로 및 프로토콜을 제공
• 인터커넥트는 스레드 간의 데이터 전송과 동기화를 지원하며, 고성능 및 효율적인 데이터 교환을 가능
• ex 1 : intel core i7 (Kaby Lake)
• ex 2 : sun Niagara 2

ಌ Shared memory UMA (Uniform Memory Access)

• 균일 기억 장치 접근
• 모든 processor들이 상호간에 연결되어 하나의 메모리를 공유하는 기술
• processor들은 memory의 어느 영역 이던지 접근이 가능하며, 모든 processor가 걸리는 시간이 동일
• 구조가 간단하고, 프로그래밍 하기는 쉬우나, 메모리에 한번에 하나씩의 연결만 가능하여, 커지면 커질수록 효율성이 떨어짐

ಌ Shared memory NUMA (Non-Uniform Memory Access)

• 메모리에 접근하는 시간이 processor와 memory의 상대적인 위치에 따라 달라짐

  • local memory access (로컬 메모리에 접근) vs remote memory access (원격 메모리 접근)

    → 서로 다른 지연 시간을 가짐

    • local memory access

      : 각각의 CPU마다 memory를 가지고 있는 구조에서 memory에 접근하는 경우

    • remote memory access

      : CPU와 memory를 합쳐 node를 구성 → 자신의 memory가 아닌 다른 node의 memory 접근하는 경우

• 물리적인 interconnects로 인해 발생하는 지연(latency)및 대역폭(bandwidth) 불균형

  • 성능 저하의 원인

  • 동일한 주소 공간 내에서 발생

    ⇒ first touch 정책

  • memory가 처음으로 access 될 때 해당 memory를 local memory에 할당하는 정책

  • 각 processor가 가능한 한 local memory에 access하여 지연 시간과 대역폭 불균형을 최소화

    ⇒ 메모리 할당을 수동으로 제어 : munactl 유틸리티

  • -membind: 메모리를 할당할 노드를 정의합니다.

  • -cpunodebind: 사용할 NUMA 노드를 지정합니다.

  • -physcpubind: 사용할 CPU를 선언합니다.

  • -interleave: 메모리 할당에 대한 interleaving 정책을 사용합니다.

  • → 메모리 및 CPU 할당을 세밀하게 제어하여 성능을 최적화

• ex. modern dual socket machinecore 6에서 data x에 접근해야 한다면 ,, sol 1 : data x를 Memory 1에 위치하게 함 sol 2 : core 6에서 하는 일을 core 1이 하게끔 함

• thread migration : processor가 thread를 중지하고 현재 상태 저장 → 다른 core에서 thread를 다시 시작 → 이전 상태 복원

ෆ ILP

보통 instruction은 sequential 하게 나열 → 순서대로 하나씩 실행 시 overhead ↑

→ 두 개 이상의 instruction을 ‘동시에’ 실행하려면 ?

1. 서로 independent한 instruction들을 찾아서 parallel(병렬)하게 실행시킬 수 있다면 overhead ↓ 가능
   • Superscalar
     • 1 cycle 동안에 서로 다른 independent한 2개의 instruction을 동시에 수행
2. 완전히 중첩시키지는 않더라도 pipeline과 같이 stage를 약간씩 중첩시켜서 실행 가능
   • Superpipeline
     • 한 클럭을 2개로 나누고, 나누어진 클럭에서 각각 서로 다른 연산을 수행
3. 동시에 수행

⇒ ILP 방식

_: 서로 독립적인 명령어들을 최대한 찾고, 이들을 오버랩해서 실행 _

ෆ ILP 예시

$$ a = xx + yy + z*z $$

• processor : a machine that executes the assembly instructions in sequence

                 → 컴퓨터 운영을 위해 기본적인 명령어들을 처리하고 반응하기 위한 논리회로

• PC (Program Counter) : references the instruction to be executed

→ 해당 예시에서 모든 instruction을 실행하려면 5 cycle이 걸림

• 하지만 위와 같이 여러 개의 execution unit이 있다면 여러 개의 instruction을 한 cycle에 수행 가능
• 그럼에도 1 cycle에 모든 instruction을 수행할 수는 없음
  • (4) instruction의 경우, (1)과 (2)의 수행결과가 있어야 수행할 수 있으므로 ..
  • ⇒ Data Dependency : 한 작업이나 명령이 다른 작업의 결과에 의존할 때 발생하는 상황
• 3 cycle에 모든 instruction 수행 완료
  • Q: execution unit은 몇 개가 필요한가 ..
    • 기본적으로 3개 : (1), (2), (3) 의 연산을 한 번에 수행
    • 2개도 가능 : (3), (4) 의 연산은 독립적이기 때문에 한 번에 수행해도 ok !

ෆ Scalar processor VS Superscalar processor

• Scalar processor : 한 번에 하나의 데이터를 처리하는 CPU (1ALU)

  • 한 번에 하나의 instruction만 처리 가능
  • 각 instruction는 순차적으로 처리 (다음 instruction은 현재의 instruction의 처리가 완료된 후 실행)
  • 단순하고 예측하기 쉬운 성능 제공
  • 처리 능력이 제한적

• Superscalar processor

  • 한 번에 여러 개의 instruction 처리 가능
  • 여러 ALU를 통해 동시에 다양한 instruction 실행
  • instruction을 parallel(병렬적)으로 처리

⇒ 주요 차이점

• 처리 능력 : Superscalar processor는 Scalar processor보다 더 많은 instruction을 동시에 처리 가능 → 처리 능력 ↑
• 구조 복잡성 : Superscalar processor는 여러 ALU를 동시에 관리하고 조율해야 하므로 Scalar processor보다 더 복잡한 구조
• 성능 측면에서의 효율성 : Superscalar processor는 parallel 처리를 통해 더 빠른 성능을 제공

                                  but, 이로 인해 설계와 구현이 더 어려워짐, 비용도 ↑

ෆ Superscalar processor

컴퓨터 성능 → CPU의 기본 처리 속도 = cycle 당 instruction을 한 번 처리하는 것 (IPC = 1)

⇒ 한 cycle에 instruction이 하나 이상 처리되면 CPU는 그만큼 한 번에 여러 개의 연산 처리가 가능 ~ 체감 속도 ↑

ex. “ $a = (x+x)*y$ “

해당 연산 결과를 뽑으라는 instruction을 줬다고 가정했을 때

• IPC = 1인 환경 → 1 cycle이 지나면 곱셈의 결과를 얻을 수 있음
• 하지만 해당 식은 덧셈의 결과를 바탕으로 곱셈의 결과를 얻어야 함 → 1 cycle 이상 걸림
  • 덧셈의 instruction을 수행하는 데에 1 cycle이 소비되기 때문
• 컴퓨터 성능 향상 불가 ..

⇒ instruction 간의 dependence 때문

이를 극복하기 위한 방법 → Superscalar processor

instruction이 처리되는 path를 여러 개 만들고 각각의 instruction을 해당 path를 통해서 처리하게 하면 됨

• 지금까지 생각한 MIPS 구조의 pipeline을 그대로 따라가면서 그것과 비슷한 line을 하나 더 생성

  • 하나는 data만 처리할 수 있게

  • 하나는 instruction만 처리할 수 있게

    ⇒ instruction을 읽어오면서 data pipeline을 통해서 결과를 뽑을 수 있게끔

• 이 모든 작업을 parallel하게 처리

  • IPC = 1인 형태를 넘어서서 성능향상 구현 가능

independent한 instruction을 어떻게 찾냐 → dynamic scheduling을 통해서 ..

ෆ Superscalar processor가 그럼 limit 없이 성능이 향상되는가

• Superscalar processor의 장점

  1. 프로그램 호환성

     : 기존의 프로그램 코드를 변경하지 않고도 성능 향상 가능

     processor가 자동으로 instruction 간의 independency 판별, parellel로 실행 가능한 instruction 선정

  2. 효율성

     : 복수의 ALU를 통해 instruction을 동시에 처리 → 처리 속도가 ↑

     (특히 복잡한 계산이나 대량의 data 처리가 필요한 application에서 유용)

### ⇒ 한계 ?
![](https://velog.velcdn.com/images/ii_seo/post/0d918521-1366-4afe-bedd-2851cae84048/image.png)
  1. 자원의 한계

      : 동시에 실행할 수 있는 instruction의 수는 결국 processor 내의 ALU의 수와 관련 자원에 의해 제한됨

  2. instruction dependency

      : 일부 instruction은 다른 instruction의 result에 의존 → 성능의 병목 현상

  3. 메모리 대역폭

      : processor가 더 많은 processor를 동시에 처리하려면, memory로부터 data를 더 빠르게 가져와야 함

ෆ Processor scaling trend

• 무어의 법칙 : 집적회로 내의 transistor 수가 약 18개월에서 24개월마다 2배로 증가한다는 관찰을 기반으로 함

                 → 초기 몇십년 동안 processor 성능 향상의 주요 동력이었으나, 물리적 한계와 제조 비용의 증가로 인해 지속 가능한지 …

• clock speed : processor가 초 당 수행할 수 있는 cycle 수

                    이 clock speed를 늘리는 것에 집중했으나, 높은 clock speed는 열 문제와 전력 소비 증가를 초래

• power : 효율적인 에너지 설계가 중요 .. (배터리 수명 .. 등) → 전력 소비를 줄이면서도 성능을 최적화 하는 방향으로 ..

⇒ multi-core , multi-threading

: clock speed 향상의 한계에 직면 (발열 문제)

→ 여러 개의 처리 core를 하나의 칩에 집적하는 multi-core processor !

• 단일 processor 내에서 parellel 처리가 가능해져 성능이 향상
• hyper-threading 같은 기술을 통해 core 당 여러 thread를 동시에 처리할 수 있음

❦ Multi-core processors (MIMD, Multiple Instruction Multiple Data)

ෆ Multi-core processor

• 여러 개의 작업을 보다 효율적으로 처리하기 위해 2개 이상의 느린 processor가 붙어있는 ‘집적회로’
• power가 증가되고 열 손실이 감소한 2개의 processing 엔진 > processing core가 하나일 자원이 부족한 칩

e.g. 80% clock frequency → 2 cores : $$2*0.8 = 1.6 > 1$$

다시 돌아와서 .. multi-core processor에서 다음 코드를 돌린다고 가정하면,

오히려 드는 시간이 늘어나게 됨 ..

→ multi-thread와 같은 기법을 사용하지 않으면, core 한개가 노는 상태 ..

~ 결국 위 코드의 실행 시간은 $1 * 0.8 = 0.8 < 1$

⇒ thread를 이용해야 ..!

ෆ Thread

: process 내에서 process의 자원을 이용하여 실행되는 여러 흐름의 단위

: process 내에서 실제로 작업을 수행하는 주체

→ 운영체제의 스케줄러에 의해 독립적으로 관리될 수 있는 프로그래밍된 명령어의 가장 작은 시퀀스

1. subroutine을 호출하는 경우
   • subroutine : 프로그램 내에서 다른 부분에서 실행되는 코드 블록
   • 현재 실행 중인 작업을 중단하고 해당 서브루틴으로 제어를 이동
   • 서브루틴을 실행한 후 다시 호출한 지점으로 돌아와 작업을 계속할 수 있음
   • 일반적인 함수 호출 방식과 유사한 방식
2. 새로운 thread를 시작하는 경우
   • 새로운 스레드가 현재 스레드와 병렬로 실행 → 여러 작업을 동시에 처리 가능
   • 새로운 스레드를 시작하는 작업은 일반적으로 다른 함수나 메소드 내에서 수행 → 새로운 스레드의 실행을 시작하고, 해당 스레드가 실행될 함수 또는 코드 블록을 지정

ෆ Process VS Thread

• process

  작업 중인 프로그램

  • process가 memory에 올라갈 때 OS로부터 시스템 자원을 할당받음
    • process마다 각각 독립된 memory 영역
      • 기본적으로 process끼리 다른 process의 memory에 직접 접근 불가
    • Code/Data/Stack/Heap의 형식

  → 한 프로세스를 실행하다가 오류가 발생해서 프로세스가 강제로 종료된다면, 다른 프로세스에게 어떤 영향이 있을까? : 공유하고 있는 파일을 손상시키는 경우가 아니라면 아무런 영향을 주지 않는다.

• thread

  프로세스의 코드에 정의된 절차에 따라 실행되는 특정한 수행 경로

  

  • 메모리를 서로 공유할 수 있음

    • Code/Data/Heap 형식으로 할당된 메모리 영역을 공유

      • heap 메모리는 공유하기 때문에 서로 다른 스레드에서 가져와 읽고 쓸 수 있음

        → 어떤 스레드 하나에서 오류가 발생한다면 같은 프로세스 내의 다른 스레드 모두가 강제로 종료

    • address space

    • …

  • 공유되지 않는 resource

    • Stack 형식으로 할당된 메모리 영역은 따로 할당
      • stack: 함수 호출 시 전달되는 인자, 되돌아갈 주소값, 함수 내에서 선언하는 변수 등을 저장하는 메모리 공간
      • 독립적인 스택을 가졌다 → 독립적인 함수 호출이 가능하다 → 독립적인 실행 흐름이 추가된다
      • 독립적인 stack을 가짐으로써 thread는 독립적인 실행 흐름을 가질 수 있게 됨
    • PC
      • 각 스레드는 자체 프로그램 카운터를 가지고 다음에 실행할 명령어의 위치를 추적
      • instruction이 같다면 PC 공유도 가능 .. 하긴 함
    • register
      • 각 스레드는 자체 레지스터를 가지고 데이터 및 연산을 처리
      • instruction이 같아도 register는 공유 불가 → thread마다 다른 data를 다루기 때문 ,,

ෆ Example code

#include <iostream>
const int N = 100;
int main()
{
    int a[N], b[N], k[N], c[N];
    for(int i=0;i<N;i++) {
        a[i] = i;
        b[i] = 1000*i;
        k[i] = 10;
        c[i] = 0;
    }
    for(int i=0;i<N;i++) {
        c[i] = k[i]*a[i];
        c[i] += k[i]*b[i];
    }
    return 0;
}

multi-thread program

#include <iostream>
#include <thread>
#include <vector>

// 정수 포인터를 선언하여 동적으로 할당된 배열을 가리키는 역할
int *a, *b, *k, *c;

// 벡터 연산을 수행하는 함수
// mac : multiply-accumulate, 주어진 두 배열을 곱하고 결과를 누적하는 역할
// tid : thread의 index, num_threads : 전체 thread의 수
void mac(int tid, int num_threads)
{
    // 전체 vector의 크기를 전체 thread 수로 나누어 각 thread가 처리할 부분을 결정
    for(int i=0;i<N/num_threads;i++)
    {
        // idx : 현재 thread가 처리할 index
        int idx = tid*(N/num_threads) + i;
        c[idx] = k[idx] * a[idx];
        c[idx] += k[idx] * b[idx];
    }
    return;
    }
int main(int argc, char* argv[])
{
...
    // thread를 저장할 vector를 선언
    std::vector<std::thread> threads;
    // 전체 thread 수만큼 반복하면서 thread를 생성
    for(int t=0;t<NT;t++) {
        // 새로운 스레드를 생성하고 벡터 threads에 추가
        // 각 스레드는 mac 함수를 호출하며, 스레드의 인덱스(t)와 전체 스레드 수(NT)를 전달
        threads.push_back(std::thread(mac, t, NT));
    }
    // 모든 스레드가 종료될 때까지 대기
    for(auto& thread: threads) {
        thread.join();
    }
    return 0;
}

Data-Parallel expressions

병렬화를 위한 loop나 반복문을 쉽게 target으로 지정할 수 있는 개념

→ 프로그래머가 루프의 반복이 독립적이라고 선언하고, 해당 루프를 병렬로 실행할 수 있도록 지시

#include <iostream>

//const int N = 1000000;
#defiine N 1000000000LL
int main()
{
...

#pragma omp parallel for
    for(long long int i=0;i<N;i++) {
        c[i] = k[i]*a[i];
        c[i] += k[i]*b[i];
    }

    return 0;
}

• 각 반복이 다른 반복과 독립적으로 실행될 수 있는 경우 : 독립성을 활용하여 병렬 처리를 수행

• 이러한 독립적인 반복을 탐지하고, 해당 반복을 여러 스레드로 병렬화하여 동시에 실행할 수 있는 코드를 생성

• OpenMP : data-parallel expression을 사용하여 loop를 병렬화

  • 프로그래머는 OpenMP의 지시문을 사용하여 루프가 독립적임을 선언

  • OpenMP는 해당 지시문을 해석하여 루프를 병렬로 실행하는 코드를 생성

    → 프로그래머는 직접 thread를 관리하지 않고도 병렬 처리를 수행할 수 있음

❦ Vector processing (SIMD, Single Instruction Multiple Data)

ෆ Multicore processor의 Fetch/Decode 부분이 여러 개여야 하는가 ,,

이전의 예시에서

• 위의 코드가 정확히 같은 code, data만 다른 data를 다루는 것

  → fetch/decode가 꼭 2개의 unit일 필요가 없음 : Vector processing !

• execution context는 2개의 unit 이어야 함

  • thread별로 각각 다른 memory가 필요하기 때문 ..

ෆ Vector processing

• 하나의 instruction을 통해 여러 개의 data 요소를 동시에 처리하는 기술

하나의 명령어가 여러 개의 데이터 요소에 대해 동시에 작업을 수행할 수 있도록

→ 하나의 명령어가 다수의 연산장치(ALU)에서 동시에 실행되도록 : 병렬성 ↑, 연산량 효율적으로 처리

#include <immintrin.h>

#pragma omp parallel for
for(long long int i=0;i<N;i+=8) {

        // __m256i : 256비트(32바이트)크기의 정수형 벡터를 나타내는 데이터 타입
        // _mm256_load_si256 : AVX register에 data load
        __m256i A = _mm256_load_si256((__m256i*)(&a[i]));
        __m256i B = _mm256_load_si256((__m256i*)(&b[i]));
        __m256i K = _mm256_load_si256((__m256i*)(&k[i]));
        // _mm256_mullo_epi32 : 두 개의 256비트 정수형 벡터의 각 요소를 곱한 결과를 반환
        __m256i C1 = _mm256_mullo_epi32(A,K);
        __m256i C2 = _mm256_mullo_epi32(B,K);
        // _mm256_add_epi32 : 두 개의 256비트 정수형 벡터의 각 요소를 더한 결과를 반환
        __m256i C = _mm256_add_epi32(C1,C2);

        // _mm256_store_si256 : AVX register의 데이터를 메모리에 저장
        _mm256_store_si256((__m256i*)(&c[i]), C);
    }
    return 0;
}

• SSE(Streaming SIMD Extensions)

  • 128비트 SIMD 명령어 세트 : 432비트, 264비트
  • 이전의 기본 x86 명령어 세트를 확장하여 추가된 기능

• AVX2(Advanced Vector Extentions 2)

  • 256비트 SIMD 명령어 세트 : 832비트, 464비트
  • SSE의 확장으로, 더 많은 데이터를 한 번에 처리할 수 있도록 하여 성능을 향상

• AVX-512

  • 512비트 SIMD 명령어 세트 : 1632, 864
  • AVX2의 확장으로, 더 많은 데이터를 한 번에 처리할 수 있어서 더 높은 성능을 제공

• 컴파일러는 코드를 분석하여 병렬성을 추론하고 필요한 경우에는 자동으로 SIMD 명령어를 생성

• 프로그래머가 직접 SIMD 명령어를 사용하고 싶은 경우→ ntrinsics(인트린식)라는 특별한 함수를 사용 (위의 코드 예시 참고)

  → 성능을 더욱 향상시킬 수 있음

Conditional execution ?

벡터 처리에서 조건부 실행을 구현하는 방법

⇒ Predication : Masking

• SIMD instruction을 사용하여 조건을 확인

• 해당 조건이 참(True)일때만 연산을 수행

  • 해당 연산에 대한 마스크 설정 → 해당 연산이 실행되도록 ,,

• 해당 조건이 거짓인 경우 연산을 건너뜀

  • 해당 연산에 대해 마스크를 설정하지 않음 → 해당 연산이 무시되도록 ,,

• 전체적인 연산량에 대한 이점을 제공 but! 일부 연산은 실제로는 실행되지 않으므로 이로 인해 하드웨어의 이용률이 낮아질 수 있음 ⇒ 마스킹을 사용하면 일부 ALU(산술 논리 장치)가 실제로는 유휴 상태일 수 있다 ,,

• GPU(Graphic Processing Unit)에서도 마스킹 기술이 널리 사용됨

❦ 정리

ෆ SISD : Single Instruction, Single Data

• Scalar processor

• Superscalar processor

  ෆ MIMD : Multiple Instruction, Multiple Data

  

• Multi-core processor

  ෆ SIMD : Single Instruction, Multiple Data

  

• Vector processor

  ෆ MISD : Multiple Instruction, Single Data

  일반적으로 병렬성을 향상시키는 데 사용되지 않음 → 특정 유형의 작업에 최적화된 특수 목적 프로세서에서 사용

• Systolic Array

  • 여러 개의 프로세서 코어가 특정한 데이터 스트림을 따라 일련의 연산을 수행하는 구조
  • 주로 행렬 곱셈과 같은 수치 연산에서 사용

• Google TPU

  • 대규모 딥러닝 모델의 추론 및 학습을 가속화하기 위해 설계

• 그리고 많은 다른 NPU(Neural Processing Unit)

  • NPU : 인공 신경망을 실행하고 가속화하기 위해 설계된 전용 하드웨어 장치