Optimum or near-optimum solutions of the Golomb ruler (gr) problem have applications in information theory, error correction, current transformers, radio frequency selection, placement of antenna arrays in astronomy, among others. In mathematics, there is a well-defined relationship of Golomb rulers and graceful graphs. A massively parallel computing project on gr has been on-going for more than 10 years: the order-24 ruler was claimed as optimum in November 2004 (after a 4-year computational effort), followed by order-25, -26, -27 rulers in 2008, 2009, 2014. The order-28 ruler is work-in-progress. The distribution of waiting times, in years, such as {4, 4, 1, 5} may be impossible to predict under a variable number of processors running simultaneously. This paper proposes a model to experimentally predict the asymptotic runtime complexity of any gr solver that returns the best-known-value (BKV) Golomb ruler defined by the paired list (L = length, M = order). A subset of this list includes {(6,4), (11,5), (17,6), (25,7), (34,8), (44,9),..., (680,30)}. Given the number of processors N and the runtime limit tlmt, we observe at least Nu≥ 100 processors reaching the target BKV with the first-passage-timelmtand say that each such observation is uncensored. In other words, the mean runtime value we measure is based strictly on at least 100 uncensored observations from the experiment. Experiments in this paper focus on a stochastic gr-solver that implements a variation of a self-avoiding walk. In the total number of steps, the solver asymptotic walkLength complexity is 409.2 × 1.0762L. When measuring the number of CPU seconds on a loaded grid of 100 processors, the solver asymptotic runtime complexity is 0.000206 × 1.08711L. This solver significantly outperforms the alternative stochastic gr-solvers reported to date.

Covering problems arise in many areas of electronic design automation such as logic minimization and technology mapping. An exact solution can critically impact both size and performance of the devices being designed. This paper introduces eclipse, a branch-and-bound solver that can solve many covering problems orders of magnitude faster than existing solvers. When used in place of the default covering engine of a well-known logic minimizer, eclipse makes it possible to find, in less than six minutes, true minima for three benchmark problems that have eluded exact solutions for more than a decade.

We introduce a universal client (OmniFlow) whose GUI can be readily configured by the user to invoke any number of applications, concurrently or sequentially, anywhere on the network. The design and the implementation of the client is based on the principles of taskflow-oriented programming, whereby we merge concepts from structured programming, hardware description, and mark-up languages. A mark-up language such as XML supports a well-defined schema that captures the decomposition of a program into a hierarchy of tasks, each representing an instance of a blackbox or a whitebox software component. The HDL-like input/output port definitions capture data-task-data dependencies. A highly interactive hierarchical GUI, rendered from the hierarchical taskflow descriptions in extended XML, supports structured programming language constructs to control sequences of task synchronization, execution, repetition, and abort. Experimental evaluations of the prototype, up to 9150 tasks and the longest path of 1600 tasks, demonstrate the scalability of the environment and the overall effectiveness of the proposed architecture for a number of networked design and computing projects. 1.

OpenDesign is an open user-configurable project environment that supports distributed collaborative design and execution on the Internet. The environment is created by configuring a generic client for a specific project. This is in contrast to an implementation of a project-specific client-server architecture. This paper introduces the OpenDesign environment in the contest of a design process and project-specific tasks. An OpenDesign task is defined as execution of one or more CAD point tools, whereas a task flow is a dependency graph of tasks and/or other task flows. Challenges arise when, within a single project, (1) tasks must be executed on remote hosts under different file systems, (2) data must be accessed, moved, modified, and archived with consistency, (3) tasks and task flows are assigned to more than one designer, and (4) designers are physically dispersed. In collaboration with peer institutions, a number of demo design projects demonstrate the features and the opportunities with the OpenDesign environment.

