Accession Number:

ADA439474

Title:

Scalable Partitioning Algorithms for FPGAs With Heterogeneous Resources

Descriptive Note:

Technical rept.

Corporate Author:

MINNESOTA UNIV MINNEAPOLIS DEPT OF COMPUTER SCIENCE

Report Date:

2004-09-29

Pagination or Media Count:

25.0

Abstract:

As FPGA densities increase, partitioning-based FPGA placement approaches are becoming increasingly important as they can be used to provide high-quality and computationally scalable placement solutions. However, modern FPGA architectures incorporate heterogeneous resources, which place additional requirements on the partitioning algorithms because they now need to not only minimize the cut and balance the partitions, but also they must ensure that none of the resources in each partition is over-subscribed. In this paper, we present a number of multilevel multiresource hypergraph partitioning algorithms that are guaranteed to produce solutions that balance the utilization of the different resources across the partitions. We evaluate our algorithms on twelve industrial benchmarks ranging in size from 5,236 to 140,118 cells and show that they achieve minimal degradation in the min-cut while balancing the various resources. Comparing the quality of the solution produced by some of our algorithms against that produced by hMETIS, we show that our algorithms are capable of balancing the different resources while incurring only a 3.3-5.7 higher cut.

Subject Categories:

  • Electrical and Electronic Equipment
  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE