Digital Commons Network^™

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.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 3, March 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A twelve page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Dynamic Id3: A Symbolic Learning Algorithm For Many-Valued Attribute Domains, Roger Gallion, Chaman Sabharwal, Daniel C. St. Clair, William E. Bond

Computer Science Faculty Research & Creative Works

Quinlan's ID3 machine learning algorithm induces classification trees (rules) from a set of training examples. The algorithm is extremely effective when training examples are composed of attributes whose values are taken from small discrete domains. The classification accuracy of ID3-produced trees on domains whose attributes are many-valued tends to be marginal due to the large number of possible values which may be associated with each attribute. Attempts to solve this problem by a priori grouping of attribute values into distinct subsets has met with limited success. The dynamic ID3 algorithm improves the performance of ID3 on this type of problem …

Simulated Annealing And Optimal Codes, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Following standard notation, an (n, m, d) code C denotes a binary code C which has length n, size m, and Hamming distance d. According to Hill [6] the “main coding theory problem” is to optimize one of these three parameters when the other two are held fixed. The usual version of this optimization problem is to find the largest code for a given length and given minimum distance. This is the problem we shall consider, thus making it clear what we mean by an “optimal code.”

Back-Face Culling Applied To Collision Detection Of Polyhedra, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

Recovering 3d Image Parameters From Corresponding Two 2d Images, Chaman Sabharwal

Computer Science Faculty Research & Creative Works

An improved algorithm for computing the three-dimensional structure of a scene from pair of stereo images is given. The spatial relationship between the two images is not known, only the "corresponding" points in the two images are known. This problem of 3D scene reconstruction involves: (1) establishing a one-to-one correspondence between the image plane stereo pairs corresponding to the spatial points-'the correspondence problem', and (2) determining the relative orientation of the two image planes and the depth relation of spatial points with respect to the image planes. This paper assumes the first problem solved [Usikov et al. 1991] and addresses …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 2, February 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A fourteen page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Decentralized Global Transaction Management In Multidatabase Systems, Aidong Zhang, Jiansan Chen, Ahmed K. Elmagarmid, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

Systems Integration In Pharmaceutical Industry Using Object-Oriented Expert System Technology, Korrapolu Reddy

Theses

SPHINX is an object-oriented expert system addressed to solve the burning problems of pharmaceutical industry. SPHINX stands for Systems integration in PHarmaceutical INdustry using object-oriented eXpert system technology.

Various problems that American pharmaceutical industries are facing have been explained. Using the revolutionary object-oriented concepts and the powerful expert systems technology, it has been shown how a prescription can be written to solve all the problems of pharmaceutical industries. A problem "Minimizing the wastage of Interferon" has been taken to demonstrate the power of Object-oriented Expert System technology.

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 …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 1, January 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi Shankar

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach. The algorithm was implemented on the CM-2 and the CM-5 in the data parallel and message passing models. The performance of these implementations is examined and compared.

Runtime Compilation Techniques For Data Partitioning And Communication Schedule Reuse, Ravi Ponnusamy, Joel Saltz, Alok Choudhary

Northeast Parallel Architecture Center

In this paper, we describe two new ideas by which HPF compiler can deal with irregular computations effectively. The first mechanism invokes a user specified mapping procedure via a set of compiler directives. The directives allow the user to use program arrays to describe graph connectivity, spatial location of army elements and computational load. The second is a simple conservative method that in many cases enables a compiler to recognize that it is possible to reuse previously computed results from inspectors (e.g. communication schedules, loop iteration partitions, information that associates off-processor data copies with on-processor buffer locations). We present performance …

A Fast Serial Algorithm For The Finite Temperature Quenched Potts Model, Gregory N. Hassold, Elizabeth A. Holm

Physics Publications

An efficient serial algorithm for finite temperature, quenched Potts model simulations of domain evolution has been developed. This ''n‐fold way'' algorithm eliminates unsuccessful spin flip attempts a priori by flipping sites with a frequency proportional to their site activity, defined as the sum of the probability of success for every possible spin flip at that site. Finite temperature efficiency for high‐spin degeneracy systems is achieved by utilizing a new, analytical expression for the portion of the site activity due to flips to non-neighbor spin values. Hence, to determine the activity of a site, only flips to the …