This paper formalizes the synthesis process of wiring signature-invariant (WSI) combinational circuit mutants. The signature /spl sigma//sub 0/ is defined by a reference circuit /spl eta//sub 0/, which itself is modeled as a canonical form of a directed bipartite graph. A wiring perturbation /spl gamma/ induces a perturbed reference circuit /spl eta//sub /spl gamma//. A number of mutant circuits /spl eta//sub /spl gamma/i/ can be resynthesized from the perturbed circuit /spl eta//sub /spl gamma//. The mutants of interest are the ones that belong to the wiring-signature-invariant equivalence class N/sub /spl sigma/0/, i.e. the mutants /spl eta//sub /spl gamma/i//spl isin/N/sub /spl sigma/0/. Circuit mutants /spl eta//sub /spl gamma/i//spl isin/N/sub /spl sigma/0/ have a number of useful properties. For any wiring perturbation /spl gamma/, the size of the wiring-signature-invariant equivalence class is huge. Notably, circuits in this class are not random, although for unbiased testing and benchmarking purposes, mutant selections from this class are typically random. For each reference circuit, we synthesized eight equivalence subclasses of circuit mutants, based on 0 to 100% perturbation. Each subclass contains 100 randomly chosen mutant circuits, each listed in a different random order. The 14,400 benchmarking experiments with 3200 mutants in 4 equivalence classes, covering 13 typical EDA algorithms, demonstrate that an unbiased random selection of such circuits can lead to statistically meaningful differentiation and improvements of existing and new algorithms.

Applying the Dmign of Experiments methodology to the evaluation of BDD van'able orden.ngalgon.thmshas yielded a number of conclusive Tesults.The methodology reiies on the rtient~y i~tTOdUCd equivalence classes of functionally petiurbed circuits that maintain logic invariance, , ...)-mintems of the original refeTence OT aTe urithin {1, 2 circuit function, abo maintaining entTopy-invan.ante.FOT some of the current vam.ableOTde~ng algom.thmsand tools, the negative raults include: (1) statistically significant sensitivity to naming of vatiables, (2) confirmation that a numbeT of variable orden.ngalgorithms aTe statistically equivalent to a random variable order assignment, and (3) obsemation of a statistically anomalous variable ordefl-ng behavioT of a wellknown benchmaTk circuit isomorphic class when analyzed un-deT a single and multiple outputs.On the positive side, the methodology supports a statistically significant mem.t evaluation of any newly introduced vatiable oTdem.ngalgon.thm,including the one bm.e~yintroduced in this papeT.

This paper analyzes the effect of resource sharing and assignment on the clock period of the synthesized circuit. The assignment phase assigns or binds operations of the scheduled behavioral description to a set of allocated resources. We focus on control-flow intensive descriptions, characterized by the presence of mutually exclusive paths due to the presence of nested conditional branches and loops. We show that clustering multiple operations in the same state of the schedule, possibly leading to chaining of functional units (FUs) in the RTL circuit, is an effective way to minimize the total number of clock cycles, and hence total execution time. We present an assignment algorithm that is particularly effective for such design styles by minimizing data chaining and hence the clock period of the circuit, thereby leading to further reduction in total execution time. Existing resource sharing and assignment approaches for reducing the clock period of the resulting circuit either increase the resource allocation or use faster modules, both leading to leading to larger area requirements. In this paper we show that even when the type of available resource units and the number of resource units of each type is fixed, different assignments may lead to circuits with significant differences in clock period. We provide a comprehensive analysis of how resource sharing and assignment introduces long paths in the circuit. Based on the analysis, we develop an assignment algorithm that uses a high-level delay estimator to asign operations to a fixed set of available resources so as to minimize the clock period of the resultant circuit, with no or minimal effect on the area of the circuit. Experimental results on several conditional-intensive designs demonstrate the effectiveness of the assignment algorithm.

This paper introduces a directed hypergraph modelthat supports (1) workflow composition and reconfigurationwhile accessing and executing programs, data, and computingresources across the Internet, (2) synchronous and asynchronouspeer-to-peer interaction between members of anyteam during workflow composition and execution, (3) synchronousand asynchronous peer-to-workflow interaction betweenany team member and any object in the workflow.Given a library of program and data nodes, editing theworkflow and its execution is as intuitive as the hierarchicalschematic design capture and simulation.Examples of multi-sitemulti-user applications demonstrate that the proposedworkflow implementation provides a user-friendly paradigmfor distracted and collaborative team design.

The Internet-based desktop environment as defined in this paper consists of a cross-platform browser, a number of server icons (host nodes), a number of application icons (program nodes) and a number of data iwns'(file nodes).In contrast to typical desktops of today, where data icons may be dragged and dropped onto application icons for execution, this environment allows (I) user-defined and reconfigurable execution sequences by creating dependency edges between program nodes (application icons) and file nodes (data icons); (2) data-dependent execution sequences by dynamic scheduling of path as well as loop executions; (3) host-transparency as to the location of applications and data (60th can reside on any host with a unique IP address).We argue that the Internet-based workflow paradigm is suitable for creation of dynamically reco;lfigurable desktop environments.The summary of 450 Internet-based expen'ments demonstrates (1) the value of making the desktop recordable, and (2) the feasibility of rendering it collaborative.

