Self-Timed Control of Concurrent Processes

'Et moi ... ~ si j'avait su comment en revenir. One service mathematics has rendered thl je n'y serais point aile: human race. It has put common sense back where it belongs. on the topmost shelf nexl Jules Verne to the dusty canister labelled 'discarded non· The series is divergent; therefore we may be sense'. Eric T. Bell able to do something with it O. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and non· Iinearities abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and fO! other sciences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One service topology has rendered mathematical physics .. .'; 'One service logic has rendered com· puter science ... .'; 'One service category theory has rendered mathematics .. .'. All arguably true. And all statements obtainable this way form part of the raison d'etre of this series.

1 Introduction.- 2 Asynchronous processes and their interpretation.- 2.1 Asynchronous processes.- 2.1.1 Definition.- 2.1.2 Some subclasses.- 2.1.3 Reposition.- 2.1.4 Structured situations.- 2.1.5 An asynchronous process as a metamodel.- 2.2 Petri nets.- 2.2.1 Model description.- 2.2.2 Some classes.- 2.2.3 Interpretation.- 2.3 Signal graphs.- 2.4 The Muller model.- 2.5 Parallel asynchronous flow charts.- 2.6 Asynchronous state machines.- 2.7 Reference notations.- 3 Self-synchronizing codes.- 3.1 Preliminary definitions.- 3.2 Direct-transition codes.- 3.3 Two-phase codes.- 3.4 Double-rail code.- 3.5 Code with identifier.- 3.6 Optimally balanced code.- 3.7 On the code redundancy.- 3.8 Differential encoding.- 3.9 Reference notations.- 4 Aperiodic circuits.- 4.1 Two-phase implementation of finite state machine.- 4.1.1 Matched implementation.- 4.2 Completion indicators and checkers.- 4.3 Synthesis of combinatorial circuits.- 4.3.1 Indicatability.- 4.3.2 Standard implementations.- 4.3.2.1 Minimum form implementation.- 4.3.2.2 Orthogonal form implementation.- 4.3.2.3 Hysteresis flip-flop-based implementation.- 4.3.2.4 Implementation based on “collective responsibility”.- 4.4 Aperiodic flip-flops.- 4.4.1 Further discussion of flip-flop designs.- 4.4.1.1. RS-flip-flops.- 4.4.1.2 D-flip-flops.- 4.4.1.3 T-flip-flops.- 4.5 Canonical aperiodic implementations of finite state machines.- 4.5.1 Implementation with delay flip-flops.- 4.5.2 Implementation using flip-flops with separated inputs.- 4.5.3 Implementation with complementing flip-flops.- 4.6 Implementation with multiple phase signals.- 4.7 Implementation with direct transitions.- 4.8 On the definition of an aperiodic state machine.- 4.9 Reference notations.- 5 Circuit modelling of control flow.- 5.1 The modelling of Petri nets.- 5.1.1 Event-based modelling.- 5.1.2 Condition-based modelling.- 5.2 The modelling of parallel asynchronous flow charts.- 5.2.1 Implementation of standard fragments.- 5.2.2 A multiple use circuit.- 5.2.3 A loop control circuit.- 5.2.4 Using an arbiter.- 5.2.5 Guard-based implementation.- 5.3 Functional completeness and synthesis of semi-modular circuits.- 5.3.1 Formulation of the problem.- 5.3.2 Some properties of semi-modular circuits.- 5.3.3 Perfect implementation.- 5.3.4 Simple circuits.- 5.3.5 The implementation of distributive and totally sequential circuits.- 5.4 Synthesis of semi-modular circuits in limited bases.- 5.5 Modelling pipeline processes.- 5.5.1 Properties of modelling pipeline circuits.- 5.5.1.1 Pipelinization of parallel fragments.- 5.5.1.2 Pipelinization of a conditional branch.- 5.5.1.3 Transformation of a loop.- 5.5.1.4 Pipelinization for multiply-used sections.- 5.6 Reference notations.- 6 Composition of asynchronous processes and circuits.- 6.1 Composition of asynchronous processes.- 6.1.1 Reinstated process.- 6.1.2 Process reduction.- 6.1.3 Process composition.- 6.2 Composition of aperiodic circuits.- 6.2.1 The Muller theorem.- 6.2.2 The generalization of the Muller theorem.- 6.3 Algebra of asynchronous circuits.- 6.3.1 Operations on circuits.- 6.3.2 Laws and properties.- 6.3.3 Circuit transformations.- 6.3.4 Homological algebras of circuits.- 6.4 Reference notations.- 7 The matching of asynchronous processes and interface organization.- 7.1 Matched asynchronous processes.- 7.2 Protocol.- 7.3 The matching asynchronous process.- 7.4 The T2 interface.- 7.4.1 General notations.- 7.4.2 Communication protocol.- 7.4.3 Implementation.- 7.5 Asynchronous interface organization.- 7.5.1 Using the code with identifier.- 7.5.2 Using the optimally-balanced code.- 7.5.2.1 Half-byte data transfer.- 7.5.2.2 Byte data transfer.- 7.5.2.3 Using non-balanced representation.- 7.6 Reference notations.- 8 Analysis of asynchronous circuits and processes.- 8.1 The reachability analysis.- 8.2 The classification analysis.- 8.3 The set of operational states.- 8.4 The effect of non-zero wire delays.- 8.5 Circuit Petri nets.- 8.6 On the complexity of analysis algorithms.- 8.7 Reference notations.- 9 Anomalous behaviour of logical circuits and the arbitration problem.- 9.1 Arbiters.- 9.2 Oscillatory anomaly.- 9.3 Meta-stability anomaly.- 9.4 Designing correctly-operating arbiters.- 9.5 “Bounded” arbiters and safe inertial delays.- 9.6 Reference notations.- 10 Fault diagnosis and self-repair in aperiodic circuits.- 10.1 Totally self-checking combinational circuits.- 10.2 Totally self-checking sequential machines.- 10.3 Fault detection in autonomous circuits.- 10.4 Self-repair organization for aperiodic circuits.- 10.5 Reference notations.- 11 Typical examples of aperiodic design modules.- 11.1 The JK-flip-flop.- 11.2 Registers.- 11.3 Pipeline registers.- 11.3.1 Non-dense registers.- 11.3.2 Semi-dense pipeline register.- 11.3.3 Dense pipeline registers.- 11.3.4 One-byte dense pipeline register.- 11.3.5 Pipeline register with parallel read-write and the stack.- 11.3.6 Reversive pipeline registers.- 11.4 Converting single-rail signals into double-rail ones.- 11.4.1 Parallel register with single-rail inputs.- 11.4.2 Input and output heads of pipeline registers.- 11.5 Counters.- 11.6 Reference notations.- Editor’s Epilogue.- References.