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

Physical Sciences and Mathematics Commons™

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

Syracuse University

1995

Articles 31 - 55 of 55

Full-Text Articles in Physical Sciences and Mathematics

Note On Algol And Conservatively Extending Functional Programming, Peter W. O'Hearn Jan 1995

Note On Algol And Conservatively Extending Functional Programming, Peter W. O'Hearn

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

A simple Idealized Algol is considered, based on Reynolds's "essence of Algol." It is shown that observational equivalence in this language conservatively extends observational equivalence in its assignment-free functional sublanguage.

Go to article

Irregular Personalized Communication On Distributed Memory Machines, Sanjay Ranka, Jhy-Chun Wang Jan 1995

Irregular Personalized Communication On Distributed Memory Machines, Sanjay Ranka, Jhy-Chun Wang

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

In this paper we present several algorithms for performing all-to-many personalized communication on distributed memory parallel machines. We assume that each processor sends a different message (of potentially different size) to a subset of all the processors involved in the collective communication. The algorithms are based on decomposing the communication matrix into a set of partial permutations. We study the effectiveness of our algorithms both from the view of static scheduling and from runtime scheduling.

Go to article

Run-Time Support For Parallelization Of Data-Parallel Applications On Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka Jan 1995

Run-Time Support For Parallelization Of Data-Parallel Applications On Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Sanjay Ranka

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

In this paper we discuss the runtime support required for the parallelization of unstructured data parallel applications on nonuniform and adaptive environments. The approach presented is reasonably general and is applicable to a wide variety of regular as well as irregular applications. We present performance results for the solution of an unstructured mesh on a cluster of heterogeneous workstations.

Go to article

The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf Jan 1995

The Expressiveness Of Locally Stratified Programs, Howard A. Blair, Wiktor Marek, John S. Schlipf

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

This paper completes an investigation of the logical expressibility of finite, locally stratified, general logic programs. We show that every hyperarithmetic set can be defined by a suitably chosen locally stratified logic program (as a set of values of a predicate over its perfect model). This is an optimal result, since the perfect model of a locally stratified program is itself an implicitly definable hyperarithmetic set (under a recursive coding of the Herbrand base); hence to obtain all hyperarithmetic sets requires something new, in this case selecting one predicate from the model. We find that the expressive power of programs …

Go to article

Communication-Efficient And Memory-Bounded External Redistribution, Jang Sun Lee, Sanjay Ranka, Ravi V. Shankar Jan 1995

Communication-Efficient And Memory-Bounded External Redistribution, Jang Sun Lee, Sanjay Ranka, Ravi V. Shankar

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

This paper presents communication-efficient algorithms for the external data redistribution problem. Deterministic lower bounds and upper bounds are presented for the number of I/O operations, communication time and the memory requirements of external redistribution. Our algorithms differ from most other algorithms presented for out-of-core applications in that it is optimal (within a small constant factor) not only in the number of I/O operations, but also in the time taken for communication. A coarse-grained MIMD architecture with I/O subsystems attached to each processor is assumed, but the results are expected to be applicable over a wider variety of architectures.

Go to article

Mapping Unstructured Computational Graphs For Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Chao Wei Ou, Sanjay Ranka Jan 1995

Mapping Unstructured Computational Graphs For Adaptive And Nonuniform Computational Environments, Maher Kaddoura, Chao Wei Ou, Sanjay Ranka

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

In this paper we study the problem of mapping a large class of irregular and loosely synchronous data-parallel applications in a nonuniform and adaptive computational environment. The computational structure of these applications can be described in terms of a computational graph, where nodes of the graph represent computational tasks and edges describe the communication between tasks. Parallelization of these applications on nonuniform computational environments requires partitioning the graph among the processors in such fashion that the computation load on each node is proportional to its computational power, while communication is minimized. We discuss the applicability of current methods for graph …

Go to article

Optimization Using Replicators, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka Jan 1995

Optimization Using Replicators, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

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

Replicator systems are among the simplest complex systems and can be considered to be at the foundation of many popularly used models ranging from theories of evolution and neurobiology to sociobiology and ecology. This paper presents the first successful application 2 of replicators to optimization problems. For a graph bi-partitioning problem with 50,000 nodes and 300,000 edges, for instance, close to optimal solutions were obtained in a few hundred iterations. Replicators provide a potentially powerful new tool to solve other optimization problems as well.

Go to article

Runtime And Language Support For Compiling Adaptive Irregular Programs On Distributed Memory Machines, Yuan-Shin Hwang, Bongki Moon, Shamik D. Sharma, Ravi Ponnusamy Jan 1995

Runtime And Language Support For Compiling Adaptive Irregular Programs On Distributed Memory Machines, Yuan-Shin Hwang, Bongki Moon, Shamik D. Sharma, Ravi Ponnusamy

