Computer Sciences Commons^™

Smili-Visualization Of Asynchronous Massively Parallel Programs, Rashi Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyse the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMil...l (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Comparison Of Three Axiomatic Systems For Csp, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

Currently software engineering practices use relatively few formal methods. However, formal methods can be used to find errors earlier in the software cycle and hence reduce software cost. One useful formal method is program verification. The axiomatic approach to program verification uses assertions to characterize properties of program variables and relationships between them at various stages of program execution. In order to verify these assertions, axioms or inference rules are needed for each statement as well as some statement-independent inference rules. The message passing and nondeterminism of a distributed programming language present special difficulties. This paper examines and compares three …

A Visualization Model For Massively Parallel Algorithms, R. Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyze the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMILI (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Applying Parallel Bidirectional Search To A System For The Diagnosis Of Faults, J. E. Finlay, R. W. Wilkerson

Computer Science Technical Reports

Decreasing the time it takes an application to run is always an important concern. One of the ways to achieve this is through separating work in the application that need not be run sequentially onto two or more processors to be run in parallel. This work will take a look at an attempt to do this in one of the primary application areas of Artificial Intelligence, diagnosis.

Reiter's theory is presented for the diagnosis of faults from first principles, as well as a correction to the algorithm which defines the theory. An existing implementation of the theory is also discussed. …

An Implementation Of "Theorem Proving With Lemmas", C. J. Merz, R. W. Wilkerson

Computer Science Technical Reports

Two resolution proof strategies developed by Peterson [ Pe76j are implemented by modifying Otter, an existing automated theorem prover. The methods, Lock-T refutation and LNL-T refutation, are generalizations of unit refutation and input refutation, respectively, to non-Hom sets and represent independent, equivalent but opposite ways of searching. Thus, the two techniques can be run simultaneously, exchanging only important intermediate results known as lemmas.

The algorithms used in the implementation, which are based on a corrected version of the foundational work, are outlined in detail and justified. Next, the newly implemented strategies are tested individually and together on various non-Horn challenge …

Object Orientation In The Cim Environment, B. M. Higgins, J. B. Prater

Computer Science Technical Reports

Manufacturing industries are constantly looking for better ways to develop the software required to plan and control production processes. Experimental software is being developed using objectoriented program development techniques. There are many prototypes being used and tested at both academic and industrial institutions around the world.

The purpose of this paper is to examine a selection of these systems in order to highlight some of the main benefits which are being achieved by using object-oriented methods over the use of conventional approaches. Practical considerations are made concerning the long-term adoption of object-oriented methodologies in software development for Computer Integrated Manufacturing …

Investigation Of Threaded Code, K. E. Graves, Paul D. Stigall

Computer Science Technical Reports

The design, structure and performance of threaded code are examined through the development of a threaded. code classification system and the modification of the threaded code technique used by a Forth programming language implementation. The classification system distinguishes threaded code designs by three elements: the interpreter, the code structure and the reference method to routines. Threaded code designs from the literature are described using the new classification scheme. The threaded code techniques of variable depth indirect threaded code and token indirect token threaded code are examined in a Forth programming language system on an INMOS IMS T222 transputer. Their design …

Incremental Learning Of Numeric Clusters In Classifier Systems, K. R. Hacke, D. C. St. Clair

Computer Science Technical Reports

Classifier systems are knowledge-based learning algorithms which take training instances as input and produce a set of rules as output Many classifier systems represent the knowledge they learn in the form of one or more decision trees. Accurate knowledgebase systems for a variety of domains have been constructed by generating decision trees using J. R. Quinlan's (1986) inductive algorithm ID3 and P. E. Utgoffs (1988) IDS. IDS is an incremental version of ID3.

Unfortunately, all these algorithms suffer from the inability to easily and effectively handle domains with numeric-valued attributes. Numeric attributes are those whose values are taken from a …

Modeling The Software Design Project, C. C. Dziedzic, D. C. St. Clair

Computer Science Technical Reports

The information content of the software design product as needed by various user communities is identified. Definitions of design in classical engineering disciplines are investigated and then applied specifically to the area of software design. The Entity-Relationship model is used to describe the information content of the software design product. All the relationship types and entity types that compose the design product are described in detail. The Military Standard: Defense System Software Development, DOD-STD-2167A, is analyzed to determine how it meets the relationship type requirements.

Investigation Of Threaded Code, K. E. Graves, Paul D. Stigall

Computer Science Technical Reports

The design, structure and performance of threaded code are examined through the development of a threaded. code classification system and the modification of the threaded code technique used by a Forth programming language implementation. The classification system distinguishes threaded code designs by three elements: the interpreter, the code structure and the reference method to routines. Threaded code designs from the literature are described using the new classification scheme. The threaded code techniques of variable depth indirect threaded code and token indirect token threaded code are examined in a Forth programming language system on an INMOS IMS T222 transputer. Their design …

Applying Parallel Bidirectional Search To A System For The Diagnosis Of Faults, J. E. Finlay, R. W. Wilkerson

Computer Science Technical Reports

Decreasing the time it takes an application to run is always an important concern. One of the ways to achieve this is through separating work in the application that need not be run sequentially onto two or more processors to be run in parallel. This work will take a look at an attempt to do this in one of the primary application areas of Artificial Intelligence, diagnosis.

Reiter's theory is presented for the diagnosis of faults from first principles, as well as a correction to the algorithm which defines the theory. An existing implementation of the theory is also discussed. …

An Implementation Of "Theorem Proving With Lemmas", C. J. Merz, R. W. Wilkerson

Computer Science Technical Reports

Two resolution proof strategies developed by Peterson [ Pe76j are implemented by modifying Otter, an existing automated theorem prover. The methods, Lock-T refutation and LNL-T refutation, are generalizations of unit refutation and input refutation, respectively, to non-Hom sets and represent independent, equivalent but opposite ways of searching. Thus, the two techniques can be run simultaneously, exchanging only important intermediate results known as lemmas.

The algorithms used in the implementation, which are based on a corrected version of the foundational work, are outlined in detail and justified. Next, the newly implemented strategies are tested individually and together on various non-Horn challenge …

Object Orientation In The Cim Environment, B. M. Higgins, J. B. Prater

Computer Science Technical Reports

Manufacturing industries are constantly looking for better ways to develop the software required to plan and control production processes. Experimental software is being developed using objectoriented program development techniques. There are many prototypes being used and tested at both academic and industrial institutions around the world.

The purpose of this paper is to examine a selection of these systems in order to highlight some of the main benefits which are being achieved by using object-oriented methods over the use of conventional approaches. Practical considerations are made concerning the long-term adoption of object-oriented methodologies in software development for Computer Integrated Manufacturing …

Incremental Learning Of Numeric Clusters In Classifier Systems, K. R. Hacke, D. C. St. Clair

Computer Science Technical Reports

Classifier systems are knowledge-based learning algorithms which take training instances as input and produce a set of rules as output Many classifier systems represent the knowledge they learn in the form of one or more decision trees. Accurate knowledgebase systems for a variety of domains have been constructed by generating decision trees using J. R. Quinlan's (1986) inductive algorithm ID3 and P. E. Utgoffs (1988) IDS. IDS is an incremental version of ID3.

Unfortunately, all these algorithms suffer from the inability to easily and effectively handle domains with numeric-valued attributes. Numeric attributes are those whose values are taken from a …

Modeling The Software Design Project, C. C. Dziedzic, D. C. St. Clair

Computer Science Technical Reports

The information content of the software design product as needed by various user communities is identified. Definitions of design in classical engineering disciplines are investigated and then applied specifically to the area of software design. The Entity-Relationship model is used to describe the information content of the software design product. All the relationship types and entity types that compose the design product are described in detail. The Military Standard: Defense System Software Development, DOD-STD-2167A, is analyzed to determine how it meets the relationship type requirements.

Vehicle Routing Using The Sweep Algorithm In Parallel, Jana G. Beattie, Carol L. Spelman

Opportunities for Undergraduate Research Experience Program (OURE)

This paper presents a parallel version of the Sweep Algorithm, a heuristic solution to the smgle-termma] vehicle routing problem The Sweep Algorithm uses a duster-first route-second approach in finding a near-optimal set of routes. The clusters of delivery points are formed by using the terminal as the center and moving around it m a sweeping fashion After a duster is defined, the route is found with a traveling salesperson algorithm.

The parallel version begins the sweep at different angles and performs both forward and backward sweeps. Each node handles a sweep and returns information concerning total distance traveled to the …

Simulated Annealing On The Composite Graph Coloring Problem, Kevin Alons

Opportunities for Undergraduate Research Experience Program (OURE)

The composite graph is a finite undirected graph G with no loops and no multiple edges and with positive integers associated with each vertex of G. The number of integers associated with each vertex is the chromaticity of the vertex. The chromatic degree of a vertex v is the sum of the chromaticity of v and the chromaticities of all vertices adjacent to v. The graph G is a v-composite graph if the chromaticities are not equal.

The Traveling Salesman Problem A Parallel Branch And Bound Solution, Tracy Orton, Lan Tran

Opportunities for Undergraduate Research Experience Program (OURE)

A book published in Germany in 1852 said of the successful traveling salesman: "The most important aspect is to cover as many locations as possible without visiting the same location twice." This quote is the earliest mention of the "Traveling Salesman Problem" (TSP). There are many algorithms to solve the TSP, the one we implemented was the Branch and Bound algorithm. The TSP graph G is completely connected by a set of edges E, with a non-negative cost C_ij associated with each edge. A tour of the graph is a cycle containing all vertices once and only once, starting …

An Overview And Evaluation: Computer Software To Aid Students In Prewriting, Writing, And Revision, Mary Lou Shomaker

Opportunities for Undergraduate Research Experience Program (OURE)

The research on computer software to aid inexperienced writers was done from May, 1990 through August, 1990, and involved examining software that would help students improve their writing. The softwares also were evaluated according to their value for use in computer assisted writing classes. The project had three objectives: 1) to evaluate software designed to aid the writer in the pre-writing, writing, and revising stages; 2) to identify the components of this type of software; 3) to recommend software for the beginning academic writer.

