# US 2012/0084742 A1 · Method and apparatus for using entropy in ant colony optimization circuit design from high level synthesis

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084742 A1
- Document ID: US20120084742A1
- Status: Published application
- Kind: A1
- Application number: 12/894,756
- Filed: 2010-09-30
- Published: 2012-04-05
- Earliest claimed: 2010-09-30
- Assignees: Synopsys, Inc.
- Inventors: Mustafa Ispir; Levent Oktem
- Web page: https://patentgrep.com/patent/US20120084742A1

## CPC

- G06F 30/30: Circuit design
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A method and apparatus for using entropy in ant colony optimization circuit design from high level synthesis is described. In one example, an operation to be performed by a circuit is selected. A plurality of hardware components for performing the operation are represented with a data flow graph having edges and nodes. A plurality of solutions for performing the operation are simulated as hardware component combinations represented as paths on the data flow graph. For each solution the cost including a number of edges and nodes traversed on the data flow graph and a supplemental sub-integer cost is determined and a solution is selected with the lowest cost as a hardware component combination for a circuit.

## Claims

### Claim 1

A method comprising:
selecting an operation to be performed by a circuit;
representing, through a data flow graph having edges and nodes, a plurality of hardware components for performing the operation;
simulating a plurality of solutions for performing the operation, each solution corresponding to a hardware component combination represented as a path on the data flow graph;
determining a cost for each solution of the plurality of solutions, the cost including a number of edges and nodes traversed on the data flow graph and a supplemental sub-integer cost; and
selecting a solution from among the plurality of solutions, the selected solution having a lowest determined.

### Claim 2 (depends on 1)

The method of claim 1, wherein the supplemental sub-integer cost is a virtual cost.

### Claim 3 (depends on 1)

The method of claim 1, wherein the supplemental cost is a normalized value of an entropy of a number of steps to complete the respective solution.

### Claim 4 (depends on 1)

The method of claim 1, wherein the supplemental sub-integer cost is based on a value of an entropy of a histogram of operations

### Claim 5 (depends on 1)

The method of claim 1, wherein determining a cost comprises creating a histogram array of a number of steps of each simulated solution.

### Claim 6 (depends on 5)

The method of claim 5, wherein the number of steps comprises the number of edges traversed on the data flow graph for each solution.

### Claim 7 (depends on 6)

The method of claim 6, further comprising determining a probability of each simulated solution based on the histogram value and the number of operations of the respective solution and wherein the supplemental sub-integer cost is a function of the probability.

### Claim 8 (depends on 1)

The method of claim 1, wherein simulating a plurality of solutions comprises simulating each step through the data flow graph for each solution, each step comprising traversing an edge between two nodes of the data flow graph.

### Claim 9 (depends on 8)

The method of claim 8, further comprising associating a pheromone trail with each traversed edge.

### Claim 10 (depends on 1)

The method of claim 1, wherein simulating a plurality of solutions comprises heuristically searching for local solutions.

### Claim 11 (depends on 1)

The method of claim 1, wherein simulating a plurality of solutions comprises performing an ant colony optimization and wherein determining a cost further comprises applying a cost to increment a pheromone value of an edge in the data flow graph.

### Claim 12

A non-transitory computer-readable medium storing instructions thereon, the instructions when executed by a processor causing the processor to:
select an operation to be performed by a circuit;
represent, through a data flow graph having edges and nodes, a plurality of hardware components for performing the operation;
simulate a plurality of solutions for performing the operation, each solution corresponding to a hardware component combination represented as a path on the data flow graph;
determine a cost for each solution of the plurality of solutions, the cost including a number of edges and nodes traversed on the data flow graph and a supplemental sub-integer cost; and
select a solution from among the plurality of solutions, the selected solution having a lowest determined cost.

### Claim 13 (depends on 12)

The computer-readable medium of claim 12, wherein determining a cost comprises creating a histogram array of a number of steps of each simulated solution.

### Claim 14 (depends on 13)

The computer-readable medium of claim 13, wherein the number of steps comprises a number of edges traversed on the data flow graph for each solution.

### Claim 15 (depends on 14)

The computer-readable medium of claim 14, further comprising determining a probability of each simulated solution based on a histogram value and a number of operations of the respective solution and wherein the supplemental sub-integer cost is a function of the probability.

### Claim 16 (depends on 12)

The computer-readable medium of claim 12, wherein simulating a plurality of solutions comprises simulating each step through the data flow graph for each solution, each step comprising traversing an edge between two nodes of the data flow graph.

### Claim 17 (depends on 16)

The computer-readable medium of claim 16, further comprising associating a pheromone trail with each traversed edge.

### Claim 18

A digital processing system comprising:
means for selecting an operation to be performed by a circuit;
means for representing, through a data flow graph having edges and nodes, a plurality of hardware components for performing the operation;
means for simulating a plurality of solutions for performing the operation, each solution corresponding to a hardware component combination represented as a path on the data flow graph;
means for determining a cost for each solution of the plurality of solutions, the cost including a number of edges and nodes traversed on the data flow graph and a supplemental sub-integer cost; and
means for selecting a solution from among the plurality of solutions, the selected solution having a lowest cost.

### Claim 19 (depends on 18)

The system of claim 18, wherein the supplemental sub-integer cost is a normalized value of an entropy of a number of steps to complete the respective solution.

### Claim 20 (depends on 18)

The system of claim 18, wherein the supplemental sub-integer cost is based on a value of an entropy of a histogram of operations.

### Claim 21

An apparatus comprising:
a memory to store a data flow graph representing a plurality of hardware components for performing at least one operation, the data flow graph having edges and nodes;
a solution simulator coupled to the memory to receive the data flow graph and to simulate a plurality of solutions for performing the operation as hardware component combinations represented as paths on the data flow graph;
a cost estimator coupled to the solution simulator to receive the solutions and to determine a cost for each solution, the cost including a number of edges and nodes traversed on the data flow graph and a supplemental sub-integer cost; and
a solution selector coupled to the cost estimator to receive the estimated costs and to select a solution with the lowest cost as a hardware component combination for a circuit.

### Claim 22 (depends on 21)

The apparatus of claim 21, further comprising an operation and variable binder to bind variable to the operation before supplying the data flow graph to the solution simulator.

### Claim 23 (depends on 21)

The method of claim 21, wherein the supplemental cost is based on a value of the entropy of a histogram of operations
