SAT based solutions for detailed routing of island style FPGA architectures

Detailed routing solutions for island style FPGA architectures using Boolean satisfiability (SAT) based formulations have been proposed in this paper. Due to decreasing size of ICs and hence, the increasing complexity of the routing resource constraints, routing has been a big challenge in electronic design automation field. Our proposed techniques work on multi-pin net routing where all nets are considered for routing in their intact form whereas, most of the existing routing solutions decompose multi-pin nets into two-pin nets for detailed routing to ease the problem. However this approach, apart from increasing the number of nets in the circuits, may also introduce pin doglegging which, when not permitted by the architecture of FPGA, would require extra constraints to eliminate. Many detailed routers adopt sequential detailed routing approaches which are vulnerable to the net ordering problem which may cause a routable circuit to be erroneously classified as unroutable. Our proposed techniques avoid these pitfalls by keeping the multi-pin nets intact and solve all nets simultaneously using SAT. The SAT-based multi-pin net dogleg-free formulations presented here achieve significant improvement over existing SAT-based solutions with respect to the number of variables and clauses used, thereby achieving greater scalability and also display comparable and sometimes better routability results on benchmark circuits when compared with other detailed routing solutions. Detailed routing is also significantly affected by the architecture of the switching blocks. This paper proposes SAT-based formulation for three different switch box architectures i.e. Subset, Wilton, and Universal switches. Our experiments clearly demonstrate how routing solutions for a circuit can differ significantly for different types of switch boxes.     

Fast coupled noise estimation for crosstalk avoidance in the MCGmultichip module autorouter

A multilayer, multichip module (MCM) router, called MCG, is introduced for x-y routing. An efficient method has been derived to allow candidate routes for the nets to be considered simultaneously for compatibility rather than incrementally extending routes or routing one net at a time as in many other techniques. This allows incorporation of accurate models for determining the potential for crosstalk problems during the routing process. MCG incorporates a crosstalk avoidance procedure which facilitates correct-by-design routing in systems susceptible to noise problems. In comparisons with other routers on industrial benchmarks, the MCG router has shown substantial improvement in routing density, number of layers, number of vias, and total interconnect length over routers such as V4R and SLICE. Our test results show up to 18% improvement in via count and up to 33% improvement in the required number of routing layers for these examples over V4R. One of the benchmarks presented contains 37 VHSIC gate arrays, over 7000 nets, and over 14000 pins (pads). Routing at finer pitches with crosstalk avoidance shows a further improvement in interconnect density     

High-speed IP routing with binary decision diagrams based hardware address lookup engine

With a rapid increase in the data transmission link rates and an immense continuous growth in the Internet traffic, the demand for routers that perform Internet protocol packet forwarding at high speed and throughput is ever increasing. The key issue in the router performance is the IP address lookup mechanism based on the longest prefix matching scheme. Earlier work on fast Internet protocol version 4 (IPv4) routing table lookup includes, software mechanisms based on tree traversal or binary search methods, and hardware schemes based on content addressable memory (CAM), memory lookups and the CPU caching. These schemes depend on the memory access technology which limits their performance. The paper presents a binary decision diagrams (BDDs) based optimized combinational logic for an efficient implementation of a fast address lookup scheme in reconfigurable hardware. The results show that the BDD hardware engine gives a throughput of up to 175.7 million lookups per second (Ml/s) for a large AADS routing table with 33 796 prefixes, a throughput of up to 168.6 Ml/s for an MAE-West routing table with 29 487 prefixes, and a throughput of up to 229.3 Ml/s for the Pacbell routing table with 6822 prefixes. Besides the performance of the scheme, routing table update and the scalability to Internet protocol version 6 (IPv6) issues are discussed.     

Length-constrained escape routing of differential pairs

