병렬 컴퓨팅 효율검사

출처: http://web.skhu.ac.kr/~mckim1/Lecture/DS/dna/class15/class15_04.html

		어떤 문제 를 해결하는 가장 빠른 순차 알고리즘의 실행시간을 이라 하자
		여기서 은 입력 데이터의 개수
		문제 를 해결하는 병렬 알고리즘이 개의 프로세서를 사용하여
		의 시간 안에 그 문제를 해결 할 수 있다하자
		이  보다 작을 수 없음
		병렬 알고리즘의 효율성(Efficiency)는  와  의 비율로 표시
		..........
		효율성의 값은 0과 1 사이의 수 - 1에 가까울수록 더 효율적인 알고리즘
		예제 : 어떤 문제를 해결하는 가장 빠르다고 알려진 순차 알고리즘의 실행시간이  초이고, 4개의
		.........프로세서를 사용하는 병렬 알고리즘이 그 문제를 푸는데 걸리는 시간이  초라 하자. 이때
		.........병렬 알고리즘의 효율성은 1 이고 이러한 알고리즘은 병렬화 과정에서 부가적으로 걸리는 시간이 전
		.........혀 없는 최적 알고리즘(Optimal algorithm)이다. 이때  초 라면 효율성은 0.75가 된다.
		속도 향상률 (Speedup)
		병렬 알고리즘의 효율을 나타낼 수 있는 또 하나의 척도 병렬 알고리즘이 동일한 문제를 푸는 순차 알고리즘에 비하여 몇 배의 속도를 냉 수 있는가를 나타냄 프로세서 4개를 사용하면 4배보다 더 높은 속도를 낼 수 없음 위의 예제에서  초,  초,  인 경우는   프로세서를 4개 사용하여 3배의 속도향상을 얻은 경우
		작업량 (Total Work)
		병렬 알고리즘이 사용한 프로세서의 개수를 그 알고리즘의 실행시간에 곱한 것 작업량이 그 문제를 푸는 가장 빠르다고 알려진 순차 알고리즘의 실행시간과 같으면   그 병렬 알고리즘은 최적 알고리즘