Article Towards a new benchmarking paradigm in EDA: analysis of equivalence class mutant circuit distributions Share on Authors: Nevin Kapur CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C. CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C.View Profile , Debabrata Ghosh CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C. CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C.View Profile , Franc Brglez CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C. CBL (Collaborative Benchmarking Laboratory), Department of Computer Science, Box 7550, North Carolina State University, Raleigh, N.C.View Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 136–143https://doi.org/10.1145/267665.267704Published:01 April 1997 12citation213DownloadsMetricsTotal Citations12Total Downloads213Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper addresses the problem of true delay estimation during high level design. The true delay is the delay of the longest sensitizable path in the resulting circuit, as opposed to the topological delay which is the delay of the longest path in the circuit. The existing delay estimation techniques either estimate the topological delay, which may be pessimistic if the longest path is unsensitizable or false, or estimate the true delay using gate-level timing analysis which may be prohibitively expensive. Resource sharing in high level synthesis can create false paths in the circuit implementation. Hence, determining the clock period using topological delay can be unduly conservative, resulting in excessive hardware to meet tight timing specifications. In this paper, we introduce an efficient technique to compute an estimate of the true delay. The proposed technique relies on partitioning the paths in the circuit and topological delay computation, and not on path sensitization. The paths in the implementation are partitioned into two sets given the high level information on scheduling and resource sharing: the complete determining path set (CDP/sub R/) and the nondetermining path set (NDP/sub R/). We prove that the delay of the longest path in CDP/sub R/ is lower bounded by the true delay and upper bounded by the topological delay of the circuit. Consequently, an estimate of the true delay of the resulting circuit can be computed by measuring the topological delay of the longest path in CDP/sub R/. We have developed a Functional delay ESTimation tool (FEST). Experimental results on a set of benchmarks reveal the following: approximately 50% of all paths are in NDP/sub R/ and can be ignored for true delay estimation, and the true delay estimates are on the average 15% less than the topological delay. The high level true delay estimates are accurate, as verified by comparing with the true delays obtained by gate-level timing analysis on actual implementations. Furthermore, results reveal that high level true delay estimation can be done very fast, even when gate-level true delay estimation becomes infeasible.

This paper introduces the concept of detectable perturbations as a method to generate tests that can then cover any technology-specific faults such as multiple bridging, open and stuck-at faults. Rather than devising a customized test pattern generation system for each class of technology-specific faults, we implemented a generic system to generate tests for single and multiple perturbations. We demonstrate the versatility of this approach by generating tests for a set of large benchmark circuits that have been mapped into singleand multi-output modules. These tests cover single stuck-at, multi-output bridging, stuck-at, as well as any mutation faults in the functionality of the technology-mapped cells. Experimental results provide useful insights about the quality of single stuck-at test patterns versus coverages for the additional classes of faults.

Abstract- This paper analyzes the effect of resource sharing and assignment on the clock period of the synthesized circuit. We focus on behavioral specifications with mutually exclusive paths, due to the presence of nested conditional branches and loops. It is shown that even when the set of available resources is fixed, different assignments may lead to circuits with significant differences in clock period. We provide a comprehensive analysis of how resource sharing and assignment introduces long paths in the circuit. Based on the analysis, we develop an assignment algorithm which uses a high-level delay estimator to assign operations to a fixed set of available resources so as to minimize the clock period of the resultant circuit. Experimental results on several conditionalintensive designs demonstrate the effectiveness of the assignment algorithm. I.

Abstract- This paper presents a new method,based on Markov chain analysis, to evaluate the performance of schedules of behavioral specifications. The proposed performance measure is the expected number of clock cycles required by the schedule for a complete execution of the behavioral specification for any distribution of inputs. The measure considers both the repetition of operations (due to loops) and their conditional execution (due to conditional branches). We propose an efficient technique to calculate the metric. We introduce a loop-directed scheduling algorithm (LDS). The algorithm produces schedules such that the expected number of clock cycles, required by the schedule for a complete execution of the behavioral specification, is minimized. Experimental results on several conditional and loop-intensive specifications demonstrate the relevance and effectiveness of both the performance measure and the scheduling algorithm. I.

