| Designing Arithmetic Circuits by Refinement in Ruby (1992) | |||||||||||||||||
Abstract | |||||||||||||||||
| . This paper presents in some detail the systematic derivation of a static bit-level parallel algorithm to implement multiplication of integers, that is to say one which might be implemented as an electronic circuit. The circuit is well known, but the derivation shows that its design can be seen as the consequence of decisions made (and explained) in terms of the abstract algorithm. The systematic derivation serves both as an explanation of the circuit, and as a demonstration that it is correct `by construction'. We believe that the technique is applicable to a wide range of similar algorithms. 1 Introduction We advocate a style of `design by calculation' for the very fine-grained parallel algorithms that are implemented as regular arrays of electronic circuits. The design of such circuits is particularly difficult because the implementation medium imposes severe constraints on what is possible and what is reasonably efficient. In consequence the details of the final implementation ha... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||