RACES 2012

Workshop on Relaxing Synchronization for Multicore and Manycore Scalability

Theme and Goal of the Workshop

The RACES workshop is a first attempt at bringing a new school of thought to the attention of the computer science community: that of abandoning absolute certainty in favor of scalability and performance when considering parallel computation.
Today, multi core systems are becoming more and more the rule and conventional wisdom has been to scale up software for these systems by reducing synchronization constraints. Amdahl’s law however, implies that even the smallest fraction of inherently sequential code limits scaling. The RACES workshop wants to promote an approach towards scalability for many-core systems by reducing synchronization requirements drastically, possibly to the point of discarding them altogether. This will of course cause us to move from the certain into the merely probable.

By organizing this workshop we want to provoke discussion of languages, data structures, and algorithms that support parallelism by relying on probabilistic approaches. Although some research has already been applied to this idea, there is still a long way to go before we can start talking about a new field of research within computer science. We would like to invite all those that have been exploring non-determinism in a parallel setting - recently or in the past. We do not wish to exclude any avenue of research - one of the results of this workshop will be a first step towards an inventory of existing work in the broadest possible sense. We also invite interested researchers that may not have experience in this domain but feel they can contribute in a meaningful way.

Please consult the call for contributions for further details on how to participate in RACES.

Contact: races@soft.vub.ac.be

Accepted Papers

Call for Participation

Massively-parallel systems are coming: core counts keep rising – whether conventional cores as in multicore and manycore systems, or specialized cores as in GPUs. Conventional wisdom has been to utilize this parallelism by reducing synchronization to the minimum required to preserve determinism – in particular, by eliminating data races. However, Amdahl’s law implies that on highly-parallel systems even a small amount of synchronization that introduces serialization will limit scaling. Thus, we are forced to confront the trade-off between synchronization and the ability of an implementation to scale performance with the number of processors: synchronization inherently limits parallelism. This workshop focuses on harnessing parallelism by limiting synchronization, even to the point where programs will compute inconsistent or approximate rather than exact answers.

Theme and Topics

A new school of thought is arising: one that accepts and even embraces nondeterminism (including data races), and in return is able to dramatically reduce synchronization, or even eliminate it completely. However, this approach requires that we leave the realm of the certain and enter the realm of the merely probable. How can we cast aside the security of correctness, the logic of a proof, and adopt a new way of thinking, where answers are good enough but not certain, and where many processors work together in parallel without quite knowing the states that the others are in? We may need some amount of synchronization, but how much? Or better yet, how little? What mental tools and linguistic devices can we give programmers to help them adapt to this challenge? This workshop focuses on these questions and related ones: harnessing parallelism by limiting synchronization, even to the point where programs will compute inconsistent or approximate rather than exact answers.

This workshop aims to bring together researchers who, in the quest for scalability, have been exploring the limits of how much synchronization can be avoided. We invite submissions on any topic related to the theme of the workshop, pro or con. We want to hear from those who have experimented with formalisms, algorithms, data structures, programming languages, and mental models that push the limits. In addition, we hope to hear from a few voices with wilder ideas: those who may not have reduced their notions to practice yet, but who have thoughts that can inspire us as we head towards this yet-uncertain future. For example, biology may yield fruitful insights. The ideal presentation for this workshop will focus on a grand idea, but will be backed by some experimental result.

Submission

Authors are invited to submit short position papers, technical papers, or experience reports. Submissions may range from a single paragraph to as long as desired, but the committee can only commit to reading one full page. Nonetheless, we expect that in many cases reviewers will read farther than that. Submissions should be formatted according to the ACM SIG Proceedings style and should be submitted via EasyChair in PDF format.

PLEASE NOTE: All submissions (except for those retracted by their authors) will be posted on the workshop website, along with reviews, which will be signed by the reviewers, and a rating assigned by the program committee. Further, the submissions to be presented at the workshop will be selected by a vote of all registered attendees. As well, submissions to be published in an official proceedings will be selected by the program committee. Please see the sections below concerning the rationale and details for this process.

Goals and Outcomes

We will consider the workshop a success if attendees come away with new insights into fundamental principles, and new ideas for algorithms, data structures, programming languages, and mental models, leading to improving scaling by limiting synchronization, even to the point where programs will compute inconsistent or approximate rather than exact answers. The goal of this workshop is both to influence current programming practice and to initiate the coalescence of a new research community giving rise to a new subfield within the general area of concurrent and parallel programming. Results generated by the workshop will be made persistent via the workshop website and possibly via the ACM Digital Library.

The RACES 2012 Review Process and Workshop Presentation Selection Process

