# 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

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$.