SPAA

This volume contains the 35 regular papers and eight brief announcements that were selected for presentation at the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'09), held on August 11-13, 2009, in Calgary, Alberta, Canada. The volume also includes the two abstracts of the keynote addresses by Sarita Adve and Bruce Hendrickson and the three abstracts of the presentations by Yahoo! Research, Facebook, and Google. These last three presentations appeared in an invited session on industrial applications. The industrial session and the two keynotes addresses were organized in collaboration with PODC, which this year was co-located with SPAA.

The 43 contributed presentations were selected by the program committee after a preliminary electronic meeting and an all-day phone meeting that took place on April 14, 2009. These presentations were chosen from 129 submissions (114 regular submissions and 15 brief announcements). In keeping with the tradition of previous years, a selection of papers has been invited to appear in a special issue of the Theory of Computing Systems dedicated to SPAA 2009. The paper "Reducers and Other Cilk++ Hyperobjects" by Matteo Frigo, Pablo Halpern, Charles E. Leiserson, and Stephen Lewin-Berlin was selected for the Best Paper Award.

The mix of papers reflects the unique nature of SPAA in bringing together the theory and practice of parallel computing. The technical papers in this volume are to be considered preliminary versions, and authors are generally expected to publish polished and complete versions in archival scientific journals. The brief announcements were chosen based on their perceived interest, with the goal that they serve as foundation for further advances in parallelism in computing. Extended versions of the brief announcements may be published later in other conferences or journals.

The program committee would like to thank the authors who submitted papers and the external reviewers who helped us in the review process. The names of these external reviewers appear later in the proceedings.