Directed test generation is an effective method to detect potential hardware Trojan (HT) in RTL. While the existing works are able to activate hard-to-cover Trojans by covering security targets, the effectiveness and efficiency of identifying the targets to cover are ignored. We propose a static probability analysis method for identifying the hard-to-active data channel targets and generating the corresponding assertions for the HT test generation. Our method could generate test vectors to trigger Trojans from Trusthub, DeTrust, and OpenCores in 1 minute and get 104.33X time improvement on average compared with the existing method.

Accurate and robust power models are highly demanded to explore better CPU designs. However, previous learning-based power models ignore the discrepancies in data distribution among different CPU designs, making it difficult to use data from the historical configuration to aid modeling for new target configuration. In this paper, we investigate the transferability of power models and propose a microarchitecture power modeling method based on transfer learning (TL). A novel TL method for artificial neural network (ANN)-based power models is proposed, where cross-domain mixup generates more auxiliary samples close to the target configuration to fill in the distribution discrepancy and domain-adversarial training extracts domain-invariant features to complete the target model construction. Experiments show that our method greatly improves the model transferability and can effectively utilize the knowledge of the existing CPU configuration to facilitate target power model construction.

Power efficiency has become a nonneglected issue of modern CPUs. Therefore, accurate and robust power models are highly demanded in academia and industry. However, it is hard for existing power models to balance modeling speed, generality, and accuracy well. This article introduces McPAT-Calib, a microarchitecture power modeling framework, which combines McPAT with machine learning (ML) calibration and active learning (AL) sampling. McPAT-Calib can quickly and accurately estimate the power of different benchmarks executed on different CPU configurations, and provide an effective evaluation tool for the early design stage. First, McPAT-7nm is introduced to support the preliminary analytical power modeling for the 7-nm technology node. Then, a wide range of modeling features are identified, and automatic feature selection and advanced nonlinear regression are used to calibrate the McPAT-7nm modeling results, greatly improving the accuracy. Moreover, a novel AL approach termed power greedy sampling (PowerGS) embedded with domain knowledge is leveraged to reduce the modeling cost effectively. We use up to 15 configurations of the RISC-V Berkeley out-of-order machine (BOOM) along with 80 benchmarks, targeting 7-nm technology, to extensively evaluate McPAT-Calib. Compared with state-of-the-art (SOTA) microarchitecture power models, McPAT-Calib can reduce the mean absolute percentage error (MAPE) under different cross-validation (CV) strategies by 3.64%–6.14% (absolute reduction). Meanwhile, PowerGS is superior to the existing AL approaches, which can significantly reduce the demand for labeled samples to speed up model construction. The effectiveness of the overall modeling and estimation flow with AL sampling has also been verified.

Microarchitecture design is a key stage of processor development involving various core design metrics, e.g., performance, power consumption, etc. However, due to the high complexity and huge design space of microarchitecture, it becomes challenging to get better designs quickly. In this article, we propose a microarchitecture design space exploration (DSE) approach via Pareto-driven active learning (AL). First, a more accurate dynamic tree ensemble model is used to guide the exploration and can give the importance of each design parameter. Then, a Pareto-driven AL approach is proposed that prioritizes the exploration of designs with larger hypervolume contributions in the predicted Pareto fronts and allows the acceptance of poor solutions to handle model inaccuracies. Finally, a parallel strategy is utilized to speed up the exploration. The experimental results on the 7-nm RISC-V Berkeley out-of-order machine (BOOM) show that our method can find diversified designs converging to real Pareto fronts more efficiently, achieving better exploration quality and efficiency than previous work.

Recent years, Convolution Neural Networks (CNNs) have achieved impressive results in facial landmark detection task. Especially, the u-shaped architecture, also known as U-net, has become the de-facto standard and achieved tremendous success. However, due to the locality property of convolution operation, it has a limitation in modeling global and long-range semantic information interaction, which is essential in localization tasks. In this work, we propose a Unet-like pure transformer method TransMarker, in which we give a new perspective to tackle facial landmark detection task in a sequence-to-sequence manner. We first split the input image into non-overlapping patches, which are seen as tokens in NLP tasks. Then, we feed the image patches into a symmetric u-shaped Encoder-Decoder architecture for local-global semantic feature learning. In addition, we introduce a Dense Skip-Connection schema to leverage the multi-level information within different resolutions. Note that, unlike conventional U-net architecture, we design the network with pure Transformer blocks, without any conventional operations. Extensive experiments demonstrate the state-of-the-art performance of our method on several standard datasets, i.e., WFLW, COFW and 300W, which remarkably outperform previous convolutional-based methods.

Recent video facial landmark detection methods heavily rely on the supervised learning with large amount of annotated data. Nevertheless, the annotation of data on the video is very labor-intensive and time-consuming. Also, the supervised learning with massive parameters is easy to make the network suffer from overfitting and generalization-losing. In this work, we propose the Separation-and-Recombination Learning (SRL) framework to tackle this problem, in which the crucial idea is to adequately mine the inherent information of the limited labeled data in a semi-supervised manner. Specifically, we split the SRL framework into two stages, a separation stage and a recombination stage. Firstly, in the separation stage, we propose to train an Auto-Encoder network, disentangling-net, taking multi-frame temporal cues as input and with reconstruction and KL-divergence loss as constraints. In this stage, we successfully disentangle the face into two weak-coupling latent spaces, i.e., structure and appearance space. Then, in the recombination stage, with the trained disentangling-net, the limited labeled data can be greatly expended as pseudo paired data, with the recombination of structure and appearance code. Finally, we train a replaceable landmark detection network, predicting-net, with the supervision of both labeled and pseudo-labeled data. In the experiment, we demonstrate state-of-the-art performance on several well-known benchmarks, i.e., 300VW [56], blurred-300VW [60] and RWMB [60] dataset. Most importantly, our method is able to maintain impressive accuracy on extremely small training sets down to as few as 50% samples.

Energy efficiency has become the core issue of modern CPUs, and it is difficult for existing power models to balance speed, generality, and accuracy. This paper introduces McPAT-Calib, a microarchitecture power modeling framework, which combines McPAT with machine learning (ML) calibration methods. McPAT-Calib can quickly and accurately estimate the power of different benchmarks running on different CPU configurations, and provide an effective evaluation tool for the design of modern CPUs. First, McPAT-7nm is introduced to support the analytical power modeling for the 7nm technology node. Then, a wide range of modeling features are identified, and automatic feature selection and advanced regression methods are used to calibrate the McPAT-7nm modeling results, which greatly improves the generality and accuracy. Moreover, a sampling algorithm based on active learning (AL) is leveraged to effectively reduce the labeling cost. We use up to 15 configurations of 7nm RISC-V Berkeley Out-of-Order Machine (BOOM) along with 80 benchmarks to extensively evaluate the proposed framework. Compared with state-of-the-art microarchitecture power models, McPAT-Calib can reduce the mean absolute percentage error (MAPE) of shuffle-split cross-validation by 5.95%. More importantly, the MAPE is reduced by 6.14% and 3.64% for the evaluations of unknown CPU configurations and benchmarks, respectively. The AL sampling algorithm can reduce the demand of labeled samples by 50 %, while the accuracy loss is only 0.44 %.

Predicting the design rule check (DRC) violation hotspots in an early stage plays an essential role in the efficiency of the physical design. Multiple factors that affect the performance of a DRC hotspot predictor, among them, the efficacy of the extracted features plays a substantial role. In this paper, we propose a connectivity-based DRC hotspot prediction method using a convolutional neural network. We show that the proposed method is efficient in both training and prediction. The relation between pin features and predictor performance is further investigated and two weighted connectivity-based route map features are introduced. Experimental results demonstrate that the proposed algorithm can predict on average 73% of the DRC hotspots with only 2.7% false alarms.

Electromigration (EM) has been considered to be a severe reliability issue in power grid networks of large integrated circuits (IC). The via array possesses special EM characteristics that have been observed to be distinct from a single via. In this study, a compact analytical model for the fast estimation of EM for via array was proposed by calculating the current distribution in the via arrays. The proposed model was then analyzed in a multi-layer power grid, which, for the first time, considered the impacts of the current propagation that exists in the vertical via array connected within the multi-level interconnection to improve the accuracy of the analytical model further. According to the model, a novel methodology for full- chip EM checking for multi-layered power grids was proposed. This method factored in the routing structure of the multi-layer power grid network, ensuring the EM assessment analysis's efficiency for large-scale power grid networks without sacrificing accuracy.

Paper-based digital microfluidic biochips (P-DMFBs) have recently emerged as a promising low-cost and fast-responsive platform for biochemical assays. In P-DMFBs, electrodes and control lines are printed on a piece of photograph paper using an inkjet printer and carbon nanotubes (CNTs) conductive ink. Compared with traditional digital microfluidic biochips (DMFBs), P-DMFBs enjoy significant advantages, such as faster in-place fabrication with printer and ink, lower costs, and better disposability. Since electrodes and CNT control lines are printed on the same side of this paper, a critical design challenge for P-DMFB is to prevent control interference between moving droplets and the voltages on CNT control lines. Control interference may result in unexpected droplet movements and thus incorrect assay outputs. To address this design challenge, a control-fluidic codesign methodology is proposed in this paper, along with two demonstrative design flows integrating both fluidic design and control design, i.e., the droplet-oriented codesign flow and the electrode-oriented codesign flow. The droplet-oriented flow is suitable for designing biochips with sparse electrodes and relatively larger number of droplets, whereas the electrode-oriented flow is suitable for biochips with dense electrodes and smaller number of droplets. The computational simulation results of real-life bioassays demonstrate the effectiveness of the proposed codesign flows.

Electromigration(EM) and power supply noise has been considered serious reliability issue in the power grid networks. Several performance goals in EM reliability optimization and power supply noise optimization are typically conflict with each other. In this paper, we propose a composite optimization method trading off EM and power noise optimization process. In the method, we expand a temperature-aware EM model, which takes EM transient effect into account. Experimental results show that composite reliability optimization method can lengthen the lifetime of an entire circuit by approximately 10% compared with previous respective optimization strategy and no power noise violations exists after the composite optimization.

In this paper, we note that the hardware Trojans that leak information through the unspecified output pins are difficult to detect by functional testing or side-channel signal analysis. Especially, the Trojans that leak the information through the side channel has proven stealthy to be detected. To solve this problem, we propose a feature matching method based on information flow tracking at high abstraction level. In this paper, the Trojans features are summarized with the format of high-level information flow tracking, which can be used to detect the Trojans. Experimental results show that our method can successfully identify the above-mentioned Trojans from Trust-hub, DeTrust, and OpenCores in less than 20 ms, showing significantly lower time complexity compared with the existing works.

Since the first circuit obfuscation technique was proposed to thwart reverse engineering (RE) attacks to integrated circuits (ICs), there have been active research in de-obfuscation attacks and new obfuscation countermeasures. Although it is crucial for an obfuscation method to be secure against known de-obfuscation attacks, it is equally important to keep the cost of circuit obfuscation low. Most importantly, obfuscation methods need to be formally analyzed for their effectiveness and efficiency. In this paper, we propose a set of quantitatively evaluable metrics for this purpose, particularly facilitated by a recently proposed circuit partition attack (CPA) and the powerful SAT-based attack (SATA). Moreover, we find that CPA can be applied prior to any de-obfuscation attacks to reduce RE efforts exponentially. We then propose a new equivalent class guided obfuscation scheme (ECG-Obfus) to defeat CPA which leverages specially designed camouflaged cells to replace judiciously selected logic gates. Specifically, we select candidate gates for obfuscation from one certain equivalent class, in which the underlying equivalent relation is defined based on IC topological structure information. We evaluate ECG-Obfus using the proposed metrics and conduct experiments on ISCAS 85/89 standard benchmark suites and OpenSparc T1 microprocessor. The results show that ECG-Obfus gains good resilience against known de-obfuscation attacks (including CPA and SATA), with low design complexity and performance overhead.

In this paper, we note that the hardware Trojans that leak information through the unspecified output pins are difficult to detect by functional testing or side-channel signal analysis. To solve this problem, we propose a feature matching method based on information flow tracking at high abstraction level. Experimental results show that our method can successfully identify the above-mentioned Trojans from Trust-hub, DeTrust, and OpenCores in less than 20 ms, showing significantly lower time complexity compared with the existing works.

