Search

Although 3-D floorplanning has been studied widely, routability which is a very important issue in modern integrated circuit (IC) designs is rarely discussed. Floorplanning in 3-D ICs is much difficult than that in 2-D ICs because of large difference in sizes between modules and through silicon vias (TSVs), which are key components in 3-D ICs. And the locations of TSVs have great impact on wirelength and routability in resulting floorplans. Hence, this paper proposes a TSV-aware 3-D floorplanning methodology which can consider wirelength and routability at the same time under the fixed-outline constraint. Unlike most of previous works which completely apply the simulated annealing algorithm, our methodology mainly apply deterministic algorithms to resolve the problem. Thus, our approach is more efficient and flexible than previous works. Experimental results have demonstrated that the proposed methodology can significantly reduce routing congestion in 3-D ICs with a slight increase in wirelength.

As technology advances, power consumption becomes a big challenge in modern very large-scale integration designs. To resolve this problem, power-gated technology has been widely adopted in circuit designs. Since the turn-on sequence of power switches has a great impact on the rush current, wake-up, and sequence times of a power gating design, this paper proposes a methodology to construct a hybrid routing structure to connect power switches. Our hybrid routing structure can induce less rush current and satisfy timing constraints because a better daisy chain is constructed. To find members of the daisy chain, an integer linear programming algorithm is used to pick up suitable power switches. To determine suitable depth of a daisy chain, we propose a model for a power gating design and induct precise equations to estimate voltage and rush current equations according to the model. All of our experiments are based on industrial designs and measured by vendor tools. The experimental results demonstrate the efficiency and effectiveness of our design methodology.

As advances in manufacture technology, leakage current increases dramatically in modern ICs. By turning off supply voltage in a low-power domain with power switches, power gating becomes a useful technique in resolving this problem. Since number and locations of power switches have great impact on chip area and IR-drop, an efficient and effective approach to insert power switches is required for the power gating designs. Unlike previous works using the greedy algorithm to handle this problem, this paper uses a simplified model to approximate required equivalent resistance of power switches in a low-power domain, and then determines number and types of power switches based on the value. In order to reduce impact on preplaced standard cells, we also propose a mathematical approach to find locations with less placement density to place power switches. The proposed methodology was integrated into a real-design flow. Experimental results demonstrate that our approach can insert less number of power switches and still satisfy the IR-drop constraint than other approaches.

This paper presents a two-stage approach to handle fixed-outline floorplanning for mixed size modules, named F-FM. F-FM combines the advantages of the analytical approach and the slicing tree representation. Thus, it is not only suitable for handling fixed-outline floorplanning but also can be extended to handle other important issues in floorplanning such as routability or thermal effect in addition to wirelength. Recently, low power has become big challenges in very large-scale integration designs, which makes voltage-island driven floorplanning more important than ever. Although the problem has been discussed by previous works, no paper considers signal wirelength, powerplanning, and voltage drop at the same time under the fixed-outline constraint. Thus, this paper extends F-FM to handle this problem and consider these issues by properly dividing modules in a voltage domain into several islands. The experimental results show our approach obtains the best results in these problems.

Power has become a burning issue in modern VLSI design. In modern integrated circuits, the power consumed by clocking gradually takes a dominant part. Given a design, we can reduce its power consumption by replacing some flip-flops with fewer multi-bit flip-flops. However, this procedure may affect the performance of the original circuit. Hence, the flip-flop replacement without timing and placement capacity constraints violation becomes a quite complex problem. To deal with the difficulty efficiently, we have proposed several techniques. First, we perform a co-ordinate transformation to identify those flip-flops that can be merged and their legal regions. Besides, we show how to build a combination table to enumerate possible combinations of flip-flops provided by a library. Finally, we use a hierarchical way to merge flip-flops. Besides power reduction, the objective of minimizing the total wirelength is also considered. The time complexity of our algorithm is Θ(n1.12) less than the empirical complexity of Θ(n2). According to the experimental results, our algorithm significantly reduces clock power by 20-30% and the running time is very short. In the largest test case, which contains 1 700 000 flip-flops, our algorithm only takes about 5 min to replace flip-flops and the power reduction can achieve 21%.

Switched capacitors are commonly used in analog circuits to increase the accuracy of analog signal processing and lower power consumption. To take full advantage of switched capacitors, it is very important to achieve accurate capacitance ratios in the layout of the capacitor arrays, which are affected by systematic and random mismatches. A good capacitor placement should have a common-centroid structure with the highest possible degree of dispersion to mitigate mismatches. Several dummy units should be inserted to make the placement shape more square and compact. This paper proposes a simulated-annealing-based approach for mismatch-aware common-centroid placement under the above constraints. A pair-sequence representation is used to record a placement, and a couple of associated operations are developed to find better solutions. The experimental results show that the proposed placements achieve smaller oxide-gradient-induced mismatch and larger overall correlation coefficients (i.e., higher degree of dispersion) than those of previous works.