Fast Mapping And Remapping Algorithms For Irregular And Adaptive Problems, Chao Wei Ou, Sanjay Ranka, Geoffrey C. Fox

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper describes the performance of locality-based mapping and remapping partitioners for unstructured grids. We show that the algorithm produces good mappings at a relatively low cost and can be easily parallelized. Further, the algorithm can provide remapping for incremental problems at a fraction of the total cost.

Distributed Scheduling Of Unstructured Collective Communication On The Cm-5 (1993), Jyu-Chun Wang, Tseng-Hui Lin, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Parallelization of many irregular applications results in unstructured collective communication. In this paper we present a distributed algorithm for scheduling such communication on parallel machines. We describe the performance of this algorithm on the CM-5 and show that the scheduling algorithm has very small overhead and gives a significant improvement over naive methods.

Georg Cantor And The Battle For Transfinite Set Theory, Joseph Dauben

ACMS Journal 2004

Georg Cantor is well known as the founder of transfinite set theory. Equally celebrated, however, are the obstacles he faced in trying to win acceptance for his seemingly unorthodox views, his acrimonious differences with Leopold Kronecker and his unfortunate but progressively debilitating nervous breakdowns that some authors have linked directly to his many problems with set theory. Above all, Cantor's justification of set theory was all the more urgent because of Kronecker's critical denunciation of Cantor's mathematics. In tracing the evolution of Cantorian set theory, it is necessary to examine the opposition it met, and evaluate the technical, philosophical, psychological, …

On Matching Ann Structure To Problem Domain Structure, George G. Lendaris, Martin Zwick, Karl Mathia

Complex Systems Faculty Publications and Presentations

To achieve reduced training time and improved generalization with artificial neural networks (ANN, or NN), it is important to use a reduced complexity NN structure. A "problem" is defined by constraints among the variables describing it. If knowledge about these constraints could be obtained a priori, this could be used to reduce the complexity of the ANN before training it. Systems theory literature contains methods for determining and representing structural aspects of constrained data (these methods are herein called GSM, general systems method). The suggestion here is to use the GSM model of the given data as a pattern for …

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

Computer Science Technical Reports

No abstract provided.

Observation Of B0 Decay To Two Charmless Mesons, M. Battle, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

We report results from a search for the decays B0→π+π-, B0→K+π-, and B0→K+K-. We find 90% confidence level upper limits on the branching fractions, Bππ

A Methodology For Developing High Performance Computing Models: Storm-Scale Weather Prediction, Nikos Chrisochoides, Kelvin Droegemeier, Geoffrey C. Fox, Kim Mills, Ming Xue

Northeast Parallel Architecture Center

A methodology for developing future generations of a storm-scale weather prediction model for Massively Parallel Processing is described. The forecast model is the Advanced Regional Prediction System (ARPS), a three-dimensional, fully compressible, non-hydrostatic predictive model. In the short term, the computational goals include developing a portable, scalable model for distributed memory SIMD and MIMD architectures, while preserving a high degree of modularity to support rapid design and validation, maintainability, educational goals and operational testing. Longer term computational goals include a parallel adaptive mesh refinement scheme. A FortranD/High Performance Fortran version of the ARPS provides portability in the current version of …

Fortran 90d/Hpf Compiler For Distributed Memory Mimd Computers: Design, Implementation, And Performance Results, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

Fortran 90D/HPF is a data parallel language with special directives to enable users to specify data alignment and distributions. This paper describes the design and implementation of a Fortran90D/HPF compiler. Techniques for data and computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. Finally, initial performance results for the compiler are presented which show that the code produced by the compiler is portable, yet efficient. We believe that the methodology to process data distribution, computation partitioning, communication system design and the overall compiler design can be used by the implementors of HPF compilers.

A Compilation Approach For Fortran 90d/Hpf Compilers On Distributed Memory Mimd Computers, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt

Northeast Parallel Architecture Center