Hardware Trojans (HT) has been one of the major concerns of IC designers, and formal methods have been applied to the HT detection. In general, the assertions for detecting HT are manually defined, which is time-consuming and error-prone even for an expert engineer. However, there is a lack of studies on the automatic definition for security assertions. To fill in this gap, we propose an automatic security assertion extraction (ASAX) tool. ASAX labels the candidate signals and infers the proposed register transfer level (RTL) invariants from simulation traces. Next, the security assertions are mined from the inferred RTL invariants. By adopting a two-step invariants inferring technique, ASAX can extract high-coverage assertions with a low runtime. We validate the effectiveness and efficiency of ASAX through experiments on the benchmarks from Trust-hub, DeTrust and OpenCores. The results show that the HT can be 100% detected by model checking with the extracted security assertions.

As one of the most effective proactive countermeasures against reverse engineering, circuit camouflaging has emerged to be a hot research topic and it is becoming a mature technology with the development of various de-camouflaging attacks. Among them, the SAT-based method is the most powerful one to defeat circuit camouflaging. However, SAT-based attacks have scalability problem due to the complexity of the underlying SAT solvers, and straightforward approach to parallelize SAT-based attacks will fail. In this paper, we propose a two-level partition method (independent module partitioning and k-medoids clustering), together with a novel conflict avoidance strategy to solve the problem. Experimental results on OpenSparc T1 microprocessor controller demonstrate that our approach can on average reduce the scales of the SAT formulas by more than 50% and achieve 3.6× speedup on the best-known SAT-based de-camouflaging tool.

We present a novel boundary-aware face alignment algorithm by utilising boundary lines as the geometric structure of a human face to help facial landmark localisation. Unlike the conventional heatmap based method and regression based method, our approach derives face landmarks from boundary lines which remove the ambiguities in the landmark definition. Three questions are explored and answered by this work: 1. Why using boundary? 2. How to use boundary? 3. What is the relationship between boundary estimation and landmarks localisation? Our boundary-aware face alignment algorithm achieves 3.49% mean error on 300-W Fullset, which outperforms state-of-the-art methods by a large margin. Our method can also easily integrate information from other datasets. By utilising boundary information of 300-W dataset, our method achieves 3.92% mean error with 0.39% failure rate on COFW dataset, and 1.25% mean error on AFLW-Full dataset. Moreover, we propose a new dataset WFLW to unify training and testing across different factors, including poses, expressions, illuminations, makeups, occlusions, and blurriness. Dataset and model are publicly available at https://wywu.github.io/projects/LAB/LAB.html

Electromigration (EM) in interconnects is becoming a major concern as the scaling of technology nodes. Electromigration affects chip performance and signal integrity seriously by generating shorts or opens, and then shortens the life-time of integrated circuits. In this paper, we propose an EM-aware routing algorithm in both global and detailed routing stages. Based on physics-based EM modeling and analysis, EM issue is modeled as physical design rule. In global routing stage, an efficient EM-aware Mazerouting algorithm is implemented. An concurrent EM-aware detailed router is then proposed based on multi-commodity flow method. Experimental results show that comparing with general routing algorithm, the proposed EM-aware algorithm could effectively reduce EM risk of signal wires by 92% with slight increasing of wire length and via count.

Electromagnetic (EM) analysis is to reveal the secret information by analyzing the EM emission from a cryptographic device. EM analysis (EMA) attack is emerging as a serious threat to hardware security. It has been noted that the on-chip power grid (PG) has a security implication on EMA attack by affecting the fluctuations of supply current. However, there is little study on exploiting this intrinsic property as an active countermeasure against EMA. In this paper, we investigate the effect of PG on EM emission and propose an active countermeasure against EMA, i.e. EM Equalizer (EME). By adjusting the PG impedance, the current waveform can be flattened, equalizing the EM profile. Therefore, the correlation between secret data and EM emission is significantly reduced. As a first attempt to the co-optimization for power and EM security, we extend the EME method by fixing the vulnerability of power analysis. To verify the EME method, several cryptographic designs are implemented. The measurement to disclose (MTD) is improved by 1138x with area and power overheads of 0.62% and 1.36%, respectively.

Detailed routing is an important stage in very large scale integrated physical design. Due to the extreme scaling of transistor feature size and the complicated design rules, ensuring routing completion without design rule checking (DRC) violations becomes more and more difficult. Studies have shown that the low routing quality partly results from nonoptimal net-ordering nature of traditional sequential methods. The concurrent routing strategy is always based on an NP-hard model, thus is at a disadvantage in runtime. In this paper, we present a novel concurrent detailed routing algorithm that routes all nets simultaneously. Based on the multicommodity flow model, detailed routing problem with complex design rule constraints is formulated as an integer linear programming. Some model simplification heuristics and efficient model solving algorithms are proposed to improve the runtime. Experimental results show that, the proposed algorithms can reduce the DRC violations by 80%, meanwhile can reduce wirelength and via count by 5% and 8% compared with an industry tool. In addition, the proposed algorithm is general that it can be adopted as an incremental detailed router to refine a routing solution, so the number of DRC violations that industry tool cannot fix are further reduced by 27%.

Flow-based microfluidic biochips are attracting increasing attention with successful applications in biochemical experiments, point-of-care diagnosis, etc. Existing works in design automation consider the flow-layer design and control-layer design separately, lacking a global optimization and hence resulting in degraded routability and reliability. This paper presents a novel integrated physical co-design methodology, which seamlessly integrates the flow-layer and control-layer design stages. In the flow-layer design stage, a sequence-pair-based placement method is presented, which allows for an iterative placement refinement based on routing feedbacks. In the control-layer design stage, the minimum cost flow formulation is adopted to further improve the routability. Besides that, effective placement adjustment strategies are proposed to iteratively enhance the solution quality of the overall control-layer design. Experimental results show that compared with the existing work, the proposed design flow obtains an average reduction of 40.44% in flow-channel crossings, 31.95% in total chip area, and 22.02% in total flow-channel length. Moreover, all the valves are successfully routed in the control-layer design stage.

Flow-based microfluidic biochips are promising with significant applications for automating and miniaturizing laboratory procedures in biochemistry. Automated design methods for flow-based microfluidic biochips are becoming increasingly important due to the advancement in both integration scale and design complexity for complicated biochemical applications. Though the multilayer soft lithography fabrication provides flexibility to route both flow and control channels in any angle, existing routing algorithms still adopt Manhattan routing metrics, which design channel in either vertical or horizontal direction only. Moreover, based on the computational fluid dynamics analysis, rectilinear channels with 90° bends have the following issues: 1) reduced the fluidic flow rate, which degrades the performance of the biochip and may even result in the erroneous outcome of the whole procedure and 2) increased pressure at the right-angle bend, which negatively affects the reliability of the biochip. To fully utilize the routing flexibility, this paper proposes the first any-angle routing algorithm for flow-based microfluidic biochip, called AARF. Computational simulation results show that compared with traditional Manhattan routing method, the proposed AARF significantly improves the total wirelength and total effective wirelength (considering the turning angles) by 17.11% and 35.91%, respectively, which prove the effectiveness of the AARF routing flow.

Flow-based microfluidic biochips have progressed significantly in the past decade. Thanks to innovations in multilayer soft lithography (MSL) fabrication technology, the integration of thousands of microvalves along with large-scale networks of microchannels on a chip has been enabled. This progress has even been compared to the evolution of VLSI circuits following Moore's Law. In flow-based microfluidic biochips, microvalves are critical components to control the fluidic transportation for complex operations. To activate the open/close states of a microvalve, off-chip control pins are required. Due to the tremendous increase of the number of microvalves, a software-programmable microfluidic platform has been proposed to reduce the number of off-chip control pins, which integrates a microfluidic multiplexer on a separate control layer to control the array of microvalves. The multiplexer needs to be switched when the states of microvalves are changed between every two adjacent time slots. High switching frequency will make the multiplexer vulnerable and decrease the chip's reliability. We observe that different switching orders of microvalves lead to different switching frequencies of a multiplexer. Based on this observation, this paper proposes the first Hamming-distance-based switching order optimization method for microvalves to enhance the reliability of the multiplexer. Experimental results show that our method can significantly reduce the switching frequency of multiplexer, and the solution is very close to the theoretical optimal lower bound.

Electromigration (EM) is considered to be one of the most important reliability issues for current and future ICs in 10nm technology and below. In this paper we focus on the EM stress evaluation for one-dimensional multi-segment interconnect wires in which all the segments have the same direction, which is a common routing structure for power grid networks. The proposed method, which is based on integral transform technique, could efficiently calculate the hydrostatic stress evolution for multi-segment metal wires stressed with different current densities. The new method can also naturally consider the pre-existing residual stresses coming from thermal or other stress sources. Based on this new transient EM assessment method, a full-chip assessment algorithm for power grid networks is then proposed. The new algorithm is also based on the IR-drop metrics for failure assessment of the power grid networks. However, it finds the precise location and time of EM-induced void nucleation by directly checking the time-changing hydrostatic stresses of all the wires. The resulting EM assessment method can ensure sufficient accuracy of the EM verification for large scale power grid networks without sacrificing the efficiency. The accuracy of the proposed transient analysis approach is validated against the numerical analysis. Also the resulting EM-aware full-chip power grid reliability analysis has been demonstrated and compared with existing methods.

Existing sample preparation algorithms are either based on NP-style problem formulations, e.g., using integer linear programming (ILP), which runs very slowly, or based on heuristic algorithms, which cannot obtain optimal solutions regarding different objectives. This paper proposes the first online sample preparation algorithm based on the lookup table method, named LUTOSAP. LUTOSAP enables fast query response for online sample preparation requirements with the solution where the weighted sum of sample consumption, buffer consumption, and the number of mix-split operations is optimized. Experimental results show that LUTOSAP obtains optimal sample preparation solutions in microseconds within the accuracy tolerance of $0.2\%$ for both single and double concentration values, which is orders of magnitude faster than existing algorithms. For multiple concentration values, the multiple-target sample preparation algorithm in LUTOSAP obtains near-optimal solution based on the constructed lookup table in microseconds, which well meets the critical fast-response requirements in online sample preparation.

Gate camouflaging has emerged as a leading proactive countermeasure for reverse engineering (RE) attacks. However, a recently proposed circuit partition attack (CPA) can significantly reduce the complexity of revealing the original design from a camouflaged circuit. In this paper, we first conduct an empirical study on how CPA can facilitate the state-of-the-art de-camouflaging methods to perform more efficient attacks. We then study how an equivalent class guided camouflaging approach may thwart these de-camouflaging attempts and re-establish the defense against RE. Experimental results demonstrate that (1) CPA is an effective pre-processing technique to boost de-camouflaging methods, and (2) Equivalent class guided camouflaging technique is resilient against the union of CPA and existing de-camouflaging methods.

In recent years, formal methods have been adopted to detect the hardware Trojans (HT). However, they generally suffer from the time-consuming and error-prone development for property, lack of self-learning system to counter with the future HT types, and high computational complexity due to the growth of design scales. To overcome the above limitations, we propose an automatic security property generation method (ASPG) by feature analysis and property matching techniques. Machine learning is applied to systematically training the property library from the suspicious behaviors in unknown designs, which is expected to counter with the future HT. To reduce the computational complexity, we transform the register-transfer level (RTL) code into an introduced succinct abstract format to remove the redundant information which is unnecessary for depicting HT features. Experimental results show that the properties are generated in less than 50 ms with low memory consumption and the benchmarks from Trust-hub and DeTrust can be successfully detected with 0 false negatives and positives.

Power attack is an important side-channel attack (SCA) method based on the correlation between measured power profile and internal switching activities. Various techniques have been proposed to prevent power attack. It has been noted that the on-chip power grid (PG) has a vital effect on the effectiveness of power attack by inducing a noise in the power profile. However, there is a lack of study on this intrinsic effect of PG. In this paper, we explore the methods of exploiting the PG-induced noise to counter with power attack. We note that the PG-induced noise strongly depends on the PG impedance and it can be regulated by adjusting the PG capacitor to control the power profile to fixed values, which contributes to reducing the power leakage. Further, we propose a novel adjustment technique for PG capacitor, i.e. power profile equalizer (PPE), as a lightweight (low-overhead) countermeasure against power attack. PPE exploits the regulated noise to equalize the power profile without violating the layout and supply noise constraints. To reduce the overheads, random walk is adopted to utilize the utmost on-chip resources. Moreover, PPE is implemented by optimizing PG which is an essential IC component rather than producing new circuits. As a result, PPE incurs low overheads. Experimental results show that PPE is able to improve the measurements to disclose (MTD) by 1800x while the area and power increase respectively by 0.12% and 0.91%.

