The increasing integration of renewable and distributed energy resources into the power grid makes Electromagnetic Transient (EMT) simulation more critical for ensuring grid stability. Efficient numerical solvers are crucial for the computationally intensive task of simulating electrical distribution networks (EDN). This paper presents an FPGA-based accelerator for solving the linear system derived from EMT simulation of EDNs. It features a reconfigurable datapath that can exploit parallelism in handling dynamic matrix shapes during runtime. FPGA prototyping shows significant speedup over prior works with reduced logic resource usage.

In this paper, a novel system utilizing a hybrid relay-intelligent reflecting surface (HR-IRS) to boost the security performance of directional modulation (DM) is established. In particular, the malicious attacker works in full-duplex (FD) mode and it will eavesdrop on confidential message (CM) as well as send malicious jamming. To maximize the secrecy rate (SR), a joint problem of optimizing the receive beamforming, transmit beamforming, power allocation (PA) factor, and phase shift matrix (PSM) of HR-IRS is formulated. Since the optimization problem is un-convex and the variables are coupled with each other, we address this problem by iteratively optimizing these variables. First, the receive beamforming is designed based on the generalized Rayleigh-Ritz theorem. Then, the transmit beamforming and PA factor are optimized via Dinkelbach’s Transform and successive convex approximation methods. And for PSM, two strategies, called separate optimization of PSM (SO-PSM) and joint optimization of PSM (JO-PSM), are proposed. Thus, two iterative schemes are proposed accordingly, namely maximizing SR based on SO-PSM (Max-SR-SOP) and maximizing SR based on JO-PSM (Max-SR-JOP). The former has a better performance and the latter has a lower complexity. Simulation results show that given a sufficient power budget of HR-IRS, the proposed Max-SR-SOP and Max-SR-JOP can enable HR-IRS-aided DM network to obtain a higher SR than that aided by passive IRS.

As an emerging technology for wireless communication, the intelligent reconfigurable surface (IRS) is made up of numerous low-cost passive elements with reconfigurable parameters, which can reflect signals with a certain phase shift and build a programmable communication environment. To reduce the high hardware cost and energy consumption in spatial modulation (SM), an IRS-aided hybrid secure SM (SSM) system with a hybrid precoder is proposed in this paper, where an optimization problem is formulated to maximize the secrecy rate (SR) by jointly optimizing the beamforming at IRS and the hybrid precoding at transmitter. For the IRS beamforming, an alternating direction method of multipliers (IRS-ADMM) scheme is first proposed. To achieve a higher SR, an IRS beamforming scheme via semidefinite relaxation (IRS-SDR) is put forward. To reduce the high complexity of IRS-SDR, we design a block coordinate ascend-based IRS beamforming scheme (IRS-BCA) with a closed-form solution. As for the hybrid precoding, two methods, called a successive convex approximation method based on the approximate secrecy rate (ASR-SCA) and a gradient ascend method based on cut-off rate (COR-GA), are presented. Simulation results show that the proposed IRS-ADMM and IRS-SDR harvest substantial SR performance gains over IRS-BCA. In comparison to the IRS-ADMM and IRS-SDR, the proposed IRS-BCA is of the lowest complexity at the cost of performance loss. Regarding hybrid precoding, the proposed ASR-SCA outperforms COR-GA in the high transmit power region. According to the complexity and SR performance of six combination methods including each IRS beamforming method and each hybrid precoding method, we selected three combinations: IRS-BCA plus ASR-SCA, IRS-ADMM plus ASR-SCA and IRS-SDR plus COR-GA. Moreover, it is showed that the SR performance achieved by the three combination methods is significantly higher than those of IRS with random beamforming and without IRS.

The use of a reconfigurable intelligent surface (RIS) in the enhancement of the rate performance is considered to involve the limitation of the RIS being a passive reflector. To address this issue, we propose a RIS-aided amplify-and-forward (AF) relay network in this paper. By jointly optimizing the beamforming matrix at AF relay and the phase-shift matrices at RIS, two schemes are put forward to address a maximizing signal-to-noise ratio (SNR) problem. First, aiming at achieving a high rate, a high-performance alternating optimization (AO) method based on Charnes–Cooper transformation and semidefinite programming (CCT-SDP) is proposed, where the optimization problem is decomposed into three subproblems solved using CCT-SDP, and rank-one solutions can be recovered using Gaussian randomization. However, the optimization variables in the CCT-SDP method are matrices, leading to extremely high complexity. To reduce the complexity, a low-complexity AO scheme based on Dinkelbachs transformation and successive convex approximation (DT-SCA) is proposed, where the variables are represented in vector form, and the three decoupling subproblems are solved using DT-SCA. Simulation results verify that compared to three benchmarks (i.e., a RIS-assisted AF relay network with random phase, an AF relay network without RIS, and a RIS-aided network without AF relay), the proposed CCT-SDP and DT-SCA schemes can harvest better rate performance. Furthermore, it is revealed that the rate of the low-complexity DT-SCA method is close to that of the CCT-SDP method.

Reconfigurable intelligent surfaces (RISs) are envisioned to be a disruptive wireless communication technique that is capable of reconfiguring the wireless propagation environment. In this paper, we study a free-space RIS-assisted multiple-input single-output (MISO) communication system in far-field operation. To maximize the received power from the physical and electromagnetic nature point of view, a comprehensive optimization, including beamforming of the transmitter, phase shifts of the RIS, orientation and position of the RIS is formulated and addressed. After exploiting the property of line-of-sight (LoS) links, we derive closed-form solutions of beamforming and phase shifts. For the non-trivial RIS position optimization problem in arbitrary three-dimensional space, a dimensional-reducing theory is proved. The simulation results show that the proposed closed-form beamforming and phase shifts approach the upper bound of the received power. The robustness of our proposed solutions in terms of the perturbation is also verified. Moreover, the RIS significantly enhances the performance of the mmWave/THz communication system.

