PROBE on Parallel Thinking

Organized by Guy Blelloch

With the advent of chip multiprocessors and the apparent end of exponential improvements in clock speeds, parallelism is set to become pervasive at all levels of computation.  This trend is likely to eventually lead to a scenario in which parallel programming will become predominant and sequential programming will be a special case. Are we ready for this change?  Short-term solutions based on introducing some libraries or threading constructs along with training on how to convert sequential code to use these is unlikely to be sufficient in the long term.  Instead the change will likely require a more fundamental rethinking that permeates the programmers' methodologies from early stages of algorithm design to the construction and maintenance of complete systems.  This will require developing a form of "parallel thinking".

As part of the Center on Computational Thinking we propose to run a PROBE (PROBlem-oriented Exploration) on "Parallel Thinking".  The PROBE will study how to make parallelism a natural part of the way we think about algorithms, systems, programming, and applications. Topics of interest include:

• What are the key concepts in parallel programming?  How do these map onto different types of applications?  How are they supported by the runtime and hardware?  How do they scale?
• What are the right algorithmic models for thinking about and analyzing parallel algorithms?  How do we tie them with programming models?  What are the key techniques in designing parallel algorithms?
• How can parallelism be used in non-traditional ways, e.g., to help achieve robustness?  What sort of non-traditional architectures might become effective in the future.

Many of these concepts in parallel thinking have already been explored, and perhaps need to be revisited, others surely need to be developed.  The emphasis of the PROBE will be on well-founded long-term solutions involving high-level abstractions that minimize the end-to-end cost of developing and maintaining parallel software.

The PROBE will start with a workshop that brings together researchers who are working across a variety of topics in parallelism.  This will include researchers in parallel algorithms, in programming languages, in software engineering and in architecture.  The focus of the workshop will be on what are the core long-term ideas of parallelism and will be used to help guide research topics to be explored in more detail.  Such research topics could include comparing programming constructs, developing parallel algorithms using different models, or developing new concurrency models.  A group of Carnegie Mellon faculty and students will collaborate with Microsoft researchers and others exploring these topics.  There will also be an educational component of the PROBE that will develop a proposed curriculum based on what are determined to be the core ideas of parallel thinking that should be taught to our students.  This would include an outline of where these ideas can be incorporated into the undergraduate and graduate course sequences.  We would plan a second workshop after a year.  The topic of the second workshop would be more focused on the particular research topics being explored by the participants.

Parallel Thinking Seminar Series 2008