Hierarchically connectable configurable cellular array

Claim 2

An hierarchically-scalable cellular array comprising: a plurality of cells; a first routing resource for interconnecting each cell to its adjacent neighboring cells, said first routing resource including a first plurality of lines having a length n, where n is a predetermined distance; a second routing resource including a second plurality of lines having a length N×n where N>1, said second routing resource connecting said cells into blocks of cells and interconnecting said blocks of cells; and a third routing resource including a third plurality of lines having a length N m ×n where n≧2 and where N m ×n≦T, the total length of said cellular array, said third routing resource interconnecting groups of said blocks of cells.

Claim 3

The cellular array of claim 1 wherein n is approximately one cell width.

Claim 4

The cellular array of claim 1 wherein N is 4.

Claim 5

The cellular array of claim 3 wherein m is 2.

Claim 6

The cellular array of claim 3 wherein m is 3.

Claim 7

The cellular array of claim 1 further including a fourth routing resource including a fourth plurality of lines having a length N r ×n where r≧3, and r=m+1.

Claim 8

A programmable logic structure comprising: an array of cells arranged in rows and columns; a plurality of switches, said plurality of switches partitioning said array into a first plurality of cell blocks, wherein each cell includes: four input lines for providing four input signals to said cell, each of said input lines coupled to an adjacent cell or switch; and four output lines for providing four output signals from said cell, each of said output lines coupled to an adjacent cell or switch, wherein said array further includes four intermediate, directed input lines for providing an additional four input signals to said cell, wherein each intermediate input line provides signals to the cells in either a row or a column of one of said blocks.

Claim 9

A programmable logic structure comprising: an array of cells arranged in rows and columns; a plurality of switches, said plurality of switches partitioning said array into a first plurality of cell blocks, wherein each cell includes: four input lines for providing four input signals to said cell, each of said input lines coupled to an adjacent cell or switch; and four output lines for providing four output signals from said cell, each of said output lines coupled to an adjacent cell or switch, wherein said array further includes four intermediate, directed input lines for providing an additional four input signals to said cell, wherein each intermediate input line provides signals to the cells in either a row or a column of one of said blocks.

Claim 10

The logic structure of claim 7 wherein said array further includes a plurality of flyover lines, each flyover line coupled between two of said plurality of switches, wherein said plurality of flyover lines determines a second plurality of cell blocks.

Claim 11

In an integrated circuit having a two-dimensional array of logic cells, a switch comprising: a set of multiplexers, each of which receives a plurality of input signals and provides an output signal; for each multiplexer, multiplexer control means for causing said multiplexer to select one of said input signals to provide said output signal, said input signals being taken from the following wires: a wire extending to the west from said switch and having a length approximately equal to a first multiple of said length of one of said cells; a wire extending to the east from said switch and having a length approximately equal to said first multiple of said length of one of said cells; a wire extending to the west from said switch and having a length approximately equal to a second multiple of said length of one of said cells; and a wire extending to the east from said switch and having a length approximately equal to said second multiple of said length of one of said cells; said output signals being placed on the following wires: a wire extending to the west from said switch and having a length approximately equal to a first multiple of said length of one of said cells; a wire extending to the east from said switch and having a length approximately equal to said first multiple of said length of one of said cells; a wire extending to the west from said switch and having a length approximately equal to a second multiple of said length of one of said cells; and a wire extending to the east from said switch and having a length approximately equal to said second multiple of said length of one of said cells.

Claim 12

In an integrated circuit having a two-dimensional array of logic cells, a switch comprising: a set of multiplexers, each of which receives a plurality of input signals and provides an output signal; for each multiplexer, multiplexer control means for causing said multiplexer to select one of said input signals to provide said output signal, said input signals being taken from the following wires: a wire extending to the west from said switch and having a length approximately equal to a first multiple of said length of one of said cells; a wire extending to the east from said switch and having a length approximately equal to said first multiple of said length of one of said cells; a wire extending to the west from said switch and having a length approximately equal to a second multiple of said length of one of said cells; and a wire extending to the east from said switch and having a length approximately equal to said second multiple of said length of one of said cells; said output signals being placed on the following wires: a wire extending to the west from said switch and having a length approximately equal to a first multiple of said length of one of said cells; a wire extending to the east from said switch and having a length approximately equal to said first multiple of said length of one of said cells; a wire extending to the west from said switch and having a length approximately equal to a second multiple of said length of one of said cells; and a wire extending to the east from said switch and having a length approximately equal to said second multiple of said length of one of said cells.

