Microfluidics planar placement and routing algorithm

Patent metadata

Field	Value
Publication number	US-10360336-B2
Application number	US-201715794957-A
Country	US
Kind code	B2
Filing date	Oct 26, 2017
Priority date	Oct 27, 2016
Publication date	Jul 23, 2019
Grant date	Jul 23, 2019

Abstract

A method of developing a physical design layout of microfluidic system chip can include receiving a planarized graph of a netlist including vertices representing microfluidic components. The vertices can be expanded into components, where each component includes a first dimension and a second dimension. The components can be shifted to a position where the first and second dimension of each component do not overlap with the first dimension and the second dimension of any other component. A flow route can be determined based on the first and second dimension of each component and the position of each component, the flow route including channels connecting two or more of the components.

First claim

What is claimed is:

1. A method of developing a physical design layout of microfluidic system chip, the method comprising:
receiving a planarized graph of a netlist including vertices representing microfluidic components;
expanding the vertices into components, each component including a first dimension and a second dimension;
shifting the components to a position where the first and second dimension of each component do not overlap with the first dimension and the second dimension of any other component; and
determining a flow route based on the first and second dimension of each component and the position of each component, the flow route including channels connecting two or more of the components.

2. The method of claim 1 , further comprising:
ordering the vertices before expanding the vertices.

3. The method of claim 1 , wherein determining the flow route is based on a set of grid points, the position of each component, the first and second dimensions of each component, and the location of each channel.

4. The method of claim 1 , further comprising:
shifting each component, individually, to a second position after determining a flow route, to reduce an area of the microfluidic system chip.

5. The method of claim 4 , further comprising:
rerouting the channels to produce a second flow route based on the second position.

6. The method of claim 1 , further comprising:
producing a planar embedding using the planarized graph including the vertices.

7. The method of claim 1 , further comprising:
exporting the physical design layout including positions of the components and channel routes connecting the components; and
adding a control layer to the physical design layout.

8. The method of claim 1 , wherein each component represents a microfluidic control device.

9. A method of developing a physical design layout of microfluidic system chip, the method comprising:
receiving a planarized graph of a netlist including vertices representing microfluidic components;
expanding the vertices into components, each component including a first dimension and a second dimension defining a component perimeter;
shifting the components to a position where the first and second dimension of each component do not overlap with the first dimension and the second dimension of any other component;
defining a chip area around the shifted components; and
routing channels to intersect with perimeters of source and destination components and to avoid other components, the channel route to remain within the chip area.

10. The method of claim 9 , further comprising:
ordering the components using circular propagation.

11. The method of claim 9 , further comprising:
routing channels that cannot be routed within the perimeter such that they are allowed to cross the perimeter twice.

12. The method of claim 11 , further comprising:
rerouting channels that intersect the perimeter to have a route running substantially parallel to the perimeter and to have only two intersections with the perimeter.

13. The method of claim 12 , further comprising:
expanding the perimeter to a second perimeter that encompasses the rerouted channels.

14. The method of claim 13 , further comprises:
trimming the chip area to the second perimeter.

15. The method of claim 9 , further comprising:
assigning a source port located on a first component of the components;
assigning a sink port located on a second component of the components; and
routing a port channel connecting the source port to the sink port based on locations of the source port and sink port, the first and second dimensions of the components, and locations of other channels.

16. The method of claim 9 , wherein shifting the components further comprises:
assigning a shift factor based on a distance between an expanded component of the components and the remaining components, based on dimensions of the expanded component, and based on the first and second dimension of the remaining components.

17. A non-transitory machine-readable medium including instructions, for developing a physical design layout of microfluidic system chip, which when executed by a machine, cause the machine to:
receive a planarized graph of a netlist including vertices representing microfluidic components;
expand the vertices into components, each component including a first dimension and a second dimension;
shift the components to a position where the first and second dimension of each component do not overlap with the first dimension and the second dimension of any other component; and
determine a flow route based on the first and second dimension of each component and the position of each component, the flow route including channels connecting two or more of the components.

18. The non-transitory machine-readable medium of claim 17 , the instructions to further cause the machine to:
assign a shift factor based on a distance between an expanded component of the components and the remaining components, based on dimensions of the expanded component, and based on the first and second dimension of the remaining components.

19. The non-transitory machine-readable medium of claim 17 , the instructions to further cause the machine to:
assign a source port located on a first component of the components;
assign a sink port located on a second component of the components; and
route a port channel connecting the source port to the sink port based on locations of the source port and sink port, the first and second dimensions of the components, and locations of other channels.

20. The non-transitory machine-readable medium of claim 17 , the instructions to further cause the machine to:
shift, individually, each component to a second position after determining a flow route to reduce an area of the microfluidic system chip; and
reroute the channels to produce a second flow route based on the second position.

Assignees

• Univ California

Inventors

• Brisk Philip
• Crites Brian
• Mcdaniel Jeffrey

Classifications

• G06F2111/06

  Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA] · CPC title

• G06F30/39

  Circuit design at the physical level (physical level design for reconfigurable circuits G06F30/347) · CPC title

• G06F2111/20

  Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules · CPC title

• B01L2300/0816

  Cards, e.g. flat sample carriers usually with flow in two horizontal directions · CPC title

• B81C99/006

  Design; Simulation · CPC title