Browsing by Author "Lin, JM"

Now showing 1 - 12 of 12

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.
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.
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.
Matching-based algorithm for FPGA channel segmentation design
(2001-06-01)
Chang, YW
;
Lin, JM
;
Wong, MDF
;
資訊工程學系
;
Department of Computer Science
Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the Literature; the previous methods are based on experimental studies, stochastic models, 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 problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multilevel matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.
Module placement with boundary constraints using B*-trees
(2002-08-01)
Lin, JM
;
Yi, KE
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
The module placement problem is to determine the co-ordinates of logic modules in a chip such that no two modules overlap and some cost (e.g. silicon area, interconnection length, etc.) is optimised. To shorten connections between inputs and outputs and/or make related modules adjacent, it is desired to place some modules along the specific boundaries of a chip. To deal with such boundary constraints, we explore the feasibility conditions of a B*-tree with boundary constraints and develop a simulated annealing-based algorithm using B*-trees. Unlike most previous work, the proposed algorithm guarantees a feasible B*-tree with boundary constraints for each perturbation. Experimental results show that the algorithm can obtain a smaller silicon area than the most recent work based on sequence pairs.
Short leaky-wave antennas of sum and difference patterns
(1996-07-04)
Lin, JM
;
Tzuang, CKC
;
Chou, GJ
;
Su, S
;
交大名義發表
A set of differential feed short (similar to 0.7 lambda(0)) leaky-wave antennas with sum (Sigma) and difference (Delta) patterns is presented. Rigorous field-theory analyses show that the radiation characteristics of these antennas agree well with the measurements. The performance of these antennas is well suited for direction finding applications.
Short leaky-wave antennas of sum and difference patterns
(1996-07-04)
Lin, JM
;
Tzuang, CKC
;
Chou, GJ
;
Su, S
;
電信工程研究所
A set of differential feed short (similar to 0.7 lambda(0)) leaky-wave antennas with sum (Sigma) and difference (Delta) patterns is presented. Rigorous field-theory analyses show that the radiation characteristics of these antennas agree well with the measurements. The performance of these antennas is well suited for direction finding applications.
Synthesis and characterization of light-emitting oligo(p-phenylene-vinylene)s and polymeric derivatives containing three- and five-conjugated phenylene rings
(2006-01-15)
Lin, HC
;
Tsai, CM
;
Huang, GH
;
Lin, JM
;
材料科學與工程學系
Several series of light-emitting oligo(p-phenylene-vinylene)s (BIII and BV series containing three- and five-conjugated phenylene rings) with various side groups and end groups attached to the cores were synthesized and characterized. The analogous PBV polymers, derived from the BV series, were also synthesized and investigated. Blue and greenish light emissions were observed in the photoluminescence (PL) and electroluminescence (EL) spectra of the blend and pure films with these pi-conjugated structures. In contrast to the three-conjugated ring oligomers, the five-conjugated ring derivatives (oligomers and polymers) had larger maximum emission wavelength values of PL and EL emissions. Mesomorphism was introduced into the BV series by the replacement of three-conjugated rings (BIII series) with five-conjugated phenyl cores (BV series). The liquid-crystalline properties of the BV series with end groups (on both end rings) were better than those of analogous BV-OC8 without end groups. Polarized PL emissions were obtained by the alignment of liquid-crystalline phase in rubbing cells. Upon heating, different PL emission wavelengths and intensities were observed in various phases. Not only the solubility and thermal properties but also the PL and EL properties could be effectively adjusted by the attachment of flexible alkoxy groups either on the central rings or on both end rings of the conjugated cores. (c) 2005 Wiley Periodicals, Inc.
TCG-S: Orthogonal coupling of P*-admissible representations for general floorplans
(2002)
Lin, JM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
We extend in this paper the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P-admissible representations, SP, BSG, and TCG, has its strengths as well as weaknesses. We show the equivalence of the two most promising P*-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a new representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, faster packing and perturbation schemes are possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits art elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.
TCG-S: Orthogonal coupling of P*-admissible representations for general floorplans
(2004-06-01)
Lin, JM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
In this paper, we extend the concept of the P-admissible floorplan representation to that of the P* -admissible one. A P* -admissible representation can model the most general floorplans. Each of the currently existing P* -admissible representations, sequence pair (SP), bounded-slicing grid, and transitive closure graph (TCG), has its strengths as well as weaknesses. We show the equivalence of the two most promising P* -admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, a fast packing scheme is possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.
TCG: A transitive closure graph-based representation for non-slicing floorplans
(2001)
Lin, JM
;
Chang, YW
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.