Computer Visualization Of Irrotational Flow Over Bluff And Streamlined Bodies, Nora Okong' O

Opportunities for Undergraduate Research Experience Program (OURE)

Computer programs were developed to visualize irrotational flow over bluff bodies (circular cylinders and half-bodies) and streamlined bodies (elliptical cylinders and airfoils). The method of superposition of flows was used, with stream functions or complex velocity potentials for fundamental flows being added to obtain the flows over the bodies. For the flow over the circular cylinders, half-bodies and elliptical cylinders, the stream function was calculated directly. The flow over the airfoil was obtained by Joukowski mapping of the imaginary part of the complex velocity potential for flow over a circular cylinder.

The programs developed will be valuable learning tools for …

Computer Modeling Of A Liquid Fuel Spray, Clemin R. Goodin Jr.

Opportunities for Undergraduate Research Experience Program (OURE)

The initial phase of this project involved manipulation of a lengthy FORTRAN computer code named "Kirwan." The code originated from England many years ago and was transferred to UMR by Dr. Drallmeier. Dr. Drallmeier had the code on a series of 5.25 inch floppy diskettes and the objective of the project was to load the code on to the Apollo computer system and be able to use it....The second phase of the project was begun in early November 1990 and is currently ongoing. The objective of this project is to predict "Rosin-Rammler" (RR) distribution equations for a fuel spray, given …