Northeast Parallel Architecture Center

In many scientific applications, arrays containing data are indirectly indexed through indirection arrays. Such scientific applications are called irregular programs and are a distinct class of applications that require special techniques for parallelization. This paper presents a library called CHAOS, which helps users implement irregular programs on distributed-memory message-passing machines, such as the Paragon, Delta, CM-5 and SP-1. The CHAOS library provides efficient runtime primitives for distributing data and computation over processors; it supports efficient index translation mechanisms and provides users high-level mechanisms for optimizing communication. CHAOS subsumes the previous PARTI library and supports a larger class of applications. In …

Go to article

Communication Strategies For Out-Of-Core Programs On Distributed Memory Machines, Rajesh Bordawekar, Alok Choudhary Jan 1995

Communication Strategies For Out-Of-Core Programs On Distributed Memory Machines, Rajesh Bordawekar, Alok Choudhary

Northeast Parallel Architecture Center

In this paper, we show that communication in the out-of-core distributed memory problems requires both inter-processor communication and file I/O. Given that primary data structures reside in files, even communication requires I/O. Thus, it is important to optimize the I/O costs associated with a communication step. We present three methods for performing communication in out-of-core distributed memory problems. The first method, termed as the “out-of-core“communication method, follows a loosely synchronous model. Computation and Communication phases in this case are clearly separated, and communication requires permutation of data in files. The second method, termed as”demand-driven-in-core communication” considers only communication required of …

Go to article

Supporting Irregular Distributions Using Data-Parallel Languages, Ravi Ponnusamy, Yuan-Shin Hwang, Raja Das, Alok Choudhary, Geoffrey Fox Jan 1995

Supporting Irregular Distributions Using Data-Parallel Languages, Ravi Ponnusamy, Yuan-Shin Hwang, Raja Das, Alok Choudhary, Geoffrey Fox

Northeast Parallel Architecture Center

Languages such as Fortran D provide irregular distribution schemes that can efficiently support irregular problems. Irregular distributions can also be emulated in HPF. Compilers can incorporate runtime procedures to automatically support these distributions.

Go to article

Parallel Remapping Algorithms For Adaptive Problems, Chao Wei Ou, Sanjay Ranka Jan 1995

Parallel Remapping Algorithms For Adaptive Problems, Chao Wei Ou, Sanjay Ranka

Northeast Parallel Architecture Center

In this paper we present fast parallel algorithms for remapping a class of irregular and adaptive problems on coarse-grained distributed memory machines. We show that the remapping of these applications, using simple index-based mapping algorithm, can be reduced to sorting a nearly sorted list of integers or merging an unsorted list of integers with a sorted list of integers. By using the algorithms we have developed, the remapping of these problems can be achieved at a fraction of the cost of mapping from scratch. Experimental results are presented on the CM-5.

Go to article

Software Tool Evaluation Methodology, Salim Hariri, Sung Yong Park, Rajashekar Reddy, Mahesh Subramanyan Jan 1995

Software Tool Evaluation Methodology, Salim Hariri, Sung Yong Park, Rajashekar Reddy, Mahesh Subramanyan

Northeast Parallel Architecture Center

The recent development of parallel and distributed computing software has introduced a variety of software tools that support several programming paradigms and languages. This variety of tools makes the selection of the best tool to run a given class of applications on a parallel or distributed system a non-trivial task that requires some investigation. We expect tool evaluation to receive more attention as the deployment and usage of distributed systems increases. In this paper, we present a multi-level evaluation methodology for parallel/distributed tools in which tools are evaluated from different perspectives. We apply our evaluation methodology to three message passing …

Go to article

Cluster Computing Review, Mark Baker, Geoffrey C. Fox, Hon W. Yau Jan 1995

Cluster Computing Review, Mark Baker, Geoffrey C. Fox, Hon W. Yau

Northeast Parallel Architecture Center

In the past decade there has been a dramatic shift from mainframe or ‘host−centric’ computing to a distributed ‘client−server’ approach. In the next few years this trend is likely to continue with further shifts towards ‘network−centric’ computing becoming apparent. All these trends were set in motion by the invention of the mass−reproducible microprocessor by Ted Hoff of Intel some twenty−odd years ago. The present generation of RISC microprocessors are now more than a match for mainframes in terms of cost and performance. The long−foreseen day when collections of RISC microprocessors assembled together as a parallel computer could out perform the …

Go to article

High Performance Fortran And Possible Extensions To Support Conjugate Gradient Algorithms, K. Dincer, Ken Hawick, Alok Choudhary, Geoffrey C. Fox Jan 1995

High Performance Fortran And Possible Extensions To Support Conjugate Gradient Algorithms, K. Dincer, Ken Hawick, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