In this paper, we consider deploying an intelligent reflecting surface (IRS) to enhance the downlink (DL) energy transfer and uplink (UL) information transmission efficiency for secure multiple-input multiple-output (MIMO) wireless powered communication networks (WPCNs). We aim to maximize the secrecy throughput of all users by jointly optimizing the DL/UL time allocation, the energy transmit covariance matrix of hybrid access point (AP), the information transmit beamforming matrix of users and the phase shifts of IRS in DL/UL, subject to constraints of energy/information transmit power at the hybrid AP/users and that of unit-modulus IRS phase shifts for DL/UL. To tackle the non-convex problem, we first transform the original problem into an equivalent form based on the mean-square error (MSE) method given time allocation, and then apply the alternating algorithm to update the optimization variables iteratively. Specifically, the energy covariance matrix and the information beamforming matrix are obtained based on the dual subgradient method. For the IRS phase shifts, we investigate two IRS beamforming reflection setups, namely different DL/UL IRS beamforming and identical DL/UL IRS beamforming. For the former case, the second-order cone programming technique and the Majorization-Minimization algorithm/element by element iterative algorithm are applied to obtain the DL and UL IRS phase shifts, respectively. For the latter case, the IRS phase shifts are obtained by the successive convex approximation technique. To further reduce the computational complexity of the single-user system, we derive the closed-form solutions of IRS phase shifts in each iteration for the two different reflection setups. Simulation results show that all the proposed algorithms can greatly improve the secrecy throughput compared to the conventional system without IRS.

Intelligent reflecting surface (IRS) is of low-cost and energy-efficiency and will be a promising technology for the future wireless communications like sixth generation. To address the problem of conventional directional modulation (DM) that Alice only transmits single confidential bit stream (CBS) to Bob with multiple antennas in a line-of-sight channel, IRS is proposed to create friendly multipaths for DM such that two CBSs can be transmitted from Alice to Bob. This will significantly enhance the secrecy rate (SR) of DM. To maximize the SR (Max-SR), a general non-convex optimization problem is formulated with the unit-modulus constraint of IRS phase-shift matrix (PSM), and the general alternating iterative (GAI) algorithm is proposed to jointly obtain the transmit beamforming vectors (TBVs) and PSM by alternately optimizing one and fixing another. To reduce its high complexity, a low-complexity iterative algorithm for Max-SR is proposed by placing the constraint of null-space (NS) on the TBVs, called NS projection (NSP). Here, each CBS is transmitted separately in the NSs of other CBS and AN channels. Simulation results show that the SRs of the proposed GAI and NSP can approximately double that of IRS-based DM with single CBS for massive IRS in the high signal-to-noise ratio region.

MOTIVATION: Small P-values are often required to be accurately estimated in large-scale genomic studies for the adjustment of multiple hypothesis tests and the ranking of genomic features based on their statistical significance. For those complicated test statistics whose cumulative distribution functions are analytically intractable, existing methods usually do not work well with small P-values due to lack of accuracy or computational restrictions. We propose a general approach for accurately and efficiently estimating small P-values for a broad range of complicated test statistics based on the principle of the cross-entropy method and Markov chain Monte Carlo sampling techniques. RESULTS: We evaluate the performance of the proposed algorithm through simulations and demonstrate its application to three real-world examples in genomic studies. The results show that our approach can accurately evaluate small to extremely small P-values (e.g. 10-6 to 10-100). The proposed algorithm is helpful for the improvement of some existing test procedures and the development of new test procedures in genomic studies. AVAILABILITY AND IMPLEMENTATION: R programs for implementing the algorithm and reproducing the results are available at: https://github.com/shilab2017/MCMC-CE-codes. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

3-D held solvers have become popular tools for parasitic capacitance extraction of full custom circuits, IPs, and packages. Traditional held solvers based on hnite difference method/hnite element method/floating random walk truncate the held on the outer boundary of the numerical region by applying Dirichlet or Neumann boundary conditions. However, to ensure high accuracy in the vicinity of circuit elements, a substantial gridded region between the circuit and the outer boundary is necessary in order to reduce distortion of the held caused by these truncation conditions. In this paper, we make a fundamental contribution to the application of numerical held solvers by proposing a class of absorbing boundary conditions, which when implemented, signihcantly reduce the distortion of the held at the numerical boundary, and consequently, throughout the numerical region. The absorbing boundary condition we propose will allow the held throughout the numerical region to behave as though there is no numerical boundary, accurately mimicking the helds in an actual circuit. As a result, the size of the numerical region can be signihcantly reduced, which in turn reduces the run time without sacrihcing accuracy. A mathematical development of the proposed absorbing boundary condition is presented. It is shown that the error of the proposed nth order absorbing boundary is O(1/rn+2), while the error of the traditional Neumann boundary is O(1/r2), where r is the size of the numerical region. Experimental results for capacitance extraction with interconnects in multilayer dielectrics and silicon on insulator show the proposed methods improve the run time and accuracy of numerical solutions of Laplace's equation over previous boundary conditions for uniform or nonuniform meshes.

This paper presents a fast compressive sensing reconstruction algorithm implemented on FPGA using Orthogonal Matching Pursuit (OMP). The algorithm is optimized with QR decomposition to solve the least square problem and avoids the square root operations to facilitate the hardware implementation. The implementation results show that this design can run at a frequency of 100MHz and the proposed algorithm achieves 50% lower complexity than the other existed algorithms.

High-speed I/O link plays an important role in modern computer systems. In order to accurately estimate a small BER value in the order of 10-12, a large number of bits need to be transmitted, which results in expensive testing cost. In this paper, we exploit the correlation between the performance of high-speed I/O link under different corners/configurations to improve the accuracy of the estimated BER. A graphical generative model is used to represent the underlying correlations. This template provides a way to share information between different models, hence increases the modeling accuracy. Experimental results show that our method achieves up to 2x speed-up over the traditional method.

