[컴퓨터 알고리즘]병렬 알고리즘

소개

병렬 알고리즘에 대한 전반적인 소개와 더불어

간략한 수도코드가 들어있습니다.

목차

1. Introduction
2. Parallel Computer Model
3. PRAM ( Parallel Random Access Machine )
4. Examples
5. Efficiency

본문내용

Parallel Algorithm

1. Introduction

어떤 농부가 100000평의 논을 추수해야 한다고 하자. 아무리 기계를 이용한다한들 십만평의 논을 추수한다는 것은 매우 힘든 일이다. 이 작업을 가장 오랫동안 길게 하려면, 농부 혼자서 추수를 하면 된다. 그러나 3명의 인부를 써서 추수작업을 병렬로 수행한다면 이 추수를 빠르게 끝낼 수 있다.
여러 사람이 동시에 사용하여 어떤 작업을 병렬로 수행하면 그 일을 빨리 종료할 수 있듯이, 우리가 컴퓨터를 사용하여 문제를 해결할 때에도 여러 개의 프로세서가 컴퓨터 프로그램의 명령어들을 병렬로 수행한다면 일을 훨씬 빨리 끝낼 수 있다. 그러면 위의 이야기에서 우리는 추수하는 농부를 프로세서로, 추수작업은 컴퓨터가 처리해야 할 프로그램으로 간주할 수 있다.

이와 같은 코드는 이 문제를 해결하는 코드이다. 배열 s의 크기가 n이므로 s[i] < smallest의 코드는 n-1번 수행되고 결국 O(n)의 시간복잡도를 가지게 된다. 이 프로그램을 프로세서가 여러 개인 환경에서 병렬로 실행시킨다고 해서 각 프로세서가 일을 나누어서 처리하지 않는다. 물론 병렬 환경을 지원하는 컴파일러나 환경의 도움으로 앞에서 처럼 작성된 코드는 컴파일 타임에 병렬 환경을 지원하게끔 변환되어져 수행될 수도 있지만 그런 상황을 생각하지 않는다면 말이다. 따라서 우리는 이 문제를 병렬 알고리즘으로 보다 빠른 시간에 해결하고자 한다면 병렬 환경을 생각해서 알고리즘을 재작성해야 하는 것이다.

참고자료

· 없음