3 ms·

A very timely submission! I've been looking into performance optimizations on heterogeneous multicore systems and much of what I've seen published recently on

by OldHand2018 5y ago

A very timely submission! I've been looking into performance optimizations on heterogeneous multicore systems and much of what I've seen published recently on Arxiv seems to point to tasks, their granularity and their scheduling as increasingly important. This book mentions but doesn't spend a lot of space on these subjects. It will be very interesting to see how it all evolves.

jandrewrogers 5y ago
A book could probably be written on the topic of latency-hiding schedule design alone, and I am not aware of a canonical resource that gives it a thorough treatment. The case of regular hardware/software parallelism is trivial, but it becomes interesting and very complex once you introduce irregular hardware parallelism (e.g. heterogeneous compute elements) or irregular software parallelism (e.g. variable and unpredictable task concurrency -- graph analysis often has this characteristic). The optimal number of tasks any scheduler deals with always falls in a bounded range; trying to keep the number of immediate tasks within that range when the tasks are generated unpredictably and non-locally is non-trivial. It isn't enough that the task scheduler is adaptive to irregular hardware and software parallelism, in HPC you are effectively running a lot of task schedulers in parallel, each managing their local compute environment and interacting with each other. You sort of need a "meta-scheduler" to schedule the dynamic behavior across all the schedulers so they don't adversely affect each other, which is not scalable. An alternative approach I've often seen is adding a game theoretic context to task schedulers, each tacitly modeling the expected dynamic behavior of other schedulers they interact with. This doesn't require schedulers to explicitly coordinate their state, a big win for scalability, in order to optimize their aggregate behavior. In the HPC context a robust and nearly optimal equilibrium can sometimes be achieved. In the ideal case you can prove the resource requirements for an individual scheduler that can guarantee well-bounded worst case behaviors. In HPC the topology of the schedulers is essentially fixed (i.e. you know what hardware you are working with) but there is an even more difficult flavor of the same latency-hiding task scheduling problem when the execution environment can have a variable topology i.e. nodes appear and disappear in random places. There is still a lot opportunity for interesting research on this topic.
- OldHand2018 5y ago
  You know, I have noticed some of this when going over research papers, but I don't think I'm fully appreciating the significance. I appreciate the response, although it is going to force me to do more research and do a lot more thinking ;)

jandrewrogers 5y ago

A book could probably be written on the topic of latency-hiding schedule design alone, and I am not aware of a canonical resource that gives it a thorough treatment. The case of regular hardware/software parallelism is trivial, but it becomes interesting and very complex once you introduce irregular hardware parallelism (e.g. heterogeneous compute elements) or irregular software parallelism (e.g. variable and unpredictable task concurrency -- graph analysis often has this characteristic). The optimal number of tasks any scheduler deals with always falls in a bounded range; trying to keep the number of immediate tasks within that range when the tasks are generated unpredictably and non-locally is non-trivial. It isn't enough that the task scheduler is adaptive to irregular hardware and software parallelism, in HPC you are effectively running a lot of task schedulers in parallel, each managing their local compute environment and interacting with each other. You sort of need a "meta-scheduler" to schedule the dynamic behavior across all the schedulers so they don't adversely affect each other, which is not scalable. An alternative approach I've often seen is adding a game theoretic context to task schedulers, each tacitly modeling the expected dynamic behavior of other schedulers they interact with. This doesn't require schedulers to explicitly coordinate their state, a big win for scalability, in order to optimize their aggregate behavior. In the HPC context a robust and nearly optimal equilibrium can sometimes be achieved. In the ideal case you can prove the resource requirements for an individual scheduler that can guarantee well-bounded worst case behaviors. In HPC the topology of the schedulers is essentially fixed (i.e. you know what hardware you are working with) but there is an even more difficult flavor of the same latency-hiding task scheduling problem when the execution environment can have a variable topology i.e. nodes appear and disappear in random places. There is still a lot opportunity for interesting research on this topic.

OldHand2018 5y ago
You know, I have noticed some of this when going over research papers, but I don't think I'm fully appreciating the significance. I appreciate the response, although it is going to force me to do more research and do a lot more thinking ;)