Computer Sciences Commons^™

Indexing And Distributing A General Patterned Spare Array, Daria Dooling, Lenore Mullin

Computer Science Technical Reports

High performance computing and communication (HPCC) requires that space and time usage are kept to a minimum when solving very large scientific problems. These problems often are represented by sparse systems, and in particular banded systems. In this paper, a new banded array index algorithm is presented that uses substantially less memory than the BLAS (Basic Linear Algebra Subroutines) representation. The algorithm presented here works for multi-dimensional arrays and on all bandwidths. It is visualized as a layer between the applications and the data, thus shielding the caller from the complexities of the sparse representation. Information is returned to the …

Ccsp - A Formal System For Distributed Program Debugging, Beth Arrowsmith, Bruce Mcmillin

Computer Science Technical Reports

One of the major problems with programming in a parallel/distributed environment is the difficulty in debugging the programs due to their complex interactions. One can have results that appear random, but when given a complete knowledge of the specific run-time behavior, the results are foregone. Unfortunately, this complete knowledge is not generally attainable in a distributed system. In order to develop a system for debugging distributed program and, for the more general case, ensuring their correctness at run-time, we built a distributed execution enviromnent based on Hoare's CSP [5] which allows for the execution and evaluation of embedded assertions within …

Parallel Adaptive Mesh Refinement Algorithms, Mustafa Keskin, Fikret Ercal

Computer Science Technical Reports

This study is aimed at developing 2D parallel adaptive mesh refinement algorithms for engineering applications such as penetration mechanics, manufacturing and combustion which use the finite element method for simulation. A new algorithmic approach, called piecewise adaptive mesh refinement for parallelization, is developed and implemented to run on a sequential machine. Performance of the new method is compared against a conventional advancing front technique proposed earlier. A parallel implementation model to run on a massively parallel computer is proposed and its expected efficiency is analyzed theoretically. Furthermore, some issues concerning parallelization and task partitioning are also discussed. In addition, a …

A Deterministic Membership Algorithm In Asynchronous Distributed Systems, P. Su, B. Mcmillin, A. Dekock

Computer Science Technical Reports

This work presents a deterministic asynchronous membership protocol (AMP). Conceptually a membership algorithm provides a means of recruiting members (machines) in a distributed system. Currently most of the research in membership recruiting emphasizes how to obtain the members after a machine fail-stop has occurred during the system operation, and the membership algorithms proposed arc non-deterministic. This work extends the research to develop a deterministic membership algorithm to recruit machines dynamically at the system cold-start. Once it is possible to recruit machines at system cold-start, then it is trivial to recruit members after a machine fail-stop has occurred during the system …

Using Temporal Subsumption To Generate Efficient Error-Detecting Distributed Algorithms, Martina Schollmeyer, Bruce Mcmillin

Computer Science Technical Reports

Distributed algorithms can use executable assertions, which can be derived from program verificatioll or specified in an ad hoc manner, to detect. errors at run-time. However, there may be more assertions available than are really unecessary, and embedding all of them into the program to be checked at run-time would make error-detection very inefficient. For safety-critical systems we often need to make decisions very quickly and cannot allow too much time to be spent on error detection.

The new technique of temporal submission, which is introduced in this dissertation, examines the dependencies between the individual assertions along program execution paths. …

The Formal Description Of Resource Deadlock In Distributed Systems, P. Lu, B. Mcmillin

Computer Science Technical Reports

Deadlock detection is a fundamental problem in a distributed system and has been extensively studied in the past few years. Many distributed deadlock detection/resolution alg·orithms have been proposed, but most of them either have not given a correctness proof or have given an informal proof by using intuitive operational arguments. Informal arguments are prone to errors and many of the published algorithms have been fouud to be incorrect. In trying to avoid this situation, the development of a formal approach to the algorithm correctness proof is required.

In this work, a formal resource deadlock model with global and local clocks …

Designing A New Programming Methodology For Optimizing Array Accesses In Complex Scientific Problems, Larry Coffin

Opportunities for Undergraduate Research Experience Program (OURE)

