Computer Sciences Commons^™

Diagnosis Of Malignant Melanoma Using A Neural Network, Anurag Chawla, Fikret ErçAl

Computer Science Technical Reports

Malignant melanoma is the deadliest form of all skin cancers. Approximately 32,000 new cases of malignant melanoma were diagnosed in 1991, with approximately 80 percent of patients expected to survive five years [1], Fortunately, if detected early, even malignant melanoma may be treated successfully. Thus, in recent years, there has been a rising interest in the automated detection and diagnosis of skin cancer, particularly malignant melanoma [2]. In this thesis, a novel neural network approach for the automated distinction of melanoma from three benign categories of tumors which exhibit melanoma-like characteristics is presented. The approach is based on devising new …

An Analysis Of Modern Cryptosystems, Thomas Gerald Sauder, Chung You Ho

Computer Science Technical Reports

Since the ancient Egyptian empire, man has searched for ways to protect information from getting into the wrong hands. Julius Caesar used a simple substitution cipher to protect secrets. During World War II, the Allies and the Axis had codes that they used to protect information. Now that we have computers at our disposal, the methods used to protect data in the past are ineffective. More recently, computer scientists and mathematicians have been working diligently to develop cryptosystems which will provide absolute security in a computing environment.

The three major cryptosystems in use today are DES, RSA, and the Knapsack …

Parallel Genetic Algorithms For The Dag Vertex Splitting Problem, Matthias Mayer, Fikret ErçAl

Computer Science Technical Reports

Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given δ. The problem has been proven to be NP-hard.

A Sequential Genetic Algorithm has been developed to solve the DAG Vertex Splitting Problem. Unlike a standard Genetic Algorithm, this approach uses a variable chromosome length to represent the vertices that split the …

The Interpolating Random Spline Cryptosystem And The Chaotic-Map Public-Key Cryptosystem, Fengi Hwu, Chung You Ho

Computer Science Technical Reports

The feasibility of implementing the interpolating cubic spline function as encryption and decryption transformations is presented. The encryption method can be viewed as computing a transposed polynomial. The main characteristic of the spline cryptosystem is that the domain and range of encryption are defined over real numbers, instead of the traditional integer numbers. Moreover, the spline cryptosystem can be implemented in terms of inexpensive multiplications and additions.

Using spline functions, a series of discontiguous spline segments can execute the modular arithmetic of the RSA system. The similarity of the RSA and spline functions within the integer domain is demonstrated. Furthermore, …

The Design, Analysis, And Implementation Of Parallel Simulated Annealing And Parallel Genetic Algorithms For The Composite Graph Coloring Problem, Brent S. Elmer, Billy E. Gillett

Computer Science Technical Reports

The composite graph coloring problem (CGCP) is similar to the standard graph coloring problem (SGCP). Associated with each vertex of a composite graph is a positive integer which represents the chromaticity of that vertex. This number is the number of consecutive integers (colors) which must be assigned to the vertex. The goal of the CGCP is to color the graph with as few colors as possible. The largest integer used in the coloring is called the chromatic number of the graph. The CGCP is proven to be NP-complete.

Exact, heuristic, and stochastic methods are analyzed and compared. Exact methods are …

Considerations For Rapidly Converging Genetic Algorithms Designed For Application To Problems With Expensive Evaluation Functions, Richard Patrick Rankin, Ralph W. Wilkerson

Computer Science Technical Reports

A genetic algorithm is a technique designed to search large problem spaces using the Darwinian concepts of evolution. Solution representations are treated as living organisms. The procedure attempts to evolve increasingly superior solutions. As in natural genetics, however, there is no guarantee that the optimum organism will be produced.

One of the problems in producing optimal organisms in a genetic algorithm is the difficulty of premature convergence. Premature convergence occurs when the organisms converge in similarity to a pattern which is sub-optimal, but insufficient genetic material is present to continue the search beyond this sub-optimal level, called a local maximum. …

Cartographic Pattern Recognition Using Template Matching, Angela G. Lammers, Ralph W. Wilkerson, Fikret ErçAl

Computer Science Technical Reports

In creating digital maps from paper maps, the paper map must first be scanned to produce a raster image, and then converted into vector format. Vector format allows non-graphical cartographic information to be stored along with the graphical objects. At the United States Geological Survey, the conversion from raster to vector format is performed by a commercial software package. The package also attempts to classify the graphical objects based on shape, line patterns, and other information gained from the raster file. Since the package frequently fails to classify a significant percentage of the elements in the map, manual map analysis …

Efficient Parallel Algorithms For Some Tree Layout Problems, J Diaz, A Gibbons, Grammati E. Pantziou, M Serna, Paul G. Spirakis, J Toran

Computer Science Technical Reports

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two algorithms in NC. The first solves the minimum length linear arrangement problem for unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM processors. The second algorithm solves the minimum cut arrangement for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and $O(n^2 /\log n)$ CREW PRAM processors.

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Computer Science Technical Reports

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

Genetic Algorithms For Vertex Splitting In Dags, Matthias Mayer, Fikret ErçAl

Computer Science Technical Reports

Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given δ. The problem has been proven to be NP-hard. A Genetic Algorithm is used to solve the DAG Vertex Splitting Problem. This approach uses a variable string length to represent the vertices that split the graph and a dynamic population size. The …

Intermediate Code Generation For Portable Scalable, Compilers. Architecture Independent Data Parallelism: The Preliminaries, Lenore Mullin, C. Chang, S. Huang, Matthias Mayer, N. Nemer, C. Ramakrishna

Computer Science Technical Reports

This paper introduces the goals of the Portable, Scalable, Architecture Independent (PSI) Compiler Project for Data Parallel Languages at the University of Missouri-Rolla. A goal of this project is to produce a subcompiler for data parallel scientific programming languages such as HPF(High Performance Fortran) where the input grammar is translated to a three-address code intermediate language. Ultimately we plan to integrate our work into automated synthesis systems for scientific programming because we feel that it should not be necessary to learn complicated programming techniques to use multiprocessor computers or networks of computers effectively. This paper shows how to compile a …

Modeling Of Supersonic Combustor Flows Using Parallel Computing, Bruce M. Mcmillin, Eric Jui-Lin Lu, Larry Reeves

Computer Science Technical Reports

Computational Fluid Dynamics (CFD) has matured rapidly in the past 20 years and is now an important tool for analyzing and understanding complex fluid flows. Since 1985, CFD has played a vital role in the study of hypersonic flight. It has provided the capability for scientists and engineers to model both internal and external hypersonic flow-fields. Such flows are often impractical or impossible to analyze in laboratory conditions. In particular, the recent application of CFD to the modeling of internal reacting supersonic combustor flows has significantly advanced the understanding of such flows and has increased confidence in the predictive ability …

The Computation Of Supersonic Combustor Flows Using Multi-Computers, Bruce M. Mcmillin, Eric Jui-Lin Lu, Larry Reeves

Computer Science Technical Reports

An explicit computational fluid dynamics (CFD) computer code with parallel processing capability has been developed for the purpose of simulating internal high-speed reacting flows. The code solves the three-dimensional Navier-Stokes equations for compressible flows. The CFD code can be executed on either sequential (single processor) computers or multi-computers (multiple processor machines with distributed memory and message passing between processors). The parallel implementation involves homogeneous domain decomposition between processors with message passing needed only between neighbor processors. The code is validated for a compression ramp, an expansion ramp, a viscous flat plate, and a viscous flat plate with wall injection. These …

How To Program In Ccsp, Elizabeth Arrowsmith, Bruce M. Mcmillin

Computer Science Technical Reports

No abstract provided.

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Leonard F. Wisniewski

Computer Science Technical Reports

No abstract provided.

Vector Layout In Virtual-Memory Systems For Data-Parallel Computing, Thomas H. Cormen

Computer Science Technical Reports

In a data-parallel computer with virtual memory, the way in which vectors are laid out on the disk system affects the performance of data-parallel operations. We present a general method of vector layout called banded layout, in which we divide a vector into bands of a number of consecutive vector elements laid out in column-major order, and we analyze the effect of the band size on the major classes of data-parallel operations. We find that although the best band size varies among the operations, choosing fairly small band sizes—at most a track—works well in general.

Videoscheme: A Programmable Video Editing System For Automation And Media Recognition, James Matthews, Peter Gloor, Fillia Makedon

