waashk/dblp huggingface dataset:
optimal routing algorithms for pin clusters in high-density multichip modules. optimal routing algorithms for pin clusters in high-density multichip modules as the circuit densities and transistor counts are increasing, the package routing problem is becoming more and more challenging. in this paper, we study an important routing problem encountered in typical high-end mcm designs: routing within dense pin clusters. pin clusters are often formed by pins that belong to the same functional unit or the same data bus, and can become bottlenecks in terms of overall routability. topically, these clusters have irregular shapes, which can be approximated with rectilinear convex boundaries. since such boundaries have often irregular shapes, a traditional escape routing algorithm may give unroutable solutions. in this paper, we study how the positions of escape terminals on a convex boundary affect the overall routability. for this purpose, we propose a set of necessary and sufficient conditions to model routability outside a rectilinear convex boundary. given an escape routing solution, we propose an optimal algorithm to select the maximal subset of nets that are routable outside the boundary. after that, we focus on an integrated approach to consider routability constraints (outside the boundary) during the actual escape routing algorithm. here, we propose an optimal algorithm to find the best escape routing solution that satisfies all routability constraints. our experiments demonstrate that we can reduce the number of layers by 17% on the average, by using this integrated methodology.
a local circuit topology for inductive parasitics. a novel circuit topology for inductive coupling between interconnecting wires is presented. the model is local, i.e., only coupling between neighboring wires is explicitly modeled. however, the topology accounts for long-range coupling by propagating the vector potential from one wire to the next. examples of model calibration, both directly from layout and as model-order reduction of a given inductance matrix, are presented for simple wiring structures.
analytic modeling of interconnects for deep sub-micron circuits. closed form equations for second order transfer functions of generalarbitrarily-coupled rc trees with multiple drivers are reported.the models allow precise delay and noise calculations for systemsof coupled interconnects with guaranteed stability, and representthe minimum complexity associated with this class of circuits. thesimplicity, accuracy and generality of the models make them suitablefor use in early delay and noise planning of global signals incomplex systems.
pseudo-random testing and signature analysis for mixed-signal circuits. in this paper, we address the problem of functional testing of mixed-signal circuits using pseudo-random patterns. by embedding the linear, time-invariant (lti) analog circuit between a digital-to-analog converter (dac) and an analog-to-digital converter (adc), we can model the analog and converter circuitry as a digital lti system and test it using the pseudo-random vectors. we give mathematical analysis and formulate the pseudo-random testing process as the linear transformation of a random process by the analog lti device under test (dut). we choose the first and the second moments of the transformed random process, which are closely related to the functionality of the dut, as the signatures for fault detection. we show that such signatures can be estimated by proper arithmetic operations on the output responses of the dut to the vectors generated by lfsrs. we illustrate and compare the effectiveness of several possible choices of signatures, through analysis and experimental results of several circuits, in terms of their fault detection capabilities and the testing hardware requirements.
a comprehensive fault macromodel for opamps. in this paper, a comprehensive macromodel for transistor level faults in an operational amplifier is developed. with the observation that faulty behavior at output may result from interfacing error in addition to the faulty component, parameters associated with input and output characteristics are incorporated. test generation and fault classification are addressed for stand-alone opamps. a high fault coverage is achieved by a proposed testing strategy. transistor level short/bridging faults are analyzed and classified into catastrophic faults and parametric faults. based on the macromodels for parametric faults, faults simulation is performed for an active filter. we found many parametric faults in the active filter cannot be detected by traditional functional testing. a dft scheme alone with a current testing strategy to improve fault coverage is proposed.
area minimization for general floorplans. two methods for the area minimization problem in floorplanning are presented. these methods can be viewed as generalizations of stockmeyer's algorithm in the sense that they reduce to stockmeyer's algorithm for floorplans that are slicing. the present methods can also be applied to general floorplans. compared with the branch-and-bound algorithm, which is enumerative in nature and does not have any nontrivial performance bound for general floorplans, these methods are probably better than exhaustive methods for all the floorplans studied
area minimization for hierarchical floorplans. two results are presented in this paper. first we settle the open problem on the complexity of the area minimization problem for hierarchical floorplans by showing it to be n p-complete. we then present a pseudo-polynomial area minimization algorithm for hierarchical floorplans of order-5. the algorithm is based on a new algorithm for determining the set of nonredundant realizations of a wheel. the new algorithm for wheels has time cost o(k2logk) and space cost o(k2) if each of the (five) blocks in a wheel has at mostkrealizations&mdash;a reduction by a factor of k in both costs in comparison with previous algorithms. the area minimization algorithm was implemented. our experimental results show that the algorithm is indeed very fast.
an efficient and effective detailed placement algorithm. in the past few years, there has been a lot of research in the area of global placement. in comparison, not much attention has been paid to the detailed placement problem. existing detailed placers either fail to improve upon the excellent solution quality enabled by good global placers or are very slow. to handle the above problems, we focus on the detailed placement problem. we present an efficient and effective detailed placement algorithm to handle the wirelength minimization problem. the main contributions of our work are: (1) an efficient global swap technique to identify a pair of cells that can be swapped to reduce wirelength; (2) a flow that combines the global swap technique with other heuristics to produce very good wirelength; (3) an efficient single-segment clustering technique to optimally shift cells within a segment to minimize wirelength. on legalized mpl5 global placements on the ibm standard-cell benchmarks, our detailed placer can achieve 19.0%, 13.2% and 0.5% more wirelength reduction compared to fengshui5.0, rowironing and domino respectively. correspondingly we are 3.6/spl times/ 2.8/spl times/ and 15/spl times/ faster. on the ispd05 benchmarks (gi-joon nam et al., 2005), we achieve 8.1% and 9.1% more wirelength reduction compared to fengshui5.0 and rowironing respectively. correspondingly we are 3.1/spl times/ and 2.3/spl times/ faster.
memory bank customization and assignment in behavioral synthesis. with increasing design complexity and chip area, on-chip memory has become an important component whose integration needs to be addressed during system design. modern embedded dram technology allows for large amounts of on-chip memory space. however, in order to utilize the available memory intelligently, the memory has to be appropriately customized for the specific application. we address the topic of incorporating the application-specific customization of memory bank configuration into behavioral synthesis. the strategy involves a partitioning of behavioral arrays into memory banks based on a cost function that estimates the performance implications. for a given candidate partition, we present a heuristic for determining the access sequence that minimizes page misses in a bank while respecting data dependences. the output of the exploration is a graph displaying the variation of delay and memory area with the bank configuration. our experiments on several memory-intensive examples confirm that the exploration results can provide critical feedback to the designer about the optimal memory configuration for a given application.
an energy-conscious algorithm for memory port allocation. multiport memories are extensively used in modern system designs because of the performance advantages they offer. the increased memory access throughput could lead to significantly faster schedules in behavioral synthesis. however, they also have an associated area and energy penalty. we describe a technique for mapping data accesses to multiport memories during behavioral synthesis that results in significantly better energy characteristics than an unoptimized multiport design. the technique consists of an initial colouring of the array access nodes in the data flow graph based on spatial locality, followed by attempts to consecutively access memory locations with the same colour on the same port. our experiments on several applications indicate a significant reduction in address bus switching activity, leading to an overall energy reduction over an unoptimized design, while still maintaining a performance advantage over a single-port solution.
exploiting off-chip memory access modes in high-level synthesis. memory-intensive behaviors often contain large arrays that are synthesized into off-chip memories. with the increasing gap between on-chip and off-chip memory access delays, it is imperative to exploit the efficient access mode features of modern-day memories (e.g., page-mode drams) in order to alleviate the memory bandwidth bottleneck. our work addresses this issue by: (a) modeling realistic off-chip memory access modes for high-level synthesis (hls), (b) presenting algorithms to infer applicability of hls with these memory access modes, and (c) transforming input behavior to provide further memory access optimizations during hls. we demonstrate the utility of our approach using a suite of memory-intensive benchmarks with a realistic dram library module. experimental results show a significant performance improvement (more than 40\%) as a result of our optimization techniques.
who are the variables in your neighborhood. dynamic reordering techniques have had considerable success in reducing the impact of the initial variable order on the size of decision diagrams. sifting, in particular, has emerged as a very good compromise between low cpu time requirements and high quality of results. sifting, however, has the absolute position of a variable as the primary objective, and only considers the relative positions of groups of variables indirectly. in this paper we propose an extension to sifting that may move groups of variables simultaneously to produce better results. variables are aggregated by checking whether they have a strong affinity to their neighbors. (hence the title.) our experiments show an average improvement in size of 11%. this improvement, coupled with the greater robustness of the algorithm, more than offsets the modest increase in cpu time that is sometimes incurred.
symmetry detection and dynamic variable ordering of decision diagrams. knowing that some variables are symmetric in a function has numerous applications; in particular, it can help produce better variable orders for binary decision diagrams (bdds) and related data structures (e.g., algebraic decision diagrams). it has been conjectured that there always exists an optimum order for a bbd wherein symmetric variables are contiguous. we propose a new algorithm for the detection of symmetries, based on dynamic reordering, and we study its interaction with the reordering algorithm itself. we show that combining sifting with an efficient symmetry check for contiguous variables results in the fastest symmetry detection algorithm reported to date and produces better variable orders for many bdds. the overhead on the sifting algorithm is negligible.
static timing analysis considering power supply variations. power supply integrity verification has become a key concern in high performance designs. in deep submicron technologies, power supply noise can significantly increase the circuit delay and lead to performance failures. traditional static timing analysis which applies worst-case voltage margins to compute circuit delay leads to a very conservative analysis because the worst-case drop is localized to a small area of the die. in this paper, we propose a new approach for analyzing the impact of power supply variations on circuit delay. the circuit delay maximization problem is formulated as a constrained non-linear optimization problem which takes both ir and ldi/dt drops into account the proposed approach does not require apriori knowledge of critical paths in the circuit and can be effectively incorporated in an existing static timing analysis framework. the proposed method has been implemented and tested on iscas85 benchmark circuits and compared with the traditional methods for computing worst-case circuit delay under supply variations.
vectorless analysis of supply noise induced delay variation. the impact of power supply integrity on a design has become acritical issue, not only for functional verification, but also for performanceverification. traditional analysis has typically applied a worstcase voltage drop at all points along a circuit path which leads to avery conservative analysis. we also show that in certain cases, thetraditional analysis can be optimistic, since it ignores the possibilityof voltage shifts between driver and receiver gates. in this paper, wepropose a new analysis approach for computing the maximum pathdelay under power supply fluctuations. our analysis is based on theuse of superposition, both spatially across different circuit blocks,and temporally in time. we first present an accurate model of pathdelay variations under supply drops, considering both the effect oflocal supply reduction at individual gates and voltage shifts betweendriver/receiver pairs. we then formulate the path delay maximizationproblem as a constrained linear optimization problem, consideringthe effect of both ir drop and ldi/dt drops. we show how correlationsbetween currents of different circuit blocks can be incorporatedin this formulation using linear constraints. the proposed methodswere implemented and tested on benchmark circuits, including anindustrial power supply grid and we demonstrate a significantimprovement in the worst-case path delay increase.
efficient diagnosis of path delay faults in digital logic circuits. a new methodology involving effect-cause analysis has been demonstrated for the diagnosis of path delay faults. we seek to provide an improved understanding of the methods introduced in [6], with the goal of devising efficient representations and algorithms for the diagnosis of path delay faults. results indicate that the diagnostic resolution obtained is very high and includes all possible causes of the observed delay faults.
a test synthesis technique using redundant register transfers. this paper presents a test synthesis technique for behavioral descriptions. the technique is guided by two testability metrics which quantify the controllability and observability of behavioral variables and structural signals. the method is based on utilizing redundant register transfers in the data path to produce a test behavior with better controllability and observability properties. this approach can avoid unnecessary insertions of test structures in the data path. a test scheme for conditional statements has been developed involving minimal changes in the controller. our experimental results show improvements in fault coverage at modest hardware overhead.
i-copes: fast instruction code placement for embedded systems to improve performance and energy efficiency. the ratio of cache hits to cache misses in a computer system is, to a large extent, responsible for its characteristics such as energy consumption and performance. in recent years energy efficiency has become one of the dominating design constraints, due to the rapid growth in market share for mobile computing/communication/internet devices.in this paper we present a novel fast constructive technique that relocates the instruction code in such a manner into the main memory that the cache is utilized more efficiently. the technique is applied as a pre-processing step, i.e. before the code is executed. it is applicable for embedded systems where the number and characteristics of tasks running on the system is know a priori. the technique does not impose any computational overhead to the system. as a result of applying our technique to a variety of real-world applications we measured (through simulation) that the number of cache misses drops significantly. further, this reduces the energy consumption of a whole system (cpu, caches, buses, main memory) by up to 65% at an only slightly increased memory size of 13% on average.
fast cycle-accurate behavioral simulation for pipelined processors using early pipeline evaluation. modeling and simulating pipelined processors in procedurallanguages such as c/c++ requires lots of cost in handlingconcurrent events, which hinders fast simulation. a number ofresearches on simulation have devised speed-up techniques toreduce the number of events. this paper presents a newsimulation approach developed to enhance the simulation ofpipelined processors. the proposed approach is based on earlypipeline evaluation that all the intermediate values of aninstruction are computed in advance, creating a future state for thenext instructions. the future state allows the next instructions tobe computed without considering data dependencies betweennearby instructions. we apply this concept to building a cycle-accurate simulator for a pipelined risc processor and achieve almost the same speed as the instruction-level simulator.
rtl sat simplification by boolean and interval arithmetic reasoning. we present a method that combines interval-arithmetic (ia) and boolean reasoning with structural hashing for simplifying sat problems on circuits expressed at the register-transfer level. we demonstrate that simple transformations based on interval-arithmetic operations can significantly reduce the complexity of the problem. we identify cases where the inherent over-approximations in ia operations can be reduced. we demonstrate that these techniques can significantly reduce rtl-sat instances in size and runtime.
convertibility verification and converter synthesis: two faces of the same coin. an essential problem in component-based design is how to compose components designed in isolation. several approaches have been proposed for specifying component interfaces that capture behavioral aspects such as interaction protocols, and for verifying interface compatibility. likewise, several approaches have been developed for synthesizing converters between incompatible protocols. in this paper, we introduce the notion of adaptability as the property that two interfaces have when they can be made compatible by communicating through a converter that meets specified requirements. we show that verifying adaptability and synthesizing an appropriate converter are two faces of the same coin: adaptability can be formalized and solved using a game-theoretic framework, and then the converter can be synthesized as a strategy that always wins the game. finally we show that this framework can be related to the rectification problem in trace theory.
push-up scheduling: optimal polynomial-time resource constrained scheduling for multi-dimensional applications. multi-dimensional computing applications, such as image processing and fluid dynamics, usually contain repetitive groups of operations represented by nested loops. the optimization of such loops, considering processing resource constraints, is required to improve their computational time. this study presents a new technique, called push-up scheduling, able to achieve the shortest possible schedule length in polynomial time. such technique transforms a multi-dimensional data flow graph representing the problem, while assigning the loop operations to a schedule table in such a way to occupy, legally, any empty spot. the algorithm runs in o(n|e|) time, where n is the number of dimensions of the problem, and |e| is the number of edges in the graph.
reducing cache misses by application-specific re-configurable indexing. the predictability of memory access patterns in embedded systems can be successfully exploited to devise effective application-specific cache optimizations. in this work, we propose an improved indexing scheme for direct-mapped caches, which drastically reduces the number of conflict misses by using application-specific information; the scheme is based on the selection of a subset of the address bits. with respect to similar approaches, our solution has two main strengths. first, it models the misses analytically by building a miss equation, and exploits a symbolic algorithm to compute the exact optimum solution (i.e., the subset of address bits to be used as cache index that minimizes conflict misses). second, we designed a re-configurable bit selector, which can be programmed at run-time to fit the optimal cache indexing to a given application. results show an average reduction of conflict misses of 24%, measured over a set of standard benchmarks, and for different cache configurations.
statistical behavioral modeling and characterization of a/d converters. this paper presents a method to characterize nyquist rate a/d converters based on the use of a first order statistical behavioral model. the proposed model is derived from a very basic statistical interpretation of the conversion operation which contemplates noise and statistical process variations effects on traditional converter parameters. both dc and dynamic converter parameters can be easily measured. the applicability of the proposed method is illustrated with two different examples. the first serves to show the possibility of deriving the statistical behavioral model from real measured data, and to prove the correctness of the model by comparing results to those obtained with traditional deterministic models. the second example illustrates the incorporation of the model in the mixed-signal simulator eldo [6]. the obtained results show that despite the model's simplicity, it is very efficient for quick and complete simulation of data converters.
compiler-based register name adjustment for low-power embedded processors. we present an algorithm for compiler-driven register name adjustmentwith the main goal of power minimization on instruction fetchand register file access. in most instruction set architecture (isa) designs,the register fields reside in fixed positions within the instructionencoding, hence forming streams of indices on the instruction bus andto the register file address decoder. the number of bit transitions inthese streams greatly determines the power consumption on the addressbus and the register file decoder. while general-purpose registersare semantically indistinguishable and hence interchangeable,the particular register indices do have a direct impact on power consumption.the algorithms presented in this paper address this powerminimization problem by reassigning/encoding the registers so thatthe bit transitions within the register index streams are minimized.