1550167
Verification of arithmetic circuits using binary moment diagrams
Abstract.Binary moment diagrams (BMDs) provide a canonical representation for linear functions similar to the way binary decision diagrams (BDDs) represent Boolean functions. Within the class of linear functions, we can embed arbitrary functions from Boolean variables to real, rational, or integer values. BMDs can thus model the functionality of data path circuits operating over word-level data. Many important functions, including integer multiplication, that cannot be represented efficiently at the bit level with BDDs, have simple representations at the word level with BMDs. Furthermore, BMDs can represent Boolean functions as a special case. We propose a hierarchical approach to verifying arithmetic circuits, where component modules are first shown to implement their word-level specifications. The overall circuit functionality is then verified by composing the component functions and comparing the result to the word-level circuit specification. Multipliers with word sizes of up to 256 bits have been verified by this technique.
10324421
Advanced techniques for RTL debugging
Conventional register transfer level (RTL) debugging is based on overlaying simulation results on structural connectivity information of the Hardware Description Language (HDL) source. This process is helpful in locating errors but does little to help designers reason about the how and why. Designers usually have to build a mental image of how data is propagated and used over the simulation run. As designs get more and more complex, there is a need to facilitate this reasoning process, and automate the debugging. In this paper, we present innovative debug techniques to address this shortage in adequate facilities for reasoning about behavior, and debugging errors. Our approach delivers significant technology advances in RTL debugging; it is the first comprehensive and methodical approach of its kind that extracts, analyzes, traces, explores, and queries a design's multi-cycle temporal behavior. We show how our automatic tracing scheme can shorten debugging time by orders of magnitude for unfamiliar designs. We also demonstrate how the advanced debug techniques reduce the number of regression iterations.
9328998
Verification of Arithmetic Circuits with Binary Moment Diagrams
Binary Moment Diagrams (BMDs) provide a canonical representations for linear functions similar to the way Binary Decision Diagrams (BDDs) represent Boolean functions. Within the class of linear functions, we can embed arbitrary functions from Boolean variables to integer values. BMDs can thus model the functionality of data path circuits operating over word-level data. Many important functions, including integermultiplication, that cannot be represented efficiently at the bit level with BDDs have simple representations at the word level with BMDs. Furthermore, BMDs can represent Boolean functions with around the same complexity as BDDs. We propose a hierarchical approach to verifying arithmetic circuits, where componentmodules are first shownto implement their word-level specifications. The overall circuit functionality is then verified by composing the component functions and comparing the result to the word-level circuit specification. Multipliers with word sizes of up to 256 bits have been verified by this technique.
7335648
A Systolic Algorithm for the k-Nearest Neighbors Problem
The authors present a systolic algorithm and its variations for the k-nearest neighbors problem (kNNP). Multiple-shot queries with different ranges (k values) can be served in a pipelined fashion. A partitioning scheme is developed to handle large size problems. Performance of the algorithm is analyzed. Formulas for the optimal array size in terms of computation time and area-time-time product (ATT) are derived. The algorithm can solve a multiple-shot kNNP in N+2 square root N*K systolic steps using square root N*K processing elements, where N is the problem size (i.e. the number of points), and K is the sum of all k-values. >
6571672
Using object and trajectory analysis to facilitate indexing and retrieval of video
This paper aims to show that by using low level feature extraction, motion and object identifying and tracking methods, features can be extracted and indexed for efficient and effective retrieval for video; such as an awards ceremony video. Video scene/shot analysis and key frame extraction are used as a foundation to identify objects in video and be able to find spatial relationships within the video. The compounding of low level features such as colour, texture and abstract object identification lead into higher level real object identification and tracking and scene detection. The main focus is on using a video style that is different to the heavily used sports and news genres. Using different video styles can open the door to creating methods that could encompass all video types instead of specialized methods for each specific style of video.
13939828
Mutual information regularized Bayesian framework for multiple image restoration
Bayesian methods have been extensively used in various applications. However, there are two intrinsic issues rarely addressed, namely generalization and validity, in the context of multiple image restoration, we show that traditional Bayesian methods are sensitive to model errors and cannot guarantee valid results satisfying the underlying prior knowledge, e.g. independent noise property. To improve the Bayesian framework's generalization, we propose to explicitly enforce the validity of the result. Independent noise prior is very important but largely under-utilized in previous literature. In this paper, we use mutual information (MI) to explicitly enforce the independence. Efficient approximations based on Taylor expansion are proposed to adapt MI into standard energy forms to regularize the Bayesian methods. The new regularized Bayesian framework effectively utilizes the traditional generative signal/noise models but is much more robust to various model errors, as demonstrated in experiments on some demanding imaging applications.
18308344
Using Colored Petri Nets for Conversation Modeling
Conversations are a useful means of structuring communicative interactions among agents. The value of a conversation-based approach is largely determined by the conversational model it uses. Finite State Machines, used heavily to date for this purpose, are not sufficient for complex agent interactions requiring a notion of concurrency. We propose the use of Colored Petri Nets as a model underlying a language for conversation specification. This carries the relative simplicity and graphical representation of the former approach, along with greater expressive power and support for concurrency. The construction of such a language, Protolingua, is currently being investigated within the framework of the Jackal agent development environment. In this paper, we explore the use of Colored Petri Nets in modeling agent communicative interaction.
17244811
Cooperative and group testing in verification of dynamic composite Web services
Verifying Web services (WS) in a dynamic Service Oriented Architecture (SOA) is challenging because new services can be composed at runtime using existing WS. Furthermore, in a composite service, any component can be dynamically replaced during execution if the component fails. Another challenge is that the testing is time critical because verification must be conducted at runtime and in real time. We compare and contrast traditional software testing and WS testing techniques and propose a WS group testing technique to test composite services. The group testing technique also has the ability to evaluate the test scripts, automatically establish the oracle of the each test script, and identify faulty WS in a failed composite WS.
12984676
Hybrid Evolutionary And Annealing Algorithms For Nonlinear Discrete Constrained Optimization
This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms.