Implementation of factor graphs

• US 8,627,246 B2
• Filed: 01/13/2011
• Issued: 01/07/2014
• Est. Priority Date: 01/13/2010
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Hershey, Shawn, Vigoda, Benjamin
• Primary Examiner(s): Dinh, Paul
• Application Number:
  US13/006,060
• Publication Number:
  US 20120159408A1
• Time in Patent Office: 1,090 Days
• Field of Search: 716100-104, 716110-113
• US Class Current: 716/100
• CPC Class Codes: G06F 30/331 with hardware acceleration, e.g. by using field programmable gate array [FPGA] or emulation

Abstract

The process of implementing a belief propagation network in software and/or hardware can begin with a factor-graph-designer who designs a factor graph that implements that network. A development system provides a user with a way to specify a factor graph at a high or abstract level, and then solve the factor graph, or make an instance of the factor graph in software and/or hardware based on the specification. Factor graphs enable designers to create a graphical model of complicated belief propagation networks such as Markov chains, hidden Markov models, and Bayesian networks.

Claims

1. A computer-implemented method for generating a hardware description of a belief propagation network, said method comprising:

receiving an initial representation of a belief propagation network representing a graphical model for performing inference having a factor graph that includes a first class of nodes representing variables and a second class of nodes representing constraints between variables, the nodes being connected by edges;

receiving a specification indicating that that a hardware element is to be used to implement at least two nodes of said factor graph;

generating empty nodes for receiving information representative of hardware modules each having one or more hardware elements for physically implementing said nodes; and

on the basis of said initial representation and said specification, generating, by using a computer, a hardware representation of an electronic circuit for implementing said factor graph.

2. The method of claim 1, wherein generating a hardware representation comprises generating a hardware descriptor language representation of said specification.

3. The method of claim 1, wherein generating a hardware representation comprises generating a VERILOG representation of said specification.

4. The method of claim 1, further comprising receiving a specification of hardware to be placed in said nodes.

5. The method of claim 1, wherein receiving said specification comprises receiving a specification of function nodes to be implemented by a particular XOR-processor.

6. The method of claim 1, wherein receiving said specification comprises receiving a specification of variable nodes to be implemented by a particular equals-processor.

7. The method of claim 1, further comprising specifying additional hardware elements to enable said hardware element to realize at least two nodes of said factor graph.

8. The method of claim 7, wherein specifying additional hardware elements comprises specifying at least one switch.

9. The method of claim 7, wherein specifying additional hardware elements comprises specifying at least one memory element.

10. The method of claim 1, further comprising providing said hardware representation to a hardware simulator for simulation of said belief propagation network.

11. The method of claim 1, further comprising providing said hardware representation to a floor planner for generating a floor plan of an integrated circuit for implementing said belief propagation network.

14. The non-transitory machine readable medium of claim 1, wherein said instructions, when executed by the data processing system, cause the system to generate a VERILOG representation of said specification.

12. A non-transitory machine readable medium having instructions encoded thereon, said instructions, when executed by a data processing system, cause the system to

receive an initial representation of a belief propagation network representing a graphical model for performing inference having a factor graph that includes a first class of nodes representing variables and a second class of nodes representing constraints between variables, the nodes being connected by edges;

receive a specification indicating that that a hardware element is to be used to implement at least two nodes of said factor graph;

generate empty nodes for receiving information representative of hardware modules each having one or more hardware elements for physically implementing said nodes; and

on the basis of said initial representation and said specification, generate a hardware representation of an electronic circuit for implementing said factor graph.

13. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, further cause the system to generate a hardware representation comprise instructions for causing said data processing system to generate a hardware descriptor language representation of said specification.

15. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, further cause the system to receive a specification of hardware to be placed in said nodes.

16. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, cause the system to receive said specification comprise instructions for receiving a specification of function nodes to be implemented by a particular XOR-processor.

17. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, cause the system to receive a specification of variable nodes to be implemented by a particular equals-processor.

18. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, cause the system to specify additional hardware elements to enable said hardware element to realize at least two nodes of said factor graph.

19. The non-transitory machine readable medium of claim 18, wherein said instructions, when executed by the data processing system, cause the system to specify at least one switch.

20. The non-transitory machine readable medium of claim 18, wherein said instructions, when executed by the data processing system, cause the system to specify at least one memory element.

21. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, cause the system to provide said hardware representation to a hardware simulator for simulation of said belief propagation network.

22. The non-transitory machine readable medium of claim 12, wherein said instructions, when executed by the data processing system, cause the system to provide said hardware representation to a floor planner for generating a floor plan of an integrated circuit for implementing said belief propagation network.