Work Stealing은 항상 가장 적절한 사용자 수준의 스레드 스케줄링 알고리즘입니까?

Question

저는 구현중인 스레드 풀에 대한 다른 스케줄링 알고리즘을 조사했습니다. 해결할 문제의 본질 때문에 병렬로 실행되는 작업은 독립적이며 새로운 작업을 생성하지 않는다고 가정 할 수 있습니다. 작업은 다양한 크기 일 수 있습니다.

로컬 작업 대기열에 대해 잠금없는 데크를 사용하여 가장 인기있는 스케줄링 알고리즘 인 "work stealing"을 즉시 사용했습니다.이 접근법에 비교적 만족합니다. 그러나 나는 work-stealing이 최선의 방법이 아닌 일반적인 경우가 있는지 궁금해하고 있습니다.

이 특정 문제에 대해서는 각 개별 작업의 크기를 잘 예측했습니다. Work-stealing은이 정보를 사용하지 않으며이 정보로 작업을 도용하는 것보다로드 밸런싱을 향상시키는 스케줄러가 있는지 궁금합니다.

NB. 이 질문은 이전의 question과 관련이 있습니다.

Answer 1

나는 작업을 선전 할 것이다. 예상 실행 시간에 대한 정보를 사용하여 각 스레드에 대해 개별 대기열에 분배 할 수 있습니다.

작업 배포는 기본적으로 knapsack problem이며 각 큐의 시간은 동일해야합니다.

큐를 실행하는 동안 큐를 수정하려면 논리를 추가해야합니다. 예를 들어, 예상 가동 시간이 실제 가동 시간과 일정량 차이가 난 후에 재분배가 이루어져야합니다.

Answer 2

작업 도용 스케줄러는 해당 정보를 사용하지 않지만 이론적 인 한계를 제공하는 데 의존하지 않기 때문에 가능합니다 (예 : 사용하는 메모리, 작업자 간의 예상되는 전체 통신 또한 예상 시간은 여기에 읽을 수있는 완전 엄격한 계산을 실행합니다 : http://supertech.csail.mit.edu/papers/steal.pdf를)

한 가지 흥미로운 종이 (난 당신이 액세스 할 수있는 희망 : http://dl.acm.org/citation.cfm?id=2442538를) 실제로 (즉 되려고 노력 공식적인 증거를 제공하는 제한된 실행 시간을 사용 가능한 한 원래의 도둑질 경계에 가깝게).

그렇습니다. 예를 들어 불균형 트리 검색 및 기타 특정 사례와 같이 작업 도용이 최적으로 수행되지 않는 경우가 있습니다. 그러나 이러한 경우 최적화가 수행되었습니다 (예 : 하나의 작업 (예 : http://dl.acm.org/citation.cfm?id=571876) 대신 피해자의 양말의 절반을 도용하여 허용).