새로운 프로젝트 관리 알고리즘이 한정된 수의 직원을 필요로했습니다

Question

저는 작업 기반 병렬 컴퓨팅을 연구 중이며 오래된 프로젝트 관리 문제의 변형에 관심이있었습니다 - AOV (critical-activity-on-vertex) 프로젝트 네트워크는 교착 상태 사이클이 없다면 토폴로지 정렬 알고리즘을 사용하여 계산할 수 있습니다. 임계 경로에있는 활동의 총 시간은 프로젝트의 최소 완료 시간을 제공합니다.

그러나 이것은 우리가 항상 서로에게 의존하지 않고 활동을 마무리하는 데 충분한 인력을 고용하고 있다고 가정합니다. 사용할 수있는 작업자 (프로세서/코어)의 수가 제한적일 경우 특정 작업은 의존하는 활동이 아직 완료되지 않았기 때문에가 아니라 단순히 모든 작업자가 다른 활동을 수행하기 때문에 바쁠 수 있습니다. 이것은 오늘날의 멀티 코어 병렬 컴퓨팅을위한 단순화 된 모델입니다. 모든 활동을 수행해야하는 직원이 단 한 명이라면 프로젝트 완료 시간은 모든 활동의 총 시간입니다. 우리는 그런 식으로 싱글 코어 직렬 컴퓨팅으로 돌아 왔습니다.

제한된 수의 근로자를 사용할 수있는 경우 AOV 네트워크의 최소 완료 시간을 제공하는 효율적인 알고리즘이 있습니까? 어떻게 할 수있는 활동이 나중에 더 많은 근로자들의 공회전 시간을 최소화 할 수 있도록 근로자의 수보다 많을 때 먼저해야 할 활동을 현명하게 선택해야합니까? 최소 시간은 임계 경로 시간 (무한 작업자)과 모든 활동의 총 시간 (한 명의 작업자) 사이의 어딘가에 있어야합니다. 또한 전체 시간을 근로자 수로 나눈 값 (공회전 없음)보다 커야합니다. 최소 시간을 얻기위한 알고리즘이 있습니까?

Answer 1

나는 거의 질문에 대답하는 "work stealing"이라는 C++ 회의 비디오를 발견했습니다. 18시 40 분에, 활동이 일시 중지되거나, 더 분열되거나, 근로자에서 근로자로 이전 될 수 없다면 문제는 미끄럼틀에서 NP 하드가된다. 그러한 제한은 어떤 작업자가 어떤 작업 (활동)을 끝내기가 너무 어려운지에 대한 결정을 내린다. 따라서 사전에 그러한 어려운 결정을하는 것을 피하기 위해 도둑질이 도입됩니다. 그보다는 명백한 탐욕스러운 규칙이 따르는 한 더 이상 그러한 결정을 내리지 않습니다. 전체 프로젝트는 제한된 수의 근로자의 임계 경로 또는 무부하 시간의 제약 조건 또는 둘 모두의 제약 하에서 가능한 한 빨리 완료됩니다. 비디오는 구현이 분산되고 캐시 친화적이되도록하여 다른 직원 (프로세서)간에 "작업 도용"절차를보다 효율적으로 만드는 방법에 대해 설명합니다.

비디오에 따르면 향후 C++ shared- 메모리 병렬 코딩은 루프 기반보다는 작업 기반이 될 것입니다. 문제를 해결하기 위해 프로그래머는 여러 작업을 정의하고 종속 관계를 존중하도록 정의한 다음 코딩 언어가 런타임에 여러 코어에서 작업을 유연한 방식으로 자동으로 예약합니다. 분산 태스크 큐잉 시스템으로 유연한 코드를 구현하는 "이벤트 중심"방식은 병렬 컴퓨팅에서 매우 유용하게 사용될 것입니다.

최적화 문제가 NP 하드 인 경우 문제를 해결하는 가장 좋은 방법은 문제를 방지하는 것입니다.