IRP Banner

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

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

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

Shimin Chen, Anastasia Ailamaki, Manos Athanassoulis, Phillip B. Gibbons, Ryan Johnson, Ippokratis Pandis, and Radu Stoica. TPC-E vs. TPC-C: Characterizing the New TPC-E Benchmark via an I/O Comparison Study. In ACM Sigmod Record, 39(4), December 2010.

Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. Low Depth Cache-Oblivious Algorithms. In Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'10), Santorini, Greece, June 2010.

Shimin Chen, Phillip B. Gibbons, and Suman Nath. PR-Join: A Non-Blocking Join Achieving Higher Result Rate with Statistical Guarantee. In Proceedings of the 29th ACM SIGMOD International Conference on Management of Data (SIGMOD'10), Indianapolis, IN, June 2010.

Suman Nath and Phillip B. Gibbons. Online Maintenance of Very Large Random Samples on Flash Storage. The VLDB Journal, 19(1), 2010. Special issue of best papers from VLDB'08. Preliminary version in Proceedings of the 34th International Conference on Very Large Data Bases (VLDB'08), Auckland, New Zealand, August 2008.

Daniel Spoonhower, Guy E. Blelloch, Phillip B. Gibbons, and Robert Harper. Beyond Nested Parallelism: Tight Bounds on Work-Stealing Overheads for Parallel Futures. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'09), Calgary, Canada, August 2009.

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

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, and Phillip B. Gibbons. Space Profiling for Parallel Functional Programs. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming (ICFP'08), Victoria, British Columbia, Canada, September 2008. Invited to special journal issue of best papers from ICFP'08.

Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. Combinable Memory-Block Transactions. In Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'08), Munich, Germany, June 2008.

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

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



Researchers


Collaborators

Students
  • Harsha Vardhan Simhadri (CMU)
  • Ippokratis Pandis (CMU)
  • Manos Athanassoulis (EPFL)
  • Radu Stoica (EPFL)
  • F. Ryan Johnson (CMU)
Past Collaborators
  • Rezaul Chowdhury (U.T. Austin)
  • Robert Harper (CMU)
  • Michael Kozuch (Intel Labs Pittsburgh)
  • Vijaya Ramachandran (U.T. Austin)
  • Steve Schlosser
  • Daniel Spoonhower (now at Google)