Workshop on Theory and Many-Cores (T&MC)

What Does Theory Have to Say About Many-Core Computing?

Friday, May 29, 2009
Kim Engineering Building, Room 1110, University of Maryland, College Park, Maryland

The sudden shift from single-processor computer systems to many-processor parallel computing systems requires reinventing much of Computer Science (CS): how to actually build and program the new parallel systems. Indeed, the programs of many mainstream computer science conferences, such as ASPLOS, DAC, ISCA, PLDI and POPL are heavily populated with papers on parallel computing and in particular on many-core computing. In contrast, the recent programs of flagship theory conferences, such as FOCS, SODA and STOC, hardly have any such paper. This low level of activity should be a concern to the theory community, for it is not clear, for example, what validity the theory of algorithms will have if the main model of computation supported by the vendors is allowed to evolve away from any studied by the theory. The low level of current activity in the theory community is not compatible with past involvement of theorists in parallel computing, and to their representation in the technical discourse. For example, 19 out of 38 participants in a December 1988 NSF-IBM Workshop on Opportunities and Constraints of Parallel Computing in IBM Almaden had theory roots. The lack of involvement of theorists should also concern vendors that build many-core computers: theorists are often the instructors of courses on algorithms and data-structures, and without their cooperation it will be difficult to introduce parallelism into the curriculum.

The main objective of the workshop is to explore opportunities for theoretical computer science research and education in the emerging era of many-core computing, and develop understanding of the role that theory should play in it.


The workshop program includes five invited presentations, five short (10 minute) contributed presentations and a panel discussion.
Please see the workshop program.
Please see titles and abstracts of invited presentations.
Please see titles and abstracts of contributed presentations.

The workshop took place on May 29, as planned. The number of registrants was 82


Workshop Presentations in order of presentation:


Invited Presentations:
Contributed Presentations:
Panel Discussion:
  • In order to promote the objectives of the workshop, the workshop program sought to be as inclusive as possible, representing a broad spectrum of approaches and perspectives. The diversity of the presentations and the Q&A sessions following them did not prepare the audience for the rather broad agreement that emerged in the panel discussion that concluded the workshop.

The panel discussion indicated agreement on the following issues:
  • Education for thinking in parallel as early as possible in one's career is very important. It was clear to all that regardless of how many-core programming will end up looking, CS must take immediate action towards educating a new generation of people about parallelism. This education scope must soon reach the level of parallel computing education available during the 1990s, but should not stop at that. To the extent possible the education for parallelism should be pushed as early as possible in CS education: to lower division undergraduates and K-12 education.
  • Theory is uniquely positioned to guide these education advances.
  • The fact that the convergence to a stable general-purpose many core platform is still under work, should not delay the education enterprise from developing introductory courses on parallelism and widely disseminate their content. This effort should be advanced as a "non-partisan" activity, as it would benefit the whole community, as well as the various vendors in this space.

Sponsors: The University of Maryland Institute for Advanced Computer Studies (UMIACS), Electrical and Computer Engineering Department, and the Center for Computational Thinking, Carnegie-Mellon University.
Organizer: Uzi Vishkin.