Digital Commons Network^™

A Theory Of Testability With Application To Fault Coverage Analysis, Sharad C. Seth, Vishwani Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit-dependent. In fact, the actual rise of fault coverage depends on the characteristics of vectors, as well as, on the circuit. The paper shows that the average fault coverage can be computed from circuit testability. A relationship between fault coverage and circuit testability is derived. The mathematical formulation allows computation of coverage for deterministic and random vectors. Applications of this analysis include: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation …

Testability Analysis Of Synchronous Sequential Circuits Based On Structural Data, Raghu V. Hudli, Sharad C. Seth

School of Computing: Faculty Publications

Bounds on test sequence length can be used as a testability measure. We give a procedure to compute the upper bound on test sequence length for an arbitrary sequential circuit. We prove that the bound is exact for a certain class of circuits. Three design rules are specified to yield circuits with lower test sequence bounds.

A Microcomputer-Based Cia System Designed To Compliment Traditional Instruction In Navy Technical Training, John M. Kaiser

CCAC Theses and Dissertations

A prototype microcomputer-based CBI program was developed to provide review, structured self-study, and remediation to students undergoing initial skills training at the Naval Air Technical Training Center (NATTC), Lakehurst, NJ. The program demonstrates the capabilities of the authoring (LSAUT) and delivery (LSSTU) programs that are parts of the Language Skills Computer Aided Instruction (LSCAI) system developed by the Navy Personnel Research and Development Center and the University of Utah. A course of instruction at NATTC, Lakehurst was selected for this project on the basis of level of training, student throughput, attrition and setback rates, and category of learning objectives. Student …

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein

Computer Science: Faculty Publications and Other Works

No abstract provided.

Graph Coloring Algorithms On Random Graphs, Shi-Jen Lin

Doctoral Dissertations

"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes …

The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne

Doctoral Dissertations

"The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to …

Personal Computing For The Visually Impaired, Bruce M. Mcmillin, P. Y. Mcmillin

Computer Science Faculty Research & Creative Works

The problem of providing feedback from the computer to a visually impaired user is examined. The use of traditional tactile input and output (Braille) is described. The limitations of voice output are discussed, and difficulties posed by complicated screen formats and screen review are considered.

Reliable Distributed Sorting Through The Application-Oriented Fault Tolerance Paradigm, Bruce M. Mcmillin, L. M. Ni

Computer Science Faculty Research & Creative Works

The design and implementation of a reliable version of the distributed bitonic sorting algorithm using the application-oriented fault tolerance paradigm on a commercial multicomputer is described. Sorting assertions in general are discussed and the bitonic sort algorithm is introduced. Faulty behavior is discussed and a fault-tolerant parallel bitonic sort developed using this paradigm is presented. The error coverage and the response of the fault-tolerant algorithm to faulty behavior are presented. Both asymptotic complexity and the results of run-time experimental measurements on an Ncube multicomputer are given. The authors demonstrate that the application-oriented fault tolerance paradigm is applicable to problems of …

Safe Computing, Bruce M. Mcmillin, T. L. Casavant

Computer Science Faculty Research & Creative Works

So-called worms, viruses, and Trojan horses that attack computer systems are defined. The vehicle that allows these attacks to occur, namely, the open computer internetwork, is examined. The problem of providing protection against attack in an internetwork environment is discussed. The need for professional responsibility on the part of the scientific and engineering community in enforcing strong ethical practices and neither tolerating nor condoning such practices is stressed.

A Definition Optimization Technique Used In A Code Translation Algorithm, David M. Dejean, George Winston Zobrist

Computer Science Faculty Research & Creative Works

Data flow analysis is used to optimize variable definitions in a program that translates microprocessor object code to a higher order language. © 1989, ACM. All rights reserved.

Expectations For Associative-Commutative Unification Speedups In A Multicomputer Environment, Ralph W. Wilkerson, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

An essential element of automated deduction systems is unification algorithms which identify general substitutions and when applied to two expressions, make them identical. However, functions which are associative and commutative, such as the usual addition and multiplication functions, often arise in term rewriting systems, program verification, the theory of abstract data types and logic programming. The introduction to the associative and commutative equality axioms together with standard unification brings with it problems of termination and unreasonably large search spaces. One way around these problems is to remove the troublesome axioms from the system and to employ a unification algorithm which …

Fault Diagnosis Using First Order Logic Tools, Ralph W. Wilkerson, Barbara A. Smith

Computer Science Faculty Research & Creative Works

