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 271 - 300 of 532

Full-Text Articles in Computer Sciences

Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox Jan 1996

Benchmarking The Computation And Communication Performance Of The Cm-5, Kivanc Dincer, Zeki Bozkus, Sanjay Ranka, Geoffrey C. Fox

Northeast Parallel Architecture Center

Thinking Machines' CM-5 machine is a distributed-memory, message-passing computer. In this paper we devise a performance benchmark for the base and vector units and the data communication networks of the CM-5 machine. We model the communication characteristics such as communication latency and bandwidths of point-to-point and global communication primitives. We show, on a simple Gaussian elimination code, that an accurate static performance estimation of parallel algorithms is possible by using those basic machine properties connected with computation, vectorization, communication, and synchronization. Furthermore, we describe the embedding of meshes or hypercubes on the CM-5 fat-tree topology and illustrate the performance results …

Go to article

Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam Jan 1996

Efficient Algorithms For Array Redistribution, Rajeev Thakur, Alok Choudhary, J. Ramanujam

Electrical Engineering and Computer Science - All Scholarship

Dynamic redistribution of arrays is required very often in programs on distributed memory parallel computers. This paper presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find …

Go to article

An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary Jan 1996

An Extended Two-Phase Method For Accessing Sections Of Out-Of-Core Arrays, Rajeev Thakur, Alok Choudhary

Electrical Engineering and Computer Science - All Scholarship

A number of applications on parallel computers deal with very large data sets that cannot fit in the main memory. In such applications, data must be stored in files on disks and fetched into memory during program execution. Parallel programs with large out-of-core arrays stored in files must read/write smaller sections of the arrays from/to files. In this paper, we describe a method for accessing sections of out-of-core arrays efficiently. Our method, the extended two phase method, uses collective I/O: Processors cooperate to combine several I/O requests into fewer larger granularity requests, reorder requests so that the file is accessed …

Go to article

Designing Dependencies, Howard A. Blair Dec 1995

Designing Dependencies, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

Given a binary recursively enumerable relation R, one or more logic programs over a language L can be constructed and interconnected to produce a dependency relation D on selected predicates within the Herbrand base BL of L isomorphic to R. D can be, optionally, a positive, negative or mixed dependency relation. The construction is applied to representing any effective game of the type introduced by Gurevich and Harrington, which they used to prove Rabin's decision method for S2S, as the dependency relation of a logic program. We allow games over an infinite alphabet of possible moves. We use this representation …

Go to article

Simulations Between Programs As Cellular Automata, Howard A. Blair, Fred Dushin, Polar Humenn Dec 1995

Simulations Between Programs As Cellular Automata, Howard A. Blair, Fred Dushin, Polar Humenn

Electrical Engineering and Computer Science - Technical Reports

We present cellular automata on appropriate digraphs and show that any covered normal logic program is a cellular automaton. Seeing programs as cellular automata shifts attention from classes of Herbrand models to orbits of Herbrand interpretations. Orbits capture both the declarative, model-theoretic meaning of programs as well as their inferential behavior. Logically and intentionally different programs can produce orbits that simulate each other. Simple examples of such behavior are compellingly exhibited with space-time diagrams of the programs as cellular automata. Construing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn …

Go to article

Using Passion System On Lu Factorization, Haluk Rahmi Topcuoglu, Alok Choudhary Nov 1995

Using Passion System On Lu Factorization, Haluk Rahmi Topcuoglu, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

Parallel I/0 subsystems are added to massively parallel computers in order to lessen I/0 bottleneck to some extent. Up to now, a few number of parallel software systems have been designed and implemented to assist programmers in I/0 intensive applications; PASSION is one of them. By providing parallel I/0 support at the language, compiler and run-time level, PASSION system explores the large design space of parallel systems. The target of this paper is to show the performance benefits of using PASSION I/0 libraries at runtime in comparison with using conventional parallel I/0 primitives for high performance parallel I/0 in LU …

Go to article

A Statistical Approach To Mpeg Video Stream Characterization, Kubilay Cardakli Jul 1995

A Statistical Approach To Mpeg Video Stream Characterization, Kubilay Cardakli

Electrical Engineering and Computer Science - Technical Reports

As video consumes a significant percentage of the available network bandwidth, understanding video bandwidth requirements will translate into better network control schemes. In this study, several commercially available video streams are statistically analyzed and several modeling approaches are developed. The segmentation techniques are found to be rewarding. However, the improvements due to complexity of the polynomial models are insignificant.

Go to article

A Domain-Specific Parallel Programming System Ii. Automatic Data Partitioning, Elaine Wenderholm May 1995

