[sp] Thread-Level Parallelism

1. Exploiting parallel execution

(1) I/O delay를 다루기 위해 쓰레드를 사용

ex) 클라이언트 당 하나의 쓰레드는 다른 쓰레드를 지연시키는 것을 막기 위해 사용

 

(2) Multi-core (4) /Hyperthreaded (8) CPU가 제공하는 것

 - 쓰레드를 병렬로 수행시키면서 작업을 분산

 - 많은 독립적인 task가 있을 경우 자동적으로 발생

ex) 많은 어플리케이션을 실행하거나 많은 클라이언트를 서빙할 경우

- 하나의 큰 테스크를 빠르게 만들기 위한 코드를 작성

ex) 여러 개의 병렬 sub-task로 구성됨

 

2. Typical Multicore Processor

단일 칩 안에 여러 개의 core (cpu)가 들어있음

L1, L2 - private cache

L3 - shared cache (여러 cpu들이 동시에 접근)

 

 

3. Benchmark Machine

(1) /proc/cpuinfo로 부터 데이터를 얻음

(2) shark machines

§ Intel Xeon E5520 @ 2.27 GHz

§ Nehalem, ca. 2010

§ 8 Cores

§ Each can do 2x hyperthreading

 

4. ex1) Parallel Summation ; 0부터 n-1까지의 합 -> ((n-1)*n)/2

각 파티션마다 쓰레드들이 assign됨

 

(1) 1에서 n-1의 숫자들을 partition으로 쪼개서 t개의 partition을 만듦

(2) 각 파티션의 [n/t] 을 구함

(3) 각 t 쓰레드들은 하나의 range를 수행

(4) 단순함을 위해 n이 t의 배수라고 가정

 

(5) sol) psum-mutex ; 쓰레드들은 semaphore mutex에 의해 보호되는 글로벌 변수에 sum을 넣음

 

void *sum_mutex(void *vargp); /* Thread routine */

/* Global shared variables */
long gsum = 0; /* Global sum */
long nelems_per_thread; /* Number of elements to sum */
sem_t mutex; /* Mutex to protect global sum */

int main(int argc, char **argv)
{
    long i, nelems, log_nelems, nthreads, myid[MAXTHREADS];
    pthread_t tid[MAXTHREADS];
    
    /* Get input arguments */
    nthreads = atoi(argv[1]);
    log_nelems = atoi(argv[2]);
    nelems = (1L << log_nelems);
    nelems_per_thread = nelems / nthreads;
    sem_init(&mutex, 0, 1);
    
    /* Create peer threads and wait for them to finish */
    for (i = 0; i < nthreads; i++) {
        myid[i] = i;
        Pthread_create(&tid[i], NULL, sum_mutex, &myid[i]);
    }
    for (i = 0; i < nthreads; i++)
    	Pthread_join(tid[i], NULL);
        
    /* Check final answer */
    if (gsum != (nelems * (nelems-1))/2)
    	printf("Error: result=%ld\n", gsum);
        
    exit(0);
}

/* Thread routine for psum-mutex.c */ //각 쓰레드가 실행하는 방법
void *sum_mutex(void *vargp)
{
    long myid = *((long *)vargp); /* Extract thread ID */
    long start = myid * nelems_per_thread; /* Start element index */
    long end = start + nelems_per_thread; /* End element index */
    long i;
    
    for (i = start; i < end; i++) {
        P(&mutex);
        gsum += i;
        V(&mutex);
    }
    return NULL;
}

 

각 쓰레드들은 gsum을 공유하면서 update시킴

 

- psum-mutex Performance

8 core를 가진 shark machine, n = 2^31

- 싱글 쓰레드는 매우 느림

- 많은 core를 사용할 수록 느려짐

 

 

(6) sol) psum-array 

- peer thread i는 글로벌 array의 element인 psum[i]에 합을 넣어줌

- main은 쓰레드들이 완료하기를 기다리고, 그 후 psum의 element들을 모두 더해줌

- mutex 동기화를 할 필요 없음

 

/* Thread routine for psum-array.c */
void *sum_array(void *vargp)
{
    long myid = *((long *)vargp); /* Extract thread ID */
    long start = myid * nelems_per_thread; /* Start element index */
    long end = start + nelems_per_thread; /* End element index */
    long i;
    
    for (i = start; i < end; i++) {
    	psum[myid] += i;
    }
    
    return NULL;
}

 

- psum-array Performance

 

psum-mutex보다 더 빠름

 

(7) sol) psum-local

 - 로컬 변수에 각 쓰레드들의 합을 넣어줌으로써 메모리 참조를 감소함

 - 레지스터에서 중간값을 update

 

/* Thread routine for psum-local.c */
void *sum_local(void *vargp)
{
    long myid = *((long *)vargp); /* Extract thread ID */
    long start = myid * nelems_per_thread; /* Start element index */
    long end = start + nelems_per_thread; /* End element index */
    long i, sum = 0;
    
    for (i = start; i < end; i++) {
    	sum += i; // reg에 있음
    }
    psum[myid] = sum;
    return NULL;
}

 

- psum-local performance

psum-array보다 더 빨라짐

 

 

5. Characterizing Parallel program performance

(1) p 프로세서 코어, Tk는 k 코어를 사용한 수행 시간

(2) speed up: Sp = T1/Tp  ; p개의 cpu를 사용하여 성능이 얼마나 빨라지는지

 - Sp : relative speedup ; T1이 하나의 코어에서 실행되는 코드의 병렬 버전의 수행 시간일 경우

 - Sp : absolute speedup ; T1이 하나의 코어에서 실행되는 코드의 sequential한 버전의 수행시간일 경우

        : parallelism의 이점에 대한 측정을 훨씬 더 정확하게 측정

 

(3) Efficiency : Ep = Sp/p = T1/(p*Tp)

-> (0, 100]

-> 병렬화로 인한 오버헤드 측정

 

ex) 

T1 = 1, T4 = 0.25 -> S4 = 1/0.25 = 4

-> E4 = 4/4 = 1  ---> 100

 

T4 = 0.5 -> S4 = 1/0.5 = 2

-> E4 = 2/4 = 1/2 ---> 50

 

 

6. Performance of psum-local

- 성능은 더 좋아졌지만 효율은 더 떨어짐

- 예시는 쉽게 병렬화 가능

- 실제 코드는 병렬화하기 훨씬 어려움

 

 

7. Memory Consistency

- 중간에 interleaving 가능함

- 출력이 가능한 값

  : 메모리의 일관성에 따라 다름

  : 하드웨어가 concurrent한 접근을 처리하는 방법에 대한 추상적인 모델

 

- Sequential consistency (순차 일관성)

  : 전반적인 효과는 각 쓰레드와 일치함

  : 그렇지 않으면 arbitrary interleaving

 

- 불가능한 출력 값

 : 100, 1 and 1, 100

 -> Wa와 Wb전에 Ra와 Rb에 동시에 도달해야함

 

 

8. Non-coherent Cache Scenario

 

 

각 쓰레드에는 a, b의 카피본이 존재함

T1에서 a = 2로 만들고 , T2에서 b = 200으로 만들지만 메인 메모리에 최종 업데이트를 하지 않았기 때문에

업뎃 이전의 값을 출력하게 됨

 

 

9. Snoopy Caches

각 cache 블럭에 state를 태그함

: Invalid -> Cannot use value

: Shared -> Readable copy

: Exclusive -> Writeable copy

 

캐시가 E로 태그된 블럭의 요청을 봤을 때

-> 캐시로 부터 값을 공급받음

-> 태그를 S로 변경

 

 

-> 출력시

print 2

print 200