Many problems of interest to scientists and engineers, such as fluid flow and stress analysis, require the solution of complex PDEs. Often the solution requires discretizing the physical domain into a mesh or grid then stepping from a given initial state towards some final state using small incremental time steps. Grid sizes can reach several thousand to hundreds of thousands of elements and the number of time steps required to solve the problem can vary from several thousand to tens of thousands or more. Traditional programming techniques are unable to take advantage of the non-random grid access patterns and generally …

Image Processing Techniques And Implementations In Software For Use With A Ccd Camera, Clarence Franklin Jr.

Opportunities for Undergraduate Research Experience Program (OURE)

The concept of image processing is used whenever there is a reference to digital images. By random and natural errors introduced into the image during collection and transmission, the images are distorted. Image processing techniques are used to eliminate these error before viewing of the images. For this experiment, the images provided by the ST-6 CCD Camera System will be used in the development and implementation of image processing techniques into a software package.

Load Balancing The Heat Equation In A Heterogeneous Environment With Pvm, N. Nemer-Preece, L. Mullin

Computer Science Technical Reports

Parallel processing is maturing with the ability to program heterogeneous environments and the help of networking systems such as PVM. Heterogeneous multiprocessing has been revolutionized due to tools such as PVM which allows the user to develop code independent of the machine arthitecture. This thesis develops a load balancing algorithm to handle the time march problem, heat conduction. It is based on the speeds of the machines in the current environment.

The heat equation algorithm is enhanced by the Psi Calculus of a Mathematics of Arrays. \l' Calculus allows the indexing of the heat matrix in terms of starts, stops …

Providing Assurance For Reponsive Computing Systems, G. Tsai, B. Mcmillin

Computer Science Technical Reports

A responsive computing system is a hybrid of real-time, distributed and fault-tolerant systems. In such a system, severe consequences will occur if the logical and physical specifications of the system are not met. In this dissertation, an approach to ensure satisfaction of specifications in the operational environment is presented as follows. First, we specify properties of the system using ITL formulas. Next, we collect, at runtime, events and maintain equivalent event histories to represent system execution. Finally, we apply a decision procedure to determine satisfaction of the formulas. A run-time evaluation system was built according to this approach and we …

Skin Cancer Diagnosis Using Hierarchal Neural Networks And Fuzzy Logic, H. C. Lee, F. Ercal

Computer Science Technical Reports

Skin cancer, the most common cancer in the United States that affects about 600,000 Americans every year, accounts for 1% of all cancer deaths. Among all, Malignant Melanoma is the most virulent form of skin cancer that is responsible for 75% of all deaths from skin cancer. In 1992, approximately 32,000 people are expected to develop melanoma and about 6,700 will die. However, even malignant melanoma can be treated successfully if detected in the early phase. Therefore, our research goal is to diagnose skin cancer, especially malignant melanoma.

In this study, only the digitized images obtained from color tumor slides …

Classification Characteristics Of Som And Art2, J. Aleshunas, D. St. Clair, W. Bond

Computer Science Technical Reports

Artificial neural network algorithms were originally designed to model human neural activities. They attempt to recreate the processes involved in such activities as learning, short term memory, and long term memory. Two widely used artificial neural network algorithms are the Self-Organizing Map (SOM) and the Adaptive Resonance Theory (ART2). Each was designed to simulate a particular biological neural activity. Both can be used as unsupervised data classifiers.

This paper compares performance characteristics of two unsupervised artificial neural network architectures; the SOM and the ART2 networks. The primary factors analyzed were classification accuracy, sensitivity to data noise, and sensitivity to the …

Classification Characteristics Of Som And Art2, J. J. Aleshunas, Daniel C. St. Clair, William E. Bond

Mathematics and Statistics Faculty Research & Creative Works

Artificial neural network algorithms were originally designed to model human neural activities. They attempt to recreate the processes involved in such activities as learning, short term memory, and long-term memory. Two widely used unsupervised artificial neural network algorithms are the Self-Organizing Map (SOM) and Adaptive Resonance Theory (ART2). Each was designed to simulate a particular biological neural activity. Both can be used as unsupervised data classifiers. This paper compares performance characteristics of two unsupervised artificial neural network architectures; the SOM and the ART2 networks. The primary factors analyzed were classification accuracy, sensitivity to data noise, and sensitivity of the algorithm …

