Computer Sciences Commons^™

A Detailed Simulation Model Of The Hp 97560 Disk Drive, David Kotz, Song Bac Toh, Sriram Radhakrishnan

Computer Science Technical Reports

We implemented a detailed model of the HP 97560 disk drive, to replicate a model devised by Ruemmler and Wilkes (both of Hewlett-Packard, HP). Our model simulates one or more disk drives attached to one or more SCSI buses. The design is broken into three components: a test driver, the disk model itself, and the discrete-event simulation support. Thus, the disk model can be easily extracted and used in other simulation environments. We validated our model using traces obtained from HP, using the same "demerit" measure as Ruemmler and Wilkes. We obtained a demerit percentage of 3.9%, indicating that our …

A 2-3/4-Approximation Algorithm For The Shortest Superstring Problem, Chris Armen, Clifford Stein

Computer Science Technical Reports

Given a collection of strings S={s_1,...,s_n} over an alphabet Sigma, a superstring alpha of S is a string containing each s_i as a substring, that is, for each i, 1<=i<=n, alpha contains a block of |s_i| consecutive characters that match s_i exactly. The shortest superstring problem is the problem of finding a superstring alpha of minimum length. The shortest superstring problem has applications in both computational biology and data compression. The problem is NP-hard [GallantMS80]; in fact, it was recently shown to be MAX SNP-hard [BlumJLTY91]. Given the importance of the applications, several heuristics and approximation algorithms have been proposed. Constant factor approximation algorithms have been given in [BlumJLTY91] (factor of 3), [TengY93] (factor of 2-8/9), [CzumajGPR94] (factor of 2-5/6) and [KosarajuPS94] (factor of 2-50/63). Informally, the key to any algorithm for the shortest superstring problem is to identify sets of strings with large amounts of similarity, or overlap. While the previous algorithms and their analyses have grown increasingly sophisticated, they reveal remarkably little about the structure of strings with large amounts of overlap. In this sense, they are solving a more general problem than the one at hand. In this paper, we study the structure of strings with large amounts of overlap and use our understanding to give an algorithm that finds a superstring whose length is no more than 2-3/4 times that of the optimal superstring. We prove several interesting properties about short periodic strings, allowing us to answer questions of the following form: given a string with some periodic structure, characterize all the possible periodic strings that can have a large amount of overlap with the first string.

Efficiency And Stability Issues In The Numerical Computation Of Fourier Transforms And Convolutions On The 2-Sphere, D M. Healy Jr, S S. B. Moore, D Rockmore

Computer Science Technical Reports

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the sphere. In this paper we present a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. We also discuss implementational considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. This discussion is supplemented with numerical experiments from our implementation in C on a DecStation 5000. These results give strong indications that the algorithm is both reliable and efficient for a large …

Hardware Assists For High Performance Computing Using A Mathematics Of Arrays, H. Pottinger, W. Eatherton, L. Mullin, T. Schiefelbein

Computer Science Technical Reports

Work in progress at the University of Missouri - Rolla on hardware assists for high performance computing and communication is presented. This research consists of a field programmable gate array based rapid prototyping environment (Chameleon) being used to evaluate hardware architectures for speedup of array partitioning and routing algorithms. These algorithms have been developed using a Mathematics of Arrays (MOA) and are optimal in the sense that they reduce normal array indexing operations to a series of primitive additions based on array shape. The method is simple yet powerful, produces algorithms which are provably correct, and are independent of dimensionality. …

An Fpga Based Reconfigurable Coprocessor Board Utilizing A Mathematics Of Arrays, H. Pottinger, W. Eatherton, T. Schiefelbein, L. Mullin, R. Ziegler

Computer Science Technical Reports

Work in progress at the University of Missouri-Rolla on hardware assists for high performance computing is presented. This research consists of a novel field programmable gate array (FPGA) based reconfigurable coprocessor board (the Chameleon Coprocessor) being used to evaluate hardware architectures for speedup of array computation algorithms. These algorithms have been developed using a Mathematics of Arrays (MOA) and are optimal in the sense that they reduce normal array cartesian indexing operations to a series of primitive additions and offsets based on array shape. The method is simple yet powerful, produces algorithms which are provably correct, and are independent of …

