Algorithms for Multiple-Criterion Design of Microprogrammed Control Hardware

This paper describes two algorithms designed to optimize memory size and controller performance for a microprogrammed controller. The algorithms accept two inputs: a set of interconnected registers and logical operators called the data paths, and a control flow graph which describes how these data paths are to be exercised. The Autonomy algorithm identifies data path elements which should be controlled directly from the microword without encoding. This algorithm aids the effectiveness of the subsequent encoding algorithm by eliminating some signals from consideration. A second algorithm, the Attraction algorithm, determines which microoperations will execute in parallel and which will be encoded into separate microinstruction formats. This algorithm accepts a microword width constraint and implements parallel operations in the microcode and the corresponding encoding. Both the parallelism and the encoding are determined by the algorithm. Application of these algorithms to an example, the PDP (FOOTNOTE: PDP is a registered trademark of Digital Equipment Corporation.)-11/40, has produced a control store design 14 percent wider and equal in parallelism to an equivalent portion of the human design.