[go: up one dir, main page]

WO1992009042A1 - Placement logique utilisant un algorithme de decoupage a positionnement asymetrique - Google Patents

Placement logique utilisant un algorithme de decoupage a positionnement asymetrique Download PDF

Info

Publication number
WO1992009042A1
WO1992009042A1 PCT/US1991/008311 US9108311W WO9209042A1 WO 1992009042 A1 WO1992009042 A1 WO 1992009042A1 US 9108311 W US9108311 W US 9108311W WO 9209042 A1 WO9209042 A1 WO 9209042A1
Authority
WO
WIPO (PCT)
Prior art keywords
elements
partitioning
group
cell
cut
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/US1991/008311
Other languages
English (en)
Inventor
Mon Ren Chene
Stephen M. Trimberger
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Xilinx Inc
Original Assignee
Xilinx Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US07/784,844 external-priority patent/US5224056A/en
Application filed by Xilinx Inc filed Critical Xilinx Inc
Publication of WO1992009042A1 publication Critical patent/WO1992009042A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/30—Circuit design
    • G06F30/39—Circuit design at the physical level
    • G06F30/392—Floor-planning or layout, e.g. partitioning or placement

Definitions

  • the present invention is generally directed to a method for partitioning and placing components of a circuit design into a programmable integrated circuit device which can be configured to implement the design.
  • the invention is more specifically directed to a modified placement by partitioning method used for initial or "rough" placement of a circuit design into a field-programmable gate array (FPGA).
  • FPGA field-programmable gate array
  • VLSI design comprises the steps of circuit design, in which a schematic design resembling a desired circuit is created; and layout, in which an actual VLSI device is planned and produced to perform the function described in the schematic design.
  • the VLSI device may be a custom circuit which is produced on a silicon substrate by wafer fabrication processes, or the VLSI device may be a circuit design which is incorporated into a programmable integrated circuit device (PICD) such as a field programmable gate array (FPGA).
  • PICD programmable integrated circuit device
  • FPGA field programmable gate array
  • the goal of the layout process is to efficiently construct a device which minimizes layout area and signal propagation delays between associated logic elements.
  • the layout process is generally divided into two separate procedures: placement and routing.
  • Placement is the assignment of elements of a circuit design to specified areas of a VLSI circuit. The total required layout area and the signal propagation delays between connected elements are considered in the selection of locations for each element. Routing is the formation of an interconnection network connecting associated elements of the circuit design.
  • placement and routing processes are relatively simple and can be done manually by a skilled practitioner.
  • VLSI design is typically far too complicated for a skilled practitioner to perform un-aided placement and routing efficiently. For this reason, computer-aided design tools have been developed.
  • VLSI Cell Placement Techniques K. Shahookar and P. Mazumder, ACM Computing Surveys, Vol. 23, No. 2, June, 1991 (pages 143-220).
  • the five algorithms identified in this article are placement by partitioning, simulated annealing, force-directed placement, numerical optimization techniques and placement by genetic algorithm.
  • two or more algorithms may be used during the layout process of VLSI design, the present invention is concerned only with placement by partitioning.
  • Min-cut is a numeric algorithm wherein a circuit design is repeatedly partitioned into smaller and smaller groups of constituent elements while the number of nets interconnecting one group to another group is kept to a minimum. In minimizing the number of interconnecting nets, the Min-cut algorithm attempts to create an efficient physical layout of the elements for implementation on a VLSI chip.
  • Partitioning a circuit design may be done from the bottom up or from the top down, or both.
  • Bottom-up partitioning begins with grouping individual elements of a circuit design into larger units.
  • Copending application serial no. 07/456,010 [attorney docket M-904] describes such a method.
  • Top-down partitioning begins with dividing the entire circuit design into two sections, then four, and so forth until a stop condition is satisfied. The algorithm presented in this application incorporates the latter of these two methods.
  • the top-down Min-cut algorithm first identifies each element of a circuit design, and each element's interconnection with every other element of the circuit design. For instance, an AND gate may be designated as element 1. Element 1 may have two inputs from elements 2 and 3, and have one output to element 4. Each of the interconnections between element 1 and elements 2, 3 and 4 is given a value of one.
  • the Min-cut algorithm begins by arbitrarily partitioning (dividing) the total number of elements of the circuit design into two groups. For instance, as shown in Fig. 5a, if a circuit design has 100 elements, the algorithm would divide the elements into subcircuit groups 1 (elements ai to aso) and 2 (elements bi to bso).
  • a partition "line" PL is defined as an imaginary line disposed between the two groups.
  • Some elements of subcircuit group 1 are typically connected to elements in group 2. For example, element a3 is connected only to elements a 2 and as, while element a is connected to elements a ⁇ in group 1 and also to elements D 3 and b 5 in group 2.
  • an initial count is made of the number of cut nets. For instance, four nets are shown to be cut by partition line PL in Fig. 5a.
  • the algorithm then systematically exchanges each of the elements of the two subcircuit groups, and the number of cut nets resulting from each exchange are counted and stored. After the storage of each cut net count, the elements are returned to their original subcircuit group and a next pair of elements are exchanged.
  • Fig. 5b illustrates an exchange between elements a 4 and b 3 . As shown, the calculated cut net count is seven, which is an increase of three cut nets above the initial cut net count of four shown in Fig. 5a.
  • Fig. 5c shows an exchange of elements a- and bs. As shown, the resulting calculated cut net count is three, yielding a gain of -1. After every combination of elements has been exchanged, the gains from each exchanged pair of elements are compared and the best gain (lowest calculated cut net count) is identified and stored. The elements which were exchanged to obtain the best gain are then "swapped" between the subcircuit groups and then ignored by the algorithm in the next exchange cycle. For example, if the swap shown in Fig.
  • the swap of elements resulting in a "best gain” may represent a larger number of cut nets than before the swap of elements.
  • the gain resulting from the exchange shown in Fig. 5b may represent a best gain of +3.
  • the best gain may be thought of as a "least degradation” value.
  • the best gain or "least degradation” number is stored as a best gain value. This practice recognizes that some swaps may yield short term increases in the number of cut nets, but subsequent swaps may result in an eventual decrease in the number of cut nets.
  • the algorithm compares all 50 of the best gain values from the swapping sequences, and determines which of the 50 swaps resulted in a lowest best gain value. The algorithm then "keeps" all of the swaps occurring before the lowest best gain swap and all swaps occurring after the lowest best gain swap are undone.
  • subcircuit group 1 contains several "b” elements and subcircuit group 2 contains several "a” elements. All original and newly acquired subcircuit group 1 elements are then renumbered as "a” elements and subcircuit group 2 elements are renumbered as "b” elements.
  • the algorithm repeats the exchanging and swapping sequences for all 50 newly designated "a” elements and 50 newly designated "b” elements.
  • the original Min-cut algorithm is limited in various ways, and numerous modifications have been proposed.
  • One limitation is that the two groups created by a partition are required to contain an equal number of elements.
  • An improved Min-cut algorithm developed by C. M. Fiduccia and R. M. Mattheyses modifies the original Min-cut algorithm by allowing a selectable imbalance between two subcircuit groups.
  • the Fiduccia/Mattheyses modified .
  • algorithm does not swap pairs of elements across a partitioning line but rather picks a single element in one group and moves it to the other group.
  • the algorithm checks for a decrease in the number of interconnecting nets cut by the partitioning line.
  • the algorithm also checks the imbalance which is created by such a move. If the move creates an imbalance above a predetermined threshold, then it is undone.
  • Min-cut algorithm treats all cut nets as having an equal "cost". That is, every cut net is given a "cost" of one, and the total number of cut nets is simply their sum. However, it is recognized that some nets are more "important" than others.
  • a high fan-out signal such as a clock line might be given low priority while a multiplexer output which is part of a critical path or a carry line between arithmetic digits might have high priority.
  • a modified Min-cut algorithm developed by C. Sechen and Dahe Chen assigns a weighted cost to each net. Nets which are determined to be important are given a high cost, for instance, two or five. Nets which are unimportant are given a low cost such as 0.5 or 0.0. The result is that the Sechen/Chen Min-cut algorithm recognizes gains which may not be recognized using the original Min-cut algorithm.
  • Sechen and Chen also generate a cost for cut nets that is lower when the pins on the net are unbalanced on the two sides of a cut.
  • This improved cost function leads the Min-cut optimizations to move whole nets to one side of the cut line.
  • An improved Min-cut algorithm developed by M. A. Breuer assigns X and Y coordinates to the subcircuit groups as they are partitioned. Each sequential partition line dividing a subcircuit group into two or more smaller groups is alternately designated as "vertical” or "horizontal".
  • partitioning lines designated as "horizontal” divide each group into two subgroups, each subgroup having new Y-range values.
  • the subgroups are partitioned independently and their range values may be different.
  • the subgroups are similarly divided until a stop condition is satisfied.
  • the orthogonal coordinates describing the location of each group on the substrate or FPGA is determined by the X- and Y-range within which, the group falls.
  • a problem arising from assigning X- and Y- range values to groups of elements is addressed by a modified Min-cut algorithm developed by A. E. Dunlop and B. W. Kernighan, which is commonly referred to as "terminal propagation".
  • the problem is illustrated in Figs. 6a - 6c.
  • initial partitioning of a group of elements results in at least one net ni connecting two elements ai and bi crossing partition line P-i .
  • the problem occurs when subsequent partitioning divides each of these groups into two or more subgroups.
  • Min-cut algorithm fails to account for elements of the two groups which are connected to elements in groups other than the two groups being partitioned. For instance, subsequent partitions may result in the elements ai and bi being moved to orthogonally remote X and Y positions, as shown in Fig. 6b.
  • Dunlop and Kernighan developed a modified algorithm which addresses this problem by assigning a "dummy" element ai' (shown in Fig. 6c) to a location adjacent the partition line separating elements ai and bi .
  • the dummy element ai' is "connected" by nets n ⁇ ' and n to elements a and bi , respectively.
  • the dummy elements represent external pins and cannot be moved because the pins are not considered to be part of the groups being partitioned. As subsequent partitioning occurs, the net n-i' prevents the movement of the element ai to an X-Y position which is remote from the element bi , unless sufficient gain results from the movement.
  • a modified partitioning method for placement of a circuit design into a PICD the PICD having a specific distribution of physical resources corresponding to a specific circuit structure.
  • the specific circuit structure can be, for instance, the three-state bus structure described above.
  • the specific circuit structure can also be any circuit structure determined by a PICD manufacturer as being supported by a particular physical distribution of resources on the PICD.
  • the circuit design comprises a plurality of circuit elements which include specific circuit elements, the specific circuit elements being associated with the specific circuit structure.
  • the modified placement method of the present invention begins by analyzing the elements of the circuit design and determining if specific circuit elements are present. In its simplest form, the modified partitioning method according to the present invention then restricts partitioning of the specific circuit elements such that these elements are placed in locations corresponding to the physical distribution of resources on the PICD which support the specific circuit structure.
  • the step of partitioning further includes the steps of forming into a cell the identified specific circuit elements and performing a first phase of partitioning wherein the cell and the remaining elements of the plurality of circuit elements are partitioned until a stop condition is satisfied.
  • This stop condition may be, for instance, when the cell is partitioned into a group containing no other elements.
  • the group containing the cell defines an area and a location associated with the PICD.
  • the cell is then decomposed such that the contents of the group containing the cell change to include the specific circuit elements.
  • the group containing the specific circuit elements is then partitioned so that the area and the location of the group correspond to the specific physical distribution of resources.
  • the physical distribution of resources into which the specific circuit elements are placed is aligned along horizontal long lines of an FPGA.
  • second phase partitioning of the group containing the specific circuit elements is limited to vertical partitioning lines so that the specific circuit elements are placed to contact a common horizontal long line.
  • the step of decomposing the cell includes adjusting an X-range value and an orthogonal Y-range value associated with the group, such that the group is associated with a small area and location corresponding to the specific physical distribution of resources.
  • the step of adjusting the Y-range value and the X-range value includes constricting the Y-range and expanding the X-range such that the group is aligned along a horizontal strip corresponding to the specific physical distribution of resources.
  • the direction of partitioning cuts is then restricted to vertical in order to prevent misalignment along the horizontal strip.
  • Fig. 1 is a plan view of a prior art FPGA.
  • Fig. 2 is a simplified circuit diagram showing a CLB from a
  • Fig. 3 is a simplified circuit diagram showing an IOB from a Xilinx 4000-series FPGA.
  • Fig. 4 is a circuit diagram showing the placement of CLBs, lOBs and Tbufs on a Xilinx 4000-series FPGA.
  • Figs. 5a-5c illustrate the basic prior art Min-cut algorithm.
  • Figs. 6a-6c illustrate the prior art terminal propagation Min- cut algorithm.
  • Figs. 7a-7e illustrate the Tbuf problem addressed by one embodiment of the present invention.
  • Fig. 8 is a simplified circuit diagram showing the results of partitioning using the prior art Min-cut algorithm as applied to the Tbuf problem.
  • Figs. 9a and 9b illustrate identification of Tbuf elements and forming a cell according to the present invention.
  • Figs. 10a-10g illustrate a first example showing how the present invention solves the Tbuf problem.
  • Figs. 11a-11g illustrate a second example showing how the present invention solves the Tbuf problem.
  • the modified partitioning method of the present invention overcomes many of the limitations of the prior art Min-cut algorithms and provides incentive to use Min-cut for initial placement of a circuit design into a PICD.
  • the modified partitioning method of the present invention is presented below in four parts.
  • pseudocode embodying the modified partitioning method is presented which addresses the Tbuf problem associated with Xilinx 4000-series FPGAs, which is discussed above. Finally, the pseudocode is further explained by application of the pseudocode to the Tbuf problem.
  • FPGAs Field Programmable Gate Arrays
  • PICDs Programmable integrated circuit devices
  • PICDs may be configured by an end-user to provide a desired logic function.
  • PICDs are usually comprised of a pattern of logic elements connected by programmable interconnections.
  • PICDs are configured to perform a desired logic function by connecting the logic elements together using the programmable interconnections.
  • special logic elements such as function generators are also configurable to perform logic functions representing a combination of basic logic elements.
  • PICDs include programmable logic arrays (PLAs) and field- programmable gate arrays (FPGAs). This invention is mainly concerned with FPGAs.
  • An FPGA is typically organized as shown in Fig. 1.
  • FPGAs are generally characterized in that they consist of a matrix of configurable logic blocks (CLBs) 11 surrounded by input/output blocks (lOBs) 12.
  • CLBs configurable logic blocks
  • lOBs input/output blocks
  • lines 13 drawn between the rows and columns of CLBs are provided for showing a network of interconnect resources which can be configured to provide desired connections between two or more CLBs and between CLBs and lOBs.
  • these interconnect resources are not necessarily disposed between the CLBs and lOBs, but may be disposed above the CLBs and lOBs.
  • An example of a CLB used in a Xilinx, Inc. 4000-series FPGA, to which the method according to the present invention is advantageously applied, is shown in Fig. 2.
  • the combinational logic cells 21 are capable of implementing any Boolean function of their logic inputs 24. Data input for either flip-flop 22 within the CLB is supplied from the outputs of the combinational logic cells 21 , or the control inputs 26.
  • the periphery of the FPGA is made up of user programmable lOBs.
  • An example of an IOB 12 used in the Xilinx 4000-series FPGA is shown in Fig. 3.
  • the IOB 12 includes both registered input paths 31 and direct input paths 32.
  • Each IOB provides a programmable 3- state output buffer 33, which may be driven by a registered or direct output signal.
  • Each IOB also provides input clamping means and means to inhibit latch-up produced by input currents.
  • the matrix of CLBs and lOBs are linked by programmable interconnect resources which are configurable to create desired connections between the lOBs and CLBs.
  • An example of the interconnect resources used in the Xilinx 4000-series FPGAs is shown in Fig. 4.
  • the interconnect architecture includes general purpose interconnect lines 41 and long lines 43.
  • General purpose interconnect lines 41 consist of a grid of horizontal and vertical metal segments located between the rows and columns of CLBs and lOBs.
  • Switching matrices 44 join the ends of these segments and allow programmed interconnections between the horizontal and vertical segments.
  • Long lines 43 bypass the switching matrices 44 and are intended primarily for signals that must travel a long distance, or must have minimum skew among multiple destinations. (Skew is the difference between maximum and minimum delay between source and all destinations on a single conductive path. A path through several transistors will incur RC delay as the signal passes through the transistors.)
  • Each interconnection column has vertical long lines, and each interconnection row has horizontal long lines. Long lines can be driven by a CLB or IOB output on a column-by- column basis. This capability provides a common low skew control or clock line within each column of CLBs.
  • lOBs and interconnection resources available on the Xilinx 4000-series FPGA are a set of three-state buffers (also referred to as Tbufs).
  • Fig. 4 shows that a pair of Tbufs 45 are connected to an output of each CLB, and permits the CLB to drive two of the horizontal long lines to provide multiplexing functions.
  • Xilinx 4000-series FPGA is further described in "XC 4000 Logic Cell Array Family", copyright 1990, Xilinx Inc., and available from Xilinx, Inc. at 2100 Logic Way, San Jose, CA, 95194. This publication is incorporated by reference.
  • FPGAs and computer-aided design tools are recognized as making possible complete automation of VLSI design.
  • Computer- aided design tools include graphics systems which aid circuit design, and computer software for automatically placing and routing the circuit design into an FPGA. Placement may be implemented using one or more of the software algorithms mentioned in the Shahookar and Mazumder article discussed above. Placement and routing of a circuit design into an FPGA introduces problems which are not present in the layout of custom circuits.
  • An analogy is planning the layout of a city. In custom circuits, a planner begins essentially from scratch. Decisions regarding the placement of elements, similar to the placement of industry, residential and emergency structures, can be made prior to construction. In addition, necessary interconnection lines, similar to roadways and highways, can be anticipated and necessary space can be set aside.
  • This algorithm teaches the duplication of basic logic components (i.e., gates) so that they can be implemented by existing combinational logic cells, flip-flops and Tbufs located on a Xilinx 4000-series FPGA. This algorithm simplifies placement by reducing the number of elements considered by the placement algorithm.
  • placement is considered to include two overlapping steps: partitioning and placement. Partitioning is used to divide elements into groups which fit into CLBs and lOBs and to provide initial or "rough" placement of the circuit design. Partitioning is followed by final placement using one of the other placement algorithms mentioned in the Shahookar and Mazumder article.
  • the modified placement method according to the present invention teaches the use of the Min-cut algorithm during the partitioning step, despite the limitations of the Min-cut algorithm which are commonly known and discussed below.
  • Min-cut Algorithms can be used as a very fast rough placement algorithm, it is commonly recognized as being inefficient for use even in initial placement of circuit designs into PICDs, and in particular FPGAs.
  • One limitation of the Min-cut algorithm is that it fails to account for the physical distribution of resources on an FPGA. That is, certain associated CLBs, lOBs, interconnect lines and other elements on an FPGA are physically located in proximity to each other or aligned such that they may be conveniently and efficiently routed together to perform functions which are commonly used in a circuit design. The arrangement of the CLBs, lOBs, elements and interconnect lines is chosen by the FPGA manufacturer in anticipation of the needs of an FPGA purchaser.
  • Min-cut algorithm fails to account for the physical arrangement of the FPGA resources, the Min-cut algorithm will typically place elements of a circuit design poorly with respect to the available wiring resources. If the Min-cut algorithm is used as an initial placement tool, the Min-cut placement can generate unsolvable problems for final placement of the circuit design. Therefore, the Min-cut algorithm is typically not used for the placement of circuit designs on FPGAs.
  • Min-cut algorithms are better understood with the following example of a three-state bus structure placed on a Xilinx 4000-series FPGA.
  • Three-state buffers are elements receiving one input signal and one control signal and generating one output signal.
  • the input signal is either high or low, and the control signal either allows the high or low input signal to be transmitted as the output signal, or prevents the input signal from being transmitted, thereby creating an "off" output signal.
  • the high, low and "off" output signals applied to a bus by one or more Tbufs produce a three-state bus structure.
  • each Tbuf 45 in a Xilinx 4000- series FPGA is connected to the outputs of a CLB 11.
  • the control signal of each Tbuf is provided from one of the several interconnect lines.
  • the output of each Tbuf is connected to one of the several horizontal long lines 43.
  • Xilinx purposefully arranges the horizontal rows of CLBs connected to rows of Tbufs, which in turn are connected to horizontal long lines, because FPGA purchasers often have use of three-state bus structures in which one long line is driven by several Tbufs.
  • a placement algorithm In order to place a three-state bus structure into an FPGA, a placement algorithm must identify the Tbufs that are physically connected to a common long line, and must place the circuit design elements associated with the three-state bus structure such that the associated Tbufs access the common long line. This task would be elementary if there were only one set of Tbufs connected to one long line on an FPGA, but actual FPGAs, such as shown in Fig. 4, contain several sets of Tbufs and several associated long lines. The problem presented by several sets of Tbufs and several long lines located on an FPGA is that unless the placement algorithm orients a three-state bus structure along a single horizontal long line, then the associated Tbufs will not be able to provide a three-state bus structure.
  • the Min-cut algorithm is not concerned with the orientation of associated elements, but only seeks to minimize the number of cut nets. Even using the terminal propagation modification, the associated Tbufs of a circuit design containing a three-state bus structure can be placed such that they are not connected to the same horizontal long line.
  • Fig. 7a indicates a three-state bus structure consisting of four Tbufs T1 - T4. Each of the Tbufs receives one control signal and one input signal, indicated as CS1-CS4 and IN1-IN4. The outputs of Tbufs T1- T4 are connected together so that one of them may drive a common bus line. Also shown are circuit elements E1-E4 which are also part of the circuit design to be configured, but are not directly connected to the Tbufs.
  • Fig. 8 illustrates a simplified FPGA comprised of 16 CLBs. Minimal interconnecting lines are shown for clarity. This example assumes that other elements of the circuit design have already been partitioned, and that the only remaining elements to be partitioned are Tbufs T1-T4 and elements E1-E4.
  • the Min-cut algorithm will attempt to partition Tbufs T1-T4 and elements E1-E4 such that the minimum number of nets are cut. It is easily seen that the only division of elements which results in zero cut nets is to separate the Tbufs from the elements E1-E4, as shown in Fig. 7b. This division results in the following problems.
  • the partition line L1 is designated as "vertical". This would divide the resources of the simplified FPGA shown in Fig. 8 as indicated with line L1.
  • the Tbufs T1-T4 of Fig. 7b would be placed to the left of line L1 in Fig. 8, and elements E1-E4 would be placed to the right of line L1.
  • Note that there are 16 Tbufs located to the left of line L1 which would be recognized by the prior art Min-cut algorithms as being sufficient to support the four Tbufs T1-T4 of Fig. 7b. What would not be recognized by the prior art Min-cut algorithms is that only two of the 16 Tbufs to the left of line L1 are connected to any one of the eight long lines 43.
  • the modified placement method of the present invention begins by analyzing the elements of a circuit design and determining if a specific circuit structure is present.
  • the specific circuit structure can be, for instance, the three-state bus structure described above.
  • the specific circuit structure can also be any circuit structure determined by a PICD manufacturer as being supported by a particular physical distribution of resources on the PICD.
  • the modified partitioning method according to the present invention then restricts partitioning of the elements associated with the specific circuit structure such that these elements are placed in locations corresponding to the physical distribution of resources on the PICD which support the specific circuit structure.
  • the step of restricting partitioning of the elements associated with the specific circuit structure includes assigning the elements to a cell, performing a first phase of partitioning wherein the cell and the remaining elements are partitioned until the cell is isolated into its own group, then decomposing the cell into its source elements.
  • a second phase of partitioning is then performed wherein the group containing the source elements is partitioned while restricting the direction of partitioning cuts such that the elements are placed according to the physical distribution of resources of the PICD which support the specific circuit structure.
  • the modified placement algorithm assigns the elements associated with each circuit structure to a single cell.
  • position-dependent elements elements which must be placed in a specific relation to the physical resources on the PICD
  • the cells may include position-independent elements (elements which may be placed more generally on the PICD) which are immediately connected to the position-dependent elements.
  • assigning elements to a cell should not be confused with combining circuit design components (e.g., logic gates) in order to efficiently fill CLBs and lOBs in an FPGA.
  • Combining components to fit within CLBs and lOBs involves, for instance, recognizing basic design components which can be implemented in one combinational logic cell or one flip-flop of a CLB or IOB.
  • assigning elements to a cell involves assigning elements which would be implemented in, for instance, several combinational logic cells, registers and Tbufs of several CLBs or lOBs in an FPGA.
  • the process of combining components is preferably used in the modified partitioning method of the present invention, it is not necessary to implement the inventive method.
  • a first phase of partitioning begins for the cells and the remaining elements which are not part of one of the specific circuit structures.
  • the cells which contain multiple elements, are identified by the partitioning program as having essentially the same "size" as single elements. That is, the number or type of source elements assigned to the cell are not taken into consideration for the purposes of the first phase of partitioning.
  • the partitioning algorithm used may be the prior art Min-cut partitioning process (described above), or any other partitioning algorithm. That is, groups including both elements and cells are initially partitioned into two groups, then four groups, etc.
  • the first phase of partitioning terminates when all of the cells are isolated in their own group such that they are separated from all other cells and groups of elements.
  • each cell is separated by one or more partition lines from all other groups containing only a single cell or one or more elements
  • the cells are decomposed into the source elements making up the cell. That is, the contents of the cell is replaced by its source elements.
  • Each group of source elements (those elements from a decomposed cell) is marked to indicate that the source elements are from a particular type of parent cell.
  • the type of parent cell from which source elements originate determines the adjustments to the X- and Y-range of the group of source elements and the restrictions on second phase partitioning of the group of source elements (discussed below).
  • the source elements Upon decomposition of the cell, the source elements are initially assigned the X-range and Y-range of the "group" into which the parent cell was partitioned.
  • the cell was treated as having the "size" of an element, the X- and Y-ranges into which the cell is partitioned is almost always too small to support the cell's numerous source elements.
  • the X- range of the group of source elements is expanded to include the entire horizontal area bounded by the supporting resources on the PICD.
  • the Y-range may be modified to align the elements along a specific horizontal section of the PICD. That is, if the Y-range of the group of source elements encompasses five conducting horizontal lines, and the source elements are to be aligned along one of the horizontal lines, the Y-range is adjusted to encompass only one of the five conducting lines.
  • the X- and Y- ranges for the group may similarly be adjusted to be aligned vertically, or to assume any shape which would best account for the physical distribution of resources on the PICD. Note that the adjustment of X- and Y-ranges of a group of source elements will usually create an overlap between the group containing the source elements and other adjacent groups. This overlap problem will be addressed below.
  • second phase partitioning is initiated during which the groups of source elements, along with all other groups, are partitioned until each group satisfies a second stop condition.
  • each group containing source elements from a decomposed cell is subject to restrictions determined by the type of parent cell. For instance, if all of the elements are to be aligned along a horizontal row of the PICD, then during the second phase of partitioning the group may be restricted to "vertical" partitioning cuts. This results in the source elements being partitioned to be aligned along the adjusted X-range of the group.
  • Other possible restrictions may be applied to the group during the second phase of partitioning. For instance, the partitioning may be restricted to horizontal partitioning cuts, or a limited number of horizontal and/or vertical partitioning cuts.
  • the modified partitioning method is used only as an initial placement tool, and at least one other placement algorithm is used for final placement.
  • the overlap problem that may occur due to the modified partitioning method according to the present invention is easily corrected during final placement. Therefore, each group is partitioned without considering the X- and Y-range of every other group. That is, all groups having adjusted X- and Y-ranges are subject to further partitioning as if they were originally partitioned into the adjusted ranges. Similarly, all groups which overlap an adjusted group are partitioned as if the adjusted group doesn't exist.
  • the preferred application of the modified partitioning algorithm is an initial or "rough" placement algorithm.
  • one or more additional algorithms mentioned above in the Shahookar and Mazumder article, are necessary for further refining the placement of the elements of the circuit design.
  • the modified partitioning method of the present invention assigns elements into cells, partitions, decomposes the cells and then partitions the source elements subject to certain constraints, the modified method provides an efficient and relatively accurate method for initial placement of a circuit design into a PICD. Also important is that the modified method meets constraints present in the physical structure of the PICD which will implement the design.
  • Appendix I below includes pseudocode for a partitioning algorithm according to a preferred embodiment of the present invention.
  • the pseudocode is tailored for partitioning a circuit design for placement into a Xilinx 4000-series FPGA, described above.
  • the only specific circuit structure addressed in the pseudocode is the three-state bus (Tbuf) structure, described above. Further, the pseudocode assumes only one Tbuf structure is present in the circuit design. Other specific circuit structures may be addressed by the modified partitioning method of the present invention in a similar manner.
  • the MAIN program begins by analyzing a circuit design. If the circuit design includes a Tbuf structure, MAIN program calls the CREATE_TBUFS_CELL subroutine. If there is no Tbuf structure, the MAIN program immediately executes the second phase PARTITION subroutine, described below.
  • the CREATE_TBUFS_CELL subroutine assigns all of the elements making up the Tbuf structure to a single cell.
  • the CREATE_TBUFS_CELL subroutine then returns to the MAIN program.
  • the MAIN program then executes the PARTITION subroutine and begins a first phase of partitioning. Note that the first phase of partitioning is not executed if there is no Tbufs structure.
  • the first phase PARTITION subroutine begins by setting the direction of the partitioning cut to vertical.
  • the PARTITION subroutine then analyzes the primary group containing the cell and all elements to determine if the group is too large to fit into a single CLB or IOB. This analysis usually succeeds during partitioning of the primary group because the cell is commonly composed of several elements of the logic design.
  • the cut direction and any constraints on cut direction for the primary group are compared to determine if the primary group may be partitioned using the current cut direction, in this instance vertical. Note that this test always succeeds during the first phase of partitioning because cut constraints do not exist prior to execution of the DECOMPOSE/LIMIT TBUF CELL subroutine. Therefore, the primary group is partitioned using the PROPAGATION and SELECT_PARTITION subroutines.
  • the PROPAGATION subroutine is essentially the Dunlop and Kernighan "terminal propagation" modified Min-cut algorithm, discussed in the Background section.
  • the PROPAGATION subroutine calls the CREATE_DUMMY_ELEMENT subroutine as described in the discussion of terminal propagation.
  • the SELECT_PARTITION and the TRY_PARTITION subroutines are essentially the basic Min-cut algorithm which is described in the Background section.
  • One modification to the SELECT_PARTITION subroutine which is specific to FPGAs is that the elements associated specifically with lOBs are always assigned to the "outermost" sub-group resulting from a partitioning cut.
  • the "outermost" sub-group is the sub-group resulting from the partitioning of a group which is closest to the highest or lowest X- or Y-range value. This assures that the lOB-associated elements are placed into X- and Y-ranges which correspond to the physical position of the lOBs.
  • the PARTITION subroutine changes the cut direction and partitions each of the two newly formed groups. This process of changing the cut direction and then partitioning all groups continues for each successively smaller group until the cell is isolated in its own group. At this point the first phase of partitioning ends and the pseudocode returns to the MAIN program.
  • the MAIN program next calls the DECOMPOSE/LIMIT_TBUFS_CELL subroutine.
  • This subroutine replaces the contents of the group containing the cell with the source elements making up the cell.
  • the X-range of the group is then expanded to include the entire horizontal row bounded by the Y- range of the group.
  • a constraint is placed on the group which restricts the limits the cut direction applied to the group to vertical partition lines only.
  • the PARTITION subroutine is then executed for a second time.
  • This second phase of partitioning is executed in the same manner as in the first phase of partitioning, with the following exception.
  • the PROPAGATION subroutine Before each group which is too large to fit within one CLB or IOB is subjected to the PROPAGATION subroutine, it is checked for cut direction constraints. Since the group containing the source elements from the cell is now restricted to vertical partitioning cuts, every time the cut direction is horizontal, the group is not partitioned. That is, if the cut direction is vertical, then the group is subjected to the PROPAGATION and SELECT_PARTITION subroutines. However, if the cut direction is horizontal, the group is not subjected to any partitioning. Eventually, all of the groups of elements and the group containing the source elements are partitioned into groups which will fit within one CLB and IOB. At this time the program ends.
  • the elements to be partitioned are four Tbufs and four elements E1-E4 (refer to Fig. 9a).
  • the four Tbufs are not connected by any nets to the elements E1-E4.
  • the dashed line surrounding the four Tbufs indicates the Tbuf structure which is recognized by the pseudocode.
  • the MAIN program calls the CREATE_TBUF_CELL subroutine upon detection of the Tbuf structure.
  • the CREATE_TBUF_CELL subroutine then assigns the four Tbufs to the cell C (shown in Fig. 9b).
  • the pseudocode then returns control to the MAIN program, which then executes the first phase of partitioning.
  • the following two examples will describe the first and second phases of partitioning after the creation of the cell C.
  • Example One Vertical Initial Partitioning Cut
  • the Min-cut algorithm may be modified, as discussed above, to partition the group into equal or nearly equal portions, or the Min-cut algorithm may partition the group such that a substantial balance in the number of elements in each sub-group is created. The latter modification is assumed in this example.
  • Figs. 10a-10f illustrate the partitioning of the cell and elements E1-E4 during this example.
  • the cell is separated by partition line PL1 into the left sub-group as shown in Fig. 10a.
  • the elements are partitioned into the right sub-group. After this partitioning cut, the cell is isolated from all other elements of the circuit design. Therefore, the condition set for the end of the first phase of partitioning is satisfied.
  • the MAIN program calls the
  • DECOMPOSE/LIMIT_TBUF_CELL subroutine decomposes the cell into the "source elements", or the four Tbufs, while retaining the four Tbufs in one group (Fig. 10b).
  • the X-range and Y-range of the group are then adjusted to correspond to the entire upper row of four Tbufs connected to the upper row of four CLBs. Note that the X-range of the group of Tbufs overlaps the group containing elements E1-E4. As explained above, this overlap is not addressed by the modified partitioning method of the present invention. Finally, a constraint is placed on the group that its elements are only to be partitioned using vertical partition lines.
  • second phase partitioning is called by the MAIN program. Because the previous partitioning cut direction was vertical, the partitioning cut direction is changed to horizontal. Each of the two groups is tested for cut direction constraints.
  • the group containing elements E1-E4 has no cut direction constraints, and is partitioned as indicated by line PL2 in Fig. 10c.
  • group containing the Tbufs is limited to vertical partitioning only. Therefore, the Tbuf group is not partitioned by a horizontal partitioning line.
  • the PARTITION subroutine next changes the cut direction to vertical. Because the "group” containing element E1 fits within one CLB, the "group” is not further partitioned.
  • the groups containing elements E2-E4 and the four Tbufs are partitioned with partition lines PL3, as shown in Fig. 10d.
  • the PARTITION subroutine then changes the cut direction to horizontal. Because the "group” containing element E2 fits within one CLB, the "group” is not further partitioned.
  • the group containing elements E3 and E4 is partitioned with partition lines PL4, as shown in Fig. 10e. Note that because the partition line is horizontal, neither of the sub-groups containing Tbufs is partitioned.
  • the PARTITION subroutine changes the cut direction to vertical for the last partition cut. Because all of the "groups" containing elements fit within one CLB, the "groups" are not further partitioned.
  • the sub-groups containing Tbufs are each partitioned by partition lines PL5 as shown in Fig. 10f. At the end of this partition all "groups" fit within one CLB, and therefore the program ends.
  • Fig. 10g The "rough" placement of the Tbufs and elements into the 4x4 CLB matrix, and as determined by the modified partitioning method described above, is shown in Fig. 10g.
  • the placement of elements E1-E4 are indicated by superimposing the element on the associated CLB.
  • the placement of Tbufs is indicated by the row of darkened Tbuf elements.
  • Example Two assumes that the first partitioning cut direction is horizontal. In addition this example assumes that the cell is grouped with element E4 as a result of the initial horizontal partitioning cut.
  • Figs. 11a-11f illustrate the partitioning of the cell and elements E1-E4 during this example.
  • the cell and element E4 are partitioned by partition line PL1 into the lower sub ⁇ group as shown in Fig. 11a.
  • the elements E1-E3 are partitioned into the upper sub-group.
  • the PARTITION subroutine would then change the partition cut direction to vertical and apply the partitioning cut to the two groups.
  • One possible result of a vertical cut is indicated by partition lines PL2, as shown in Fig. 11 b.
  • partition lines PL2 As shown in Fig. 11 b.
  • the MAIN program calls the DECOMPOSE/LIMIT_TBUF_CELL subroutine. This subroutine decomposes the cell into the four Tbufs, while retaining the four Tbufs in one group (Fig. 11c).
  • the X-range and Y-range of the group are then adjusted to correspond to the entire upper row of four Tbufs connected to the lower-middle row of four CLBs. Note that the X-range of the group of Tbufs does not overlap any the groups containing elements E1-E4 in this example. Finally, a constraint is placed on the group that its elements are only to be partitioned using vertical partition lines.
  • second phase partitioning is called by the MAIN program. Because the previous partitioning cut direction was vertical, the partitioning cut direction is changed to horizontal. Also, because the "groups" containing elements E1 and E4 fit within one CLB, the "groups" are not further partitioned. Each of the remaining groups is tested for cut direction constraints. The group containing elements E2 and E3 has no cut direction constraints, and is partitioned as indicated by line PL3 in Fig. 11d. However, group containing the Tbufs is limited to vertical partitioning only. Therefore, the Tbuf group is not partitioned by a horizontal partitioning line.
  • the PARTITION subroutine next changes the cut direction to vertical. Because the "groups" containing element E2 and E3 fit within one CLB, the "groups" are not further partitioned. The group containing the four Tbufs is partitioned with partition line PL4, as shown in Fig. 11e.
  • the PARTITION subroutine then changes the cut direction to horizontal. Because no group of elements is to be partitioned, and because of the cut direction constraints on the group containing the Tbufs, no further partitioning is done in the horizontal direction. Finally, the PARTITION subroutine changes the cut direction to vertical for the last partition cut.
  • the sub-groups containing Tbufs are each partitioned by partition lines PL5 as shown in Fig. 11f. At the end of this partition all "groups" fit within one CLB, and therefore the program ends.
  • Fig. 11g The "rough" placement of the Tbufs and elements into the 4x4 CLB matrix, and as determined by the modified partitioning method described above, is shown in Fig. 11g.
  • the placement of elements E1-E4 are indicated by superimposing the element on the associated CLB.
  • the placement of Tbufs is indicated by the row of darkened Tbuf elements.
  • circuit design contains a Tbuf structure
  • Do PARTITION (see subroutine below, which draws successive partitioning lines through the elements of the circuit design, alternating the current cut direction between horizontal and vertical) until the cell is isolated from all other groups of elements.
  • DECOMPOSE/LIMIT_TBUF_CELL (see subroutine below for decomposing the cell into a group containing the cell's source elements) End if.
  • PROPAGATION subroutine
  • CREATE_DUMMY_ELEMENT (see subroutine below for placing a dummy element at the edge of the group closest to the actual location of the element in an adjacent group to which the net connects) End for.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Architecture (AREA)
  • Evolutionary Computation (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Design And Manufacture Of Integrated Circuits (AREA)

Abstract

Procédé de découpage modifié destiné à placer une configuration de circuit dans un dispositif de circuit intégré programmable (DCIP), ledit DCIP ayant une répartition spécifique des ressources physiques correspondant à une structure de circuit spécifique. Ladite configuration de circuit comporte une pluralité d'éléments de circuits (E1-E4) qui comprennent des éléments spécifiques de circuit (45) correspondant à la structure de circuit spécifique. Le procédé modifié comporte les phases d'identification des éléments de circuit spécifiques (45) et de découpage de la pluralité d'éléments de circuit (E1-E4), de telle manière que les éléments de circuit spécifiques identifiés (45) soient placés en un lieu correspondant à la répartition physique spécifique des ressources. Dans un mode d'exécution du procédé de découpage modifié selon la présente invention, la phase de découpage comporte en outre les étapes de formation d'une cellule à partir des éléments de circuit spécifiques identifiés (45) et de réalisation d'une première phase de découpage lors de laquelle la cellule et le reste de la pluralité des éléments de circuit (E1-E4) sont découpés en groupes successivement de plus en plus petits jusqu'à ce qu'une condition d'arrêt soit satisfaite. La cellule est ensuite décomposée de telle manière que le contenu du groupe contenant la cellule se modifie pour inclure les éléments de circuit spécifiques (45). Le groupe contenant les éléments de circuit spécifiques (45) est ensuite découpé de manière que la zone et l'emplacement du groupe correspondent à la répartition physique spécifique des ressources.
PCT/US1991/008311 1990-11-15 1991-11-14 Placement logique utilisant un algorithme de decoupage a positionnement asymetrique Ceased WO1992009042A1 (fr)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US61490690A 1990-11-15 1990-11-15
US614,906 1990-11-15
US07/784,844 US5224056A (en) 1991-10-30 1991-10-30 Logic placement using positionally asymmetrical partitioning algorithm
US784,844 1991-10-30

Publications (1)

Publication Number Publication Date
WO1992009042A1 true WO1992009042A1 (fr) 1992-05-29

Family

ID=27087357

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1991/008311 Ceased WO1992009042A1 (fr) 1990-11-15 1991-11-14 Placement logique utilisant un algorithme de decoupage a positionnement asymetrique

Country Status (2)

Country Link
AU (1) AU9063491A (fr)
WO (1) WO1992009042A1 (fr)

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3617714A (en) * 1969-04-15 1971-11-02 Bell Telephone Labor Inc Method of minimizing the interconnection cost of linked objects
UST940008I4 (en) * 1974-05-17 1975-11-04 Automated logic mapping system
US4890238A (en) * 1986-12-17 1989-12-26 International Business Machines Corporation Method for physical VLSI-chip design
US4908772A (en) * 1987-03-30 1990-03-13 Bell Telephone Laboratories Integrated circuits with component placement by rectilinear partitioning
US4967367A (en) * 1988-11-21 1990-10-30 Vlsi Technology, Inc. Synthetic netlist system and method

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3617714A (en) * 1969-04-15 1971-11-02 Bell Telephone Labor Inc Method of minimizing the interconnection cost of linked objects
UST940008I4 (en) * 1974-05-17 1975-11-04 Automated logic mapping system
US4890238A (en) * 1986-12-17 1989-12-26 International Business Machines Corporation Method for physical VLSI-chip design
US4908772A (en) * 1987-03-30 1990-03-13 Bell Telephone Laboratories Integrated circuits with component placement by rectilinear partitioning
US4967367A (en) * 1988-11-21 1990-10-30 Vlsi Technology, Inc. Synthetic netlist system and method

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
B.W. KERIGHAN et al., "An efficient Heuristic Procedure for Partitioning Graphs", THE BELL SYSTEM TECHNICAL DISCLOSURE, published February 1970, see pages 241 to 306. *
GOTARO ODAWARA et al., "Partitioning and Placement Technique for CMOS Gate Arrays", IEEE TRANS. ON COMPUTER-AIDED DESIGN, Vol. CAD-6, No. 3, published May 1987, see pages 355-363. *
M.A. BREUER, "Min-Cut Placement", J. DESIGN AUTOMATION AND FAULT COMPUTING, Vol. 1, No. 4, published October 1977, see pages 105 to 114. *
R.J. FRANCIS et al., "Chortle: A Technology Mapping Program for Lookup table-Based Field Programmable Gate Arrays", 27TH ACM/IEEE DESIGN AUTOMATION CONFERENCE, 1990, see pages 613-619. *
SHUNICHIRO NAKAMURA et al., "Lores-logic Reorganization System", IEEE 15TH DESIGN AUTOMATION CONFERENCE, 1978, see pages 250 to 260. *

Also Published As

Publication number Publication date
AU9063491A (en) 1992-06-11

Similar Documents

Publication Publication Date Title
US5224056A (en) Logic placement using positionally asymmetrical partitioning algorithm
US5513124A (en) Logic placement using positionally asymmetrical partitioning method
Sait et al. VLSI physical design automation: theory and practice
US6195788B1 (en) Mapping heterogeneous logic elements in a programmable logic device
EP0271596B1 (fr) Puce VLSI et méthode pour la fabrication
US5930499A (en) Method for mixed placement of structured and non-structured circuit elements
US6493658B1 (en) Optimization processing for integrated circuit physical design automation system using optimally switched fitness improvement algorithms
US5712793A (en) Physical design automation system and process for designing integrated circuit chips using fuzzy cell clusterization
US5761078A (en) Field programmable gate arrays using semi-hard multicell macros
US6813754B2 (en) Placement processing for programmable logic devices
JPH07254019A (ja) フィールドプログラム可能なゲートアレイ・インプリメンテーションをマスクプログラム可能な論理セル・インプリメンテーションに変換するための方法と装置
EP0951687B1 (fr) Procede de placement de dispositif logique programmable faisant appel a une fonction de ponderation pour faciliter le verrouillage de broches
US20020087939A1 (en) Method for designing large standard-cell based integrated circuits
JP2004501439A (ja) 集積回路をパーティション化して、配置及び配線をするシステム
Chang et al. Postlayout logic restructuring using alternative wires
US6958545B2 (en) Method for reducing wiring congestion in a VLSI chip design
US5835378A (en) Computer implemented method for leveling interconnect wiring density in a cell placement for an integrated circuit chip
US8201126B1 (en) Method and apparatus for performing hardware assisted placement
Corrigan A placement capability based on partitioning
US6530070B2 (en) Method of constraining non-uniform layouts using a uniform coordinate system
WO1992009042A1 (fr) Placement logique utilisant un algorithme de decoupage a positionnement asymetrique
US7509618B1 (en) Method and apparatus for facilitating an adaptive electronic design automation tool
US6615401B1 (en) Blocked net buffer insertion
EP0486248A2 (fr) Méthode de duplication de logique pour réduire la taille d'un circuit et le temps de retardement
Boubekeur et al. Configuring a wafer-scale two-dimensional array of single-bit processors

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AT AU BB BG BR CA CH CS DE DK ES FI GB HU JP KP KR LK LU MC MG MN MW NL NO PL RO SD SE SU

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BF BJ CF CG CH CI CM DE DK ES FR GA GB GN GR IT LU ML MR NL SE SN TD TG

REG Reference to national code

Ref country code: DE

Ref legal event code: 8642

NENP Non-entry into the national phase

Ref country code: CA