ParallelSpeedup

Code

public class ParallelSpeedup

{

    public int numProcessors(int k, int overhead) {

        int min = k;

        for (int num = 2, j = 0, d = 1; ; num++, j += d++) {

            int cycleTime = (k%num == 0) ? k/num : k/num+1;

            int total = cycleTime + (j+d)*overhead;

            if(min <= total) return num-1;

            min = total;

        }

    }

}

Explanation

cycle은 모든 프로세서가 한 번 돌때 걸리는 시간이다. 단일 프로세스가 처리할 수 있는 작업량이 남았을 경우에도 모든 프로세서는 작동하기 때문에 k/i가 아닌 k/i + 1을 해준다.

(j+d)*overhead

프로세서가 추가될 때마다 오버헤드는 증가하므로 총 프로세서 수 - 1 을 해주면 된다. 증가하는 방식은 등차수열이다.