Fixed outline floorplanning has recently attracted more attention due to its usefulness in solving real problems in industry. This paper applies two convex optimization methods, named UFO, to solve this problem, which consists of a global distribution stage followed by a local legalization phase. In the first stage, modules are transformed into circles, and a push-pull (PP) model is proposed to uniformly distribute modules over the fixed outline with consideration of their wirelength. Due to the quality of the PP model, we obtain good results after the first stage. Therefore, it is not necessary to consider wirelength in the legalization phase. In order to maintain good results of the first stage, we propose a procedure to extract the geometric relations of the modules from the results of the first stage and store it in constraint graphs. Then, the locations and shapes of the modules are determined by second-order cone programming, which penalizes overlap and obeys the boundary constraints. Finally, we extend the UFO methodology to consider pre-placed modules in a fixed outline. We have implemented two convex functions on MATLAB, and experimental results have demonstrated that UFO clearly outperforms the results reported in the literature on the GSRC and MCNC benchmarks.

Chao S-C, Chen J-S, Tsai C-H, Lin JY-M, Lin Y-J, Sun HS. Novel exon nucleotide substitution at the splice junction causes a neonatal Marfan syndrome. The fibrillin-1 gene (FBN1) mutations are associated with a broad spectrum of disorders including Marfan syndrome (MFS) and show great clinical heterogeneity. An underrepresentation for mutations leading to premature termination codon (PTC) in FBN1 exons 24–32 was found in neonatal or severe MFS but the underlying cause was unclear. This study thoroughly examined two FBN1 mutations on exons 24–32 region to illustrate the molecular mechanisms underlying these FBN1 mutations on MFS etiology. Two nucleotide substitutions, c.3208G> C, the last nucleotide of exon 26, and c.3209A>G, the first nucleotide of exon 27, affecting the same amino acid, p.D1070H and p.D1070G, respectively, gave very different phenotypes. We demonstrate that c.3208G>C generates two alternatively spliced transcripts, while c.3209A>G does not affect the splicing. We further demonstrate that the aberrantly spliced transcripts do not go through nonsense-mediated decay, but rather produce unstable, premature protein peptides that are degraded by endoplasmic reticulum associated degradation. The molecular mechanism outlined here defines a model for the pathogenesis of PTC-containing mutation within the exons 24–32 of FBN1 in MFS. Furthermore, our data suggest that PTC mutation within this region may lead to early lethality in neonatal MFS.

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 nonslicing 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.

In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/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 to perform 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 for the postprocessing 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.

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 multi-level 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.

Prevalence of liver injury associated with dimethylformamide (DMF) exposure was determined. Medical examinations, liver function tests, and creatine phosphokinase (CPK) determinations were performed on 183 of 204 (76%) employees of a synthetic leather factory. Air concentrations of solvents were measured with personal samplers and gas chromatography. The concentration of DMF in air to which each worker was exposed was categorized. High exposure concentrations of DMF (i.e., 25-60 ppm) were significantly associated with elevated alanine aminotransferase (ALT) levels (ALT greater than or equal to 35 IU/l), a result that did not change even after stratification by hepatitis B carrier status. Modeling by logistic regression demonstrated that exposure to high concentrations of DMF was associated with an elevated ALT (p = .01), whereas hepatitis B surface antigen (HBsAg) was slightly but independently associated with an elevated ALT (p = .07). In those workers who had normal ALT values, there occurred still significantly higher mean ALT and aspartate aminotransferase (AST) activities, especially among those who were not HBsAg carriers. A significant association existed between elevated CPK levels and exposure to DMF. However, an analysis of the CPK isoenzyme among 143 workers did not reveal any specific damage to muscles. This outbreak of liver injury among synthetic leather workers is ascribed to DMF. It is recommended that the occupational standard for DMF and its toxicity among HBsAg carriers be evaluated further.

In order to handle device matching for analog circuits, some pairs of modules need to be placed symmetrically with respect to a common axis. In this paper, we deal with the module placement with symmetry constraints for analog design using the transitive closure graph-sequence (TCG-S) representation. Since the geometric relationships of modules are transparent to TCG-S and its induced operations, TCG-S has better flexibility than previous works in dealing with symmetry constraints. We first propose the necessary and sufficient conditions of TCG-S for symmetry modules. Then, we propose a polynomial-time packing algorithm for a TCG-S with symmetry constraints. Experimental results show that the TCG-S based algorithm results in the best area utilization.

Architecture and CAD are closely related issues in FPGA design. Routing architecture design shall optimize routability and facilitate router development; on the other hand, router design shall consider the specific properties of routing architectures to optimize the performance of the router. In this paper, we propose effective and efficient unified matching-based algorithms for array-based FPGA routing and segmentation design. For the segmentation design, we consider the similarity of input routing instances and formulate a net-matching problem to construct the optimal segmentation architecture. For the router design, we present a matching-based timing-driven routing algorithm which can consider a versatile set of routing segments. Experimental results show that our designed segmentations significantly outperform those used in commercially available FPGAs. For example, our designed segmentations achieve, on average, 14.6% and 19.7% improvements in routability, compared with those used in the Lucent Technologies ORCA 2C-series and the Xilinx XC4000E-series FPGAs, respectively.

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.