Computer Sciences Commons^™

Composite Stock Cutting Through Simulated Annealing, Pipatpong Poshyanonda, Cihan H. Dagli

Computer Science Technical Reports

This paper explores the use of Simulated Annealing as an optimization technique for the problem Composite Material Stock Cutting. The shapes are not constrained to be convex polygons or even regular shapes. However, due to the composite nature of the material, the orientation of the shapes on the stock is restricted. For placements of various shapes, we show how to determine a cost function, annealing parameters, and performance.

Ilona: An Advanced Cai Tutorial System For The Fundamentals Of Logic, Otto Mayer, Graham E. Oberem, Fillia Makedon

Computer Science Technical Reports

An advanced tutorial system for teaching the fundamentals of logic has been developed to run on UNIX work stations and commonly available micro-computers. An important part of this tutorial is the intelligent problem solving environment which allows students to practise wiriting logical sentences in mathematical notation. A natural language system for intelligent logic narrative analysis (ILONA) allows students to type in their own logical sentences in plain English and then have the computer check their working when they write these in mathematical form. ILONA is an intelligent tutoring system which allows students a great deal of initiative in problem solving …

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

Computer Science Technical Reports

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 a5 the fault occurs instead of at problem termination. For 112 processors, the fault-latency time of the ID algorithm is l/11 of that of checksum algorithm with a run-time penalty of …

Composite Stock Cutting Through Simulated Annealing, Pipatpong Poshyanonda, Cihan H. Dagli

Computer Science Technical Reports

This paper explores the use of Simulated Annealing as an optimization technique for the problem Composite Material Stock Cutting. The shapes are not constrained to be convex polygons or even regular shapes. However, due to the composite nature of the material, the orientation of the shapes on the stock is restricted. For placements of various shapes, we show how to determine a cost function, annealing parameters, and performance.

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

Computer Science Technical Reports

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 a5 the fault occurs instead of at problem termination. For 112 processors, the fault-latency time of the ID algorithm is l/11 of that of checksum algorithm with a run-time penalty of …

Formal Methods Of Real-Time Systems, Su-Mei Tsai, Bruce M. Mcmillin

Computer Science Technical Reports

Formal aid in specification and verification techniques have become an accepted approach to achieving reliable software for life-critical real-time systems, in which testing may be impossible or too dangerous, since the real inputs to the systems come from the real world. Modelling, assertion languages, and proof systems are three major components that are employed to accomplish the confidence of safe real-time environments. This paper examines these currently available techniques that are used for safety analysis of real-time systems.

Application-Oriented Fault-Tolerant Parallel Branch & Bound, Aggie Sun, Bruce M. Mcmillin

Computer Science Technical Reports

An important aspect which is often overlooked in the software design cycle is the question of reliability. Many methodologies in the past have attempted to provide reliability efficiently but have never been successful at eliminating explicit time and space redundancy. The approach taken here is based on the Application-Oriented Fault Tolerance Paradigm which provides reliability by examining the behavior and properties of the application. This paper will demonstrate how fault detecting constraints are developed and incorporated using the Application-Oriented Fault Tolerance paradigm for the class of Branch and Bound algorithms. Branch and bound algorithms are a type of combinatorial search …

Multi Cast Routing In Unreliable Networks, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

The efficient routing of messages in a multicomputer interconnection network is the key to the performance of such a network. Multicast communication refers to the delivery of a message from a source node to several destination nodes. Although multicast is highly desirable for many applications, it is not directly supported in most multicomputer architectures. This paper examines existing algorithms for multicast routing in multicomputer networks and groups them into a number of categories such as multicast trees, multicast paths, multicast stars, etc. These algorithms are evaluated in terms of deadlock handling, adaptability and suitability for wormhole routing. Wormhole routing is …

Formal Generation Of Executable Assertions For A Fault-Tolerant Parallel Bitonic Sort, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

No abstract provided.

Fast Symmetric Graph Drawing: Theory And Realization, R. T. Pacheco, J. B. Manning

Computer Science Technical Reports

This thesis explores the computational techniques necessary to efficiently realize certain optimal algorithms for the production of drawings which exhibit maximum axial and rotational symmetries of abstract graphs.

The problem of geometric symmetry detection for general graphs has been shown to be NP-complete. However, optimal algorithms have recently been established for the detection of symmetry in trees, outerplanar graphs, and embedded planar graphs. This thesis focuses on the utilization of these algorithms to efficiently produce maximally symmetric drawings of graphs from the classes of symmetric trees and outerplanar graphs.

The construction of symmetric tree drawings is presented first. Following a …

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 …

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.

An Object-Oriented Learning/Design Support Environment, Fillia Makedon, Julie C. Jumes, Jill P. David

Computer Science Technical Reports

We present an object-oriented experimental learning and design support environment, call AVT, for an Algorithm Visualization Tool, implemented in Digitalk's Smalltalk/V1 on a Macintosh II2, AVT provides a domain- independent visualization tool, an exploratory learning environment, and an experimental heuristic design environment. Algorithm visualization is the exploration of ways to visualize intuitively the computational behavior of an algorithm using multiple views, some of which are visual in the graphical sense [2,4]. AVT employs other views (combining text and graphics) to explain the problem, the strategy, the heuristics, and the reasoning process behind the solutions. User interaction in AVT includes not …

A Metric Towards Efficient Exhaustive Test Pattern Generation, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

A viable technique [7] in built-in self-test (BIST)[2] is to generate test patterns pseudo-exhaustively by using linear feedback shift registers (LFSR's). The goal is to find an appropriate primitive polynomial of degree d that will generat 2d test patterns in order to exercise all circuit outputs simultaneously. In an attempt to reduce the degree d of the polynomial the following strategy was proposed in [6,5]. In the first phase, partition the circuit into segments by inserting a small number of register cells, so that the input dependency of any circuit element in the segments is no more than d. Then, …

On Minimizing Hardware Overhead For Exhaustive Circuit Testability, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

Exhaustive built-in self testing is given much attention as a viable technique in the context of VLSI technology. In this paper, we present heuristic in order to make exhaustive testing of combinational circuits practical. The goal is to place a small number of register cells on the nets of the input circuit so that the input dependency of combinational elements in the circuit is less than a small given integer k. Our heuristic guarantees that each output can be individually tested with 2k test patterns and can be used as a subroutine to generat efficient test patterns to test all …