Computer Sciences Commons^™

A System For Recognizing A Large Class Of Engineering Drawings, Yuhong Yu, Ashok Samal, Sharad C. Seth

School of Computing: Faculty Publications

We present a system for recognizing a large class of engineering drawings characterized by alternating instances of symbols and connection lines. The class includes domains such as flowcharts, logic and electrical circuits, and chemical plant diagrams. The output of the system, a netlist identifying the symbol types and interconnections, may be used for design simulation or as a compact portable representation of the drawing. The automatic recognition task is divided into two stages: 1) Domain-independent rules are used to segment symbols from connection lines in the drawing image that has been thinned, vectorized, and preprocessed in routine ways. 2) A …

Using Atm Networks For Processing Global Earth Data, Barbara L. Kess, Phillip R. Romig Iii, Stephen E. Reichenbach, Ashok K. Samal

School of Computing: Conference and Workshop Papers

amount of computational power to researchers at an affordable cost, making it feasible to use workstations rather than expensive supercomputers to perform scientific analysis of large data sets, such as the Global Land 1-Km AVHRR data. In addition to this, inexpensive high speed ATM networks have the potential to improve the overall computational efficiency of workstations by using several workstations in a distributed environment. This research studies the practicality of using distributed workstations interconnected with a 155 Mb ATM network for analysis and compression of the Global Land 1-Km AVHRR data versus sequential computing on one of the workstations. Performance …

Synthesis For Testability By Two-Clock Control, Shashank K. Mehta, Sharad C. Seth, Kent L. Einspahr

School of Computing: Conference and Workshop Papers

In previous studies clock control has been inserted after design to improve the testability of a sequential circuit. In this paper we propose a two-clock control scheme that is included as a part of the logic synthesis of a finite state machine (fsm). The scheme has low area overhead and competes well with scan methods in its ability to initialize and observe circuit states. The states of the machine are assigned a pair of binary values using a novel split coding system. The purpose of the encoding is to ease navigation between any pair of states using a combination of …

Minimizing The Number Of Optical Amplifiers Needed To Support A Multi-Wavelength Optical Lan/Man, Byrav Ramamurthy, Jason Iness, Biswanath Mukherjee

School of Computing: Conference and Workshop Papers

Optical networks based on passive star couplers and employing wavelength-division multiplexing (WDhf) have been proposed for deployment in local and metropolitan areas. Amplifiers are required in such networks to compensate for the power losses due to splitting and attenuation. However, an optical amplifier has constraints on the maximum gain and the maximum output power it can supply; thus optical amplifier placement becomes a challenging problem. The general problem of minimizing the total amplifier count, subject to the device constraints, is a mixed-integer non-linear problem. Previous studies have attacked the amplifier placement problem by adding the “artificial” constraint that all wavelengths, …

Separate Computation Of Alias Information Fior Reuse, Mary Jean Harrold, Gregg Rothermel

School of Computing: Faculty Publications

Interprocedural data flow information IS useful for many software testing and analysis techniques, including data flow testing, regression testing, program slicing, and impact analysis. For programs with aliases, these testing and analysis techniques can yield invalid results, unless the data flow information accounts for aliasing effects. Recent research provides algorithms for performing interprocedural data flow analysis in the presence of aliases; however, these algorithms are expensive, and achieve precise results only on complete programs. This paper presents an algorithm for performing alias analysis on incomplete programs that lets individual software components such as library routines, subroutines, or subsystems be independently …

Analyzing Regression Test Selection Techniques, Gregg Rothermel, Mary Jean Harrold

School of Computing: Faculty Publications

Regression testing is a necessary but expensive maintenance activity aimed at showing that code has not been adversely affected by changes. Regression test selection techniques reuse tests from an existing test suite to test a modified program. Many regression test selection techniques have been proposed; however, it is difficult to compare and evaluate these techniques because they have different goals. This paper outlines the issues relevant to regression test selection techniques, and uses these issues as the basis for a framework within which to evaluate the techniques. We illustrate the application of our framework by using it to evaluate existing …

Elimination Of All-Optical Cycles In Wavelength-Routed Optical Networks, Jason Iness, Byrav Ramamurthy, Biswanath Mukherjee, Krishna Bala

School of Computing: Faculty Publications

A transparent (wide-area) wavelength-routed optical network may be constructed by using wavelength cross-connect switches connected together by fiber to form an arbitrary mesh structure. The network is accessed through electronic stations that are attached to some of these cross-connects. These wavelength cross-connect switches have the property that they may configure themselves into unspecified states. Each input port of a switch is always connected to some output port of the switch whether or not such a connection is required for the purpose of information transfer. Due to the presence of these unspecified states, there exists the possibility of setting up unintended …

Improving Circuit Testability By Clock Control, Kent L. Einspahr, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Conference and Workshop Papers

