여기서 독립적이라는 말은 여러 처리 자원이 작업을 임의의 순서로 처리해도 결과가 동일해야 한다는 의미다. 이러한 조건을 만족하지 못하면 그 문제에 병렬 컴퓨팅을 적용할 수 없다.
어떤 프로그램을 병렬 실행할 수 있는지 알아보려면 어떤 작업으로 분해되었고, 각 작업이 독립적으로 실행 가능한지를 살펴보면 된다. 작업의 분해(decomposition)에 대해서는 7장에서 더 자세히 설명하겠다.
노트
병렬 실행할 수 있는 프로그램은 모두 순차 실행이 가능하지만, 그 반대는 성립하지 않는다. 즉, 순차 실행할 수 있는 프로그램이 모두 병렬 실행이 가능하지는 않다.
당연히 모든 프로그램이나 알고리즘이 독립적인 작업만으로 구성됐을 리 없으므로 작업 독립성이 성립하지 않는 것도 있다. 일부 작업은 독립적이지만, 이전 작업의 실행이 필요한 작업도 섞여 있다. 이런 경우에는 개발자가 서로 의존적인 작업의 순서를 맞춰 동기화(synchronize)해야 정확한 처리 결과를 얻을 수 있다.