The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Hai Zhou - One of the best experts on this subject based on the ideXlab platform.
-
eboarst an efficient edge based obstacle avoiding rectilinear steiner Tree Construction algorithm
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008Co-Authors: Jieyi Long, Hai Zhou, Seda Ogrenci MemikAbstract:Obstacle-avoiding Steiner routing has arisen as a fundamental problem in the physical design of modern VLSI chips. In this paper, we present EBOARST, an efficient four-step algorithm to construct a rectilinear obstacle-avoiding Steiner Tree for a given set of pins and a given set of rectilinear obstacles. Our contributions are fourfold. First, we propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. Second, we present a fast algorithm for the minimum terminal spanning Tree Construction step, which dominates the running time of several existing approaches. Third, we present an edge-based heuristic, which enables us to perform both local and global refinements, leading to Steiner Trees with small lengths. Finally, we discuss a refinement technique called segment translation to further enhance the quality of the Trees. The time complexity of our algorithm is O(nlogn). Experimental results on various benchmarks show that our algorithm achieves 16.56 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner Trees is only 0.46% larger than the best existing solution.
-
efficient steiner Tree Construction based on spanning graphs
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004Co-Authors: Hai ZhouAbstract:The Steiner Minimal Tree (SMT) problem is a very important problem in very large scale integrated computer-aided design. Given n points on a plane, an SMT connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running time. This paper records an implementation of an efficient SMT algorithm that has a worst case running time of O(nlogn) and a performance close to that of the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et al.'s spanning graph. Extensive experimental studies are conducted to compare it with other programs.
-
efficient steiner Tree Construction based on spanning graphs
International Symposium on Physical Design, 2003Co-Authors: Hai ZhouAbstract:Steiner Minimal Tree (SMT) problem is a very important problem in VLSI CAD. Given n points on a plane, a Steiner minimal Tree connects these points through some extra points (called Steiner points) to achieve a minimal total length. Even though there exist many heuristic algorithms for this problem, they have either poor performances or expensive running times. This paper records an implementation of an efficient Steiner minimal Tree algorithm that has a worst case running time of O(n logn) and a similar performance as the Iterated 1-Steiner algorithm. The algorithm efficiently combines Borah et al.'s edge substitute concept with Zhou et al.'s spanning graph. Extensive experimental studies are conducted to compare it with other programs.
-
efficient minimum spanning Tree Construction without delaunay triangulation
Information Processing Letters, 2002Co-Authors: Hai Zhou, Narendra V Shenoy, William NichollsAbstract:Abstract Given n points in a plane, a minimum spanning Tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n 2 ) time. More efficient approaches find a minimum spanning Tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning Tree Construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning Tree without using Delaunay triangulation.
-
efficient minimum spanning Tree Construction without delaunay triangulation
Asia and South Pacific Design Automation Conference, 2001Co-Authors: Hai Zhou, Narendra V Shenoy, William NichollsAbstract:Minimum spanning Tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning Tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least ω(n2) time. More efficient approaches find a minimum spanning Tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning Tree Construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(n log n) sweep-line algorithm to construct a rectilinear minimum spanning Tree without using Delaunay triangulation.
William Nicholls - One of the best experts on this subject based on the ideXlab platform.
-
efficient minimum spanning Tree Construction without delaunay triangulation
Information Processing Letters, 2002Co-Authors: Hai Zhou, Narendra V Shenoy, William NichollsAbstract:Abstract Given n points in a plane, a minimum spanning Tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n 2 ) time. More efficient approaches find a minimum spanning Tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning Tree Construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning Tree without using Delaunay triangulation.
-
efficient minimum spanning Tree Construction without delaunay triangulation
Asia and South Pacific Design Automation Conference, 2001Co-Authors: Hai Zhou, Narendra V Shenoy, William NichollsAbstract:Minimum spanning Tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning Tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least ω(n2) time. More efficient approaches find a minimum spanning Tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning Tree Construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(n log n) sweep-line algorithm to construct a rectilinear minimum spanning Tree without using Delaunay triangulation.
Xinbing Wang - One of the best experts on this subject based on the ideXlab platform.
-
distributed multicast Tree Construction in wireless sensor networks
IEEE Transactions on Information Theory, 2017Co-Authors: Hongyu Gong, Luoyi Fu, Xinzhe Fu, Lutian Zhao, Kainan Wang, Xinbing WangAbstract:Multicast Tree is a key structure for data dissemination from one source to multiple receivers in wireless networks. Minimum length multica modeled as the Steiner Tree problem, and is proven to be NP-hard. In this paper, we explore how to efficiently generate minimum length multi wireless sensor networks (WSNs), where only limited knowledge of network topology is available at each node. We design and analyze a simple algorithm, which we call toward source Tree (TST), to build multicast Trees in WSNs. We show three metrics of TST algorithm, i.e., running and energy efficiency. We prove that its running time is $O(\sqrt {n\log n})$ , the best among all existing solutions to our best knowledge. We prove that TST Tree length is in the same order as Steiner Tree, which give a theoretical upper bound and use simulations to show the ratio be only 1.114 when nodes are uniformly distributed. We evaluate energy efficiency in terms of message complexity and the number of forwarding prove that they are both order-optimal. We give an efficient way to construct multicast Tree in support of transmission of voluminous data.
Xianlong Hong - One of the best experts on this subject based on the ideXlab platform.
-
an o nlogn algorithm for obstacle avoiding routing Tree Construction in the λ geometry plane
International Symposium on Physical Design, 2006Co-Authors: Zhe Feng, Xianlong Hong, Tong Jing, Guiying YanAbstract:Routing is one of the important phases in VLSI/ULSI physical design. The obstacle-avoiding rectilinear Steiner minimal Tree (OARSMT) Construction is an essential part of routing since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Efficient OARSMT algorithms can be employed in practical routers iteratively. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y- / X-architecture (λ3- / λ4-geometry) to improve the chip performance. This paper presents an O(nlogn) heuristic, λ-OASMT, for obstacle-avoiding Steiner minimal Tree Construction in the λ-geometry plane. Based on obstacle-avoiding constrained Delaunay triangulation, a full connected Tree is constructed and then embedded into λ-OASMT by a novel method called zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with two most recent works on OARSMT problem, λ-OASMT obtains up to 30Kx speedup with an even better quality solution. We have tested randomly generated cases with up to 1K terminals and 10K rectilinear obstacles within 3 seconds on a Sun V880 workstation (755MHz CPU and 4GB memory). The high efficiency and accuracy of λ-OASMT make it extremely practical and useful in the routing phase, as well as interconnect estimation in the process of floorplanning and placement.
-
an o n log n algorithm for obstacle avoiding routing Tree Construction in the λ geometry plane
International Symposium on Physical Design, 2006Co-Authors: Zhe Feng, Xianlong Hong, Tong Jing, Yu Hu, Xiaodong HuAbstract:Routing is one of the important phases in VLSI/ULSI physical design. The obstacle-avoiding rectilinear Steiner minimal Tree (OARSMT) Construction is an essential part of routing since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Efficient OARSMT algorithms can be employed in practical routers iteratively. Recently, IC routing and related researches have been extended from Manhattan architecture (λ 2- geometry) to Y- / X-architecture (λ 3- / λ 4- geometry) to improve the chip performance. This paper presents an O(nlogn) heuristic, λ-OASMT, for obstacle-avoiding Steiner minimal Tree Construction in the λ-geometry plane. Based on obstacle-avoiding constrained Delaunay triangulation, a full connected Tree is constructed and then embedded into λ-OASMT by a novel method called zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with two most recent works on OARSMT problem, λ-OASMT obtains up to 30Kx speedup with an even better quality solution. We have tested randomly generated cases with up to 1K terminals and 10K rectilinear obstacles within 3 seconds on a Sun V880 workstation (755MHz CPU and 4GB memory). The high efficiency and accuracy of λ-OASMT make it extremely practical and useful in the routing phase, as well as interconnect estimation in the process of floorplanning and placement.
-
cdcTree novel obstacle avoiding routing Tree Construction based on current driven circuit model
Asia and South Pacific Design Automation Conference, 2006Co-Authors: Tong Jing, Lei He, Zhe Feng, Xianlong HongAbstract:Routing Tree Construction is a fundamental problem in modern VLSI design. In this paper we propose CDC-Tree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDC-Tree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting Tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50.
-
the polygonal contraction heuristic for rectilinear steiner Tree Construction
Asia and South Pacific Design Automation Conference, 2005Co-Authors: Yin Wang, Xianlong Hong, Tong Jing, Yang Yang, Guiying YanAbstract:Motivated by VLSI/ULSI routing applications, we present a heuristic for rectilinear Steiner minimal Tree (RSMT) Construction. We transform a rectilinear minimum spanning Tree (RMST) into an RSMT by a novel method called polygonal contraction. Experimental results show that the heuristic matches or exceeds the solution quality of previously best known algorithms and runs much faster.
Aichun Pang - One of the best experts on this subject based on the ideXlab platform.
-
a mobility aware node deployment and Tree Construction framework for zigbee wireless networks
IEEE Transactions on Vehicular Technology, 2013Co-Authors: Yuanyao Shih, Weiho Chung, Picheng Hsiu, Aichun PangAbstract:ZigBee is a specification formalized by the IEEE 802.15.4 standard for low-power low-cost low-data-rate wireless personal area networks. In ZigBee networks, a Tree topology is often used to construct a wireless sensor network for data delivery applications. However, delivery failures constantly occur in ZigBee wireless applications due to node movements and network topology changes. The conventional route reConstruction method is designed to mitigate the effects of topology changes, but it consumes a large amount of resources. In this paper, we exploit the regularity in node mobility patterns to reduce the frequency of route reConstructions and ensure that the transmission of data to mobile nodes is efficient. To increase the data delivery ratio and mitigate the effects of packet loss caused by the node mobility, we propose a ZigBee node deployment and Tree Construction framework. In particular, the framework considers the regularity in mobility patterns during the Construction of the routing Tree and deployment of nodes. It also includes an overhearing mechanism for mobile nodes to further improve the data delivery ratio. We present details of the proposed algorithms for node deployment and Tree Construction in the framework. The effectiveness of network topologies constructed under the framework is demonstrated through comprehensive ns-2 simulations based on two real-world scenarios. The results show that our approach can construct ZigBee Tree topologies with a high data delivery ratio and low routing overhead.