Computer Science Technical Reports

The recent development of powerful, inexpensive hardware and software support had made digital video editing possible on personal computers and workstations. To date the video editing application category has been dominated by visual, easy-to-use, direct manipulation interfaces. These systems bring high-bandwidth human-computer interaction to a task formerly characterized by slow, inflexible, indirectly-operated machines. However, the direct manipulation computer interfaces are limited by their manual nature, and can not easily accommodate algorithmically- defined operations. This paper proposes a melding of the common direct manipulation interfaces with a programming language which we have enhanced to manipulate digital audio and video. The result …

Ensuring The Satisfaction Of A Temporal Specification At Run-Time, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents an approach to operationally evaluate a temporal specification in a distributed computing environment. First, an algorithm Compute History is proposed to allow every distributed processor to collect events executed by itself and by other processors, and to order the collected events by causality. This algorithm employs neither monitors nor a global clock to order collected events of a processor. These collected events of a processor form an execution history of a distributed computation, and they represent behaviors of all the processors during execution. Next, the semantics of operational evaluation of a temporal assertion is presented. The evaluation …

Neural Network Diagnosis Of Malignant Melanoma From Color Images, Fikret ErçAl, C. Chawla, William V. Stoecker, Randy Hays Moss

Computer Science Technical Reports

Malignant melanoma is the deadliest form of all skin cancers. Approximately 32,000 new cases of malignant melanoma were diagnosed in 1991, with approximately 80 percent of patients expected to survive five years [1]. Fortunately, if detected early, even malignant melanoma may be treated successfully. Thus, in recent years, there has been a rising interest in the automated detection and diagnosis of skin cancer, particularly malignant melanoma [2]. In this paper, we present a novel neural network approach for the automated separation of melanoma from three other benign categories of tumors which exhibit melanoma-like characteristics. Our approach is based on devising …

Visual Inspection Algorithms For Printed Circuit Board Patterns A Survey, Madhav Moganti, Fikret ErçAl, Cihan H. Dagli

Computer Science Technical Reports

The importance of the inspection process has been magnified by the requirements of the modern manufacturing environment. In electronics mass-production manufacturing facilities, an attempt is often made to achieve 100 % quality assurance of all parts, subassemblies, and finished goods. A variety of approaches for automated visual inspection of printed circuits have been reported over the last two decades. In this survey, algorithms and techniques for the automated inspection of printed circuit boards are examined. A classification tree for these algorithms is presented and the algorithms are grouped according to this classification. This survey concentrates mainly on image analysis and …

An Application-Oriented Approach To Distributed Error-Detecting Branch & Bound, Aggie Y. Sun, Hanan Lutfiyya, Bruce Mcmillin

Computer Science Technical Reports

An important aspect which is often overlooked in software _design of distributed environments is that of fault tolerance. Many methodologies in the past have attempted to provide fault tolerance efficiently, but have never been successful at eliminating explicit time and space redundancy. One approach is the Application-Oriented Fault Tolerance Paradigm, which provides fault tolerance by examining the behavior and properties of the application and deriving executable assertions for the detection of faults. Previous work has demonstrated the feasibility of the application-oriented fault tolerance paradigm for various applications. However, the executable assertions were guided by the natural constraints of the problem. …

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

Computer Science Technical Reports

An embedding is said to be 1-step recoverable if any single fault in the embedding can be recovered in one reconfiguration step. In this paper we present a heuristic approach to construct such 1-step recoverable embeddings. We show that to embed a k (even) length ring in ad-cube, where 6 < = k < = 3/4 2d and d < = 3, our scheme will guarantee finding a 1-step recoverable embedding, provided such an embedding exists. Compared to other previously proposed schemes, our scheme achieves much better results. A sufficient condition for the non-existence of 1-step recoverable embeddings for embedding rings of length > 3/4 2d in d-cubes is also given.

Building Segment Trees In Parallel, Peter Su, Scot Drysdale

Computer Science Technical Reports

The segment tree is a simple and important data structure in computational geometry [7,11]. We present an experimental study of parallel algorithms for building segment trees. We analyze the algorithms in the context of both the PRAM (Parallel Random Access Machine) and hypercube architectures. In addition, we present performance data for implementations developed on the Connection Machine. We compare two different parallel alforitms, and we also compare our parallel algorithms to a good sequential algorithm for doing the same job. In this way, we evaluate the overall efficiency of our parallel methods. Our performance results illustrates the problems involved in …

