Search

As 2.5-D field-programmable gate arrays (FPGAs) have larger logic capacity and higher pin counts compared to conventional FPGAs, they are already deployed in some multi-FPGA systems. 2.5-D FPGA consists of multiple dies connected through an interposer. Since the interposer provides only a fraction of the amount of interconnect resources with an increased delay compared to that within individual dies, it is important to reduce the number of signal crossings between dies both for routability and timing consideration when a circuit is mapped to a 2.5-D FPGA. In a multi-2.5D FPGA system with time-multiplexed hardwired inter-FPGA connections, there can be tens of thousands of inter-FPGA signals incident with each FPGA and their pin assignment can greatly affect the amount of die-crossing signals within the FPGAs. In this article, we formulate the pin assignment problem for such systems with the objective of minimizing signal crossings between dies within the individual FPGAs. Taking into consideration of the multi-die structure of 2.5-D FPGA, we propose two different iterative refinement approaches to the problem, one based on integer linear programming (ILP) and the other algorithm C-2MCF based on clustering optimization and minimum cost flow optimization. Compared to a greedy pin assignment heuristic for minimization of signal crossings between dies, C-2MCF produced 27.1% less crossings on average. While the ILP-based algorithm has up to 1% quality advantage over C-2MCF for moderate-sized instances, C-2MCF is orders of magnitude faster and can comfortably handle very large problem instances. In addition, the proposed minimum cost flow techniques within C-2MCF can also be used in conjunction with any other possible pin assignment method to enhance the final result. [ABSTRACT FROM AUTHOR]

Threshold voltage assignment is a very effective technique to reduce leakage power consumption in modern integrated circuit design. As feature size continues to decrease, the layout constraints [called minimum implant area (MinIA) constraints] on the implant area, which determines the threshold voltage of a device, are becoming increasingly difficult to satisfy. It is necessary to take these constraints into consideration during the placement stage. In this paper, we propose to resolve the MinIA constraint violations of a given placement by performing simultaneous detailed placement and threshold voltage refinement. We first present an optimal and efficient mixed integer-linear programming (MILP)-based algorithm to handle intrarow MinIA constraints. We then extend the MILP-based algorithm to handle both inter-row and intrarow MinIA constraints. Both of our algorithms guarantee to fix all MinIA constraint violations. Experimental results demonstrate that our algorithms only perturb the original placement and threshold voltage assignment solutions minimally to eliminate all violations and are fast in practice. [ABSTRACT FROM AUTHOR]

With the increasing complexity of circuit design in recent years, the pin assignment and escape routing problems for field-programmable gate array (FPGA) on a printed circuit board (PCB) have become greatly difficult due to the fast increase in pin count and density. Most existing works only focus on either the FPGA pin assignment problem or the PCB escape routing problem independently, but cannot handle them simultaneously. In this paper, we propose an integer linear programming based method to simultaneously solve the problem of pin assignment and escape routing for FPGA-PCB co-design. Moreover, differential pairs and single-ended signals are handled together optimally to minimize the total wirelength in escape routing. Encouraging experimental results are shown to support our approach showing reduction in the number of PCB routing layers and/or wirelength. [ABSTRACT FROM PUBLISHER]

Wire bonding is currently the most popular method for connecting signals between dies in system-in-package (SiP) design. Pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for SiP design because the quality of a pad assignment solution affects both the cost and the performance of an SiP design. In this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking SiP design. We first consider the two-die cases and die-stacks with a bridging die, and present a minimum-cost flow-based approach to optimally solve them in polynomial time. We then describe an approach, which uses a modified left-edge algorithm and an integer linear programming technique, for pyramid die-stacks with no bridging die. Finally, we discuss extensions of the two approaches to handle additional design constraints. Encouraging experimental results are shown to support our approaches. [ABSTRACT FROM AUTHOR]

In this paper, we present the first exact approach to solve the constrained input/output (I/O) placement problem for field programmable gate arrays (FPGAs) that support multiple I/O standards. We derive a compact integer linear program formulation for the constrained I/O placement problem. The size of the integer linear program derived is independent of the number of I/O objects to be placed and, hence, is scalable to very large design instances. For example, for a Xilinx Virtex-E FPGA, the number of integer variables required is never more than 32 and is much smaller for practical design instances. Extensive experimental results using a noncommercial integer linear program solver shows that it only takes seconds to solve the resultant integer linear program in practice. In addition, we also propose a new overall placement flow to place both core logic and I/Os. [ABSTRACT FROM AUTHOR]