Claim 13

The switch of claim 9 wherein said first multiple is 1 and second multiple is 4.

Claim 14

The switch of claim 9 wherein said first multiple is 4 and second multiple is 16.

Claim 15

The switch of claim 9 wherein said first multiple is 16 and second multiple is 64.

Claim 16

The switch of claim 9 wherein said multiplexers further receive input signals taken from the following wires: a wire extending to the west from said switch and having a length approximately equal to a third multiple of said length of one of said cells; and a wire extending to the east from said switch and having a length approximately equal to said third multiple of said length of one of said cells.

Claim 17

The switch of claim 13 wherein said first multiple is 1, said second multiple is 4, and said third multiple is

Claim 18

The switch of claim 13 wherein said first multiple is 4, said second multiple is 16, and said third multiple is 64.

Claim 19

A programmable integrated circuit comprising: a two-dimensional array of logic cells, each cell comprising means for generating as an output signal a selected logic function of a plurality of logic cell input signals; a plurality of switches, said switches positioned so as to group said cells into cell blocks; each cell including: four short input wires for providing four of said input signals, said four short input wires carrying output signals from the cells or the switches which comprise nearest neighbors on four sides of said cell; four medium input wires for providing four of said input signals, said four medium input wires extending in four compass directions between switches which define a cell block in which said cell is positioned, wherein a plurality of said medium input wires are simultaneously accessable by said cell; and four short output wires for providing said output signal, said four short output wires carrying output signals to the cells or the switches which comprise nearest neighbors on four sides of said cell.

Claim 20

A programmable integrated circuit comprising: a two-dimensional array of logic cells, each cell comprising means for generating as an output signal a selected logic function of a plurality of logic cell input signals; a plurality of switches, said switches positioned so as to group said cells into cell blocks; each cell including: four short input wires for providing four of said input signals, said four short input wires carrying output signals from the cells or the switches which comprise nearest neighbors on four sides of said cell; four medium input wires for providing four of said input signals, said four medium input wires extending in four compass directions between switches which define a cell block in which said cell is positioned, wherein a plurality of said medium input wires are simultaneously accessable by said cell; and four short output wires for providing said output signal, said four short output wires carrying output signals to the cells or the switches which comprise nearest neighbors on four sides of said cell.

Claim 21

The programmable integrated circuit of claim 16 wherein each of said medium input wires carries a signal from a switch in one of the four compass directions to said cell and to other cells positioned between two of said switches making up said cell block.

Claim 22

The programmable integrated circuit of claim 17 wherein said medium wires are approximately four times the length of said short wires.

Claim 23

A programmable logic structure comprising: an array of cells; a plurality of switches arranged to group said cells into cell blocks such that for each cell block at least one west switch is positioned to the west of that block, and at least one east switch is positioned to the east of that block; a neighbor wire connecting from an output of said west switch to an input of the nearest cell east of said west switch; a flyover wire connecting from an output of said west switch to an input of said east switch; a neighbor wire connecting from an output of said east switch to an input of the nearest cell west of said east switch; and a flyover wire connecting from an output of said east switch to an input of said west switch.

Claim 24

A programmable logic structure comprising: an array of cells; a plurality of switches arranged to group said cells into cell blocks such that for each cell block at least one west switch is positioned to the west of that block, and at least one east switch is positioned to the east of that block; a neighbor wire connecting from an output of said west switch to an input of the nearest cell east of said west switch; a flyover wire connecting from an output of said west switch to an input of said east switch; a neighbor wire connecting from an output of said east switch to an input of the nearest cell west of said east switch; and a flyover wire connecting from an output of said east switch to an input of said west switch.

Claim 25

A programmable logic structure of claim 19 wherein said plurality of switches is further arranged such that for each cell block at least one north switch is positioned to the north of that block, and at least one south switch is positioned to the south of that block, wherein said programmable logic structure further comprises: a neighbor wire connecting from an output of said north switch to an input of the nearest cell south of said north switch; a south flyover wire connecting from an output of said north switch to an input of said south switch; a short wire connecting from an output of said south switch to an input of the nearest cell north of said south switch; and a north flyover wire connecting from an output of said south switch to an input of said north switch.

