Optimizing chain placement in a programmable logic device

• US 5,838,584 A
• Filed: 04/04/1997
• Issued: 11/17/1998
• Est. Priority Date: 01/27/1995
• Status: Expired due to Term

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Kazarian, Peter J.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Fiul, Dan
• Application Number:
  US08/825,838
• Time in Patent Office: 592 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 326/39, 326/40, 365/185.22
• US Class Current: 716/102
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A technique is used to implement chains into a programmable logic device. In one embodiment, the method includes solving a bin packing problem (step 105), test-placing a chain in each logic element position (step 401), forming groups of unused logic element positions (step 405), determining whether future chains can be placed in these remaining unused logic element positions (step 410), comparing each placement against a previously stored placement, and storing the logic element position of the more efficient logic element positions have been checked (step 210). In the end, a substantially optimum placement for each chain is found.

Claims

1. A method of implementing logical functions in a programmable logic device comprising the steps of:

inputting design characteristics, said design characteristics defining a plurality of chains wherein a chain is a group of linked circuit elements, into a programmed digital computer;

in said programmed digital computer, solving a bin packing problem for said design characteristics after chain placement, each bin comprising a plurality of logic elements linked in a linear fashion, wherein a routing of said logic elements is predetermined;

programming said programmable logic device with a result of said solving step; and

using said programmable logic device to implement said logical functions.

2. The method of claim 1 wherein said step of solving a bin packing problem is exhaustive.

3. The method of claim 1 wherein said step of solving a bin packing problem comprises:

determining whether placing a chain of said design characteristics at one of a plurality of logic element positions will block future chains from being placed.

4. The method of claim 3 further comprising the step of:

repeating said determining step until a number of chains placeable in a logic array block is substantially maximized.

5. The method of claim 3 further comprising the step of:

repeating said determining step until said plurality of logic element positions in a logic array block are substantially occupied.

10. The method of claims 4, 5, 6, or 9 wherein said logic array block has eight or less logic elements.

11. The method of claims 4, 5, 6, or 9 wherein said logic array block has sixteen logic elements.

12. The method of claims 4, 5, 6, or 9 wherein said logic array block has at least two groups of eight or less elements.

13. The method of claims 3, 6, 7, or 9 wherein said determining step is performed serially.

14. The method of claim 1 wherein said programming step comprises:

based on a result of said solving step, using said programmed digital computer, selecting a size of programmable logic device; and

programming said selected programmable logic device with said result of said solving step.

15. The method of claim 1 wherein said programming step comprises:

based on a result of said solving step, using said programmed digital computer, selecting a particular programmable logic device to increase an operating speed of said design characteristics; and

programming said selected particular programmable logic device with said result of said solving step.

16. The method of claims 3, 6, or 9 wherein said programming step comprises:

based on a result of said determining step, selecting a size of programmable logic device; and

programming said selected programmable logic device with said result of said determining step.

17. The method of claims 3, 6, or 9 wherein said programming step comprises:

based on a result of said determining step, selecting a particular programmable logic device to increase an operating speed of said design characteristics; and

programming said selected particular programmable logic device with said result of said determining step.

18. The method of claim 3 further comprising the step of:

repeating said determining step until signals in said programmable logic device are routable.

19. The method of claim 3 further comprising the step of:

repeating said determining step until a number of chains placeable in a logic array block is substantially maximized and signals in said programmable logic device are routable.

20. The method of claim 3 further comprising the step of:

repeating said determining step until said plurality of logic element positions in a logic array block are substantially occupied and signals in said programmable logic device are routable.

6. A method for programming a programmable logic device, having a plurality of logic array blocks, each logic array block comprising a plurality of logic elements, comprising the steps of:

inputting design characteristics, said design characteristics defining a plurality of chains, into a programmed digital computer;

in said programmed digital computer, determining whether placing a chain of said design characteristics at one of a plurality of logic element positions in a logic array block of said plurality of logic array blocks will block future chains from being placed in said logic array block, wherein said logic array block comprises a plurality of logic element positions organized in a linear linked structure having predetermined routing;

repeating said determining step for said plurality of logic element positions in said logic array block; and

