×

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
First Claim
Patent Images

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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×