Placement and routing are the most time-consuming processes in automatically synthesizing and configuring circuits for field-programmable gate arrays (FPGAs). In this paper, we use the negotiation-based paradigm to parallelize placement. Our new FPGA placer, NAP (Negotiated Analytical Placement), uses an analytical technique for coarse placement and the negotiation paradigm for detailed placement. We describe the serial algorithm and report results. We also report findings related to parallelizing NAP under a multicast networking and multi-threaded operating system environment; the parallel placer is tolerant to multicast packet loss as well as out-of-order packet delivery. Our parallel placer exhibits little performance degradation while attaining speedups of 2 using 3 processors.

The negotiation-based routing paradigm has been used successfully in a number of FPGA routers. In this paper, we report several new findings related to the negotiation-based routing paradigm. We examine in-depth the convergence of the negotiation-based routing algorithm. We illustrate that the negotiation-based algorithm can be parallelized. Finally, we demonstrate that a negotiation-based parallel FPGA router can perform well in terms of delay and speedup with practical FPGA circuits.

This paper presents a novel systematic offset minimization circuit for designing a class-AB CMOS operational amplifier. The proposed structure has a replica-gain circuit, generating a DC replica bias to the differential input stage, and providing differential gain as well as level conversion to drive the class-AB output stage. Statistical measurements on 15 samples of the amplifier showed the mean and standard deviation of the input offset were of 0.88 mV and 0.49 mV respectively. These results were achieved using an active area of only 3700 /spl mu/m/sup 2/ for the critical differential input stage in a 0.8 /spl mu/m standard CMOS technology.

The problems of placement and routing are without doubt the most time-consuming part of the process of automatically synthesizing and configuring circuits for field-programmable gate arrays (FPGAs). FPGAs offer the ability to quickly reconfigure circuits to support rapid prototyping, emulation, or configurable computing, but the time to perform placement and routing, which can take many hours, has become a serious bottleneck. This problem is addressed here by showing that the negotiation-based routing paradigm, which has been applied successfully in several FPGA routers, can be parallelized to achieve increased performance without any significant decrease in the quality of the results. In this paper, we report several new findings related to the negotiation-based routing paradigm. We examine in-depth the convergence of the negotiation-based routing algorithm. We illustrate that the negotiation-based algorithm can be parallelized. Finally, we demonstrate that a negotiation-based parallel FPGA router performs well in terms of delay and speedup with practical FPGA circuits.

We present schemes to reduce the compilation time of configurable hardware that solves Boolean satisfiability. The SAT solver presented by Zhong et al. (1998) has a large compilation time overhead mainly due to placement and routing of many FPGAs. We attack the problem on three fronts. First, we partition the SAT solver into instance-specific and instance non-specific components. Secondly, we transform SAT instances into canonical forms; and finally we present a board-level multiple-chip architecture to solve large SAT instances. All these efforts amount to a reduction in placement and routing time to configure the configurable hardware. We are able to reduce the compilation time to mere routing time of the implication circuits for each instance of the SAT problem, given the best scenario.

This paper presents a new spectral partitioning formulation which directly incorporates vertex size information by modifying the Laplacian of the graph. Modifying the Laplacian produces a generalized eigenvalue problem, which is reduced to the standard eigenvalue problem. Experiments show that the scaled ratio-cut costs of results on benchmarks with arbitrary vertex size improve by 22% when the eigenvectors of the Laplacian in the spectral partitioner KP are replaced by the eigenvectors of our modified Laplacian. The inability to handle vertex sizes in the spectral partitioning formulation has been a limitation in applying spectral partitioning in a multilevel setting. We investigate whether our new formulation effectively removes this limitation by combining it with a simple multilevel bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experiments show that in a multilevel setting where the spectral partitioner KP provides the initial partitions of the most contracted graph, using the modified Laplacian in place of the standard Laplacian is more efficient and more effective in the partitioning of graphs with arbitrary-size and unit-size vertices; average improvements of 17% and 18% are observed for graphs with arbitrary-size and unit-size vertices, respectively. Comparisons with other ratio-cut based partitioners on hypergraphs with unit-size as well as arbitrary-size vertices, show that the multilevel spectral partitioner produces either better results or almost identical results more efficiently.

The authors describe their experience and progress in accelerating an FPGA router. Placement and routing is undoubtedly the most time-consuming process in automatic chip design or configuring programmable logic devices as reconfigurable computing elements. Their goal is to accelerate routing of FPGAs by 10 fold with a combination of processor clusters and hardware acceleration. Coarse-grain parallelism is exploited by having several processors route separate groups of nets in parallel. A hardware accelerator is presented which exploits the fine-grain parallelism in routing individual nets.