Wirelength is a traditional optimization objective in global placement algorithms. To eliminate cell overlaps, spreading forces need to be added to pull cells away from highly congested areas. At the same time, to optimize wirelength, the quadratic nature should be maintained. In this paper, several techniques are proposed to optimize spreading force orientation and modulation. Specifically, a percentage-driven method is proposed to cluster overfilled bins, followed by a center-uniformization algorithm to demarcate the expand region for the cluster. Finally, cells are distributed evenly within each expand region while maintaining relative cell positions and minimizing cell displacements. Experimental results show that the global placer that integrated with the proposed strategies achieves 13.0% and 2.1% less wirelength compared with Capo10.5 and Aplace3, respectively.

Flow-based microfluidic biochips are attracting increasing attention with successful applications in lab-on-a-chip experiments and point-of-care diagnosis. Physical design for flow-based biochips determines the number of flow-channel intersections, and thus affects the number of microvalves. As reducing microvalves will significantly improve the overall design quality and reliability, physical design is of great importance. Typically, physical design consists of two major stages, i.e., component placement and routing. Existing works follow the step-by-step scheme, which perform placement and routing separately. The lack of interactions between the two design stages results in degraded design with large number of unfavorable channel intersections and microvalves. This paper presents a novel placement and routing method based on the sequence-pair representation, which seamlessly integrates placement and routing stages and allows iterative placement adjustment upon routing feedbacks. Experimental results show that compared with the existing work, the proposed method obtains average 54.10% improvement in flow-channel crossings, 42.15% improvement in total chip area, and 23.43% improvement in total channel length.

In modern VLSI design, manufacturing yield and chip performance are seriously affected by via failure. Redundant via insertion is an effective technique recommended by foundries to deal with the via failure. However, due to the extreme scaling of feature size, it is more and more difficult to resolve redundant via insertion (RVI) with limited routing resource while obeying complicated design rules. In this paper, we propose an RVI enhanced concurrent detailed router, MCFRoute 2.0, which effectively avoids design rule violations through a compact integer linear programming (ILP) model. The proposed router can not only route all nets simultaneously but also search for redundant via positions for all via simultaneously during routing stage. In addition, it proposes an RVI aware pin access allocation to further improve the routing performance. Experimental results show that our detailed router outperforms an industry EDA tool that it improves the redundant via insertion rate by 21%, while reducing design rule checking violation count, total wire length and via count by 47%, 4% and 14%, respectively.

Circuit obfuscation techniques have been proposed to conceal circuit's functionality in order to thwart reverse engineering (RE) attacks to integrated circuits (IC). We believe that a good obfuscation method should have low design complexity and low performance overhead, yet, causing high RE attack complexity. However, existing obfuscation techniques do not meet all these requirements. In this paper, we propose a polynomial obfuscation scheme which leverages special designed multiplexers (MUXs) to replace judiciously selected logic gates. Candidate to-be-obfuscated logic gates are selected based on a novel gate classification method which utilizes IC topological structure information. We show that this scheme is resilient to all the known attacks, hence it is secure. Experiments are conducted on ISCAS 85/89 and MCNC benchmark suites to evaluate the performance overhead due to obfuscation.

Paper-based digital microfluidic biochips (P-DMFBs) have recently emerged as a promising low-cost and fast-responsive platform for biochemical assays. In P-DMFBs, electrodes and control lines are printed on a piece of photo paper using inkjet printer and conductive ink of carbon nanotubes (CNTs). Compared with traditional digital microfluidic biochips (DMFBs), P-DMFBs enjoy notable advantages, such as faster in-place fabrication with printer and ink, lower costs, better disposability, etc. Because electrodes and CNT control lines are printed on the same side of a paper, a new design challenge for P-DMFB is to prevent the interference between moving droplets and the voltages on CNT control lines. These interactions may result in unexpected droplet movements and thus incorrect assay outputs. To address the new challenges in automated design of P-DMFBs, this paper proposes the first control-fluidic codesign flow, which simultaneously adjusts the control line routing and fluidic droplet scheduling to achieve an optimized solution. As the control line routing may not be able to address all the interferences between moving droplets and the voltages on control lines, droplet rescheduling is performed to effectively deal with the remaining interferences in the routing solution. Computational simulation results on real-life bioassays show that the proposed codesign method successfully eliminates all the interferences, while a state-of-the-art maze routing method cannot solve any of the benchmarks without conflicts.

Physical Unclonable Function (PUF) is one of the most efficient technique to generate unique and random identification for chip authentication. Ring oscillator (RO) PUF takes advantage of delay variations of a pair of ROs, which is easy to implement on FPGAs. An important consideration for FPGA based RO PUF is how to eliminate systematic variation without reducing the number of output bits. To address this problem, we introduce high performance RO organization and comparison framework. Moreover, an enhanced configurable RO, which has up to 512 different configurations but only occupies one FPGA slice, is proposed to improve the reliability and output bits number. Experimental results demonstrate that our PUF achieves best value on bit-aliasing rate (50.37%) compared with other existing configurable RO PUFs. The output bits number also increases by the factors of 2.1-9.2.

Circuit camouflaging techniques have been proposed to thwart reverse engineering (RE) attacks to integrated circuits (IC). In one of the most well-known camouflaging methods, selective XOR, NAND, and NOR gates are replaced by configurable logic units which have the same appearance to the RE attackers. It is argued that a successful attack has to brute force search all the camouflaged gates' possible {XOR, NAND, NOR} combinations, resulting in the attack complexity exponential to the number of camouflaged gates. In this paper, we have reported an attack to significantly reduce this complexity by partitioning the IC to many subcircuits to attack individually. We validate the power of the proposed circuit partition based attack on IS CA S benchmark suite and OpenSparc T1 microprocessor, and propose a potential countermeasure to re-secure IC camouflaging.

Digital microfluidic biochips (DMFBs) are gaining increasing attention with promising applications for automating and miniaturizing laboratory procedures in biochemistry. In DMFBs, cross-contamination of droplets with different biomolecules is a major issue, which causes significant errors in bioassays. Washing operations are introduced to clean the cross-contamination spots. However, existing works have oversimplified assumptions on the washing behavior, which either assume infinite washing capacity, or ignore the routing conflicts between functional and washing droplets. This paper proposes the first integrated functional and washing droplet routing flow, which considers practical issues including the finite washing capacity constraint, and the routing conflicts between functional and washing droplets. Washing droplets of different sizes are also proposed to wash the congested cross-contamination spots. Effectiveness of the proposed method is validated by real-life biochemical applications.

Early stage power estimation is critical for SoC architecture exploration and validation in modern VLSI design, but real-time, long time interval and accurate estimation is still challenging for system-level estimation and software/hardware tuning. This work proposes a model abstraction approach for real-time power estimation in the manner of machine learning. The singular value decomposition (SVD) technique is exploited to abstract the principle components of relationship between register toggling profile and accurate power waveform. The abstracted power model is automatically instrumented to RTL implementation and synthesized into FPGA platform for real-time power estimation by instrumenting the register toggling profile. The prototype implementation on three IP cores predicts the cycle-by-cycle power dissipation within 5% accuracy loss compared with a commercial power estimation tool.

In flow-based microfluidic biochips, microvalves on the control layer need to be connected to control pins via control channels. In application-specific and portable microfluidic devices, critical microvalves need to switch at the same time for correct functionality. Those microvalves are required to have equal or similar channel lengths to the control pin, so that the control signal can reach them simultaneously. This paper presents a practical control-layer routing flow (PACOR) considering the critical length-matching constraint. Major features of PACOR include: (1) effective candidate Steiner tree construction and selection methods for multiple microvalves based on the deferred-merge embedding (DME) algorithm and maximum weight clique problem (MWCP) formulation, (2) minimum cost flow-based formulation for simultaneous escape routing for improved routability, and (3) minimum-length bounded routing method to detour paths for length matching. Computational simulation results show effectiveness and efficiency of PACOR with promising matching results and 100% routing completion rate.

The chip-level design problem is critical in pin-constrained electrowetting-on-dielectric (EWOD) biochips, which not only affects the number of control pins and PCB routing layers from the manufacturing cost point of view, but also determines the functional reliability induced by excessive applied voltage. Existing works either greedily minimize the number of control pins with degraded routability, or disregard the differences in driving voltages on the electrodes, where the trapped charge due to excessive applied voltage causes significant reliability issue. This paper presents the first SVM-based classifier for electrode addressing in chip-level design stage, which simultaneously optimizes the number of control pins, routability, as well as reliability. Experimental results on both real-life chips and synthesized benchmarks show that, compared with the state-of-the-art method, the SVM-based electrode addressing method obtains significant improvements in both routability and reliability.

As VLSI technology continuously scales down, buffered clock tree synthesis (CTS) has become increasingly critical in an attempt to generate a high-performance synchronous chip design. This paper presents a novel obstacle-avoiding CTS approach with slew constraints satisfied and signal polarity corrected. We build a look-up table through NGSPICE simulation to achieve accurate buffer delay and slew, which guarantees that the final skew after NGSPICE simulation is as satisfactory as expected. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buffer positions and a fast heuristic buffer insertion algorithm. With an overall view on obstacles to explore the global optimization space, our CTS approach effectively overcomes the negative influence on skew brought by the obstacles. Experimental results show the effectiveness of our CTS approach with significantly improved skew and latency by 69.0% and 72.0% on average. In addition, the accuracy of the look-up table is demonstrated through the huge skew reduction by 87.3% on average. Moreover, our OBB heuristic algorithm obtains 53.2% improvement in skew than the classic balanced bipartition algorithm.

Vectorless power grid verification is a practical approach for early stage safety check without input current patterns. The power grid is usually formulated as a linear system and requires intensive matrix inversion and numerous linear programming (LP), which is extremely time-consuming for large-scale power grid verification. In this paper, the power grid is represented in the manner of domain-decomposition approach, and we propose a selected inversion technique to reduce the computation cost of matrix inversion for vectorless verification. The locality existence among power grids is exploited to decide which blocks of matrix inversion should be computed while remaining blocks are not necessary. The vectorless verification could be purposefully performed by this manner of selected inversion, while previous direct approaches are required to perform full matrix inversion and then discard small entries to reduce the complexity of LP. Meanwhile, constraint locality is proposed to improve the verification accuracy. In addition, a concept of quasi-Poisson block is introduced to exploit grid locality among realistic power grids and a scheme of pad-aware partitioning is proposed to enable the selected inversion approach available for practical use. Experimental results show that the proposed approach could achieve significant speedups compared with previous approaches while still guaranteeing the quality of solution accuracy.

With the rapid growth of design size and complexity, global routing has always been a hard problem. Several new factors contribute to global routing congestion and can only be measured and optimized in 3-D global routing rather than 2-D routing. We propose an enhanced congestion model in global routing to capture local congestion and more accurately reflect modern design rule requirements. To achieve better global and detailed routing solution quality, we propose a 3-D global router VFGR with parallel computing using this congestion model. Experimental results show that VFGR can achieve comparable or better global routing solution quality with two start-of-the-art global routers in shorter runtime. It is also demonstrated that adopting proposed congestion model in global routing, higher solution quality and much shorter runtime can be achieved in detailed routing stage.

Time-Domain worst case or performance bound estimation for analog integrated circuits and interconnect circuits are crucial for both analog and digital circuit design and optimization in the presence of process variations. In this paper, we present a novel non-Monte-Carlo (MC) performance bound analysis technique in time domain. The new method consists of several steps. First the symbolic transient modified nodal analysis (MNA) formulation of the circuit matrices of (linearized) analog and interconnect circuits at a time step is formed. Then the closed-form expressions of the interested performance in terms of variational parameters of the circuit matrices of (linearized) analog and interconnect circuits are derived via a graph-based symbolic analysis method. Then time-domain performance response bound of current time step are obtained by a nonlinear constrained optimization process subject to the parameter variations and variational circuit state bounds computed from the previous time step. We study the bounds computed by the proposed against the different sigma bounds by the standard MC method, which shows that the proposed method is more efficient for computing high sigma bounds than the MC method. Experimental results show that the new method can deliver order of magnitudes speedup over the standard Monte Carlo simulation on some typical analog circuits and interconnect circuits with high accuracy.

Power grid integrity verification is critical for reliable chip design. Vectorless power grid verification provides a promising approach to evaluate the worst-case voltage fluctuations without the detailed information of circuit activities. Vectorless verification is usually required to solve numerous linear programming problems to obtain the worst-case voltage fluctuation throughout the grid, which is extremely time-consuming for large-scale verification. In this paper, a maximum voltage drop location estimation approach is proposed for efficient vectorless verification. The power grid nodes are grouped into disjoint subsets, and an estimation strategy is utilized to roughly locate the nodes which have the worst-case voltage drop in each group. Consequently, the verification problem size can be significantly reduced compared with accurate verification. Experimental results show that the proposed approach can achieve remarkable speedups with acceptable accuracy loss.

