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



Publications


Note: Papers marked with ACM logo 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.

ACM DL Author-ize service Brief Announcement: The Problem Based Benchmark Suite
Julian Shun, Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Aapo Kyrola, Harsha Vardhan Simhadri, Kanat Tangwongsan
[SPAA '12] Proceedings of the 24th ACM symposium on Parallelism in algorithms and architectures, Pittsburgh, PA, June 2012

ACM DL Author-ize service BWS: Balanced Work Stealing for Time-sharing Multicores
Xiaoning Ding, Kaibo Wang, Phillip B. Gibbons, Xiaodong Zhang
[EuroSys '12] Proceedings of the 7th ACM european conference on Computer Systems, Bern, Switzerland, April 2012

ACM DL Author-ize service Internally Deterministic Parallel Algorithms can be Fast
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Julian Shun
[PPoPP '12] Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming, New Orleans, LA, February 2012

ACM DL Author-ize service MaSM: Efficient Online Updates in Data Warehouses
Manos Athanassoulis, Shimin Chen, Anastasia Ailamaki, Phillip B. Gibbons, Radu Stoica
[SIGMOD '11] Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, Athens, Greece, June 2011

ACM DL Author-ize service Scheduling Irregular Parallel Computations on Hierarchical Caches
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons, Harsha Vardhan Simhadri
[SPAA '11] Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, San Jose, CA, June 2011

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

ACM DL Author-ize service Low Depth Cache-oblivious Algorithms
Guy E. Blelloch, Phillip B. Gibbons, Harsha Vardhan Simhadri
[SPAA '10] Proceedings of the 22nd ACM symposium on Parallelism in algorithms and architectures, Santorini, Greece, June 2010

ACM DL Author-ize service PR-join: A Non-blocking Join Achieving Higher Early Result Rate with Statistical Guarantees
Shimin Chen, Phillip B. Gibbons, Suman Nath
[SIGMOD '10] Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, Indianapolis, IN, June 2010

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

ACM DL Author-ize service Beyond Nested Parallelism: Tight Bounds on Work-stealing Overheads for Parallel Futures
Daniel Spoonhower, Guy E. Blelloch, Phillip B. Gibbons, Robert Harper
[SPAA '09] Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, Calgary, Canada, August 2009

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.

ACM DL Author-ize service Space Profiling for Parallel Functional Programs
Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons
[ICFP '08] ACM SIGPLAN Notices - ICFP '08, Victoria, British Columbia, Canada, September 2008

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

ACM DL Author-ize service Combinable Memory-block Transactions
Guy E. Blelloch, Phillip B. Gibbons, S. Harsha Vardhan
[SPAA '08] Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, Munich, Germany, June 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)