출처: http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class15/class15_04.html
어떤 문제 를 해결하는 가장 빠른 순차 알고리즘의 실행시간을 이라 하자 | ||||||||||||||||||||||||
여기서 은 입력 데이터의 개수 | ||||||||||||||||||||||||
문제 를 해결하는 병렬 알고리즘이 개의 프로세서를 사용하여 | ||||||||||||||||||||||||
의 시간 안에 그 문제를 해결 할 수 있다하자 | ||||||||||||||||||||||||
이 보다 작을 수 없음 | ||||||||||||||||||||||||
병렬 알고리즘의 효율성(Efficiency)는 와 의 비율로 표시 | ||||||||||||||||||||||||
.......... | ||||||||||||||||||||||||
효율성의 값은 0과 1 사이의 수 - 1에 가까울수록 더 효율적인 알고리즘 | ||||||||||||||||||||||||
예제 : 어떤 문제를 해결하는 가장 빠르다고 알려진 순차 알고리즘의 실행시간이 초이고, 4개의 | ||||||||||||||||||||||||
.........프로세서를 사용하는 병렬 알고리즘이 그 문제를 푸는데 걸리는 시간이 초라 하자. 이때 | ||||||||||||||||||||||||
.........병렬 알고리즘의 효율성은 1 이고 이러한 알고리즘은 병렬화 과정에서 부가적으로 걸리는 시간이 전 | ||||||||||||||||||||||||
.........혀 없는 최적 알고리즘(Optimal algorithm)이다. 이때 초 라면 효율성은 0.75가 된다. | ||||||||||||||||||||||||
속도 향상률 (Speedup) | ||||||||||||||||||||||||
| ||||||||||||||||||||||||
작업량 (Total Work) | ||||||||||||||||||||||||
|
'Parallel Programming' 카테고리의 다른 글
KSC 2013 3번 문제 및 답안 (0) | 2016.10.01 |
---|---|
KSC 2013 2번 문제 및 답안 (0) | 2016.10.01 |
KSC 2013 1번 문제 및 답안 (0) | 2016.10.01 |
유한차분법(finite difference method)에서 boundary exchange하기 (0) | 2016.09.28 |
블록 분할코드 (0) | 2016.09.13 |
댓글