Using Software To Demonstrate Kinematics Of Gear Sets, John F. Hall

Opportunities for Undergraduate Research Experience Program (OURE)

The research was done in the area of developing software which could be used to demonstrate the motion of gears. To demonstrate this motion involved learning about programming using graphics. Engineering skills were used in the programming in various ways. One way was in developing and implementing the equations and theory. The more critical engineering aspect of this project is in determining what is effective in demonstrating the kinematic principles associated with gear sets.

The programs will be a helpful aid in showing students what is happening with the motion of gear sets. Not only will instructors be allowed to …

A Computer Graphics Program For Displaying Water Molecules On A Dn3500 Apollo Workstation, Michael A. Stuller

Opportunities for Undergraduate Research Experience Program (OURE)

A computer graphics program is developed for displaying water molecule configurations on the screen of a DN3500 Apollo workstation. The motivation was to generate a fast display of output from molecular dynamics or Monte Carlo computer simulations. Input to the program consists of a listing of the Cartesian coordinates of the atomic constituents of the molecules. Options in the program include: 1) number of molecules; 2) plot size; 3) atomic radii; 4) superposition of substrate atomic positions; 5) viewing angle; and 6) color-coded and/or numbered atoms. The program is written in Fortran.

Suggestions For Improvements In Current Computer Image Processing Methods In Detection And Quantification Of The Severity Of Atrophic Rhinitis In Pigs, Jimmy Yu

