A full-scale solution to the rectilinear obstacle-avoiding Steiner problem

Routing is one of the important steps in very/ultra large-scale integration (VLSI/ULSI) physical design. Rectilinear Steiner minimal tree (RSMT) construction is an essential part of routing. Macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. However, OARSMT algorithms for multi-terminal net routing still cannot meet the requirements of practical applications. This paper focuses on the OARSMT problem and gives a solution to full-scale nets based on two algorithms, namely An-OARSMan and FORSTer. (1) Based on ant colony optimization (ACO), An-OARSMan can be used for common scale nets with less than 100 terminals in a circuit. An heuristic, greedy obstacle penalty distance (OP-distance), is used in the algorithm and performed on the track graph. (2) FORSTer is a three-step heuristic used for large-scale nets with more than 100 terminals in a circuit. In Step 1, it first partitions all terminals into some subsets in the presence of obstacles. In Step 2, it then connects terminals in each connected graph with one or more trees, respectively. In Step 3, it finally connects the forest consisting of trees constructed in Step 2 into a complete Steiner tree spanning all terminals while avoiding all obstacles. (3) These two graph-based algorithms have been implemented and tested on different kinds of cases. Experimental results show that An-OARSMan can handle both convex and concave polygon obstacles with short wire length. It achieves the optimal solution in the cases with no more than seven terminals. The experimental results also show that FORSTer has short running time, which is suitable for routing large-scale nets among obstacles, even for routing a net with one thousand terminals in the presence of 100 rectangular obstacles.     

A GRASP heuristic for the delay-constrained multicast routing problem

The increasing development of real-time multimedia network applications, many of which require multiple participants, has created the need for efficient multicast routing algorithms. Examples of such applications include video and tele-conferencing, video-on-demand, tele-medicine, distance education, etc. Several of them require multicasting with a certain Quality of Service (QoS) with respect to elements such as delay or bandwidth. This paper deals with Delay-Constrained Multicast Routing (DCMR) where the maximum end-to-end delay in a multicast session is bounded. The DCMR problem can be reduced to the Constrained Minimum Steiner Tree Problem in Graphs (CMStTG) which has been proven to be NP-complete. As a result, several heuristics have been developed to help solve it. In this paper, we developed a GRASP heuristic for the DCMR problem. Computational experiments on medium sized problems (50-100 nodes) from literature and comparison with existing algorithms have shown that the suggested GRASP heuristic is superior in quality for this set of problems.     

一种比特平面并行处理的零树编码结构

提出了比特平面并行处理的零树编码结构.根据内嵌编码的零树结构,指出每一个比特平面的编码信息可以同时获得,从而给出了并行的零树编码结构.与现有的结构相比,该结构具有并行度高,没有中间缓冲等特点.实验结果表明,处理速度有明显提高,图像质量可满足大多数应用要求.     

A decision tree cognitive routing scheme for cognitive radio mesh networks

Routing in a cognitive radio network operating in a dynamic environment is a complex decision problem. Diversity in the number of available spectrum bands and their stability, in addition to the secondary users' heterogeneities, affect the consequence of the routing decision. We use a decision theory framework to model the problem of routing under uncertainties involved in a cognitive radio network. A utility function is designed to capture the effect of spectrum measurement, fluctuation of bandwidth availability, and path quality. A node cognitively decides its best candidate among its neighbors by utilizing a decision tree. Each branch of the tree is quantified by the utility function and a posterior probability distribution that predicts the suitability of available neighbors. In decision tree cognitive routing (DTCR), nodes learn their operational environment and adapt their decision‐making accordingly. We compared our scheme with the optimal performance in a highly dynamic environment and local coordination‐based routing and spectrum assignment protocol [1]. Our results show that the DTCR tends to perform near optimum. It easily adapts to environmental dynamics. Copyright © 2013 John Wiley & Sons, Ltd.     

A new delay‐constrained algorithm for multicast routing tree construction

New multimedia applications provide guaranteed end‐to‐end quality of service (QoS) and have stringent constraints on delay, delay‐jitter, bandwidth, cost, etc. The main task of QoS routing is to find a route in the network, with sufficient resources to satisfy the constraints. Most multicast routing algorithms are not fast enough for large‐scale networks and where the source node uses global cost information to construct a multicast tree. We propose a fast and simple heuristic algorithm (EPDT) for delay‐constrained routing problem for multicast tree construction. This algorithm uses a greedy strategy based on shortest‐path and minimal spanning trees. It combines the minimum cost and the minimum radius objectives by combining respectively optimal Prim's and Dijkstra's algorithms. It biases routes through destinations. Besides, it uses cost information only from neighbouring nodes as it proceeds, which makes it more practical, from an implementation point of view. Copyright © 2004 John Wiley & Sons, Ltd.     

A three-sided rearrangeable switching network for a binary fat tree

A binary fat tree needs an internal node to interconnect the left-children, right-children and parent terminals to each other. In this article, we first propose a three-stage, 3-sided rearrangeable switching network for the implementation of a binary fat tree. The main component of this 3-sided switching network (3SSN) consists of a polygonal switch block (PSB) interconnected by crossbars. With the same size and the same number of switches as our 3SSN, a three-stage, 3-sided clique-based switching network is shown to be not rearrangeable. Also, the effects of the rearrangeable structure and the number of terminals on the network switch-efficiency are explored and a proper set of parameters has been determined to minimise the number of switches. We derive that a rearrangeable 3-sided switching network with switches proportional to N ^3/2 is most suitable to interconnect N terminals. Moreover, we propose a new Polygonal Field Programmable Gate Array (PFPGA) that consists of logic blocks interconnected by our 3SSN, such that the logic blocks in this PFPGA can be grouped into clusters to implement different logic functions. Since the programmable switches usually have high resistance and capacitance and occupy a large area, we have to consider the effect of the 3SSN structure and the granularity of its cluster logic blocks on the switch efficiency of PFPGA. Experiments on benchmark circuits show that the switch and speed performances are significantly improved. Based on the experimental results, we can determine the parameters of PFPGA for the VLSI implementation.