# What is the right theoretical model to design algorithms for current and upcoming high performance computers

This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in.
Here, I ask specifically about current high performance computers (like the ones listed as the Top 500) or even about upcoming supercomputers.

Given that these computers are typically working on huge data sets (it seems that some people use such machines mainly because they have enormous combined main memory) aspects of the I/O-model (introduced by Aggarwal and Vitter in 1988) and its parallel version, the PEM (Arge, Goodrich, Nelson and Sitchinava in 2008) should be present. On the other hand, there should be something about communication, in particular punishing ultra small packages to all other computing nodes.

As you might imagine, I am not afraid that I am running out of ideas when creating a new model, but I am a little worried that I might overlook previous attempts in doing so, in particular because I have the impression that the years 1980-1995 or so saw many such modeling attempts (like BSP or bridging models) that seem to not have been widely used.

What models should I take a closer look at?

• this does not answer at all, but any model for current and upcoming supercomputers but embed faults/fault-tolerance. – Sylvain Peyronnet Feb 15 '11 at 14:21
• Have look at Flynn's taxonomy. According to Wikipedia, "All the top 10 and most of the TOP500 supercomputers are based on a MIMD architecture". en.wikipedia.org/wiki/MIMD – Mohammad Al-Turkistany Feb 26 '11 at 19:20
• can you clarify the sentence: "On the other hand, there should be something about communication, in particular punishing ultra small packages to all other computing nodes." is that a typo? should it be pushing? could one answer to this question be parallel design patterns eg mapreduce, Hoare's CSP? see also cache oblivious algorithms, wikipedia – vzn Feb 24 '13 at 1:34

## 3 Answers

At PODC 2009, Bruce Hendrickson gave a phenomenmal invited talk about these issues. (His slides don't appear to be online, but you might want to ask him if you could see them.) I don't think there's a "right" model yet -- bonus for you! -- but I would suggest you look at his papers, especially the ones on the Graphs and Architectures page, where he tries to figure out how to handle enormous graphs with little structure (i.e. "modern" datasets) on massively multithreaded machines.

• Thanks for the pointer. Glancing through it, I have the impression that he is not so much into defining a model that would allow theoretical analysis. Do I overlook something? Perhaps I should contact him directly. – Riko Jacob Feb 16 '11 at 8:18
• @Riko Jacob: I agree that Hendrickson is more of a practitioner than a modeler. I thought he had a superb intuition for what was needed, though. If you want papers about models, you might be more interested in the Workshop on Theory and Many-Cores. I don't find any of those models satisfying, though, and I would be very interested to see what you come up with. :-) – Aaron Sterling Feb 16 '11 at 14:21

One issue that is unclear is how caches will develop. The 2009 thesis of Nikos Hardavellas considers these things from a systems perspective, including considerations of physical limits to scalable memory systems. The thesis does not present a model as such, but may give you some clues.

One model that captures hierarchical models nicely (think local cores, shared on-chip memory, and global memory) is a STOC 87 paper by Aggarwal et al. I don't think it ever got any traction, but it makes an interesting read. The main idea is that access to memory location x takes time $\lceil \log x\rceil$.

• After glancing through it, it looks to me like a predecessor of the cache-oblivious model. I also did not see any ideas about parallel processing. Did I miss something here? – Riko Jacob Feb 15 '11 at 18:35
• I think it's more about hierarchical memory models, that is true. – Suresh Venkat Feb 15 '11 at 19:27