Towards a Theory of Universal Speed-Independent Modules

Abstract

Of concern here are asynchronous modules, i.e., those whose activity is regulated by initiation and completion signals with no clocks being present. First a number of operating conditions are described that are deemed essential or useful in a system of asynchronous modules, while retaining an air of independence of particular hardware implementations as much as possible. Second, some results are presented concerning sets of modules that are universal with respect to these conditions. That is, from these sets any arbitrarily complex module may be constructed as a network. It is stipulated that such constructions be speed independent, i.e., independent of the delay time involved in any constituent modules. Furthermore it is required that the constructions be delay insensitive in the sense that an arbitrary number of delay elements may be inserted into or removed from connecting lines without effecting the external behavior of the network.