We develop a new multi-way, hybrid spectral/iterative hypergraph partitioning algorithm that combines the strengths of spectral partitioners and iterative improvement algorithms to create a new class of partitioners. We use spectral information (the eigenvectors of a graph) to generate initial partitions, influence the selection of iterative improvement moves, and break out of local minima. Our 3-way and 4-way partitioning results exhibit significant improvement over current published results, demonstrating the effectiveness of our new method. Our hybrid algorithm produces an improvement of 25% over GFM for 3-way partitions, 41% improvement over GFM for 4-way partitions, and 58% improvement over ML/sub F/ for 4-way partitions.

This paper presents a new spectral partitioning formation which directly incorporates vertex size information. The new formulation results in a generalized eigenvalue problem, and this problem is reduced to the standard eigenvalue problem. Experimental results show that incorporating vertex sizes into the eigenvalue calculation produces results that are 50% better than the standard formation in terms of scaled ratio-cut cost, even when a Kernighan-Lin style iterative improvement algorithm taking into account vertex sizes is applied as a post-processing step. To evaluate the new method for use in multi-level partitioning, we combine the partitioner with a multi-level bottom-up clustering algorithm and an iterative improvement algorithm for partition refinement. Experimental results show that our new spectral algorithm is more effective than the standard spectral formulation and other partitioners in the multi-level partitioning of hypergraphs.

Recent research on FPGA partitioning has focused on finding minimum cuts between partitions without regard to the routability of the partitioned subcircuits. In this paper, we develop a spectral approach to multiway partitioning in which the primary goal is to produce routable subcircuits while maximizing FPGA device utilization. To assist the partitioner in assessing the routability of the partitioned subcircuits, we have developed a theory to predict the routability of the partitioned subcircuits prior to partitioning. Advancement over previous work is evidenced by results of experiments on standard MCNC benchmarks.

Recent research on FPGA partitioning has focussed on finding minimum cuts between partitions without regard to the routability of the partitioned subcircuits. In this paper we develop a spectral approach to multi-way partitioning in which the primary goal is to produce routable subcircuits while maximizing FPGA device utilization. To assist the partitioner in assessing the routability of the partitioned subcircuits, we have developed a theory to predict the routability of the partitioned subcircuits prior to partitioning. Advancement over the current work is evidenced by results of experiments on the standard MCNC benchmarks.

Recent research on partitioning has focused on the ratio-cut cost metric, which maintains a balance between the cost of the edges cut and the sizes of the partitions without fixing the size of the partitions a priori. Iterative approaches and spectral approaches to two-way ratio-cut partitioning have yielded higher quality partitioning results. In this paper, we develop a spectral approach to multi-way ratio-cut partitioning that provides a generalization of the ratio-cut cost metric to L-way partitioning and a lower bound on this cost metric. Our approach involves finding the k smallest eigenvalue/eigenvector pairs of the Laplacian of the graph. The eigenvectors provide an embedding of the graph's n vertices into a k-dimensional subspace. We devise a time and space efficient clustering heuristic to coerce the points in the embedding into k partitions. Advancement over the current work is evidenced by the results of experiments on the standard benchmarks.>

A new algorithm for technology mapping of lookup table-based Field-Programmable Gate Arrays (FPGA's) is presented. It has the capability of producing compact designs (minimizing the number of cells (CLB's)), as well as the flexibility of trading routability with compactness of a design. Research in this area has focussed on minimizing the number of cells. However, minimizing the number of cells without regard to routability is ineffective. Since placement and routing is really the most time-consuming part of the FPGA design process, producing a routable design with a slightly larger number of cells is preferable than producing a design using fewer cells which is difficult to route, or in the worst case unroutable. We have implemented our algorithm in the Rmap program, and studied routability of two other mappers with respect to Rmap. Rmap produces mappings with better routability characteristics, and more significantly Rmap produces routable mappings when other mappers do not.>

Efficient utilization of Field Programmable Gate Arrays (FPGAs) depends on the ability to determine whether designs will exceed the logic or routing capacities of the devices.Here, we focus on the problem of assessing the routability of designs for FPGAs before place-and-rpute.Specifically, we identify the relevant wmeabilit y t heorles, modify and adapt the theories for FPGAs, and conduct experiments to validate the theories.

Article Free Access Share on Spectral K-way ratio-cut partitioning and clustering Authors: Pak K. Chan View Profile , Martine D. F. Schlag View Profile , Jason Y. Zien View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 749–754https://doi.org/10.1145/157485.165117Published:01 July 1993Publication History 93citation903DownloadsMetricsTotal Citations93Total Downloads903Last 12 Months83Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The performance of multilevel logic minimization tools for a lookup-table-based field-programmable gate array (FPGA) technology was examined. The experiments used the university tools, misII for combinational logic minimization and mustang for state assignments, and the industrial tools xnfmap for technology mapping and apr for automatic placement and routing. The quality of the multilevel logic minimization tools was measured by the number of routed configurable logic blocks (CLBs) in the FPGA realization. A linear relationship between the number of literals and the number of routed CLBs was found. In all 34 MCNC-89 benchmark finite state machines, one-hot state assignment resulted in substantially fewer CLBs than any other state encoding methods available in mustang. A delay model that provides routing delay prediction based on fan-out is presented and used to estimate the delays of the FPGA implementation of logic expressions prior to technology mapping, place, and route.>

