Method for determining a matched routing arrangement for semiconductor devices

• US 20050050508A1
• Filed: 08/25/2004
• Published: 03/03/2005
• Est. Priority Date: 08/28/2002
• Status: Active Grant

• Current Assignee: Brooklin J. Gore, Matthew L. Priest, Michael D. Lee
• Original Assignee: Brooklin J. Gore, Matthew L. Priest, Michael D. Lee
• Inventors: Lee, Michael D., Gore, Brooklin J., Priest, Matthew L.
• Granted Patent: US 7,210,110 B2
• Time in Patent Office: Days
• US Class Current: 716/126
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

The present invention relates to a method for determining a matched routing netlist for a semiconductor device. In a particular embodiment, a topological plan for the microelectronic device is compiled and used to calculate a population of netlists. The netlists are then dynamically modified using a genetic algorithm to generate a matched netlist for the device.

Claims

1. A method for determining matched netlists for a microelectronic device, comprising:

compiling a topological plan for the microelectronic device;

determining nets to be matched in the topological plan

calculating a first netlist solution corresponding to the plan;

dynamically modifying the first netlist solution using a genetic algorithm to generate a first successive population of second netlist solutions that approach a matched netlist for the device;

calculating fitness values that indicate how well nets to be matched are matched in the second netlist solutions from the first successive population; and

selecting at least one of the second netlist solutions from the first successive population based on how well the fitness value indicates the nets to matched are matched in the second netlist solutions.

29. The method of claim 1, further comprising dynamically modifying the population of the second netlist solutions by applying crossover and mutation to the second netlist solutions to generate a second successive population containing third netlist solutions;

calculating fitness values for the third netlist solutions from the second successive population; and

selecting at least one of the third netlist solutions from the second successive population based on how well the fitness values for the third netlist solutions indicates the nets to matched are matched in the third netlist solutions.

30. The method of claim 1, wherein calculating the fitness values for the netlist solutions comprises forming a sum of a source coefficient multiplied by a source balance factor, a group coefficient multiplied by a group balance factor, and a weight coefficient multiplied by a sum of the routing weights.

31. The method of claim 30, wherein calculating the fitness values further comprises calculating the source balance factor by forming the difference between a maximum weight and a minimum weight for common source nets.

32. The method of claim 30, wherein calculating the fitness values further comprises calculating the group balance factor by forming the difference between a maximum weight and a minimum weight for common group nets.

33. The method of claim 30, wherein calculating the fitness values further comprises assigning a value to the source coefficient and the group coefficient of approximately about two.

34. The method of claim 30, wherein calculating the fitness values further comprises assigning a value to the weight coefficient of approximately about one-half.

35. The method of claim 1, further including, establishing an initial population of first netlists by successively mutating the first established netlist to obtain the initial population and dynamically modifying the first netlist includes dynamically modifying the population of first netlists.

36. The method of claim 1, wherein calculating the first netlist solution comprises calculating a population of minimum length netlists corresponding to the plan.

37. The method of claim 29, wherein dynamically modifying the population of the second netlist solutions further comprises:

associating a randomly generated number with the second netlist solutions;

comparing the number with a preselected crossover probability; and

performing the crossover based on the comparison.

38. The method of claim 29, wherein dynamically modifying the population of the second netlist solutions further comprises:

associating a randomly generated number with the second netlist solutions;

comparing the number with a preselected mutation probability; and

performing the mutation based on the comparison.

39. The method of claim 1, wherein compiling a topological plan comprises:

identifying cells within the device and pins coupled to the cells;

providing a description of the vertices to be coupled;

describing the channels extending between the vertices; and

specifying the nets that are to be matched.

40. The method of claim 39, wherein providing a description of the vertices to be coupled further comprises compiling a vertex matrix for the device.

41. The method of claim 39, wherein describing the channels extending between the vertices further comprises compiling a channel table for the device.

42. The method of claim 39, wherein specifying the nets that are to be matched further comprises compiling a route table for the device.

2-28. -28. (Cancelled)

43. A method for generating a matched netlist for a microelectronic device, comprising:

generating a first population of netlists for the device;

evaluating the generated netlists according to a predetermined fitness criterion that determines how well nets to be matched are matched in the first population of netlists and generating a fitness value for each netlist based upon the evaluation;

comparing the fitness values and selecting a pair of netlists based on the comparison; and

performing a crossover of the pair of selected netlists to generate a pair of offspring netlists; and

performing a mutation of at least one of the offspring netlists.

44. The method of claim 43, wherein evaluating the netlists according to a predetermined fitness criterion further comprises calculating the fitness value by forming a sum of a source coefficient multiplied by a source balance factor, a group coefficient multiplied by a group balance factor, and a weight coefficient multiplied by a sum of the routing weights.

45. The method of claim 44, wherein calculating the fitness value further comprises calculating the source balance factor by forming a difference between a maximum weight and a minimum weight for common source routes.

46. The method of claim 44, wherein calculating the fitness value further comprises calculating the group balance factor by forming a difference between a maximum weight and a minimum weight for common group routes.

47. The method of claim 44, wherein calculating the fitness value further comprises assigning a value to the source coefficient and the group coefficient of at least about two.

48. The method of claim 44, wherein calculating the fitness value further comprises assigning a value to the weight coefficient of at least about one-half.

49. The method of claim 43, wherein comparing the fitness values and selecting at least two netlists further includes selecting the pair of netlists using a tournament selection procedure.

50. The method of claim 43, wherein performing a crossover of the pair of netlists further comprises:

selecting a net from a first one of the pair of netlists by a random selection process;

selecting a net from a second one of the pair of netlists by a random selection process;

interchanging the net from the first one of the pair of netlists and the net from the second one of the pair of netlists to obtain a pair of offspring netlists.

51. The method of claim 50, further comprising generating a random number and comparing the random number to a predetermined crossover probability and performing the crossover based upon the comparison.

52. The method of claim 51, wherein generating a random number and comparing the random number to a predetermined crossover probability further comprises comparing the random number to a crossover probability of approximately about 0.8.

53. The method of claim 43, wherein performing a mutation of at least one of the offspring netlists further comprises:

selecting a net from a first one of the pair of netlists by a random selection process;

selecting a first vertex in the selected net by a random selection process;

selecting a second vertex in the selected net by a random selection process;

adding a segment length that extends from the first vertex to the second vertex and recursively extends to the first vertex; and

including the segment length to the selected net.

54. The method of claim 53, further comprising generating a random number and comparing the random number to a predetermined mutation probability and performing the mutation based upon the comparison.

55. The method of claim 54, wherein generating a random number and comparing the random number to a predetermined mutation probability further comprises comparing the random number to a crossover probability of approximately about 0.2.