In this paper, given a set of differential pairs (DPs) inside a single chip and the maximum tolerant length difference in a DP, a length-constrained escape routing problem in DPs is formulated. Firstly, the feasible merging connections and the feasible merging grids of all the DPs can be selected to satisfy the given length constraint and avoid routing an acute angle on a wire. Furthermore, based on the observation of the DP escape routing results from industrial boards, all the DPs can be divided into global and local DPs. By using two-phase escape routing, some local DPs can be escaped under the direction constraint and routed by using direct paths in direct escape routing and the unrouted local DPs and the global DPs can be escaped and routed by using obstacle-aware shortest paths in iterative obstacle-aware flow-based escape routing. Compared with Yan׳s escape router [11] and Li׳s escape router [12], the experimental results show that our proposed approach uses a shorter total wirelength under the larger length constraint and reduces 79.6% and 46.8% of the CPU time on the average to achieve 100% escape routability for six tested examples, respectively. Additionally, our proposed approach can obtain length-constrained escape routing results with the avoidance of routing an acute angle under the smaller length constraint for the tested example in the reasonable CPU time.     

设计规则驱动的多层布线算法

迷宫算法是集成电路两端线网优化布线问题的经典算法。多层布线受复杂版图设计规则约束．简单直接应用迷宫布线算法，或者无法获得优化的结果，或者无法满足设计规则。文章分析了迷宫算法特性与局限．提出基于群组图的多层迷宫算法，圆满地解决了上述问题。     

一种多线程FPGA时序驱动布线算法

随着现场可编程门阵列(FPGA)器件尺寸不断增大,计算机辅助设计(CAD)工具运行时间成为突出的问题。布线是FPGA的CAD流程中最为耗时的一个阶段,一种能有效缩短布线时间的方法就是并行布线。本文提出一种减少FPGA时序驱动布线算法运行时间的多线程方法。该算法首先将信号按照线网的扇出数量进行排序,再将排序后的线网均匀分配到各个线程中,最后并发执行所有的线程。在布线质量没有受到显著影响的前提下,即线长增加2.58%,关键路径延时增加1.78%的情况下,相对于传统通用布局布线工具(VPR)时序驱动布线算法8线程下的加速比为2.46。     

Efficient algorithm for FPGA board routing

A simple and fast algorithm for solving the two-terminal board level routing problem in FPGA-based logic emulation systems is presented. The method is based on the net scan selection process. Experimental results are the first implemented results for an algorithm presented previously. The comparison results show that the current approach achieves better effectiveness and uses less CPU time.     

Efficient routing in MANETs using ordered walks

A new approach for routing protocols operating in MANETs is presented in which flooding is not required to establish paths from sources to destinations on demand in MANETs of moderate size. The concept of ordered walk is introduced as a depth-first search (DFS) that does not rely on geographical or virtual coordinate information and is much more efficient than mere random walks. The benefits of using DFS as the building block of the signaling in MANET routing protocols are exemplified by the introduction of the Ordered Walk Search Algorithm (OSA), which is used as part of the proposed Ordered Walk with Learning (OWL) protocol. OWL integrates OSA with the learning of paths from prior successful and failed attempts, and performs one or multiple concurrent ordered walks to search for destinations. Simulation experiments are used to compare the performance of OWL against that of well-known MANET routing protocols based on BFS (e.g., OLSR and AODV). The results show that OWL can achieve a performance comparable to traditional protocols that rely on some form of flooding of link states or network-wide dissemination of distance information in terms of packet delivery ratios and average end-to-end delays, while incurring up to ten times less overhead than AODV.     

Zone_Cut网络模拟本地路由策略

提出并实现了Zone_Cut网络模拟本地路由策略,根据节点属性的不同将节点分为T区、LD区和HD区,对不同的区域采用不同的存储和查找策略,降低并更好地平衡了路由存储空间和查找时间。基于PDNS的实验结果表明,Zone_Cut 路由策略比 MTree_Nix 路由策略综合性能有大幅提高。低频分组情况下,模拟时间平均减少18.08%,模拟空间平均减少51.23%;高频分组情况下,模拟时间平均减少55.29%,模拟空间平均减少74.4%。     

Coprocessor design for multilayer surface-mounted PCB routing