In order to perform accurate parasitic extraction, foundries must provide the cross section profile of devices, and IP vendors must provide sufficient layout information. However, foundries and IP vendors are increasingly reluctant to reveal such sensitive information, especially for advanced devices. Therefore, the industry is faced with the following challenges: 1) foundries/IP vendors need to protect their trade secrets; 2) electronic design automation vendors need to integrate foundry data into extraction tools; and 3) IC designers need to have the accurate parasitic data. In this paper, we propose an innovative and practical solution to these challenges, by building a macro model around any region in 2-D/3-D on a circuit where foundries or IP vendors wish to hide information, yet the macro model allows accurate capacitance extraction inside and outside of the region. We first give algorithms to construct the macro model. Then, we describe how existing extraction algorithms can interface with the macro model to perform extraction for the entire circuit at the same accuracy as if complete information was given. The macro model can be used in finite difference method/finite element method and floating random walk, due to an equivalence theorem we proved. Finally, we propose the concept of equivalent profile and describe how to find one based on the macro model. Experimental results show the macro model can be efficiently constructed and used to produce accurate capacitance extraction.

Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple$O(mn)$time algorithm for optimal buffer insertion, where$m$is the number of sinks and$n$is the number of buffer positions. When$m$is small, our algorithm is a significant improvement over the recent$O(n\log^{2}n)$time algorithm by Shi and Li, and the$O(n^{2})$time algorithm of van Ginneken. For$b$buffer types, our algorithms runs in$O(b^{2}n+bmn)$time, an improvement of the recent$O(bn^{2})$algorithm by Li and Shi. The improvement is made possible by an innovative linked list that can perform addition of a wire, addition of a buffer in amortized$O(1)$time, and smart design of pointers. We then present the extension of our algorithm for the buffer cost minimization problem, which improves the previous best algorithm. On industrial test cases, the new algorithms is faster than previous best algorithms by an order of magnitude.

In a typical circuit optimization flow, one essential decision is to select the implementation for each gate according to a cell library. An implementation implies specific gate size, threshold voltage, etc. The selection normally needs to handle multiple and often conflicting objectives. An effective approach for multi-objective optimization is Lagrangian relaxation (LR), which has been adopted in continuous gate sizing. When LR is applied to the gate implementation selection, the Lagrangian dual problem is no longer convex like in continuous gate sizing, and conventional sub-gradient method becomes inefficient. In this paper, we propose a projection-based descent method and a new technique of Lagrangian multiplier distribution for solving the Lagrangian dual problem in discrete space. Experimental results demonstrate that our approach leads to significantly better solution quality and faster convergence compared to the sub-gradient method.

In a complete physical synthesis flow, optimization transforms, that can improve the timing on critical paths that are already well-optimized by a series of powerful transforms (timing driven placement, buffering and gate sizing) are invaluable. Finding such a transform is quite challenging, to say nothing of efficiency. This work explores innovative cloning (gate duplication) techniques to improve timing-closure in a physical synthesis environment.

The existence of nonlinear magnetic materials poses a challenge to the interconnect inductance extraction for circuits in micromotors, radio-frequency identification, and magnetoresistive random access memory. In this paper, we present a fast algorithm to extract inductance in the presence of nonlinear magnetic materials. The new algorithm models the nonlinear magnetic characteristics by solving the Landau-Lifshitz-Gilbert equation, and the nonhomogeneous magnetic characteristics by introducing a fictitious magnetic charge. To speed up the algorithm, we apply a number of innovative techniques, including the approximation of magnetic charge effect and the modeling of currents with solenoidal basis. Experimental results demonstrate the accuracy and efficiency of the new algorithm. Its relative error with respect to the commercial tool is below 3%, while its speed is up to one magnitude faster.

Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider individual nets and therefore often result in high buffer cost due to lack a global view. Thus, circuit-wise buffering is necessary to reduce buffer cost. Recently, some circuit-wise buffering algorithms are proposed. However, these algorithms are based on heuristics which are not scalable in handling large circuits.

We present a novel power-aware yield enhancement design methodology and reconfiguration scheme for deep submicron SRAM designs. We show that with the continued trend of raising array supply to counter process variations, it is more effective to use a per-element selectable virtual power-supply scenario as opposed to single array supply with traditional redundancy schemes. The element can be a bank, a sub-array, or an independent row/column, and the element's virtual supply value is determined based on fail bitmaps. The technique can also be used in conjunction with traditional redundancy schemes to further improve the efficiency. The supply and redundancy assignments can be obtained by relying on memory reconfiguration algorithms. For this, we propose a greedy yet accurate algorithm that runs in O(nlogn) as opposed to average case O(n2) traditional algorithms. The methodology leads to significant power savings ranging from 20% to 50% for 65nm technology. We expect the savings to increase in future technologies as leakage powers dominate. To the best of our knowledge, this is the first time such a methodology is applied to SRAM designs.

Recently, microprocessor industry is headed in the direction of multi-core designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multi-core processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios. If the conventional buffer insertion is performed for each scenario separately, there may be different solutions corresponding to these scenarios. A naive approach is to select one scenario's solution that is most critical among all scenarios and apply it to all the scenarios. However, a good solution for one scenario maybe a poor one for another scenario. We propose algorithmic techniques for solving these multi-scenario buffer insertion problems. Compared to the naive approach, our algorithm can improve slack by 102ps on average for maxslack solutions. For min-cost solutions, our algorithm causes no timing violation while the naive approach results in 35% timing violations. Moreover, the computation speed of our algorithm is faster

Recently, the microprocessor industry is headed in the direction of multicore designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multicore processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios, since each core has its own parameters. If conventional buffer insertion is performed for each scenario separately, there may be a different solution corresponding to each of these scenarios. A straightforward approach is to judiciously select a solution from one scenario and apply it to all the scenarios. However, a good solution for one scenario may be a poor one for another. We propose several algorithmic techniques for solving these multiscenario buffer insertion problems. Compared with a straightforward extension of the conventional buffer insertion, our algorithm can improve slack by 20-280 ps for max-slack solutions. For min-cost solutions, our algorithm causes no timing violation, while the extended conventional buffering results in 35% timing violations. Moreover, the computation speed of our algorithm is faster.