In digital microfluidic biochips, cross-contamination of different biomolecule droplets is a major issue. Washing operations are introduced to clean the cross-contamination sites. Existing works have oversimplified assumptions on the washing behavior, which either assume unrealistic infinite washing capacity, or ignore the execution time constraint and/or the routing conflicts between functional and washing droplets. This paper presents the first practical droplet routing flow, which considers realistic issues including the finite washing capacity constraint, and the routing conflicts between washing and functional droplets. Effectiveness of the presented method are validated by real-life biochemical applications.

Side Channel Attack (SCA) aims to extract the secret information from cryptography chips by analyzing the leakage of physical parameters. Power analysis based SCA is a popular approach to obtain secret keys by monitoring the power consumption of cryptography chips. However, most SCA evaluation methods are performed on FPGA platforms while many parasitic physical effects cannot be revealed before the cryptography chips are taped out. Roughly ignoring these effects will significantly increase the attack difficulties due to the corresponding measurement noise. Power supply noise has been observed to be critical for power analysis based SCA. This paper demonstrates a power supply noise aware evaluation framework for practical side channel attack from cryptography system design to physical design. On-chip power delivery network is implemented among physical design stage. Consequently the supply noise of power network can be explored according to the post-layout implementation. Additionally, the countermeasures of cryptography chips could be enhanced by on-chip decapacitors placement due to its influences on the characteristics of power delivery network.

Detailed routing is an important stage in VLSI physical design. Due to the high routing complexity, it is difficult for existing routing methods to guarantee total completion without design rule checking violations (DRCs) and it generally takes several days for designers to fix remaining DRC-s. Studies has shown that the low routing quality partly results from non-optimal net-ordering nature of traditional sequential methods. In this paper, a novel concurrent detailed routing algorithm is presented that overcomes the net-order problem. Based on the multi-commodity flow (M-CF) method, detailed routing problem with complex design rule constraints is formulated as an integer linear programming (ILP) problem. Experiments show that the proposed algorithm is capable of reducing design rule violations while introducing no negative effects on wirelength and via count. Implemented as a detailed router following track assignment, the algorithm can reduce the DRCs by 38%, meantime, wirelength and via count are reduced by 3% and 2.7% respectively comparing with an industry tool. Additionally, the algorithm is adopted as an incremental detailed router to refine a routing solution, and experimental results show that the number of DRCs that industry tool can't fix are further reduce by half. Utilizing the independency between subregions, an efficient parallelization algorithm is implemented that can get a close to linear speedup.

Routing congestion model is of great importance in design stages of modern physical synthesis, e.g. global routing and routability estimation during placement. As the technology node becomes smaller, routing congestion is more difficult to estimate during design stages ahead of detailed routing. In this paper, we propose a framework using nonparametric regression technique in machine learning to construct routing congestion model. The constructed model can capture multiple factors and enables direct prediction of detailed routing congestion with high accuracy. By using this model in global routing, significant reduction of design rule violations and detailed routing runtime can be achieved compared with the model in previous work, with small overhead in global routing runtime and memory usage.

Clock networks dissipate a significant fraction of the entire chip power budget. Therefore, the optimization for power consumption of clock networks has become one of the most important objectives in high performance IC designs. In contrast to most of the traditional works that handle this problem with clock routing or buffer sizing, this paper proposes a novel register clustering algorithm in generating the leaf level topology of the clock tree to reduce the power consumption. Aiming to guarantee the stability of our register clustering algorithm, an effective initialization algorithm called “K-Splitting” and a “Pseudo Center” technology are developed. Meanwhile, a buffer allocation algorithm is proposed to satisfy the slew constraints within the clusters at a minimum cost of power consumption. We implement the clock tree synthesis (CTS) flow in [2] to test our approach on ISPD'10 benchmark circuits. Experimental results show that our register clustering algorithm achieves a 29.0% reduction in power consumption as well as a 5.7% reduction in max latency without affecting the clock skew. Moreover, the total runtime of the CTS flow with our register clustering algorithm is significantly reduced by 87.3%.

Robust and efficient algorithms for power grid analysis are crucial for both VLSI design and optimization. Due to the increasing size of power grids, IR drop analysis has become more computationally challenging both in runtime and memory consumption. This paper presents a Fast Poisson Solver (FPS) preconditioned method for unstructured power grids with unideal boundary conditions. Unstructured power grids are transformed to structured grids, which can be modeled as Poisson blocks by analytic formulation. The analytic formulation of transformed structured grids is adopted as an analytic preconditioner for original unstructured grids, in which the analytic preconditioner can be considered as a sparse approximate inverse technique. By combining this analytic preconditioner with robust conjugate gradient method, we demonstrate that this approach is totally robust for extremely large scale power grid simulations. Theoretical proof and experimental results show that iterations of our proposed method will hardly increase with the increasing of grid size as long as the pads density and the distribution range of metal conductance value have been decided. We demonstrate that the run efficiency of our approach is much higher than classical incomplete Cholesky factorization preconditioned conjugate gradient solver and random walk-based hybrid solver.

Efficient power grid analysis is critical for modern very large scale integration design but is computationally challenging in runtime and memory consumption because of the increasing size of power grids. PowerRush is proposed as an efficient IR-drop simulator, which includes an efficient SPICE parser, a robust circuit builder, and a linear solver Algebraic MultiGrid Preconditioned Conjugate Gradient. The proposed AMG-PCG solver is a pure algebraic method, which can provide stable convergence without geometric information. Aggregation-based AMG with K-cycle acceleration is adopted as a preconditioner to improve the scalability of iterative method. In multigrid scheme, double pairwise aggregation technique is applied to matrix graph in coarsening to ensure low setup cost and memory requirement. Furthermore, K-cycle multigrid scheme is adopted to provide Krylov subspace acceleration at each level to guarantee enhanced robustness and scalability. The experimental results for large-scale power grids have shown that PowerRush has remarkable scalability both in runtime and memory consumption. DC analysis of power grid with 60-million nodes can be solved by PowerRush for 0.01 $mV$ accuracy within 150 s and 21.99 GB total memory used. Moreover, the proposed AMG-PCG solver can perform much better than widely used direct solver Cholmod and well-developed Hybrid solver both on runtime and memory consumption.

Yield estimation for analog integrated circuits are crucial for analog circuit design and optimization in the presence of process variations. In this paper, we present a novel analog yield estimation method based on performance bound analysis technique in frequency domain. The new method first derives the transfer functions of linear (or linearized) analog circuits via a graph-based symbolic analysis method. Then frequency response bounds of the transfer functions in terms of magnitude and phase are obtained by a nonlinear constrained optimization technique. To predict yield rate, bound information are employed to calculate Gaussian distribution functions. Experimental results show that the new method can achieve similar accuracy while delivers 20 times speedup over Monte Carlo simulation of HSPICE on some typical analog circuits.

Vectorless power grid verification technique makes it possible to estimate the worst-case voltage fluctuations of the on-chip power delivery network at the early design stage. For most of the existing vectorless verification algorithms, the sub-problem of linear system solution which computes the inverse of the power grid matrix takes up a large part of the computation time and has become a critical bottleneck of the whole algorithm. In this paper, we propose a new algorithm that combines the ℌ-matrix-based technique and the multilevel method to construct a data-sparse approximate inverse of the power grid matrix. Experimental results have shown that the proposed algorithm can obtain an almost linear complexity both in runtime and memory consumption for efficient vectorless power grid verification.

To capture detailed routing congestion factors in sub-90nm technology nodes, we propose a practical congestion model embedded in 3-D global routing grid graph. Using a concept of pass-through capacity and demand, intra-gcell congestion contributed by fat vias, stacked vias, local nets and related design rules can be measured and optimized. Proposed congestion model is compatible with existing widely-used path search algorithms in global routing. Experimental results validate proposed model, and demonstrate that 42% less design rule violations and 46% shorter full-flow routing runtime, as well as 3% shorter wire length and 4% less via count in detailed routing results can be achieved using proposed congestion model in global routing stage.

Physical Unclonable Function (PUF) makes use of the uncontrollable process variations during the production of IC to generate a unique signature for each IC. It has a wide application in security such as FPGA Intellectual Property (IP) protection, key generation and digital rights management. Ring Oscillator (RO) based PUF and Arbiter-based PUF are the most popular PUFs, but they are not specially designed for FPGA. RO-based PUF incurs high resource overhead while obtaining less challenge-response pairs, and requires ``hard macros'' to implement on FPGA. The arbiter-based PUF brings low resource overhead, but its structure is hard to be mapped on FPGA. Anderson'PUF can address these weaknesses of current Arbiter-based and RO-based PUFs. However, it cannot be directly implemented on the new generation FPGAs, and therefore it has the scalability issue. In order to address these problems, this paper presents a delay-based PUF using the intrinsic structure of FPGA (look-up table and multiplexer). The proposed delay-based PUF is completely realized on 28nm FPGAs. The experimental results show its high uniqueness and reliability. Moreover, we test the proposed PUF in the high temperature, and the results show its availability. Finally, the prospect of the proposed PUF in the FPGA IP protection is discussed.

Vectorless power grid verification is a practical approach for early stage safety check without input current patterns. The power grid is usually formulated as a linear system and requires intensive matrix inversion and numerous linear programming, which is extremely time-consuming for large scale power grid verification. In this paper, the power grid is represented in the manner of domain-decomposition approach, and we propose a selected inversion technique to reduce the computation cost of matrix inversion for vectorless verification. The locality existence among power grids is exploited to decide which blocks of matrix inversion should be computed while remaining blocks are not necessary. The vectorless verification could be purposefully performed by this manner of selected inversion while previous direct approaches are required to perform full matrix inversion and then discard small entries to reduce the complexity of linear programming. Meanwhile, constraint locality is proposed to improve the verification accuracy. Experimental results show that the proposed approach could achieve significant speedups compared to previous approaches while still guaranteeing the quality of solution accuracy.

Due to the high integration on vertical stacked layers, power/ground network design becomes one of the critical challenges in 3D IC design. With the leakage-thermal dependency, the increasing on-chip temperature in 3D designs has serious impact on IR drop due to the increased wire resistance and increased leakage current. Power/ground (P/G) TSVs can help to relieve the IR drop violation by vertically connecting the on-chip P/G networks on different layers. However, most previous work only fulfills a margin of the full potential of PG TSVs planning since the P/G grids are restricted in a uniform topology. Besides, the overlook of resistance variation and leakage current will make the results less accurate. In this paper, we present an efficient thermal-aware P/G TSVs planning algorithm based on a sensitivity model with temperature-dependent leakage current considered. The proposed method can overcome the limitation of uniform P/G grid topology and make full use of P/G TSVs planning for the optimization of P/G network by allowing short wires to connect the P/G TSVs to P/G grids in non-uniform topology. Moreover, with resistance variation and increased leakage current caused by high temperature in 3D ICs, more accurate result can be obtained. Both the theoretical analysis and experimental results show the efficiency of our approach. Results show that neglecting thermal impacts on power delivery can underestimate IR drop by about 11%. To relieve the severe IR drop violation, 51.8% more P/G TSVs are needed than the cases without thermal impacts considered. Results also show that our P/G TSV planning based on the sensitivity model can reduce max IR drop by 42.3% and reduce the number of violated nodes by 82.4%.

Enabled by the heterogeneous integration in modern System-On-Chips (SOCs), the design automation for analog and mixed signal circuit components in SOCs is attracting increasing interests. Matching constraints for specific analog signals are critical for correct functionalities. This paper presents a novel single-layer detailed routing algorithm with the length matching constraint, called LEMAR. LEMAR features an innovative routing model for partitioning the routing layout for wire detouring, effective detouring patterns according to the geometric shapes of the partitioned tiles, an enhanced A*-search algorithm along with the backtrack technique for finding the routing path, and an iterative rip-up and reroute procedure for finding the feasible routing solution with the matching constraint. Experimental results are promising and show that LEMAR is both effective and efficient.

Transient analysis is the most practical and effective approach for power grid validation, but which is very challengeable for large scale VLSI chips because it is really time consuming and requires large memory resources. In this paper we proposed a parallel transient simulation approach for efficient power grid analysis. Firstly we adopt symmetric formulation for NA equation of RLC power grid to reduce memory usage. Meanwhile, fast Cholesky factorization solver can be used to improve simulation efficiency. Secondly, we perform partition-based parallel transient simulation for naturally independent subnets without accuracy lost. Thirdly, we propose a composite simulation flow for efficient and practical transient analysis for industrial power grid. Finally, several industrial power grid benchmarks are evaluated on our approaches for high accurate transient simulation with extremely low memory consumption.