This paper describes a compilation approach for a Fortran 90D/HPF compiler, a source-to-source parallel compiler for distributed memory systems. Different from Fortran 77 parallelizing compilers, a Fortran90D/HPF compiler does not parallelize sequential constructs. Only parallelism expressed by Fortran 90D/HPF parallel constructs is exploited. The methodology of parallelizing Fortran programs such as computation partitioning, communication detection and generation, and the run-time support for the compiler are discussed. An example of Gaussian Elimination is used to illustrate the compilation techniques with performance results.

Integrating Multiple Programming Paradigms On Connection Machine Cm5 In A Dataflow-Based Software Environment, Gang Cheng, Geoffrey C. Fox, Kim Mills

Northeast Parallel Architecture Center

By viewing different parallel programming paradigms as essential heterogeneous approaches in mapping "real-world" problems to parallel systems, we discuss methodologies in integrating multiple programming models on a Connection Machine CM5. In a data flow based integration model built in a visualization software AVS, we demonstrate a simple, effective and modular way to couple sequential, data-parallel and explicit message-passing modules into an integrated programming environment on the CM5.

Hierarchical Tree-Structures As Adaptive Meshes, David J. Edelsohn

Northeast Parallel Architecture Center

Introduction: Two basic types of simulations exist for modeling systems of many particles: grid-based (point particles indirectly interacting with one another through the potential calculated from equivalent particle densities on a mesh) and particle-based (point particles directly interacting with a one another through potentials at their positions calculated from the other particles in the system). Grid-based solvers traditionally model continuum problems, such as fluid and gas systems, and mixed particle-continuum systems. Particle-based solvers find more use modeling discrete systems such as stars within galaxies or other rarefied gases. Many different physical systems, including electromagnetic interactions, gravitational interactions, and fluid vortex …

Binary Resolution In Surface Reasoning, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Intuition suggests the hypothesis that everyday human reasoning is conducted in the written or spoken natural language, rather than in some disparate representation into which the surface language is translated. An examination of human reasoning reveals patterns of inference that parallel binary resolution. But any standard implementation of resolution requires Skolemization. Skolemization would seem an unlikely component of human reasoning. This appears to contradict the hypothesis that human reasoning takes place at the surface. To reconcile these observations, this paper develops a new rule of inference, which operates on surface expressions directly. This rule is shown to produce results which …

Genetic Algorithms For Stochastic Flow Shop No Wait Scheduling, Harpal Maini, Ubirajara R. Ferreira

Electrical Engineering and Computer Science - Technical Reports

ln this paper we present Genetic Algorithms - evolutionary algorithms based on an analogy with natural selection and survival of the fittest - applied to an NP Complete combinatorial optimization problem: minimizing the makespan of a Stochastic Flow Shop No Wait (FSNW) schedule. This is an important optimization criteria in real-world situations and the problem itself is of practical significance. We restrict our applications to the three machine flow shop no wait problem which is known to be NP complete. The stochastic hypothesis is that the processing times of jobs are described by normally distributed random variables. We discuss how …

Multimedia Object Modelling And Storage Allocation Strategies For Heterogeneous Parallel Access Storage Devices In Real Time Multimedia Computing Systems, C.Y. Roger Chen, Kingsley C. Nwosu, P. B. Berra

Electrical Engineering and Computer Science - All Scholarship

The improvements in disk speeds have not kept up with improvements in processor and memory speeds. Conventional storage techniques, in the face of multimedia data, are inefficient and/or inadequate. Here, an efficient multimedia object allocation strategy is presented. We describe a multimedia object model, the object and storage device characteristics, and the fragmentation strategy. A bipartite graph approach is used for mapping fragments to storage devices and a cost function is used to determine an efficient allocation of an object and to balance the loads on the devices.

On Transactional Workflows, Amit P. Sheth, Marek Rusinkiewicz

Kno.e.sis Publications

The basic transaction model has evolved over time to incorporate more complex transactions structures and to take the advantage of semantics of higher-level operations that cannot be seen at the level of page reads and writes. Well known examples of such extended transaction models include nested and multi-level transactions. A number of relaxed transaction models have been defined in the last several years that permit a controlled relaxation of the transaction isolation and atomicity to better match the requirements of various database applications. Correctness criteria other than global serializability have also been proposed. Several examples of extended/relaxed transaction models are …