This paper presents the first boundary element method (BEM) impedance extraction algorithm for interconnects with multiple dielectrics. Multiple dielectrics are common in integrated circuits and packages. However, previous BEM algorithms, including FastImp and FastPep, assume uniform dielectric due to their limitation, thus causing considerable errors. Our algorithm introduces a circuit formulation which makes it possible to utilize either multilayer Green's function or equivalent charge method to extract impedance in multiple dielectrics. The novelty of the formulation is the reduction of the unknowns and the application of hierarchical data structure. The hierarchical data structure permits efficient sparsification transformation and preconditioners to accelerate the linear equation solver. Experimental results demonstrate that the new algorithm is accurate and efficient. For uniform dielectric problems, our algorithm is more accurate than FastImp while its number of unknowns is ten times less than that of FastImp. For multiple dielectric problems, its relative error with respect to HFSS is below 3%.

Even with the wide adaptation of resolution enhancement techniques in sub-wavelength lithography, the geometry of the fabricated interconnect is still quite different from the drawn one. Existing layout parasitic extraction (LPE) tools assume perfect geometry, thus introducing significant error in the extracted parasitic models, which in turn cases significant error in timing verification and signal integrity analysis. Our simulation shows that the RC parasitics extracted from perfect GDS-II geometry can be as much as 20% different from those extracted from the post litho/etching simulation geometry. This paper presents a new LPE methodology and related fast algorithms for interconnect parasitic extraction under photolithographic effects. Our methodology is compatible with the existing design flow. Experimental results show that the proposed methods are accurate and efficient.

Twisted differential line structure can effectively reduce crosstalk noise on global bus, which foresees a wide applicability. However, measured performance based on fabricated circuits is much worse than simulated performance based on the layout. It is suspected that the via resistance variation is the cause.

In modern VLSI circuits, metal conductors are separated by multiple planar, conformal or embedded dielectric media. Previous algorithms based on Boundary Element Method (BEM) are inefficient to extract interconnect capacitance due to the complex dielectric structures. In this paper, we present a new algorithm that combines multilayer Green's function with the equivalent charge method to efficiently deal with the complex dielectrics. The multilayer Green's function is efficient to model layered dielectric media, while the equivalent charge method is powerful to model non-planar complex dielectric. Our method can also model ground plane and reflective boundary wall. From experimental results, the new method is significantly faster than previous methods in realistic conditions, i.e., 70X speedup and 99% memory saving compared with FastCap and 2X speedup and 80% memory saving compared with PHiCap for complex dielectric structure with similar accuracy.

In this paper, we present the first BEM impedance extraction algorithm for multiple dielectrics. The effect of multiple dielectrics is significant and efficient modeling is challenging. However, previous BEM algorithms, including Fastlmp and EastPep, assume uniform dielectric, thus causing considerable errors. The new algorithm introduces a circuit formulation which makes it possible to utilizes either multilayer Green's function or equivalent charge method to extract impedance in multiple dielectrics. The novelty of the formulation is the reduction of the number of unknowns and the application of the hierarchical data structure. The hierarchical data structure permits efficient sparsification transformation and preconditioners to accelerate the linear equation solver. Experimental results demonstrate that the new algorithm is accurate and efficient. For uniform dielectric problems, the new algorithm is one magnitude faster than Fastlmp, while its results differ from Fastlmp within 2%. For multiple dielectrics problems, its relative error with respect to HFSS is below 3%.

As a prevalent constraint, sharp slew rate is often required in circuit design, which causes a huge demand for buffering resources. This problem requires ultrafast buffering techniques to handle large volume of nets while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm using the maximum matching technique is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Fourth, buffer blockage avoidance is handled, which makes the algorithms ready for practical use. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve about 90x speedup and save up to 20% buffer area over the commonly used van Ginneken style buffering. The new algorithms also significantly outperform previous works that indirectly address the slew buffering problem.

Most existing methods for interconnect wire sizing are designed for RC trees. With the increasing popularity of the non-tree topology in clock networks and multiple link networks, wire sizing for non-tree networks becomes an important problem. In this paper, we propose the first systematic method to size the wires of general non-tree RC networks. Our method consists of three steps: 1) decompose a non-tree RC network into a tree RC network such that the Elmore delay at every sink remains unchanged; 2) size wires of the tree; and 3) merge the wires back to the original non-tree network. All three steps can be implemented in low-order polynomial time. Using this method, previous wiresizing techniques for tree topology for various objectives, such as minimizing the maximum delay, minimizing the total area or power, and reducing skew variability under process variations, can be applied to non-tree topologies. For certain types of networks, such as the tree+link network, our method gives the optimal solution, provided the tree wire sizing is optimal. Compared with the previous best wire-sizing method for non-tree circuits we can achieve 2% to 17% Elmore delay reduction with 14% to 30% total wire area reduction. Compared with unsized minimum width networks, our delay is 25% less and the skew is 34% less, under SPICE simulation. For the tree+link network, we can achieve significant delay reduction and zero skew in nominal case, while get up to 66% skew variation reduction.

Along with the progress of very-large-scale-integration technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in suboptimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path-based-buffer-insertion (PBBI) scheme which can overcome the weakness of the net-based approaches. We also discuss some potential difficulties of the PBBI approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net-based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

Buffer insertion is an effective technique to reduce interconnect delay. In this paper, we give a simple O(mn) time algorithm for optimal buffer insertion, where m is the number of sinks and n is the number of buffer positions. This is the first linear time buffer insertion algorithm for nets with constant number of sinks. When m is small, it is a significant improvement over our recent O(nlog/sup 2/n) time algorithm, and the O(n/sup 2/) time algorithm of van Ginneken. For b buffer types, the new algorithm runs in O(b/sup 2/n + bmn) time, an improvement of our recent O(bn/sup 2/) algorithm. The improvement is made possible by a clever bookkeeping method and an innovative linked list data structure that can perform addition of a wire, and addition of a buffer in amortized O(1) time. On industrial test cases, the new algorithm is faster than previous best algorithms by an order of magnitude.

As a prevalent constraint, sharp slew rate is often required in circuit design which causes a huge demand for buffering resources. This problem requires ultra-fast buffering techniques to handle large volume of nets, while also minimizing buffering cost. This problem is intensively studied in this paper. First, a highly efficient algorithm based on dynamic programming is proposed to optimally solve slew buffering with discrete buffer locations. Second, a new algorithm is developed to handle the difficult cases in which no assumption is made on buffer input slew. Third, an adaptive buffer selection approach is proposed to efficiently handle slew buffering with continuous buffer locations. Experiments on industrial netlists demonstrate that our algorithms are very effective and highly efficient: we achieve > 100X speed up and save up to 40% buffer area over the commonly-used van Ginneken style buffering.

