Digital Commons Network^™

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

Computer Science Technical Reports

No abstract provided.

A Probabilistic Analysis Of A Locality Maintaining Load Balancing Algorithm, Kishan Mehrotra, Sanjay Ranka, Jhy-Chun Wang

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

This paper presents a simple load balancing algorithm and its probabilistic analysis. Unlike most of the previous load balancing algorithms, this algorithm maintains locality. We show that the cost of this load balancing algorithm is small for practical situations and discuss some interesting applications for data remapping.

Static And Runtime Scheduling Of Unstructured Communication, Sanjay Ranka, Jyu-Chun Wang

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

With the advent of new routing methods, the distance to which a message is sent is becoming relatively less and less important. Thus assuming no link contention, permutation seems to be an efficient collective communication primitive. All-to-many communication is required for solving a large class of irregular and loosely synchronous problems on distributed memory MIMD machines. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. These partial permutations avoid node contention and/or link contention. We discuss several algorithms and study their effectiveness both from the view of static scheduling as …

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.

Architectural Support For High-Performance Distributed Computing, Jongbaek Park, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

The emergence of high speed networks and the proliferation of high performance workstations have attracted a lot of interest in workstation-based distributed computing. Current trend in local area networks is toward higher communication bandwidth as we progress from Ethernet networks that operate at 10 Mbit/sec to higher speed networks that can operate in Gbit/sec range. Also, current workstations are capable of delivering tens and hundreds of Megaflops of computing power. By using a cluster of such high-performance workstations and the high-speed networks, a high-performance distributed computing environment could be built in cost-effective manner as an alternative of supercomputing platform. However, …

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 …

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.

A Model For Syntactic Control Of Interference, Peter W. O'Hearn

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

Two imperative programming language phrases interfere when one writes to a storage variable that the other reads from or writes to. Reynolds has described an elegant linguistic approach to controlling interference in which a refinement of typed λ-calculus is used to limit sharing of storage variables; in particular, different identifiers are required never to interfere. This paper examines semantic foundations of the approach. We describe a category that has (an abstraction of) interference information built into all objects and maps. This information is used to define a “tensor” product whose components are required never to interfere. Environments are defined using …

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.

Ccis Networking - January 1993, Nova University

CCIS Networking / SCIS Networking magazines

No abstract provided.

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

Software And Hardware Support For Workstation-Based, Salim Hariri, Manish Parashar, Jongbaek Park

Electrical Engineering and Computer Science - All Scholarship

The proliferation of high performance workstations and the emergence of high speed networks have attracted a lot of interest in workstation-based supercomputing. We project that workstation-based environments with supercomputing capabilities will be available in the not-so-distant future. However a number of hardware and software issues have to be resolved before the full potential of these workstation-based supercomputing environments can be exploited. The presented research has two main objectives: (1) to investigate the limitations of communications techniques used in current workstation-based systems and to identify a set of requirements that must be satisfied to achieve workstation-based supercomputing; (2) to use these …

A-Hohfeld: A Language For Robust Structural Representation Of Knowledge In The Legal Domain To Build Interpretation-Assistance Expert Systems, Layman E. Allen, Charles S. Saxon

Book Chapters

The A-Hohfeld language is presented as a set of definitions; it can be used to precisely express legal norms. The usefulness of the AHohfeld language is illustrated in articulating 2560 alternative structural interpretations of the four-sentence 1982 Library Regulations of Imperial College and constructing an interpretation-assistance legal expert system for these regulations by means of the general-purpose Interpretation-Assistance legal expert system builder called MINT. The logical basis for A-Hohfeld is included as an appendix.

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 …

An Object Oriented Preemptive Multitasking Kernel, Lee Gene Shipman

Masters Theses

“This paper describes a preemptive multitasking kernel designed and coded using C++ using an object oriented paradigm. The kernel design, while implemented on an Intel 80386 based IBM PC running MS-DOS 4.01, can be ported to any platform, rewriting only the low level, hardware specific code.

The kernel, in application framework form, enables the applications developer to create real-time multitasking applications. This can be done in a systematic way by capitalizing on the power of object oriented program development.

A simulation was created to verify the correctness of the kernel against a traditional non-multitasking approach. This simulation provides the proof …

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.

Evidence For Penguin-Diagram Decays: First Observation Of B→K*(892)Γ, R. Ammar, M. Thulasidas

Research Collection School Of Computing and Information Systems

We have observed the decays B0→K*(892)0γ and B−→K*(892)−γ, which are evidence for the quark-level process b→sγ. The average branching fraction is (4.5±1.5±0.9)×10−5. This value is consistent with standard model predictions from electromagnetic penguin diagrams.

Search For Τ-→Γμ-: A Test Of Lepton Number Conservation, A. Bean, M. Thulasidas

Research Collection School Of Computing and Information Systems

A search for the lepton mumber violating decay of the τ lepton to the γμ final state has been performed with the CLEO II detector at the Cornell e+e− storage ring CESR. In a data sample that corresponds to an integrated luminosity of 1.55 fb−1, we observe no candidates in the signal region. We thus determine an upper limit of B(τ−→γμ−)