Seminar on Provably good scheduling for parallel programs
April 7, 2014 – 15:00 – Retis Lab
In recent years, parallel computing has become ubiquitous, as modern computation platforms, from smartphones to network routers and personal computers to large clusters and clouds, each contain multiple processors. On these parallel computers, scheduling decisions --- what happens when and where --- has a large impact on performance. This talk will present recent research on scheduling algorithms that provide provable guarantees on the performance of parallel programs that they schedule. In particular, the talk will cover 2 main topics:
- Data structures are an important component in designing sequential algorithms. However, using data structures within parallel algorithms while guaranteeing speedup is challenging due to contention between concurrent operations and the resulting slowdown. Amortized data structures, in particular, are extremely difficult to use from within parallel algorithms. This talk will present BATCHER, a scheduling algorithm that allows parallel algorithms to use data structures while still guaranteeing speedup to the algorithm.
- Streaming computations represent an important class of parallel applications. We consider the problem of scheduling streaming applications to minimize the number of cache misses incurred by the application. We show that for a large class of streaming applications, we can reduce this problem to a graph partitioning problem. Given a good partition, we describe a runtime strategy for scheduling streaming graphs and prove that this runtime strategy is asymptotically optimal with constant factor cache-augmentation.
Kunal Agrawal (personal page) an assistant professor at Washington University in St. Louis. She is interested in a variety of problems related to parallel computing including scheduling algorithms, synchronization mechanisms, transactional memory, real-time scheduling and caching