Chapter 13 – 병렬 프로그래밍과 병렬 처리 Outline 13.1 병렬 처리 소개 13.2 병렬 처리와 프로그래밍 언어 13.3 세마포어 13.4 모니터 13.5 메시지 전달 기법 13.6 실시간 언어

13.1 병렬 처리 소개 병렬 처리(parallel processing) 병렬 프로그래밍에 대한 연구 다수의 프로세서들이 여러 개의 프로그램들 또는 한 프로그램의 분할된 부분들을 동시에 처리하는 기술 병렬 프로그래밍에 대한 연구  병렬 프로그래밍 언어 자체에 대한 연구 Ada, Occam, Concurrent Pascal  병렬 컴파일러에 관한 연구

13.1 병렬 처리 소개 컴퓨터 시스템을 분류 - Flynn의 분류 스트림 Flynn에 의한 네 가지 분류 하나의 프로세서에 의하여 순서대로 처리되는 일련의 명령어들과 데이터들의 흐름 Flynn에 의한 네 가지 분류 SISD(Single-instruction Single-data) SIMD(Single-instruction Multiple-data) MISD(Multiple-instruction Single-data) MIMD(Multiple-instruction Multiple-data)

13.1 병렬 처리 소개 컴퓨터 시스템을 분류 - Flynn의 분류 병렬 처리 컴퓨터는 SIMD와 MIMD

13.1 병렬 처리 소개 MIMD 형태의 병렬 처리 컴퓨터는 프로세서들이 메모리를 사용하는 방식 공유 메모리 구조(shared-memory architecture) 분산 메모리 구조(distributed-memory architecture)

13.1 병렬 처리 소개 공유 메모리 구조 공유 메모리 구조에서 일반적으로 사용되는 상호 연결망 버스(Bus) 크로스바 스위치(Crossbar Switch) 다단계 상호 연결망(Multistage Interconnection Network：MIN)

13.1 병렬 처리 소개 분산 메모리 구조의 형태 분산 메모리 구조(1) 초기의 병렬 처리 컴퓨터 메시지 전달(message passing) 방식 분산 메모리 구조의 형태

13.1 병렬 처리 소개 분산 메모리 구조(2) 분산 메모리 구조에서 사용되는 상호 연결망 선형 배열 구조 원형 구조 성형 구조 트리 구조 메시(mesh) 구조 시스톨릭(systolic) 구조 완전 연결(completely connected) 구조 코달 원형(chordal ring) 구조 하이퍼큐브(hypercube)

13.2 병렬 처리와 프로그래밍 언어 병렬, 병행 병행성의 표현 병렬 구조 모델 ① 문제가 지니고 있는 고유의 병행성을 자연스럽게 표현 ② 효율적인 병행 기계어 프로그램으로 번역 병렬 구조 모델 ① 언어들이 분산 모델을 가정하고 통신 기능을 제공 ② 공유 기억 장소 모델과 상호 배제를 위한 기능들을 사용

13.2 병렬 처리와 프로그래밍 언어 FOR i := 1 TO n DO 대표적 예제 유한 버퍼 문제(the bounded buffer problem) 병렬 행렬 곱셈(parallel matrix multiplication) 정수형 행렬 선언 VAR a,b,c：ARRAY[n,n] OF INTEGER FOR i := 1 TO n DO FOR j := 1 TO n DO c[i,j] := 0； FOR k := 1 TO n DO c[i,j] := c[i,j] + a[i,k] * b[k,j]； END；

13.2 병렬 처리와 프로그래밍 언어 명시적인 언어 기능을 사용하지 않는 병렬 프로그래밍 묵시적으로 본래의 병렬성을 포함 함수형 언어, 논리형 언어, 객체 지향 언어 프로그래밍 언어에서 병렬 구조를 정의 번역기에게 프로그래머가 병렬성이 요구되는 프로그램의 부분을 명확히 지적할 수 있도록 컴파일러 옵션을 주는 것 병렬 처리를 할 수 있는 라이브러리를 제공 m_set_procs, m_fork, m_kill_procs, m_get_myid

