1
A Programmable Logic Architecture
Richard Barth
Draft of May 22, 1989 11:56:56 am PDT
1.0 Introduction
This paper describes a new implementation of RAM programmable logic. A description of the closest commercial realization of this type of logic can be found in [Xilinx].
2.0 Assembly Language
This section describes the low level abstraction used to program the devices.
2.1 Basic Programming
Figure 1 shows the low-level wires from which all larger structures are built.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 1. Basic Interconnect
Output is the wire which carries the output of a basic gate. Input carries the input of a basic gate. RightUp is a short length of uncommitted wire whose direction is fixed to right or up. LeftDown is similiar but its direction is fixed to left or down. The dots on RightUp and LeftDown indicate that the value is inverted when making the transition across the wire segment. Long is a wire which extends across the width of a chip to enhance interconnect density and performance. Its direction is not fixed.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 2. Minor Array
Figure 2 shows an array of basic interconnects organized as a repetition in the horizontal and vertical directions. The basic interconnects are numbered, increasing from left to right, and bottom to top.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 3. Programming Primitives
Figure 3 portrays the graphical symbols used to program the array. Program indicates that an input wire is connected to an output wire through a gate. Inverter indicates that a signal is inverted. FlipFlop indicates that a signal flows through an edge-triggered flip-flop. The allowable placement locations for these tiles are described later in this document.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 4. Basic Logic Function Classification
Figure 4 classifies the 16 functions of 2 variables. A single output wire can perform the nand function of 5 variables. Through the use of De Morgan's theorems, the programmable number of inputs, and the propagation of inversions, this basic capability can perform any of the function classes except xor, which requires three output wires for implementation.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 5. Example Function
Figure 5 shows the programming of the function horizontal0 ← not (vertical0 * vertical2 * vertical3), in the top row of a minor array. The remaining 3 rows are elided for clarity. In this same manner all horizontal outputs can be functions of all the vertical inputs (not the RightUp, LeftDown, or Long lines), and all vertical outputs can be functions of all horizontal inputs. In addition, the input parallel to an output, and of the same index, can participate in the formation of the output as illustrated in figure 6, which computes horizontal0 ← not (horizontal0 * vertical0 * vertical2 * vertical3).
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 6. Another Example Function
The input wire can be inverted. The output wire can be delayed by a flip-flop. Figure 7 shows the same function as figure 6 except that the horizontal output has been delayed and the horizontal input has been inverted.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 7. Example Function with Inversion and Delay
The interior of a chip is formed by tiling the plane with minor arrays. Figure 8 illustrates a 4 by 4 array. A realistic chip using 2 micron DLM CMOS has an array which is 16 by 16.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 8. Sample Chip Interior Tiling
In this array logical networks are constructed by connecting physical wires in straight lengths, either horizontally or vertically, and then connecting the vertical and horizontal segments together with corners formed from 1 input gates.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 9. Connection Tiles
Figure 9 displays the tiles used to connect segments of wire together. At each intersection of basic interconnects any combination of these tiles may be used except that no wire may be driven more than once. The titles indicate function as follows:
ORUToI - Output Right Up To Input
LDToLD - Left Down To Left Down
OLDToI - Output Left Down To Input
ORUToL - Output Right Up To Long
RUToRU - Right Up To Right Up
ORUToLD - Output Right Up to Left Down
LDToI - Left Down To Input
OLDToRU - Output Left Down To Right Up
LToI - Long To Input
RUToI - Right Up To Input
The tiles are shown here in the orientation used for horizontal interconnects. Each tile must be rotated 270 degrees, and mirrored in Y, before use in vertical interconnects. This cumbersome mechanism of tiles is used to simplify printing and parsing of assembly language programs. It also succinctly expresses the permissible interconnections amoung the 9 wires which participate at each junction. Only 10 connections are legal out of the 81 possible.
Note that the output is delayed by a flip-flop even if the interconnect tile connects to the output wire on the far side of the minor array. For a given output the connection through an OLDToI or OLDToRU tile is delayed, just as an ORUToI, ORUToL, or ORUToLD is delayed by a FlipFlop tile, even though the geometric path does not pass through the flip-flop symbol.
Figure 10 is an example of routing a logical net through several wires, utilizing 2 corners. The net begins in the top horizontal output of the left minor array, runs to the top horizontal input wire of the right minor array, goes through a corner onto the leftmost vertical output of the right minor array, is fed back to the left vertical input wire, through a corner, onto the second from top horizontal output, and finishes as the second from top horizontal LeftDown wire in the left minor array.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 10. Logical Net Example
Whenever a function requires the inverted form of an input, an Inverter symbol must be placed on the corresponding input. Figure 11 computes the OR of two variables by inverting the inputs.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 11. OR gate implementation
Some functions require an inverted output, e.g. the AND gate. This is achieved by inverting the destination inputs. Since each corner also introduces an inversion, the input inversion is actually controlled by the parity function of the input inversion requirement, the source output inversion requirement, and all of the corners between the source output and the input.
2.2 Pin Programming
Eventually the abstraction of an infinite plane of silicon must break down. At this point we introduce the traces of the printed circuit board, to which the pins of the integrated circuit are attached, into the abstraction. In this section we describe the details of connecting the inner array to the pcb traces.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 12. Minor Array with Pins
In figure 12 only one minor array is shown. In a real array, which is 16x16, there would be 64 pins on each edge instead of the 4 pins shown.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 13. Pin Connection Tiles
Figure 13 shows the tiles available to connect the pins to the array. The upper row is the set of tiles available for the left and bottom (when rotated 270 degrees and mirrored in Y) edges. The lower row is the set of tiles available for the right and top (when rotated 270 degrees and mirrored in Y) edges. When a tile appears in both rows this indicates that the tile may be used for any of the four edges. The titles indicate function as follows:
OToP - Output To Pin
RUToP - Right Up To Pin
LDToP - Left Down To Pin
LToP - Long To Pin
PToI - Pin To Input
PToRU - Pin To Right Up
PToLD - Pin To Left Down
PToL - Pin To Long
2.3 Tristate Programming
Tristate programming is available as a tile which enhances the ORUToL tile by using the LeftDown output to control the long line driver. Figure 14 illustrates the usage of the tristate tile in a situation where a common control line is running horizontally and data lines are running vertically.
[ Nectarine figure; type 'Artwork on' to a CommandTool ]
Figure 14. Tristate Tile
This tile allows emulation of tristate buses that are straight and contained only within one chip. Some day there will be a pin tile that helps gang a tristate bus across chips, but that will be a directional solution, i.e. either the bus will have to be manually wired end-around (ycch) or all the receivers will have to sense a different grain so that information is collected upwards from the drivers then broadcast downwards to the receivers.
References
[Xilinx]
Xilinx Inc., The Programmable Gate Array Design Handbook, 1986.