| Title | CrossRouter: A Droplet Router for Cross-Referencing Digital Microfluidic Biochips |
| Author | *Zigang Xiao, Evangeline F.Y. Young (The Chinese University of Hong Kong, Hong Kong) |
| Page | pp. 269 - 274 |
| Keyword | droplet routing, biochip, cross-referencing, DMFB, microfluidic |
| Abstract | Digital Microfluidic Biochip (DMFB) has drawn lots of attention today. It offers a promising platform for various kinds of biochemical experiments. DMFB that uses cross-referencing technology to drive droplets movements scales down the control pin number on chip, which not only brings down manufacturing cost but also allows large-scale chip design. However, the cross-referencing scheme that imposes different voltage on rows and columns to activate the cells, might cause severe electrode interference, and hence greatly decreases the degree of parallelism of droplet routing. Most of the previous papers get a direct-addressing result first, and then convert to cross-referencing compatible result.This paper proposes a new method that solves the droplet routing problem on cross-referencing biochip directly. Experimental results on public benchmarks demonstrate the effectiveness and efficiency of our method in comparison with the latest work on this problem. |
| Slides | |
| Title | Optimal Simultaneous Pin Assignment and Escape Routing for Dense PCBs |
| Author | *Hui Kong, Tan Yan, Martin D. F. Wong (University of Illinois at Urbana-Champaign, U.S.A.) |
| Page | pp. 275 - 280 |
| Keyword | Pin assignment, Escape routing, PCB routing, Algorithms |
| Abstract | In PCB designs, pin positions greatly affect routability of the design. State-of-the-art pin assignment algorithms are guided by simple (heuristic) metrics to estimate routability and thus have no guarantee to obtain a routable solution. In this paper, we present a novel approach to obtain a pin assignment solution that guarantees routability. We show that the problem of simultaneous pin assignment and escape routing can be solved optimally in polynomial time. We then focus on the pin assignment and escape routing for the terminals in a bus, and present algorithmic enhancements as well as discuss the trade-offs between single-layer and multi-layer implementations. We tested our approach on a state-of-the-art industrial board with 80 buses (over 7000 nets). The pin assignment and escape routing solutions for all the 80 buses are successfully obtainted in less than 5 minutes of CPU time. |
| Title | CAFE router: A Fast Connectivity Aware Multiple Nets Routing Algorithm for Routing Grid with Obstacles |
| Author | *Yukihide Kohira (The University of Aizu, Japan), Atsushi Takahashi (Osaka University, Japan) |
| Page | pp. 281 - 286 |
| Keyword | river routing, length-matching, PCB routing |
| Abstract | In this paper, we propose CAFE router which obtains routes of multiple nets with target wire lengths for single layer routing grid with obstacles. CAFE router extends the route of each net from a pin to the other pin greedily so that the wire length of the net approaches its target wire length. Experiments show that CAFE router obtains the routes of nets with small length error in short time. |
| Title | Obstacle-Aware Longest Path using Rectangular Pattern Detouring in Routing Grids |
| Author | Jin-Tai Yan, Ming-Ching Jhong, *Zhi-Wei Chen (Chung Hua University, Taiwan) |
| Page | pp. 287 - 292 |
| Keyword | detailed routing, detouring path, bus routing, pattern routing |
| Abstract | As the clock frequency increases, signal propagation delays on PCBs are requested to meet the timing specifications with very high accuracy. Generally speaking, the length controllability of a net decides the routing delay of the net. If a routing result has the higher length controllability, the routing delay will be obtained with higher accuracy. In this paper, given a start terminal, S, and a target terminal, T, in mxn routing grids with obstacles, based on the rectangular partition in routing grids and the analysis of unreachable grids in rectangular pattern detouring, an efficient O(mnlog(mn)) algorithm is proposed to generate the longest path in routing grids from S to T. Compared with the US routing[5], our proposed routing approach can achieve longer paths for tested examples in less CPU time. |
| Slides | |