Component placement tool for printed circuit board

• US 8,751,999 B2
• Filed: 07/05/2011
• Issued: 06/10/2014
• Est. Priority Date: 07/05/2011
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shibuya, Toshiyuki
• Primary Examiner(s): Dinh, Paul
• Application Number:
  US13/176,310
• Publication Number:
  US 20130014076A1
• Time in Patent Office: 1,071 Days
• Field of Search: 716110-111, 716118-119, 716/123, 716/137
• US Class Current: 716/137
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In one embodiment, creating a layout for a Printed Circuit Board (PCB) by creating n boundary lines at n locations, respectively, on the PCB and placing n sets of electronic components on the n boundary lines, respectively; and iteratively adjusting and evaluating the layout of the PCB until a set of layout requirements for the PCB has been satisfied.

Claims

1. A method comprising:

by one or more computing devices,

creating a layout for a Printed Circuit Board (PCB), comprising;

creating n boundary lines at n locations, respectively, on the PCB; and

randomly placing n sets of electronic components on the n boundary lines, respectively; and

iteratively adjusting and evaluating the layout of the PCB until a set of layout requirements for the PCB has been satisfied, and

wherein for iteratively evaluating the layout of the PCB, each iteration comprises;

computing a cost of the layout of the PCB based on the set of layout requirements;

generating, by a random value generating function, a random value;

computing a value to evaluate a currently best layout of the PCB, the value computed based on at least a cost of the currently best layout of the PCB and a current temperature controlling the iterative process; and

if the random value is less than the value, then;

setting the currently best layout of the PCB as the layout of the PCB; and

setting the cost of the currently best layout of the PCB as cost of the layout of the PCB.

2. The method of claim 1, further comprising representing the layout of the PCB with a Slicing Tree.

3. The method of claim 1, further comprising representing the layout of the PCB with a Polish Expression or Reverse Polish Expression.

4. The method of claim 1, wherein iteratively adjusting and evaluating the layout of the PCB is based on Simulated Annealing, such that the iterative process is controlled by a temperature, comprising:

setting the temperature to an initial value;

decreasing the temperature by a step value during each iteration; and

ending the iterative process when the temperature reaches a final value.

5. The method of claim 1, wherein for iteratively adjusting the layout of the PCB, each iteration comprises randomly performing one of:

swapping two randomly selected boundary lines;

swapping two randomly selected sets of electronic components;

moving one randomly selected component from a first randomly selected set of electronic components to a second randomly selected set of electronic components;

or

changing a ratio of a randomly selected boundary line to a random value between 0 and 1.

6. A system comprising:

a memory comprising instructions executable by one or more processors; and

the one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to;

create a layout for a Printed Circuit Board (PCB), comprising;

create n boundary lines at n locations, respectively, on the PCB; and

randomly place n sets of electronic components on the n boundary lines, respectively; and

iteratively adjust and evaluate the layout of the PCB until a set of layout requirements for the PCB has been satisfied, and

wherein for iteratively evaluating the layout of the PCB, each iteration comprises;

computing a cost of the layout of the PCB based on the set of layout requirements;

generating, by a random value generating function, a random value;

computing a value to evaluate a currently best layout of the PCB, the value computed based on at least a cost of the currently best layout of the PCB and a current temperature controlling the iterative process; and

if the random value is less than the value, then;

setting the currently best layout of the PCB as the layout of the PCB; and

setting the cost of the currently best layout of the PCB as cost of the layout of the PCB.

7. The system of claim 6, wherein the one or more processors are further operable when executing the instructions to represent the layout of the PCB with a Slicing Tree.

8. The system of claim 6, wherein the one or more processors are further operable when executing the instructions to represent the layout of the PCB with a Polish Expression or Reverse Polish Expression.

9. The system of claim 6, wherein iteratively adjusting and evaluating the layout of the PCB is based on Simulated Annealing, such that the iterative process is controlled by a temperature, comprising:

set the temperature to an initial value;

decrease the temperature by a step value during each iteration; and

end the iterative process when the temperature reaches a final value.

10. The system of claim 6, wherein for iteratively adjusting the layout of the PCB, each iteration comprises randomly performing one of:

swap two randomly selected boundary lines;

swap two randomly selected sets of electronic components;

move one randomly selected component from a first randomly selected set of electronic components to a second randomly selected set of electronic components;

or

change a ratio of a randomly selected boundary line to a random value between 0 and 1.

11. One or more computer-readable non-transitory storage media embodying software operable when executed by one or more computer systems to:

create a layout for a Printed Circuit Board (PCB), comprising;

create n boundary lines at n locations, respectively, on the PCB; and

randomly place n sets of electronic components on the n boundary lines, respectively; and

iteratively adjust and evaluate the layout of the PCB until a set of layout requirements for the PCB has been satisfied, and

wherein for iteratively evaluating the layout of the PCB, each iteration comprises;

compute a cost of the layout of the PCB based on the set of layout requirements;

generate, by a random value generating function, a random value;

compute a value to evaluate a currently best layout of the PCB, the value computed based on at least a cost of the currently best layout of the PCB and a current temperature controlling the iterative process; and

if the random value is less than the value, then;

set the currently best layout of the PCB as the layout of the PCB; and

set the cost of the currently best layout of the PCB as cost of the layout of the PCB.

12. The media of claim 11, wherein the software is further operable when executed by the one or more computer systems to represent the layout of the PCB with a Slicing Tree.

13. The media of claim 11, wherein the software is further operable when executed by the one or more computer systems to represent the layout of the PCB with a Polish Expression or Reverse Polish Expression.

14. The media of claim 11, wherein iteratively adjusting and evaluating the layout of the PCB is based on Simulated Annealing, such that the iterative process is controlled by a temperature, comprising:

set the temperature to an initial value;

decrease the temperature by a step value during each iteration; and

end the iterative process when the temperature reaches a final value.

15. The media of claim 11, wherein for iteratively adjusting the layout of the PCB, each iteration comprises randomly performing one of:

swap two randomly selected boundary lines;

swap two randomly selected sets of electronic components;

move one randomly selected component from a first randomly selected set of electronic components to a second randomly selected set of electronic components;

or

change a ratio of a randomly selected boundary line to a random value between 0 and 1.

16. A system comprising:

means for creating a layout for a Printed Circuit Board (PCB), comprising;

means for creating n boundary lines at n locations, respectively, on the PCB; and

means for randomly placing n sets of electronic components on the n boundary lines, respectively; and

means for iteratively adjusting and evaluating the layout of the PCB until a set of layout requirements for the PCB has been satisfied, and

wherein, for each iteration, the means for iteratively evaluating the layout of the PCB comprises;

means for computing a cost of the layout of the PCB based on the set of layout requirements;

means for generating, by a random value generating function, a random value;

means for computing a value to evaluate a currently best layout of the PCB, the value computed based on at least a cost of the currently best layout of the PCB and a current temperature controlling the iterative process; and

if the random value is less than the value, then;

means for setting the currently best layout of the PCB as the layout of the PCB; and

means for setting the cost of the currently best layout of the PCB as cost of the layout of the PCB.