Generating Indexing Functions Of Regularly Sparse Arrays For Array Compilers, Scott Thibault, Lenore Mullin, Matt Insall

Computer Science Technical Reports

There are many applications involving arrays that contain non-zero components in regular geometric partitions. These include triangular, diagonal, tridiagonal, banded, etc. When computing with this type of arrays, they are usually stored in a packed form and computations are performed with only the non-zero components. This packed form requires an indexing function that maps an index of the array to an index of the packed lexico-graphically stored array. This paper presents a method of describing regular partitions and of automatically generating an indexing function from that description. These methods enable an array compiler to compile array operations on these type …

A Reduction Semantics For Array Expressions:The Psi Compiler, L. Mullin, S. Thibault

Computer Science Technical Reports

No abstract provided.

Formal Verification Of Distributed Deadlock Detection Algorithm Using A Time-Dependent Proof Technique, Pei-Yu Li, Bruce Mcmillin

Computer Science Technical Reports

A large number of published distributed deadlock detection/resolution algorithms are found to be incorrect because they have used informal approaches to prove the correctness of their algorithms. In this paper, we present a formal approach for the correctness proof and give an example of the proof. In this proposed approach, a formal model of distributed deadlock is presented with a local-time deadlock specification for correctness verification. With the formal model, we have an insight into the definition of deadlock in local views which is used to show the existence of a real deadlock. A rigorous proof to show the equivalence …

Conjugating Polynomials On Finite Rings, M. Insall, L. Mullin, R. Wilkerson

Computer Science Technical Reports

No abstract provided.

A Pipeline Implementation Of Lu-Decomposition On A Hypercube, Scott Thibault, Lenore Mullin

Computer Science Technical Reports

This paper presents a method of performing LU-Decomposition on a hypercube. The algorithm is constructed similar to the way a pipeline would be used in hardware or on a systolic array processor. Using this method eliminates the need to broadcast data to all the processors at each iteration of the algorithm. Communication takes place at each iteration but since we are using a pipeline model, the communication is between each processor and the next processor in the pipeline. On the hypercube this communication can be done in parallel by using the Gray code ordering to embed a ld mesh (pipeline) …

Formal Methods For Portable, Scalable, Scheduling, Routing And Communication Protocol, Lenore M. R. Mullin, Scott A. Thibault, Daria R. Dooling, Erik A. Sandberg

Computer Science Technical Reports

The PRAM model has been shown to be an optimal design for emulating both loos and tightly coupled multiprocessors for unit time operations. Extensions to this design employ software pipelining on a network of homogeneous workstations. Partitioning array data structures and pipelining groups of partitions to processors can minimize latency and bottlenecking on distributted message passing multiprocessing architectures. Our previous paper developed a general message passing design that was conjectured to port to a CMS and scale to more processors connected via TCPIP protocol. This paper presents the results of of our ported and scaled designs. We have indeed developed …

Effective Data Parallel Computation Using The Psi Calculus, L. R. Mullin, M. A. Jenkins

Computer Science Technical Reports

No abstract provided.

Efficient Run-Time Assurance In Distributed Systems Through Selection Of Executable Assertions, Martina Schollmeyer, Bruce Mcmillin

Computer Science Technical Reports

Run-time assurance of a distributed system can be obtained by comparing, at run-time, the behavior of the program with the expected behavior described in the program's specification. Executable assertions, embedded into the program code, can determine when there are discrepancies, due to processor failures, between actual and expected behavior. Thus, there is no global monitoring scheme but processes will check each other.

A non-faulty process will always perform correct computation. It can detect errors in other processes after receiving information from them and checking it against expected values by using executable assertions. In order to efficiently check programs at run-time, …

Parameter Tuning For The Max Expert System, Christopher J. Merz, M. J. Pazzani

Computer Science Faculty Research & Creative Works

We investigate methods for tuning numeric parameters in Nynex MAX, a telephone trouble screening expert system. Steepest descent, hillclimbing, and simulated annealing parameter adjustment strategies are applied to the problems of maximizing classification accuracy and minimizing misclassification cost. For both of those optimization problems we evaluate each algorithm''s ability to tune initial parameters for several situations

