1
$\begingroup$

I work in computational fluid dynamics. And I spend most of my time waiting for simulation to complete.

The common way to improve simulation performance is to use a suitable distributed linear algebra library, a big computer with Infiniband, tweek some parameters and hope for the best.

Most of my simulations can be seen as many iterations of a single big "computational graph" of mul/div/add, without a single branch. It seems that finding a optimal scheduling for this computation could be seen as a optimization problem.

The absence of branch, the complete knowledge of the architecture (Memory hierarchy, number of functional units, communication interface...) and the fact that the same graph will be used many time make me think that some very aggressive optimization could be done ahead of time.

As some work been done in computer science to find a optimal scheduling for a "computational graph" and a given architecture?

$\endgroup$
  • $\begingroup$ This is a pretty broad question -- there's lots of work on compiler optimization, with different work focusing on different aspects. It's an entire field. See, e.g., en.wikipedia.org/wiki/Optimizing_compiler and en.wikipedia.org/wiki/Superoptimization. Can you think of any way to narrow the question? e.g., by focusing on one specific aspect (e.g., instruction selection; register allocation; reducing memory/cache pressure)? At present the best advice I can give is: study the literature on superoptimization. Is that what you're looking for? $\endgroup$ – D.W. Dec 2 '15 at 21:52
  • $\begingroup$ Superoptimization is very close to what I am looking for. (From the wiki article) "search in the space of valid instruction sequences" is what i was thinking about when writing my question. Superoptimization seems to focus on small scale (I think). I more looking for how to tackle large scale, let's say 10^11 branch-less instructions, where brute force is not possible. I hope this is a bit more focus. $\endgroup$ – RYegavian Dec 2 '15 at 22:38
1
$\begingroup$

The general problem of mapping a graph, where nodes are computational operations and edges are transfers of data (i.e. dependencies), to computational resources is known as graph partitioning.

The general graph partitioning problem is NP-hard and therefore not directly solvable. However, there are good heuristic approaches. There are a number of open-source frameworks for graph partitioning, for example Metis, Scotch and Zoltan.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.