In this paper, we present a family of multiobjective hypergraph-partitioning algorithms based on the multilevel paradigm, which are capable of producing solutions in which both the cut and the maximum subdomain degree are simultaneously minimized. This type of partitionings are critical for existing and emerging applications in very large scale integration (VLSI) computer-aided design (CAD) as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the International Symposium on Physical Design (ISPD98) benchmark show that our algorithms produce solutions, which when compared against those produced by hM/sub E/T/sub I/S have a maximum subdomain degree that is reduced by up to 36% while achieving comparable quality in terms of cut.

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 oversubscribed. In this paper, we present a number of multilevel multi-resource 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 vertices 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.

As the chip densities increase, the modern FPGAs contain large capacity and increasingly provide heterogeneous units such as multipliers, processor/DSP cores, RAM-blocks etc, for efficient execution of crucial functions of the design. The hypergraph partitioning algorithms are generally used as a divide-and-conquer strategy, during synthesis and placement. The partitioning algorithms for designs with heterogeneous resources, need to not only minimize the cut, but also balance the individual types of resources. Unfortunately, the state-of-the-art multilevel hypergraph partitioning algorithms (hMetis,MLPart), are not capable of distinguishing the types of cells. To overcome this problem, we developed a new set of multilevel hypergraph partitioning algorithms, that are aware of multiple resources, and are guaranteed to balance the utilization of different resources. By evaluating these algorithms on large benchmarks, we found that it is possible to achieve such feasible partitions, while incurring only a slightly higher cut (3.3%-5.7%) compared to infeasible partitions generated by hMetis.

In this paper we present multi-objective hMetis partitioning for simultaneous cutsize and circuit delay minimization. We change the partitioning process itself by introducing a new objective function that incorporates a truly path-based delay component for the most critical paths. To avoid semi-critical paths from becoming critical, the traditional slack based delay component is also included in the cost function. The proposed timing driven partitioning algorithm is built on top of the hMetis algorithm, which is very efficient. Simulations results show that 14% average delay improvement can be obtained. Smooth trade-off between cutsize and delay is possible in our algorithm.