Graph partitioning engine based on programmable gate arrays

• US 5,761,077 A
• Filed: 05/23/1995
• Issued: 06/02/1998
• Est. Priority Date: 05/23/1995
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Shackleford, J. Barry
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/447,469
• Time in Patent Office: 1,106 Days
• Field of Search: 364/488-491, 364/578, 326/41, 395/500
• US Class Current: 716/125
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register

Abstract

A method for operating a FPGA to compute a function whose optimum represents the preferred partitioning of a graph having a plurality of vertices connected by edges. The FPGA is configured to provide a partition state register having a plurality of cells. Each cell corresponds to one of the vertices in the graph and is used to store a number indicative of the partition to which the corresponding vertex is currently assigned. The algorithm for determining the optimum partition computes a cost function having two components. The assignment of the vertices to the various partitions is made such that this cost function is minimized. For any given assignment of the vertices, the FPGA computes the cost function using two circuits that are configured from the FPGA. The first circuit computes the number of edges that connect vertices belonging to different partitions. The second circuit computes a number that represents the extent to which the various partitions differ from one another in size. The ideal partitioning is that which minimizes a weighted sum of these computed numbers. Special circuits for generating random numbers and binary vectors having a controllable number of randomly placed ones therein are also described.

Claims

1. In a method for operating a field programmable gate array (FPGA) to compute a function whose optimum represents the partitioning of a graph into a plurality of partitions, said graph comprising a plurality of vertices connected by edges, said partitioning assigning each of said verticies to one of said partitions, the improvement comprising configuring said FPGA to provide:

a partition state register(PSR), comprising a plurality of cells, each cell corresponding to one of said vertices, each cell storing a number indicative of the partition to which said vertex is currently assigned, said PSR representing a partitioning of said graph;

a circuit for computing the sum of the edges that connect vertices in different partitions; and

a circuit for computing a value representing the degree to which the partitions are of different sizes.

2. The method of claim 1 wherein the numbers stored in said cells of said PSR are in binary and wherein said method further comprising the step of configuring said FPGA to provide a circuit for generating a state change vector having one bit corresponding to each bit in said PSR, the number of bits having the value 1 in said state change vector being less than half of the total number of said bits in said state change vector, said bits having the value 1 being randomly placed in said state change vector.

3. The method of claim 2 wherein said circuit for generating said state change vector comprises a circuit for masking selected bits in said state change vector such that the partitioning represented by combining said masked state change vector and the contents of said PSR differs from the partitioning represented by said PSR only with respect to vertices that are on the boundary of one of said partitions, a vertex being on the boundary of a partition if said vertex is connected to a vertex in a different partition by an edge of said graph.

4. The method of claim 2 where said step of configuring said FPGA to provide a circuit for generating a state change vector comprises the step of configuring said FPGA to provide

a first shift register having an input for receiving a binary value to be shifted through said first shift register, said shift register comprising a plurality of cells through which said received binary value is shifted, each said cell having an output indicative of the value stored in said cell in said shift register, a first random number generating circuit having an output comprising a first sequence of random numbers, and a first comparator for comparing each number in said first sequence of random numbers with a first value, said first comparator having an output connected to the input of said first shift register;

a second shift register having an input for receiving a binary value to be shifted through said second shift register, said shift register comprising a plurality of cells through which said received binary value is shifted, each said cell having an output indicative of the value stored in said cell in said shift register, a second random number generating circuit having an output comprising a second sequence of random numbers, and a second comparator for comparing each number in said second sequence of random numbers with a second value, said second comparator having an output connected to the input of said second shift register; and

a circuit, connected to said outputs of corresponding said cells in said first and second shift registers, for generating said change vector.

5. The method of claim 4 wherein one of said random number generating circuits comprises a plurality of cells connected in series, said series comprising a first cell, a last cell, and one or more intermediate cells, each said cell comprising a circuit for storing a binary state and outputting a state value, an output terminal, said cell'"'"'s next state being a function of the cell'"'"'s current state and first and second inputs, wherein said intermediate cells are connected such that said first and second inputs of each said intermediate cells are connected, respectively, to said state outputs of said cells on each side of said intermediate cell in said series, and wherein one of said inputs of said first cell is connected to a circuit whose output is the sum of all of said cell states modulo 2.

6. The method of claim 1 wherein at least three vertices in said graph are connected to a hyperedge and wherein said method further comprises configuring said FPGA to provide a circuit connected to said cells in said PSR corresponding to said vertices connected to said hyperedge, said circuit having an output between 0 and k-1, wherein k is the number of partitions into which said graph is to be partitioned, said output of 0 being equal to the number of different values in said cells of said PSR corresponding to said hyperedge connected vertices less one.

7. A circuit for generating a sequence of random numbers, said circuit comprising a plurality of cells connected in series, said series comprising a first cell, a last cell, and one or more intermediate cells, each said cell comprising a circuit for storing a binary state and outputting a state value, and an output terminal, said cell'"'"'s next state being a function of the cell'"'"'s current state and first and second inputs, wherein said intermediate cells are connected such that said first and second inputs of each said intermediate cells are connected, respectively, to said state outputs of said cells on each side of said intermediate cell in said series, and wherein one of said inputs of said first cell is connected to a circuit whose output is the sum of all of said cell states modulo 2.

8. A circuit for generating a binary vector having a density of ones determined by a control value, the placement of ones in said binary vector being random, said circuit comprising:

a first shift register having an input for receiving a binary value to be shifted through said first shift register, said shift register comprising a plurality of cells through which said received binary value is shifted, each said cell having an output indicative of the value stored in said cell in said shift register, a first random number generating circuit having an output comprising a first sequence of random numbers, and a first comparator for comparing each number in said first sequence of random numbers with a first value, said first comparator having an output connected to the input of said first shift register;

a second shift register having an input for receiving a binary value to be shifted through said second shift register, said shift register comprising a plurality of cells through which said received binary value is shifted, each said cell having an output indicative of the value stored in said cell in said shift register, a second random number generating circuit having an output comprising a second sequence of random numbers, and a second comparator for comparing each number in said second sequence of random numbers with a second value, said second comparator having an output connected to the input of said second shift register; and

a circuit, connected to said outputs of corresponding said cells in said first and second shift registers, for generating the bits of said binary vector.

9. The circuit of claim 8 wherein said circuit for generating said bits of said binary vector comprises a plurality of two bit AND gates, each said AND gate having one input connected to a bit in said first shift register and the other input connected to a bit in said second shift register.