Model order reduction has been a driving force for reducing analysis complexity of VLSI systems containing large linear networks. However, most existing reduction techniques are only applicable to networks with a small number of ports, failing to fulfill an even stronger need of reducing massively interconnected subsystems such as power grids and wide buses. In this paper, a port packing scheme is presented wherein the correlation between circuit ports is explored in a frequency-dependent manner. In the proposed McPack (multiport circuit packing) algorithm, port packing is combined with a practical realization of the recently developed tangential interpolation scheme for model reduction. McPack performs feasible moment matching for networks with many ports in the sense of tangential interpolation. With guaranteed passivity, extensibility to multi-point expansion as well as comparable complexity, McPack systematically introduces frequency-domain port packing into the existing projection-based model order reduction framework. For several large networks with high port count, the presented algorithm is shown to be significantly more accurate than the standard block-moment matching algorithm as well as other recently developed alternative.

Most existing buffer insertion algorithms, such as van Ginneken's algorithm, consider only individual nets. As a result, these algorithms tend to over buffer when applied to combinational circuits, since it is difficult to decide how many buffers to insert in each net. Recently, Sze, et al. [1] proposed a path-based algorithm for buffer insertion in combinational circuits. However their algorithm is inefficient for large circuits when there are many critical paths.In this paper, we present a new buffer insertion algorithm for combinational circuits such that the timing requirements are met and the buffer cost is minimized. Our algorithm iteratively inserts buffers in the circuit to improve the circuit delay. The core of this algorithm is simple but effective technique that guides the search for a good buffering solution. Experimental results on ISCAS85 circuits show that our new algorithm on average uses 36% less buffers and runs 3 times faster than Sze's algorithm.

Most existing buffering algorithms neglect the impact of inductance on circuit performance, which causes large error in circuit analysis and optimization. Even for the approaches considering inductance effects, their delay models are too simplistic to catch the actual performance. As delay-length dependence is approaching linear with inductance effect [1], fewer buffers are needed to reduce RLC delay. This motivates this work to propose a new algorithm for RLC buffer insertion. In this paper, a new buffer insertion algorithm considering inductance for intermediate and global interconnect is proposed, based on downstream impedance instead of traditional downstream capacitance. A new pruning technique that provides tremendous speedup and a new frequency estimation method that is very accurate in delay computation are also proposed. Experiments on industrial netlists demonstrate that our new algorithm reduces the number of buffers up to 34.4% over the traditional van Ginneken’s algorithm that ignores inductance. Our impedance delay estimation is very accurate compared to SPICE simulations, with only 10 % error while the delay model used in the previous RLC algorithm has 20 % error [2]. The accurate delay model not only reduces the number of buffers, but also brings high fidelity to the buffer solutions. Incorporating slew constraints, the algorithm is accelerated by about 4 × with only slight degradation in solution quality. 1.

Boolean Satisfiability (SAT) is a core NP-complete problem in logic synthesis. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper, we present a hardware solution to the SAT problem. We propose a custom IC to implement our approach, in which the traversal of the implication graph as well conflict clause generation are performed in hardware, in parallel. In our approach, clause literals are stored in specially designed cells. Clauses are implemented in banks, in a manner that allows clauses of variable width to be accommodated in these banks. To maximize the utilization of these banks, we initially partition the SAT problem. Our design is flexible in that it can implement various Boolean Constraint Propagation (BCP) engines on the same die, at the same time, allowing the user to switch BCP engines dynamically. Our solution has significantly larger capacity than existing hardware SAT solvers, and is scalable in the sense that several ICs can be used to simultaneously operate on the same SAT instance, effectively increasing capacity further. Our area and performance figures are derived from layout and SPICE (using extracted parasitics) estimates. Additionally, the approach presented in this paper have been functionally validated in Verilog. Preliminary results demonstrate that our approach can accommodate instances with approximately 63K clauses on a single IC of size 1.5cmx 1.5cm. The approach re suits in over 4 orders of magnitude speed improvement over BCP based software SAT approaches (2-3 orders of magnitude over other hardware SAT approaches). The capacity of our approach is significantly higher than most hardware based approaches.

Buffer insertion is a popular technique to reduce the interconnect delay. The classic buffer insertion algorithm of van Ginneken has a time complexity of O(n/sup 2/), where n is the number of buffer positions. Lillis, Cheng, and Lin extended van Ginneken's algorithm to allow b buffer types in O(b/sup 2/n/sup 2/) time. For modern design libraries that contain hundreds of buffers, it is a serious challenge to balance the speed and performance of the buffer insertion algorithm. In this paper, we present a new algorithm that computes the optimal buffer insertion in O(bn/sup 2/) time. The reduction is achieved by the observation that the (Q,C) pairs of the candidates that generate the new candidates must form a convex hull. On industrial test cases, the new algorithm is faster than the previous best buffer insertion algorithms by orders of magnitude. Since van Ginneken's algorithm with multiple buffer types are used by most existing algorithms on buffer insertion and buffer sizing, our new algorithm improves the performance of all these algorithms.

Capacitance-extraction algorithms based on the boundary element method (BEM) have to solve large linear systems. The number of unknowns equals the number of discretization panels n, which is much greater than the number of conductors m. The authors present a capacitance-extraction algorithm RedCap that first reduces the BEM system of size n into a small system of size O(m) and then solves the small system to compute the capacitances. RedCap uses a number of techniques, including the hierarchical-refinement technique of HiCap [Shi, 2002], the dense-to-sparse transformation of PHiCap [Yan, 2005], a reordering of the sparse linear system, and an incomplete LU factorization, to obtain the reduced system. RedCap achieves a significant speed improvement over previous methods. On benchmark problems with conductors in uniform and multilayer dielectrics, RedCap is up to 100 times faster than FastCap [Nabors and White, 1991] and up to four times faster than PHiCap [Yan, 2005], while restricting error to within 2% of FastCap

