A scheduling and hardware sharing algorithm is presented. This algorithm is generic and can be used for synthesizing both nonpipelined and pipelined data paths. The scheduling algorithm tries to distribute operations equally among partitions to maximize hardware sharing. Multiplexer delays are explicitly considered to produce a more accurate scheduling. In hardware sharing, structural parameters such as the size of multiplexers, interconnect overhead, the size of the smallest sharable operator etc. are used to control the amount of sharing globally and produce a heuristically optimized RTL structure. The scheduling algorithm is iterated until a satisfactory structure is obtained. The algorithm also can be used for partitioning a large system into implementable pieces. The algorithm has been used successfully for synthesizing a pipelined data path from a graphics processing description that contains about 1000 components.>

A conditional resource-sharing algorithm for pipeline synthesis is presented. It allows sharing of hardware components among the mutually exclusive parts of any conditional branches appearing in a behavioral description. If done improperly, resource sharing in a conditional branch can increase its critical path delay excessively, causing performance degradation. Given area/time constraints for a pipelined design, finding an optimal conditional sharing solution is a combinatorial optimization problem. The algorithm uses heuristics with a user-defined weight that trades off area versus time; the algorithm is either manually or automatically iterated by changing the weight until a solution close to the target is obtained or is determined to be impossible to obtain. The algorithm is interactive, so designers can manually determine partial or whole sharing.>

In this paper, we analyze combinational logic circuits using "fan-out constraints" to generate tests for single stuck-at faults. A method of circuit transformation is employed to explicitly derive "fan-out constraints for controllability" and "fan-out constraints for observability," which are dependent Boolean functions and Boolen difference functions, respectively, in terms of primary inputs and fan-out stems. Then, a simplified version of a test generation algorithm which uses only the fan-out constraints for controllability at internal reconvergent fan-out stems is illustrated with an example. This approach differs from earlier work in that information about the circuit is accumulated and refined as the test generation process proceeds. In this test generation algorithm, the dependencies among fan-out nodes are ordered and solved in a hierarchical fashion so that the computation time for generating tests and detecting redundant faults can be greatly reduced--especially for locally redundant or "difficult" faults.