In this article, we study the technology mapping problem for a novel field-programmable gate array (FPGA) architecture that is based on k -input single-output programmable logic array- (PLA-) like cells, or, k/m -macrocells. Each cell in this architecture can implement a single output function of up to k inputs and up to m product terms. We develop a very efficient technology mapping algorithm, k_m_flow, for this new type of architecture. The experimental results show that our algorithm can achieve depth-optimality on almost all the testcases in a set of 16 Microelectronics Center of North Carolina (MCNC) benchmarks. Furthermore it is shown that on this set of benchmarks, with only a relatively small number of product terms ( m ≤ k + 3), the k/m -macrocell-based FPGAs can achieve the same or similar mapping depth compared with the traditional k -input single-output lookup table- ( k -LUT-) based FPGAs. We also investigate the total area and delay of k/m -macrocell-based FPGAs and compare them with those of the commonly used 4-LUT-based FPGAs. The experimental results show that k/m -macrocell-based FPGAs can outperform 4-LUT-based FPGAs in terms of both delay and area after placement and routing by VPR on this set of benchmarks.

Placement is one of the most important steps in the RTL-to-GDSII synthesis process, as it directly defines the interconnects, which have become the bottleneck in circuit and system performance in deep submicron technologies. The placement problem has been studied extensively in the past 30 years. However, recent studies show that existing placement solutions are surprisingly far from optimal. The first part of this tutorial summarizes results from recent optimality and scalability studies of existing placement tools. These studies show that the results of leading placement tools from both industry and academia may be up to 50% to 150% away from optimal in total wirelength. If such a gap can be closed, the corresponding performance improvement will be equivalent to several technology-generation advancements. The second part of the tutorial highlights the recent progress on large-scale circuit placement, including techniques for wirelength minimization, routability optimization, and performance optimization.

In this paper we study the large-scale mixed-size placement problem where there is a significant size variation between big and small placeable objects (the ratio can be as large as 10,000). We develop a multi-level optimization algorithm, MPGMS, for this problem which can efficiently handle both large-scale designs and large size variations. Compared with the recently published work [1] on large-scale mixed macro and standard cell placement benchmarks for wirelength minimization, our method can achieve 13% wirelength reduction on average with comparable runtime.

Multiple clock cycles are needed to cross the global interconnects for multi-gigahertz designs in nanometer technologies. For synchronous designs, this requires retiming and pipelining on global interconnects. In this paper, we present a practical solution for simultaneous retiming and multilevel global placement for performance optimization, based on the theory and algorithms of sequential timing analysis (Seq-TA). We extend the Seq-TA to handle gates/clusters with multiple outputs and integrate it into a multilevel optimization framework for simultaneous retiming and placement. We also develop two speed-up techniques which enable the Seq-TA to be efficiently integrated into a simulated annealing-based multilevel coarse placement for large-scale designs. Experimental results show that (i) retiming can improve the performance (delay) by 14% on average when it is applied after placement; (ii) our approach for simultaneous retiming and placement can outperform the two-step approach (placement followed by retiming) by 10% on average in terms of delay minimization.

In this paper, we develop a multilevel global placement algorithm (MGP) integrated with fast incremental global routing for directly updating and optimizing congestion cost during physical hierarchy generation. Fast global routing is achieved using a fast two-bend routing and incremental A-tree algorithm. The routing congestion is modeled by the wire usage estimated by the fast global router. A hierarchical area density control is developed for placing objects with significant size variations. Experimental results show that, compared to GORDIAN-L, the wire length-driven MGP is 4-6.7 times faster and generates slightly better wire length for test circuits larger than 100000 cells. Moreover, the congestion-driven MGP improves wiring overflow by 45%-74% with 5% larger bounding box wire length but 3%-7% shorter routing wire length measured by a graph-based A-tree global router.

Modern high performance design requires using a large number of buffers. In practice, buffers are organized into buffer blocks and planned in the early stages of design process [1]. Thus, the locations of buffer blocks are usually fixed prior to routing tree construction. In this paper we present the first algorithm for simultaneous routing tree construction and buffer insertion for multiple-pin nets under fixed buffer locations. Given a source and n sinks of a net, the required arrival time associated with each sink, and m buffers with fixed locations, our algorithm can construct a routing tree for this net with possible insertion of buffers at given locations such that the required arrival time at the source is maximized. Experimental results show that our algorithm is efficient to handle fixed buffer location constraints and can also be used for routing tree construction without buffer insertion. Moreover, it can handle obstacles and congestion which will benefit its adaption in a global router. Compared to the well-known BA-tree algorithm [2] followed by a post-processing step for handling fixed buffer location constraints, our algorithm outperforms it by up to 46% in terms of delay while using comparative wirelength.

In this paper, we study the technology mapping problem for a novel FPGA architecture that is based on k-input single-output PLA-like cells, or, k/m-macrocells. Each cell in this architecture can implement a single output function of up to k inputs and up to m product terms. We develop a very efficient technology mapping algorithm, k_m_flow, for this new type of architecture. The experiment results show our algorithm can achieve depth-optimality in practically all cases. Furthermore it is shown that the k/m-macrocell based FPGAs are practically equivalent to the traditional k-LUT based FPGAs with only a relatively small number of product terms (m≤k + 3). We also investigate thetotal are and delay of k/m-macrocell based FPGAs on various benchmarks to compare it with commonly used 4-LUT based FPGAs. The experimental result shows k/m-macrocell based FPGAs can outperform 4-LUT based FPGAs in terms of both delay and area after placement and routing by VPR.