The authors present the issues involved in the design of a special-purpose processing array system, called HAM, which accelerates computationally intensive wire routing tasks. It is especially suited for double-sided surface-mounted boards, which require complex three-dimensional search operations over multiple wiring planes. The novel features of the design include a hexagonal interconnection scheme to improve workload distributions during multilayer concurrent search operations and the VLSI custom design of the processors. Particular emphasis has been placed on the demands of maze routing. A cell-address propagation scheme, which is quite different from the traditional grid-coordinate approach, is discussed. It provides rapid lookup of pertinent routing information and can be extended to any distributed memory multiprocessor system. A global pipelining scheme of cell updates and expands is discussed. Experimental results are presented relating the speedup to various criteria for two different modes of parallel wave propagation     

Scalable domain partitioning in Internet OSPF routing

This paper addresses the scalability problem arising from rapidly increasing routing overhead at network expansion. Focusing on the OSPF (Open Shortest Path First) protocol, we propose a hierarchical routing scheme of partitioning a routing domain into areas. Supplemented to the scheme is a step to reinforce system performances, particularly reliability, against possible degradation from domain partitioning. For an Internet service provider with its own domain, the framework provides a practical vehicle for scalable hierarchical routing indispensable to overall service quality. Due to the unavailability of similar studies, a simple experiment with a small network is reported on, in place of extensive comparative testing. This revised version was published online in June 2006 with corrections to the Cover Date.     

Putting routing tables in silicon

Moving routing tables from RAM to custom or semicustom VLSI can lower cost and boost performance. The routing table problem is presented by discussing the available architectures and how they are related. It is shown that simple table lookup is just a special case of the standard trie structure and that the use of partitioning combined with the trie structure provides a continuum that can lead to a CAM implementation at one extreme. The high-level tradeoffs in the choice of various parameters for the trie are estimated. A careful choice of word size can balance the requirements for speed with the costs of area. Also considered are the costs and benefits of splitting the table into a number of tries, which are searched simultaneously. VLSI implementations are outlined, and the costs are compared. General CAM structures are not needed for the routing table application, and custom CAMs can be very efficient. Tries, however, can be competitive in many cases, due to the resources available for building conventional memories     

LAKER: learning from past actions to guide future behaviors in ad hoc routing

In this paper, we present a location aided knowledge extraction routing (LAKER) protocol for mobile ad hoc networks (MANETs). The novelty of LAKER is that it learns from past actions to guide future behaviors. In particular, LAKER can gradually discover current topological characteristics of the network, such as population density distribution, residual battery map, and traffic load status. This knowledge can be organized in the form of a set of guiding routes, each of which consists of a chain of guiding positions between a pair of source and destination locations. The guiding route information is learned by individual nodes during route discovery phase, and it can be used to guide future route discovery processes in a more efficient manner. LAKER is especially suitable for mobility models where nodes are not uniformly distributed. LAKER can exploit topological characteristics in these models and limit the search space in route discovery processes in a more refined granularity than location aided routing (LAR) protocol. Simulation results show that LAKER outperforms LAR and DSR in term of routing overhead, saving up to 30–45% broadcast routing messages compared to LAR approach. Copyright © 2006 John Wiley & Sons, Ltd.     

A novel and efficient routing architecture for multi-FPGA systems

Multi-FPGA systems (MFSs) are used as custom computing machines, logic emulators and rapid prototyping vehicles. A key aspect of these systems is their programmable routing architecture which is the manner in which wires, FPGAs and field-programmable interconnect devices (FPIDs) are connected. Several routing architectures for MFSs have been proposed, and previous research has shown that the partial crossbar is one of the best existing architectures. In this paper, we propose a new routing architecture, called the hybrid complete-graph and partial-crossbar (HCGP) which has superior speed and cost compared to a partial crossbar. The new architecture uses both hard-wired and programmable connections between the FPGAs. We compare the performance and cost of the HCGP and partial crossbar architectures experimentally, by mapping a set of 15 large benchmark circuits into each architecture. A customized set of partitioning and interchip routing tools were developed, with particular attention paid to architecture-appropriate interchip routing algorithms. We show that the cost of the partial crossbar (as measured by the number of pins on all FPGAs and FPIDs required to fit a design), is on average 20% more than the new HCGP architecture and as much as 25% more. Furthermore, the critical path delay for designs implemented on the partial crossbar were on average 20% more than the HCGP architecture and up to 43% more. Using our experimental approach, we also explore a key architecture parameter associated with the HCGP architecture-the proportion of hard-wired connections versus programmable connections-to determine its best value     