The testability of a sequential circuit can be improved by controlling the clocks of individual storage elements during testing. We propose several clock control strategies derived from an analysis of the circuit, its S-graph structure, and its function. Through examples we show how the number of clocks affects the circuit’s testability. It is shown that if certain flip-flops (FFs) are scanned (or otherwise initialized), the remaining FFs can be controlled and initialized to any arbitrary state using the clock control. We derive a controllability graph and use it to assign clocks to FFs and to schedule the clocks to set …

Safe Stratified Datalog With Integer Order Programs, Peter Revesz

School of Computing: Conference and Workshop Papers

Guaranteeing termination of programs on all valid inputs is important for database applications. Termination cannot be guaranteed in Stratified Datalog with integer (gap)-order programs on generalized databases because they express any Turing-computable function. This paper introduces a restriction of those programs that can express only computable queries. The restricted language has a high expressive power and a non-elementary data complexity.

Restoration And Reconstruction Of Avhrr Images, Stephen E. Reichenbach, Daniel Kohler, Dennis Strelow

School of Computing: Faculty Publications

This paper describes the design of small convolution kernels for the restoration and reconstruction of Advanced Very High Resolution Radiometer (AVHRR) images. The kernels are small enough to be implemented efficiently by convolution, yet effectively correct degradations and increase apparent resolution. The kernel derivation is based on a comprehensive, end-to-end system model that accounts for scene statistics, image acquisition blur, sampling effects, sensor noise, and postfilter reconstruction. The design maximizes image fidelity subject to explicit constraints on the spatial support and resolution of the kernel. The kernels can be designed with h e r resolution than the image to perform …

Accessing Earth System Science Data And Applications Through High-Bandwidth Networks, R. Vetter, M. Ali, M. Daily, J. Gabrynowic, Sunil G. Narumalani, K. Nygard, W. Perrizo, P. Ram, S. Reichenbach, G. A. Seielstad, W. White

School of Computing: Faculty Publications

In this paper, we discuss gigabit network applications enabled by "Mission to Planet Earth," an international effort to monitor the Earth as a system. We describe the design of a network architecture to support applications developed as part of this program; introduce a new component, public access resource centers (PARC9s); and discuss how PARC's would facilitate access by users outside the traditional research community. We also describe how a particular class of users, agriculture users, might to Planet Earth program and delivered in a value-added form to them by a so-called AgPARC. The suggested architecture requires the deployment of high-bandwidth …

A Comprehensive, Automated Approach To Determining Sea Ice Thickness From Sar Data, Donna Haverkamp, Leen-Kiat Soh, Costas Tsatsoulis

School of Computing: Faculty Publications

This paper documents an approach to sea ice classification through a combination of methods, both algorithmic and heuristic. The resulting system is a comprehensive technique, which uses dynamic local thresholding as a classification basis and then supplements that initial classification using heuristic geophysical knowledge organized in expert systems. The dynamic local thresholding method allows separation of the ice into thickness classes based on local intensity distributions. Because it utilizes the data within each image, it can adapt to varying ice thickness intensities to regional and seasonal charges and is not subject to limitations caused by using predefined parameters.

A System For Recognizing A Large Class Of Engineering Drawings, Yuhong Yu, Ashok Samal, Sharad C. Seth

School of Computing: Conference and Workshop Papers

We present a complete system for recognizing a large class of symbolic engineering drawings that includes flowcharts, chemical plant diagrams, and logic & electrical circuits. The output of the system, a netlist identifying the symbol types and interconnections, may be used for design verification or as a compact portable representation of the drawing. The automatic recognition task is done in two stages: (1) domain-independent rules segment symbols from connection lines in the preprocessed drawing image and (2) an understanding subsystem makes use of a set of domain-specific matchers to classify symbols and correct errors automatically. A graphical user interface is …

Hga: A Hardware-Based Genetic Algorithm, Stephen D. Scott, Ashok Samal, Sharad C. Seth

School of Computing: Conference and Workshop Papers

A genetic algorithm (GA) is a robust problem-solving method based on natural selection. Hardware's speed advantage and its ability to parallelize offer great rewards to genetic algorithms. Speedups of 1-3 orders of magnitude have been observed when frequently used software routines were implemented in hardware by way of reprogrammable field-programmable gate arrays (FPGAs). Reprogrammability is essential in a general-purpose GA engine because certain GA modules require changeability (e.g. the function to be optimized by the GA). Thus a hardware-based GA is both feasible and desirable. A fully functional hardware-based genetic algorithm (the HGA) is presented here as a proof-of-concept system. …

A Trainable, Single-Pass Algorithm For Column Segmentation, Son Sylwester, Sharad C. Seth

School of Computing: Conference and Workshop Papers

