finding static scheduling of DAG for multiprocessors - library? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or find a tool, library or favorite off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this question

I have a graph of the dependencies of all tasks, and the costs of each task. Now I want to calculate a scheduling for a given amount of CPUs. I've found many papers on scheduling algorithms, optimal schedulers seem to be too expensive for my problem size (around 100 nodes) as it's an NP-hard problem. I'd settle for a heuristic, preferably one that has a bound how close it gets to the optimum. My problem now is: do I really have to code it myself?? This should have been solved many times before, it can be easily applied to project management, maybe there something exists?

If you happen to know a library in python that'd be perfect or the next best thing would be C++, otherwise i'd settle for anything else.

Answer 1

This is a pretty common problem. It also shows up in hardware design. There has been a lot of work on algorithms to solve it.

If you are going to write something yourself, start by checking out "Hu's Algorithm".

If you just want a solution, these functions are built into architectural synthesis programs. Look at the Wikipedia pages on high level synthesis and logic synthesis. There are several professional tools that can handle this, if you can get access to them through school or work.

There are university programs you can often get for free that can also handle this problem. I'm not up-to-date on what is currently available. An very old one is MIS II from Berkeley. It's scripting language was Tcl, not Python.