Guy E. Blelloch Professor Department of Computer Science Carnegie Mellon University Email: blelloch at cs dot cmu dot edu Phone: (412) 268-6245 Fax: (412) 268-5576 Office: GHC 9211 Other Contact Information

Research:

Some recent talks

Parallelism

Benchmarking Parallel Algorithms. We are developing a benchmark suite of parallel algorithmic problems for testing machines and programming paradigms. The ideas is that they will be defined in terms of the interface instead of the code so they can be compared across machine types and programming paradigms.
Cache efficient parallel algorithms. We have been developing cost models, algorithms, and schedulers for taking advantage of locality on parallel cache hierarchies without worrying about details of the machine.
Synchronization and concurrent algorithms. We are looking into the idea of adding transactions on individual memory blocks to the memory system and how this can be used to simplify many concurrent algorithms. We have also looked into the idea "room-synchronizations".
Thread Scheduling. We are developing scheduling dynamic parallel languages and studying how they affect time, memory and cache performance.

Data structures and algorithms

Self-adjusting Computation. The idea is to keep track of dependencies while executing an algorithm so that you can go back, change history, and propagate the change to the output.
Computational Biology: algorithms for phylogenetic tree construction. We have been looking at algorithms that generate trees with maximum-parsimony.
Uniquely Represented Data Structures. Data structures that only depend on their contents and not the order of insertion or deletion have applications in security and concurrency.

Algorithms for Multiprocessor Garbage Collection. The goal here is to bound the wait time for a GC while also bounding the memory required.
The NESL Language
Provably Efficient Language Implementations
Compact Data Structures. We look at how to represent graphs, meshes, indices and sets with a number of bits that are asymptotically optimal and access/update times that are also asymptotically optimal.
Parallel Algorithms including work on Delaunay Triangulation, Treaps, and Sorting.
Other: Pipelining with Futures, Multibank Memory Systems.

You can try our animations of parallel algorithms. These were written in NESL and converted to JAVA using our NESL-to-Java-applet translator.

Teaching:

15-210: Parallel and Sequential Data Structures and Algorithms (Fall 11)
15-853: Algorithms in the Real World (Fall 10)
15-492: Parallel Algorithms (Spring 09)