Browse Prior Art Database

TIMING-DRIVEN PARTITIONING OF PLAs

IP.com Disclosure Number: IPCOM000034440D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Ditlow, GS: AUTHOR [+2]

Abstract

When designing VLSI microprocessors, control logic such as op-decode is conveniently specified in PLA [1] form. For large fanout designs, such as op-decode, PLAs can be more suitable than random logic implementations since global wiring requirements are minimized. All internal wiring within a PLA is 100% wirable because of the regular PLA structure. The penalty for designs using PLAs is speed, since a two-level representation has a large number of product terms. Disclosed is a new algorithm which partitions a PLA into several smaller PLAs such that the timing is optimized. This differs from previous approaches [2, 3] to PLA partitioning which were based on minimizing PLA area.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

TIMING-DRIVEN PARTITIONING OF PLAs

When designing VLSI microprocessors, control logic such as op-decode is conveniently specified in PLA [1] form. For large fanout designs, such as op-decode, PLAs can be more suitable than random logic implementations since global wiring requirements are minimized.

All internal wiring within a PLA is 100% wirable because of the regular PLA structure. The penalty for designs using PLAs is speed, since a two-level representation has a large number of product terms. Disclosed is a new algorithm which partitions a PLA into several smaller PLAs such that the timing is optimized. This differs from previous approaches [2, 3] to PLA partitioning which were based on minimizing PLA area. Using this approach, the area of the PLA is increased slightly, but the timing is improved significantly, depending on the number of partititions and the size of the original PLA. The benefit from this algorithm is maximized when the number of product terms is large compared to the number of inputs or outputs. Timing Assumptions The delay of a PLA can be divided into three components -- (1) decoder, (2) AND array, (3) OR array. The PLA is assumed to be implemented using NORs in the AND array and OR array. The decoder creates a true/complement pair for each input and then drives the AND array using a large buffer. By virtue of the buffer, the decoder delay is the least important delay. The AND array delay of a product term is significant only when the number of inputs plus the number of outputs is large compared to the number of product terms. Most of the delay in a large PLA is dominated by the OR array since it is implemented as a non-buffered NOR circuit with a p-channel pull-up. Within each OR array output there are two components of delay -- the wire delay connecting product terms and the device delay due to the existence of a pull-down. The device delay is an order of magnitude more significant than the wire delay because the wires are so short and the diffusion capacitance of the pull-down is so high. Partitioning During the partitioning process, product terms are placed into partitions so that the device delay is distributed among each partition. The cost function for this partitioning is "timing driven" in the sense that for k partitions, the k critical paths have delays d1, d2,...dk such that max(di) is minimized, for i = 1,...,k. To maintain the same functionality before and after partitioning, the outputs of each partition must be "ORed" together...