are requiring buffers to be inserted on interconnects of even moderate length for both critical paths and fixing electrical violations. Consequently, buffer insertion is needed on tens of thousands of nets during physical synthesis optimization. Even the fast implementation of van Ginneken’s algorithm requires several hours to perform this task. This work seeks to speed up the van Ginneken style algorithms by an order of magnitude while achieving similar results. To this end, we present three approximation techniques in order to speed up the algorithm: (1) aggressive pre-buffer slack pruning, (2) squeeze pruning, and (3) library lookup. Experimental results from industrial designs show that using these techniques together yields solutions in 9 to 25 times faster than van Ginneken style algorithms, while only sacrificing less than 3 % delay penalty. I.

Along with the progress of VLSI technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in sub-optimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path based buffer insertion scheme which can overcome the weakness of the net based approaches. We also discuss some potential difficulties of the path based buffer insertion approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.

Buffer insertion is a popular technique to reduce interconnect delay. The classic buffer insertion algorithm of L.P.P.P. van Ginneken (see ISCAS, p.865-8, 1990) has time complexity O(n/sup 2/), where n is the number of buffer positions. J. Lillis et al. (see IEEE Trans. Solid-Slate Circuits, vol.31, no.3, p.437-47, 1996) extended van Ginneken's algorithm to allow b buffer types in time O(b/sup 2/n/sup 2/). For modern design libraries that contain hundreds of buffers, it is a serious challenge to balance the speed and performance of the buffer insertion algorithm. We present a new algorithm that computes the optimal buffer insertion in O(bn/sup 2/) time. The reduction is achieved by the observation that the (Q, C) pairs of the candidates that generate the new candidates must form a convex hull. On industrial test cases, the new algorithm is faster than the previous best buffer insertion algorithms by orders of magnitude.

It is well known that n-detection test sets are effective to detect unmodeled defects and improve the defect coverage. However, in these sets, each of the n-detection test patterns has the same importance on the overall test set performance. In other words, the test pattern that detects a fault for the first time plays the same important role as the test pattern that detects that fault for the (n)-th time. In this paper, we propose a linear programming-based optimal test pattern selection method which aims at reducing the overall defect part level (DPL). Using resistive bridge faults as surrogates, our experimental results on ISCAS85 circuits demonstrate the proposed test pattern selection method achieves higher defect coverage than traditional n-detection method.

Excessive power supply noise can lead to overkill during delay test. A static test vector compaction solution is described to prevent such overkill. Low-cost power supply noise models are developed and used in compaction. An error analysis of these models is given. This paper improves on prior work in terms of models and algorithm to increase accuracy and performance. Experimental results are given on ISCAS89 circuits

Excessive power supply noise can lead to overkill during delay test. A static compaction algorithm is described in this paper that prevents such overkill. A power supply noise estimation tool has been built and integrated into the compaction process. Compaction results for KLPG delay tests for ISCAS89 circuits under different power grid environments are presented.

Given a set of points in the first quadrant, a rectilinear Steiner arborescence (RSA) is a directed tree rooted at the origin, containing all points, and composed solely of horizontal and vertical edges oriented from left to right, or from bottom to top. The complexity of finding an RSA with the minimum total edge length for general planar point sets has been a well-known open problem in algorithm design and VLSI routing. In this paper, we prove the problem is NP-complete in the strong sense.

Under manufacturing process variation, a path through a net is called longest if there exists a process condition under which the path has the maximum delay among all paths through the net. There are often multiple longest paths for each net, due to different process conditions. In addition, a local defect, such as resistive open or a resistive bridge, increases the delay of the affected net. To detect delay faults due to local defects and process variation, it is necessary to test all longest paths through each net. Previous approaches to this problem were inefficient because of the large number of paths that are not longest. This paper presents an efficient method to generate the set of longest paths for delay test under process variation. To capture both structural and process correlation between path delays, we use linear delay functions to express path delays under process variation. A novel technique is proposed to prune paths that are not longest, resulting in a significant reduction in the number of paths. In experiments on International Symposium on Circuits and Systems (ISCAS) circuits, our number of longest paths is 1-6% of the previous best approach, with 300/spl times/ less running time.

The classic buffer insertion algorithm of van Ginneken has time and space complexity O(n/sup 2/), where n is the number of possible buffer positions. For more than a decade, van Ginneken's algorithm has been the foundation of buffer insertion. In this paper, we present a new algorithm that computes the same optimal buffer insertion, but runs much faster. For 2-pin nets, our time complexity is O(nlogn) and space complexity is O(n). For multipin nets, our time complexity is O(nlog/sup 2/n) and space complexity is O(nlogn). The speedup is achieved by four novel techniques: predictive pruning, candidate tree, fast redundancy check, and fast merging. On industrial test cases, the new algorithms is 2-80 times faster than van Ginneken's algorithm and uses 1/4-1/500 of the memory. Since van Ginneken's algorithm and its variations are used by most existing algorithms on buffer insertion and buffer sizing, our new algorithm significantly improves the performance of all these algorithms. The predictive pruning technique has been applied to buffer cost minimization (Shi et al., 2004), and significantly improved the running time.

Three-dimensional (3-D) capacitance-extraction algorithms are important due to their high accuracy. However, the current 3-D algorithms are slow and thus their application is limited. In this paper, we present a novel method to significantly speed up capacitance-extraction algorithms based on boundary element methods (BEMs), under uniform and multiple dielectrics. The n/spl times/n coefficient matrix in the BEM is dense, even when approximated with the fast multipole method or hierarchical-refinement method, where n is the number of panels needed to discretize the conductor surfaces and dielectric interfaces. As a result, effective preconditioners are hard to obtain and iterative solvers converge slowly. In this paper, we introduce a linear transformation to convert the n/spl times/n dense coefficient matrix into a sparse matrix with O(n) nonzero entries, and then use incomplete factorization to produce a very effective preconditioner. For the k/spl times/k bus-crossing benchmark, our method requires at most four iterations, whereas previous best methods such as FastCap and HiCap require 10-20 iterations. As a result, our algorithm is up to 70 times faster than FastCap and up to 2 times faster than HiCap on these benchmarks. Additional experiments illustrate that our method consistently outperforms previous best methods by a large magnitude on complex industrial problems with multiple dielectrics.

