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.

Traditionally, FPGAs have been the bastard step-brother of ASICs. They have been forced to act like ASICs and fit themselves into the ASIC development model. This has meant ignoring their unique strengths: reprogrammability, late-binding and run-time reconfiguration. Today, however, FPGAs are becoming more acceptable for their own merits. The majority of new design starts are FPGA designs. As FPGAs rise from under the shadow of their aging brother, should they continue to try to wear his hand-me-downs? Or is it time to develop more suitable models that lets them shine? At the same time, the old ASIC model is not even serving ASICs well, and new models for developing ASICs are emerging. All of this may encourage us to rethink how we should be programming FPGA-based systems. Possibilities include:

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.

The recent past has seen a tremendous increase in the size of design circuits that can be implemented in a single FPGA. The size and complexity of modern FPGAs has far outpaced the innovations in FPGA physical design. The problems faced by FPGA designers are similar in nature to those that preoccupy ASIC designers, namely, interconnect delays and design management. However, this paper will show that a simple re-targeting of ASIC physical design methodologies and algorithms to the FPGA domain will not suffice. We will show that several well researched problems in the ASIC world need new problem formulations and algorithms research to be useful for today's FPGAs. Partitioning, floorplanning, placement, delay estimation schemes are only some of the topics that need complete overhaul. We will give problem formulations, motivated by experimental results, for some of these topics as applicable in the FPGA domain.

Traditional integrated-circuit (IC) design methodologies have used wire-load models during logic synthesis to estimate the expected impact of the metal wiring on the gate delays. These models are based on wire-length statistics from legacy designs to facilitate a top-down IC design flow process. Recently, there has been increased concern regarding the efficacy of wire-load models as deep-submicrometer (DSM) interconnect parasitics begin to dominate the delay of digital IC logic gates. Some technology projections (Sylvester and Keutzer, 1998) have suggested that wire-load models will remain effective to block sizes on the order of 50 000 gates. This suggests that existing top-down synthesis methodologies will not have to be changed substantially since this is approximately the maximum size for which logic synthesis is effective. However, our analyses on production designs show that the problem is not quite so straightforward and the efficacy of synthesis using wire-load models depends upon technology data as well as specific characteristics of the design and the granularity of available physical information. We analyze these effects and dependencies in detail in this paper and draw some conclusions regarding the future challenges associated with top-down IC design and block synthesis, in particular, in the DSM design era.

The advent of deep sub-micron technologies has created a number of problems for existing design methodologies. Most prominent among them is the problem of timing closure, whereby design time is dramatically increased due to iterations between gate-level synthesis and physical design. It is well known that the heart of this problem lies in the use of wireload models based on wirelength statistics from legacy designs. Some technology projections in have suggested that wireload models will remain effective to block sizes on the order of 50k gates. This suggests that synthesis will not have to be changed much since this is approximately the maximum size for which logic synthesis is effective. However, our analyses on production designs show that the problem is not quite so straightforward, and the efficacy of synthesis using wireload models depends upon technology data as well as specific characteristics of the design. We analyze these effects and dependencies in detail in this paper, and draw some conclusions about the amount of physical information that is required for synthesis to be effective. Finally, we discuss the implications on hierarchical design flows, and propose a solution via physical prototyping.

There are a number of VLSI problems that have a common structure. We investigate such a structure that leads to a unified approach for three independent VLSI layout problems: partitioning, placement, and via minimization. Along the line, we first propose a linear-time approximation algorithm on maxcut and two closely related problems: k-coloring and maximal k-color ordering problem. The k-coloring is a generalization of the maxcut and the maximal k-color ordering is a generalization of the k-coloring. For a graph G with e edges and n vertices, our maxcut approximation algorithm runs in O(e+n) sequential time yielding a nodebalanced maxcut with size at least (w(E)+w(E)/n)/2, improving the time complexity of O(e log e) known before. Building on the proposed maxcut technique and employing a height-balanced binary decomposition, we devise an O((e+n)log k) time algorithm for the k-coloring problem which always finds a k-partition of vertices such that the number of bad (or "defected") edges does not exceed (w(E)/k)((n-1)/n)/sup log k/, thus improving both the time complexity O(enk) and the bound e/k known before. The other related problem is the maximal k-color ordering problem that has been an open problem. We show the problem is NP-complete, then present an approximation algorithm building on our k-coloring structure. A performance bound on maximal k-color ordering cost, 2kw(E)/3 is attained in O(ek) time. The solution quality of this algorithm is also tested experimentally and found to be effective.

Resource sharing is one of the main tasks in high-level synthesis, and although many algorithms have addressed the problem there are still several limitations which restrict the generality and applicability of current algorithms. Most clique-partitioning-based algorithms use local and inaccurate cost-functions which result in inefficient results. This paper presents algorithms for the resource sharing problem on registers and functional units, and shows how they overcome the limitations of existing algorithms. The main characteristics of this work are: interleaved register and functional unit merging in a global clique partitioning based framework, accurate merging cost estimation, accurate interconnect cost estimation, relative control cost taken into account and efficient false loop elimination. The results obtained show significant improvements in the delay of designs, while also minimizing area, specially for large designs with many sharing possibilities.

As high-level synthesis techniques gain acceptance among designers, it is important to be able to provide a robust system which can handle large designs in short execution times, producing high-quality results. Scheduling is one of the most complex tasks in high-level synthesis, and although many algorithms exist for solving the scheduling problem, it remains a main source of inefficiency by either not producing high-quality results, not taking into account realistic design requirements, or requiring unacceptable execution times. One of the main problems in scheduling is the dichotomy between control and data. Many algorithms to date have been able to provide scheduling solutions by looking only at either the data part or the control part of the design. This has been done in order to simplify the problem; however, it has resulted in many algorithms unable to handle efficiently large designs with complex control and data functionality. This paper presents algorithms for combining dataflow and control-flow techniques into a robust scheduling system. The main characteristics of this system are as follows: 1) it uses path-based techniques for efficient handling of control and mutual exclusiveness (for resource sharing), 2) it allows operation reordering and parallelism extraction within the context of path-based scheduling, 3) it contains a control partitioning algorithm for design space exploration as well as for reducing the number of control paths, and 4) it combines the above algorithms into an adaptive scheduling system which is capable of trading optimality for execution time on-the-fly. Results involving billions of paths are presented and analyzed.

Partitioned memory with bus interconnect architecture in its most general form consists of several functional units with associated memory accessible to the functional unit via local interconnect and global buses to communicate data values across from one functional unit to another.As can be expected, the time at which certain values are c ommunicated aect the size of the local memories and the number of buses that are n e e ded.We address the problem of scheduling communications in a bus architecture under memory constraints.We present here a network ow formulation for the problem and obtain an exact algorithm to schedule the communications, such that the constraint on the number of registers in each functional unit is satis ed.As an increasing number of architectures use multiple memories in addition to (or instead of) one central RAM, this work is especially interesting.Several authors have already studied this problem in related a r chitectures, yet all use heuristic approaches to schedule the communications.Our technique is the rst exact solution to the problem.Also, our graph theoretic formulation provides a clearer insight into the problem.