Column Segmentation logically precedes OCR in the document analysis process. The trainable algorithm described here, XYCUT, relies on horizontal and vertical binary profiles to produce an XY- tree representing the column structure of a page of a technical document in a single pass through the bit image. Training against ground truth adjusts a single, resolution independent, parameter using only local information and guided by an edit distance function. The algorithm correctly segments the page image for a (fairly) wide range of parameter values, although small, local and repairable errors may be made, an effect measured by a repair cost function.

Parallel Test Generation With Low Communication Overhead, Sivaramakrishnan Venkatraman, Sharad C. Seth, Prathima Agrawal

School of Computing: Conference and Workshop Papers

In this paper we present a method of parallelizing test generation for combinational logic using boolean satisfiability. We propose a dynamic search-space allocation strategy to split work between the available processors. This strategy is easy to implement with a greedy heuristic and is economical in its demand for inter-processor communication. We derive an analytical model to predict the performance of the parallel versus sequential implementations. The effectiveness of our method and analysis is demonstrated by an implementation on a Sequent (shared memory) multiprocessor. The experimental data shows significant performance improvement in parallel implementation, validates our analytical model, and allows predictions …

Devious: A Distributed Environment For Vision Tasks, Phillip R. Romig Iii, Ashok K. Samal

School of Computing: Conference and Workshop Papers

We present a system for the integration of computer vision tasks in a distributed environment. This system, called DeViouS, is based on the client/server model and runs in a heterogeneous environment of Unix workstations. It takes advantage of the free cycles in modern workstation environments to distribute and speed up the execution of vision tasks.

Two primary goals of DeViouS are to provide a practical distributed system and a research environment for vision computing. DeViouS is based on a modular design that allows experimentation in various aspects of algorithm design, scheduling and network programming. It can make use of any …

Constraint Objects, Divesh Srivastava, Raghu Ramakrishnan, Peter Revesz

School of Computing: Conference and Workshop Papers

We describe the Constraint Object Data Model (CODM), which enhances an object-based data model with existential constraints to naturally represent partially specified information. We present the Constraint Object Query Language (COQL), a declarative, rule-based query language that can be used to infer relationships about and monotonically refine information represented in the CODM. COQL has a model-theoretic and an equivalent fixed-point semantics, based on the notions of constraint entailment and "proofs in all possible worlds." We also provide a novel polynomial-time algorithm for quantifier elimination for set-order constraints, a restricted class of set constraints that uses membership of subset-equal.

Logic Simulation Using An Asynchronous Parallel Discrete-Event Simulation Model On A Simd Machine, Sharad C. Seth, Lee Gowen, Matt Payne, Don Sylwester

School of Computing: Conference and Workshop Papers

The Chandy-Misra-Bryant (CMB) model has been applied to logic simulation of synchronous sequential circuits using a massively parallel SIMD computer, a CM-2 Connection Machine. Several methods of reducing message traffic in a logic simulation have been adapted to the SIMD architecture of the CM-2, with the result that each method of reducing message traffic actually decreases the speed of the simulation. This suggests that communication costs required to support logic simulation are small compared to the cost of deciding which messages need not be sent.

Recognizing Plants Using Stochastic L-Systems, Ashok K. Samal, Brian Peterson, David J. Holliday

School of Computing: Conference and Workshop Papers

Recognizing naturally occurring objects has been a difficult task in computer vision. One of the keys to recognizing objects is the development of a suitable model. One type of model, the fractal, has been used successfully to model complex natural objects. A class of fractals, the L-system, has not only been used to model natural plants, but has also aided in their recognition. This research extends the work in plant recognition using L-systems in two ways. Stochastic L-systems are used to model and generate more realistic plants. Furthermore, to handle the complexity of recognition, a learning system is used that …

A Sign-To-Speech Translation System, Koka Veera Raghava Rao

School of Computing: Dissertations, Theses, and Student Research

This thesis describes sign-to-speech translation using neural networks. Sign language translation is an interesting but difficult problem for which neural network techniques seem promising because of their ability to adjust to the user's hand movements, which is not possible to do by most other techniques. However, even using neural networks and artificial sign languages, the translation is hard, and the best-known system, that of Fels & Hinton (1993), is capable of translating only 66 root words and 203 words including their conjugations. This research improves their results to 790 root signs and 2718 words including their conjugations while preserving a …

Clock Partitioning For Testability, Kent L. Einspahr, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Conference and Workshop Papers

An implementation of a design for testability model for sequential circuits is presented. The flip-flops in a sequential circuit are partitioned to reduce the number of cycles and the path lengths in each partition, thereby reducing the complexity of test generation. The implementation includes a Podem-based test generator. Preliminary results using the Contest sequential test generator are presented.

Accurate Computation Of Field Reject Ratio Based On Fault Latency, Dharamvir Das, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Faculty Publications

