UTCS ACT Colloquia - Kunal Agrawal, Washington University in St. Louis, "Provably Good Schedulers for Parallel Computations"

Contact Name: 
Vijaya Ramachandran
GDC 4.516
Feb 14, 2014 2:00pm - 3:15pm

Signup Schedule: http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Host:  Vijaya Ramachandran

Talk Abstract: 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: (1) 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.  (2) 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.