13.2 병렬 처리와 프로그래밍 언어 표 13.1 병렬 처리를 제공하는 라이브러리 사용의 예 #include <parallel/paralle.h> #define SIZE 100 #define NUMPROCS 10 shared int a[SIZE][SIZE], b[SIZE][SIZE], c[SIZE][SIZE]; void main(void) { int err; int multiply(); m_set_procs(NUMPROCS); m_fork(multiply); m_kill_procs(); } void multiply(void) { int i,j,k; for(i = m_get_myid(); i < SIZE; i += NUMPROCS) for(j = 0; j < SIZE; ++j) for(k = 0;k < SIZE; ++k) c[i][j] += a[i][k] * b[k][j];

13.2 병렬 처리와 프로그래밍 언어 프로세스 생성과 소멸(1) 병렬 처리 메커니즘 지원 프로세스 생성 기능 m_set_procs와 m_fork 라이브러리 프로시저 프로세스를 생성하는 방법 현 프로세스를 두 개 이상의 프로세스로 분리 사용. 같은 프로그램의 사본 사용 부모 프로세스, 자식 프로세스 SIMD 구조와 유사 SPMD(Single Program Multiple Data) 프로그래밍 각 코드 세그먼트 – 새 프로세스 각각의 다른 프로세스는 다른 코드를 가짐 MPMD 전형적인 예(fork – join 모델)

13.2 병렬 처리와 프로그래밍 언어 프로세스 생성과 소멸(2) MPMD MPMD 예 - fork-join 모델 다수의 자식 프로세스 생성(a fork) 모든 자식 프로세스 종결 기다림(a join) UNIX 시스템 호출 fork()는 SPMD 프로세스 생성기 fork-join 생성기가 아님(용어 혼돈) fork-join 모델을 MPMD 프로세스 생성기라 칭함 표 12.1 은 MPMD 예(m_kill_procs – join)

13.2 병렬 처리와 프로그래밍 언어 병렬 처리를 위한 세 가지 선택 방법 입상(granularity)크기에 따른 분류 ① 명령어 수준의 병렬성- 작은 덩이 ② 프로시저 수준의 병렬성 - 중간 덩이 ③ 프로그램 수준의 병렬성- 큰 덩이 작은 덩이 : 입상 프로세스 생성 유지 오버헤드 큰 덩이 : 병렬성 부여 기회 소멸

13.2 병렬 처리와 프로그래밍 언어 프로세스 생성자(부모), 피생성자(자식) 프로세스 생성 기법 고려 사항 구분가능(생성방법 관계없이) 프로세스 생성 기법 고려 사항 자식 프로세스 수행 중 - 부모 프로세스 일시 중지 가능한가? - 부모 프로세스 동시 실행 가능한가? 기억 장소 공유 가능 - 부모 프로세스와 자식 프로세스 자식 프로세스들 사이 표 13.1 사용 예 부모 프로세스 일시 중지 전역 변수 a, b, c (shared 선언) – 모든 프로세스 공유 프로세스 종결 기법 제공

13.2 병렬 처리와 프로그래밍 언어 명령어 수준의 병렬성 parbegin S1； S2； . . . Sn； parend - 명령어 수준의 병렬성은 VHDL과 같은 하드웨어 기술 언어 parbegin S1； S2； . . . Sn； parend for i := 1 to n do parallel begin for j := 1 to n do begin c[i,j] := 0； for k := 1 to n do begin c[i,j] := c[i,j] + a[i,k] * b[k,j]； end； for j := 1 to n do begin c[i,j] := 0； end； for k := 1 to n do begin c[i,j] := c[i,j] + a[i,k] * b[k,j]； end；

13.2 병렬 처리와 프로그래밍 언어 프로시저 수준의 병렬성 한 프로시저 – 한 프로세스 대응 생성 소멸 기법 ( p : 프로시저, x : 프로세스) 1) 2) 선언문 사용 X의 영역과 생성 종결 : 지역 변수와 유사 Ada에서 이 기법 사용 x := newprocess(p)； . . . killprocess(x)； var x : process(p);

