Programmable Logic Array and Method for Its Design Using a Three Step Approach

U.S. patent application Ser. No. 08/603,662, entitled "PLA LATE SIGNAL CIRCUITRY USING A SPECIALIZED GAP CELL AND PLA LATE SIGNAL CIRCUITRY USING SWITCHED OUTPUT", filed concurrently herewith is assigned to the same assignee hereof and contains subject matter related, in certain respect, to the subject matter of the present application. The above-identified patent application is incorporated herein by reference.

1. Technical Field of the Invention

This invention pertains to an improved hardware design for programmable logic arrays (PLAs). In particular, this invention tackles the problems associated with propagation delay of signals through a PLA, thereby providing enhanced performance of the PLA structure.

2. Background Art

The need for quick turn around time for generation of logic is well known. PLAs help tackle this need in that they can be easily automated in their creation. The propagation delay of signals through PLAs is a concern especially on high performance chips. One problem that can occur in PLAs with respect to its propagation delay is a particularly slow path or paths from the true/complement generator input or inputs through a product term or terms that increase the entire delay of the PLA. These slow paths can affect many of the PLA outputs, thereby producing significant signal propagation delay in many of the input-to-output transitions.

It is an object of the invention to reduce signal propagation delay through a PLA by redesigning pre-identified slow signal paths.

It is another object of the invention to provide a PLA with superior delay characteristics resulting from better placement of slow signal paths.

During a timing analysis of proposed PLA designs the slowest transitioning product terms inside of the PLA can be identified. These timing analyses are well known in the art and are not described further. Based on this information we describe here an invention that solves the slow product term problem (slowest path or paths) by taking a three step approach, any of which steps implemented individually also would improve the PLA performance. First, we physically relocate the offending (slow) product terms as close as possible to the input/output buffers, also known as the true/complement generators. Second, we duplicate the offending input buffers. Third, we split the product terms in question into two or more product terms and recombine them in a modified gap cell before propagating the signal into the OR array.

This invention solves the timing problem associated with propagation delays through PLAs. By attacking the problem with this unique three step approach which includes moving the offending product terms closer to the input/output buffers, duplicating the true/complement generators, then duplicating the heavily loaded product terms and recombining them within the modified gap cell, we can easily decrease the propagation delays through the PLA.

Other features and advantages of this invention will become apparent from the following detailed description of the presently preferred embodiment of the invention, taken in conjunction with the accompanying drawings.

FIG. 1 illustrates a typical PLA structure.

FIG. 2 shows an improved PLA resulting from the inventive three step redesign approach.

FIG. 3 illustrates an overall view of a PLA system.

Referring to FIGS. 1 and 2, the first step of our three step redesign approach is to move the pre-identified offending product term 12 as close to the input true/complement generators 10 as possible. This will reduce the wiring propagation delay caused by signals traversing a relatively lengthy transmission path 14 (FIG. 1). We can physically move this product term as close to the inputs 10 as possible and, in so doing, push the other product terms 16 further away. Moving a product terms like this does not in any way change the logical operation of the PLA. Element 12 in FIGS. 1 & 2 illustrate the differences in the PLA by this improvement. We have just reduced the wiring delay due to the product term (element 12 of FIG. 1) being far away from the input true/complement generators 10.

The second step in this three step approach involves partitioning the input true/complement generator 10a to help distribute the load on this input generator and, thus, to speed up this path. We take the existing input true/complement generator 10a that contains our previously identified slow path and we duplicate it 10a' (FIG. 2). Although we have increased the input capacitance on this input node 10a' and increased the size of the PLA, we have decreased the loading on these generators. FIGS. 1 & 2 show the before and after improvements of this redesign. We have increased the speed of the input true/complement generator 10a' by duplicating it and thus distributing its load.

The third step in this three step approach involves partitioning the offending product 12 term so as to distribute the load on it. We take the existing product term 12 and split it into divided but less loaded terms, i.e., sub-terms 12a and 12b (FIG. 2). These terms now evaluate faster than the original 12 (FIG. 1). We then recombine these signals in the gap cell 22 with a logical function (we show the presently preferred embodiment NAND gate 23 in FIG. 2). FIG. 2 shows the redesign improvements over the conventional PLA of FIG. 1. We have just increased the speed of the product term 12 itself by partitioning it to distribute the load, then recombining it within the gap cell 22. This effectively reduces the propagation delay through the product term.

One example is having a PLA with 20 inputs (10a thru 10b of FIG. 1), 80 Product Terms 16, and any number of outputs 18. If we identify the worst case timing path propagating through the PLA as coming from input 10a, which is assumed to be heavily loaded in this example, and passing through the 80th product term (furthest from the inputs in this example), and that product term contained a connection to every input, then we have a propagation delay that can be greatly improved by the present invention.

First, we move the 80th product term from the furthest position away from the true/complement generators and relocate it adjacent to the true/complement generators. Next, we would split input 10a into two true/complement generators, instead of the typical one true/complement generator, effectively cutting in half the load seen by the generator at its input. Finally, we would take this 80th product term and split it into two product terms, each containing half of the original number of inputs connected to them. These two new product terms (12a and 12b of FIG. 2) will now be recombined within the gap cell with a two input NAND gate. By the presently described three step approach we have increased the speed of this example transmission path within the PLA. This approach has decreased the loading on both the input 10a true/complement generator and on the product term 12, which also contributes to the speed improvement over this path.

It will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without departing from the spirit and scope of the invention. In particular, one alternative implementation is to use this three step approach on several product terms and on several inputs simultaneously to speed up multiple paths through a PLA simultaneously. A second alternative implementation is to partition the product term itself into more than two sections. A third alternative implementation is to partition the input true/complement generators into more than two sections.

Since other changes may be made in the above structure and method without departing from the scope of the invention described herein, it is intended that all the matter contained in the above description or shown in the accompanying drawings shall be interpreted in an illustrative and not in a limiting sense. Thus other alternatives and modifications will now become apparent to those skilled in the art without departing from the spirit and scope of the invention as set forth in the following claims. Accordingly, the scope of protection of this invention is limited only by the following claims and their equivalents.