Notes from RC’05
First International Workshop on Reversible Computing
Ischia, Italy, May 4-6, 2005-05-07

The workshop was a rousing success, at least from my perspective, and based on the feedback I received from many participants. I think that we achieved what we set out to do, which was to bring together different segments of the reversible computing community, to catch up on recent activity in each others’ areas, as well as to discuss issues of goals and strategy for the field overall.

The schedule of speakers was full; only three of the scheduled speakers had to cancel due to scheduling or logistical difficulties (Porod, Williams, and Averin) and, although they were missed, this was not a fatal problem, since it meant that the remaining speakers’ talks could be a bit less compressed. The talks were of good quality and the material seemed fresh and interesting to many participants. There was a good level of audience participation.

The keynote speaker (Charles Bennett) was unable to attend in person, but he did us the favor of pre-recording a very interesting talk which was played back during the workshop, and he was able to speak with us briefly over the internet before the panel session, although unfortunately the VoIP connection proved too unreliable to allow him to fully participate and we had to fall back on occasional text messages.

I am posting the slides of the talks (including Bennett’s) on the website; speakers are requested to please email their PowerPoint and/or PDF files to mpf@eng.fsu.edu. Photographs of the meetings (or other activities) are also requested.

Particular points of interest were a couple of ideas that were discussed during the panel session (and in various smaller discussions) for ways to raise the world’s awareness of the field. The most widely discussed ideas were:

Start a low-power computing contest.
Select a new and more intuitive name for the field.

As well, we discussed plans for next year’s workshop. Some more detailed notes are below.

Notes on Discussions

Low-Power Computing Competition

To encourage more students to learn about the low-power computing field, and more researchers to tackle its challenges, and also to provide better publicity for the field’s promise, attendees expressed broad support for the idea of starting a design competition, where the contestants would be asked to design the most energy-efficient design meeting certain constraints. Specific elements of this idea that were discussed included:

The contest will be managed by a committee of members of the low-power community, including members of the reversible computing community in particular.
The contest should be advertised widely among students and in industry.
The contest should be structured as a low-power computing contest, not as a reversible computing contest specifically. That is, any manufacturable technology may be utilized by contestants. Our position is that reversible computing ought to eventually begin winning the contest fairly, if sufficient effort is put into its development. The very existence of the contest should help to provide an impetus for this development.
We could raise funds for the contest from industry and from individual donations. Possibly also with grants from organizations such as SRC, NSF, or other national agencies.
We could manage the contest fund through a non-profit organization or a university account.
We could solicit industry representatives to sit on the contest committee to help shape contest details and judge the results.
Provide contestants with design requirements including fixed upper-bound constraints on design cost or complexity by some measure (e.g., number of devices, or estimated layout area), total available energy, enclosure geometry, execution time, and available fabrication technologies.
Specify to contestants the computational problem to be solved.
The problem should be specified precisely, by giving an algorithm and a simple reference implementation for the function to be computed in some well-defined programming language or behavioral hardware-description language.
The contestants’ task will be to build a system that produces the exact same output for any given input as the reference implementation, while remaining within design constraints. (Timing of results will probably not be important as long as they are provided within the time limit.)
Contestants are not required to use the exact same algorithm as the one provided, as long as the I/O relation (function computed) is exactly the same.
However, the problem class chosen should be such that it’s unlikely that there will be algorithms found that are dramatically (e.g., asymptotically) more efficient than the most straightforward ones. (The contest should be about implementation technology, not about algorithms.)
The problem class should be scalable; that is, it should include problem instances of a wide range of complexity.
Designs will be compared based on what is the maximum size problem instance that they can solve while remaining within the design constraints.
The problem should be compute-intensive, as opposed to I/O dominated or memory-intensive.
Problems should be highly parallelizable.
Problems should require tightly-coupled communication between parallel processing locations.
The specific inputs that will be used at evaluation time will not be known to contestants in advance of design delivery, to prevent hard-coding of results.
Designs will be delivered to the judges as project files for some fairly standard and widely-available simulation tool.
Process and device-model libraries defining the technologies and devices that are available to contestants will be specified.
Novel devices can be added to the library in future iterations of the contest as those devices become increasingly well-specified.
Designs will be self-contained in a black box, and must include both logic devices and power supplies
Energy input to the system is given only (say) in the form of a DC battery with a finite energy content.
Data input is provided in a ROM that can be adiabatically queried.
Designs will be evaluated by simulating them.
Designs will be simulated on a variety of input sizes, while measuring design complexity and checking for correct output.
The simulation round could be just an initial qualification round; i.e., the top n designs from this round could be allowed through to a subsequent step of the competition.
One or more of the best designs as determined by simulation will be fabricated (this can be considered part of the prize for the contest).
After fabrication, designs may be empirically re-evaluated in a second round to determine an overall winner.
The outcome of the contest should be widely publicized, to gain exposure for the winning technology.
Each year (or within a given year) the contest could involve a different computational problem for variety (since different technologies may win at different applications).
Different combinations of design constraints may also be tested each year, since different technologies may win under different constraints.
The contest could include several categories of problems, including problems that are more memory-intensive or I/O-intensive. Different technologies might win in different categories.
Some sort of additional award could be given for important new theoretical developments or for particularly creative new ideas. These awards would be subjectively evaluated by judges.