Opportunities for Undergraduate Research Experience Program (OURE)

This paper investigates several techniques to aid in the utilization of computer image processing methods to detect and quantify the severity of atrophic rhinitis in pigs. An algorithm for reducing the complexity of matrix multiplications from O(n³) to O(n^2.81) is explored. A one-pixel-wide edge detection method is also studied. These techniques are considered for improving the accuracy, repeatability, and speed of existing detection and quantification methods.

Termination Via Conditional Reductions, Timothy B. Baird, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

We Generalize the Notion of Rewriting Modulo an Equational Theory to Include a Special Form of Conditional Reduction. We Are Able to Show that This Conditional Rewriting Relation Restores the Finite Termination Property Which is Often Lost When Rewriting in the Presence of Infinite Congruence Classes. in Particular, We Are Able to Handle the Class of Collapse Equational Theories Which Contain Associative, Commutative, and Identity Laws for One or More Operators.

A Model-Based Approach For Organizing Quantitative Computations, J. Sticklen, A. Kamel, William E. Bond

Computer Science Faculty Research & Creative Works

Model based reasoning (MBR) is currently receiving wide spread attention because it offers a way to circumvent the brittleness of reasoning systems built solely on associational knowledge. To date, most MBR approaches have focused on the use and manipulation of qualitative models. The authors report their experience in applying techniques of functional reasoning to the general problem of organizing quantitative calculations. As a testbed, they have solved a problem initially posed at the Model-Based Diagnosis workshop (Paris, July, 1989): representing an automotive cruise control system. The results show that the principles of the functional reasoning approach can provide leverage in …

Simulating Adaptive Load Sharing Policies On An Ipsc/2 Multicomputer, Yuh Jong Hu, Billy E. Gillett

Computer Science Faculty Research & Creative Works

Unlike most other adaptive load sharing (LS) policy studies, each node in the distributed system is modeled as a central server model represented by a closed queueing network (QN). The primary objective of this study is to use a simulation model to find the improvement for an adaptive LS policy in a distributed system. In homogeneous distributed systems, the simulation results in this study show that the performance improvements between no LS, LS with task placement, and LS with task migration are very small. These results are quite different from other studies, which show a significant improvement of mean response …

Fault-Tolerant Parallel Matrix Multiplication With One Iteration Fault Detection Latency, Chul Eui Hong, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

The checksum technique is a low-cost method to detect errors in matrix operations performed by processor arrays. The fault detection of this method is done only at problem termination, so this method is not an effective fault tolerance technique for large scale matrix multiplication. This paper presents a new algorithm, the ID algorithm, which minimizes the fault-detection latency, In the ID algorithm, a fault is detected as soon as the fault occurs instead of at problem termination. For n2 processors, the fault-latency time of the ID algorithm is l/n of that of checksum algorithm with a run-time penalty of O(nlog2n) …

Pattern Recognition For Nondestructive Evaluation, S. Morris, P. O'Rorke, William E. Bond, M. M. Amirfathi, Daniel C. St. Clair

Computer Science Faculty Research & Creative Works

The issues involved in automating nondestructive evaluation (NDE) techniques are outlined. Attention is given to research focused on the application of machine learning techniques to the construction and maintenance of knowledge-based systems which are capable of evaluating the readings from nondestructive tests that have been performed on aircraft components. Preliminary results obtained from this research are described. In particular, the authors discuss the application of a symbolic machine learning algorithm, ID3, to the NDE problem. ID3 has been used by Douglas Aircraft to classify defects in sets of standard NDE reference blocks. Based on the preliminary results, a need for …

A Visualization Model For Massively Parallel Algorithms, Rashi Khanna, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

A visualization model has been developed to analyze the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns. These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMILI (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff s Faces have been selected to …