Mapping a lookup table to prefabricated TCAMS

Patent metadata

Field	Value
Publication number	US-9824756-B2
Application number	US-201313966266-A
Country	US
Kind code	B2
Filing date	Aug 13, 2013
Priority date	Aug 13, 2013
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

Access is obtained to a truth table having a plurality of rows, each including a plurality of input bits and a plurality of output bits. At least some rows include don't-care inputs. At least some of the rows are clustered into a plurality of multi-row clusters. At least some of the multi-row clusters are assigned to ternary content-addressable memory modules of a prefabricated programmable memory array. Instructions for interconnecting the ternary content-addressable memory modules with a plurality of input pins of the prefabricated programmable memory array and a plurality of output pins of the prefabricated programmable memory array are specified in a data structure, in order to implement the truth table.

First claim

What is claimed is:

1. A method comprising:
obtaining access to a truth table having a plurality of rows, each of said rows comprising a plurality of input bits and a plurality of output bits, at least some of said rows comprising don't-care inputs;
clustering at least some of said rows into a plurality of multi-row clusters;
assigning at least some of said multi-row clusters to ternary content-addressable memory modules of a prefabricated programmable memory array; and
specifying in a data structure instructions for interconnecting said ternary content-addressable memory modules with a plurality of input pins of said prefabricated programmable memory array and a plurality of output pins of said prefabricated programmable memory array, in order to implement said truth table.

2. The method of claim 1 , wherein:
said clustering is based upon configuration information for said prefabricated programmable memory array, said prefabricated programmable memory array comprising said ternary content-addressable memory modules, said plurality of input pins, said plurality of output pins, a reconfigurable input logic fabric, and a reconfigurable output logic fabric, said reconfigurable input logic fabric being programmable to selectively interconnect said plurality of input pins with said ternary content-addressable memory modules, said reconfigurable output logic fabric being programmable to selectively interconnect said plurality of output pins with said ternary content-addressable memory modules; and
said specifying step comprises specifying settings for a plurality of programmable switches in said reconfigurable input logic fabric and said reconfigurable output logic fabric.

3. The method of claim 2 , further comprising programming said reconfigurable input logic fabric and said reconfigurable output logic fabric by setting said plurality of programmable switches in said reconfigurable input logic fabric and said reconfigurable output logic fabric in accordance with said settings.

4. The method of claim 2 , wherein, with respect to said configuration information, said prefabricated programmable memory array further comprises non-ternary content-addressable memory modules, further comprising:
assigning at least some of said multi-row clusters to non-ternary content-addressable memory modules; and
interconnecting said non-ternary content-addressable memory modules with said plurality of input pins and said plurality of output pins to implement said truth table.

5. The method of claim 4 , wherein said clustering comprises grouping together those of said rows having similar don't-care inputs.

6. The method of claim 4 , wherein said clustering comprises grouping together those of said rows having similar outputs.

7. The method of claim 4 , wherein said clustering comprises:
representing each row of said truth table as a node in a graph, each of said nodes having an input dependency pattern;
interconnecting said nodes with a plurality of edges;
assigning to each of said edges a cost;
merging two of said nodes connected with a minimal-cost one of said edges;
updating said edge costs and said input dependency patterns to reflect said merged nodes; and
repeating said merging and updating steps until no further clustering is possible and all of said truth table fits on said prefabricated programmable memory array.

8. The method of claim 4 wherein said assigning comprises applying at least one of network flow and bipartite graph matching, subject to placing cascaded ones of said clusters closely, placing said ternary content-addressable memory modules on a fastest available path between said input pins and said output pins, and placing those of said clusters with a higher input dependency on said fastest available path between said input pins and said output pins.

9. The method of claim 4 , further comprising providing a system, wherein the system comprises distinct software modules, each of the distinct software modules being embodied on a computer-readable storage medium, and wherein the distinct software modules comprise an input-output module, a clustering module, a mapping module, and a hardware design language module;
wherein:
said step of obtaining access to said truth table is carried out by said input-output module executing on at least one hardware processor;
said clustering step is carried out by said clustering module executing on said at least one hardware processor;
said assigning step is carried out by said mapping module executing on said at least one hardware processor; and
said specifying step is carried out by said hardware design language module executing on said at least one hardware processor.

10. An apparatus comprising:
a memory; and
at least one processor, coupled to said memory, and operative to:
obtain access to a truth table having a plurality of rows, each of the rows comprising a plurality of input bits and a plurality of output bits, at least some of the rows comprising don't-care inputs;
cluster at least some of the rows into a plurality of multi-row clusters;
assign at least some of the multi-row clusters to ternary content-addressable memory modules of a prefabricated programmable memory array; and
specify in a data structure in said memory instructions for interconnecting the ternary content-addressable memory modules with a plurality of input pins of the prefabricated programmable memory array and a plurality of output pins of the prefabricated programmable memory array, in order to implement the truth table.

11. The apparatus of claim 10 , wherein the clustering is based upon configuration information for the prefabricated programmable memory array, the prefabricated programmable memory array comprising the ternary content-addressable memory modules, the plurality of input pins, the plurality of output pins, a reconfigurable input logic fabric, and a reconfigurable output logic fabric, the reconfigurable input logic fabric being programmable to selectively interconnect the plurality of input pins with the ternary content-addressable memory modules, the reconfigurable output logic fabric being programmable to selectively interconnect the plurality of output pins with the ternary content-addressable memory modules;
wherein said at least one processor is further operative to specify by specifying settings for a plurality of programmable switches in the reconfigurable input logic fabric and the reconfigurable output logic fabric.

12. The apparatus of claim 11 , wherein said at least one processor is operative to cluster by:
representing each row of the truth table as a node in a graph, each of the nodes having an input dependency pattern;
interconnecting the nodes with a plurality of edges;
assigning to each of the edges a cost;
merging two of the nodes connected with a minimal-cost one of the edges;
updating the edge costs and the input dependency patterns to reflect the merged nodes; and
repeating the merging and updating until no further clustering is possible and all of the truth table fits on the prefabricated programmable memory array.

13. The apparatus of claim 12 wherein said at least one processor is operative to assign by applying at least one of network flow and bipartite graph matching, subject to placing cascaded ones of the clusters closely, placing the ternary content-addressable memory modules on a fastest available path between the input pins and the output pins, and placing those of the clusters with a higher input dependency on the fastest available path between said input pins and said output pins.

14. The apparatus of claim 10 , further comprising a plurality

Assignees

• Globalfoundries Inc

Inventors

• Brand Daniel
• Cho Minsik
• Puri Ruchir
• Sullivan Andrew J

Classifications

• G11C15/04 Primary

  using semiconductor elements · CPC title

• G11C15/00

  Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores · CPC title