超平面布线

本文大胆打破了传统通道模型的束缚,建立了一个能更好体现多层布线内在本质约束的新模型：超平面布图模型,在该模型下提出了超平面布线算法。该算法以全新的逆向删冗策略成功地解决了布线线序的问题,使线网布线真正达到了并行处理。算法遵循了王守觉先生关于总体分析的方法作为解决超平面布线问题的指导思想,以布线层数最少化和通孔最少化为目标,通过动态地分析线网间的相互位置关系,全局考虑去释放各线网占据的不合理布线资源     

Net Clustering Based Constructive and Iterative Improvement Approaches for Macro-Cell Placement

We propose a net clustering based RT-level macro-cell placement approaches. Static timing analysis identifies critical nets and critical primary input/output paths. Net clustering (based on shared macro-cells and net criticality) yields clusters wherein each cluster has strongly interdependent nets. The circuit is modeled as a graph in which each vertex v represents a net and each edge (v,u) a shared cell between nets v and u. The net clusters are obtained by applying a clique partitioning algorithm on the circuit graph. Two approaches to generate placements at RTL are proposed: constructive (cluster growth) approach and iterative improvement (simulated annealing) based approach. In the constructive approach, a cluster-level floorplanning is performed and a cluster ordering is obtained. The cluster ordering is used by a constructive procedure to generate the physical placement. In the case of iterative improvement based approach, a good ordering of clusters is obtained using simulated annealing.We report experimental results for five RTL datapaths implemented in 0.35 m technology to demonstrate the efficacy of the proposed approaches. We compared the layouts produced by our approaches with those produced by Flint, an automatic floor planner in Lager IV Silicon Compiler [1]. For constructive placement approach, we obtained an average decrease of 43.4% in longest wirelength and 32.4% in total wirelength. The average area reduction is 7.3%. On the other hand, for the SA-based approach, we obtained an average decrease of 57.6% in longest wirelength and 42.2% in total wirelength. The average reduction in the bounding-box area is 12.3%. As expected, the SA-based approach yielded better optimization results, due to its ability to climb out of local minima.     

VLSI版图综合中的P／G网实体优化布线

本文提出了一种在通道内将Ｐ／Ｇ网与信号网的实体布线一体化考虑的优化布线策略，目的是在保证１００％布通的前提下，完成Ｐ／Ｇ网的平面化实体嵌入和信号网的实体布线，并使Ｐ／Ｇ走线对信号网走线的影响尽可能小。算法以提高布线区利用率、减小通道高度和减少通孔数为目标，实现总体性能的优化。系统实现的结果表明，本文算法所采用的策略是可行的、有效的。     

A Tabu search algorithm for static routing and wavelength assignment problem

Static routing and wavelength assignment (RWA) is usually formulated as an optimization problem with the objective of minimizing wavelength usage (MWU). Existing solution methodologies for the MWU problem are usually based on a two-step approach, where routing and wavelength assignment are done independently. Though this approach can reduce computational cost, the optimality of the solution is compromised. We propose a novel tabu search (TS) algorithm, which considers routing and wavelength assignment jointly without increasing the computational complexity. The performance of the proposed TS algorithm is compared with the integer linear programming (ILP) method, which is known to solve the MWU to optimality. The results for both small and large networks show that our proposed TS algorithm works almost as well as the ILP solution and is much more computationally efficient.     

Interchangeable terminals in channel routing problem

The traditional channel routing problem is known to be solvable, if and only if the constraint graph is acyclic. In the letter we examine channels with two-terminal nets without doglegging and assume that some terminals are interchangeable. A necessary and sufficient condition is established for the interchangeability of the points to ensure solvability. Regular channel structures, like those in gate arrays, are compared. The routability condition is shown to be weaker if noninter-changeable points have different abscissas.     

双层PCB线网均匀化问题及其算法

线网分布均匀性直接影响到PCB上电路的性能。但由于布线问题的计算复杂性很高,在布线过程中很难保证布线的线网均匀性。在本文中,提出了一种双层PCB线网均匀化的方法。