Multi-CPU Scheduling

1. Multiprocessor
2. Multiprocessor: Background
3. Multiprocessor: Algorithms

 

---

1.  Multiprocessor

Multicore Processors
CPU, Processor, Core, Thread
Concurrency vs Parallelism
Amdahl's Law

 

Multicore Processors

 

Single Core Processor의 성능 ( Clock Hz )의 증가가 Power Density 때문에 한계에 다다릅니다.

 

결국 number of threads per core 를 높이기로 결정하게 되었습니다.

 

CPU, Processor, Core, Thread

멀티프로세스 시스템에서 프로그램을 짜는 것은 매우 어렵습니다.

Concurrency vs Parallelism

Concurrency는 한개 이상의 Task가 Singlecore에서 돌아가는 방식이고, Parallelism은 여러 코어에서 task를 동시에 돌리는 것을 의미합니다.

 

Parallelism의 Type은 두개입니다

 

Data parallelism : 다른 Data에 대한 같은 연산을 여러 Core에 나누어 주는 것을 의미합니다.

Task parallelism : 같은 Data에 대한 다른 연산을 여러 Core에 나누어 주는 것을 의미합니다.

 

둘다 사용한다면 Hybrid parallelism 입니다.

Amdahl's Law

어쩔수 없이 Sequential 하게 돌아갈 수 밖에 없는 부분이 있기 때문에, Maximum speedup Limitation이 존재합니다.

 

---

2.  Multiprocessor Scheduling: Background

Multicore Scheduling
Cache Conherence
Synchronization
Cache Affinity

Multicore Scheduling

모든 프로그램이 병렬성이 잘 되어있다고 가정한다면, 우리는 Operating System에서 어떻게 Scheduling을 하는 것이 좋을까요?

-> 병렬성 높이는 문제에 대해서는 생각하지 않습니다.

 

Cache Conherence

-> Bus Snooping

Always update invalidate data

 

Operating System에서는 Bus Snooping에 대해 잘 알 필요는 없습니다.

Synchronization

공유된 자원에서 연산을 수행하다면 생각보다 많은 문제가 일어납니다.

아래 코드는 Double free falut가 일어날 수 있는 코드입니다.

typedef struct __Node_t {
    int value;
    struct __Node_t *next;
} Node_t;

int List_Pop() {
    Node_t *tmp = head; // remember old head ...
    int value = head->value; // ... and its value
    head = head->next; // advance head to next pointer
    free(tmp); // free old head
    return value; // return value at head
}

-> Lock

Lock을 걸어 해결할 수 있는 문제입니다.

Cache Affinity

Cache Miss 가 비효율적으로 발생하는 Issue 입니다.

---

3.  Multiprocessor Scheduling: Algorithms

Single Queue Multiprocessor Scheduling (SQMS)
Multi-Queue Scheduling (MQMS)
Work Stealing

Single Queue Multiprocessor Scheduling (SQMS)

공유되는 Global Queue에서 각 프로세서가 작업을 스케쥴 합니다.

 

Strength : 매우 간단한 알고리즘 입니다.

Weakness : 락이 되어야 하기때문에 scalability가 감소합니다, Cache affinity가 없습니다.

 

Solution : affinity를 위해서 최대한 같은 CPU에 같은 작업이 돌아가도록 해 줍니다.

Multi-Queue Shceduling (MQMS)

Strength : 싱글 큐에서의 scalability 문제가 해결됩니다.

Weakness : 로드 언밸런싱 문제가 발생합니다.

 

Solution : Migration (큐를 바꿔주기)

 

Work Stealing ( Migration )

High Overhead, Finding right Threshold problem