We evaluate the High-Performance Fortran (HPF) language for the compact expression and efficient implementation of conjugate gradient iterative matrix-solvers on High Performance Computing and Communications(HPCC) platforms. We discuss the use of intrinsic functions, data distribution directives and explicitly parallel constructs to optimize performance by minimizing communications requirements in a portable manner. We focus on implementations using the existing HPF definitions but also discuss issues arising that may influence a revised definition for HPF-2. Some of the codes discussed are available on the World Wide Web at http://www.npac.syr.edu/hpfa/ alongwith other educational and discussion material related to applications in HPF.

Go to article

The Use Of The National Information Infrastructure And High Performance Computers In Industry, Geoffrey C. Fox, Wojtek Furmanski Jan 1995

The Use Of The National Information Infrastructure And High Performance Computers In Industry, Geoffrey C. Fox, Wojtek Furmanski

Northeast Parallel Architecture Center

We divide potential NII (National Information Infrastructure) services into five broad areas: Collaboration and televirtuality; InfoVISiON (Information, Video, Imagery, and Simulation on Demand), and digital libraries; commerce; metacomputing; WebTop productivity services. The latter denotes the broad suite of tools we expect to be offered on the Web in a general environment we term WebWindows. We review current and future World Wide Web technologies, which could underlie these services. In particular, we suggest an integration framework WebWork for High Performance (parallel and distributed) computing and the NII. We point out that pervasive WebWork and WebWindows technologies will enable, facilitate and substantially …

Go to article

Exploiting High Performance Fortran For Computational Fluid Dynamics, Volume 919, Ken Hawick, Geoffrey C. Fox Jan 1995

Exploiting High Performance Fortran For Computational Fluid Dynamics, Volume 919, Ken Hawick, Geoffrey C. Fox

Northeast Parallel Architecture Center

We discuss the High Performance Fortran data parallel programming language as an aid to software engineering and as a tool for exploiting High Performance Computing systems for computational uid dynamics applications. We discuss the use of intrinsic functions, data distribution directives and explicitly parallel constructs to optimize performance by minimizing communications requirements in a portable manner. In particular we use an implicit method such as the ADI algorithm to illustrate the major issues. We focus on regular mesh problems, since these can be efficiently represented by the existing HPF definition, but also discuss issues arising from the use of irregular …

Go to article

A Multithreaded Message Passing Environment For Atm Lan/Wan, Rajesh Yadav, Rajashekar Reddy, Salim Hariri, Geoffrey C. Fox Jan 1995

A Multithreaded Message Passing Environment For Atm Lan/Wan, Rajesh Yadav, Rajashekar Reddy, Salim Hariri, Geoffrey C. Fox

Northeast Parallel Architecture Center

Large scale High Performance Computing and Communication (HPCC) applications (e.g. Video-on-Demand, and HPDC) would require storage and processing capabilities which are beyond existing single computer systems. The current advances in networking technology (e.g. ATM) have made high performance network computing an attractive computing environment for such applications. However, using only high speed network is not sufficient to achieve high performance distributed computing environment unless some hardware and software problems have been resolved. These problems include the limited communication bandwidth available to the application, high overhead associated with context switching, redundant data copying during protocol processing and lack of support to …

Go to article

High Performance Distributed Computing, Geoffrey C. Fox Jan 1995

High Performance Distributed Computing, Geoffrey C. Fox

Northeast Parallel Architecture Center

High Performance Distributed Computing (HPDC) is driven by the rapid advance of two related technologies -- those underlying computing and communications, respectively. These technology pushes are linked to application pulls, which vary from the use of a cluster of some 20 workstations simulating fluid flow around an aircraft, to the complex linkage of several hundred million advanced PCs around the globe to deliver and receive multimedia information. The review of base technologies and exemplar applications is followed by a brief discussion of software models for HPDC, which are illustrated by two extremes -- PVM and the conjectured future World Wide …

Go to article

Basic Issues And Current Status Of Parallel Computing -- 1995, Geoffrey C. Fox Jan 1995

Basic Issues And Current Status Of Parallel Computing -- 1995, Geoffrey C. Fox

Northeast Parallel Architecture Center

The best enterprises have both a compelling need pulling them forward and an innovative technological solution pushing them on. In high-performance computing, we have the need for increased computational power in many applications and the inevitable long-term solution is massive parallelism. In the short term, the relation between pull and push may seem unclear as novel algorithms and software are needed to support parallel computing. However, eventually parallelism will be present in all computers -- including those in your children's video game, your personal computer or workstation, and the central supercomputer.

Go to article

Passion Runtime Library For The Intel Paragon, Alok Choudhary, Rajesh Bordawekar, Sachin More, K. Sivaram, Rajeev Thakur Jan 1995

Passion Runtime Library For The Intel Paragon, Alok Choudhary, Rajesh Bordawekar, Sachin More, K. Sivaram, Rajeev Thakur