Traditional sequence based routing algorithms for FPGAs usually route only one net at a time, so as to simplify the routing problems. However, with the number of logic blocks in the FPGAs becomes larger and larger, the time need to route each net can increase significantly. A new recursive detailed routing algorithm is proposed to address this problem. As decided by its recursive nature, this algorithm can only be applied for hierarchical FPGAs, which of the architectural features with its connection patterns is also presented in detail in this paper. The overall algorithm begins its routing from the topmost cluster and continues to route for each cluster from top down recursively, where the routing clusters map to the architectural cluster exactly. At each cluster level, a new heuristic is proposed to solve the specific routing problem. The scale of the problem is so small that the heuristic can be considered deterministic and quickly to solve. The proposed algorithm also takes advantages of the architectural features such as the connection patterns of switch box. As a result, the proposed algorithm is very fast in runtime due to all these facts. The experimental results show that detailed routing for a very large circuit can be done very quickly in just a few seconds.

Buered clock tree synthesis (CTS) is increasingly critical as VLSI technology continually scales down. Many researches have been done on this topic due to its key role in CTS, but current approaches either lack the obstacle-avoiding functionality or lead to large clock latency and/or skew. This paper presents a new obstacle-avoiding CTS approach with separate clock tree construction and buer insertion stages based on an integral view to explore the global optimization space. Aiming at skew optimization under constraints of slew and obstacles, our CTS approach features the clock tree construction stage with the obstacle-aware topology generation algorithm called OBB, balanced insertion of candidate buer positions, and a fast heuristic buer insertion algorithm. Experimental results show the eectiveness of our CTS approach with significantly improved skew and latency than [6] by 46% and 63% on average, and 15.3% reduction in skew than [5]. Our OBB heuristic obtains 36% improvement in skew than the classic balanced bipartition algorithm (BB) in [10].

As analog and mixed-signal (AMS) circuitry gains increasing portions in modern SoCs, automotive analog routing is becoming more and more important. This paper presents a fast real-time interactive analog router called SIAR based on a splitting graph. A key feature is that SIAR allows real-time interactions between the router and the designer. The designer can try different guiding points by moving the cursor in the user window and the router will show the corresponding routing solutions in real-time for the designer to select the most satisfactory one. To enable real-time interactions, we present a new splitting graph to represent the routing area, which greatly enhances the routing efficiency. Different design rules such as variable wire and via width/spacing are supported by the router. Moreover, SIAR supports different routing modes such as point-to-point, point-to-module and module-to-module. Experimental results show that SIAR obtains promising routing efficiency with upto 28.6x speedup and better routing solutions compared with the commercial router Laker as well as upto 108x speedup compared with a modified implication-graph-based gridless routing approach [13].

Robust and efficient algorithms for power grid analysis are crucial for both VLSI design and optimization. Due to the increasing size of power grids IR drop analysis has become more computationally challenging both in runtime and memory consumption. This work presents a fast Poisson solver preconditioned method for unstructured power grid with unideal boundary conditions. In fact, by taking the advantage of analytical formulation of power grids this analytical preconditioner can be considered as sparse approximate inverse technique. By combining this analytical preconditioner with robust conjugate gradient method, we demonstrate that this approach is totally robust for extremely large scale power grid simulations. Experimental results have shown that iterations of our proposed method will hardly increase with grid size increasing once the pads density and the range of metal resistances value distribution have been decided. We demonstrated that this approach solves an unstructured power grid with 2.56M nodes in only 1/3 iterations of classical ICCG solver, and achieves almost 20X speedups over the classical ICCG solver on runtime.

As the increasing size of power grids, IR drop analysis has become more computationally challenging both in runtime and memory consumption. In this paper, we propose a linear complexity simulator named PowerRush, which consists of an efficient SPICE Parser, a robust circuit Builder and a linear solver. The proposed solver is a pure algebraic method which can provide an optimal convergence without geometric information. It is implemented by Algebraic Multigrid Preconditioned Conjugate Gradient method, in which an aggregation based algebraic multigrid with K-Cycle acceleration is adopted as a preconditioner to improve the robustness of conjugate gradient iterative method. In multigrid scheme, double pairwise aggregation technique is applied to the matrix graph in coarsening procedure to ensure low setup cost and memory requirement. Further, a K-Cycle multigrid scheme is adopted to provide Krylov subspace acceleration at each level to guarantee optimal or near optimal convergence. Experimental results on real power grids have shown that PowerRush has a linear complexity in runtime cost and memory consumption. The DC analysis of a 60 Million nodes power grid can be solved by PowerRush for 0.01mV accuracy in 170 seconds with 21.89GB memory used.

Voltage island has become a very effective design style for power saving in low-power design. However, the new design style also brings forward new challenges, especially to the designers of power/ground (P/G) networks. In this paper, we study the power delivery problem in voltage island designs, and propose to consider voltage drop during the floorplanning process to reduce design iterations. Our analysis shows that it is unnecessary to consider the pitch of the P/G network in the floorplan stage. By using the simplified searching strategy in floorplanning, we can obtain more robust low power design within reasonable runtime. Experimental results have demonstrated the effectiveness of our approach.

In this paper, we present a new voltage IR drop analysis approach for large on-chip power delivery networks. The new approach is based on recently proposed sampling based reduction technique to reduce the circuit matrices before the simulation. Due to the disruptive nature of tap current waveforms in typical industry power grid networks, input current sources typically has wide frequency power spectrum. To avoid the excessively sampling, the new approach introduces an error check mechanism and on-the-fly error reduction scheme during the simulation of the reduced circuits to improve the accuracy of estimating the the large IR drops. The proposed method presents a new way to combine model order reduction and simulation to achieve the overall efficiency of simulation. The new method can also easily trade errors for speed for different applications. Experimental results show the proposed IR drop analysis method can significantly reduce the errors of the existing ETBR method at the similar computing cost, while it can have 10X and more speedup over the the commercial power grid simulator in UltraSim with about 1-2% errors on a number of real industry benchmark circuits.

The gramian approximation methods have been proposed recently to overcome the high computing costs of classical balanced truncation based reduction methods. But those methods typically gain efficiency by projecting the original system only onto one dominant subspace of the approximate system gramian (for instance using only controllability gramian). This single gramian reduction method can lead to large errors as the subspaces of controllability and observability can be quite different for general interconnects with unsymmetric system matrices. In this paper, we propose a fast balanced truncation method where the system is balanced in terms of two approximate gramians as achieved in the classical balanced truncation method. The novelty of the new method is that we can keep the similar computing costs of the single gramian method. The proposed algorithm is based on a generalized SVD-based balancing scheme such that the dominant subspace of the approximate gramian product can be obtained in a very efficient way without explicitly forming the gramians. Experimental results on a number of published benchmarks show that the proposed method is much more accurate than the single gramian method with similar computing costs.

Boolean Satisfiability (SAT) has successfully been applied to the FPGA routing. It has many advantages over the conventional one-net-a-time routing algorithm such as routing all nets concurrently, higher flexibility and unroutability provable. However it also has the limits of scalability and is time-consuming. This paper presents some optimizations to the SAT-based routing approach by applying some architecture related features to the generated the Boolean constraints function. Specifically, Switch Box based connectivity optimization to reduce the variable number for each net, Logic Block pins rearrangement to improve the flexibility for each net and Exclusivity constraints optimization based on net-to-track distribution. Each of the optimizations is discussed in detail in this paper. Some heuristics and algorithms are also presented to implement the optimizations. We implement the SAT-based routing strategy as well as the optimizations on a general hierarchical FPGA architecture. The experimental results show that we can greatly reduce the variable and constraint number of the generated Boolean SAT functions. Hence, the generated SAT functions can be solved much more quickly. It also shows that high routing flexibility is also achieved due to the pins rearrangement.

Manufacturing hotspots are the layout patterns which cause excessive difficulties to manufacturing process. Design rules are effective at handling sizing/spacing induced hotspots, but are inadequate at dealing with topological hotspots. In wire routings, existing approaches often remove the hotspots through iteratively ripping up and rerouting one net at a time guided by litho-simulations. This procedure can be very time-consuming because litho-simulation is typically very slow and the rerouting may result in new hotspots due to its heuristic nature. In this paper, we propose a new approach for improving the efficiency of hotspot removal. In our approach, multiple nets in each hotspot region are simultaneously ripped up and rerouted based on Boolean satisfiability (SAT). The hotspot patterns, which are described and stored in a pre-built library, are forbidden to appear in the reroute through SAT constraints. Since multiple nets are simultaneously processed and SAT can guarantee to find a feasible solution if it exists, our approach can greatly accelerate the convergence on manufacturability. Experimental results on benchmark circuits show that our approach can remove over 90% of the hotspots in less than one minute on circuits with more than 20K nets and hundreds of hotspots.

The power/ground solvers have to solve circuits with millions of nodes, and are generally assumed as processor-bounded in former study. In this paper, we focused on micro-architectural level of power/ground solvers on multi-core and identified insufficient memory bandwidth can possibly lead to poor scalability, which can be a common issue. Several solutions such as better memory traffic efficiency, reusing in-cache data and assistance of other device had been proposed to improve power/ground solvers on multi-core.

Analog signals are more sensitive to crosstalk than digital signals, resulting in instability of analog circuits. To eliminate coupling, it is common practice to insert shielding wires on one or both sides of critical signals. In this paper, a novel analog circuit shielding routing algorithm based on net classification is proposed. Circuit performance requirements are transformed into geometric properties of nets according to the result of placement, and different shielding wire routing algorithms are designed to meet these geometric properties. A* algorithm is adopted to route the critical nets, and shielding wires are added at the same time. Maze algorithm is used to route the P/G nets and other general nets. Experimental results show that the router is efficient in routing and effective in reducing crosstalk. Although capacitive load and routing area increase, the resulting coupling is negligible and the circuit performance is significantly improved.

Clock gating is one of the most effective techniques to reduce clock tree power. Although it has already been studied considerably, most of the previous works are restricted to either register transfer level (RTL) or clock tree synthesis stage. Clock gating design at RTL is coarse and it pays no attention to the physical information, therefore, it often results in large wirelength overhead. While if clock gating is considered only at clock tree synthesis, the optimization space is largely limited due to the fixing of registers. To fully use the logical and physical information between registers, we propose a new flow for low-power gated clock tree design in this work. It mainly includes three parts: gated clock tree aware register placement, gated clock tree construction, and incremental placement. Compared with the previous works on clock gating, our algorithm reduces the clock tree power with much fewer gating logics, therefore, the overhead to the placement is also reduced.

In this paper, we propose a novel statistical capacitance extraction method for interconnect conductors considering process variations. The new method is called statCap, where orthogonal polynomials are used to represent the statistical processes in a deterministic way. We first show how the variational potential coefficient matrix is represented in a first-order form using Taylor expansion and orthogonal decomposition. Then, an augmented potential coefficient matrix, which consists of the coefficients of the polynomials, is derived. After this, corresponding augmented system is solved to obtain the variational capacitance values in the orthogonal polynomial form. Finally, we present a method to extend statCap to the second-order form to give more accurate results without loss of efficiency compared to the linear models. We show the derivation of the analytic second-order orthogonal polynomials for the variational capacitance integral equations. Experimental results show that statCap is two orders of magnitude faster than the recently proposed statistical capacitance extraction method based on the spectral stochastic collocation approach and many orders of magnitude faster than the Monte Carlo method for several practical conductor structures.

In this paper, a novel design-for-manufacture-aware detailed routing algorithm that seeks to minimize the thickness range of the chip surface after copper damascene process is proposed. The paper is based on an electroplating (ECP) and chemical mechanical polishing (CMP) model and predictors for final thickness range are abstracted. The proposed detailed routing is implemented in a W-shape multilevel full-chip routing framework using depth first search and branch-and-bound techniques in maze backtracking. Experimental results show that compared to maze routing (MR) (that does not consider CMP), the improvements in the average metal density standard and the average amount of dummy fill are 12.0% and 6.99% respectively. Compared to density-driven maze routing (DMR) that considers only CMP but does not consider ECP, the improvements in the average metal density standard and the average amount of dummy fill are 0.53% and 0.72%, respectively. So, the proposed algorithm can obtain improvement in optimizing CMP while the wire length and vias are not increased clearly and the completion rate is guaranteed. Therefore, the yield of chips is improved.

In this paper, we present a novel statistical full-chip leakage power analysis method. The new method can provide a general framework to derive the full-chip leakage current or power in a closed form in terms of the variational parameters, such as the channel length, the gate oxide thickness, etc. It can accommodate various spatial correlations. The new method employs the orthogonal polynomials to represent the variational gate leakages in a closed form first, which is generated by a fast multi-dimensional Gaussian quadrature method. The total leakage currents then are computed by simply summing up the resulting orthogonal polynomials (their coefficients). Unlike many existing approaches, no grid-based partitioning and approximation are required. Instead, the spatial correlations are naturally handled by orthogonal decompositions. The proposed method is very efficient and it becomes linear in the presence of strong spatial correlations. Experimental results show that the proposed method is about 10× faster than the recently proposed method [4] with constant better accuracy.