programming said programmable logic device with a result of said repeating step.

7. The method of claim 6 wherein said determining step comprises the steps of:

forming groups of consecutive empty logic element chains of a logic array block when a chain of said plurality of chains is placed at one of a plurality of logic element positions; and

determining whether remaining chains of said plurality of chains can fit into said groups of consecutive empty logic element chains of said logic array block.

8. The method of claim 7 further wherein said determining step comprises:

comparing a first size of said groups of consecutive empty logic element chains resulting from said forming step against a second size of said groups of consecutive empty logic element chains resulting from a previous forming step; and

storing a logic element position for a smaller of said first size and said second size resulting from said comparing step.

9. A method of programming a programmable logic device comprising the steps of:

inputting design characteristics, said design characteristics comprising a plurality of chains, into a computing machine;

forming groups of consecutive empty logic element chains for said logic array block when a chain of said plurality of chains is placed at a logic element position of a plurality of logic element positions in said logic array block;

determining whether remaining carry chains of said plurality of chains can fit into said groups of consecutive empty logic element chains of said logic array block, wherein said logic array block comprises a plurality of logic element positions organized in a linear linked structure having predetermined routing;

repeating said forming and determining steps until said plurality of logic element positions in said logic array block are substantially occupied; and

programming said programmable logic device with a result of said repeating step.

21. A computer program product comprising computer usable medium having computer readable code embodied therein for causing the implementation of chains in a programmable integrated circuit, said computer program product comprising:

computer readable code device configured to cause a computer to effect inputting design characteristics defining a plurality of chains wherein a chain is a group of linked circuit elements;

computer readable code device configured to cause a computer to effect solving a bin packing problem for said design characteristics after chain placement, each bin comprising a plurality of logic elements linked in a linear fashion, wherein a routing of said logic elements is predetermined; and

computer readable code device configured to cause a computer to effect programming said programmable logic device with a result of solving said bin packing problem.

22. The computer program product of claim 21 wherein said computer readable code device configured to cause a computer to effect solving a bin packing problem for said design characteristics after chain placement comprises:

computer readable code device configured to cause a computer to effect determining whether placing a chain of said design characteristics at one of a plurality of logic element positions will block future chains from being placed.

23. The computer program product of claim 22 further comprising:

computer readable code device configured to cause a computer to effect repeating said determining step until a number of chains placeable in a logic array block is substantially maximized.

24. The computer program product of claim 22 further comprising:

computer readable code device configured to cause a computer to effect repeating said determining step until said plurality of logic element positions in a logic array block are substantially occupied.

25. A computer program product comprising computer usable medium having computer readable code embodied therein for causing the implementation of chains in a programmable integrated circuit, said computer program product comprising:

computer readable code device configured to cause a computer to effect inputting design characteristics, said design characteristics defining a plurality of chains;

computer readable code device configured to cause a computer to effect determining whether placing a chain of said design characteristics at one of a plurality of logic element positions in a logic array block of said plurality of logic array blocks will block future chains from being placed in said logic array block, wherein said logic array block comprises a plurality of logic element positions organized in a linear linked structure having predetermined routing; and

computer readable code device configured to cause a computer to effect repeating said determining step for said plurality of logic element positions in said logic array block.

26. The computer program product of claim 25 wherein said computer readable code device configured to cause a computer to effect solving a bin packing problem for said design characteristics after chain placement comprises:

computer readable code device configured to cause a computer to effect forming groups of consecutive empty logic element chains of a logic array block when a chain of said plurality of chains is placed at one of a plurality of logic element positions; and

computer readable code device configured to cause a computer to effect determining whether remaining chains of said plurality of chains can fit into said groups of consecutive empty logic element chains of said logic array block.

27. The computer program product of claim 26 wherein said computer readable code device configured to cause a computer to effect solving a bin packing problem for said design characteristics after chain placement comprises:

computer readable code device configured to cause a computer to effect comparing a first size of said groups of consecutive empty logic element chains resulting from said forming step against a second size of said groups of consecutive empty logic element chains resulting from a previous forming step; and

computer readable code device configured to cause a computer to effect storing a logic element position for a smaller of said first size and said second size resulting from said comparing step.