Stochastic Algorithms for Discrete Parameter Simulation Optimization

We present two efficient discrete parameter simulation optimization (DPSO) algorithms for the long-run average cost objective. One of these algorithms uses the smoothed functional approximation (SFA) procedure, while the other is based on simultaneous perturbation stochastic approximation (SPSA). The use of SFA for DPSO had not been proposed previously in the literature. Further, both algorithms adopt an interesting technique of random projections that we present here for the first time. We give a proof of convergence of our algorithms. Next, we present detailed numerical experiments on a problem of admission control with dependent service times. We consider two different settings involving parameter sets that have moderate and large sizes, respectively. On the first setting, we also show performance comparisons with the well-studied optimal computing budget allocation (OCBA) algorithm and also the equal allocation algorithm. Note to Practitioners-Even though SPSA and SFA have been devised in the literature for continuous optimization problems, our results indicate that they can be powerful techniques even when they are adapted to discrete optimization settings. OCBA is widely recognized as one of the most powerful methods for discrete optimization when the parameter sets are of small or moderate size. On a setting involving a parameter set of size 100, we observe that when the computing budget is small, both SPSA and OCBA show similar performance and are better in comparison to SFA, however, as the computing budget is increased, SPSA and SFA show better performance than OCBA. Both our algorithms also show good performance when the parameter set has a size of 10(8). SFA is seen to show the best overall performance. Unlike most other DPSO algorithms in the literature, an advantage with our algorithms is that they are easily implementable regardless of the size of the parameter sets and show good performance in both scenarios.

Extrinsic Analog Synthesis using Piecewise Linear Current-Mode Circuits

A methodology is presented for the synthesis of analog circuits using piecewise linear (PWL) approximations. The function to be synthesized is divided into PWL segments such that each segment can be realized using elementary MOS current-mode programmable-gain circuits. A number of these elementary current-mode circuits when connected in parallel, it is possible to realize piecewise linear approximation of any arbitrary analog function with in the allowed approximation error bounds. Simulation results show a close agreement between the desired function and the synthesized output. The number of PWL segments used for approximation and hence the circuit area is determined by the required accuracy and the smoothness of the resulting function.

Coupling of High Voltage AC Power Line Fields to Metallic Pipelines

In the recent years, there has been a trend to run metallic pipelines carrying petroleum products and high voltage AC power lines parallel to each other in a relatively narrow strip of land. Due to this sharing of the right-of-way, verhead AC power line electric field may induce voltages on the metallic pipelines running in close vicinity leading to serious adverse effects. In this paper, the induced voltages on metallic pipelines running in close vicinity of high voltage power transmission lines have been computed. Before computing the induced voltages, an optimum configuration of the phase conductors based on the lowest conductor surface gradient and field under transmission line has been arrived at. This paper reports the conductor surface field gradients calculated for the various configurations. Also the electric fields under transmission line, for single circuit and double circuit (various phase arrangements) have been analyzed. Based on the above results, an optimum configuration giving the lowest field under the power line as well as the lowest conductor surface gradient has been arrived at and for this configuration, induced voltage on the pipeline has been computed using the Charge Simulation Method (CSM). For comparison, induced voltages on the pipeline has been computed for the various other phase configurations also.

Voltage and Temperature-Aware SSTA Using Neural Network Delay Model

With the emergence of voltage scaling as one of the most powerful power reduction techniques, it has been important to support voltage scalable statistical static timing analysis (SSTA) in deep submicrometer process nodes. In this paper, we propose a single delay model of logic gate using neural network which comprehensively captures process, voltage, and temperature variation along with input slew and output load. The number of simulation programs with integrated circuit emphasis (SPICE) required to create this model over a large voltage and temperature range is found to be modest and 4x less than that required for a conventional table-based approach with comparable accuracy. We show how the model can be used to derive sensitivities required for linear SSTA for an arbitrary voltage and temperature. Our experimentation on ISCAS 85 benchmarks across a voltage range of 0.9-1.1V shows that the average error in mean delay is less than 1.08% and average error in standard deviation is less than 2.85%. The errors in predicting the 99% and 1% probability point are 1.31% and 1%, respectively, with respect to SPICE. The two potential applications of voltage-aware SSTA have been presented, i.e., one for improving the accuracy of timing analysis by considering instance-specific voltage drops in power grids and the other for determining optimum supply voltage for target yield for dynamic voltage scaling applications.

Physically consistent simulation of mesoscale chemical kinetics: The non-negative FIS-alpha method

Biochemical pathways involving chemical kinetics in medium concentrations (i.e., at mesoscale) of the reacting molecules can be approximated as chemical Langevin equations (CLE) systems. We address the physically consistent non-negative simulation of the CLE sample paths as well as the issue of non-Lipschitz diffusion coefficients when a species approaches depletion and any stiffness due to faster reactions. The non-negative Fully Implicit Stochastic alpha (FIS alpha) method in which stopped reaction channels due to depleted reactants are deleted until a reactant concentration rises again, for non-negativity preservation and in which a positive definite Jacobian is maintained to deal with possible stiffness, is proposed and analysed. The method is illustrated with the computation of active Protein Kinase C response in the Protein Kinase C pathway. (C) 2011 Elsevier Inc. All rights reserved.

Modeling of the Effects of Process Variations on Circuit Delay at 65nm

A novel methodology for modeling the effects of process variations on circuit delay performance is proposed by relating the variations in process parameters to variations in delay metric of a complex digital circuit. The delay of a 2-input NAND gate with 65nm gate length transistors is extensively characterized by mixed-mode simulations which is then used as a library element. The variation in saturation current Ionat the device level, and the variation in rising/falling edge stage delay for the NAND gate at the circuit level, are taken as performance metrics. A 4-bit x 4-bit Wallace tree multiplier circuit is used as a representative combinational circuit to demonstrate the proposed methodology. The variation in the multiplier delay is characterized, to obtain delay distributions, by an extensive Monte Carlo analysis. An analytical model based on CV/I metric is proposed, to extend this methodology for a generic technology library with a variety of library elements.

Dynamic Supply and Threshold Voltage Scaling for CMOS Digital Circuits Using In-Situ Power Monitor

A generalized power tracking algorithm that minimizes power consumption of digital circuits by dynamic control of supply voltage and the body bias is proposed. A direct power monitoring scheme is proposed that does not need any replica and hence can sense total power consumed by load circuit across process, voltage, and temperature corners. Design details and performance of power monitor and tracking algorithm are examined by a simulation framework developed using UMC 90-nm CMOS triple well process. The proposed algorithm with direct power monitor achieves a power savings of 42.2% for activity of 0.02 and 22.4% for activity of 0.04. Experimental results from test chip fabricated in AMS 350 nm process shows power savings of 46.3% and 65% for load circuit operating in super threshold and near sub-threshold region, respectively. Measured resolution of power monitor is around 0.25 mV and it has a power overhead of 2.2% of die power. Issues with loop convergence and design tradeoff for power monitor are also discussed in this paper.