In this paper, we propose a fast placer for FPGA placement on a new commercial hierarchical FPGA device. The novelty of this research lies in the application of a multilevel V-shape optimization flow including an architecture related cluster process and a constructive placement. The new placer can handle large-scale FPGA placement problem quickly. Experimental results show that the proposed placer can further reduced the wirelength average 28.3% compared with simulated annealing based tool while achieving near 5X speedup in runtime for the five largest MCNC benchmarks.

The three-dimensional (3D) integration circuit is a new technology with higher integration density. To solve the critical thermal issue in 3D layout, we propose a thermal-driven force-directed floorplanning algorithm. Based on the characteristic of the different stages of floorplanning, this algorithm applies different methods to calculate the thermal distribution to reach a tradeoff between time efficiency and accuracy. And a new effective strategy of the layer assignment is used in which we consider the area, the overlaps and the power densities simultaneously. Experimental results show that, compared with the recent thermal-driven force-directed 3D floorplanner, it averagely decreases the temperature by 8% and runtime by 10.7% while only increases the area and wirelength by 3% at most.

In this paper, we propose a novel simulation algorithm for large scale structured power grid networks. The new method formulates the traditional linear system as a special two-dimension Poisson equation and solves it using an analytical expressions based on FFT technique. The computation complexity of the new algorithm is O(NlgN), which is much smaller than the traditional solver's complexity O(N1.5) for sparse matrices, such as the SuperLU solver and the PCG solver. Also, due to the special formulation, graphic process unit (GPU) can be explored to further speed up the algorithm. Experimental results show that the new algorithm is stable and can achieve 100X speed up on GPU over the widely used SuperLU solver with very little memory footprint.

This paper proposes an efficient decoupling (decaps) capacitance optimization algorithm to reduce the voltage noise of on-chip power grid networks. The new method is based on the efficient charge formulation of the decap allocation problem. But different from the existing work [12], the new method applies the more accurate piecewise polynomial micromodels to estimate the voltage noises during the linear programming process. The resulting method overcomes the over-estimation problem, which plagues the existing method. The proposed method has the best of two worlds: it has the efficiency of the charge-based methods and the accuracy of the sensitivity-based methods. Experimental results demonstrate that the proposed method leads to the decap values similar to that of the sensitivity-based methods, which give the best reported results and are much better than the existing charge-based method, and at the same time, it enjoys the similar efficiency of the charge-based method.

A new fast timing-driven placement is presented in this paper, which is partitioning-based method, explicitly considering the congestion for island style FPGAs. The most distinct feature of this approach is that it not only reduces the circuit critical path delay efficiently, but also takes congestion into account. The harmony between partitioning objective and timing improvement goal is kept; moreover, the congestion constraint is added to cost function to improve routability in the meantime. As a result, it avoids the excessive usage of local routing resources while remaining circuit performance much better. The experimental results show our method, FCTP, is very fast. It is able to produce solutions with equal or better routability and up to average 8.19% improvement on performance but only less 1/3 average runtime compared to TVPR [1]. It also achieves much better results than PPFF [7] in terms of timing and congestion with negligible runtime penalty.

Decoupling capacitance (decap) is an efficient way to reduce transient noise in on-chip power supply networks. However, excessive decap may cause more leakage power, chip resource waste, and even lead to more design iterations. In this paper, we present a novel decap-efficient placement algorithm for transient power supply noise reduction. In contrast to traditional design flow, our approach considers decap impacts at the placement stage to seek the placement minimizing decap requirements while still satisfying the traditional placement objectives. In the new method, we first devise a fast procedure to assess the decap requirement for the force-based placement framework, in which the required decap is modeled as a density function over the chip. Then, we build a corresponding supply and demand system to adjust the placement in favor of minimizing decap. Finally, we develop a decap efficient placement algorithm with a new force induced by imbalance between power supply and power demands. Experimental results show that the new combined placement and decap optimization flow could reduce the minimum decap area by 35% with a wire length increase of only 0.5% at nearly the same computational cost, which is efficient for practical problems.

In multi-layered power/ground (P/G) networks, to connect the whole network together, vertical vias are usually placed at intersections between metal wires of adjoining layers. In this paper, a deep study about the design of vertical vias is presented. First we present an efficient heuristic algorithm based on sensitivity analysis to optimize via allocation in early design stage. Compared with even allocation, averagely our algorithm is capable of reducing worst voltage drop by 8.43% while using the same or even less number of vias. Also, adjoint network method is utilized and significantly improves the efficiency of our algorithm. Next, we demonstrate that by linking metal wires of nonadjacent layers, cross-layer vias are powerful in eliminating "hot" areas which suffer from large voltage drop on bottom layer. A similar heuristic algorithm is also developed for the addition of cross-layer vias.

It's a trend to consider power supply integrity at early stage to improve the design quality. In this paper, we propose a novel algorithm to optimize floorplan together with P/G network. Compared with previous methods, our algorithm can search the floorplan space more efficiently and therefore lead to better results. Further, we also propose a smart heuristic method to build P/G mesh grid with optimized topology. Experimental results show our method can speedup the floorplanning process by about 10 times and reduce the routing area of P/G network while maintaining the floorplan quality and P/G integrity.

Traditionally, clock network layout is performed after cell placement. Such methodology is facing a serious problem in nanometer IC designs where people tend to use huge clock buffers for robustness against variations. That is, clock buffers are often placed far from ideal locations to avoid overlap with logic cells. As a result, both power dissipation and timing are degraded. In order to solve this problem, we propose a low power clock buffer planning methodology which is integrated with cell placement. A Bin- Divided Grouping algorithm is developed to construct virtual buffer tree, which can explicitly model the clock buffers in placement. The virtual buffer tree is dynamically updated during the placement to reflect the changes of latch locations. To reduce power dissipation, latch clumping is incorporated with the clock buffer planning. The experimental results show that our method can reduce clock power significantly by 21% on average.

Recent generation of FPGA devices takes advantage of speed and density benefits resulted from heterogeneous FPGA architecture, in which several basic LUTs can be combined to form one larger size LUT called Macro. Large Macros not only decrease network depth efficiently but also reduce area. In this paper, a new technology mapping algorithm, named MacroMap is proposed for the heterogeneous FPGAs with effective area estimation to overcome the main disadvantage that traditional technology mapping algorithms only generate one kind of typical K-LUT and cannot make full use of LUTs with different sizes (basic LUTs and Macros). Experimental results show that MacroMap can obtain 19% gain on area while keeping the network depth optimal compared with the existing heterogeneous FPGA mapping algorithm heteromap[8].

Power Gating is an effective method to reduce leakage power. One of the most important issues in power gating design is the decision on the size of sleep transistor, which is mostly determined by the maximum instantaneous current (MIC) and the maximum tolerable voltage drop. In order to reduce the sleep transistor area, the distributed sleep transistor network (DSTN) was proposed to reduce MIC by connecting all the virtual ground nets together. Most of the following works focused on estimating the MICs through sleep transistors accurately. But the previous works use a pre-defined global voltage drop constraint on circuit, which leads to a uniform gate slowdown. In this paper, we propose a performance driven methodology for DSTN design, which exploits the maximum tolerable voltage drops of gates, particularly the non-critical ones, to reduce the total sleep transistor area without additional performance loss. Moreover, a clustering strategy in placement is proposed to help further reduce the total sleep transistor area. Experimental results show that the proposed approach can reduce the total sleep transistor area by about 36% on average.

Clock gating is a popular technique for reducing power dissipation in clock network. Although there have been numerous research efforts on clock gating, the previous approaches still have a significant weakness. That is, they usually construct a gated clock tree after cell placement, i.e., cell placement is performed without considering clock gating and may generate a solution unfriendly to subsequent gated clock tree construction. As a result, the control gates inserted in the tree construction is very likely to cause cell overlap. Even though the overlap can be eventually removed in placement legalization, remarkable wirelength/power overhead is incurred. In this paper, we propose a gate planning technique which is integrated with a partition-based cell placer. During cell placement, the planning judiciously inserts clock gates based on power estimation. In addition, pseudo edges are inserted between clock gates and registers in order to reduce clock wirelength and enable long shut-off periods. At the end, when a relatively detailed placement is obtained, a post-processing is performed to degrade the inefficient clock gates to clock buffers. We compared our approach with recent previous works on ISCAS89 benchmark circuits. Our method reduces the clock tree wirelength and power by 22.06% and 40.80%, respectively, with a very limited increase on signal nets wirelength and power compared with the conventional (register-oblivious) placement. The results also indicate that our algorithm outperforms the clock-gating-oblivious placement [9] on power reduction and performance improvement.

Leakage power soars quickly as VLSI technology advance and supply voltage scaling, in the near future, it will exceed the dynamic power to become the main contributor of power dissipation. Previous methods on leakage power minimization always notice the negative effect of increasing the gate’s threshold voltage Vth, and the power reduction is obtained based on power and speed (or performance) tradeoff. However, increasing the gate’s Vth could be used to adjust the subtrees’ imbalance for a clock tree. In this paper, for a gated clock tree, we analyze the bottom up merging segment generation process and conclude the conditions for increasing the gate’s Vth. Our idea is trying to assign high Vthto the gates without total wirelength and performance overheads, and in some cases, it could even be used to get more balanced subtrees. Experimental results on a set of ISCAS89 benchmark circuits demonstrate that our algorithm could assign more than half of the gates with high Vth, the resultant leakage power reduction is more than 43% without any total wirelength and delay penalties.

Clock gating is one of the most effective techniques to reduce clock network power dissipation. Although it has already been studied considerably, most of the previous works are restricted to either logic level or clock routing stage. Due to the restriction, clock gating often meets the trouble of wirelength overhead and frequent control signal switching, both of which degrade its effectiveness. Furthermore, previous design flows which insert gate logics after placement introduce a lot of overlaps, especially when there are lots of gate logics inserted. In this work, we propose a new design flow for low power gated clock network construction, in order to minimize the clock wirelength and the activity of control signals, and to eliminate the overlaps incurred by the gate logics. Our method begins with a coarse placement followed by soft register clustering. Then, we perform clock tree topology construction and zero skew clock routing to further reduce the power and the clock skew. Last, the gated clock network is fed back to the placer for incremental placement. Experimental results on ISCAS89 benchmarks demonstrate that our method outperforms previous algorithm of activity aware register placement in clock wirelength and clock power reduction with signal nets wirelength and signal nets power increase within 5% and 3%, respectively

This paper proposes a novel stochastic method for analyzing the voltage drop variations of on-chip power grid networks, considering lognormal leakage current variations. The new method, calledStoEKS, applies Hermite polynomial chaos to represent the random variables in both power grid networks and input leakage currents. However, different from the existing orthogonal polynomial-based stochastic simulation method, extended Krylov subspace (EKS) method is employed to compute variational responses from the augmented matrices consisting of the coefficients of Hermite polynomials. Our contribution lies in the acceleration of the spectral stochastic method using the EKS method to fast solve the variational circuit equations for the first time. By using the reduction technique, the new method partially mitigates increased circuit-size problem associated with the augmented matrices from the Galerkin-based spectral stochastic method. Experimental results show that the proposed method is about two-order magnitude faster than the existing Hermite PC-based simulation method and many order of magnitudes faster than Monte Carlo methods with marginal errors. StoEKS is scalable for analyzing much larger circuits than the existing Hermit PC-based methods.

Multiple supply voltage (MSV) is one of the most effective schemes to achieve low power, but most works are based on logic level. A few recent works are based on physical level but all of them do not consider level converters which have an important effect in dual-vdd design. In this work we propose a logic and layout aware approach for voltage assignment and voltage island generation in placement process to minimize the number of level converters and to implement voltage islands with minimal overheads. Experimental results show that our approach uses much less level converters than the approach in (Bin Liu, 2006) (reduced by 59.50% on average) when achieving the same power savings. The approach is able to produce feasible placement with a small impact to traditional placement goals.

This paper proposes a fast and practical decoupling capacitor (decap) budgeting algorithm to optimize the power ground (P/G) network design. The new method adopts a modified random walk process to partition the circuit. Then, by utilizing the isolation property of decaps, this new method avoids solving the large nonlinear programming problem in traditional decap optimization process. Also, this method integrates leakage currents optimization algorithm using a refined leakage model. Experimental results demonstrate that our proposed method achieves approximate a 10times speed up over the heuristic method based on sensitivity and only about 6% decap area deviation from the optimal budget using the programming method.