Claim 26

A programmable logic structure as in claim 20 in which each of said cells comprises a plurality of smaller cells, each of said smaller cells being defined by: a plurality of switches, said switches arranged to group said smaller cells into smaller cell blocks such that for each smaller cell block at least one west switch is positioned to the west of that block, at least one east switch is positioned to the east of that block, at least one north switch is positioned to the north of that block, and at least one south switch is positioned to the south of that block; said smaller cells being connected to said switches by: a neighbor wire connecting an output of said west switch to an input of the nearest smaller cell east of said west switch; a neighbor wire connecting an output of the nearest smaller cell east of said west switch to an input of said west switch; an east flyover wire connecting from an output of said west switch to an input of said east switch; a neighbor wire connecting from an output of said east switch to an input of the nearest smaller cell west of said east switch; and a neighbor wire connecting an output of the nearest smaller cell west of said east switch to an input of said east switch; a west flyover wire connecting from an output of said east switch to an input of said west switch; a neighbor wire connecting from an output of said north switch to an input of the nearest smaller cell south of said north switch; a neighbor wire connecting an output of the nearest smaller cell south of said north switch to an input of said north switch; a south flyover wire connecting from an output of said north switch to an input of said south switch; a neighbor wire connecting from an output of said south switch to an input of the nearest smaller cell north of said south switch; and a neighbor wire connecting an output of the nearest smaller cell north of said south switch to an input of said south switch; a north flyover wire connecting from an output of said south switch to an input of said north switch.

Claim 27

An input/output structure for a programmable logic device having a plurality of logic cells comprising: a plurality of pads, each pad connected to an external pin of said programmable logic device; a plurality of I/O buffers, each I/O buffer connected to one of said plurality of pads, each I/O buffer including a switch for connecting said I/O buffer to at least one of said plurality of logic cells, wherein said switch forms part of a hierarchial interconnect structure receiving input signals both from wires from neighboring cells and wires from other switches and providing output signals to both wires in neighboring cells and wires leading to other switches; and means for controlling said switch.

Claim 28

An input/output structure for a programmable logic device having a plurality of logic cells comprising: a plurality of pads, each pad connected to an external pin of said programmable logic device; a plurality of I/O buffers, each I/O buffer connected to one of said plurality of pads, each I/O buffer including a switch for connecting said I/O buffer to at least one of said plurality of logic cells, wherein said switch forms part of a hierarchial interconnect structure receiving input signals both from wires from neighboring cells and wires from other switches and providing output signals to both wires in neighboring cells and wires leading to other switches; and means for controlling said switch.

Claim 31

The method of claim 23 further including the step of providing a plurality of flyover lines, each flyover line coupling two of said plurality of switches.

Claim 32

The method of claim 24 further including the step of providing a signal from a first cell to a second cell, wherein said providing includes transferring said signal via at least one intermediate input line.

Claim 33

The method of claim 25 wherein said step of providing further includes transferring said signal via at least one flyover line.

Claim 34

The method of claim 23 further including the steps of: sending a signal via a first path including a plurality of switching units, said first path paralleling a direct, second path; using logic gates to detect whether said signal travels the full length of said first path; and if said signal travels said full length, then placing said signal on said second path.

Claim 35

A routing device in a programmable logic device comprising: a plurality of cells providing a first path, wherein each cell includes: means for receiving a plurality of input signals and providing an output signal; a plurality of memory bits associated with said means for receiving; and a first logic gate for providing a trigger signal determined by the state of said plurality of memory bits; a second path not including cells, said second path paralleling said first path; a second logic gate coupled to the output terminals of the first logic gates to detect whether said signal travels the full length of said first path; and means for determining whether a signal is provided on said first path or on said second path, said means for determining controlled by said second logic gate.

Claim 36

A routing device in a programmable logic device comprising: a plurality of cells providing a first path, wherein each cell includes: means for receiving a plurality of input signals and providing an output signal; a plurality of memory bits associated with said means for receiving; and a first logic gate for providing a trigger signal determined by the state of said plurality of memory bits; a second path not including cells, said second path paralleling said first path; a second logic gate coupled to the output terminals of the first logic gates to detect whether said signal travels the full length of said first path; and means for determining whether a signal is provided on said first path or on said second path, said means for determining controlled by said second logic gate.