Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences Commons™

Open Access. Powered by Scholars. Published by Universities.®

Syracuse University

Discipline
Keyword
Publication Year
Publication
Publication Type

Articles 361 - 390 of 532

Full-Text Articles in Computer Sciences

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

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 …

Go to article

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

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.

Go to article

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

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 …

Go to article

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

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 …

Go to article

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

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.

Go to article

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

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.

Go to article

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

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.

Go to article

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

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 …

Go to article

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

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 …

Go to article

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

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 …

Go to article

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

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 …

Go to article

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

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 …

Go to article

Binary Resolution In Surface Reasoning, William C. Purdy Jan 1993

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 …

Go to article

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

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 …

Go to article

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 Jan 1993

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.

Go to article

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen Sep 1992

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Go to article

Numerical Solution Of Laplace's Equation, Per Brinch Hansen Sep 1992

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Go to article

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen Sep 1992

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Go to article

All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang Sep 1992

All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

In this paper we present several algorithms for all-too-many personalized communications which avoid node contention.

Go to article

Parallel Monte Carlo Trials, Per Brinch Hansen Jun 1992

Parallel Monte Carlo Trials, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

The best results of Monte Carlo methods are generally obtained by performing the same computation many times with different random numbers. We develop a generic algorithm for parallel execution of Monte Carlo trials on a multicomputer. The generic algorithm has been adapted for simulated annealing and primality testing by simple substitutions of data types and procedures. The performance of the parallel algorithms was measured on a Computing Surface.

Go to article

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann Jun 1992

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Go to article

Primality Testing, Per Brinch Hansen Jun 1992

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Go to article

Simulated Annealing, Per Brinch Hansen Jun 1992

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

Go to article

General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair May 1992

General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …

Go to article

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary Apr 1992

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …

Go to article

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

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

Electrical Engineering and Computer Science - Technical Reports

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.

Go to article

A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris Mar 1992

A Non-Deterministric Parallel Sorting Algorithm, Xue Shirley Li, F. Lockwood Morris

Electrical Engineering and Computer Science - Technical Reports

A miniswap Si,1 ≤ i < n, compares two adjacent keys Пi, Пi+1 in the sequence (П1, ... , Пn), and transposes them if they are out of order. A full sweep is any composition of all n - 1 possible miniswaps. We prove that the composition of any n- 1 full sweeps is a sorting function.

Go to article

A Declarative Foundation Of Λprolog With Equality, Mino Bai Feb 1992

A Declarative Foundation Of Λprolog With Equality, Mino Bai

Electrical Engineering and Computer Science - Technical Reports

We build general model-theoretic semantics for higher-order logic programming languages. Usual semantics for first-order logic is two-level: i.e., at a lower level we define a domain of individuals, and then, we define satisfaction of formulas with respect to this domain. In a higher-order logic which includes the propositional type in its primitive set of types, the definition of satisfaction of formulas is mutually recursive with the process of evaluation of terms. As result of this in higher-order logic it is extremely difficult to define an effective semantics. For example to define T p operator for logic program P, we need …

Go to article

Conceptual Background For Symbolic Computation, Klaus Berkling Feb 1992

Conceptual Background For Symbolic Computation, Klaus Berkling

Electrical Engineering and Computer Science - Technical Reports

This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …

Go to article

Fault-Detection In Networks, H. F. Mattson Jr Feb 1992

Fault-Detection In Networks, H. F. Mattson Jr

Electrical Engineering and Computer Science - Technical Reports

To find broken links in networks we use the cut-set space. Information on which nodes can talk, or not, to which other nodes allows reduction of the problem to that of decoding the cut-set code of a graph. Special classes of such codes are known to have polynomial-time decoding algorithms. We present a simple algorithm to achieve the reduction and apply it in two examples.

Go to article

First Prev Next Last