Consider the above description an RFC (Request for Comments) on the contest idea to the community. What does everyone think about these ideas? Any suggestions for ways to further improve the contest?

Renaming the Field?

One thing I have observed is that the very name “reversible computing” hurts the field. This is because the first thing people think when they hear this is a skeptical, “How can going backwards possibly help you run forwards faster?” “Adiabatic” computing is little better, because even if they know what adiabatic means, they immediately think “How can running slowly help you run faster?”

In fact, we in the field know that running relatively slowly, alternatingly forwards and backwards, does help you run forwards faster, when power dissipation is a constraint and you parallelize highly, or use devices whose base speed is very fast. But it takes some time to explain how this works. People’s first impression is that the idea makes no sense, and often they don’t stick around long enough to learn more about it.

So, since first impressions matter, the suggestion was raised that the field needs a new name. Suggestions that were heard at the meeting included items on the following list. Beside each one, I have listed at least one possible problem with each name. Other suggestions are invited.

Reversible computing (not obvious to people why it’s a good thing)
Conservative computing (political connotations)
Adiabatic computing (baffles laypeople, sounds slow to experts)
Non-dissipative computing (exaggerated, a mouthful)
Zero-energy computing (exaggerated)
Energy-conserving computing (energy conservation is a law of physics)
Asymptotically … computing (big words, a mouthful)
Quasi-… computing (sounds vague)
Ballistic computing (a bit obscure, evokes ICBMs)
Inertial computing (sounds massive and slow)
Computational coasting (a bit awkward)
Computational gliding (awkward)
Smooth computing (informal-sounding)
Efficient computing (non-specific)
Energy-efficient computing (still somewhat non-specific)
Green computing (evokes hard-core environmentalism)
Frugal computing (evokes coupon-clipping)
Better computing (non-specific, a bit immodest)
Isentropic computing (highly technical)
Frictionless computing (exaggerated)
Cool(er) computing (informal sounding, somewhat inaccurate)
Backwards computing (sounds like a step backwards)
Sustainable computing
Recovery computing

Please email your votes for your favorites, or additional suggestions to mpf@eng.fsu.edu. I will update this list as I receive your input.

Plans for Next Year’s Workshop

We were invited by the Computing Frontiers organizers to return to their conference next year, and/or the year after. However, we did not yet firmly commit to do so. There are several reasons why we might not want to hold the workshop under CF every year:

We need to reach out to other communities besides just the CS-type people at Computing Frontiers (e.g., electrical engineers, device physicists)
High cost of ACM sponsorship and conference venue (high registration fees)
Little support for invited speakers (so far, SIGMicro only agreed to waive fees for the organizer and keynote speaker next year if participation is above 6-8 people)
Long, expensive travel for US participants (hold meeting in US on alternate years?)
Inability for us to choose the date of the workshop
Inflexibility of ACM publication schedules (early due date on final papers)
Lack of printed proceedings
No vehicle for turning conference publications into journal articles

However, running the conference under CF also had certain advantages:

Logistical details taken care of by CF organizers
CF program committee contributed to paper reviewing process
Little financial risk for workshop organizers (except own travel)
Nice venue (Continental Terme Hotel, Ischia) & amenities (banquet, etc.)

My tentative suggestion would be that we should try to hold the next workshop in the US, and run it under the umbrella of some IEEE conference, so as to better reach out to the electrical engineering community next time. Then, we could potentially return to CF and/or Europe during a subsequent year, if we wished. Perhaps we could cycle between two or more venues.

There is also the question of whether we should hold the workshop every year at all, or instead only every two years or so, so as to give the participants more time to come up with interesting new results.

I would be happy to hear any suggestions or feedback on these issues from the community.