Capacitance extraction is an important problem that has been extensively studied. This paper presents a significant improvement for the fast multipole accelerated boundary element method. We first introduce an algebraic transformation to convert the n x n dense capacitance coefficient matrix into a sparse matrix with O(n) nonzero entries. We then use incomplete Cholesky factorization or incomplete LU factorization to produce an effective preconditioner for the sparse linear system. Simulation results show that our algorithm drastically reduces the number of iterations needed to solve the linear system associated with the boundary element method. For the k x k bus crossing benchmark, our algorithm uses 3-4 iterations, compared to 10-20 iterations used by the previous algorithms such as FastCap [1] and HiCap [2]. As a result, our algorithm is 2-20 times faster than those algorithms. Our algorithm is also superior to the multi-scale method [3] because our preconditioner reduces the number of iterations further and applies to multiple dielectrics.

To detect the smallest delay faults at a fault site, the longest path(s) through it must be tested at full speed. Existing test generation tools are inefficient in automatically identifying the longest testable paths due to the high computational complexity. In this work a test generation methodology for scan-based synchronous sequential circuits is presented, under two at-speed test strategies used in industry. The two strategies are compared and the test generation efficiency is evaluated on ISCAS89 benchmark circuits and industrial designs. Experiments show that testing transition faults through the longest paths can be done in reasonable test set size.

The path delay fault model is the most realistic model for delay faults. Testing all the paths in a circuit achieves 100% delay fault coverage according to traditional path delay fault coverage metrics. These metrics result in unrealistically low fault coverage if only a subset of paths is tested, and the real test quality is not reflected. For example, the traditional path delay fault coverage of any practical test for circuit c6288 is close to 0 because this circuit has an exponential number of paths. In this paper, a statistical and realistic path delay fault coverage metric is presented. Then the quality of several existing test sets (path selection methods) is evaluated in terms of local and global delay faults using this metric, in comparison with the transition fault and traditional path delay fault coverage metrics.

We present a divide-and-conquer algorithm to improve the three-dimensional (3-D) boundary element method (BEM) for capacitance extraction. We divide large interconnect structures into small sections, set new boundary conditions using the border for each section, solve each section, and then combine the results to derive the capacitance. The target application is critical nets, clock trees, or packages where 3-D accuracy is required. Our algorithm is a significant improvement over the traditional BEMs and their enhancements, such as the "window" method, where conductors far away are dropped, and the "shield" method where conductors hidden behind other conductors are dropped. Experimental results show that our algorithm is a magnitude faster than the traditional BEM and the window+shield method, for medium to large structures. The error of the capacitance computed by the new algorithm is within 2% for self capacitance and 7% for coupling capacitance, compared with the results obtained by solving the entire system using BEM. Furthermore, our algorithms gives accurate distributed RC, where none of the previous 3-D BEM algorithms and their enhancements can.

We improve the accuracy and speed of boundary element method (BEM) or multipole accelerated BEM for interconnect parasitic extraction. Three techniques are presented and applied to capacitance extraction: selective coefficient enhancement, variable order multipole and multigrid. Experimental results show that the techniques are effective for extracting parasitics between all pairs of conductors, or between selected pairs of conductors.

Recent probabilistic test generation approaches have proven that detecting single stuck-at-faults multiple times is effective at reducing the defective part level (DPL). Unfortunately, these test generation strategies increase the number of test patterns. In this paper, we present a novel linear programming-based method to accelerate the optimal selection of test sets to minimize the defective part level based upon the MPG-D model. Our experimental results show that the proposed method is on average 300 times faster than the existing test pattern selection method.

The classic algorithm for optimal buffer insertion due to van Ginneken has time and space complexity O(n2), where n is the number of possible buffer positions.

Delay faults are an increasingly important test challenge. Traditional open and bridge fault models are incomplete because only the functional fault or a subset of delay fault are modeled. In this paper, we propose a circuit level model for resistive open and bridge faults. All possible fault behaviors are illustrated and a general resistive bridge delay calculation method is proposed. The new models are practical and easy to use. Fault simulation results show that the new models help the delay test to catch more bridge faults.

Delay faults are an increasingly important test challenge. Modeling bridge faults as delay faults helps delay tests to detect more bridge faults. Traditional bridge fault models are incomplete because these models only model the logic faults or these models are not efficient to use in delay tests for large circuits. In this article, we propose a physically realistic yet economical resistive bridge fault model to model delay faults as well as logic faults. An accurate yet simple delay calculation method is proposed. We also enumerate all possible fault behaviors and present the relationship between input patterns and output behaviors, which is useful in ATPG. Our fault simulation results show the benefit of at-speed tests.

The ability to compute the parasitic inductance of the interconnect is critical to the timing verification of modern VLSI circuits. A challenging aspect of inductance extraction is the solution of large, dense, complex linear systems of equations via iterative methods. Accelerating the convergence of the iterative method through preconditioning is made difficult due to the non-availability of the system matrix. This paper presents a novel algorithm to solve these linear systems by restricting current to a discrete solenoidal subspace in which Kirchoff's law is obeyed, and solving a reduced system via an iterative method such as GMRES. A preconditioner based on the Green's function is used to achieve near-optimal convergence rates in several cases. Experiments on a number of benchmark problems illustrate the advantages of the proposed method over FastHenry.

