Graph partitioning engine based on programmable gate arrays

Details Graph partitioning engine based on programmable gate arrays Graph partitioning engine based on programmable gate arrays

1995-05-23

1998-06-02

Voeltz, Emanuel Todd

Boots, shoes, and leggings

364490, 364491, 364488, G06F 1750

Patent

active

057610770

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.

REFERENCES:
patent: 5224056 (1993-06-01), Chene et al.
patent: 5455525 (1995-10-01), Ho et al.
patent: 5675500 (1997-10-01), Kung et al.
Hsu et al. "Combining Logic Minization and Folding for PLA's," IEEE, pp. 706-713, Jun. 1991.
Liu et al. "An Efficient Algorithm for Selecting Bipartite Row or Column Folding of Programmable Logic Arrays," IEEE, pp. 494-498, Jul. 1994.
Tragoudas et al. "An Improved Algorithm for the Generation Min-Cut Partitioning Problem," IEEE, pp. 242-247, Mar. 1994.
Unaltuna et al. "A Stochastic Reward and Punishment Neural Network Algorithm for Circuit Bipartitioning," IEEE, pp. 181-184, Jun. 1994.
Shi et al. "Circuit Partitioning Under Capacity and I/O Constraints," IEEE, pp. 659-685, May 1994.
Saarinen et al. "vLSI Implementation of Tausworthe Random Number Generator for Parallel Processing Environment," IEEE, pp. 138-146, May 1991.
Cong et al. "Net Partitions Yield Better Module Partitions," IEEE, pp. 47-52, Jun. 1992.
Park et al. "An Efficient Algorithm for VLSI Network Partitioning Problem Using a Cost Function With Balancing Factor," IEEE, pp. 1686-1694, Nov. 1993.
Lee et al. "An Efficient K-Way Graph Partitioning Algorithm for Task Allocation in Parallel Computing Systems," IEEE, pp. 748-751, Apr. 1990.
Gopalakrishnan Vijayan "Generalization of Min-Cut Partioning to Tree Structures and its Applications," IEEE, pp. 307-314, Mar. 1991.

Affiliated with

Also associated with

Rating

Graph partitioning engine based on programmable gate arrays does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Graph partitioning engine based on programmable gate arrays, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph partitioning engine based on programmable gate arrays will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1468138