A Fuzzy Logic-Based Foundation For Analyzing Imprecise Conflicting Requirements, J. Yen, Xiaoqing Frank Liu

Computer Science Faculty Research & Creative Works

Imprecise requirements are represented by the canonical form in test-score semantics. The concepts of feasibility, satisfiability, and specificity are formalized based on the fuzzy sets. The relationships between requirements are classified to be conflicting and cooperative. A feasible overall requirement can thus be formulated based on the tradeoff analysis of the conflicting requirements by using fuzzy multi-criteria optimization technique

An Improved Characterization Of 1-Step Recoverable Embeddings: Rings In Hypercubes, Jun-Lin Liu, T.J. Sager, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

An embedding is 1-step recoverable if any single fault occurs, the embedding can be reconfigured in one reconfiguration step to maintain the structure of the embedded graph. In this paper we present an efficient scheme to construct this type of 1-step recoverable ring embeddings in the hypercube. Our scheme will guarantee finding a 1-step recoverable embedding of a length-k (even) ring in a d-cube where 6 less than or equal to k less than or equal to (3/4)2/sup d/ and d greater than or equal to 3, provided such an embedding exists. Unlike previously proposed schemes, we solve the general …

Neural Network Diagnosis Of Malignant Melanoma From Color Images, Fikret Erçal, Hsi-Chieh Lee, William V. Stoecker, Randy Hays Moss, Anurag Chawla

Computer Science Faculty Research & Creative Works

Malignant melanoma is the deadliest form of all skin cancers. Approximately 32,000 new cases of malignant melanoma were diagnosed in 1991 in the United States, with approximately 80% of patients expected to survive 5 years. Fortunately, if detected early, even malignant melanoma may be treated successfully, Thus, in recent years, there has been rising interest in the automated detection and diagnosis of skin cancer, particularly malignant melanoma. Here, the authors present a novel neural network approach for the automated separation of melanoma from 3 benign categories of tumors which exhibit melanoma-like characteristics. The approach uses discriminant features, based on tumor …

Skin Cancer Diagnosis Using Hierarchical Neural Networks And Fuzzy Logic, Hsi-Chieh Lee

Masters Theses

"Skin cancer, the most common cancer in the United States that affects about 600,000 Americans every year, accounts for 1 % of all cancer deaths. Among all, Malignant Melanoma is the most virulent form of skin cancer that is responsible for 75% of all deaths from skin cancer. In 1992, approximately 32,000 people are expected to develop melanoma and about 6,700 will die. However, even malignant melanoma can be treated successfully if detected in the early phase. Therefore, our research goal is to diagnose skin cancer, especially malignant melanoma.

In this study, only the digitized images obtained from color tumor …

A Simulated Annealing/Tabu Search Algorithm For The Vehicle Routing Problem, Jeffrey Dale White, Billy E. Gillett

Computer Science Technical Reports

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. …

Process Driven Software Engineering Environments, John Hayes Lampkin, T. Lo, Daniel C. St. Clair

Computer Science Technical Reports

Software development organizations have begun using Software Engineering Environments (SEEs) with the goal of enhancing the productivity of software developers and improving the quality of software products. The encompassing nature of a SEE means that it is typically very tightly coupled with the way an organization does business. To be most effective, the components of a SEE must be well integrated and the SEE itself must be integrated with the organization.

The challenge of tool integration increases considerably when the components of the environment come from different vendors and support varying degrees of “openness”. The challenge of integration with the …

Subsumption In Modal Logic, Dirk Heydtmann, Ralph W. Wilkerson

Computer Science Technical Reports

Subsumption has long been known as a technique to detect redundant clauses in the search space of automated deduction systems for classical first order logic. In recent years several automated deduction methods for non-classical modal logics have been developed. This thesis explores, how subsumption can be made to work in the context of these modal logic deduction methods.

Many modern modal logic deduction methods follow an indirect approach. They translate the modal sentences into some other target language, and then determine whether there exists a proof in that language, rather than doing deduction in the modal language itself. Consequently, subsumption …

The Difficulty Of Approximating The Chromatic Number For Random Composite Graphs, Jeffrey Wayne Jenness, Billy E. Gillett

Computer Science Technical Reports

Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are NP-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to …