waashk/dblp huggingface dataset:
code restructuring for improving cache performance of mpsocs. one of the critical goals in code optimization for mpsoc architectures is to minimize the number of off-chip memory accesses. this is because such accesses can be extremely costly from both performance and power angles. while conventional data locality optimization techniques can be used for improving data access pattern of each processor independently, such techniques usually do not consider locality for shared data. this paper proposes a strategy that reduces the number of off-chip references due to shared data. it achieves this goal by restructuring a parallelized application code in such a fashion that a given data block is accessed by parallel processors within the same time frame, so that its reuse is maximized while it is in the on-chip memory space. this tends to minimize the number of off-chip references since the accesses to a given data block are clustered within a short period of time during execution. our approach employs a polyhedral tool that helps us isolate computations that manipulate a given data block.
area and power reduction of embedded dsp systems using instruction compression and re-configurable encoding. in this paper, we propose a reconfiguration mechanism that allows multiple instruction compression to reduce both code size, which in turn reduces the cost, and (instruction fetch) power, which enhances the battery lifetime, two key considerations in embedded dsp systems. we enhance texas instruments dsp core tms320c27x to incorporate this mechanism and evaluate the improvements on code size and instruction fetch energy using real life embedded control application programs. we show that even with minimal hardware overhead, we can improve code size by over 10% and instruction fetch energy by over 40%.
runtime integrity checking for inter-object connections. ensuring integrity of heap resident data is critical for many embedded systems. ever-scaling process technology combined with power-saving techniques employed in embedded systems is increasing vulnerability of such systems to hardware-related errors such as soft errors. while such errors are transient and do not harm the architecture, they can corrupt data. in this study, we explore solutions to the inter-object connectivity problem in heap memory of java-based embedded environments. our objective is to ensure that the connections between the objects are consistent. in particular, we want to detect the cases where an inter-object link disappears or points to a wrong object. to address this problem, we propose a rule based approach, where the application programmer expresses the important connectivity rules to be satisfied using a special rule language, and a modified jvm (java virtual machine) checks these rules at runtime.
a power aware system level interconnect design methodology for latency-insensitive systems. latency-insensitive interconnects require first-in-first-out buffers (fifo) for flow-control and storage. interconnect delays are not scaling in proportion to the clock period and hence multiple stages of fifos will be needed for high performance interconnects. fifos in the interconnect are a significant contributor to the total power consumption. in this work, we propose a design methodology to synthesize a low power interconnect channel containing series connected fifos for latency-insensitive systems. our approach is the first to consider and simultaneously optimize the channel clock frequency, voltage and the fifo sizes to minimize the power consumption. for small problem size, we show that our approach finds solutions which are close to optimal. the power aware interconnect channel synthesis is affected by the system parameters like the data production rate and data consumption rate. the choice of optimal channel clock frequency, voltage and fifo sizes can lead to power savings as high as 77.7%, 83.6% and 87% for a 3 stage, 4 stage and a 5 stage channel respectively.
multilevel expansion-based vlsi placement with blockages. the rapid growth of system-on-chip designs makes it a necessity for physical design tools to efficiently handle the coexistence of large intellectual property (ip) blocks and small standard cells in a single design. in this work, we present an efficient expansion-based placer to address standard-cell placement problem in the presence of blockages induced by pre-placed ip blocks. expansion refers to the process during which cells are gradually distributed over a specified region. we implement expansion in a new placer by enhancing a quadratic placement technique based on fixed-point addition originally presented by b. hu and m. marek-sadowska (2003), where fixed points were defined as dimensionless pseudo cells, and were deliberately introduced into the circuit to pull cells from one location to another. the new placer not only produces very competitive placement results over multiple sets of public-domain benchmarks with conventional rectangle-like chip boundary, but also efficiently handles the existence of blockages. especially, we develop three expansion strategies and use them under different blockage settings.
congestion minimization during placement without estimation. this paper presents a new congestion minimization technique for standard cell global placement. the most distinct feature of this approach is that it does not follow the traditional "estimate-then-eliminate" strategy. instead, it avoids the excessive usage of routing resources by the "local" nets so that more routing resources are available for the uncertain "global" nets. the experimental results show that our new technique, sparse, achieves better routability than the traditional total wire length (bounding box) guided placers, which had been shown to deliver the best routability results among the placers optimizing different cost functions [2]. another feature of sparse is the capability of allocating white space implicitly. sparse exploits the well known empirical rent's rule and is able to improve the routability even more in the presence of white space. compared to the most recent academic routability-driven placer dragon[8], sparse is able to produce solutions with equal or better routability.
hyper-lp: a system for power minimization using architectural transformations. an automated high-level synthesis system, hyper-lp, for minimizing power consumption in application-specific datapath-intensive cmos circuits using a variety of architectural and computational transformations is presented. the sources of power consumption are reviewed, and the effects of architectural transformations on the various power components are presented. the synthesis environment consists of high-level estimation of power consumption, a library of transformation primitives (local and global), and heuristic/probabilistic optimization search mechanisms for fast and efficient scanning of the design space. examples with varying degree of computational complexity and structures are optimized and synthesized. the results indicate that an order of magnitude reduction in power can be achieved over current-day design methodologies while maintaining the system throughput; in some cases, this can be accomplished while preserving or reducing the implementation area
high-level scheduling model and control synthesis for a broad range of design applications. this paper presents a versatile scheduling model and an efficient control synthesis methodology which enables architectural (high-level) design/synthesis systems to seamlessly support a broad range of architectural design applications from datapath-dominated digital signal processing (dsp) to micro-processors/controllers and control-dominated peripherals, utilizing multi-phase clocking schemes, multiple threading, data-dependent delays, pipelining, and combinations of the above. the work presented in this paper is an enabling technology for high-level synthesis to go beyond traditional datapath-dominated dsp applications and to start becoming a viable and cost-effective design methodology for commodity ics such as micro-processors/controllers and control-dominated peripherals.
cdma/fdma-interconnects for future ulsi communications. future inter- and intra-ulsi interconnect systems demand extremely high data rates as well as bidirectional multi-i/o concurrent service, reconfigurable computing/processing architecture, and total compatibility with mainstream silicon soc (system-on-chip) and sip (system-in-package) technologies. in this talk, we review recent advances in cdma and fdma interconnect schemes that promise to meet all of the above system requirements. the physical transmission line is no longer limited to a direct-coupled metal wire. rather, it can be accomplished via either wired or wireless mediums through capacitor couplers that reduce the baseband noise and dc power consumption. these new advances in interconnect schemes would fundamentally alter the paradigm of ulsi data communications and enable the design of next generation computing/processing systems.
towards true crosstalk noise analysis. accurate noise analysis is currently of significant concern to high-performance designs, and the number of signals susceptible to noise effects will certainly increase in smaller process geometries. our approach uses a combination of temporal and functional information to eliminate false transition combinations and thereby overcome insufficiencies in static noise analysis. a similar idea arises in timing analysis where functional and timing information is used to eliminate false paths. the goal of our work is to develop an algorithm, software tool, and noise analysis flow that provide an accurate and conservative approach to noise analysis. in particular, this paper proposes an approach to identifying a pair of vectors that exercises the maximum crosstalk noise.
simulation-based bug trace minimization with bmc-based refinement. finding the cause of a bug can be one of the most time-consuming activities in design verification. this is particularly true in the case of bugs discovered in the context of a random simulation- based methodology, where bug traces, or counter-examples, may contain several hundred thousand cycles. in this work we propose butramin, a bug trace minimizer. butramin considers a bug trace produced by a random simulator or a semi-formal verification software and produces an equivalent trace of shorter length. butramin applies a range of minimization techniques, deploying both simulation-based and formal methods, with the objective of producing highly reduced traces that still expose the original bug. we evaluated butramin on a range of designs, including the publicly available picojava microprocessor. our experiments show that in most cases butramin is able to reduce traces to a small fraction of their initial size, in terms of cycle length and signals involved.
miller factor for gate-level coupling delay calculation. in coupling delay computation, a miller factor of more than 2x may be necessary to account for active coupling capacitance when modeling the delay of deep submicron circuitry in the presence of active coupling capacitance. we propose an efficient method to estimate this factor such that the delay response of a decoupling circuit model can emulate the original coupling circuit. under the assumptions of zero initial voltage, equal charge transfer, and 0.5vdd as the switching threshold voltage, an upper bound of 3x for maximum delay and a lower bound of -1x for minimum delay can be proven. efficient newton-raphson iteration is also proposed as a technique for computing the miller factor or effective capacitance. this result is highly applicable to crosstalk coupling delay calculation in deep submicron gate-level static timing analysis. detailed analysis and approximation are presented. spice simulations are demonstrated to show high correlation with these approximations.
induction-based gate-level verification of multipliers. we propose a method based on unrolling the inductive definition of binary number multiplication to verify gate-level implementations of multipliers. the induction steps successively reduce the size of the multiplier under verification. through induction, the verification of an n-bit multiplier is decomposed into n equivalence checking problems. the resulting equivalence checking problems could be significantly sped up by simple structural analysis. this method could be generalized to the verification of more general arithmetic circuits and the equivalence checking of complex data-path.
switching window computation for static timing analysis in presence of crosstalk noise. crosstalk effect is crucial for timing analysis in very deep submicron design. in this paper, we present and compare multiple scheduling algorithms to compute switching windows for static timing analysis in presence of crosstalk noise. we also introduce an efficient technique to evaluate the worst case alignment of multiple aggressors.
synthesis for multiple input wires replacement of a gate for wiring consideration. the alternative wire technique attempts to replace a target wire by another wire without charging the logic functionality. in this paper, we propose two new transformations of replacing wires. one transformation simultaneously replaces multiple input wires of a gate by a new set of input wires and the other performs gate decompostion during the alternative wire process. to accomplish such complex transformations, we discuss some theoretical foundations for replacing multiple wires. understanding how wires/gates can be replaced by other wires/gates allows us to speedup the process tremendously.
refining switching window by time slots for crosstalk noise calculation. for crosstalk noise calculation, computing switching windows of a net helps us identify noise sources accurately. traditional approaches use a single continuous switching window for a net. under this model, signal switching is assumed to happen any time within the window. although conservative and sound, this model can result in too much pessimism since in reality the exact timing of signal switching is determined by a path delay up to the net, i.e. the underlying circuit structure does not always allow signal switching at arbitrary time within the continuous switching window. to address this inherent inaccuracy of the continuous switching window, we propose a refinement of the traditional approaches, where signal switching is characterized by a set of discontinuous switching windows instead of a single continuous window. each continuous switching window is divided into multiple windows, called time slots, and the signal switching activity of each slot is analyzed separately to calculate the maximum noise with more accuracy. by controlling the size of a time slot we can trade off accuracy and runtime, which makes this approach highly scalable. we have confirmed by experiments on industrial circuits that up to 90% of the noise violations detected by the traditional approach can be unreal.
array composition and decomposition for optimizing embedded applications. optimizing array accesses is extremely critical in embedded computingas many embedded applications make use of arrays (in formof images, video frames, etc). previous research considered bothloop and data transformations for improving array accesses. however,data transformations considered were mostly limited to lineardata transformations and array interleaving. in this paper, we introducetwo data transformations: array decomposition (breaking upa large array into multiple smaller arrays) and array composition(combining multiple small arrays into a single large array). thispaper discusses that it is feasible to implement these optimizationswithin an optimizing compiler.
using constraint geometry to determine maximum rate pipeline clocking. geometric knowledge of the shape of the feasible region formed by pulse width, setup, and hold constraints is used directly by an efficient (cubic complexity) algorithm, gpipe, to determine the maximum rate for single-phase clocking of a given pipeline. the pipeline model uses level-sensitive latches as synchronizers and can allow wave pipelining. gpipe is also used to explore the effect of removing nonsynchronizing and/or synchronizing latches on the maximum clock speed of the pipeline. a simple test shows which latches, if any, to remove in order to guarantee no decrease, and permit a possible increase, in the clock rate
the associative-skew clock routing problem. we introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. the associative skew problem is easier to address within current eda frameworks than useful-skew (skew-scheduling) approaches, and defines an interesting tradeoff between the traditional zero-skew clock routing problem (one sink group) and the steiner minimum tree problem (n sink groups). we present a set of heuristic building blocks, including an efficient and optimal method of merging two zero-skew trees such that zero skew is preserved within the sink sets of each tree. finally, we list a number of open issues for research and practical application.
fast boolean optimization by rewiring. this paper presents a very efficient boolean logic optimization method. the boolean optimization is achieved by adding and removing redundant wires in a circuit. our algorithm applies the reasoning of automatic test pattern generation (atpg) which can detect redundancy efficiently. during the atpg process, mandatory assignments are assignments which must be satisfied. our algorithm analyzes different characteristics of mandatory assignments during the atpg process. new theoretical results based on the analysis are presented which lead to significant performance improvements. the fast run time and the excellent scaling to large problems make our boolean optimization method practical for industrial applications. experiments show that the optimization results are comparable to those of kunz and pradhan (1994) while the run time is two orders of magnitude faster (average 126x speed up). furthermore, we report optimization results for several large examples, which were previously thought to be too large to be handled by boolean optimization methods.
a coloring approach to the structural diagnosis of interconnects. this paper presents a new approach for diagnosing stuck-at and short faults in interconnects whose layouts are known. this structural approach exploits different graph coloring and coding techniques to generate a test set with no aliasing and confounding. the conditions for aliasing and confounding are analyzed with respect to the size and number of the shorts in the fault set. the characteristics of unbalanced/balanced codes for encoding the colors in the vector generation process for interconnect diagnosis are discussed and proved using a novel algebra. an algorithm for diagnosis is then presented.
supreme: substrate and power-delivery reluctance-enhanced macromodel evaluation. the recent demand for system-on-chip rf mixed-signal designand aggressive supply-voltage reduction require chip-level accurateanalysis of both the substrate and power delivery systems.together with the rising frequency, low-k dielectric, copper interconnects,and high conductivity substrate, the inductance effectsraised serious concern recently.however, the increasing designcomplexity creates tremendous challenges for chip-level power-deliverysubstrate co-analysis.in this paper, we propose a noveland efficient reluctance-based passive model order reduction techniqueto serve these tasks.our work, supreme(substrate andpower-delivery reluctance-enhanced macromodel evaluation) notonly greatly reduces the computational complexity of previousreluctance-based model order algorithms but is also capable ofhandling large number of noise sources efficiently.to facilitatethe analysis of inductive substrate return paths and evaluate thehigh-frequency substrate coupling effects, we derive a novel rlkcsubstrate model from maxwell's equations for the first time.experimentalresults demonstrate the superior runtime and accuracyof supreme compared to the traditional mna-based simulation.
single-pass redundancy addition and removal. redundancy-addition-and-removal is a rewiring technique which for a given target wire wt finds a redundant alternative wire wa. addition of wa makes wt redundant and hence removable without changing the overall circuit functionality. incremental logic restructuring based on this technique has been used in many applications. however, the search for valid alternative wires requires trial-and-error redundancy testing of a potentially large set of candidate wires. in this paper, we study the fundamental theory behind this technique and propose a new reasoning scheme which directly identifies alternative wires without performing trial-and-error tests. experimental results show up to 15 times speedup in comparison to the best techniques in literature.
inductwise: inductance-wise interconnect simulator and extractor. we develop a robust, efficient, and accurate tool, which integrates inductance extraction and simulation, called inductwise. this paper advances the state-of-the-art inductance extraction and simulation techniques and contains two major parts. in the first part, inductwise extractor, we discover the recently proposed inductance matrix sparsification algorithm, the k-method[1], albeit its great benefits of efficiency, has a major flaw on the stability. we provide both a counter example and a remedy for it. a window section algorithm is also presented to preserve the accuracy of the sparsification method. the second part, inductwise simulator, demonstrates great efficiency of integrating the nodal analysis formulation with the improved k-method. experimental results show that inductwise has over 250x speedup compared to spice3. the proposed sparsification algorithm accelerates the simulator another 175x and speeds up the extractor 23.4x within 0.1% of error. inductwise can extract and simulate an 118k-conductor rkc circuit within 18 minutes. it has been well tested and released on the web for public usage. (http://vlsi.ece.wisc.edu/inductwise.htm)
atpg-based logic synthesis: an overview. the ultimate goal of logic synthesis is to explore implementation flexibility toward meeting design targets, such as area, power, and delay. traditionally, such flexibility is expressed using "don't cares" and we seek the best implementation that does not violate them. however, the calculation and storing of don't care information is cpu and memory-intensive. in this paper, we give an overview of logic synthesis approaches based on techniques developed for automatic test pattern generation (atpg). instead of calculating and storing don't cares explicitly, atpg-based logic synthesis techniques calculate the flexibility implicitly. low cpu and memory usage make those techniques applicable for practical industrial circuits. also, the basic atpg-based logic level operations create predictable, small layout perturbations, making an ideal foundation for efficient physical synthesis. theoretical results show that an efficient, yet simple add-a-wire-and-remove-a-wire operation covers all possible complex logic transformations.