An automated circuit diagnostic tool implementing R. Reiter's theory of diagnosis (1987) based on deep knowledge (i.e. knowledge based on certain design information) and using first-order logic as the representation language is discussed. In this approach, the automated diagnostician uses a description of the system structure and observations describing its performance to determine if any faults are apparent. If there is evidence that the system is faulty, the diagnostician uses the system description and observations to ascertain which component(s) would explain the behavior. In particular, Reiter's method finds all combinations of components which explain this behavior.

The Strong Perfect Graph Conjecture For Pan-Free Graphs, Stephan Olariu

Computer Science Faculty Publications

A graph G is perfect if for every induced subgraph F of G, the chromatic number χ(F) equals the largest number ω(F) of pairwise adjacent vertices in F. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

Automatically Generating Functional Tests From Specifications - A Knowledge Based Constraint Logical Programming Approach, Ji Chen

Computer Science Theses & Dissertations

Recent experimental results indicate that functional testing is one of the most effective methods in detecting certain classes of faults. Very little work has been done in automating functional testing. This thesis research develops a method, called hierarchical partition, for automating functional testing. The key to our approach is the utilization of a pre-existing knowledge base about the domain of discourse. Several approaches to knowledge organiza­tion are discussed along with the resulting effects on the quantity and quality of functional tests produced. This research is an application and development of Generic Constraint Logic Programming and the Knowledge Driven …

A New Conjecture About Minimal Imperfect Graphs, H. Meyniel, Stephan Olariu

Computer Science Faculty Publications

H. Meyniel proved that in every minimal imperfect graph, every pair of vertices is joined by a chordless path containing an odd number of edges. We conjectured that in every minimal imperfect graph, every pair of vertices is joined by a path containing an even number of edges. We give an equivalent version of this new conjecture.

Evaluation Of Concurrent Pools, David Kotz, Carla Ellis

Dartmouth Scholarship

The assignment of resources or tasks to processors in a distributed or parallel system needs to be done in a fashion that helps to balance the load and scales to large configurations. In an architectural model that distinguishes between local and remote data access, it is important to base these allocation functions on a mechanism that preserves locality and avoids high-latency remote references. This paper explores performance considerations affecting the design of such a mechanism, the Concurrent Pools data structure. We evaluate the effectiveness of three different implementations of concurrent pools under a variety of stressful workloads. Our experiments expose …

Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark

Masters Theses

"It was desired to develop an algorithm for the automated translation of' finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation"--Abstract, page ii.

Symbolic Automation And Numerical Synthesis For Robot Kinematics, Jen Sriwattanathamma, Chung You Ho

Computer Science Technical Reports

This research analyzes three topics in robot arm kinematics. First, the direct kinematics which determines the Cartesian position and orientation of the end effector for the specified values of joint parameters is analyzed. Second, the differential motions concerning the differential relationships between the command variables in position and orientation of the end effector and the joint-controlled variables are studied. Finally, the inverse kinematics which determines the joint variables for a specified Cartesian position and orientation of the end effector is considered.

This dissertation presents a methodology for incorporating the artificial intelligence types of knowledge into automating solutions for the direct …

A Band And Bound Technique For Simple Random Algorithms, Vernon J. Rego

Department of Computer Science Technical Reports

No abstract provided.

Machine Knowledge Maniputation Issues In Parallel Compilers, Ko-Yang Wang, Dennis Gannon, Piyush Mehrotra

Department of Computer Science Technical Reports

No abstract provided.

On The Bottleneck And Capacity Assignment Problems, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Elliptic Expert: The Design Of An Expert System For Elliptic Partial Differential Equations, Wayne R. Dyksen, Carl R. Gritter

Department of Computer Science Technical Reports

No abstract provided.

Xellpack: An Interactive Problem Solving Environment For Elliptic Partial Differential Equations, Jophn P. Bonomo, Wayne R. Dyksen

Department of Computer Science Technical Reports

No abstract provided.

Hermite Interpolation Of Rational Space Curves Using Real Algebraic Surfaces, Chanderjit Bajaj, Insung Ihm

Department of Computer Science Technical Reports

No abstract provided.

A Dimensionality Paradigm For Surface Interrogations, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

Effects Of Autonomy On Maintaining Global Serializability In Heterogeneous Database Systems, W. Du, Ahmed K. Elmagarmid, Y. Leu, S. F. Ostermann

Department of Computer Science Technical Reports

No abstract provided.

Quasi Serializability: A Correctness Criterion For Interbase, Ahmed K. Elmagarmid

Department of Computer Science Technical Reports

No abstract provided.