병렬 알고리즘 - 병렬 컴퓨터

병렬 알고리즘

- 여러 대의 컴퓨터를 사용하여 빠르게 처리하기 하기 위한걸 병렬 처리라고함. 병렬 컴퓨터에서 실행하도록 고안됨.

병렬 컴퓨터

병렬 컴퓨터는 CPU와 메모리 ,입출력 장치 등을 포함한 여러 개의 시스템들을 하나로 묶어서 구성하여 마치 하나처럼

사용할 수 있는 컴퓨터를 말한다. 이러한 병렬 처리 구현을 위해 파이프라인 방식, 배열 프로세서, 다중 연산 기법 등을 사용한다.

구분	내용
SISD	일반적인 컴퓨터 구조( 폰 노이만 방식) 단일 명령어 흐름에 따른 단일 데이터 흐름 컴퓨터 하나의 명령에 따른 하나의 자료를 처리하는 구조 병렬 처리는 파이프라인 구조로 구현
SIMD	단일 명령어 흐름에 따른 다중 데이터 흐름 컴퓨터 하나의 명령에 따른 여러 자료를 동시에 처리하는 구조 병렬 처리는 배열 처리와 벡터 처리 구조 모든 데이터 요소들을 같은 계산으로 수행
MISD	다중 명령어 흐름에 따른 단일 데이터 흐름 컴퓨터 여러 명령에 따른 하나의 자료를 처리하는 구조 실제로 구현된 적이 거의없음 이론적으로 제시 일관성 무너질수 있음
MIMD	다중 명령어 흐름에 따른 다중 데이터 흐름 컴퓨터 여러 명령에 따른 여러 자료를 동시에 처리하는 구조 여러 개의 처리기가 독립적인 명령어로 각각 다른 자료처리 병렬 처리는 다중 처리 구조로 구현 처리기 상호연결 시 Tightly Coupled System을 다중처리기 Loosely Coupled System을 분산 처리기 시스템이라 함

플린 에 의한 병렬 컴퓨터 분류

기본 용어

- 순차 컴퓨터 : single processor를 가져서 한 번에 1개의 명령만을 수행할 수 있음

- 순차 알고리즘 : 순차 컴퓨터에서 실행하도록 고안한 알고리즘

- 플린 분류에서 S가 붙으면 싱글이고 M 이 붙으면 멀티플이다.

PRAM 모델

- P개의 프로세서 P로 구성, P개의 프로세서는 기억용량이 큰 직접 접근 기억장치 M을 공용하는 계산 모델로 동기화된 공유 메모

메모리 MIMD 컴퓨터이다.

입력 단계 , 계산 단계 , 기억 단계가 있다.

PRAM 모델은 여러 개의 프로세서들이 동시에 메모리에 접근할 떄 그들 중 동시에 어떤 프로세서의 자료가 메모리에 읽고 쓰기가

가능한지는 메모리의 접근방식에 따라 4가지로 나뉜다.

읽고 쓰기 알고리즘	의미
CRCW	동시 읽기/ 동시 쓰기
CREW	동시 읽기/ 독점 쓰기
ERCW	독점 읽기/ 동시 쓰기
EREW	독점 읽기/ 독점 쓰기

PRAM 추가 설명

- CRCW 는 여러 개의 프로세서를 동일한 메모리 셀에 동시에 읽고 쓸 수 있음.  O(f(n))의 복잡도를 가짐

- CREW 는 여러 개의 프로세서를 동일한 메모리 셀에 동시에 읽고 1개의 프로세서만이 특정 메모리 셀에 쓸 수가 있다.

- ERCW 는 현실성이 떨어진다. 반면에 EREW는 현실적으로 구현이 쉬움.

- PRAM은 현재의 기술로는 구현하기 힘든 모델.

- 병렬 알고리즘 개발 시 프로세서 간의 정보교환에 드는 비용을 무시할 수 있음.

- 이론 분야에서 병렬 알고리즘의 개발 분석에 사용할 수 있는 좋은 모델

병렬 알고리즘의 효율성

어떤 문제를 푸는 가장 좋은 알고리즘의 실행시간이 T(n)이라고 가정하고 n은 문제의 입력자료 개수를 의미.

이 문제를 푸는 병렬 알고리즘은 p개의 프로세서를 사용하며 P(n)시간이 걸린다고 했을 떄 병렬 알고리즘의 시간 효율성은 

T(n)/p와 P(n)으로 표시할 수 있음.

TE = T(n)/ p x P(n) 

0과 1사이의 수로서 1에 가까울수록 더 효율적인 알고리즘이 된다.

T(n)  = 16 chdlrh 프로세서 4개를 사용해서 4초가 걸렸다면 시간의 효율성은 1이 되고 가장 완벽하다.

만일 5초가 걸렸다면 16초(4*5) = 0.8 이 된다. 병렬 알고리즘의 효율을 나타내는 또 다른 하나의 척도는 속도의 향상률로서,

T(n)/P(n)으로 나타낸다.  위의  예시에서는 3.2배 향상된다. p*P(n)이 그 알고리즘의 작업량이 된다.

최솟값 찾기

간단한 순차 알고리즘으로는 배열을 차례대로 순차적으로 검색하면서 현재까지 검색한 자료중 가장 작은 값을 저장해 두는 방법

이 있다. 이 알고리즘은 n-1회의 원소 간 비교를 한다. 

CREW PRAM 알고리즘의 효율성 . 

- N/2개의 프로세서를 사용하면 실행시간은 O(logn)이 된다.

- 순차 알고리즘의 실행시간이 O(n)이 된다.

- 최솟값을 구하는 병렬 알고리즘의 시간 효율성은 - T(n)/pP(n) = O(1/logn)

위의 알고리즘은 첫 번째 단계에서는 n/2개의 프로세서를 사용하지만 두 번째 단계에서는 n/4개의 프로세서를 사용하는 등

효율성이 좋지 않음.

최솟값 찾는 최적 CREW PRAM의 효율성

제 1단계에서는 O(logn)이 되고  2번째 단계에서는 O(logn)의 작업량 필요, O(logn) 시간에 끝냄. 프로세서의 수와 실행시간

곱한 값이 O(n)이 되어 최적 알고리즘이 됨. 이걸 블록화라고 함.

- 포인터를 옮기면서 해결하는 기법을 포인트 점핑, 혹은 더블링 이라함.

- 행렬 곱셈의 실행시간 O(n) 계산상의 낭비가 없음. 

- 병렬 합병 정렬 - 분할, 정복, 통합 이 있음  정복에선 반복하여 재귀호출을 함. 분할에선 n/2개의 부분 배열로 분할. O(log^2n).