This paper describes the stochastic model order reduction algorithm via stochastic Hermite polynomials from the practical implementation perspective. Comparing with existing work on stochastic interconnect analysis and parameterized model order reduction, we generalized the input variation representation using polynomial chaos (PC) to allow for accurate modeling of non-Gaussian input variations. We also explore the implicit system representation using sub-matrices and improved the efficiency for solving the linear equations utilizing block matrix structure of the augmented system. Experiments show that our algorithm matches with Monte Carlo methods very well while keeping the algorithm effective. And the PC representation of non-Gaussian variables gains more accuracy than Taylor representation used in previous work (Wang et al., 2004).

With the rapid development of semiconductor technology, the working frequency of chips increases dramatically. Thus simultaneous switching noise (SSN) must be considered for robust power/ground (P/G) network design. In this paper, we mainly focus on the SSN effects for P/G network optimization. We first point out the drawbacks of the P/G optimization process without considering the SSN, by analyzing the optimized P/G grids. Then we propose a random walk based technique to consider SSN by adding decoupling capacitor (decap) prior to the nonlinear optimization process. This additional decap allocation phase constructs good current return path for the switching current caused by clock buffers and then reduces the dynamic voltage drop. Experiment results show that the proposed method achieves 2X speed up over the original approach without adding decaps in advance while the decap budget overhead is acceptable.

This paper studies the impacts of dummy fill for chemical mechanical polishing (CMP)-induced capacitance variation on buffer insertion during routing. Compared with existing methods, our algorithm is more feasible by performing buffer insertion not in post-process but during routing. Our contributions are threefold. First, we introduce a fast dummy fill estimation algorithm based on [4], which is better than traditional linear programming (LP) algorithm and suitable for early estimation. Second, based on some reasonable assumptions, we present an optimum virtual dummy fill method to estimate dummy position and the effects on the interconnect capacitance. Third, further analysis shows that the influences on the intermediate layer are more than that on the global layer, and as the required metal layer density increases the influences become more serious. Experiments gave the similar results and verified the necessity of early dummy fill estimation. Our dummy fill aware buffer insertion during early routing is promising and necessary.

Yield driven skew scheduling method leads to a clock tree with much greater wire length and buffer number that is not acceptable by designer. Geometry based register position relationships are converted to skew constraints and are combined with timing constraints harmoniously. With the two kinds of skew constraints together, our algorithm solves the skew scheduling problem for both restrictions and gives safety margins for not only timing variations but clocktree wire variations. It makes the yield driven clock network realizable inpractical design. Experimental results show that our algorithm has 72.7% yield improvement then normal scheduling. In addition, the clock tree wire length and buffer number are reduced by 52.2% and 40.4% compared with previous yielddriven skew scheduling method.

We present new timing and congestion driven FPGA placement algorithms with minimal runtime overhead. By predicting the post-routing critical edges and estimating congestion accurately, our algorithms simultaneously reduce the critical path delay and the minimum number of routing tracks. The core of our algorithm consists of a criticality history record of connection edges and a congestion map. This approach is applied to the 20 largest MCNC benchmark circuits. Experimental results show that compared with VPR [1], our algorithms yield an average of 8.1% reduction (maximum 30.5%) in the critical path delay and 5% reduction in channel width. Meanwhile, the average runtime of our algorithms is only 2.3X as of VPR's.

In this paper, we propose a novel stochastic method for analyzing the voltage drop variations of on-chip power grid networks with log-normal leakage current variations. The new-method, called StoEKS, applies Hermite polynomial chaos (PC) to represent the random variables in both power grid networks and input leakage currents. But different from the existing Hermit PC based stochastic simulation method, extended Krylov subspace method (EKS) is employed to compute variational responses using the augmented matrices consisting of the coefficients of Hermite polynomials. Our contribution lies in the combination of the statistical spectrum method with the extended Krylov subspace method to fast solve the variational circuit equations for the first time. Experimental results show that the proposed method is about two-order magnitude faster than the existing Hermite PC based simulation method and more order of magnitudes faster than Monte Carlo methods with marginal errors. StoEKS also can analyze much larger circuits than the exiting Hermit PC based methods.

Minimization of clock network is traditionally achieved by clock routing, which may be helpless for a poor placement result. In this paper, a novel Dynamic Clock-Tree Building technique integrated into placement for zero-skew design is proposed. This method combines a pre-designed clock-tree with the Force-Directed Placement procedure to navigate the register placement for minimizing the clock network. Meanwhile, a new model of Multi-Level Bounding Box and technique of Multi-Level Attractive Force are proposed to give a better local distribution of registers. Experiments on several standard-cell benchmarks indicate an average 26.1% clock network reduction with the logic cell placement preserved well.

Iterative slack distribution is a prevalent method in timing analysis and clock scheduling. Finding minimum mean cycle is the most time consuming step in the each iterative process. We present a practical strategy that can speed up the loop. A fast negative cycle detection method is used for examining whether the cycle of length two is really the minimum mean cycle. Traditional complicated minimum mean cycle algorithm can be skipped during the iterative slack distribution process. Experimental results show that our method can reduce running time of the iterative slack distribution process. The percentages are from 47% to 90% for different benchmark circuits.

In this paper, we present a novel pattern-based method to simulate large-scaled power/ground (P/G) grids. This method takes advantage of both traditional direct simulation methods and iterative simulation methods. The new method explores the geometry characteristics of regular P/G grids and translates topology similarity to submatrix regularity, which is called “pattern” in this paper. Such pattern structures can reduce the memory usage dramatically. Further, a new type of preconditioner is constructed to optimize the simulation process. Experimental results show that the proposed approach is about 5$\times$faster than the previous iterative methods with much lower memory, and is superior to the macro model-based hierarchical method on the tested large cases with pattern structures.

In this paper we propose a method for standard cell placement with support for dual supply voltages, aiming to reduce total power under timing constraints and to implement voltage islands with minimal overheads. The method begins with timing and power driven coarse placement, followed by a few iterations between voltage assignment and placement refinement to generate voltage islands. Several techniques, including timing and power driven net weighting, seed growth based voltage assignment, and soft clustering strategy for placement refinements are employed in our implementation. Experimental results on a set of MCNC benchmarks show that our approach is able to produce feasible placement for dual-Vdd designs and significantly reduce total power with a wirelength increase within 14% compared to a power and timing driven placer without voltage islands.

In this paper, we study the relationship between C4 package resonance effects and logical switching timing correlations, which has not been thoroughly investigated in the past. We show that improper logic designs with some special timing correlations can lead to adverse large voltage drops, which are due to resonance effects in the widely used C4 package. We first present the numerical analysis results on industry C4 package circuits to demonstrate resonance phenomenon. Then we propose a simple algorithm to compute the worst-case logical timing correlations among cells leading to resonance. Finally, we develop an efficient technique in early logic design stage to estimate the resonance risk. Experiment results demonstrate the effectiveness of the proposed method for the accurate prediction of the resonance effect in C4 package.

In current manufacturing processes, certain layout configurations are likely to have reduced yield and/or reliability due to increased susceptibility to stress effects or poor tolerance to certain processes like lithography. These problematic layout configurations need to be efficiently detected and eliminated from a design layout to enable better yield. In this paper, such layout configurations are called processhotspots and an efficient and scalable algorithm is proposed to detect such process-hotspots in a given layout.

Increasing buffer number for future technology makes traditional one-pass-flow (timing driven placement is followed by buffer insertion and legalization) failed, since accommodation for buffers significantly disturbs original design. This paper exploits the delicate relationship between buffer insertion and timing driven placement, and proposes a novel method to incorporate buffer insertion during timing driven placement. Experimental results show that this incorporation not only ensures design convergence, but also benefits timing behavior and alleviates buffer explosion

As a promising approach to mitigate the challenge of interconnect limit, X-architecture allows routings along diagonal directions in addition to rectilinear directions. It can reduce routing wire length and vias number compared with conventional Manhattan routing. Although Steiner minimum tree and signal routing algorithms have been developed for X-architecture, clock routing has not been addressed to the best of our knowledge. However, wire length reduction is even more compelling for clock net, as wire is a major power consumer and power supply noise generator. In addition, X-architecture is very effective for interconnect delay and clock skew optimization. In this paper, we investigate the layout embedding technique for clock routing in X-architecture and integrate it with the deferred-merge embedding (DME) algorithm. To alleviate the inaccuracy of the Elmore delay (ED) model, a more accurate fitted Elmore delay (FED) model is employed. Experimental results on benchmarks exhibit encouraging results.

Power dissipation problem becomes a dominant factor in the state-of-the-art IC design. Not only transistor but also interconnect should be taken into consideration in power calculation. In this paper, we use accurate delay and power models to construct buffered routing trees with considerations of delay and power optimization. Experimental results show our method can save much of buffer and power dissipation with better solutions

This paper presents a novel W-shape multilevel full-chip routing framework. The framework features the W-shape optimization flow. The first V-shape flow aims to optimize the global routing solution. And the second V-shape flow intends to improve the quality of the detailed routing result. The framework is tested on a set of commonly used benchmark circuits and compared with the previous multilevel routing systems. The experimental results are promising.

The optimization of virtual supply network plays an important role in MTCMOS low power design. Existing low power works are mainly on gate-level without any optimization on physical design level, which can lead to large amount of virtual supply networks. This paper presents (1) a low power driven physical design flow; (2) a novel low power placement to simultaneously place standard cells and sleep transistors and (3) sleep transistor relocation technique to further reduce the virtual supply networks. Experiment results are promising for both achieving up to 28.15% savings for virtual supply networks and well controlling the increase of signal nets

In this paper, we propose more accurate power/ground network circuit model, which consider both via and ground bounce effects to improve the performance estimation accuracy of on-chip power distribution networks. On top of this, a new precondition iterative method, which exploits geometry characters of power/ground networks, is developed to reduce memory usage and speed up the simulation. Experimental results show that the proposed method is about 5X faster than the incomplete LU decomposition (ILU) based preconditioned conjugate gradient iterative method and about half memory usage for simulating multi-layers large scale power/ground networks.

This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's very large scale integration physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But several new techniques that significantly improve the efficiency of the optimization process were adopted. First, an efficient search step scheme to replace the time-consuming line search phase in the conventional CG method for decap budget optimization was proposed. Second, instead of optimizing an entire large circuit, the circuit is partitioned into a number of smaller subcircuits and optimized separately by exploiting the locality of adding decaps. Third, the time-domain merged adjoint method was applied to compute the sensitivity information and show that the partitioning-based merged adjoint method leads to better results than the flat merged adjoint method with the improved search scheme. Experimental results show that the proposed algorithm achieves at least ten times speed-up over similar decap allocation methods reported so far with similar budget quality, and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations

This paper proposes a novel hierarchical approach to the efficient analysis of large VLSI power/ground grids. Different from the existing hierarchical approach where sub-circuit equivalent models are sparsified with computation-intensive integer programming and the resulting modeling may lead to larger errors if the top circuit matrix has large condition number, the new approach employs an iterative (relaxation) procedure to explicitly compensate the errors and avoid introducing dense matrix caused by the circuit reduction. We also propose an efficient scheme for partitioning high performance center-bumped P/G grids. Experimental results demonstrate that the new algorithm is more accurate than the existing hierarchical method while delivering more speedup over the flat simulators.

In today's power/ground(P/G) network design, on-chip decoupling capacitors(decaps) are usually made of MOS transistors with source and drain connected together. The gate leakage current becomes worse as the gate oxide layer thickness continues to shrink below 20Å. As a result, decaps will become leaky due to the gate leakage from CMOS devices. In this paper, we take a first look at the leaky decaps in P/G network optimization. We propose a leakage current model for practical decaps and also present a new two-stage leakage-current-aware approach to efficiently optimize P/G networks in a more area efficient way.

In ultra-deep submicron VLSI circuits, clock network is a major source of power consumption and power supply noise. Therefore, it is very important to minimize clock network size. Traditional design methodologies usually let the clock router to undertake the task of clock network minimization independently. Since a clock routing is carried out based on register locations, register placement actually has fundamental influence to a clock network size. In this paper, we propose a new clock network design methodology that Incorporates register placement optimization. Given a cell placement result, incremental modifications are performed according to clock skew specifications. The incremental placement change moves registers toward preferred locations that may enable a small clock network size. At the same time, the side-effect to logic cell placement and wire connections is controlled. Experimental results on benchmark circuits show that the proposed methodology can reduce clock network size considerably with limited impact on signal net wirelength and critical path delay.