13.2 병렬 처리와 프로그래밍 언어 프로그램 수준의 병렬성 프로세스 – 전체 프로그램 MPMD 방식(자신의 사본을 생성 : 자식 프로세스) 예 : UNIX 의 fork() 호출 시점에 환경 상속 fork() 반환 값 – 부모(n:번호), 자식(0) 프로세스 구별 exit - 생성 프로세스 종료 wait - 프로세스 동기(부모 프로세스 일시 중지)

13.2 병렬 처리와 프로그래밍 언어 표 13.2 Fork 구조를 나타내는 C코드 예 #define SIZE 100 #define NUMPROCS 10 int a[SIZE][SIZE], b[SIZE][SIZE], c[SIZE][SIZE]; void main(void) { int myid; for (myid = 0; myid < NUMPROC; ++myid ) if(fork( ) == 0) { multiply(myid); exit(0); } for (myid = 0; myid < NUMPROCS; ++myid) wait(0); /* code to output c goes here */ void multiply(int myid) { int i,j,k; for( i=myid; i < SIZE; i += NUMPROCS) for ( j=0; j < SIZE; ++j) { c[i][j] = 0; for(k = 0; k<SIZE; ++k) c[i][j] += a[i][k] * b[k][j];

13.2 병렬 처리와 프로그래밍 언어 병행 언어는 다음 사항들을 필요 ① 병렬로 실행될 수 있는 코드 묶음을 한정 프로세스, 태스크, collateral절 ② 프로세스의 실행 시작을 기술하는 방법 ③ 공유 자료의 상호 배제를 보장하는 방법 ④ 병행 프로그램들을 동기화 시킬 수 있는 수단이 제공 모니터의 대기-신호(wait-signal) 연산과 Ada의 랑데뷰(rendezvous) ⑤ 프로세스에 우선 순위를 부여하는 방법 ⑥ 프로세스를 지정된 시간 동안 지연시키는 기법

13.3 세마포어 Process 임계구역 (critical region) – mutual exclusion 요구 Terminate (정해진 시간 안에 임계구역 실행 끝냄) Fair scheduling ( 한정된 시간 안에 임계구역 들어감) 임계구역 (critical region) – mutual exclusion 요구 세마포어 (semaphor) - Dijkstra 개발, Algol 68 Binary valued variable : s 두 연산 wait(s), signal(s) Queue, fair scheduling 요구 wait(s) : if s = 1 then s := 0 else 프로세스 P를 큐에 저장 signal(s) : if queue  empty then 대기중인 프로세스 준비 else s:= 1

13.3 세마포어 표 13.3 Mutual Exclusion Using a Binary Semaphore procedure READER begin . . . wait(mutex) DB에서 자료 읽음 signal(mutex) end procedure WRITER begin . . . wait(mutex) DB에 기록 signal(mutex) end

13.3 세마포어 표 13.4 세마포어를 이용하여 해결한 생산자-소비자 문제 ok := 0 ; fin := 1 procedure PRODUCER while 입력할 레코드가 있으면 do wait(fin) 한 레코드를 버퍼에 채움 signal(ok) end procedure CONSUMER loop wait(ok) 버퍼에서 한 레코드를 읽어서 출력 signal(fin) 결과를 출력 repeat

13.3 세마포어 Counting semaphore : ALGOL 68 (sema) Collateral 문 선언문 : sema mutex Collateral 문 ( , ) 로 분리, begin – end 또는 ( ) 로 쌓임 Down mutex : if mutex = 0 then 실행이 블록됨 else mutex := mutex – 1 Up mutex : mutex := mutex + 1, mutex 때문에 블록된 프로그램 을 실행 제개함 … BEGIN S1, S2, … , Sn END begin end S1 S2 Sn 그림 13.5 Algol 68의 collateral statement