The field reject ratio, the fraction of defective devices that pass the acceptance test, is a measure of the quality of the tested product. Although the assessment of quality is important, an accurate measurement of the field reject ratio of tested VLSI chips is often not feasible. We show that the known methods of field reject ratio prediction are not accurate since they fail to realistically model the process of testing. We model the detection of a fault by an input test vector as a random event. However, we recognize that the detection of a fault may be delayed for …

Generating Tests For Delay Faults In Nonscan Circuits, Prathima Agrawal, Vishwani D. Agrawal, Sharad C. Seth

School of Computing: Faculty Publications

This new method allows any sequential-circuit test generation program to produce path delay tests for nonscan circuits. To test a given path, the authors augment the netlist model of the circuit with a logic block in which testing for a certain single stuck-at fault is equivalent to testing for a path delay fault. The test sequence for the stuck-at fault performs all the necessary delay fault test functions: initialization, path activation, and fault propagation. The authors present results on benchmarks for nonscan and scan/hold modes of testing.

Syntactic Segmentation And Labeling Of Digitized Pages From Technical Journals, Mukkai Krishnamoorthy, George Nagy, Sharad C. Seth, Mahesh Viswanathan

School of Computing: Faculty Publications

Alternating horizontal and vertical projection profiles are extracted from nested sub-blocks of scanned page images of technical documents. The thresholded profile strings are parsed using the compiler utilities Lex and Yacc. The significant document components are demarcated and identified by the recursive application of block grammars. Backtracking for error recovery and branch and bound for maximum-area labeling are implemented with Unix Shell programs. Results of the segmentation and labeling process are stored in a labeled X-Y tree. It is shown that families of technical documents that share the same layout conventions can be readily analyzed. More than 20 types of …

Ppmb: A Partial-Multiple-Bus Multiprocessor Architecture With Improved Cost-Effectiveness, Hong Jiang, Kenneth C. Smith

School of Computing: Faculty Publications

This paper addresses the design and performance analysis of partial-multiple-bus interconnection networks. They are bus architectures that have evolved from multiple-bus structure by dividing buses into groups and reducing bus connections. Their effect is to reduce cost and alleviate arbitration and drive requirements without degrading performance significantly. One such structure, called processor-oriented partial-multiple-bus (or PPMB), is proposed. It serves as an alternative to the conventional structure called memory-oriented partial-multiple-bus (or MPMB) and is aimed at higher system performance at less or equal system cost. It has been shown, both analytically and by simulation, that a substantial increase in system bandwidth …

A Prototype Document Image Analysis System For Technical Journals, George Nagy, Sharad C. Seth, Mahesh Viswanathan

School of Computing: Faculty Publications

Intelligent document segmentation can bring electronic browsing within the reach of most users. The authors show how this is achieved through document processing, analysis, and parsing the graphic sentence.

Dynatapp Dynamic Timing Analysis With Partial Path Activation In Sequential Circuits, Prathima Agrawal, Vishwani Agrawal, Sharad C. Seth

School of Computing: Conference and Workshop Papers

This paper gives a method of finding all sensitizable paths in a non-scan synchronous sequential circuit. Path activation conditions of the circuit are mapped onto a single stuck type fault by adding a few modeling gates to the netlist. Only if the corresponding stuck type fault is found detectable by a sequential circuit test generator is the path considered sensitizable. A depth-first analysis of circuit topology, that determines all paths between primary inputs, primary outputs and flip-flops, employs a partial path hierarchy. Thus, all paths with a common unsensitizable segment need not be examined separately. Results on benchmark circuits show …

A Switch-Level Test Generation System, Kent L. Einspahr, Sharad C. Seth

School of Computing: Conference and Workshop Papers

This paper presents a switch-level test generation system for synchronous sequential circuits in which a new algorithm for switch-level test generation and an existing fault simulator are integrated. For test generation, a switch-level circuit is modeled as a logic network that correctly models all aspects of switch-level behavior. The time-frame based algorithm uses asynchronous processing within each clock phase to achieve stability in the circuit, and synchronous processing between clock phases to model the passage of time. Unlike earlier time-frame based test generators for general sequential circuits, the test generator presented uses the monotonicity of the logic network to speed …

Parallel Test Pattern Generation Using Boolean Satisfiability, V. Sivaramakrishnan, Sharad C. Seth, Prathima Agrawal

School of Computing: Conference and Workshop Papers

Recently, Larrabee proposed a sequential test generation algorithm for combinational circuits based on boolean satisfiability and presented results on benchmark circuits in support of the viability of this approach. Parallel implementations of test generation algorithms are attractive in view of the known difficulty (NP-completeness) of the problem. In this paper we suggest parallel versions of Larrabee’s algorithm, suitable for implementation on shared-memory and message-passing multicomputers.