여러 CPU를 써서 소수를 구하는 프로그램을 만든다면 우선 단순히 ‘일정한 크기만큼 분할해서 계산’하면 되겠다는 생각이 듭니다. 정수 1부터 100만까지 중에서 소수를 찾는다면 다음과 같이 하면 되지 않을까요?

• CPU 1: 정수 1~25만 중에서 소수를 찾습니다.

• CPU 2: 정수 25~50만 중에서 소수를 찾습니다.

• CPU 3: 정수 50~75만 중에서 소수를 찾습니다.

• CPU 4: 정수 75~100만 중에서 소수를 찾습니다.

그러나 이렇게 하면 CPU 0이 먼저 끝나고 CPU 4는 제일 나중에 끝날 것입니다. 숫자가 클수록 소수 판별이 늦게 끝날 테니까요. 싱글스레드 프로그램보다는 효율적이겠지만, 아무래도 모든 CPU를 골고루 사용하는 방법과는 거리가 먼 것 같습니다.

다음과 같이 이를 개선해 보겠습니다.

• 전역 변수 num을 만듭니다.

• 각 스레드는 num에서 값을 하나씩 가져옵니다. 가져온 값이 소수인지 판별합니다.

• 소수면 배열 primes에 찾은 숫자를 넣습니다.

• 모든 스레드가 일을 마치고 나면 소수를 출력합니다.

그림 1-16은 이 과정을 코드로 표현한 것입니다.

▲ 그림 1-16 개선된 소수 찾기 프로그램