Electrical Engineering and Computer Science - All Scholarship

We are developing a runtime library which provides a number of routines to perform the I/O required in parallel applications in an efficient and convenient manner. This is part of a project called PASSION, which aims to provide software support for high-performance parallel I/O at the compiler, runtime and file system levels. The PASSION Runtime Library uses a high-level interface which makes it easy for the user to specify the I/O required in the program. The user only needs to specify what portion of the data structure needs to read from or written to the file, and the PASSION routines …

Go to article

A Simulation Model Of A Surveillance Radar Data Processing System Using Hi-Mass, Steven D. Farr, Alex F. Sisti, Douglas G. Fritz, Robert G. Sargent Jan 1995

A Simulation Model Of A Surveillance Radar Data Processing System Using Hi-Mass, Steven D. Farr, Alex F. Sisti, Douglas G. Fritz, Robert G. Sargent

Electrical Engineering and Computer Science - All Scholarship

This paper discusses the model specification, construction of the executable model, model execution, and the simulation results of a simulation model of a surveillance radar data processing system that was developed using the Hierarchical Modeling and Simulation System (HI-MASS). HI-MASS is an object oriented C++ based system that supports model specification (modeling) using the Hierarchical Control Flow Graph Model paradigm and executes simulation models using the sequential synchronous simulation execution algorithm. Models specified in this model paradigm use two complementary hierarchical specification structures, one to specify the model components and their interconnections and the other to specify the behaviors of …

Go to article

An Evaluation Of Design Tradeoffs In A High Performance Media-On-Demand Server, Divyesh Jadav, Chutimet Srinilta, Alok Choudhary, P. B. Berra Jan 1995

An Evaluation Of Design Tradeoffs In A High Performance Media-On-Demand Server, Divyesh Jadav, Chutimet Srinilta, Alok Choudhary, P. B. Berra

Electrical Engineering and Computer Science - All Scholarship

One of the key components of a multi-user multimedia-on-demand system is the data server. Digitalization of traditionally analog data such as video and audio, and the feasibility of obtaining network bandwidths above the gigabit-per-second range are two important advances that have made possible the realization, in the near future, of interactive distributed multimedia systems. Secondary-to-main memory I/O technology has not kept pace with advances in networking, main memory and CPU processing power. Consequently, the performance of the server has a direct bearing on the overall performance of such a system. In this paper we present a high-performance solution to the …

Go to article

National Hpcc Software Exchange, Shirley Browne, Jack Dongarra, Stan Green, Keith Moore, Tom Rowan, Reed Wade, Geoffrey .. Fox, Ken Hawick Jan 1995

National Hpcc Software Exchange, Shirley Browne, Jack Dongarra, Stan Green, Keith Moore, Tom Rowan, Reed Wade, Geoffrey .. Fox, Ken Hawick

Electrical Engineering and Computer Science - All Scholarship

This report describes an effort to construct a National HPCC Software Exchange (NHSE). This system shows how the evolving National Information Infrastructure (NII) can be used to facilitate sharing of software and information among members of the High Performance Computing and Communications (HPCC) community. To access the system use the URL: http://www.netlib.org/nse/.

Go to article

Verification And Validation Of Simulation Models, Douglas G. Fritz, Robert G. Sargent, Thorsten Daum Jan 1995

Verification And Validation Of Simulation Models, Douglas G. Fritz, Robert G. Sargent, Thorsten Daum

Electrical Engineering and Computer Science - All Scholarship

The Hierarchical Modeling and Simulation System (HI-MASS) is a prototype modeling and simulation system that supports modeling based on the Hierarchical Control Flow Graph Model paradigm and simulation execution using a sequential synchronous simulation algorithm. The prototype is an object oriented C++ based system designed for a Unix environment and implemented using freely available software tools. Models are specified using two complementary hierarchical model specification structures, one to specify the components which comprise a model and how those components are interconnected, and the other to specify the behaviors of the individual components. A graphical user interface provides for component and …

Go to article

Effects Of Technology Mapping On Fault Detection Coverage In Reprogrammable Fpgas, Kevin A. Kwiat, Warren Debany, Salim Hariri Jan 1995

Effects Of Technology Mapping On Fault Detection Coverage In Reprogrammable Fpgas, Kevin A. Kwiat, Warren Debany, Salim Hariri

Electrical Engineering and Computer Science - All Scholarship

Although Field-Programmable Gate Arrays (FPGAs) are tested by their manufacturers prior to shipment, they are still susceptible to failures in the field. In this paper, test vectors generated for the emulated (i.e., mission) circuit are fault simulated on two different models: the original view of the circuit, and the design as it is mapped to the FPGA's logic cells. Faults in the cells and in the programming logic are considered. Experiments show that this commonly-used approach fails to detect most of the faults in the FPGA.

Go to article

First Prev