작업(Work)과 전파 시간(Span) 크레딧을 위한 병렬 시간 복잡도 분리 논리

요약

본 글은 fork-join 프로그램의 병렬 시간 복잡도를 검증하기 위한 새로운 동시성 분리 논리인 Parcas를 제시합니다. Parcas는 총 연산 횟수를 측정하는 '작업(work)'과 가장 긴 순차적 의존 체인을 측정하는 '전파 시간(span)'이라는 두 가지 기준을 다룹니다. 이를 위해 각각 작업 크레딧과 전파 시간 크레딧을 도입하여 병렬성을 엄격하게 증명할 수 있습니다.

핵심 포인트

• Parcas는 fork-join 프로그램의 병렬 시간 복잡도 검증 논리입니다.
• 작업(work)은 총 연산 횟수로, 작업 크레딧으로 제한됩니다.
• 전파 시간(span)은 가장 긴 순차적 의존 체인이며, 전용 크레딧과 규칙이 필요합니다.