Browsing by Author "Ho, Tsung-Yi"

Now showing 1 - 20 of 37

A Novel Analog Physical Synthesis Methodology Integrating Existent Design Expertise
(2015-02-01)
Wu, Po-Hsun
;
Lin, Mark Po-Hung
;
Chen, Tung-Chieh
;
Yeh, Ching-Feng
;
Li, Xin
Analog layout design has been a manual, time-consuming, and error-prone task for decades. To speed up layout design time for a new design, analog layout designers prefer referring to legacy designs and layouts rather than starting from scratch, or thoroughly applying placement and routing tools because legacy layouts contain pretty much design expertise. Motivated by such layout design process, this paper presents the first knowledge-based physical synthesis methodology to generate new layouts by integrating existent design expertise. The proposed approach can automatically analyze legacy design data including circuits, layouts, and constraints, extract matched sub-circuits between new and legacy designs, and generate multiple layouts for the new design by utilizing the quality-approved legacy layouts as much as possible. Experimental results show that the proposed methodology can achieve high layout reusage rate, and hence the designers\' layout preference can be successfully reserved.
ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips
(2014-09-01)
Liu, Sean Shih-Ying
;
Chang, Chung-Hung
;
Chen, Hung-Ming
;
Ho, Tsung-Yi
;
電子工程學系及電子研究所
The problem of pin-constrained electrowetting-ondielectric (EWOD) biochips becomes a serious issue to realize complex bio-chemical operations. Due to limited number of control pins and routing resources, additional Printed Circuit Board (PCB) routing layers may be required which potentially raises the fabrication cost. Previous state-of-the-art work has tried to develop a framework that uses a network-flow-based method for broadcast electrodeaddressing EWOD biochips. Nevertheless, greedily merging of electrical pins in previous works is at high risk of producing unroutable design. Routability should have higher priority than pin reduction. While previous works dedicated their effort on pin reduction, we have addressed our attention on routability of broadcast addressing. Experimental results demonstrate that taking routability into consideration can even have higher pin reduction. Viewed in this light, we present ACER, a routability driven clustering algorithm followed by escape routing using integer linear programming that effectively solves both pin merging and routing in broadcast addressing framework. Our proposed algorithm does not greedily focus on pin-reduction. Instead, routability is taken into consideration through agglomerative clustering. Compared to previous state-of-the-art, our proposed algorithm can further reduce required control pins by an average of 13% and route the design using 68% less wirelength.
An EDA Framework for Large Scale Hybrid Neuromorphic Computing Systems
(2015)
Wen, Wei
;
Wu, Chi-Ruo
;
Hu, Xiaofang
;
Liu, Beiye
;
Ho, Tsung-Yi
In implementations of neuromorphic computing systems (NCS), memristor and its crossbar topology have been widely used to realize fully connected neural networks. However, many neural networks utilized in real applications often have a sparse connectivity, which is hard to be efficiently mapped to a crossbar structure. Moreover, the scale of the neural networks is normally much larger than that can be offered by the latest integration technology of memristor crossbars. In this work, we propose AutoNCS - an EDA framework that can automate the NCS designs that combine memristor crossbars and discrete synapse modules. The connections of the neural networks are clustered to improve the utilization of the memristor elements in crossbar structures by taking into account the physical design cost of the NCS. Our results show that AutoNCS can substantially enhance the utilization efficiency of memristor crossbars while reducing the wirelength, area and delay of the physical designs of the NCS.
An Optimal Pin-Count Design With Logic Optimization for Digital Microfluidic Biochips
(2015-04-01)
Dinh, Trung Anh
;
Yamashita, Shigeru
;
Ho, Tsung-Yi
;
資訊工程學系
;
Department of Computer Science
Digital microfluidic biochips have become one of the most promising technologies for biomedical experiments. In modern microfluidic technology, reducing the number of independent control pins that reflects most of the fabrication cost, power consumption, and reliability of a microfluidic system, is a key challenge for every digital microfluidic biochip design. However, all the previous chip designs sacrifice the optimality of the problem, and only limited reduction on the number of control pins is observed. Moreover, most existing designs cannot satisfy high-throughput demand for bioassays, and thus inapplicable in practical contexts. In this paper, we propose the first optimal pin-count design scheme for digital microfluidic biochips. By integrating a very simple combinational logic circuit into the original chip, the proposed scheme can provide high-throughput for bioassays with an information-theoretic minimum number of control pins. Furthermore, to cope with the rapid growth of the chip\'s scale, we also propose a scalable and efficient heuristics to reduce the number of control pins. A logic optimization technique, which can be used to reduce the complexity of the integrated combinational logic circuit, is also presented in this paper. Experiments demonstrate that the proposed scheme can obtain much fewer number of control pins compared with the previous state-of-the-art works.
Analog Layout Synthesis with Knowledge Mining
(2015)
Wu, Po-Hsun
;
Lin, Mark Po-Hung
;
Ho, Tsung-Yi
;
資訊工程學系
;
Department of Computer Science
To reduce layout design time, analog layout designers prefer referring to legacy designs and layouts rather than starting from scratch, or thoroughly applying placement and routing tools because legacy layouts contain pretty much design expertise. Therefore, this paper presents the first knowledge-based layout synthesis methodology to generate new layouts by integrating existent design expertise contained in the quality-approved legacy layouts as much as possible. Experimental results show that the proposed methodology with knowledge mining can achieve high layout reusage rate and hence the designers\' layout preference can be successfully reserved.
Built-In Self-Test for Micro-Electrode-Dot-Array Digital Microfluidic Biochips
(2016)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Yu, Po-Hsien
;
Chakrabarty, Krishnendu
;
Ho, Tsung-Yi
A digital microfluidic biochip (DMFB) is an attractive platform for immunoassays, point-of-care clinical diagnostics, DNA sequencing, and other laboratory procedures in biochemistry. However, today\'s DMFBs suffer from several limitations, including (i) the lack of integrated sensors for real-time detection, (ii) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner, and (iii) the need for special fabrication processes and the associated reliability/yield concerns. To overcome the above limitations, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have been proposed recently. Droplet manipulation on MEDA biochips has also been experimentally demonstrated. In order to ensure robust fluidic operations and high confidence in the outcome of biochemical experiments, MEDA biochips must be adequately tested before they can be used for bioassay execution. We present an efficient built-in self-test (BIST) architecture for MEDA biochips. The proposed BIST architecture can effectively detect defects in a MEDA biochip, and faulty microcells can be identified. Simulation results based on HSPICE and experiments using fabricated MEDA biochips highlight the effectiveness of the proposed BIST architecture.
Co-placement optimization in sensor-reusable cyber-physical digital microfluidic biochips
(2019-01-01)
Li, Jian-De
;
Kuo, Chun-Hao
;
Lu, Guan-Ruei
;
Wang, Sying-Jyan
;
Li, Katherine Shu-Min
Digital microfluidic biochips (DMFBs) facilitate modern healthcare applications. One of the most important applications is point-of-care (POC) clinical diagnosis which is directly related to human health. However, biochemical experiments are usually error-prone, which makes monitoring intermediate results during bioassay execution be required to ensure the correctness of POC clinical diagnosis. To tackle this problem, cyber-physical digital microfluidic biochips with integrated sensors have been proposed and have attracted attention recently. In order to fully utilize the sensors for detection, the reusability of sensors should be taken into consideration during the module placement stage of cyber-physical DMFBs synthesis flow. Moreover, excessive actuation of electrodes may cause reliability degradation and this issuse should also be taken care of during module placement stage. In order to deal with the aforementioned problems, this paper presents the first co-optimization method for both module and sensor placement. Experimental results show that the proposed method can effectively minimize bioassay completion time while meeting all constraints from sensors and electrodes.
Continuous-Flow Biochips: Current Platforms and Emerging Research Challenges
(2015)
Pop, Paul
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
;
Grover, William H.
;
資訊工程學系
Control-Layer Optimization for Flow-Based mVLSI Microfluidic Biochips
(2014-01-01)
Hu, Kai
;
Dinh, Trung Anh
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
;
交大名義發表
Recent advantages in flow-based microfluidic biochips have enabled the emergence of lab-on-a-chip devices for bimolecular recognition and point-of-care disease diagnostics. However, the adoption of flow-based biochips is hampered today by the lack of computer-aided design tools. Manual design procedures not only delay product development but they also inhibit the exploitation of the design complexity that is possible with current fabrication techniques. In this paper, we present the first practical problem formulation for automated control-layer design in flow-based microfluidic VLSI (mVLSI) biochips and propose a systematic approach for solving this problem. Our goal is to find an efficient routing solution for control-layer design with a minimum number of control pins. The pressure-propagation delay, an intrinsic physical phenomenon in mVLSI biochips, is minimized in order to reduce the response time for valves, decrease the pattern set-up time, and synchronize valve actuation. Two fabricated flow-based devices and five synthetic benchmarks are used to evaluate the proposed optimization method. Compared with manual control-layer design and a baseline approach, the proposed approach leads to fewer control pins, better timing behavior, and shorter channel length in the control layer.
Design and Optimization of 3D Digital Microfluidic Biochips for the Polymerase Chain Reaction
(2015)
Li, Zipeng
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
;
資訊工程學系
;
Department of Computer Science
A digital microfluidic biochip (DMFB) is an attractive technology platform for revolutionizing immunoassays, clinical diagnostics, drug discovery, DNA sequencing, and other laboratory procedures in biochemistry. In most of these applications, real-time polymerase chain reaction (PCR) is an indispensable step for amplifying specific DNA segments. In recent years, three-dimensional (3D) DMFBs that integrate photodetectors (i.e., cyberphysical DMFBs) have been developed. They offer the benefits of smaller size, higher sensitivity and quicker time-to-results. However, current DMFB design methods target optimization in only two dimensions, hence they ignore the 3D two-layer structure of a DMFB. Moreover, these techniques ignore practical constraints related to the interference between on-chip device pairs, the performance-critical PCR thermal loop, and the physical size of devices. In this paper, we describe an optimization solution for a 3D DMFB, and present a three-stage algorithm to realize a compact 3D PCR chip layout, which includes: (i) PCR thermal-loop optimization; (ii) 3D global placement based on Strong-Push-Weak-Pull (SPWP) model; (iii) constraint-aware legalization. Simulation results for four laboratory protocols demonstrate that the proposed approach is effective for the design and optimization of a 3D chip for real-time PCR.
Design and Optimization of a Cyberphysical Digital-Microfluidic Biochip for the Polymerase Chain Reaction
(2015-01-01)
Luo, Yan
;
Bhattacharya, Bhargab B.
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
;
資訊工程學系
The amount of DNA strands available in a biological sample is a major limitation for many genomic bioanalyses. To amplify the traces of DNA strands, polymerase chain reaction (PCR) is widely used for conducting subsequent experiments. Compared to conventional instruments and analyzers, the execution of PCR on a digital microfluidic biochip (DMFB) can achieve short time-to-results, low reagent consumption, rapid heating/cooling rates, and high integration of multiple processing modules. However, the PCR biochip design methods in the literature are oblivious to the inherent randomness and complexity of bioanalyses, and they do not consider the interference among the neighboring devices and the cost of droplet transportation. We present an integrated design solution to optimize the complete PCR procedure, including: 1) DNA amplification and termination control; 2) resource placement that satisfies proximity constraints; and 3) droplet transportation. Based on the sensor feedback data, a statistical model is developed to optimize and control the DNA amplification sequence in real-time on a cyberphysical biochip. Next, we present a geometric algorithm for avoiding device interference and for reducing droplet routing cost. A novel optical sensing system is deployed based on the physical visibility of droplets. Simulation results for three laboratory protocols demonstrate that the proposed design method results in a compact layout and produces an execution sequence for efficient control of PCR operations on a cyberphysical DMFB.
Droplet Size-Aware and Error-Correcting Sample Preparation Using Micro-Electrode-Dot-Array Digital Microfluidic Biochips
(2017-12-01)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Chakrabarty, Krishnendu
;
Ho, Tsung-Yi
;
Lee, Chen-Yi
Sample preparation in digital microfluidics refers to the generation of droplets with target concentrations for on-chip biochemical applications. In recent years, digital microfluidic biochips (DMFBs) have been adopted as a platform for sample preparation. However, there remain two major problems associated with sample preparation on a conventional DMFB. First, only a (1: 1) mixing/splitting model can be used, leading to an increase in the number of fluidic operations required for sample preparation. Second, only a limited number of sensors can be integrated on a conventional DMFB; as a result, the latency for error detection during sample preparation is significant. To overcome these drawbacks, we adopt a next generation DMFB platform, referred to as micro-electrode-dot-array (MEDA), for sample preparation. We propose the first sample-preparation method that exploits the MEDA-specific advantages of fine-grained control of droplet sizes and real-time droplet sensing. Experimental demonstration using a fabricated MEDA biochip and simulation results highlight the effectiveness of the proposed sample-preparation method.
Droplet Size-Aware High-Level Synthesis for Micro-Electrode-Dot-Array Digital Microfluidic Biochips
(2017-06-01)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Yu, Po-Hsien
;
Chakrabarty, Krishnendu
;
Ho, Tsung-Yi
A digital microfluidic biochip (DMFB) is an attractive technology platform for automating laboratory procedures in biochemistry. In recent years, DMFBs based on a microelectrodedot- array (MEDA) architecture have been demonstrated. However, due to the inherent differences between today's DMFBs and MEDA, existing synthesis solutions for biochemistry mapping cannot be utilized for MEDA biochips. We present the first synthesis approach that can be used for MEDA biochips. We first present a general analytical model for droplet velocity and validate it experimentally using a fabricated MEDA biochip. We then present the proposed synthesis method targeting reservoir placement, operation scheduling, module placement, routing of droplets of various sizes, and diagonal movement of droplets in a two-dimensional array. Simulation results using benchmarks and experimental results using a fabricated MEDA biochip demonstrate the effectiveness of the proposed synthesis technique.
Efficient and Adaptive Error Recovery in a Micro-Electrode-Dot-Array Digital Microfluidic Biochip
(2018-03-01)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
McCrone, John
;
Yu, Po-Hsien
;
Chakrabarty, Krishnendu
A digital microfluidic biochip (DMFB) is an attractive technology platform for automating laboratory procedures in biochemistry. In recent years, DMFBs based on a microelectrode- dot-array (MEDA) architecture have been proposed. MEDA biochips can provide advantages of better capability of droplet manipulation and real-time sensing ability. However, errors are likely to occur due to defects, chip degradation, and the lack of precision inherent in biochemical experiments. Therefore, an efficient error-recovery strategy is essential to ensure the correctness of assays executed on MEDA biochips. By exploiting MEDA-specific advances in droplet sensing, we present a novel error-recovery technique to dynamically reconfigure the biochip using real-time data provided by on-chip sensors. Local recovery strategies based on probabilistic-timed-automata are presented for various types of errors. An online synthesis technique and a control flow are also proposed to connect local-recovery procedures with global error recovery for the complete bioassay. Moreover, an integer linear programming-based method is also proposed to select the optimal local-recovery time for each operation. Laboratory experiments using a fabricated MEDA chip are used to characterize the outcomes of key droplet operations. The PRISM model checker and three benchmarks are used for an extensive set of simulations. Our results highlight the effectiveness of the proposed error-recovery strategy.
Error Recovery in a Micro-Electrode-Dot-Array Digital Microfluidic Biochip
(2016)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Yu, Po-Hsien
;
Chakrabarty, Krishnendu
;
Pajic, Miroslav
A digital microfluidic biochip (DMFB) is an attractive technology platform for automating laboratory procedures in biochemistry. However, today\'s DMFBs suffer from several limitations: (i) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner; (ii) the lack of integrated sensors for real-time detection; (iii) the need for special fabrication processes and the associated reliability/yield concerns. To overcome the above problems, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have been proposed recently, and droplet manipulation on these devices has been experimentally demonstrated. Errors are likely to occur due to defects, chip degradation, and the lack of precision inherent in biochemical experiments. Therefore, an efficient error-recovery strategy is essential to ensure the correctness of assays executed on MEDA biochips. By exploiting MEDA-specific advances in droplet sensing, we present a novel error-recovery technique to dynamically reconfigure the biochip using real-time data provided by on-chip sensors. Local recovery strategies based on probabilistic-timed-automata are presented for various types of errors. A control flow is also proposed to connect local recovery procedures with global error recovery for the complete bioassay. Laboratory experiments using a fabricated MEDA chip are used to characterize the outcomes of key droplet operations. The PRISM model checker and three analytical chemistry benchmarks are used for an extensive set of simulations. Our results highlight the effectiveness of the proposed error-recovery strategy.
Flexible Droplet Routing in Active Matrix-Based Digital Microfluidic Biochips
(2018-04-01)
Lu, Guan-Ruei
;
Kuo, Chun-Hao
;
Chiang, Kuen-Cheng
;
Banerjee, Ansuman
;
Bhattacharya, Bhargab B.
The active matrix (AM)-based architecture offers many advantages over conventional digital electrowetting-on-dielectric (EWOD) microfluidic biochips, such as the capability of handling variable-size droplets, more flexible droplet movement, and precise control over droplet navigation. However, a major challenge in choosing the routing paths is to decide when the droplets are to be reshaped depending on the congestion of the intended path, or split- and route sub droplets,and merging them at their respective destinations. As the number of microelectrodes in AM-EWOD chips is large, the path selection problem becomes further complicated. In this article, we propose a negotiation-guided flow based on routing of subdroplets that obviates the explicit need for deciding when the droplets are to be manipulated, yet fully utilizing the power of droplet reshaping, splitting, and merging them to facilitate their journey. The proposed algorithm reduces routing cost and provides more freedom in deadlock avoidance in the presence of multiple routing tasks by assigning certain congestion penalty for sibling subdroplets and fluidic penalty for heterogeneous droplets. Compared to existing techniques, it reduces latest arrival time by an average of 29% for several benchmark and random test suites. Furthermore, our method is observed to provide 100% routability of nets for all test cases, whereas existing and baseline routers fail to produce feasible solutions in many instances. We also propose a reliable mode droplet routing strategy where the number of unreliable splitting operations can be reduced by paying a small penalty on latest arrival time.
High-Level Synthesis for Micro-Electrode-Dot-Array Digital Microfluidic Biochips
(2016)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Yu, Po-Hsien
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
A digital microlluidic biochip (DMFB) is an attractive technology platform for automating laboratory procedures in biochemistry. However, today\'s DMFBs suffer from several limitations: (i) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner; (ii) the lack of integrated sensors for real-time detection; (iii) the need for special fabrication processes and reliability/yield concerns. To overcome the above problems, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have recently been demonstrated. However, due to the inherent differences between today\'s DMFBs and MEDA, existing synthesis solutions cannot he utilized for MEDA-based biochips. We present the first biochip synthesis approach that can be used for MEDA. The proposed synthesis method targets operation scheduling, module placement, routing of droplets of various sizes, and diagonal movement of droplets in a two-dimensional array. Simulation results using benchmarks and experimental results using a fabricated MEDA biochip demonstrate the effectiveness of the proposed co-optimization technique.
High-Level Synthesis for Micro-Electrode-Dot-Array Digital Microfluidic Biochips
(2016)
Li, Zipeng
;
Lai, Kelvin Yi-Tse
;
Yu, Po-Hsien
;
Ho, Tsung-Yi
;
Chakrabarty, Krishnendu
digital microfluidic biochip (DMFB) is an attractive technology platform for automating laboratory procedures in biochemistry. However, today\'s DMFBs suffer from several limitations: (i) constraints on droplet size and the inability to vary droplet volume in a fine-grained manner; (ii) the lack of integrated sensors for real-time detection; (iii) the need for special fabrication processes and reliability/yield concerns. To overcome the above problems, DMFBs based on a micro-electrode-dot-array (MEDA) architecture have recently been demonstrated. However, due to the inherent differences between today\'s DMFBs and MEDA, existing synthesis solutions cannot be utilized for MEDA-based biochips. We present the first biochip synthesis approach that can be used for MEDA. The proposed synthesis method targets operation scheduling, module placement, routing of droplets of various sizes, and diagonal movement of droplets in a two-dimensional array. Simulation results using benchmarks and experimental results using a fabricated MEDA biochip demonstrate the effectiveness of the proposed co-optimization technique.
ILP-Based Alleviation of Dense Meander Segments With Prioritized Shifting and Progressive Fixing in PCB Routing
(2015-06-01)
Tseng, Tsun-Ming
;
Li, Bing
;
Ho, Tsung-Yi
;
Schlichtmann, Ulf
;
交大名義發表
Length-matching is an important technique to balance delays of bus signals in high-performance printed circuit board (PCB) routing. Existing routers, however, may generate very dense meander segments. Signals propagating along these meander segments exhibit a speedup effect due to crosstalk between the segments of the same wire, thus leading to mismatch of arrival times even under the same physical wire length. In this paper, we present a post-processing method to enlarge the width and the distance of meander segments and hence distribute them more evenly on the board so that crosstalk can be reduced. In the proposed framework, we model the sharing of available routing areas after removing dense meander segments from the initial routing, as well as the generation of relaxed meander segments and their groups for wire length compensation. This model is transformed into an ILP problem and solved for a balanced distribution of wire patterns. In addition, we adjust the locations of long wire segments according to wire priorities to swap free spaces toward critical wires that need much length compensation. To reduce the problem space of the ILP model, we also introduce a progressive fixing technique so that wire patterns are grown gradually from the edge of the routing toward the center area. Experimental results show that the proposed method can expand meander segments significantly even under very tight area constraints, so that the speedup effect can be alleviated effectively in high-performance PCB designs.
Intra-Vehicle Network Routing Algorithm for Wiring Weight and Wireless Transmit Power Minimization
(2015)
Huang, Ta-Yang
;
Chang, Chia-Jui
;
Lin, Chung-Wei
;
Roy, Sudip
;
Ho, Tsung-Yi
As the complexity of vehicular distributed systems increases rapidly, several hundreds of devices (sensors, actuators, etc.) are being placed in a modern automotive system. With the increase in wiring cables connecting these devices, the weight of a car increases significantly, which degrades the fuel efficiency in driving. In order to reduce the weight of a car, wireless communication has been introduced to replace wiring cables between some devices. However, the extra energy consumption for packet transmissions by wireless devices requires frequent maintenance, e.g., recharging of batteries. In this paper, we propose an intra-vehicle network routing algorithm to simultaneously minimize the wiring weight and the transmit power for wireless communication. Experimental results show that the proposed method can effectively minimize the wiring weight and the transmit power for wireless communication.