Browsing by Author "Chang, YW"

Now showing 1 - 20 of 36

4.9-GHz low-phase-noise transformer-based superharmonic-coupled GaInP/GaAs HBT QVCO
(2006-06-01)
Meng, CC
;
Chang, YW
;
Tseng, SC
;
資訊工程學系
;
Department of Computer Science
The low-phase-noise GaInP/GaAs heterojunction bipolar transistor (HBT) quadrature voltage controlled-oscillator (QVCO) using transformer-based superharmonic coupling topology is demonstrated for the first time. The fully integrated QVCO at 4.87 GHz has phase noise of -131 dBc/Hz at 1-MHz offset frequency, output power of -4 dBm and the figure of merit (FOM) -198 dBc/Hz. The state-of-the-art phase noise FOM is attributed to the superior GaInP/GaAs HBT low-frequency device noise and the high quality transformer formed on the GaAs semi-insulating substrate.
5.4GHz-127 dBc/Hz at 1MHz GaInP/GaAs HBT quadrature VCO using stacked transformers
(2005-08-04)
Meng, CC
;
Chen, CH
;
Chang, YW
;
Huang, GW
;
電信工程研究所
The first fully integrated GaInP/GaAs heterojunction bipolar transistor (HBT) quadrature voltage controlled oscillator (VCO) using the stacked-transformer LC tank is demonstrated at 5.43-5.31 GHz with low-phase-noise performance. The stacked-transformers are formed by two interconnect metal layers and possess good electrical properties at high frequencies because of the semi-insulating GaAs substrate. The quadrature VCO at 5.38 GHz has phase noise of -127.4 dBc/Hz at 1 MHz offset frequency, output power of -4 dBm and a figure of merit (FOM) -191 dBc/Hz.
A clustering- and probability-based approach for time-multiplexed FPGA partitioning
(2004-12-01)
Wu, GM
;
Chao, MCT
;
Chang, YW
;
交大名義發表
;
National Chiao Tung University
Improving logic density by time-sharing, time-multiplexed FPGAs (TMFPGAs) have become an important research topic for reconfigurable computing. Due to the precedence and capacity constraints in TMFPGAs, the clustering and partitioning problems for TMFPGAs are different from the traditional ones. In this paper, we propose a two-phase hierarchical approach to solve the partitioning problem for TMFPGAs. With the precedence and capacity considerations for both phases, the first phase clusters nodes to reduce the problem size, and the second phase applies a probability-based iterative-improvement approach to minimize cut cost. Experimental results based on the Xilinx TMFPGA architecture show that our algorithm significantly outperforms previous works. (C) 2004 Elsevier B.V. All rights reserved.
A graph-theoretic sufficient condition for FPGA/FPIC switch-module routability
(1997)
Chang, YW
;
Wong, DF
;
Wong, CK
;
交大名義發表
;
資訊工程學系
Switch modules are the most important component of the routing resources in FPGA's/FPIC's. We consider in this paper an FPGA/FPIC switch-module analysis problem: The in puts consist of a switch-module description and the number of nets required to be routed through the switch module; the question is to determine if there exists a feasible routing for the routing requirements on the switch module. This problem is applicable to the routability evaluation of FPGA/FPIC switch modules, the switch-module design for FPGA's/FPIC's, and FPGA/FPIC routing. We present a graph-theoretic sufficient condition for the analysis problem. The implications of the condition are: (1) there exist several classes of efficient approximation algorithms for the analysis problem; (2) there exist several classes of switch-module architectures on which the analysis problem can be solved efficiently.
A novel framework for multilevel routing considering routability and performance
(2002)
Lin, SP
;
Chang, YW
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
We propose in this paper a novel framework for multilevel routing considering both routability and performance. The two-stage multilevel framework consists of coarsening followed by uncoarsening. Unlike the previous multilevel routing, we integrate global routing, detailed routing, and resource estimation together at each level of the framework, leading to more accurate routing resource estimation during coarsening and thus facilitating the solution refinement during uncoarsening. Further, the exact routing information obtained at each level makes our framework more flexible in dealing with various routing objectives (such as crosstalk, power, etc). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the previous multilevel routing, the three-level routing, and the hierarchical routing can complete routing for only 3, 0, 3 circuits, respectively. In particular, the number of routing layers used by our router is even smaller. We also have performed experiments on timing-driven routing. The results are also very promising.
A study on Chinese carbon-signature recognition
(2002-03-01)
Lin, SF
;
Chang, YW
;
Su, CK
;
電控工程研究所
;
Institute of Electrical and Control Engineering
A novel off-line algorithm and a modified chain code for recognizing signatures are proposed in the present study. Carbon paper is used to detect force distributions when people write their signatures. First of all, the signature contours are located and the upper and lower profiles are generated then, these are used to classify the given si.-nature. Both the gray-scale and the chain code characteristics of a signature are used to extract structure and force distribution features, which are then transformed into a normalized vector. Finally, a Supervised Fuzzy Adaptive Hamming Network (SFAHN) is employed to interpret the feature vector in order to determine whether the signature is genuine or not. Simulation results show that the proposed algorithm has a good recognition rate.
Algorithms for an FPGA switch module routing problem with application to global routing
(1997-01-01)
Thakur, S
;
Chang, YW
;
Wong, DF
;
Muthukrishnan, S
;
資訊工程學系
We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA's). This problem was first introduced in [21], They used it to evaluate the routability properties of switch modules which they proposed, Only an approximation algorithm for the problem was proposed by them, We give an optimal algorithm for the problem based on integer linear programming (ILP), Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems, We then propose a precomputation that eliminates the need to use ILP era-line, We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known, Thus, the switch module routing problem can be solved in polynomial time for these special cases, Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router, A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions.
An architecture-driven metric for simultaneous placement and global routing for FPGAs
(2000)
Chang, YW
;
Chang, YT
;
資訊工程學系
;
Department of Computer Science
FPGA routing resources typically consist of segments of various lengths. Due to the segmented routing architectures, the traditional measure of wiring cost (wirelength, delay, congestion, etc) based on geometric distance and/or channel density is no longer accurate for FPGAs. Researchers have shown that the number of segments, instead of geometric (Manhattan) distance, traveled by a net is the most crucial factor in controlling the routing delay and cost in an FPGA. Further, the congestion information of a routing channel shall be measured by the available segments of specific lengths, instead of the density in a channel alone. In this paper, we propose an architecture-driven metric for simultaneous FPGA placement and global routing. The new metric considers the available segments and their lengths to optimize the wiring cost for placement and global routing. Experiments by employing a cluster growth placement and maze routing to demonstrate the new metric show respective average reductions of 8%, 20%, and 19% in the number of tracks used (area), maximum net delay, and average net delay based on the Lucent Technologies ORCA2C-like and the Xilinx XC4000EX-like architectures, compared with the traditional metric of geometric distance and channel density.
Arbitrary convex and concave rectilinear module packing using TCG
(2002)
Lin, JM
;
Chen, HL
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
In this paper, we deal with arbitrary convex and concave rectilinear module packing using the Transitive Closure Graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need of the post processing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.
B*-trees: A new representation for non-slicing floorplans
(2000)
Chang, YC
;
Chang, YW
;
Wu, GM
;
Wu, SW
;
資訊工程學系
We present in this paper an efficient, flexible, and effective data structure, B*-trees, for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B*-trees and their corresponding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.
Comment on "Generic universal switch blocks"
(2002-01-01)
Fan, HB
;
Wu, YL
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
In the paper [5], the authors defined the well-structured symmetric switch block M-N,M-W and showed that M-N,M-W is universal for any pair of positive integers N and W, However, we find that this result is partially correct. Here, we show that, when N greater than or equal to 7, M-N,M-W is not universal for odd Ws (greater than or equal to 3) and it is universal for any even W.
Corner sequence - A P-admissible floorplan representation with a worst case linear-time packing scheme
(2003-08-01)
Lin, JM
;
Chang, YW
;
Lin, SP
;
資訊工程學系
;
電子工程學系及電子研究所
Floorplanning/placement allocates a set of modules into a chip so that no two modules overlap and some specified objective is optimized. To facilitate floorplanning/placement, we need to develop an efficient and effective representation to model the geometric relationship among modules. In this paper, we present a P-admissible representation, called corner sequence (CS), for non-slicing floorplans. CS consists of two tuples that denote the packing sequence of modules and the corners to which the modules are placed. CS is very effective and simple for implementation. Also, it supports incremental update during packing. In particular, it induces a generic worst case linear-time packing scheme that can also be applied to other representations. Experimental results show that CS achieves very promising results for a set of commonly used MCNC benchmark circuits.
Crosstalk-constrained performance optimization by using wire sizing and perturbation
(2000)
Pan, SR
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a unified wire sizing and perturbation algo rithm for crosstalk-constrained performance optimization that is applicable to general routing structures. Our algorithm is based on a two-stage iterative technique: we first perturb all wires to the positions with the minimum delay, then we adjust the wire sizes to further optimize delay under crosstalk constraints. The unified wire sizing and perturbation technique has the property of unimodality, implying that there is a unique position resulting in the optimal delay and crosstalk. Applying these properties can dramatically reduce the search space and thus lead to a very efficient method to determine the best wire position and the optimal wire size. Experimental results show that our algorithm can achieve average improvements of 44.5% and 40.2% in delay without sacrificing area and crosstalk for the 0.18 mum and 0.25 mum process technologies, respectively. Further, we develop an effective incremental update technique that can substantially speed up the runtime. Empirically, this technique can reduce runtime by 10 times.
Crosstalk-driven interconnect optimization by simultaneous gate and wire sizing
(2000-09-01)
Jiang, IHR
;
Chang, YW
;
Jou, JY
;
資訊工程學系
;
電子工程學系及電子研究所
Noise, as well as area, delay, and power, is one of the most important concerns in the design of deep submicrometer integrated circuits. Currently existing algorithms do not handle simultaneous switching conditions of signals for noise minimization. In this paper, we model not only physical coupling capacitance, but also simultaneous switching behavior for noise optimization. Based on Lagrangian relaxation, we present an algorithm which ran optimally solve the simultaneous noise, area, delay, and power optimization problem by sizing circuit components. Our algorithm, with linear memory requirement and linear runtime, is very effective and efficient. For example, for a circuit of 6144 wires and 3512 gates, our algorithm solves the simultaneous optimization problem using only 2.1-MB memory and 19.4-min runtime to achieve the precision of within 1% error on a SUN Spare Ultra-I workstation.
Effect of Al-trace dimension on Joule heating and current crowding in flip-chip solder joints under accelerated electromigration
(2006-04-24)
Liang, SW
;
Chang, YW
;
Chen, C
;
材料科學與工程學系
;
Department of Materials Science and Engineering
Three-dimensional thermoelectrical simulation was conducted to investigate the influence of Al-trace dimension on Joule heating and current crowding in flip-chip solder joints. It is found that the dimension of the Al-trace effects significantly on the Joule heating, and thus directly determines the mean time to failure (MTTF). Simulated at a stressing current of 0.6 A at 70 degrees C, we estimate that the MTTF of the joints with Al traces in 100 mu m width was 6.1 times longer than that of joints with Al traces in 34 mu m width. Lower current crowding effect and reduced hot-spot temperature are responsible for the improved MTTF. (c) 2006 American Institute of Physics.
Generic ILP-based approaches for time-multiplexed FPGA partitioning
(2001-10-01)
Wu, GM
;
Lin, JM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
Due to the precedence constraints among vertices, the partitioning problem for time-multiplexed field-programmable gate arrays (TMFPGAs) is different from the traditional one. In this paper, we first derive logic formulations for the precedence-constrained partitioning problems and then transform the formulations into integer linear programs (ILPs). The ILPs can handle the precedence constraints and minimize cut sizes simultaneously. To enhance performance, we also propose a clustering method to reduce the problem size. Experimental results based on the Xilinx TMFPGA architecture show that our approach outperforms the list-scheduling (List), the network-flow-based (FBB-m) (Liu and Wong, 1998), and the probability-based (PAT) (Chao, 1999) methods by respective average improvements of 46.6%, 32.3%, and 21.5% in cut sizes. Our approach is practical and scales well to larger problems; the empirical runtime grows close to linearly in the circuit size. More importantly, our approach is very flexible and can readily extend to the partitioning problems with various objectives and constraints, which makes the ILP formulations superior alternatives to the TMFPGA partitioning problems.
Graph matching-based algorithms for FPGA segmentation design
(1998)
Chang, YW
;
Lin, JM
;
Wong, DF
;
資訊工程學系
;
Department of Computer Science
Process technology advances will soon make the one-million gate FPGA a reality. A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures [10]. One-dimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a net matching problem and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient matching-based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms previous work. For example, our method achieves averages of 18.2% and 8.9% improvements in routability, compared with the work in [14] and the most recent work in [7] respectively. More importantly, our approaches are very flexible and can readily extend to higher-order segmentation designs (e.g., two- or three-dimensional segmentation design, etc), which are crucial to the design of large-scale FPGAs.
Inductance modeling for on-chip interconnects
(2002)
Tu, SW
;
Shen, WZ
;
Chang, YW
;
Chen, TC
;
電子工程學系及電子研究所
As the operation frequency reaches gigahertz in deep-submicron designs, the effects of inductance on noise and delay can no longer be neglected. Most of the previous works on inductance extraction are field-solvers, which are intrinsically more accurate but computationally expensive. Others focus on modeling the inductances of special routing topologies such as the bus structure. Therefore, it is not suitable. to incorporate them on-line into a layout (placement and routing) tool for inductance (delay and noise) optimization. In this paper, we consider the overlapping of unequal wire lengths and dimensions to efficiently extract the loop inductance from the coplanar interconnect structure. The difference between our simulation results and the estimation values obtained by FastHenry [11] is within 10% for practical cases.
Inductance modeling for on-chip interconnects
(2003-04-01)
Tu, SW
;
Shen, WZ
;
Chang, YW
;
Chen, TC
;
Jou, JY
As the operation frequency reaches gigahertz in deep-submicron designs, the effects of inductance on noise and delay can no longer be neglected. Most of the previous works on inductance extraction are field-solvers, which are intrinsically more accurate but computationally expensive. Others focus on modeling the inductances of special routing topologies such as the bus structure. Therefore, it is not suitable to incorporate them on-line into a layout ( placement and routing) tool for inductance ( delay and noise) optimization. In this paper, we consider the overlapping of unequal wire lengths and dimensions to efficiently extract the loop inductance from the coplanar interconnect structure. The difference between our simulation results and the estimation values obtained by FastHenry [12] is within 10% for practical cases. In particular, our modeling is extremely efficient, and thus can be incorporated into a layout tool for inductance optimization.
Layout techniques for on-chip interconnect inductance reduction
(2004)
Tu, SW
;
Jou, JY
;
Chang, YW
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
As the operation frequency reaches gigahertz in deep-submicron designs, the effects of inductance on noise and delay can no longer be neglected. Some of the previous techniques such as net ordering, shield insertion, twisted-bundle layout structure, and interdigitated techniques are either inefficient or incur too much area penalty. In this paper, we present two techniques ground-aware net routing and source pin positioning that can reduce inductance effectively without incurring area penalty. In order to prove the effectiveness of our techniques, we use the famous 3D field-solver FastHenry [7] to extract inductances and verify our results. All simulation results show that our proposed techniques can significantly reduce inductances without incurring area penalty.