This paper considers the problem of partitioning a large logic circuit into a collection of subcircuits each of which is implemented with a device from a specific (FPGA) library. The objective function that we minimize is not only the total cost of devices to be used in the partition but also the size of the interconnect between the devices. We introduce the concept of functional replication and a unified cost model for min-cut partitioning with replication. A prototype implementation demonstrates the feasibility of the approach, based on experimental results with a set of large benchmark circuits. I. Introduction FPGAs are widely used in many applications [1]. Large designs cannot be implemented with FPGAs unless they are partitioned into smaller subcircuits. Optimizing a set of large design specifications will in general require partitioning into multiple FPGAs of varying sizes and types. Di#erent sizes and types of devices can be combined to reduce the design cost and achieve a be...

This paper considers the problem of obtain-

This paper introduces a technique to transform a given register-transfer level (RT-level) design, consisting of control logic and data path, into a functionally equivalent, minimized design which is 100% testable under full-scan at the gate level. The proposed RT-level optimization technique uses the RT-level structure and exploits the interaction between the control and the data path. Our approach maintains the RT-level design hierarchy while performing RT-level transformations of initially specified data path, followed by resynthesis of control using don't cares extracted from the data path. Experiments with several RTL benchmarks demonstrate the effectiveness of the technique in generating fully testable designs. In addition, comparison with logic-level techniques show the advantages of the proposed technique as an optimizing tool to produce circuits with reduced area and delay.>

This paper introduces a unified approach to automatic pattern generation for diagnosis of board-level wiring defects between modules both with and without boundary scan. The fault model for wiring defects includes bridging faults, stuck-at faults and open faults. We show that complete diagnosis of 1/0 faults can be achieved by considering single faults only rather than fault pairs and we have modified a traditional sptem that supports single stuck fault test generation to also perform pattern generation for complete diagnosis. Rather than building a fault dictionary from detection patterns, we introduce distinguishing functions, a fault diagnosis tree and heuristics to resolve signatures of faults so that they become unique or are proven equivalent. Experimental results with large benchmark circuits show that complete diagnosis for stuck-at as well as bridging I/O faults is possible. The number of patterns for complete diagnosis compares favorably with patterns required for first detection of single stuck-at faults only.

The authors present an algorithm for hierarchical test generation based on module-oriented decision making (MODEM). The algorithm deals with combinational logic modules and the traditional single-stuck-at model. Modules and faults are captured at the function as well as the gate level. The benefits of hierarchy are realized by introducing a generic module representation and the concepts of a dynamic netlist and a dynamic calculus. The authors present the key elements of MODEM: the framework and fault targeting strategy, the module characterization, and a notation and calculus for module-oriented decision making. They conclude with a high-level view of MODEM implementation and experimental results on a variety of hierarchical benchmarks.>

The concepts of corolla partitioning based on an analysis of signal reconvergence to cyclic sequential circuits are extended. The sequential circuit is partitioned into corollas that will contain latches but can be peripherally retimed and resynthesized using combinational techniques. Cycles are broken in the circuit by ensuring that the partitions that are formed are acyclic. Application of the proposed partitioning, retiming and resynthesis approach to a set of large sequential benchmarks has shown considerable gains after resynthesis.>

This paper introduces a circuit partitioning method based on analysis of reconvergent fanout. We consider a DAG model for a circuit. We define a corolla as a set of overlapping reconvergent fanout regions. We partition the DAG into a set of non-overlapping corollas and use the corollas to resynthesize the circuit. We show that resynthesis of large benchmark circuits consistently reduces transistor pairs and layout area while improving delay and testability.

The authors address scan-based built-in self-test (BIST) of digital circuits that are highly resistant to testing with uniform random patterns. Introducing a procedure, the precompute test patterns for random-pattern resistant faults and generate optimized distributions of weights that guarantee pattern coverage in a given number of random trials. The software implementation offers a tradeoff in the number of distributions (hardware memory) and the length of the total test time. The hardware implementation is based on a canonic weighting circuit that interfaces to a circulating memory and a pseudo-random source.>

