A Design Space and its Patterns: Modelling 2phase Asynchronous Pipelines

We present a systematic way of studying state machine based design spaces and apply it to the study of asynchronous pipelines. Starting with the specification of the most concurrent behaviour as a state machine, all possible valid smaller designs may be generated by systematically removing structured patterns of output states (C cuts) and input states (R cuts). Taking the cartesian product of cuts C×R yields the complete design space which may then be partitioned according to well understood design styles. In this paper we extend previous results by studying mixed asynchronous pipelines of which homogeneous behaviours form a subset. The approach is presented using the much smaller 2phase setting (3×6) but the insights and structures revealed carry over to full 4phase designs (35×140). We present a complete overview of mixed 2phase linear pipeline behaviours; show how their structuring C cuts and R cuts relate; characterise the behaviours of linear pipelines in terms of these cuts for any depth; and show how the much larger R mixed behaviour patterns can be calculated from knowledge of the C behaviour patterns. Applications of the theory cover mixed linear pipeline and ring behaviours and the automatic generation of quality circuits from our specifications.