Parallel Data Structures

The goal of this project is to allow easy design and analysis of parallel algorithms that use data structures. Ideally, we would like to analyze data-structure-based parallel algorithms in the same way as we analyze sequential algorithms that use data structures; that is, simply add the cost of all data structure operations to the cost of the remaining algorithm. However, this simple modularity does not apply to parallel algorithms; therefore, data structures are seldom used in the design of provably good parallel algorithms. We are designing scheduling algorithms that enable this type of analysis modularity to parallel algorithms that use data structures.

Selected Publications

Provably Good Scheduling for Parallel Programs that Use Data Structures through Implicit Batching

Helper Locks for Fork-Join Programs

Real Time Scheduling

Real-time tasks are tasks with deadlines; they are often periodic. These tasks often occur in systems where computers interact with the physical environment or with humans and must react to the change in environment in a timely manner. Examples of applications include autonomous vehicles, industrial process control, and hybrid structural testing. We are engaged in designing platforms that enable parallelism within time tasks while still ensuring that tasks meet their deadlines. Theoretical work involves designing schedulers and other mechanisms that provide guarantees that no deadline will be misses along with high utilization. In addition, we are designing a linux-based concurrency platform that for these tasks.

Selected Publications

Analysis of Federated and Global Scheduling for Parallel tasks

Analysis of Global EDF for Parallel Real-Time Tasks

A Real-Time Scheduling Service for Parallel Tasks

Multi-core Real-Time Scheduling for Generalized Parallel Task Models

For Software Releases, please check the main webpage for the project:
Main project webpage

Scheduling of Streaming Applications

A streaming application consists of a network of modules connected by FIFO channels. When a module fires, it reads data off its input channel, computes on them, and writes data on its output channels; a module is ready to fire when there is enough data on its input channels. This project involves designing scheduling algorithms for streaming applications that provide various kinds of guarantees such as deadlock freedom, few cache misses, or high throughput.

Selected Publications

Cache-Conscious Scheduling of Streaming Applications

Cache-Oblivious Scheduling of Streaming Pipelines

Efficient Deadlock Avoidance for Streaming Computations with Filtering

High-throughput Parallel Architectures such as GPUs and Vector Units

How to design and analyze algorithms for GPUs. We designed the TMM model that enables the asymptotic analysis of algorithms for GPUs.

Selected Publications

Analysis of Classic Algorithms on GPUs

A Memory Access Model for Highly-threaded Many-core Architectures