waashk/dblp huggingface dataset:
optimal adaptive modulation and coding with switching costs. we present an optimal adaptive modulation and coding policy that minimizes the transmission latency and modulation/coding switching cost across a finite-state markovian fading channel. we formulate the optimal tradeoff between transmission latency and modulation/coding switching cost as a discounted infinite horizon markov decision problem (mdp). by exploiting special structures of the formulated mdp and under certain sufficient conditions, we show that optimal modulation and coding selection policies are monotone in the state variables. these monotone optimal policies are computationally inexpensive to implement and are scalable in terms of channel and switching cost parameters. numerical results confirm the monotonicity and threshold-based structure of the optimal modulation and coding scheme (mcs) selection policies under the proposed sufficient conditions.
locating congested segments on the internet by clustering the delay performance of multiple paths. delay variation-based detection and location of congestion in a large network is considered. since the internet is still highly prone to performance deterioration due to transient large delays, locating a part of the network (segments) responsible is vital to ensure that internet service providers can mitigate or prevent such performance deterioration. in the proposed method, the end-to-end packet delays from multiple origins to multiple destinations are actively and continuously measured. by analyzing those data on delay variation along each monitored path, congestion is detected by finding a delay performance deterioration worse than a predefined criteria and a congested segment responsible could be inferred by finding a set of paths among which delay variations are strongly correlated. this is a network tomographic approach based on a clustering technique that effectively tackles the correlation among packet delay variation along individual paths. the proposed method was evaluated through a real-world long-term experiment on the japan's commercial internet, and was shown to have considerable potential to promptly locate congested segments through various analyses on the experimental results.
opportunistic scheduling for wireless network coding. this letter addresses a scheduling problem for wireless network coding (wnc). in our previous work, we have theoretically shown that the optimum number of nodes to be included into a network-coded packet as well as its transmission rate depends on time-varying link condition between a transmitting node and receiving nodes [1]. based on this observation, this letter designs practical scheme which opportunistically selects scheduled nodes, packets to be coded and an employed modulation level according to time-varying channel conditions and packet length. the numerical results show that the proposed opportunistic scheduling can improve the overall throughput as compared with non-opportunistic approach.
downlink tcp performance under cross layer rate and power allocation in infrastructure th-ppm uwb networks. ultra wideband (uwb) systems are currently an important wireless infrastructure for efficient short-range communications and mobile applications. to improve the system efficiency while guaranteeing the radio link level quality of services, the transmission rate and power of the mobile nodes in uwb based infrastructure networks can be dynamically adjusted by executing an optimization algorithm at the access points (aps). in this paper, we present a cross layer rate and power allocation algorithm based on the multilayer model of time hopping (th) pulse position modulation (ppm) uwb multimedia networks. we consider the performance of the tcp protocol under the proposed cross layer allocation scheme in various realistic uwb based infrastructure networking scenarios.
sat and atpg: boolean engines for formal hardware verification. in this survey, we outline basic sat- and atpg- procedures as well as their applications in formal hardware verification. we attempt to give the reader a trace trough literature and provide a basic orientation concerning the problem formulations and known approaches in this active field of research.
dag-aware circuit compression for formal verification. the choice of representation for circuits and boolean formulae in a formal verification tool is important for two reasons. first of all, representation compactness is necessary in order to keep the memory consumption low. this is witnessed by the importance of maximum processable design size for equivalence checkers. second, many formal verification algorithms are sensitive to redundancies in the design that is processed. to address these concerns, three different auto-compressing representations for boolean circuit networks and formulas have been suggested in the literature. we attempt to find a blend of features from these alternatives that allows us to remove as much redundancy as possible while not sacrificing runtime. by studying how the network representation size varies when we change parameters, we show that the use of only one operator node is suboptimal, and demonstrate that the most powerful of the proposed reduction rules, two-level minimization, actually can be harmful. we correct the bad behavior of two-level optimization by devising a simple linear simplification algorithm that can remove tens of thousands of nodes on examples where all obvious redundancies already have been removed. the combination of our compactor with the simplest representation outperforms all of the alternatives we have studied, with a theoretical runtime bound that is at least as good as the three studied representations.
automatic generalized phase abstraction for formal verification. a standard approach to improving circuit performance is to use an n-phase design style where combinational logic is interspersed freely between level sensitive latches controlled by separate clocks. unfortunately, the use of an n-phase design style will increase the number of state variables by a factor of n, making formal verification many orders of magnitude harder. previous approaches to solving this problem restrict the kind of designs that can be handled severely and construct an abstracted netlist with fewer state variables by a syntactic analysis that requires the user to identify clocks. we extend the current state of the art by introducing a phase abstraction algorithm that (1) poses no restrictions on the design style that can be used, that (2) avoids an error prone syntactic analysis, that (3) requires no input from users, and that (4) can be integrated into any model checker without requiring hdl code analysis.
slope propagation in static timing analysis. static timing analysis has traditionally used the pert method for identifying the critical path of a digital circuit. due to the influence of the slope of a signal at a particular node on the subsequent path delay, an earlier signal with a signal slope greater than the slope of the later signal may result in a greater delay. therefore, the traditional method for timing analysis may identify the incorrect critical path and report an optimistic delay for the circuit. we show that the circuit delay calculated using the traditional method is a discontinuous function with respect to transistor and gate sizes, posing a severe problem for circuit optimization methods. we propose a new timing analysis algorithm which resolves both these issues. the proposed algorithm selectively propagates multiple signals through each timing edge in cases where there exists ambiguity regarding which arriving signal represents the critical path. the algorithm for propagating the corresponding required times is also presented. we prove that the proposed algorithm identifies a circuit's true critical path, where the traditional timing analysis method may not. we also show that under this method circuit delay and node slack are continuous functions with respect to a circuit's transistor and gate sizes. in addition, we present a heuristic method which reduces the number of signals to be propagated at the expense of a slight loss in accuracy. finally, we show how the proposed algorithm was efficiently implemented in an industrial static timing analysis and optimization tool, and present results for a number of industrial circuits. our results show that the traditional timing analysis method underestimates the circuit delay by as much as 38%, while that the proposed method efficiently finds the correct circuit delay with only a slight increase in run time.
ic power distribution challenges. with each technology generation, delivering a timevarying current with reduced nominal supply voltage variation is becoming more difficult due to increasing current and power requirements. the power delivery network design becomes much more complex and requires accurate analysis and optimizations at all levels of abstraction in order to meet the specifications. in this paper, we describe techniques for estimation of the supply voltage variations that can be used in the design of the power delivery network. we also describe the decoupling capacitor hierarchy that provides a low impedance to the increasing high-frequency current demand and limits the supply voltage variations. techniques for high-level power estimation that can be used for performance vs. power trade-offs to reduce the current and power requirements of the circuit are also presented.
design space exploration for aggressive test cost reduction in circularscan architectures. scan-based designs effectively reduce test generation complexity and thus deliver improved fault coverage. nevertheless, the traditional scan architectures suffer from increased test time and test data volume. the circularscan architecture (arslan and orailoglu) provides a flexible environment for test cost reduction. the new scan design enables the use of the captured response of the previously applied test pattern as a template. the subsequent pattern is loaded by efficiently performing the necessary changes on the template through the functionality provided by the new architecture, conceptually exploiting the inherent low specified bit density of the test patterns. we explore the space of possible design alternatives built on the circularscan architecture; the design alternatives are presented with accompanying test application methods. the experimental results indicate a substantial test cost reduction, reaching 90% levels. the proposed scheme is not only easily scalable but also promises further reductions in test cost when applied to large state of the art ics.
the formal verification of a pipelined double-precision ieee floating-point multiplier. floating-point circuits are notoriously difficult to design and verify. for verification, simulation barely offers adequate coverage, conventional model-checking techniques are infeasible, and theorem-proving based verification is not sufficiently mature. in this paper we present the formal verification of a radix-eight, pipelined, ieee double-precision floating-point multiplier. the verification was carried out using a mixture of model-checking and theorem-proving techniques in the voss hardware verification system. by combining model-checking and theorem-proving we were able to build on the strengths of both areas and achieve significant results with a reasonable amount of effort.
polarized observability don't cares. a new method is presented to compute the exact observability don't cares (odc} for multilevel combinational circuits. a new mathematical concept, called polarization, is introduced. polarization captures the essence of odc calculation on the otherwise difficult points of reconvergence. it makes it possible to derive the odc of a node from the odcs of its fanouts with a very simple formula. experimental results for the 39 largest mcnc benchmark examples show that the method is able to compute the odc set (expressed as a boolean network} for all but 1 circuit in at most a few seconds.
placement method targeting predictability robustness and performance. we study the relationship between robustness,predictability andperformance of vlsi circuits. it is shown that predictability andperformance are conflicting objectives. performance and robustnessare statically conflicting objectives but they are statistically non-conflicting.we propose and develop means for changing a standard timing-driven partitioning-based placement algorithm in order to design more predictable and robust circuits without sacrificingmuch of performance.
multi-objective circuit partitioning for cutsize and path-based delay minimization. in this paper we present multi-objective hmetis partitioning for simultaneous cutsize and circuit delay minimization. we change the partitioning process itself by introducing a new objective function that incorporates a truly path-based delay component for the most critical paths. to avoid semi-critical paths from becoming critical, the traditional slack based delay component is also included in the cost function. the proposed timing driven partitioning algorithm is built on top of the hmetis algorithm, which is very efficient. simulations results show that 14% average delay improvement can be obtained. smooth trade-off between cutsize and delay is possible in our algorithm.
algebraic decision diagrams and their applications. in this paper we present theory and experimental results on algebraic decision diagrams. these diagrams extend bdds by allowing values from an arbitrary finite domain to be associated with the terminal nodes of the diagram. we present a treatment founded in boolean algebras and discuss algorithms and results in several areas of application: matrix multiplication, shortest path algorithms, and direct methods for numerical linear algebra. although we report an essentially negative result for gaussian elimination per se, we propose a modified form of adds which appears to circumvent the difficulties in some cases. we discuss the relevance of our findings and point to directions for future work.
parametric test development for rf circuits targeting physical fault locations and using specification-based fault definitions. the test cost of rf systems is an increasing percentage of the overall system cost. this trend is mainly due to the traditional rf testing schemes based on the full measurement of specifications over a wide range of input conditions. in this paper, we present a test development methodology for rf circuits based on a novel parametric fault definition. we target deviations in physical circuit parameters, such as a resistance or the width of a transistor. however, we consider a circuit faulty only if it violates a specification. our test development method aims at reducing not only the number of measurements, but also the overall test hardware cost by incorporating the relative set-up cost of each measurement into our selection criteria. experimental results on a low-noise amplifier (lna) circuit show that our test development technique reduces the overall test time (49%-67%) as well as the number of required measurement set-ups (17%-33%) considerably. by defining the target faults based on specification violations, our technique also provides high confidence in the test quality.
a symbolic method to reduce power consumption of circuits containing false paths. power dissipation in technology mapped circuits can be reduced by performing gate re-sizing. recently we have proposed a symbolic procedure which exploits the compactness of the add data structure to accurately calculate the arrival times at each node of a circuit for any primary input vector. in this paper we extend our timing analysis tool to the symbolic calculation of required times and slacks, and we use this information to identify gates of the circuits that can be re-sized. the nice feature of our approach is that it takes into account the presence of false paths naturally. as shown by the experimental results, circuits re-synthesized with the technique we present in this paper are guaranteed to be at least as fast as the original implementations, but smaller and substantially less power-consuming.
addressing high frequency effects in vlsi interconnects with full wave model and cfh. abstract: in order to accurately characterize dispersive system of vlsi interconnects at higher frequencies, full wave analysis which takes into account all possible field components and satisfies all boundary conditions is required. however, conventional circuit simulation of interconnects with full wave models is extremely cpu expensive. this paper presents a new method to extend the moment matching technique, complex frequency hopping, to the case of interconnects modeled with full wave analysis. formulation of circuit equations is modified to incorporate interconnect stencil from full wave analysis. a new algorithm for the moment generation for interconnect networks with full wave models has been developed. full wave analysis has been carried out with the efficient 'spectral domain approach'. results have shown that the proposed method is accurate while it yields a speed up of one to three orders of magnitude over conventional simulation techniques. subject terms: circuit analysis computing; vlsi; integrated circuit interconnections; circuit cad; high-frequency effects; vlsi interconnects; high frequency effects; full wave model; cfh; spectral domain approach; dispersive system; full wave analysis; boundary conditions; moment matching technique; complex frequency hopping
a probabilistic-based design methodology for nanoscale computation. as current silicon-based techniques fast approach their practicallimits, the investigation of nanoscale electronics, devices andsystem architectures becomes a central research priority. it is expectedthat nanoarchitectures will confront devices and interconnectionswith high inherent defect rates, which motivates the searchfor new architectural paradigms.in this paper, we propose a probabilistic-based design methodologyfor designing nanoscale computer architectures based onmarkov random fields (mrf). the mrf can express arbitrarylogic circuits and logic operation is achieved by maximizing theprobability of state configurations in the logic network. maximizingstate probability is equivalent to minimizing a form of energythat depends on neighboring nodes in the network. once we developa library of elementary logic components, we can link themtogether to build desired architectures based on the belief propagationalgorithm. belief propagation is a way of organizing theglobal computation of marginal belief in terms of smaller localcomputations. we will illustrate the proposed design methodologywith some elementary logic examples.
unification of partitioning, placement and floorplanning. large macro blocks, pre-designed datapaths, embedded memories and analog blocks are increasingly used in asic designs. however, robust algorithms for large-scale placement of such designs have only recently been considered in the literature, and improvements by over 10% per paper are still common. large macros can be handled by traditional floorplanning, but are harder to account for in min-cut and analytical placement. on the other hand, traditional floorplanning techniques do not scale to large numbers of objects, especially in terms of solution quality. we propose to integrate min-cut placement with fixed-outline floor-planning to solve the more general placement problem, which includes cell placement, floorplanning, mixed-size placement and achieving routability. at every step of min-cut placement, either partitioning or wirelength-driven, fixed-outline floorplanning is invoked. if the latter fails, we undo an earlier partitioning decision, merge adjacent placement regions and re-floorplan the larger region to find a legal placement for the macros. empirically, this framework improves the scalability and quality of results for traditional wirelength-driven floorplanning. it has been validated on recent designs with embedded memories and accounts for routability. additionally, we propose that free-shape rectilinear floorplanning can be used with rough module-area estimates before synthesis.
boolean techniques for low power driven re-synthesis. we present a boolean technique to reduce power consumption of combinational circuits that have already been optimized for area and delay and then mapped onto a library of gates. in order to achieve a better optimization, we cluster gates by collapsing two or more levels of gates into a single node. when optimizing each cluster, our method extends the algorithms used in espresso, by adding heuristics that bias the minimization toward lowering the power dissipation in the circuit. the results of our method, on a number of benchmark circuits, show an average of 16% improvement in power savings compared to existing boolean techniques.
on whitespace and stability in mixed-size placement and physical synthesis. in the context of physical synthesis, large-scale standard-cell placementalgorithms must facilitate incremental changes to layout, bothlocal and global. in particular, flexible gate sizing, net buffering anddetail placement require a certain amount of unused space in everyregion of the die. the need for "local" whitespace is further emphasizedby temperature and power-density limits. another requirement,the stability of placement results from run to run, is importantto the convergence of physical synthesis loops. indeed, logic resynthesistargetting local congestion in a given placement or particularcritical paths may be irrelevant for another placement produced bythe same or a different layout tool.in this work we offer solutions to the above problems. we showhow to tie the results of a placer to a previously existing placement,and yet leave room for optimization. in our experiments this techniqueproduces placements with similar congestion maps. we alsoshow how to trade-off wirelength for routability by manipulatingwhitespace. empirically, our techniques improve circuit delay ofsparse layouts in conjunction with physical synthesis.in the context of earlier proposed techniques for mixed-size placement, we tune a state-of-the-art recursive bisection placer to betterhandle regular netlists that offer a convenient way to representmemories, datapaths and random-logic ip blocks. these modificationsand better whitespace distribution improve results on recentmixed-size placement benchmarks.
simulation and optimization of the power distribution network in vlsi circuits. in this paper, we present simulation techniques to estimate the worst-case voltage variation using a rc model for the power distribution network. pattern independent maximum envelope currents are used as a periodic input for performing the frequency-domain steady-state simulation of the linear rc circuit to evaluate the worst-case instantaneous voltage drop for the rc power distribution networks. the proposed technique unlike existing techniques, is guaranteed to give the maximum voltage drop at nodes in the rc power distribution network. we present experimental results to compare the frequency-domain and time-domain simulation techniques for estimating the maximum instantaneous voltage drop. we also present frequency domain sensitivity analysis based decoupling capacitance placement for reducing the voltage variation in the power distribution network. experimental results on circuits extracted from layout are presented to validate the simulation and optimization techniques.