Parallel program and asynchronous circuit design

Abstract

Asynchronous circuit design is a beautiful application area for any formalism that can reason about parallelism. By means of two small, but challenging, exercises we illustrate the similarities and differences between parallel program and asynchronous circuit design. The exercises are simple to state and have many solutions, which are sometimes surprisingly efficient. They all illustrate many aspects of asynchronous circuit design. For each exercise we present several solutions, which are analyzed with respect to delay assumptions, safety, progress, and performance issues. We also mention some open problems.