Implicitly Parallel Architectures Group

The IPA group is working on techniques to automatically extract the implicit parallelism known to exist (as of yet unexploited) in sequential programs, through the Polyflow Architecture. The proposed architecture leverages key insights with respect to speculative inter-thread communication mechanisms and automatic, speculative thread identification using control dependence analysis.

This work is motivated by the recent trends in microprocessor architecture. Driven by technological challenges, high-performance processor architecture has moved towards designs that feature multiple cores per chip and multiple threads per core. Multi-core and multi-threaded designs deliver peak instruction throughput that scales with Moore's law and they provide better power/performance tradeoffs than monolithic superscalar designs given the same number of transistors. Additionally, multi-core designs leverage replication to amortize design and verification costs. Multi-core processors are simply easier and cheaper to design than monolithic designs of similar size or peak performance.

While multi-core designs solve technological scaling problems, they introduce new challenges for software designers. Multi-core and multi-threaded designs require multi-threaded software. While there are domains where finding adequate threads to run concurrently is “easy,” (perhaps in web services, database query processing, scientific computing, graphics, gaming, or signal processing), software vendors in the general purpose domain do not find multi-threaded programming cost effective. Multithreaded programs are non-deterministic, making reproducible debugging difficult, and have more bugs (race conditions, live-locks, deadlocks) than sequential programs with the same functionality. When coupled with the throughput limits imposed by Amdahl's law, these increased testing, debugging and verification costs make explicitly multithreaded models unattractive.

By automatically parallelizing sequential (but parallelizable) applications “under the hood” (presenting sequential behavior to the external world), the Polyflow Architecture aims to form a bridge between the conflicting requirements of sequential programming models (for productivity and maintainibility reasons), and the need to parallelize appllications (to get high performance on multi-core and multi-threaded architectures).