Digital Commons Network^™

Reasoning About Synchrony Illustrated On Three Models Of Concurrency, Gruia-Catalin Roman, Jerome Plun

All Computer Science and Engineering Research

This paper presents a model of concurrency (Dynamic Synchrony) whose distinctive feature is a novel formal treatment of synchronization. Synchrony is defined as the coordinated execution of two or more actions. The dynamic aspect comes from the fact that the definition of which actions must be executed synchronously can change freely during the execution of the program. This unique modeling capability comes with a UNITY-stype assertional logic that can be applied to program verification and derivation. This paper shows that the proposed proof logic can be used to verify programs expressed using other models of foncurrency without having to translate …

Representing And Learning Propositional Logic In Symmetric Connectionist Networks, Gadi Pinkas

All Computer Science and Engineering Research

The chapter presents methods for efficiently representing logic formulas in connectionist networks that perform energy minimization. Algorithms are given for transforming any formula into a network in linear time and space and for learning representations of unknown formulas by observing examples of satisfying truth assignments. The relaxation process that underlies networks of energy minimization reveals an efficient hill climbing algorithm for satisfiability problems. Experimental results indicate that the parallel implementation of the algorithm with give extremely good average-case performance, even for large-scale, hard satisfiability problems (randomly generated).

The Washington University Multimedia Explorer, William D. Richard, Jerome R. Cox Jr., A. Maynard Engebretson, Jason Fritts, Craig Horn

All Computer Science and Engineering Research

The Washington University MultiMedia eXplorer (MMX) is a complete, host-independent multimedia system capable of transmitting and receiving JPEG-compressed video, CD-quality audio, and high-resolution radiographic images over the Washington University broadband ATM network. If the host is equipped with an ATM interface card, normal network traffic is supported via "T" and "Y" connections. The MMX consists of an ATMizer and three multimedia subsystems. The ATMizer implements the host interface, the interface to the ATM network, and the interface to the three multimdeia channels. This paper describes the architecture of the MMX, the software used with the system, and the applications which …

Learning Unions Of Boxes With Membership And Equivalence Queries, Paul W. Goldberg, Sally A. Goldman, H. David Matthias

All Computer Science and Engineering Research

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. The first algorithm receives at most s*d counterexamples and uses time and membership queries polynomial in s and logn for d any constant. Further, all equivalence queries made can be formulated as the union of O(s*d*log(s)) axis-parallel boxes. Next, we introduce a new complexity measure that better captures the complexity of a union of boxes than simply the number of boxes and dimensions. …

Rule-Maker's And Rule-Follower's Meaning, R. P. Loui

All Computer Science and Engineering Research

No abstract provided.

Fril - A Fractal Intermediate Language, Ron Cytron, David Shields

All Computer Science and Engineering Research

This document describes the motivation, language description, and experience using FrIL, an intermediate language for a compiler's "middle-end." FrIL has subbessfully supported a two-semester compiler construction sequence, where the first semester included code generation from a C-like language and the second semester included advanced data flow analysis and program transformation.

The Pessimism Behind Optimistic Simulation, George Varghese, Roger D. Chamberlain, William E. Weihl

All Computer Science and Engineering Research

In this paper we make an analogy between the time that storage must be maintained in an optimistic simulation and the blocking time in a conservative simulation. By exploring this analogy, we design two new Global Virtual Time (GVT) protocols for Time Warp systems. The first simple protocol is based on the null message scheme proposed for clock advancement in some conservative approaches; this yields what we call Local Guaranteed Time. Our main contribution is a second new protocol that is inspired by Misra's circulating marker scheme for deadlock recovery in conservative simulations, and appears to have advantages over previous …

Dna Mapping Algorithms: Synchronized Double Digest Mapping, Jim Daues, Will Gillett

All Computer Science and Engineering Research

A technique called Synchronized Double Digest Mapping (SDDM) is presented; it combines classical Double Digest Mapping (DDM) and Multiple-Restriction-Enzyme Mapping (MREM). Classical DDM is a technique for determining the order of restriction fragments in a clone given three digestions of the clone: a digestion by enzyme1, a digestion by enzyme2, and a digestion by enzyme1 and enzyme2 combined. All algorithms for applying this technique are exponential (in the number of fragments present in the clone) in nature. MREM is an extension of classical high-resolution restriction-fragment mapping of a YAC or a genome, in which the overlaps among a set of …

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 …

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 …

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

Computer Science Technical Reports

No abstract provided.

Nova University Graduate Education Module (Gem) Master's And Educational Specialist Degrees Computer Science Education 1993, Nova University

Abraham S. Fischler College of Education and School of Criminal Justice College Archive

No abstract provided.

Development Of A Hypermedia Database For The Elementary Classroom, Jane Pattison Brown

All Graduate Projects