OASIS is a cell-based silicon compiler system that supports rapid implementation of digital Application specific ICs (ASICs). The system automates the design process by taking a high-level language description and producing a layout of a testable IC. OASIS facilitates design of large digital systems on silicon and gives the designer sufficient control to enable exploration of the speed-versus-area design tradeoffs. The front end of OASIS is the LOGIC-III compiler that translates a high-level language description into a hierarchical netlist of gates. The LOGIC-III language is a PASCAL-like language that allows the designer to specify his design completely and in a uniform, consistent manner. The language supports both the logic synthesis for FSMs and combinational logic, and the structural/algorithmic synthesis of data paths and regular structures such as adders or multipliers. The OASIS system comprises an integrated set of tools for complete design, simulation, verification, layout and testing of ASICs. Experience with the system shows a marked increase in design productivity when compared with more traditional design techniques. The authors describe the system with its unique features and present some of the results of using OASIS in designing semi-custom ASICs.>

The authors introduce WARP, a weighted test generation system that includes a canonical circuit for resolving weights to any desired precision. Either cellular automata registers (CARs) or linear feedback shift registers (LFSRs) are used as a source of random patterns, and optionally, it is possible to permute and linearly combine random bits from the source to control inputs to the weighting circuit. The authors analyze pattern coverage and conclude with benchmark results on fault coverage differences between CARs and LFSRs.>

The authors have proposed and implemented a dynamic framework and a method for hierarchically generating test patterns from a hierarchical net list. They have shown consistent gains in CPU over the traditional gate-level implementation while maintaining identical levels of fault coverage. In generating and characterizing modules for a large and varied set of hierarchical benchmarks, the authors benefited considerably from the consistent representations that are available during synthesis from a high-level description or when modules are generated by a process of technology mapping into standard cells. The authors introduced the concept of a single generic module which is hierarchical; the traditional AND, OR, NAND, and NOR are included implicitly. They developed a module-oriented decision-making algorithm, MODEM, which entails a dynamic calculus and procedures such as implication, error propagation, line justification, and probabilistic testability measures for a single generic module. Without loss of generality they adapted the control flow and basic features of PODEM in the first implementation of MODEM.>

The authors present a scan-based testability system that is an integral part of the cell-based design system at Microelectronics Center of North Carolina. The basic system consists of five modules: a scan-based audit to verify compliance with scan-based rules, a testability assessment module that projects fault coverage before any patterns are applied, a fast fault simulator that grades random and user-supplied patterns, an algorithmic test-pattern generator that produces test for faults that resist detection with random patterns or declares them redundant, and a test-pattern compactor to further reduce the size of the test-pattern set. The system serves as a platform for research into hierarchical methods, redundancy identification and removal, automated test point insertion, improved random test pattern generation, fault simulation, and boundary scan.>

The authors present a method for transforming multilevel equations into a gate-level netlist of a given technology. The proposed mapping procedure performs multiple mappings, each with randomly selected program parameters. The number of mappings is user-settable, and it offers the designer an option to trade off CPU runtime for better results. This feature is important to designers who begin by exploring the space of architectural possibilities, then finally create a specific, highly optimized circuit. The proposed technology mapping method has been implemented in C as a logic-design tool (McMAP) that takes full advantage of any gate library's timing and area information. Using default parameter settings, the tool synthesized several standard benchmark examples yielding higher-quality circuits with lower CPU requirements than previously reported.>

Boundary scan merging with built-in self-test is discussed. The proposed implementation of boundary scan represents a snapshot of the Joint Test Advisory Group Recommendation 1.0, while the built-in self-test implements the features of cellular automata. Test patterns generated from two distinct sources are examined, one with registers using cellular automata and the other, based on the conventional LFSR (linear-feedback shift register) configuration. Distinctive effects of these patterns on fault coverage of specific designs are analyzed and illustrated.>

This paper presents a new and an effective approach to fault simulation of transition faults in combinational or scan - based logic. An experiment with a set of benchmark circuits demonstrates the efficiency of the approach, achieved by combining a very fast single stuck - at fault simulation algorithm with a quasi - static definition of a transition fault. Tests that cover transition faults are becoming increasingly important as they also provide a cover for most typical transistor stuck - open faults in CMOS.

This paper presents ESPRIT, an automatic test pattern generation (ATPG) system for testing single stuck-at faults in combinational logic. ESPRIT generates test patterns by performing fault simulation on random patterns derived from nonuniformly distributed input signal probabilities. The system computes input signal probabilities that minimize a testability cost function. Using ESPRIT, we have observed orders-of-magnitude reduction in the number of random trials required to obtain a given fault coverage.