waashk/dblp huggingface dataset:
sapor: second-order arnoldi method for passive order reduction of rcs circuits. the recently-introduced susceptance element exhibits many prominent features in modeling the on-chip magnetic couplings. for an rcs circuit, it is better to be formulated as a second-order system. therefore, corresponding mor (model-order reduction) techniques for second-order systems are desired to efficiently deal with the ever-increasing circuit scale and to preserve essential model properties. we first review the existing mor methods for rcs circuits, such as enor and smor, and discuss several key issues related to numerical stability and accuracy of the methods. then, a technique, sapor (second-order arnoldi method for passive order reduction), is proposed to effectively address these issues. based on an implementation of a generalized second-order arnoldi method, sapor is numerically stable and efficient. meanwhile, the reduced-order system also guarantees passivity.
memory bank and register allocation in software synthesis for asips. an architectural feature commonly found in digital signal processors (dsps) is multiple data-memory banks. this feature increases memory bandwidth by permitting multiple memory accesses to occur in parallel when the referenced variables belong to different memory banks and the registers involved are allocated according to a strict set of conditions. unfortunately, current compiler technology is unable to take advantage of the potential increase in parallelism offered by such architectures. consequently, most application software for dsp systems is hand-written -- a very time-consuming task.we present an algorithm which attempts to maximize the benefit of this architectural feature. while previous approaches have decoupled the phases of register allocation and memory bank assignment, our algorithm performs these two phases simultaneously. experimental results demonstrate that our algorithm substantially improves the code quality of many compiler-generated and even hand-written programs.
reconfigurable machine and its application to logic diagnosis. it is pointed out that in the reconfigurable machine (rm) highly flexible architecture combining field-programmable gate arrays (fpgas) with rams supports a wide range of applications. since its gate-level programmability allows implementation of various kinds of parallel processing techniques, rm provides a performance comparable to that of existing special-purpose engines. a reconfigurable machine prototype (rmp) has been built as the first prototype incorporating five fpga and four sram memory banks. rmp has been applied to logic diagnosis and a logic simulator. the concept of rm may be the best solution to the trade-offs between general-purpose and special-purpose machines. rm will be a hardware platform accelerating a wide range of applications, and also offering an interesting problem in high-level synthesis
design of system interface modules. a design methodology and high-level synthesis techniques for integrating hardware modules into a system are presented. the interface between modules, which can obey arbitrary protocols, is generated from a high-level specification developed especially for describing intermodule communication. central to the design methodology are libraries which contain system-level module generators and a strategy to capture the protocol and timing information necessary for interface synthesis. the main impact of this work is raising the interface design abstraction and reducing the effort required from a designer to produce a system using various ic technologies
crosstalk fault detection by dynamic idd. undesired capacitive crosstalk between signals is expected to be a significant concern in deep submicron circuits. new test techniques are needed for these crosstalk faults since they may cause unacceptable performance degradation. we analyze the impact of crosstalk faults on a circuit's power dissipation. crosstalk faults can be detected by monitoring the dynamic supply current. the test method is based on a recently developed dynamic idd test metric, the energy consumption ratio (ecr). ecr-based test has been shown to be effective at tolerating the impact of process variations. in this paper, we apply a ecr-based test method called ecr-vdd test to detect the crosstalk faults. the effectiveness of the method is demonstrated by simulation results.
synthesis of custom processors based on extensible platforms. efficiency and flexibility are critical, but often conflicting, design goals in embedded system design. the recent emergence of extensible processors promises a favorable tradeoff between efficiency and flexibility, while keeping design turnaround times short. current extensible processor design flows automate several tedious tasks, but typically require designers to manually select the parts of the program that are to be implemented as custom instructions.in this work, we describe an automatic methodology to select custom instructions to augment an extensible processor, in order to maximize its efficiency for a given application program. we demonstrate that the number of custom instruction candidates grows rapidly with program size, leading to a large design space, and that the quality (speedup) of custom instructions varies significantly across this space, motivating the need for the proposed flow. our methodology features cost functions to guide the custom instruction selection process, as well as static and dynamic pruning techniques to eliminate inferior parts of the design space from consideration. further, we employ a two-stage process, wherein a limited number of promising instruction candidates are first selected, and then evaluated in more detail through cycle-accurate instruction set simulation and synthesis of the corresponding hardware, to identify the custom instruction combinations that result in the highest program speedup or maximize speedup under a given area constraint.we have evaluated the proposed techniques using a state-of-the-art extensible processor platform, in the context of a commercial design flow. experiments with several benchmark programs indicate that custom processors synthesized using automatic custom instruction selection can result in large improvements in performance (upto 5.4x, average of 3.4x), energy (upto 4.5x, average of 3.2x), and energy-delay product (upto 24.2x, average of 12.6x), while speeding up the design process significantly.
a scalable application-specific processor synthesis methodology. custom processors based on application-specific ordomain-specific instruction sets are gaining popularity, and areoften used to implement critical architectural blocks in complex system-on-chips. while several advances have been madein custom processor architectures, tools, and design methodologies, designers are still required to manually perform somecritical tasks, such as selection of the custom instructions bestsuited to the given application and design constraints.we present a scalable methodology for the synthesis of acustom processor from an embedded software program. a keyfeature of the proposed methodology is its scalability, whichis achieved by exploiting the structured, hierarchical natureof large software programs. we motivate the need for such amethodology, and describe the algorithms used for the criticalsteps, including hardware resource budgeting, local optimizations, and global exploration. our methodology utilizes the concept of "soft" instruction templates, which can be adapted by adding operations to them or deleting operations from them at any time during the design space exploration process, allowing for global design decisions to be interleaved with fine-grained optimizations.we have integrated our methodology in an open source compiler, and verified it using a commercial extensible processor. experiments with several benchmarks indicate that ourmethodology can effectively tackle large programs. it resultedin the synthesis of high-quality custom processors that demonstrated an average speedup of 2.61x and a maximum speedupof 6.32x. the cpu times required for custom processor synthesis were quite small, indicating that the proposed techniquescan be applied to embedded software programs of significantcomplexity.
a loosely coupled parallel algorithm for standard cell placement. we present a loosely coupled parallel algorithm for the placement of standard cell integrated circuits. our algorithm is a derivative of simulated annealing. the implementation of our algorithm is targeted towards networks of unix workstations. this is the very first reported parallel algorithm for standard cell placement which yields as good or better placement results than its serial version. in addition, it is the first parallel placement algorithm reported which offers nearly linear speedup, in terms of the number of processors (workstations) used, over the serial version. despite using the rather slow local area network as the only means of interprocessor communication, the processor utilization is quite high, up to 98% for 2 processors and 90% for 6 processors. the new parallel algorithm has yielded the best overall results ever reported for the set of mcnc standard cell benchmark circuits.
marsh: min-area retiming with setup and hold constraints. this paper describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle both setup and hold constraints. given a circuit g and a target clock period c, our algorithm either outputs a retimed version of g satisfying setup and hold constraints or reports that such a solution is not possible, in &ogr;(|v3|log|v|log(|v|c)) steps, where |v| corresponds to number of gates in the circuit and c is equal to the number of registers in the circuit. this is the first polynomial time algorithm ever reported for min-area retiming with constraints on both long and short-paths. an alternative problem formulation that takes practical issues in to consideration and lowers the problem complexity is also developed. both the problem formulations have many parallels with the original formulation of long-path only retiming by leiserson and saxe and all the speed improvements that have been obtained on that technique are likely to be valid for improving the performance of the technique described in this paper.
mosaic: a tile-based datapath layout generator. it is pointed out that mosaic achieves a routing technique based on bus patterns preplaced all over the leaf cell and joins these segments based on module schematic information. with this routing technique, a high layout density can be achieved. the layout density of the 120-mhz micro-processor datapath module was 10000-20000 transistors/mm2 in 0.5-&mu;m three-metal bicmos technology. leaf cells are not used only in one module design, but are reusable across multiple module designs. only 100 kinds of leaf cells were needed for 300 module designs
hardware scheduling for dynamic adaptability using external profiling and hardware threading. while performance, area, and power constraints have been thedriving force in designing current communication-enabled embeddedsystems, post-fabrication and run-time adaptability is now required.two dominant configurable hardware platforms are processorsand fpgas. however, for compute-intensive applications,neither platform delivers the needed performance at the desiredlow power. the need thus arises for custom, application-specificconfigurable (asc) hardware.this paper addresses the optimization of asc hardware. ourtarget application areas are multimedia and communication wherean incoming packet (task) is processed independently of otherpackets. we innovatively utilize two concepts: external profilingand hardware threading. we utilize an m/m/c queueing model toprofile task arrival patterns and show how profiling guides designdecisions. we introduce the novel concept of hardware threadingwhich allows on-the-fly borrowing of unutilized hardware, thusmaximizing task-level parallelism, to either boost performance orto lower power consumption. we present a scheduling algorithmthat synthesizes a hardware-threaded architecture, and discuss experimentalresults that illustrate adaptability to different workloads,and performance/power trade-offs.
generalized network flow techniques for dynamic voltage scaling in hard real-time systems. energy consumption is an important performance parameter forportable and wireless embedded systems. however, energy consumptionmust be carefully balanced with real-time responsivenessin hard real-time systems. we present an optimal offline dynamicvoltage scaling (dvs) scheme for dynamic power management insuch systems. a generalized network flow model for the uniprocessordvs problem is developed and solved optimally using an efficientnetwork flow algorithm. the proposed method outperformsexisting dvs schemes for several popular embedded processorswhere the number of processor speeds is limited to a few values.the gnf model provides theoretical lower bounds on energy consumptionusing dvs in hard real-time systems.
incremental formal design verification. language containment is a method for design verification that involves checking if the behavior of the system to be verified is a subset of the behavior of the specifications (properties or requirements), which it has to meet. if this check fails, language containment returns a subset of &ldquo;fair&rdquo; states involved in behavior that the system exhibits but the specification does not. current techniques for language containment do not take advantage of the fact that the process of design is incremental; namely that the designer repeatedly modifies and re-verifies his/her design. this results in unnecessary and cumbersome computation. we present a method, which successively modifies the latest result of verification each time the design is modified. our incremental algorithm translates changes made by the designer to an addition or subtraction of edges, states or constraints (on acceptable behavior) from the transition behavior or specification of the problem. next, these changes are used to update the set of &ldquo;fair&rdquo; states previously computed. this incremental algorithm is superior to the current techniques for language containment; a conclusion supported by the experimental results presented in this paper.
fast field solver-programs for thermal and electrostatic analysis of microsystem elements. to solve the problem of fast thermal and electrostatic simulation of microsystem elements two different field solver tools have been developed at tub. the us-thermanal program is capable for the fast steady state and dynamic simulation of suspended multi-layered microsystem structures, while the 2d-sunred program is the first version of a general field solver program, based on an original method, the successive network reduction. this program offers a very fast and accurate substitute of fem programs for the solution of the poisson equation, e.g. solving a 32000 grid problem in about 6 minutes on a 586 pc. application examples show the usability of the tools.
verifying clock schedules. timing verification and optimization have been formulated as mathematical programming problems. the computational aspects of using such a formulation for verifying clock schedules are considered. the formulation can have multiple solutions, and these extraneous solutions can cause previously published algorithms to produce incorrect or misleading results. the conditions under which multiple solutions exist are characterized, and it is shown that even when the solution is unique, the running times of these previous algorithms can be unbounded. by contrast, a simple polynomial time algorithm for clock schedule verification is exhibited. the algorithm was implemented and used to check the timing of all the circuits in the iscas-89 benchmark suite. observed running times are linear in circuit size and quite practical
sat based atpg using fast justification and propagation in the implication graph. in this paper we present new methods for fast justification and propagation in the implication graph (ig) which is the core data structure of our sat based implication engine. as the ig model represents all information on the implemented logic function as well as the topology of a circuit, the proposed techniques inherit all advantages of both general sat based and structure based approaches to justification, propagation, and implication. these three fundamental boolean problems are the main tasks to be performed during automatic test pattern generation (atpg) such that the proposed algorithms are incorporated into our atpg tool tip which is built on top of the implication engine.working exclusively in the ig, the complex functional operations of justification, propagation, and implication reduce to significantly simpler graph algorithms. they are easily extended to exploit bit-parallel techniques. as the ig is automatically generated for arbitrary logics the algorithms remain applicable independent of the required logic. this allows processing of various fault models using the same engine. that is, the presented ig based methods offer a complete and versatile framework for rapid development of new atpg tools that target emerging fault models such as cross-talk, delay or bridging faults. tip currently handles stuck-at as well as various delay fault models. furthermore, the proposed methods are used within tools for boolean equivalence checking, optimization of netlists, timing analysis or retiming (reset state computation).in order to demonstrate the performance of ig based atpg, i.e. justification and propagation in the ig, we provide experimental results for stuck-at and path delay fault models. they show that tip outperforms the state-of-the-art in sat based and structure based atpg.
a sat-based implication engine for efficient atpg, equivalence checking, and optimization of netlists. the paper presents a flexible and efficient approach to evaluating implications as well as deriving indirect implications in logic circuits. evaluation and derivation of implications are essential in atpg, equivalence checking, and netlist optimization. contrary to other methods, the approach is based on a graph model of a circuit's clause description called implication graph. it combines both the flexibility of sat-based techniques and high efficiency of structure based methods. as the proposed algorithms operate only on the implication graph, they are independent of the chosen logic. evaluation of implications and computation of indirect implications are performed by simple and efficient graph algorithms. experimental results for various applications relying on implication demonstrate the effectiveness of the approach.
a statistical approach to estimate the dynamic non-linearity parameters of pipeline adcs. a fully-analytical approach to estimate the statistics ofdynamic non-linearity parameters of pipeline analog-to-digitalconverters (adcs) in the presence of circuit non-idealitiesincluding capacitance mismatches and non-idealopamps is presented. these parameters include the spurious-freedynamic range (sfdr) and the signal to noise-and-distortionratio (sndr). the simple closed-form formulasfor sfdr and sndr presented here are useful for designautomation of highly-linear pipeline adcs in order toextract the required values for the circuit-level specificationsof the sub-blocks of converters. behavioral simulations arepresented to show the accuracy of the proposed equations.
a mapping algorithm for defect-tolerance of reconfigurable nano-architectures. self-assembled nano-fabrication processes yield regular and reconfigurable devices. however, defect densities in this emerging nanotechnology are higher than those in conventional lithography-based vlsi. in this paper, we present a defect-tolerant design flow to minimize customized post-fabrication design efforts to be performed per chip. we also present a greedy o(n log n) mapping algorithm which makes the connection between defect-unaware design steps and the final defect-aware step. experiments show that the results obtained by this algorithm are very close to the exact solutions.
low power state assignment targeting two-and multi-level logic implementations. the problem of minimizing power consumption during the state encoding of a finite state machine is considered. a new power cost model for state encoding is proposed and encoding techniques that minimize this power cost for two- and multi-level logic implementations are described. these techniques are compared with those which minimize area or the switching activity at the present state bits. experimental results show significant improvements.
clock-tree routing realizing a clock-schedule for semi-synchronous circuits. it is known that the clock-period can be shorter than the maximum of signal-delays between registers if the clock arrival time to each register is properly scheduled. the algorithm to design an optimal clock-schedule was given. in this paper, we propose a clock-tree routing algorithm that realizes a given clock-schedule using the elmore-delay model. following the deferred-merge-embedding (dme) framework, the algorithm generates a topology of the clock-tree and determines the locations and sizes of intermediate buffers simultaneously. the experimental results show that this method constructs clock-trees with moderate wire length compared with that of zero-skew clock-trees.
statistical timing analysis driven post-silicon-tunable clock-tree synthesis. process variations cause significant timing uncertainty and yield degradation in deep sub-micron technologies. a solution to counter timing uncertainty is post-silicon clock tuning. existing design approaches for post-silicon-tunable (pst) clock-tree synthesis usually insert a pst clock buffer for each flip-flop or put pst clock buffers across an entire level of a clock-tree. this can cause significant over-design and long tuning time. in this paper, we propose to insert pst clock buffers at both internal and leaf nodes of a clock-tree and use a bottom-up algorithm to reduce the number of candidate pst clock buffer locations. we then provide two statistical-timing-driven optimization algorithms to reduce the hardware cost of a pst clock-tree. experimental results on iscas89 benchmark circuits show that our algorithms achieve up to a 90% area or a 90% number of tunable clock buffer reductions compared to existing design methods.
algorithm level re-computing - a register transfer level concurrent error detection technique. in this paper we propose two algorithm-level time redundancy based concurrent error detection (ced) schemes that exploit diversity in a register transfer (rt) level implementation. rt level diversity can be achieved either by changing the operation-to-operator allocation (allocation diversity) or by shifting the operands before re-computation (data diversity). by enabling a fault to affect the normal result and the re-computed result in two different ways, rt level diversity yields good ced capability with low area overhead. we used synopsys behavior complier (bc) to implement the technique.