1

I'm studying task-based parallel computing and got interested in a variation of the old project management problem -- the critical path of an activity-on-vertex (AOV) project network, which can be calculated using the topological sorting algorithm if there's no deadlock cycle. The total time of those activities on a critical path gives the minimum completion time of the project.

But this is assuming we always have enough workers simultaneously finishing the activities with no dependence on each other. If the number of workers (processors/cores) available is finite, certain activities can wait not because some activities they depend on have not yet been finished, but simply because all workers are now busy doing other activities. This is a simplified model for today's multi-core parallel computing. If there's only one worker who has to do all the activities, the project completion time is the total time of all activities. We are back to single-core serial computing that way.

Is there an efficient algorithm that gives the minimum completion time of an AOV network given a finite number of workers available? How should we wisely choose which activities to do first when the doable activities is more than the number of workers so as to minimize the idling time of workers later on? The minimum time should be somewhere in between the critical path time (infinite workers) and the total time of all activities (one worker). It should also be greater than equal to the total time divided by the number of workers (no idling). Is there an algorithm to get that minimum time?

Improve this question
1
  • I googled some Youtube videos. The problem here is a special case of the constrained-resource project management. In my problem, every activity occupies one worker (processor). But unfortunately, those videos do not tell me a general algorithm. The method used there is shifting the floating activities while maintaining the critical path unchanged, to reduce the peak resource consumption rate under some constraint. This is not always possible if the constraint is very low and the project just has to delay. Any ideas? Commented Sep 16, 2016 at 15:39

1 Answer 1

Reset to default
1

I found a C++ conference video called "work stealing" that almost answers my question. At 18:40, the problem is said on the slide to be NP-hard if activities cannot be paused, further divided, or transferred from worker to worker. Such restrictions make decisions of which workers to finish which jobs (activities) too hard to make. Work stealing is therefore introduced to avoid making such difficult decisions beforehand. Instead, it makes such decions no longer crucial so long as certain apparent greedy rules are followed. The whole project will be always finished as soon as possible under the constraint of either the critical path or the no-idling time of the finite number of workers or both. The video then goes on talking about how to make the procedure of "work stealing" between different workers (processors) more efficient by making the implementation distributed and cache-friendly, etc.

According to the video, future C++ shared-memory parallel coding will be task-based rather than loop-based. To solve a problem, the programmer defines a bunch of tasks to finish and their dependence relations to respect, and then the coding language will automatically schedule the tasks on multiple cores at run time in a flexible way. This "event-driven"-like way of implementing a flexible code by a distributed task queuing system will become very useful in parallel computing.

When an optimization problem is NP-hard, the best way to solve it is to find ways to avoid it.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

While some problems are NP-hard in general, often there are many special cases that you can solve efficiently or even with a gauranteed small fraction more than optimal. So the ideal scheme would be to solve the problem well where you can (expending only bounded resources to find a decent solution) and mix in a solution like weak stealing where you can't.
There are already work-stealing implementations of many languages around. Cilk is work-stealing version of C and C++; I think you get this in Intel compilers and I was pretty sure somebody was trying to install it into GCC. Our PARLANSE compiler implements task-level parallelism; it uses some compile time analysis to improve partial order computations and work-stealing to handle load balancing. See semdesigns.com/Products/Parlanse/… It could do better using estimations of task run times; better to schedule a long task first.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.