A Domain-Specific Parallel Programming System Ii. Automatic Data Partitioning, Elaine Wenderholm

Electrical Engineering and Computer Science - Technical Reports

εm is a high-level programming system which puts parallelism within the reach of scientists who are not sophisticated programmers. εm both restricts and simplifies the programming interface, and thereby eases both the conceptual task of the programmer and the analytical task of the compiler. The εm compiler performs automatic data structure definition, scheduling and data partitioning. This document presents the automatic data partitioning algorithm used in εm.

Go to article

Weighted Coverings And Packings, G. D. Cohen, Iiro Honkala, S. N. Litsyn, H. F. Mattson Jr Feb 1995

Weighted Coverings And Packings, G. D. Cohen, Iiro Honkala, S. N. Litsyn, H. F. Mattson Jr

Electrical Engineering and Computer Science - Technical Reports

In this paper we introduce a generalization of the concepts of coverings and packings in Hamming space called weighted coverings and packings. This allows us to formulate a number of well-known coding theoretical problems in a uniform manner. We study the existence of perfect weighted codes, discuss connections between weighted coverings and packings, and present many constructions for them.

Go to article

Many-To-Many Personalized Communication With Bounded Traffic, Sanjay Ranka, Ravi V. Shankar, Khaled A. Alsabti Jan 1995

Many-To-Many Personalized Communication With Bounded Traffic, Sanjay Ranka, Ravi V. Shankar, Khaled A. Alsabti

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

This paper presents solutions for the problem of many-to-many personalized communication, with bounded incoming and outgoing traffic, on a distributed memory parallel machine. We present a two-stage algorithm that decomposes the many-to-many communication with possibly high variance in message size into two communications with low message size variance. The algorithm is deterministic and takes time 2tµ (+ lower order terms) when t >= O(p2; + p tau/µ). Here t is the maximum outgoing or incoming traffic at any processor, tau is the startup overhead and µ is the inverse of the data transfer rate. Optimality is achieved when the traffic …

Go to article

Kripke Logical Relations And Pcf, Peter W. O'Hearn, John G. Riecke Jan 1995

Kripke Logical Relations And Pcf, Peter W. O'Hearn, John G. Riecke

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

Sieber has described a model of PCF consisting of continuous functions that are invariant under certain (finitary) logical relations, and shown that it is fully abstract for closed terms of up to third-order types. We show that one may achieve full abstraction at all types using a form of "Kripke logical relations" introduced by Jung and Tiuryn to characterize λ definability.

Go to article

Objects, Interference, And The Yoneda Embedding, Peter W. O'Hearn, Uday S. Reddy Jan 1995

Objects, Interference, And The Yoneda Embedding, Peter W. O'Hearn, Uday S. Reddy

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

We present a new semantics for Algol-like languages that combines methods from two prior lines of development: [1] the object-based approach of [28,29], where the meaning of an imperative program is described in terms of sequences of observable actions, and [2] the functor-category approach initiated by Reynolds [31], where the varying nature of the run-time stack is explained using functors from a category of store shapes to a category of cpos. The semantics gives an account of both the phenomena of local state and irreversibility of state change. As an indication of the accuracy obtained, we present a full abstraction …

Go to article

Syntactic Control Of Interference Revisited, Peter W. O'Hearn, A. J. Power, M. Takeyama, R. D. Tennent Jan 1995

Syntactic Control Of Interference Revisited, Peter W. O'Hearn, A. J. Power, M. Takeyama, R. D. Tennent

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

In "Syntactic Control of Interference" (POPL, 1978), J. C. Reynolds proposes three design principles intended to constrain the scope of imperative state effects in Algol-like languages. The resulting linguistic framework seems to be a very satisfactory way of combining functional and imperative concepts, having the desirable attributes of both purely functional languages (such as pcf) and simple imperative languages (such as the language of while programs). However, Reynolds points out that the "obvious" syntax for interference control has the unfortunate property that fi-reductions do not always preserve typings. Reynolds has subsequently presented a solution to this problem (ICALP, 1989), but …

Go to article

Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent Jan 1995

Parametricity And Local Variables, Peter W. O'Hearn, R. D. Tennent

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

We propose that the phenomenon of local state may be understood in terms of Strachey 's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of locally-declared variables in the same way that a parametrically polymorphic function is independent of types to which it is instantiated. A connection between parametricity and representational abstraction was first suggested by J. C. Reynolds. Reynolds used logical relations to formalize this connection in languages with type variables and user-defined types. We use relational parametricity to construct a model for an Algol-like language …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

First Prev Next Last