In the past decades, aggressive scaling of transistor feature size has been a primary force driving higher Static Random Access Memory (SRAM) integration density. Due to technology scaling, nanometer SRAM designs become increasingly vulnerable to stability challenges. The traditional way of analyzing stability is through the use of Static Noise Margins (SNMs). SNMs are not capable of capturing the key nonlinear dynamics associated with memory operations, leading to imprecise characterization of stability. This work rigorously develops dynamic stability concepts and, more importantly, captures them in physically based analytical models. By leveraging nonlinear stability theory, we develop analytical models that characterize the minimum required amplitude and duration of injected current noises that can flip the SRAM state. These models, which are parameterized in key design, technology, and operating condition parameters, provide important design insights and offer a basis for predicting scaling trends of SRAM dynamic stability.

Bistability/Multistability has been found in many biological systems including genetic memory circuits. Proper characterization of system stability helps to understand biological functions and has potential applications in fields such as synthetic biology. Existing methods of analyzing bistability are either qualitative or in a static way. Assuming the circuit is in a steady state, the latter can only reveal the susceptibility of the stability to injected DC noises. However, this can be inappropriate and inadequate as dynamics are crucial for many biological networks. In this paper, we quantitatively characterize the dynamic stability of a genetic conditional memory circuit by developing new dynamic noise margin (DNM) concepts and associated algorithms based on system theory. Taking into account the duration of the noisy perturbation, the DNMs are more general cases of their static counterparts. Using our techniques, we analyze the noise immunity of the memory circuit and derive insights on dynamic hold and write operations. Considering cell-to-cell variations, our parametric analysis reveals that the dynamic stability of the memory circuit has significantly varying sensitivities to underlying biochemical reactions attributable to differences in structure, time scales, and nonlinear interactions between reactions. With proper extensions, our techniques are broadly applicable to other multistable biological systems.

Shrinking access cycle times and the employment of dynamic read/write assist circuits have made the use of standard static noise margins increasingly problematic for scaled SRAM designs. Recently proposed dynamic noise margins precisely characterize dynamic stability using the concept of stability boundaries, or separatrices, and provide elegant separatrix tracing algorithm. However, the present separatrix characterization method is only efficient in the two-dimensional state space and hence not practically applicable to fully extracted SRAM designs with additional parasitics. We present a rigorous system-theoretical approach for computing the tangent approximation to the separatrix in the high-dimensional space. Using this as a basis, we develop fast method based on tangent approximation and exact iterative-refinement method for analyzing SRAM dynamic stability. The proposed algorithms have been implemented as a SPICE-like CAD tool and are broadly applicable to efficient computation of dynamic noise margins.

The search for new nonvolatile universal memories is propelled by the need for pushing power-efficient nanocomputing to the next higher level. As a potential contender for the next-generation memory technology of choice, the recently found "the missing fourth circuit element", memristor, has drawn a great deal of research interests. In this paper, we characterize the fundamental electrical properties of memristor devices by encapsulating them into a set of compact closed-form expressions. Our derivations provide valuable design insights and allow a deeper understanding of key design implications of memristor-based memories. In particular, we investigate the design of read and write circuits and analyze data integrity and noise-tolerance issues.

Technology scaling in sub-100 nm regime has significantly shrunk the SRAM stability margins in data retention, read and write operations. Conventional static noise margins (SNMs) are unable to capture nonlinear cell dynamics and become inappropriate for state-of-the-art SRAMs with shrinking access time and/or advanced dynamic read-write-assist circuits. Using the insights gained from rigorous nonlinear system theory, we define the much needed SRAM dynamic noise margins (DNMs). The newly defined DNMs not only capture key SRAM nonlinear dynamical characteristics but also provide valuable design insights. Furthermore, we show how system theory can be exploited to develop CAD algorithms that can analyze SRAM dynamic stability characteristics three orders of magnitude faster than a brute-force approach while maintaining SPICE-level accuracy. We also demonstrate a parametric dynamic stability analysis approach suitable for low-probability cell failures, leading to three orders of magnitude runtime speedup for yield analysis under high-sigma parameter variations.