An algorithm for technology mapping of lookup-table-based field-programmable gate arrays is presented. It has the capability of producing slightly more compact designs than some existing mappers, and it offers the flexibility of trading routability with compactness of a design. The algorithm is implemented in the Rmap program and routability is compared with that of two other mappers. It is found that Rmap can produce mappings with better routability characteristics, and it produces routable mappings when other mappers do not.>

The worst-case carry propagation delays in carry-skip adders and block carry-lookahead adders depend on how the full adders are grouped structurally together into blocks as well as the number of levels. The authors report on a multidimensional dynamic programming paradigm for configuring these two adders to attain minimum latency. Previous methods are applicable only to very limited delay models that do not guarantee a minimum latency configuration. Under the delay model, critical path delay is calculated not only taking into account the intrinsic gate delays, but also the fanin and fanout contributions.>

The worst-case carry propagation delays in carry-skip adders and block carry-lookahead adders depend on how the full adders are grouped structurally together into blocks as well as the number of levels. The authors report a multidimensional dynamic programming paradigm for configuring these two adders to attain minimum latency. Previous methods are applicable only to very limited delay models that do not guarantee a minimum latency configuration. Under the proposed delay model, critical path delay is calculated taking into account not only the intrinsic gate delays but also the fanin and fanout contributions.>

For the original article see ibid., vol.9, no.4, p.352-66 (1990). The commenter notes that in the above-titled paper L. Pillage and R. Rohrer employ the moment-matching technique to provide different models of different accuracies for a given linear network, the general form of which is often referred to as the Pade approximation. He briefly points out the shortcomings of the Pade approximation and provides a bibliography that documents the developments of model reduction techniques in control theory and econometrics. These developments are of interest to practitioners in waveform estimation.>

We examine the problem of choosing the proper sizes from a cell library for the logic elements of a Boolean network to meet timing constraints on the propagation delay along every path from the primary input to the primary output. If the Boolean network has a tree topology, we show that there exists a pseudo-polynomial time algorithm for finding the optimal solution to this problem. A backtracking-based algorithm for finding feasible solutions for networks that are not trees is also suggested and evaluated.

Two different CMOS implementations of the Manchester carry-skip adder are analyzed using the RC timing model, which provides a unified way of analyzing both CMOS circuits and interconnect. Based on the RC timing model, the authors develop efficient polynomial algorithms to determine near-optimal (in latency) as well as optimal block sizes for the one-level manchester adder with variable carry-skip. An analysis shows that the carry-skip delay in a Manchester adder block is linearly proportional to the block size. The approach provides a general paradigm for analysis and design, applicable to different models of ripple-propagation and carry skip.>

Most RC simulators handle only tree networks, not arbitrary networks. An algorithm is presented for computing signal delays in general RC networks using the RC-tree computation as the primary operation. The algorithm partitions a given network into a spanning tree and links. It computes the signal delay of the spanning tree, and updates the signal delay as it incrementally adds the links back to reconstruct the original network. If m is the number of links, this algorithm requires m(m+1)/2 updates and m+1 tree delay evaluations. All the tree delay evaluations involve computing signal delays with the same resistive spanning tree, but with different values for the capacitors.>

A popular VLSI adder implementation is the Manchester adder using dynamic (precharge) logic, where the ripple-carry propagation delay of a block is proportional to the square of its size. The authors examine two different CMOS implementations of the Manchester adder, analyzing them with the RC timing model, which provides a unified way of analyzing both CMOS circuits and interconnect. Based on the RC timing model, they develop efficient (polynomial) algorithms to determine near-optimal, as well as optimal, block sizes for the one-level Manchester adder with variable carry-skip.>

Most RC simulators only handle tree networks, not arbitrary networks. We present an algorithm for computing signal delays in general RC networks using the RC-tree computation as the primary operation. We partition a given network into a spanning tree and link branches. Then we compute the signal delay of the spanning tree, and update the signal delay as we incrementally add the links back to reconstruct the original network. If m is the number of link branches, this algorithm requires m(m⊕1)/2 updates and m⊕1 tree delay evaluations. All the tree delay evaluations involve computing signal delays with the same resistive spanning tree, but with different values for the capacitors.

The linear RC delay model is commonly used in timing simulators for MOS digital circuits. Most simulators only handle tree networks, not arbitrary networks. More precisely, these simulators treat all networks as if they were trees. Currently, the only alternative is to invert the node-conductance matrix of the RC network numerically. Upper and lower bounds on signal delays in general RC networks are derived. The idea is to bound (element-wise) the inverse of the node-conductance matrix of the network, and use these bounding matrices in formulas for estimating signal delays in RC networks. Evaluating the bounds requires finding the least-resistance paths and the maximum cut between the input mode and the rest of the nodes in the network. For tree networks, the bounds coincide and are the same as those found by using a method due to P. Penfield, et al. (1970).>