In the layout design of transport-processing FPGAs, it is not only required that routing congestion be kept small but also that circuits implemented on them should operate with higher operation frequency. This paper extends the proposed simultaneous placement and global routing algorithm for transport-processing FPGAs, whose objective is to minimize the routing congestion, and proposes a new algorithm, in which the length of each critical signal path (path length) is limited within a specified upper bound imposed on it (path length constraint). The algorithm is based on the hierarchical bipartitioning of the layout regions and LUT (lookup table) sets that are to be placed. Each bipartitioning procedure consists of three phases: (1) estimation of path lengths, (2) bipartitioning of a set of terminals, and (3) bipartitioning of a set of LUTs. After searching the paths with tighter path length constraints by estimating the path lengths in (1), phases (2) and (3) are executed so that their path lengths are reduced with higher priority, and thus path length constraints are not violated. The algorithm has been implemented and applied to transport-processing circuits and compared with conventional approaches. The results demonstrate that the algorithm resolves path length constraints for 11 out of 13 circuits, though it increases the routing congestion by an average of 20%. After detailed routing, it achieves 100% routing for all the circuits and reduces the circuit delay by an average of 23%.

No abstract available.

Technology mapping algorithms for LUT (Look Up Table) based FPGAs have been proposed to transfer a Boolean network into logic-blocks. However, since those algorithms take no layout information into account, they do not always lead to excellent results. In this paper, a simultaneous technology mapping, placement and global routing algorithm for FPGAs, Maple, is presented. Mapleis an extended version of a simultaneous placement and global routing algorithm for FPGAs, which is based on recursive partition of layout regions and block sets. Maple inherits its basic processes and executes the technology mapping simultaneously in each recursive process. Therefore, the mapping can be done with the placement and global routing information. Experimental results for some benchmark circuits demonstrate its efficiency and effectiveness.

An FPGA layout algorithm is presented, which deals with placement and global routing simultaneously by fully exploiting its regular structure. It is based on a simple and fast top-down hierarchical bi-partitioning, with placement and global routes represented by positions of logic-blocks and pseudo-blocks, respectively. Experimental results for several benchmark circuits demonstrates its efficiency and effectiveness.>

A one-dimensional compaction method for layout patterns including rectilinear macrocells on any number of layers is presented. The algorithm is based on the shortest path search on a constraint graph. It generates an optimal layout pattern in the smallest area by introducing effective jogs in O (N log N) time, where N is the number of line segments of the input pattern and inserted jogs. The jogs are inserted by means of an enhanced plane-sweep method developed in the field of computational geometry. Performance data of an experimental program show its efficiency.>

The SURF routing system employs a grid-less flexible

A new gridless router accelerated by Content Addressable Memory (CAM) is presented. A gridless version of the line-expansion algorithm is implemented, which always finds a path if one exists. The router runs in linear time by means of the CAM-based accelerator. Experimental results show that the more obstacles there are in the routing region, the more effective the CAM-based approach is.

Dynamic layout representation is a key problem in developing a building block layout system. We have unified topological and geometrical representations, and developed efficient methods to update topological information after geometrical operations. The experimental results are very promising. This representation is the key for information flow in BEAR — a new building block layout system being developed at U. C. Berkeley.