Many computer engineers start from the premise that a computer needs to be perfectly deterministic, and to give precisely the same result when run twice from the same starting conditions.
Therefore, there appears to be a problem with asynchronous machines in which timing errors can occur. As usually understood, the term asynchronous when applied to computing machines means that they have, nevertheless, local timing feedback loops to restore determinism and are not truly asynchronous in the sense we use in this paper. We are concerned with timing events which happen truly randomly with respect to each other and can give rise to uncorrected race problems.
As there are many computationally complex chaotic systems which it is desired to model to some level of accuracy, we contend that it may not be necessary to construct perfectly deterministic machines for this purpose; and that there may be speed and power advantages in relaxing the strong condition on deterministic behaviour.
This paper is divided into three parts. It consists largely of speculative thoughts that are at an early stage of development, and are therefore appropriate for a conference presentation.
First we identify the sources of unavoidable uncertainty in asynchronous digital parallel computers that use arbiters [1]. We estimate the rate of such errors per arbiter, supporting our remarks with experimental evidence [1] [2] on metastability in standard flip-flops. We give an estimate of machine performance in terms of its unavoidable [6] arbitration error rate. There are a number of papers [4] [5] [7] which discuss the probability of errors in arbiters, and schemes have been proposed [3] to try to circumvent this problem. We suggest that these schemes have overheads in terms of speed and processing power. So we try to identify uses for machines containing arbitration errors.
Second, to this end, we define a state vector (for a large asynchronous digital parallel machine) whose dynamics are well approximated by the time evolution of a continuous variable of the kind found in classically chaotic systems. We hypothesise the conditions under which small errors in this state vector, which unavoidably arise because of the arbitration problems described earlier, grow with positive Lyapunov exponents along certain directions in machine space. Because the machine is finite, any such positive exponents will necessarily give rise to the presence of (possibly chaotic) attractors and repellers.
Third, we consider whether such uncertainty is desirable or not; whether it can be deliberately engineered or deliberately avoided; and whether the conclusions arrived at have applicability to largely synchronous parallel machines or to parallel analogue machines such as real-life neural systems.