Technology has changed the economic tradeoffs that once shaped the reviewing process. It has become cheap and easy to share submissions, reviews and the preferences of the attendees. What remains scarce is the number of hours in a day, and as a consequence the time we have in our workshop in which to learn and share with each other. I believe that this change in the balance of factors affords us the opportunity to significantly improve the review and selection processes.

Sadly, all too often, those who spend their precious time attending a workshop are not served as well they could be with respect to enlightenment, thought provoking discussions, and being challenged by new ideas. The fault lies not in the people who generously donate their time to serve on program committees and do external reviews. Rather, the fault lies in the process itself. The very notion of acceptance by committee forces us to boil a rich stew of reactions, insights, and opinions, down to a single carrot. As a result, it is common for PC members to come away from a meeting feeling that either some fraud will be perpetrated on the audience by a fundamentally flawed paper, or, more often, feeling that a sin of omission will be committed on the audience by the suppression of a significant but controversial new idea. Sometimes instead of a carrot we get a lump of gristle.

There are other, lesser, flaws in this process. Although reviewer anonymity protects negative reviewers from resentment and reprisal, all too often it prevents an open debate that would promote mutual understanding. Further, in some cases anonymity allows a reviewer to cast aspersions on authors without being accountable. Finally, we fail to take maximal advantage of the time and effort spent in creating insightful reviews when we withhold them from the audience. Attendees and readers could benefit from expert reactions as they try to glean the wisdom embedded in the authors’ papers.

In this workshop, we have an opportunity to try a different process, one that we hope will serve all parties better: All reviews will be signed, all submissions and reviews will be posted on the web (unless an author chooses to retract a submission), and the attendees will be the ones selecting which papers will be presented.

Review Process Details

At least three committee members will review each submission, and each review will be signed. Once all the reviews for a submission are in, they will be sent to the author, who can decide to retract the paper if so desired. Then, all submissions (except any that are retracted) will be posted on the workshop website, along with all reviews and a net score determined for each submission by the program committee.

At this point, prior to the workshop, all registered attendees will be invited to read the submissions and the reviews, and vote on which of the papers they want to see presented. Of course, an attendee who so wishes will be free to merely vote according to the recommendation of the PC, or to not vote and to accept the wisdom of the rest of the attendees. But the important point remains: it will be those who will be spending the time in the room who get to decide how that time is spent. Please note that a submission being posted on the workshop website and/or presented at the workshop are not intended to constitute prior publication for purposes of publishing in other workshops, major conferences, or journals.

This process is a grand experiment, designed to exploit the technologies we Computer Scientists have created, in order to better serve the advancement of Computer Science. We hope that its potential excites you as much as it excites us!essay writer

The RACES 2012 Published Proceedings Paper Selection Process

We understand that many submitters may want to publish their paper in an official proceedings in addition to having it posted on the workshop website. In order to satisfy that desire, we will publish a proceedings via the ACM Digital Library. To satisfy ACM DL selectivity requirements, a separate and more conventional process will be employed for selecting papers to be included in the published proceedings: Even though all submissions will be posted on the workshop website (unless retracted by the author), the program committee will select a smaller number of papers where to buy an essay online to be included in the published proceedings based on the signed and posted reviews. Authors of the selected papers will be asked to submit revised and extended papers mid-November, taking into account the reviews and the publisher’s guidelines. Page limits for the revised and extended papers to be included in the published proceedings are anticipated to be 10 pages for research papers, and 5 pages for position papers. Please note that inclusion in the ACM Digital Library published proceedings may well be considered to be a prior publication for purposes of publication in other workshops, major conferences, or journals. For that reason, authors may choose to decline to have their submission included in the published proceedings, even if it was presented at the workshop.

At RACES’12, we want you, the attendees, to have the opportunity to choose how your time is spent. See the Call for Participation for an explanation.

Below, you will find each submission, the program committee’s reviews, and a default time allocation based on those reviews (the allocation includes both presentation and discussion time). In addition, there are additional time slots proposed for general discussion. Please vote by adjusting the sliders to indicate the allocation that you feel would maximize your return on the time you will be spending in the workshop. When the sliders are set to your satisfaction, please hit the Submit Vote button at the bottom of the page.

We plan to start with a brief introduction during which each attendee will concisely introduce him- or herself: name, institution, and one sentence about position or interest. If it garners sufficient votes, we’ll also include an introductory lightning session in which each presenter will present a strictly limited 30-second sneak preview (cf. CHI “Madness”).

If you will be attending our workshop, please help shape it to best serve you — vote today! Questions?

Thank you,

David Ungar and the RACES’12 organizers.