Using Minimal And Maximal Fault Tolerance For The Assessment Of Fault-Tolerant Algorithms, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

No abstract provided.

Fault-Tolerant Distributed Deadlock Detection / Resolution, Pei-Yu Liu, Bruce M. Mcmillin

Computer Science Technical Reports

The problem of deadlock detection in a distributed system has been extensively studied in the past few years. Many algorithms on distributed deadlock detection have been proposed under the assumption that the processors and communication in the system are fault-free. However, in an unreliable distributed system, faulty processors may prevent a deadlock detection algorithm from properly detecting deadlocks. Few of the algorithms proposed in the literature address the issue of handling process failures in a distributed system. This paper proposes a fault-tolerant distributed deadlock detection algorithm which integrates a priority-based probe algorithm with a PMC-based diagnosis model. This algorithm detects …

Relaxing Synchronization In Distributed Simulated Annealing, Chul-Eui Hong, Bruce M. Mcmillin

Computer Science Technical Reports

Simulated annealing is an attractive, but expensive, heuristic for approximating the solution to combinatorial optimization problems. Since simulated annealing is a general purpose method, it can be applied to the broad range of NP-complete problems such as the traveling salesman problem, graph theory, and cell placement with a careful control of the cooling schedule.

Attempts to parallelize simulated annealing, particularly on distributed memory multicomputers, are hampered by the algorithm’s requirement of a globally consistent system state. In a multicomputer, maintaining the global state S involves explicit message traffic and is a critical performance bottleneck. One way to mitigate this bottleneck …

A Process-Learning Pid Controller Algorithm Utilizing An On-Line Iterative Improvement Technique, Ryan Rosandich, Ralph W. Wilkerson

Computer Science Technical Reports

Three iterative improvement algorithms are presented for the determination of process controller gains. An offline algorithm is developed and tested as a basis for comparison, and a simple on-line algorithm is developed as an incremental step toward the final algorithm, proportional on-line iterative improvement. The algorithms are based on an Artificial Neural Network learning method, and this method is compared with other control optimization techniques. The performance of each of the algorithms was experimentally evaluated in numerous realistically simulated process control situations consisting of flow, level, and temperature control loops with various values of dead-time and process noise. The experimental …

Algorithms For Closest Point Problems: Practice And Theory, Peter Su

Computer Science Technical Reports

This paper describes and evaluates know sequential algorithms for constructing planar Voronoi diagrams and Delaunay triangulations. In addition, it describes a new incremental algorithm which is simple to understand and implement, but whose performance is competitive with all known methods. The experiments in this paper are more than just simple benchmarks, they evaluate the expected performance of the algorithms in a precise and machine independent fashion. Thus, the paper also illustrates how to use experimental tools to both understand the behaviour of different algorithms and to guide the algorithm design process.

The Management Of Replicated Data, Hsueh-Chi Shih, C. Y. Ho, S. Alptekin

Computer Science Technical Reports

Data replication, which has the benefits of improving system availability and read performance, proved to be indispensable to many database applications. In a replicated database, the one-copy serializability of transaction executions can be ensured by employing a replica control mechanism on top of the traditional concurrency control mechanism. This work contains two replica control algorithms and a read-only transaction processing algorithm. Both replica control algorithms handle multiple site, communication and partitioning failures. The replica control algorithms achieve read operation efficiency by always translating a logical read operation into one local physical read operation and by taking advantage of the locality …

Formal Derivation Of An Error-Detecting Distributed Data Scheduler Using Changeling, Hanan Lutffiya, Bruce M. Mcmillin, Alan Su

Computer Science Technical Reports

Distributed database applications are a wide use of distributed systems. One of the major advantages of distributed database systems is the potential for achieving high availability in the presence of faults. Faults must be handled so that the system still operates or operates in a degraded mode. This paper focuses on being able to detect component errors which can lead to system failures in the scheduling part of the lock manager portion of the distributed database system by using embedded executable assertions. Changeling provides a systematic approach, based on the mathematical model of program verification, to deriving executable assertions that …