<p>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 <a href="http://www.sandia.gov/~bahendr/graphs-and-architectures.html" rel="nofollow">Graphs and Architectures page</a>, where he tries to figure out how to handle enormous graphs with little structure (i.e. "modern" datasets) on massively multithreaded machines.</p>

CC BY-SA 2.5
2011-02-16T08:18:56.150Z
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
CC BY-SA 2.5
2011-02-16T14:21:48.877Z
@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](http://www.umiacs.umd.edu/conferences/tmc2009/).  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
CC BY-SA 2.5
2011-02-15T21:40:45.177Z
2011-02-15T21:40:45.177Z
Aaron Sterling
<p>One issue that is unclear is how caches will develop. The 2009 <a href="http://reports-archive.adm.cs.cmu.edu/anon/2009/CMU-CS-09-150.pdf" rel="nofollow">thesis of Nikos Hardavellas</a> 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.</p>

CC BY-SA 2.5
2011-02-21T19:58:49.063Z
2011-02-21T19:58:49.063Z
Rasmus Pagh
<p>One model that captures hierarchical models nicely (think local cores, shared on-chip memory, and global memory) is a <a href="http://portal.acm.org/citation.cfm?id=28395.28428" rel="nofollow">STOC 87 paper by Aggarwal et al</a>. 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$.</p>

CC BY-SA 2.5
2011-02-15T18:35:54.967Z
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
CC BY-SA 2.5
2011-02-15T19:27:36.537Z
I think it's more about hierarchical memory models, that is true.
Suresh Venkat
CC BY-SA 2.5
2011-02-15T17:28:25.747Z
2011-02-15T17:28:25.747Z
Suresh Venkat
<p>This question is similar to a <a href="https://cstheory.stackexchange.com/q/2656/3049">more general question</a> for what is the right theoretical model of a computer to design algorithm and data structures in.<br>
Here, I ask specifically about current high performance computers (like the ones listed as the <a href="http://www.top500.org/" rel="nofollow noreferrer">Top 500</a>) or even about upcoming supercomputers.</p>

<p>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 <a href="http://portal.acm.org/citation.cfm?id=48535" rel="nofollow noreferrer">Aggarwal and Vitter in 1988</a>) and its parallel version, the PEM (<a href="http://doi.acm.org/10.1145/1378533.1378573" rel="nofollow noreferrer">Arge, Goodrich,  Nelson and Sitchinava in 2008</a>) should be present. 
On the other hand, there should be something about communication, in particular punishing ultra small packages to all other computing nodes. </p>

<p>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.</p>

<p>What models should I take a closer look at?</p>

CC BY-SA 2.5
2011-02-15T14:21:30.073Z
this does not answer at all, but any model for current and upcoming supercomputers but embed faults/fault-tolerance.
Sylvain Peyronnet
CC BY-SA 2.5
2011-02-26T19:20:59.933Z
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". http://en.wikipedia.org/wiki/MIMD
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-02-24T01:34:30.920Z
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](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm)
vzn
<reference-request><soft-question><machine-models>
What is the right theoretical model to design algorithms for current and upcoming high performance computers
Riko Jacob
# What is the right theoretical model to design algorithms for current and upcoming high performance computers

(Asked by: username_0 on 2011-02-15)

This question is similar to a [more general question](https://cstheory.stackexchange.com/q/2656/3049) 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](http://www.top500.org/)) 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](http://portal.acm.org/citation.cfm?id=48535)) and its parallel version, the PEM ([Arge, Goodrich, Nelson and Sitchinava in 2008](http://doi.acm.org/10.1145/1378533.1378573)) 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?

**Tags:** reference-request, soft-question, machine-models
> **Comments:**
> **username_1**: this does not answer at all, but any model for current and upcoming supercomputers but embed faults/fault-tolerance.  
> **username_2**: 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". http://en.wikipedia.org/wiki/MIMD  
> **username_3**: 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](http://en.wikipedia.org/wiki/Cache-oblivious_algorithm)  

---

## 3 answers

### Answer by username_4 on 2011-02-15. Score: 9

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](http://www.sandia.gov/~bahendr/graphs-and-architectures.html), where he tries to figure out how to handle enormous graphs with little structure (i.e. "modern" datasets) on massively multithreaded machines.

> **Comments:**
> **username_0**: 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.  
> **username_4**: @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](http://www.umiacs.umd.edu/conferences/tmc2009/).  I don't find any of those models satisfying, though, and I would be very interested to see what you come up with. :-)  

---

### Answer by username_5 on 2011-02-21. Score: 8

One issue that is unclear is how caches will develop. The 2009 [thesis of Nikos Hardavellas](http://reports-archive.adm.cs.cmu.edu/anon/2009/CMU-CS-09-150.pdf) 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.


---

### Answer by username_6 on 2011-02-15. Score: 4

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](http://portal.acm.org/citation.cfm?id=28395.28428). 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$.

> **Comments:**
> **username_0**: 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?  
> **username_6**: I think it's more about hierarchical memory models, that is true.  

---

