Efficient Arithmetic and Logic Unit (ALU) Design Based on Recursive Multi-Function Circuits

Previous works have shown that multiple fun-damental arithmetic operations (lead-digit detection, comparison, parallel-prefix addition, incrementation, etc.) on binary vectors share a common recursive structure, which can be leveraged to implement a multifunction circuit capable of performing any of them. The said circuit, comprising a main dyadic tree structure, is characterized by a regular structure, predominance of short connections, as well as regular and low fan-ins and fan-outs. Such a circuit could advantageously be incorporated in an arithmetic and logic unit. Furthermore, its recursive structure makes it easily amenable to automatic synthesis for arbitrary operand widths by, e.g. relying on the structural recursion features of hardware-description languages (HDLs), as well as automatic placement and routing. It is demonstrated here that each output bit for all arithmetic operations supported by this circuit exhibits a dependency on potentially all input bits and that this entails a processing delay of at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log_{2}(N)_{/}^{\backslash }$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> is the operand size. It is also shown that a different recursive structure can be devised for a set of relevant operations which exhibit the same type of dependency on their input bits (and thus are subject to the same <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log_{2}(N)$</tex> limit) while being non-numeric, and non-ordinal. In other words, the input bit vector(s) are not considered to represent numbers and the position of an input bit in the vector does not alter its effect on the output. This function set includes population count, the majority gate, as well as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex>-input basic logical gates (AND, OR, NAND, NOR, XOR, XNOR). The structure of a corresponding multifunction circuit is derived and its integration into an ALU described.