13.3 세마포어 병렬절(parallel clause) 표 13.5 Algol 68에서 해결한 생산자-소비자 문제 Begin int buffer[50] ; int I := 0, j := 0; sema numberin := level 0, openspots := level 50 ; par (do down openspots ; I := I mod 50 + 1 read(buffer[I]) ; up numberin ; od do down numberin ; j := j mod 50 + 1; print(buffer[j]) ; up openspots ; od) end

13.4 모니터 모니터 (monitor) 공유 자료 접근 코드를 하나로 묶은 단위 프로그램 Syntax monitor name SIMULA의 CLASS 비슷(추상 자료형 지원) monitor name begin 이 모니터의 지역 자료 선언 프로시저들 선언 지역 자료 초기화 코드 end name 선언된 프로시저 P를 호출하는데 다음과 같은 형식 name.P (실 매개변수들)

13.4 모니터 어느 주어진 시간에는 한 프로세스만이 모니터 프로시저를 실행시킴 Queue 구성 자동 Wait – signal Concurrent Pascal (Brinch Hansen) Modula (Wirth) Mesa (Xerox) CSP/K (Holt) – Concurrent SP/K

13.4 모니터 name : procedure options (concurrent) CSP/K 선언문 Monitor 선언 (monitor안에 entry선언) Process선언 name : procedure options (concurrent)

13.4 모니터 표 13.6 CSP/K 예 EXAMPLE: PROCEDURE OPTIONS(CONCURRENT) CRITICAL: MONITOR DECLARE (SUM) BINARY FIXED; DO; SUM=0; END; COUNT: ENTRY; SUM=SUM+1; WATCH: ENTRY; PUT SKIP LIST(SUM); SUM=0; END CRITICAL; COUNTER: PROCESS; . . . CALL COUNT; END COUNTER; WATCHER: PROCESS; CALL WATCH; END WATCHER; END EXAMPLE; 표 13.6 CSP/K 예

13.4 모니터 type 프로세스이름 = process (형식 매개 변수들) 변수, 상수, 자료형, 프로시저 선언문들; 몸체 Concurrent-Pascal(1) 프로세스, 모니터, 클래스 개념삽입 init, delay(wait), continue(signal) 자료형 : queue 프로세스 형식 (외부영역변수 상속불허) type 프로세스이름 = process (형식 매개 변수들) 변수, 상수, 자료형, 프로시저 선언문들; 몸체 end

13.4 모니터 type 모니터이름 = monitor (형식 매개 변수들) 공유 변수들 지역 프로시저들 Concurrent-Pascal(2) 모니터 형식 entry 선언 procedure type 모니터이름 = monitor (형식 매개 변수들) 공유 변수들 지역 프로시저들 진입점을 갖는 프로시저들 begin 초기화 코드 end procedure entry controldisk(var x: buffer)

13.4 모니터 Concurrent-Pascal(3) 프로세스 선언과 초기화 모니터 선언과 초기화 var X:(프로세스 이름) init X(실매개 변수) var p, q: 모니터 이름; 을 선언한 후, 문장 init q(실매개변수들)

13.4 모니터 표 13.7 Concurrent-Pascal의 생산자-소비자 문제 type buffer = array (1..80) of char, producer = process var card : buffer begin card(1) := ‘N’ while card(1) <> ‘E’ do begin read(card); spool(card) end end; consumer = process var line : buffer line := ‘N’ while line <> ‘E’ do begin unspool(line); write(line) end

13.4 모니터 cbuffer = monitor var pool : array(1..5) of buffer front, read, nobuf, noful : interger procedure entry spool(contents : buffer) begin if noful = nobuf then delay; pool(rear) := contents rear := rear mod nobuf +1; noful := noful +1; continue end; procedure entry unspool(contents : buffer) begin if noful = 0 then delay; contents := pool(front); front := front mod nobuf +1; noful := noful –1; begin front := 1; rear := 1; nobuf := 5; oful := 0 end var x: producer, y : consumer, z : cbuffer begin init x, y, z end.