Qualitative Study Of The Symplectic Stormer-Verlet Integrator, D. J. Hardy, D. I. Okunbor

Computer Science Technical Reports

Symplectic numerical integrators, such as the Stormer-Verlet method, are useful in preserving certain important properties that are not preserved by conventional numerical integrators. This paper analyzes the Stormer-Verlet method as applied to the simple harmonic model, which is an important model for molecular dynamics simulations. Restricting our attention to the one-dimensional case, both the exact solution and the Stormer-Verlet solution to this model are expressed as functions of the number of time steps taken, and then both of these functions are interpreted geometrically. The paper shows the existence of an upper bound on the error from the Stormer-Verlet method, and …

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 …

Fast Greedy Triangulation Algorithms, Matthew T. Dickerson, Robert L. Scot Drysdale, Scott A. Mcelfresh, Emo Welzl

Computer Science Technical Reports

The greedy triangulation of a set $S$ of $n$ points in the plane is the triangulation obtained by starting with the empty set and at each step adding the shortest compatible edge between two of the points, where a compatible edge is defined to be an edge that crosses none of the previously added edges. In this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time $O(n \log n)$ and space $O(n)$ for points uniformly distributed over any convex shape. A variant of this algorithm should be fast for some other distributions. As part …

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 …

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 …

Efficient Sequential And Parallel Algorithms For The Negative Cycle Problem, Dimitris Kavvadias, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

We present here an algorithm for detecting (and outputting, if exists) a negative cycle in an $n$-vertex planar digraph $G$ with real edge weights. Its running time ranges from $O(n)$ up to $O(n^{1.5}\log n)$ as a certain topological measure of $G$ varies from $1$ up to $\Theta(n)$. Moreover, an efficient CREW PRAM implementation is given. Our algorithm applies also to digraphs whose genus $\gamma$ is $o(n)$.

Conference On A Disk: A Successful Experiment In Hypermedia Publishing (Extended Abstract), M Cheyney, P Gloor, D B. Johnson, F Makedon, J Matthews, P Metaxas

Computer Science Technical Reports

Academic conferences are a long-standing and effective form of multimedia communication. Conference participants can transmit and recieve information through sight, speech, gesture, text, and touch. This same-time, same-place communication is sufficiently valuable to justify large investments in time and travel funds. Printed conference proceedings are attempts to recapture the value of a life conference, but they are limited by a fragmented and inefficient approach to the problem. We addressed this problem in the multimedia proceedings of the DAGS'92 conference. The recently published CD-ROM delibers text, graphic, audio, and video information as an integrated whole, with extensive provisions for random access …

Videoscheme: A Research, Authoring, And Teaching Tool For Multimedia, J Matthews, F Makedon, P Gloor

Computer Science Technical Reports

The availability of digital multimedia technology poses new challenges to researchers, authors, and educators, even as it creates new opportunities for rich communication. This paper suggests interactive computer programming as a fruitful approach to these challenges. VideoScheme, a prototype video programming environment, is described along with promising applications.

Quickest Paths: Faster Algorithms And Dynamization, Dimitrios Kagaris, Grammati E. Pantziou, Spyros Tragoudas, Christos D. Zaroliagis

Computer Science Technical Reports

Given a network $N=(V,E,{c},{l})$, where $G=(V,E)$, $|V|=n$ and $|E|=m$, is a directed graph, ${c}(e) > 0$ is the capacity and ${l}(e) \ge 0$ is the lead time (or delay) for each edge $e\in E$, the quickest path problem is to find a path for a given source--destination pair such that the total lead time plus the inverse of the minimum edge capacity of the path is minimal. The problem has applications to fast data transmissions in communication networks. The best previous algorithm for the single--pair quickest path problem runs in time $O(r m+r n \log n)$, where $r$ is the number …

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, …

Job Scheduling In Rings, Perry Fizzano, Clifford Stein, David Karger, Joel Wein

Computer Science Technical Reports

We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both computational load and communication time.

The algorithms are simple, require no global control, and work in a variety of settings. All come with small constant-factor approximation guarantees; the basic algorithm yields schedules of length at most …