In modern VLSI designs, the increasingly severe power problem requests to minimize clock routing wirelength so that both power consumption and power supply noise can be alleviated. In contrast to most of traditional works that handle this problem only in clock routing, we propose to navigate standard cell register placement to locations that enable further less clock routing wirelength and power. To minimize adverse impacts to conventional cell placement goals such as signal net wirelength and critical path delay, the register placement is carried out in the context of a quadratic placement. The proposed technique is particularly effective for the recently popular prescribed skew clock routing. Experiments on benchmark circuits show encouraging results.

This paper presents a novel approach for fast transient analysis of buffered hybrid structured clock networks. The new method applies structure reduction and relaxed hierarchical analysis methods to reduce the circuit complexity and speedup the simulation. A simple controlled sources model is used for modeling clock buffers to deal with nonlinearity in the buffered clock trees. Our experiment results show that the proposed algorithm is about two orders of magnitude faster than HSPICE without loss on accuracy and stability. The relatively errors on delay times are within a few percent of the exact ones.

This paper proposes a fast decoupling capacitance (decap) allocation and budgeting algorithm for both early stage decap estimation and later stage decap minimization in today's VLSI physical design. The new method is based on a sensitivity-based conjugate gradient (CG) approach. But it adopts several new techniques, which significantly improve the efficiency of the optimization process. First, the new approach applies the time-domain merged adjoint network method for fast sensitivity calculation. Second, an efficient search step scheme is proposed to replace the timeconsuming line search phase in conventional conjugate gradient method for decap budget optimization. Third, instead of optimizing an entire large circuit, we partition the circuit into a number of smaller sub-circuits and optimize them separately by exploiting the locality of adding decaps. Experimental results show that the proposed algorithm achieves at least 10X speed-up over the fastest decap allocation method reported so far with similar or even better budget quality and a power grid circuit with about one million nodes can be optimized using the new method in half an hour on the latest Linux workstations.

The progress of VLSI technology is facing two limiting factors: power and variation. Minimizing clock network size can lead to reduced power consumption, less power supply noise, less number of clock buffers and therefore less vulnerability to variations. Previous works on clock network minimization are mostly focused on clock routing and the improvements are often limited by the input register placement. In this work, we propose to navigate registers in cell placement for further clock network size reduction. To solve the conflict between clock network minimization and traditional placement goals, we suggest the following techniques in a quadratic placement framework: (1) Manhattan ring based register guidance; (2) center of gravity constraints for registers; (3) pseudo pin and net; (4) register cluster contraction. These techniques work for both zero skew and prescribed skew designs in both wirelength driven and timing driven placement. Experimental results show that our method can reduce clock net wirelength by 16%~33% with no more than 0.5% increase on signal net wirelength compared with conventional approaches.

A new methodology is proposed to accelerate AltPSM design flow for dark field AltPSM for large-scale layouts. When scaling to large-scale layouts, designing AltPSM may be much time consuming. Our new algorithm solves this problem by splitting a layout into smaller, easier-to-solve parts, solving the sub-layouts independently and simultaneously, and then recombining the sub-layouts. The experimental results on industry layouts indicate that parallel algorithm has potential to provide more significant improvement in speed and achieve a better quality of solutions.

This paper presents an improved multilevel Full-chip routing system which integrates global routing and detailed routing algorithms to achieve great enhancement in yield and reliability considering the redundant via placement. The system features a pre-coarsening stage which is equipped with a fast congestion-driven L-pattern global routing followed by the rvia-driven detailed routing. The L-pattern global routing benefits a lot to the reduction of vias and thus relieves the burden of redundant via addition. Then the rvia-driven maze routing algorithm considers the addition of redundant vias during routing. Finally the redundant via placement heuristic also contributes to improve the completion rate. We have tested the system on a set of commonly used benchmark circuits and compared the results with a previous multilevel routing framework. The experimental results are promising.

This paper presents a novel approach to reducing the complexity of the transient linear circuit analysis for a hybrid structured clock network. Topology reduction is first used to reduce the complexity of the circuits and a preconditioned Krylov-subspace iterative method is then used to perform the nodal analysis on the reduced circuits. By proper choice of the simulation time step based on Elmore delay model, the delay of the clock signal between the clock source and the sink node and the skews between the sink nodes can be obtained efficiently and accurately. Our experimental results show that the proposed algorithm is two orders of magnitude faster than HSPICE without loss of accuracy and stability and the maximum error is within 0.4% of the exact delay time.

This paper deals with area minimization of power network for very large-scale integration designs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. During the optimization, a penalty method, conjugate gradient method, circuit sensitivity analysis, and merging adjoint networks are applied, which enables the algorithm to optimize large circuits. The experiment results prove that this algorithm is robust and can achieve the objective of minimizing the area of power network in a short runtime.

Corner Block List (CBL) was recently proposed as an efficient representation for MOSAIC packing of rectangles. Although the original method is really innovative, there still remains room for improvement for our purpose. This article proposes a compact algorithm for placement based on corner block list. By introducing the dummy blocks in CBL, our algorithm can intellectively employ dummy blocks in the packing to represent the placement including empty rooms, which corner block list cannot represent. Our algorithm can obtain the fast convergence to an optimal solution. Based on the compact approach, we propose a new way to handle arbitrary shaped rectilinear modules. The experimental results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper studies the buffer planning problem for interconnect-centric floorplanning for nanometer technologies. The dead-spaces are the spaces within a placement that are not held by any circuit block. In this paper, we proposed a buffer planning algorithm based on dead space redistribution to make good use of dead-spaces for buffer insertion. Associated with circuit blocks under topological representations, the dead space can be redistributed by freely moving some circuit blocks within their rooms in the placement. The total area and the topology of the placement keep unchanged while doing the dead space redistribution. The number of nets satisfying the delay constraint can be increased by redistributing the dead space all over the placement, which has been demonstrated by the experimental results. The increment of the number of nets that satisfy delay constraints is 9% on an average.

This paper presents a path-based timing-driven quadratic placement algorithm. The delay of the path acts as the timing constraints. In the global optimization step, it tries to satisfy the timing constraints. In the partition step, it tries to decrease the cut number of critical paths. It has some special skills, such as decrease the delay on the longest path, pad assign, to decrease the delay further. Results show this algorithm can make the timing behavior improve more than 20%.

Timing performance and routability are two main issues of global routing. In this paper, we adopt a shadow price mechanism to incorporate the two issues into one unified objective function. The shadow price of a net is the sum of its congestion price and timing price. Based on the new formulation, this paper presents the UTACO algorithm for standard cell (SC) global routing. The experimental results show that UTACO is efficient for both timing and congestion optimization.

As the CMOS technology enters the very deep submicron era, inter-wire coupling capacitance becomes the dominant part of load capacitance. The coupling effects have brought new challenges to routing algorithms on both delay estimation and optimization. In this paper, we propose a timing-driven global routing algorithm with consideration of coupling effects. The two-phase algorithm based on a timing-relax method includes a heuristic Steiner tree algorithm and an optimization algorithm. Experimental results are given to demonstrate the efficiency and accuracy of the algorithm.

By dividing the packing area into routing tiles, we can give the budget of the buffer insertion. And the detail locating of the blocks in their rooms can be implemented for each iterations during the annealing process to favor the later buffer planning. The buffer insertion will affect the possible routes as well the congestion of the packing. The congestion estimation in this paper takes the buffer insertion into account. So we devise a buffer planning algorithm to allocate the buffer into tiles with congestion information considered. The buffer allocation problem is formulated into a net flow problem and the buffer allocation can be handled as an integral part in the floorplanning process. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better performance and chip area.

Previous works on buffer planning are mainly based on fixed die placement. It is necessary to reduce the complexity of computing the feasible buffer insertion sites to integrate the buffer planning with the floorplanning process. In this paper, we give an efficient buffer planning algorithm with linear complexity by computing all the feasible buffer insertion sites in a 2-step method. By partitioning all the dead spaces into blocks while doing the packing, the buffer allocation can be handled as an integral part in the floorplanning process. Our method is based on a simulated annealing approach which is divided into two phases: timing optimization phase and buffer insertion phase. Since there is more freedom for floorplan optimization, the floorplanning algorithm integrated with buffer planning can result in better time performance and chip area.

The timing behavior and congestion behavior are two important goals in the performance-driven standard-cell placement. In this paper, we analyze the relationship between the timing and congestion behavior. We bring up a multi-step placement algorithm to reach the two goals. First, the timing-driven placement algorithm is used to find the global optimal solution. In the second step, the algorithm tries to decrease the maximum congestion while not deteriorating the timing behavior. We have implemented our algorithm and tested it with real circuits. The results show that the maximum delay can decrease by 30% in our timing-driven placement and in the second step the maximum congestion will decrease by 10% while the timing behavior is unchanged.

In this paper, we describe a new congestion-driven placement based on cell inflation. In our approach, we have used the method of probability- estimation to evaluate the routing of nets. We also take use of the strategy of cell inflation to eliminate the routing congestion. Further reduction in congestion is obtained by the scheme of cell moving. We have tested our algorithm on a set of sample circuits from American industry and the results obtained have shown great improvement of routability.

In floorplanning of typical VLSI design, some modules are required to satisfy some placement constraints in the final packing. Boudary Constraint is one kind of those placement constraints to pack some modules along one of the four sides: on the left, on the right, at the bottom or at the top of the final floorplan. We implement the boundary constraint algorithm for general floorplan by extending the Corner Block List (CBL) - a new efficient topology representation for non-slicing floorplan. Our contribution is to find the necessary and sufficient characterization of the modules along the boundary represented by Corner Block List. So that we can check the boundary constraints by scanning the intermediate solutions in the linear time during the simulated annealing process and fix the corner block list in case the constraints are violated. The experiment results are demonstrated by several examples of MCNC benchmarks and the performance is remarkable.

The abutment constraint problem is one of the common constraints in practice to favor the transmission of data between blocks. Based on Corner Block List(CBL), a new algorithm to deal with abutment constraints is developed in this paper. We can obtain the abutment information by scanning the intermediate solutions represented by CBL in linear time during the simulated annealing process and fix the CBL in case the constraints are violated. Based on this algorithm, a new method to deal with L-shaped/T-shaped blocks is proposed. The shape flexibility of the soft blocks and the rotation and reflection of L-shaped/T-shaped blocks are exploited to obtain a tight packing. The experiment results are demonstrated by some benchmark data and the performance shows effectiveness of the proposed method.

This paper deals with area minimization of power distribution networks for VLSIs. A new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. Experimental results prove that this algorithm has achieved the objectives of minimizing the area of power/ground networks with higher speeds.

Article Free Access Share on Area routing oriented hierarchical corner stitching with partial bin Authors: Zhang Yan Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Wang Baohua Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Cai Yici Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Hong Xianlong Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000Pages 105–110https://doi.org/10.1145/368434.368587Published:28 January 2000Publication History 0citation220DownloadsMetricsTotal Citations0Total Downloads220Last 12 Months45Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on MMP: a novel placement algorithm for combined macro block and standard cell layout design Authors: Hong Yu Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Xianlong Hong Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile , Yici Cai Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. China Department of Computer Science and Technology, Tsinghua University, Beijing 100084, P.R. ChinaView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 271–276https://doi.org/10.1145/368434.368632Online:28 January 2000Publication History 16citation61DownloadsMetricsTotal Citations16Total Downloads61Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper, a corner block list-a new efficient topological representation for non-slicing floorplan is proposed with applications to VLSI floorplan and building block placement. Given a corner block list, it takes only linear time to construct the floorplan. Unlike the O-tree structure, which determines the exact floorplan based on given block sizes, corner block list defines the floorplan independent of the block sizes. Thus, the structure is better suited for floorplan optimization with various size configurations of each block. Based on this new structure and the simulated annealing technique, an efficient floorplan algorithm is given. Soft blocks and the aspect ratio of the chip are taken into account in the simulated annealing process. The experimental results demonstrate the algorithm is quite promising.

We proposed a new global routing algorithm solving the net ordering problem. The algorithm uses random optimization methods to keep the equality of earlier routed nets and later routed nets in passing congested areas. It can find a solution independent of net ordering in short time. A global router is implemented in this method. Experiments show that the router performs much faster than Matula router while obtaining solutions with approximate quality.

In this paper, an effective timing-driven building block placer is proposed. Interconnection delay is modeled and included during the placing process in order to minimize the area and wirelength, as well as to satisfy the timing constraints in the algorithm. The simulated annealing technique for constrained optimization problem and the sequence pair model proposed by H. Murata et al. (1996) are applied. Not only the timing constraint but also the aspect ratio is taken into account in the search process. The experimental results demonstrate the algorithm can improve the timing delay and obtain good placement.