We introduce a scheme that achieves a diversity gain for coded systems under static fading conditions by using multiple antennas and random signal mapping. In a two-antenna system, the bit-error rate performance of the proposed scheme approaches that of Alamouti's scheme when the channel is perfectly known. In the presence of channel mismatch, the proposed scheme outperforms Alamouti's scheme significantly. It is shown that, as the number of transmit antennas N goes to infinity, the effective channel for the introduced scheme behaves as if it were perfectly interleaved (i.e., as if the fading was independent). When N is small, further performance gain can be achieved by expanding the original signal constellation.

We introduce an adaptive band-selection (ABS) scheme for Multi Carrier-Code Division Multiple Access (MC-CDMA) systems to improve system capacity. Instead of using all subcarriers, mobile stations transmit message data only through the selected frequency bands based on band-selection coefficients from the base station. By using the adaptive band-selection scheme, ABS MC-CDMA systems accommodate more users than MC-CDMA systems that use all frequency bands for message data transmission. Due to the time-varying wireless channel conditions and dynamic power allocations, band-selection coefficients should be adaptively determined at the base station every update period. In our ABS MC-CDMA systems, the processing gain, the transmitted power and the data rate depend on the number of selected bands. Under the assumption that the total transmission power and the total amount of transmission data are the same for both MC-CDMA systems and ABS MC-CDMA systems, SNR behaviors are investigated and BER performances are presented in terms of the number of users and the normalized Doppler frequencies.

In previous work on decoding space-time codes, it is either assumed that perfect channel state information (CSI) is present, or a channel estimate is obtained using pilot symbols and then used as if it were perfect to extract symbol estimates. In the latter case, a loss in performance is incurred, since the resulting overall receiver is not optimal. We look at maximum-likelihood (ML) sequence estimation for space-time coded systems without assuming CSI. The log-likelihood function is presented for both-quasi-static and nonstatic fading channels, and an expectation-maximization (EM)-based algorithm is introduced for producing ML data estimates, whose complexity is much smaller than a direct evaluation of the log-likelihood function. Simulation results indicate the EM-based algorithm achieves a performance close to that of a receiver which knows the channel perfectly.

A two-layer adaptive wrapping technique is proposed in this paper to migrate legacy energy management system (EMS) modules into reusable components, and therefore transforming the legacy system into a component-based system. Meanwhile, an XML-based database wrapping technique is proposed to provide a flexible data exchange solution. These techniques help not only maintaining the reliability but also increasing the reusability of the legacy EMS during the software evolution process.

We apply a simple transmit diversity technique to downlink multicarrier CDMA (MC-CDMA) systems. The resulting diversity on each subcarrier improves orthogonality among users which is distorted by the subcarriers' multipath fading. Accordingly, the diversity suppresses multiuser interference. For equal-gain-combining (EGC) receivers, both theoretical analysis and simulation results show that interference is approximately reduced by half compared to MC-CDMA without space diversity. For the orthogonality-restoring combining (ORC) receiver, simulation results show that it suppresses noise amplification while rejecting multiuser interference.

We introduce a new scheme that achieves a diversity gain for coded systems under static fading conditions by using multiple antennas and random signal mapping. It is shown that as the number of transmit antennas N goes to infinity, the effective channel behaves as if it were perfectly interleaved (i.e. as if the fading was independent). When N is small, a further performance gain can be achieved by expanding the original signal constellation. Simulation results show that N/spl ap/8 is enough to achieve close to the performance of a perfectly interleaved system.

