Scheduling for Heterogenous Multi/Many Core Architectures

I've been working on an approach to dealing with heterogenous multi/manycore architectures. These are architectures in which 1) communication costs between execution units (cores) is not uniform, 2) processing capabilities of cores is not uniform, and 3) communication costs with different sections of memory is not uniform.

Scheduling tasks to run on these is quite difficult, especially in any kind of dynamic fashion. Examples of these architectures include the IBM Cell and Tilera Tile64 architectures. Cell has 8 SPU's with their own private memories and a fast interconnect, and Tile64 has an 8x8 grid of cores with busses connecting adjacent cores. An example of a non-uniform memory architecture would be IBM's P7 architecture, which shares L3 cache amongst eight cores in a non-uniform fashion. Cell and Tilera both have had a hard time when scheduled dynamically. The Cell requires expert programming, and the Tilera suffers from highly non-uniform communication costs between cores. Even P7 has many heirarchies to it: hyperthreads, cores, dies, packages, boards, blades, and boxes.

In the future, I don't see these architectures getting any simpler; rather, I see them becoming more and more complicated, and specialized, like GPU's did. Hence, my proposed solution is to take inspiration from the way we handle GPU's (and FPGA's for that matter). Rather than try to dynamically assign tasks to cores (which inherently requires centralization- an anathema to concurrency), I propose "compiling" programs to run on a heterogenous machine by splitting up tasks in a way that minimizes communication costs and maximizes computational power.

This is most assuredly NP-hard even for simple cases; however, I suspect that modern IP solvers can handle the task. IBM's CPLEX solver routinely handles problems on the order of millions of variables, and lp_solve has similar capabilities. I've devised a method for formulating the problem as an IP problem. We'll see how practical the approach is.