So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done as efficiently as possible. I wonder if any of you know how my problem can be mapped to existing compiler or graph algorithms?

My computations have this kind of structure. There are $N$ values in memory, of which the computation device can load at most $M$ in some kind of local cache. Computations can only be done on what's in the local cache. There are only two kinds of operations, for arbitrary $f$ and $x, y \in [N], x \neq y$:

One operand instructions: $x \leftarrow f(x)$

Two operand instructions: $x \leftarrow f(x, y)$

The computation can be represented as an ordered sequence of these operations, but there is a lot of memory locations and therefore plenty of opportunity for reordering operations without breaking correctness. The computation device's cache can swap in memory values anytime and anywhere on command, e.g. it is not just a LRU cache.

How could I schedule the computation to minimize the number of swap-in operations? Is there a good algorithm to actually minimize this number, and if not are there good heuristic methods I can look into?

I feel like my problem can be thought of as trying to optimize register usage for a compiling a highly restricted imperative language. I know that if I write a C function that manipulates a lot of local variables with simple operations, and run a decent compiler on it, it will reorder the operations and fit all the variables around the limited registers available while trying to load from memory as infrequently as possible, similar to what I want. But I don't know exactly what algorithms are responsible for making this work, or if they scale well when $N$ and $M$ is large.

I also feel like topological sorting might be relevant to the algorithms used, but with the parallelism available in my problem there are intractably many topological sorts for the computation's dependency graph, and I'm not sure how I could find the best among them.


Your Answer

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

Browse other questions tagged or ask your own question.