Guy E. Blelloch's Home Page

Guy E. Blelloch

U.A. and Hellen Whitaker University Professor
Department of Computer Science
Carnegie Mellon University

Email: blelloch at cs dot cmu dot edu
Phone: (412) 268-6245
Office: GHC 9211

Other Contact Information

My research has largely been in been in the area of parallel algorithms and data structures. This includes an interest in programming language support for them.

Some talks

  • VERLIB: Concurrent Versioned Pointers (PPoPP, 2024)
  • Deterministic and Low-Span Work-Efficient Parallel Batch-Dynamic Trees (SPAA, 2024)
  • Are Parallel Algorithms Ready for Prime Time (SPAA Parallel Computing Award Talk, 2023)
  • Should we Teach Parallelism Throughout our Data Structures and Algorithms Courses? (Dagstuhl, 2023)
  • Algorithms Are Algorithms, Some With More Parallelism than Others (Keynote, Edupar, 2023)
  • Parallel Minimum Cuts (Invited Talk, HALG, 2022)
  • Algorithms for Non-Volatile RAM (Invited Talk, APOCS, 2022)
  • Is Asymptotic Cost Analysis Useful for Developing Practical Parallel Algorithms? (IPDPS, Babbage Award Talk, 2021)
  • Batch Dynamic Algorithms (Dagstuhl, 2021)
  • Some Sequential Algorithms Are Almost Always Parallel (Keynote, SPAA and PODC, 2017)
  • Parallel Algorithms Come of Age (CMU Qatar, 2017)
  • Parallel Algorithms and Big Data for All (Karlsruhe, 2015)
  • Cost Models based on the Lambda Calculus (INRIA, 2014)
  • Big Data on Smallish Machines (Berkeley, 2013)
  • Internally Deterministic Parallel Algorithms (WODET, 2013)
  • Problem Based Benchmarks: and Their Role in Parallel Algorithms (ALENEX, 2012)
  • Functional Parallel Algorithms (ICFP, 2010)
  • Parallel Cache-Oblivious Algorithms (Max Planck Institute, 2010)
  • Parallel Thinking (PPoPP 2009).
  • Parallel Scheduling: Theory and Practice (IBM Watson, 2008).

    • Recent(ish) PhD Students

  • Magdalen Dobson
    Current student working on Nearest Neighbor Problems
  • Hao Wei
    General Techniques for Efficient Concurrent Data Structures, 2023
    PostDoc at MIT, soon to be Assistat Professor at the University of British Columbia
  • Daniel Anderson
    Parallel Batch-Dynamic Algorithms: Dynamic Trees, Graphs, and Self-Adjusting Computation, 2023
    Assistant Teaching Professor at CMU
  • Ziv Scully
    A New Toolbox for Scheduling Theory, 2022
    SIGMETRICS Doctoral Dissertation Award
    Assistant Professor at Cornell
  • Laxman Dhulipala
    Provably Efficient and Scalable Shared-Memory Graph Processing, 2020
    SCS Doctoral Dissertation Award, Honorable Mention
    Assistant Professor at University of Maryland
  • Naama Ben-David
    Theoretical Foundations for Practical Concurrent and Distributed Computation, 2020
    PODC Doctoral Dissertation Award
    Assistant Professor Technion, Israel
  • Yihan Sun
    Join-based Parallel Balanced Binary Trees, 2019
    Assistant Professor UC Riverside.
  • Yan Gu
    Write-efficient Algorithms, 2018
    Assistant Professor UC Riverside.
  • Julian Shun
    Shared Memory Parallelism Can Be Simple, Fast, and Scalable, 2015
    ACM Doctoral Dissertation Award
    Associate Professor MIT
  • Aapo Kyrola
    Large-scale Graph Computation on Just a PC, 2014
    Co-founder Sulake and Moves (acquired by Facebook)
  • Harsha Simhadri
    Program-Centric Cost Models for Locality and Parallelism, 2013
    Microsoft Research
  • Kanat Tangwongsan
    Efficient Parallel Approximation Algorithms, 2011
    SCS Doctoral Dissertation Award
    Professor Mahidol University, Thailand
  • Ruy-Ley Wild
    Programmable Self-Adjusting Computation, 2010
  • Daniel Spoonhower
    Scheduling Deterministic Parallel Programs, 2009
    Co-founder Lightstep.
  • Maverick Woo
    Finger Searching on Degree-Balanced Search Trees, 2009
    System Scientist CMU
  • Virginia Vassilevska Williams
    Efficient algorithms for path problems in weighted graphs, 2008
    Professor MIT
  • Daniel Golovin
    Uniquely Represented Data Structures with Applications to Privacy, 2008
    Google
  • Srinath Sridhar
    Algorithms for Analyzing Intraspecific Sequence Variation, 2007
    CEO & Co-Founder at regie.ai
  • Daniel Blandford
    Compact Data Structures with Fast Queries, 2006
    Facebook
  • Umut Acar
    Self-Adjusting Computation, 2005
    Associate Professor CMU
  • Perry Cheng
    Parallel, Real-Time Garbage Collection, 2001
    SCS Distinguished Dissertation Award
    Co-founder and VP Eng. at Nimbella (Acquired by Digital Ocean)

    • Recent(ish) Awards

  • SPAA Parallel Computing Award, 2023
  • Allen Newell Award for Research Excellence, 2023
  • Best Research Paper Runner-up VLDB 2023 for
    ``PIM-tree: A Skew-resistant Index for Processing-in-Memory''
  • IEEE Charles Babbage Award, 2021
  • Best paper PPoPP 2022 for
    ``Lock-free locks revisited.''
  • Best paper SPAA 2021 for
    ``Parallel Minimum Cuts in $O(m \log^2n)$ Work and Low Depth.''
  • Oustanding paper SPAA 2020 for
    ``Optimal Parallel Algorithms in the Binary-Forking Model.''
  • Distinguished paper PLDI 2019 for
    ``Low-latency graph streaming using compressed purely-functional trees.'' Best paper SPAA 2018 for
    ``Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable.''

    • I teach the following courses.

  • 15-852: Parallel and Concurrent Algorithms (Spring 24)
  • 15-210: Parallel and Sequential Data Structures and Algorithms (Fall 23)
    •

    I maintain the SCS faculty information page and was chair of the building committee for our new computer science building, the Gates and Hillman Centers. I also have a page on the ill fated Spine Line.