20
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ this does not answer at all, but any model for current and upcoming supercomputers but embed faults/fault-tolerance. $\endgroup$
    – Sylvain Peyronnet
    Commented Feb 15, 2011 at 14:21
  • $\begingroup$ 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 $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 26, 2011 at 19:20
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Feb 24, 2013 at 1:34

3 Answers 3

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Riko Jacob
    Commented Feb 16, 2011 at 8:18
  • $\begingroup$ @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. :-) $\endgroup$
    – Aaron Sterling
    Commented Feb 16, 2011 at 14:21
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Riko Jacob
    Commented Feb 15, 2011 at 18:35
  • $\begingroup$ I think it's more about hierarchical memory models, that is true. $\endgroup$
    – Suresh Venkat
    Commented Feb 15, 2011 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.