A hypermedia database including selected flora and fauna in Kittitas County, Washington, was developed using HyperCard software for researching information about 400+ species. students had the opportunity to use the database in school libraries and in the author's fifth-grade classroom. The database cards accessed videodisc images where available. On the basis of limited study to date, it appears that when studying the environment, student learning was enhanced by the use of database material created by the author.

The Introduction Of A Catalog Automation And Manufacturing Costing System For Use In A Jewelry Manufacturing Company, Moshe S. Raab

CCAC Theses and Dissertations

The jewelry manufacturing industry is an example of an industry that is slow to accept and incorporate new technology. There are, however, some large companies that have automated the accounting and inventory functions. Some of these companies have even invested in systems that can do image storage and retrieval. Until recently, these computer systems have been very expensive to purchase.

Prestige Marketing, Ltd. is a small jewelry manufacturing company. The owner of Prestige recognized the advantage of utilizing inexpensive personal computers to develop a software system that would calculate the cost of manufacturing and determine the recommended selling price of …

Computer Program: General University Requirements Package, Abhishek Kejriwal '93

Honors Projects

The objective of my research project was to write a computer program in Turbo Pascal which would determine how many general university requirements a student has completed and what requirements he or she needs to complete in order to graduate. There are six degrees offered at Illinois Wesleyan University. They are: BA (Bachelor of Arts); BS (Bachelor of Science); BFA (Bachelor of Fine Arts); BSN (Bachelor of Science in Nursing); BM (Bachelor of Music) and BME (Bachelor of Music Education). There is a different set of criteria to be met for the completion of each of these degrees. The program …

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 …

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.

The Multicomputer Toolbox - First-Generation Scalable Libraries, Anthony Skjellum, Alvin Leung, Steven G. Smith, Robert D. Falgout

Northeast Parallel Architecture Center

"First-generation" scalable parallel libraries have been achieved, and are maturing, within the Multicomputer Toolbox. The Toolbox includes sparse, dense, iterative linear algebra, a stiff ODE/DAE solver, and an open software technology for additional numerical algorithms, plus an inter-architecture Makefile mechanism for building applications. We have devised C-based strategies for useful classes of distributed data structures, including distributed matrices and vectors. The underlying Zipcodemessage passing system has enabled process-grid abstractions of multicomputers, communication contexts, and process groups, all characteristics needed for building scalable libraries, and scalable application software. We describe the data-distribution-independent approach to building scalable libraries, which is needed so …

A Message Passing Interface For Parallel And Distributed Computing, Salim Hariri, Jongbaek Park, Fang-Kuo Yu, Manish Parashar

Northeast Parallel Architecture Center

The proliferation of high performance workstations and the emergence of high speed networks have attracted a lot of interest in parallel and distributed computing (PDC). We envision that PDC environments with supercomputing capabilities will be available in the near future. However, a number of hardware and software issues have to be resolved before the full potential of these PDC environments can be exploited. The presented research has the following objectives: (1) to characterize the message-passing primitives used in parallel and distributed computing; (2) to develop a communication protocol that supports PDC; and (3) to develop an architectural support for PDC …

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 …

An Interpretive Framework For Application Performance Prediction, Manish Parashar, Salim Hariri, Tomasz Haupt, Geoffrey C. Fox

Northeast Parallel Architecture Center

Software development in parallel/distributed environment is a non-trivial task and depends greatly on the availability of appropriate support in terms of development tools and environments. Performance prediction /evaluation tools form a critical part of any software development environment as they enable the developer to visualize the effects of various design choices on the performance of the application. This paper presents an interpretive model for a source driven performance prediction framework. A prototype framework based on the proposed model has been developed for the iPSC/860 system. Numerical results obtained on this system are presented. These results confirm the potential of interpretive …

Complete Exchange On A Wormhole Routed Mesh, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

The complete exchange (or all-to-all personalized) communication pattern occurs frequently in many important parallel computing applications. We discuss several algorithms to perform complete exchange on a two dimensional mesh connected computer with wormhole routing. We propose algorithms for both powerof -two and non power-of-two meshes as well as an algorithm which works for any arbitrary mesh. We have developed analytical models to estimate the performance of the algorithms on the basis of system parameters. These models take into account the effects of link contention and other characteristics of the communication system. Performance results on the Intel Touchstone Delta are presented …

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.

Pseudobases In Direct Powers Of An Algebra, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

A subset P of an abstract algebra A is a pseudobasis if every function from P into A extends uniquely to an endomorphism on A. A is called K-free has a pseudobasis of cardinality K; A is minimally free if A has a pseudobasis. (The 0-free algebras are "rigid" in the strong sense; the 1-free groups are always abelian, and are precisely the additive groups of E-rings.) Our interest here is in the existence of pseudobases in direct powers A^I of an algebra A. On the positive side, if A is a rigid …