Browse Prior Art Database

Detection of Multiplexer Structures in Logic

IP.com Disclosure Number: IPCOM000040576D
Original Publication Date: 1987-Dec-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 3 page(s) / 48K

Publishing Venue

IBM

Related People

Perlowitz, WB: AUTHOR

Abstract

When logic is synthesized from a high level language, the efficiency of the eventual implementation is often dependent on the effective use of space efficient "intermediately sized" structures. Boolean minimization of small structures (e.g., NORs) has been an area of active research for more than two decades, and the use of large structures (e.g., multipliers) is generally known by the architect before synthesis begins. Successful detection of intermediately sized structures in the synthesis process may then determine the acceptability of the synthesized design. Architect specification of these structures is unacceptable since it will mask novel implementations of the target function.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Detection of Multiplexer Structures in Logic

When logic is synthesized from a high level language, the efficiency of the eventual implementation is often dependent on the effective use of space efficient "intermediately sized" structures. Boolean minimization of small structures (e.g., NORs) has been an area of active research for more than two decades, and the use of large structures (e.g., multipliers) is generally known by the architect before synthesis begins. Successful detection of intermediately sized structures in the synthesis process may then determine the acceptability of the synthesized design. Architect specification of these structures is unacceptable since it will mask novel implementations of the target function. Pattern recognition of structures in the target technology is likewise unacceptable since the diversity of structures implementing the intermediately sized structure is prohibitively large. This article addresses the recognition of multiplexer structures (of which the exclusive OR is a special case) using an extension of the algorithm described for finding single-bit selectors. An N:1 multiplexer can be thought of as a combination of an N:1 decoder and an N bit selector, as shown in Fig. 1. The problem of recognizing a multiplexer can then be broken into two parts: recognition of the decoder and formation of the data inputs. Fig. 2 shows NOR logic for decoder recognition and is extendable to that of other types. It is a simple NOR representation of a 2:1 multiplexer. At the box marked "B" we could find the reconvergence of the signal "C" with its inverse. (Note that this logic is for illustrative purposes only. Signal reconvergence would be derived by examining the C vectors only and the logic may take many forms.) Since we are in a NOR technology, this tells us that the "data" pins for box "X" will be placed at multiplexer input value "0", and those of box "Y" at input value "1". For larger multiplexers, we would expect more signals to reconverge at box "B", and, given N reconvergent signals, we would expect to create a 2N:1 multiplexer. Each box connected to the box where the reconvergence was found can then be assigned a multiplexer input value ranging from 0 to 2N-1. In the event that neither a reconvergent signal nor its inverse controls a box's output, that value becomes a "don't care" condition. "Don't care" conditions are assigned to all applicable multiplexer input values, and those inputs with multiple data values have these inputs ORed together. Boxes which are unaffected by any of the identified control signals are not considered part of the multiplexer, but are instead NORed with the output of the multiplexer to eliminate the redundant ORing at each input. (For NAND tech...