A Programmable Logic Architecture
Richard Barth
Draft of January 16, 1989 5:03:47 pm PST
1.0 Introduction
    This paper describes a new implementation of RAM programmable logic.  The closest commercial realization of this type of logic can 
    be found in [Xylinx].
2.0 Assembly Language
    This section describes the low level abstraction used to program the devices.
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 1. Basic Interconnect>>
    Figure 1 shows the low-level wires from which all larger structures are built.  Output is the wire which carries the output of a 
    basic gate.  Short carries the input of a basic gate.  Word is the access line for a row of RAM bits.  Long is a wire which 
    extends across the width of a chip to enhance interconnect density and performance.
<<[ 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 a short wire is connected to an output 
    wire through a gate.  Direction sets the direction of signal flow.  Invert indicates that a signal is inverted.  FlipFlop 
    indicates that a signal flows through an edge-triggered flip-flop.
<<[ 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 (horizontal,output,3) _ not ((vertical,short,0) * (vertical,short,2) * 
    (vertical,short,3)), 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 short wires (not the word or long lines), and all vertical outputs can 
    be functions of all horizontal short wires.  In addition, the short wire parallel to an output wire and of the same index can 
    participate in the formation of the output as illustrated in figure 6, which computes (horizontal,output,3) _ not 
    ((horizontal,short,0) * (vertical,short,0) * (vertical,short,2) * (vertical,short,3)).
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 6. Another Example Function>>
    The interior of a chip is formed by tiling the plane with minor arrays.  Figure 7 illustrates a 4 by 4 array.  A realistic chip 
    using current day processing has an array which is 16 by 16.
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 7. Sample Chip Interior Tiling>>
    This array constructs logical networks from the physical wires by connecting them 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 8. Connection>>
    Figure 8 illustrates the simplest type of connection.  In this diagram the short wire on the left has been connected to the short 
    wire on the right by drawing a rectangle overlapping the respective rectangles.  The direction has been set by placing a 
    Direction cell on top of the connecting rectangle.  As stated earlier the long wires implicitly connect between minor arrays.
    All connections between the 7 wires are legal except,
    no wire may be driven by more than one source, and
    the output wires must not be driven.
    Figure 9 illustrates an illegal, and a legal, connection to an output wire.
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 9. Illegal and Legal Output Connections>>
    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 short wire of the right minor array, goes through a corner onto the 
    leftmost vertical output of the right minor array, is fed back into the right minor array on the leftmost short wire, turns 
    back again, through a corner, onto the second from top horizontal output, and finishes as the second from top horizontal input 
    in the left minor array.
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 10. Corner Example>>
    Whenever a function requires the inverted form of an input, an Invert symbol must be placed on the corresponding short line.  
    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>>
    The Invert symbol can only be applied to a short wire.  It must be placed at the driven end of the wire.  Each short wire has a 
    flip-flop available.  This flip-flop is inserted between the source for the short wire and the short wire itself.  Figure 12 
    illustrates a pipelined OR gate.
<<[ Nectarine figure; type 'Artwork on' to a CommandTool ]>>
<<Figure 12. Pipelined OR gate>>
    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.
Unfinished
    There is another cell, Chip, which has the abstraction for an entire chip.
    To a first approximation each instance of a symbol controls the state of one RAM bit.  Thus, even though the direction can be 
    inferred for single output, acyclic nets, this is not done.
    Describe how RAM's, CAM's, and PLA's are implemented.
    Do not use the word line for interconnect as they directly control the access transistors in the crosspoint RAM and you won't like 
    the result.  ????  Maybe that is ok as long as you don't depend on the programming or if the programming is consistent.
    The signal must always be inverted when connected to the word line.
References
[Xylinx]
    Xilinx Inc., The Programmable Gate Array Design Handbook, 1986.