The authors present a new algorithm for computing the capacitance of three-dimensional electrical conductors of complex structures. The new algorithm is significantly faster and uses much less memory than previous best algorithms and is kernel independent. The new algorithm is based on a hierarchical algorithm for the n-body problem and is an acceleration of the boundary element method (BEM) for solving the integral equation associated with the capacitance extraction problem. The algorithm first adaptively subdivides the conductor surfaces into panels according to an estimation of the potential coefficients and a user-supplied error bound. The algorithm stores the potential coefficient matrix in a hierarchical data structure of size O(n), although the matrix is size n/sup 2/ if expanded explicitly, where n is the number of panels. The hierarchical data structure allows the multiplication of the coefficient matrix with any vector in O (n) time. Finally, a generalized minimal residual algorithm is used to solve m linear systems each of size n /spl times/ n in O(mn) time, where m is the number of conductors. The new algorithm is implemented and the performance is compared with previous best algorithms for the k /spl times/ k bus example. The new algorithm is 60 times faster than FastCap and uses 1/80 of the memory used by FastCap. The results computed by the new algorithm are within 2.5% from that computed by FastCap. The new algorithm is 5 to 150 times faster than the commercial software QuickCap with the same accuracy.

Given a graph $G=(V,\cal E)$, we want to find the vertex sets of the components of an unknown subgraph F=(V,E) of G such that $E \subseteq \cal E$. We learn about F by sending an oracle a query set $S \subseteq V$, and the oracle tells us the vertices connected to S in F. The objective is to use the minimum number of queries to partition the vertex set V into components of F. In electronic circuit design, the problem is also known as structural diagnosis of wiring networks.

We want to find the vertex sets of components of a graph G with a known vertex set V and unknown edge set E. We learn about G by sending an oracle a query set $S \subseteq V$\hspace*{-1pt}, and the oracle tells us the vertices connected to S. The objective is to use the minimum number of queries to partition the vertex set into components. The problem is also known as interconnect diagnosis of wiring networks in VLSI. We present a deterministic algorithm using O(min{k, lg n}) queries and a randomized algorithm using expected O(min{k,lg k + lg lg n}) queries, where n is the number of vertices and k is the number of components. We also prove matching lower bounds.

We present a new algorithm for computing the capacitance of three-dimensional perfect electrical conductors of complex structures. The new algorithm is significantly faster and uses much less memory than previous best algorithms, and is kernel independent. The new algorithm is based on a hierarchical algorithm for the n-body problem, and is an acceleration of the boundaryelement method for solving the integral equation associated with the capacitance extraction problem. The algorithm first adaptively subdivides the conductor surfaces into panels according to an estimation of the potential coefficients and a user-supplied error bound. The algorithm stores the potential coefficient matrix in a hierarchical data structure of size O(n), although the matrix is size n2 if expanded explicitly, where n is the number of panels. The hierarchical data structure allows us to multiply the coefficient matrix with any vector in O(n) time. Finally, we use a generalized minimal residual algorithm to...

For a reconfigurable architecture, the harvest rate is the expected percentage of defect-free processors that can be connected into the desired topology. The authors give an analytical estimation for the harvest rate of reconfigurable multipipelines based on the following model: there are n pipelines each with m stages, where each stage of a pipeline is defective with identical independent probability 0.5 and spare wires are provided for reconfiguration. By formulating the "shifting" reconfiguration as weighted chains in a partial ordered set, they prove when n=/spl theta/(m), the harvest rate is between 34% and 72%.

The traditional algorithm for area minimization of slicing floorplans due to Stockmeyer has time and space complexity O(n/sup 2/) in the worst case. For more than a decade, it has been considered the best possible. This paper presents a new algorithm of worst-case time and space complexity O(n log n), where n is the total number of realizations for the basic blocks, regardless whether the slicing is balanced or not. We also show R(n log n) is the lower bound on the time complexity of any area minimization algorithm. Therefore, the new algorithm not only finds the optimal realization, but also has the optimal running time.

The traditional algorithm of L. Stockmeyer (1983) for area minimization of slicing floorplans has time (and space) complexity O(n/sup 2/) in the worst case, or O(n log n) for balanced slicing. For more than a decade, it is considered the best possible. In this paper, we present a new algorithm of worst-case time (and space) complexity O(n log n), where n is the total number of realizations for the basic blocks, regardless whether the slicing is balanced or not. We also prove /spl Omega/(n log n) is the lower bound and the time complexity of any area minimization algorithm. Therefore, the new algorithm not only finds the optimal realization, but also has an optimal running time.

Interconnect diagnosis is an important problem in very large scale integration (VLSI), multichip module (MCM) and printed circuit board (PCB) production. The problem is to detect and locate all the shorts, opens and stuck-at faults among a set of nets using the minimum number of parallel tests. In this paper, we present worst-case optimal algorithms and lower bounds to several open problems in interconnect diagnosis.>

Reconfiguration of memory arrays with spare rows and columns has been shown to be an NP-complete problem. An analysis of average-case time complexities of several existing heuristics is presented, as well as a provably average-case polynomial-time algorithm for reconfiguration of memories with spare rows and columns. The algorithm runs faster than previous heuristics when the problem size is larger.>

An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time $O(n\log ^2 h)$and storage $O(n)$, where h is the number of extreme points. This is an improvement of the $O(nh)$ time gift-wrapping algorithm and, if $h = o(2^{\sqrt {\log _2 n} } )$, of the $O(n\log n)$ time divide-and-conquer algorithm.

Diagnosis strategies are investigated for repairable VLSI and WSI structures based on integrated diagnosis and repair. Knowledge of the repair strategy, the probability of each unit being good, and the expected test time of each unit is used by the diagnosis algorithm to select units for testing. The general problem is described, followed by an examination of a specific case. For k-out-of-n structures, a complete proof is given for the optimal diagnosis procedure of Y. Ben-Dov (1981). A compact representation of the optimal diagnosis procedure is described, which requires O(n/sup 2/) space and can be generated in O(n/sup 2/) time. Simulation results are provided to show the improvement in diagnosis time over online repair and offline repair.>

The authors investigate wafer probing strategies for the diagnosis of repairable VLSI and WSI (wafer scale integration) structures based on integrated diagnosis and repair. Knowledge of the repair strategy, the probability of each unit being good, and the expected test time each unit are used by the diagnosis algorithm to select units for wafer probe testing. The general problem is described followed by an examination of a specific case. Wafer probe diagnosis of k-out-of-n systems is analyzed and optimal diagnosis algorithms are derived. A compact representation of the optimal diagnosis scheme which needs O(n/sup 2/) space and can be generated in O(n/sup 2/) time is described.>