13.4 모니터 모니터 병행 프로세스들이 자원을 액세스하지 못하도록 자원들의 집합 둘레에 벽을 만드는 기법 프로그래머에게 세 가지 설비를 제공 모니터 안에 정의된 프로시저를 호출하는 방법 외부에서의 다양한 호출에 대한 스케줄링 방법 - 일반적으로 큐 사용 모니터를 호출한 프로세스들의 대기와 실행 계속을 허용하는 기법 - 예) wait-signal 또는 delay-continue문

13.5 메시지 전달 기법 Processor들의 network 구축 (최근) Monitors 분산형 병행처리언어 DP, CSP 단일 processor 또는 공동기억장소사용 다중 processor 분산형 병행처리언어 Brinch Hansen : DP , Hoare : CSP DP, CSP 병행 프로그램의 실행 단위로 프로세스 선택 프로세스들 간의 통신 : 메시지 느슨히 결합된 분산 네트워크

13.5 메시지 전달 기법 Q! action(x) // Q 프로세스에 메시지 송신 // CSP 에서 프로세서 P action : 메시지 형태 지정 (형태) DP : Brinch-Hansen Q! action(x) // Q 프로세스에 메시지 송신 // P? action(y) // 프로세스 P로부터 메시지 수신 // call Q.R(input # output) // 프로세스 Q의 프로시저 R를 실행 // input : 실입력 매개 변수 output : 프로세스 Q에서 값을 받기 위해 사용된 매개 변수 procedure R(입력매개변수들 # 출력매개변수들) // Q에서 프로시저 R선언

13.5 메시지 전달 기법 [p :: commands | q :: commands] 동기화 문제 CSP, Ada, DP 보호 명령어(Guarded command) non-deterministic 지원 CSP 프로세스 선언 보호 조건을 사용할 수 있는 문장  택일 명령문(alternative command)  반복 명령문(repetitive command) [p :: commands | q :: commands] - ‘|’ : p,q 프로세스, 병행 수행 가능

13.5 메시지 전달 기법 택일 명령문 CSP 반복 명령문 DP의 Guard 문 When B1 : S1 | B2 : S2 | . . . End 조건이 참인것이 있을 때까지 기다림 cycle B1 : S1 | B2 : S2 | . . . End B1 - Bn 의 조건 중 하나 이상이 참인 경우 무한 반복 [ x > 0  y := +1 | x < 0  y := -1 | x=0  y := 0 ] i := 1; *[ i <= n; A(i)  0  A(i) := b(i) / A(i) ] - i가 1에서 n까지 배열 A(i)가 0인 경우를 제외한 모든 A(i)의 요소들을 B(i)/A(i)로 배정

슬라이드 쇼가 끝났습니다.

용 어 정리

임계 구역 (critical section) 용어 국제 표준 규격 15.04.02 critical section 임계 구역 A portion of a task during the execution of which other parts of this or other tasks are prohibited from execution. 어떤 태스크의 일부분으로 이 부분을 실행 시에는 이 태스크의 다른 부분이나 다른 태스크들의 실행이 금지된다.

세마포어 (semaphore) 용어 국제 표준 규격 15.07.06 semaphore 세마포어 A data structure for controlling, by means of a queue, access to the resources that are available to more than one task, but only to one task at a time. 두 개 이상의 태스크가 사용 가능한 자원에 접근을 큐로써 제어하기 위한 자료 구조이다. 그러나 어느 한 시간에 오직 하나의 태스크만이 사용 가능하다.

monitor (in programming language) 모니터(프로그래밍 언어에서) 용어 국제 표준 규격 15.07.07 monitor (in programming language) 모니터(프로그래밍 언어에서) A shared data object together with a set of operations that may manipulate the data object in order to control requests for resources or access to the resources that are available to parallel processes, but only to one process at a time. 자원 요청을 제어하기 위하여, 또는 병렬 프로세스들이 한번에 한 개씩 이용할 수 있게 자원에 접근하도록, 자료 객체를 다룰 수 있는 연산들의 집합을 가진 공유 자료 객체.