Hi-Spade

Hierarchy-Savvy parallel algorithm design

A hierarchy-savvy approach to algorithm design and systems for emerging parallel hierarchies.

---

Good performance requires effective use of the cache/memory/storage hierarchy. Algorithm designers and application/system developers often tend towards one of two extremes:

• Ignorant: They ignore the hierarchy, programming to the API view of memory + I/O and often ignoring parallelism. Because the hierarchy is ignored, performance can suffer greatly.
• (Pain)fully aware: They consider all the details of the hierarchy, and hand-tune to a given platform. This demands high programmer effort for code that requires dedicated use of the platform and is not portable across platforms.

Moreover, two recent trends in the memory hierarchy--pervasive multicore and pervasive non-volatile memory (flash, and soon phase change memory)--bring new dimensions and new challenges to making effective use of the hierarchy, as well as provide new opportunities.

In the Hi-Spade project, we are developing a hierarchy-savvy approach to algorithm design and systems for these emerging memory hierarchies. That is, we seek a sweet spot between ignorant and (pain)fully aware that:

• Hides what aspects of the hierarchy can be hid,
• Exposes what must be exposed for good performance, and
• Is robust across many platforms and many resource-sharing scenarios.

Our research agenda includes theory (conceptual models, algorithms, analytical guarantees), systems (runtime support, performance tools, architectural features), and applications (databases, operating systems, application kernels).

• Hi-Spade Overview Talk (ppt, 5MB, April 2010)

Publications

---

Note: Papers marked with have ACM Author-izer links. You can download the pdf for free by clicking on the title, even without a subscription to the ACM Digital Library.

Rethinking Database Algorithms for Phase Change Memory  (pdf)
Shimin Chen, Phillip B. Gibbons, Suman Nath
[CIDR '11] Proceedings of the 5th Biennial Conference on Innovative Data Systems Research (CIDR'11), Asilomar, CA, January 2011

Flash in a DBMS: Where and How?  (pdf)
Manos Athanassoulis, Anastasia Ailamaki, Shimin Chen, Phillip B. Gibbons, Radu Stoica
Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 33(4), special issue on data management using modern storage hardware, December 2010

Space Profiling for Parallel Functional Programs
Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons
[JFP] Journal of Functional Programming, 20:5-6, November 2010. Special issue of best papers from ICFP '08

Online Maintenance of Very Large Random Samples on Flash Storage
Suman Nath and Phillip B. Gibbons
[VLDBJ] VLDB Journal, 19(1), 2010. Special issue of best papers from VLDB'08

FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance
Shimin Chen
[SIGMOD '09] Proceedings of the 28th ACM SIGMOD International Conference on Management of Data, Providence, RI, June-July 2009.

Online Maintenance of Very Large Random Samples on Flash Storage
Suman Nath and Phillip B. Gibbons
[VLDB '08] Proceedings of the 34th International Conference on Very Large Data Bases, Auckland, New Zealand, August 2008

Provably Good Multicore Cache Performance for Divide-and-Conquer Algorithms
Guy E. Blelloch, Rezaul A. Chowdhury, Phillip B. Gibbons, Vijaya Ramachandran, Shimin Chen, Michael Kozuch
[SODA '08] Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, January 2008

For additional related publications, see the completed Shared Caching project.

Researchers

---

• Phillip B. Gibbons
• Guy Blelloch (CMU)
• Shimin Chen (now at HP Labs)
• Jeremy Fineman (now at Georgetown)
• Anastasia Ailamaki (EPFL)
• Xiaoning Ding (now at NJIT)

Students

• Manos Athanassoulis (EPFL)
• Aapo Kyrola (CMU)
• Julian Shun (CMU)
• Harsha Vardhan Simhadri (CMU)

Past Collaborators

• Rezaul Chowdhury (when a U.T. Austin grad student)
• Robert Harper (CMU)
• F. Ryan Johnson (when a CMU grad student)
• Michael Kozuch (Intel Labs Pittsburgh)
• Suman Nath (Microsoft Research)
• Ippokratis Pandis (when a CMU grad student)
• Vijaya Ramachandran (U.T. Austin)
• Daniel Spoonhower (when a CMU grad student)
• Radu Stoica (EPFL grad student)
• Kanat Tangwongsan (when a CMU grad student)
• Kaibo Wang (when a Ohio State grad student)
• Xiaodong Zhang (Ohio State)