In this paper, we derive a time-complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of Goldstein-Levitin-Poljak type formulated by Bertsekas (1982), Bertsekas and Gallager (1987) and Bertsekas et al. (1984) converges to within /spl epsi/ in relative accuracy in O(/spl epsi//sup -2/h/sub min/N/sub max/) number of iterations, where N/sub max/ is the number of paths sharing the maximally shared link, and h/sub min/ is the diameter of the network. Based on this complexity result, we also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy, where n is the number of nodes in the network. The result of this paper argues for constructing networks with low diameter for the purpose of reducing complexity of the network control algorithms. The result also implies that parallelizing the optimal routing algorithm over the network nodes is beneficial.

This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log/sup 2/ (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log/sup 2/ (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks.

The EPRCA (enhanced proportional rate control algorithm) is a leading congestion control protocol for available bit rate (ABR) service in ATM networks. Even though EPRCA has been adopted by the ATM Forum as the standard for ABR congestion control, we show that this protocol is only marginally stable. The stability analysis presented in this paper does not consider interactions among network components and should be considered as a bottle-neck stability result. We show that, if a queue is the bottleneck of a congested path, then its queue size will eventually decrease. However, if a queue is not congested, its queue size can actually increase and the congestion can be self-induced.

In this paper, a new algorithm based on hierarchical aggregation/disaggregation and decomposition/composition (HAD) scheme is proposed to solve the optimal routing problems (ORP) for hierarchically structured networks of multi-layer backbones. Our algorithm has two major differences with the existing HAD algorithms for hierarchically clustered networks: (1) our algorithm works with more general networks than the networks with the clustered structure; (2) our algorithm parallelizes the computations for different commodities (message flows defined by a pair of origin node and destination node) so that it speeds up with a parallel time complexity of O(mlog/sup 2/(n)), which is much less than O(Mlog/sup 2/(n)) needed for the existing HAD algorithms. Here, n is the number of nodes in the network; M is the number of commodities and m is a positive number usually much smaller than M and is a function of the patterns of all the commodities including the locations of all origin nodes and destination nodes, and the flow demand of each commodity. Furthermore, our algorithm can make a trade-off between the run time and the optimality, i.e., by allowing the solution to be sub-optimal, our algorithm can save great amount of computation time. The implementation of the algorithm for a 200-node network is simulated using OPNET simulation package (OPNET or Optimized Network Engineering Tools is developed by MIL3, Inc.), and the test results are consistent with our analysis.

Derives a time complexity bound for the gradient projection method for optimal routing in data networks. This result shows that the gradient projection algorithm of the Goldstein-Levitin-Poljak type formulated by Bertsekas (1982) converges to within /spl epsiv/ in relative accuracy in O(/spl epsiv//sup 2/h/sub min/N/sub max//sup L/) iterations, where N/sub max//sup L/ is the number of paths sharing the maximally shared link, and h/sub min/ is the diameter of the network. Based on this complexity result, the authors also show that the one-source-at-a-time update policy has a complexity bound which is O(n) times smaller than that of the all-at-a-time update policy [Bertsekas, 1982], where n is the number of nodes in the network. The result of the paper argues for constructing networks with low diameter for the purpose of reducing the complexity of the network control algorithms. The result also implies that parallelizing the optimal rotating algorithm over the network nodes is beneficial.

In our earlier paper (1991), a textured decomposition based algorithm is developed to solve the optimal routing problem in data networks; a few examples were used to illustrate the speedup advantage and the convergence conditions for the textured algorithm to converge to a global minimum. The speedup advantage is investigated in Huang et al. (1993). However, the theoretical foundation is not provided. In this paper, we provide the foundation. First, we show that for any textured decomposition, the algorithm always converges to a stationary point, which may not be a global minimum. And then, we prove that if the conditions of the exact convergence theorem are satisfied, the textured algorithm will converge to a global minimum.

A distributed algorithm is presented that can be used to solve the single-destination shortest path (SDSP) problem or the all-pairs shortest path (APSP) problem for a class of clustered data networks. The network graph is assumed to be characterized with a balanced hierarchically clustered (BHC) topology. The BHC topology is introduced in this paper and is shown to be a realistic characterization for a large class of interconnected data networks. For certain types of BHC topologies, the SDSP problem can be solved with computation and communication time complexities of O(log n), assuming one processor is available at each of the n number of nodes. Assuming p processors are available at each node, computation and communication time complexities of O((n/p) log n) and O(n log n) are achievable, respectively, for solving the APSP problem. It is also shown that the algorithm converges in an asynchronous environment.>

A distributed algorithm is presented which finds the shortest path from every node in the network to a given destination node. The network topology is assumed to be organizable into a generalized balanced-tree hierarchy (BH). The BH topology is introduced and characterized, and it is shown that most large interconnected data networks are of this type. It is also shown that the algorithm converges in an asynchronous environment. Therefore, some of the difficulties associated with synchronizing the order of events can be avoided in the actual implementation of the proposed algorithm.>