Digital Commons Network^™

Prefetching In File Systems For Mimd Multiprocessors, Carla Schlatter Ellis, David Kotz

Dartmouth Scholarship

The problem of providing file I/O to parallel programs has been largely neglected in the development of multiprocessor systems. There are two essential elements of any file system design intended for a highly parallel environment: parallel I/O and effective caching schemes. This paper concentrates on the second aspect of file system design and specifically, on the question of whether prefetching blocks of the file into the block cache can effectively reduce overall execution time of a parallel computation, even under favorable assumptions. \par Experiments have been conducted with an interleaved file system testbed on the Butterfly Plus multiprocessor. Results of …

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Computer Science: Faculty Publications and Other Works

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels …

An Event-Action Model And Associated Architecture For Monitoring Parallel And Distributed Systems, Dan C. Marinescu, James E. Lumpp, Thomas L. Casavant, Howard Jhay Siegel

Department of Computer Science Technical Reports

No abstract provided.

On An Ssor Matari Relationship And Its Consequences, S. Galanis, A. Hadjidimos, D. Noutsos

Department of Computer Science Technical Reports

No abstract provided.

Implementing Educational Software And Evaluating Its Academic Effectiveness: Part Ii, Karen Jolicoeur, Dale E. Berger

CGU Faculty Publications and Research

In Part I, published last month, we presented a successful classroom implementation plan for integrating educational software into elementary school classrooms. Implementing educational software successfully into classrooms is an essential prerequisite to achieving the second goal of the present research-evaluating how much students learned by using specific software programs. In Part II, we will measure how effective eight software programs were at teaching fifth grade students new fraction concepts and spelling words. In addition, we will examine the validity of teacher and student software ratings based on the effectiveness of each program.

Comments On Proposed Transport Protocols, Anil Bhatia, James Sterbenz, Gurudatta M. Parulkar

All Computer Science and Engineering Research

Over the last few years, a number of research groups have made considerable progress on the design of high speed networks- on the order of a few hundred Mbps to the few Gbps. The emphasis of this work has been on the design of packet switches and on the design of network access protocols. However, this work has not yet addressed the internetworking and transport level issues in the high speed internet. As part of our effort on the design of VHSI model, we considered the appropriateness of recently proposed transport protocols, NETBLT and VMTP, as candidates for the transport …

A Parallel-Processing Subsystem For Rapid 3-D Interpolation Of Ct Images, William A. Barrett, Stephen J. Allan, Scott R. Cannon

Faculty Publications

An inexpensive parallel-processing subsystem for the rapid interpolation of CT image planes is demonstrated with a variety of node topologies. The subsystem is based on a tree network of INMOS T414 Transputer processors and is hosted by an AT-based image workstation. The subsystem accepts a stack of eight arbitrarily-spaced 256 x 256 image planes from the host. Subsystem output to the host consists of a stack of 32 scaled and evenly-spaced image planes (256 x 256 x 32 with cubic voxels). Benchmark execution times ranged from 12.3 seconds for three nodes to 5.8 seconds for eight nodes.

Dynamic Display And Quantitative Analysis Of Three-Dimensional Left Ventricular Pathology, William A. Barrett, Jayaram K. Udupa

Faculty Publications

Techniques have been developed for automated extraction and dynamic interactive display of three-dimensional (3D) left ventricular (LV) surface anatomy from Cine CT images using a PC-based image display architecture. Images of both endocardial and myocardial surface anatomy are generated from multiple views at multiple time instances to demonstrate various LV pathologies including apical akinesis, apical and posterior aneurysms, LV Failure, IHSS, and a left atrial myxoma. Surface generation requires interpolation between scans, surface tracking, and rendering. Generation of 60 views corresponding to a single time instance requires approximately 15 minutes. LV dimensions are measured between two or more surface points …

Parallel Algorithms For Evaluating Sequences Of Set-Manipulation Operations, Mikhail J. Atallah, Michael T. Goodrich, S. Rao Kosaraju

Department of Computer Science Technical Reports

No abstract provided.

On Local Implicit Approximation And Its Applications, Jung Hong Chuang, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

A "Generalization" Of The Patel-Jordan Parallel Iterative Technique, John P. Bonomo, Wayne R. Dyksen

Department of Computer Science Technical Reports

No abstract provided.

A Note On The Complexity Of A Simple Transportation Problem, Greg N. Frederickson

Department of Computer Science Technical Reports

No abstract provided.

Computations With Algebraic Curves, Shreeram S. Abhyankar, Chandrajit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Joyce Performance On A Multiprocessor, Per Brinch Hansen, Rangachari Anand

Electrical Engineering and Computer Science - Technical Reports

Joyce is a parallel programming language based on CSP and Pascal. The language has been moved from the IBM PC to the Encore Multimax. The paper explains how the multiprocessor implementation of Joyce was guided by performance evaluation. The measurements show that the speed-up of Joyce programs follows Amdahl’s law.

A Multiprocessor Implementation Of Joyce, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Joyce is a programming language for parallel computers based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a multiprocessor implementation of Joyce.

Implementing Educational Software And Evaluating Its Academic Effectiveness: Part I, Karen Jolicoeur, Dale E. Berger

CGU Faculty Publications and Research

Two major obstacles are responsible for the delay in getting good educational software into schools. First, software implementation is a complex process that many schools are simply not prepared to undertake. Second, there is very little empirical research available on the specific factors that make educational software effective, leaving it extremely difficult to separate good from poor quality software. We will describe a basic plan for implementing educational software into classrooms, incorporating a research design that permits educational researchers to measure the effectiveness of the software. Part I of this series of two articles presents a basic plan for implementing …

Odd Primary Periodic Phenomena In The Classical Adams Spectral Sequence, Paul L. Shick

Mathematics and Computer Science

We study certain periodic phenomena in the cohomology of the mod ρ Steenrod algebra which are related to the polynomial generators υ_n ∈ π∗ΒΡ. A chromatic resolution of the Ε₂ term of the classical Adams spectral sequence is constructed.

Relational Completeness Of Show And Tell Visual Programming Language, Takayuki Dan Kimura

All Computer Science and Engineering Research

In this paper we present the database applications of the Show and Tell Language (STL) and demonstrate the relational completeness of the language. STL is a visual programming language designed for novice computer users who are not familiar with keyboarding. A program can be constructed by using only a pointing device, except for textual data entry. A program can be constructed by using only a pointing device, except for textual data entry. Various programming concepts such as subroutine, iteration, recursion, concurrency, exception, and so forth are represented by two-dimensional graphic patterns and icons. The language is used to test the …

A Lower Bound On Embedding Tree Machines With Balanced Processor Utilization, Ajay K. Gupta, Susanne E. Hambrusch

Department of Computer Science Technical Reports

No abstract provided.

Efficient Algorithms For Hybrid Data/Voice Transmissions, Andrzej Kusiuk, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Output-Sensitive Hidden Surface Elimination For Rectangles, Mikhail J. Atallah, Michael T. Goodrich

Department of Computer Science Technical Reports

No abstract provided.

Semi-Automatic Process Decomposition For Non-Shared Memory Machines, Charles Koelbel, Piyush Mehrotra

Department of Computer Science Technical Reports

No abstract provided.

A Formalism For Describing Data Distribution, Charles Koelbel

Department of Computer Science Technical Reports

No abstract provided.

Time-Varying Images: The Effect Of Finite Resolution On Uniqueness, Chia-Hoang Lee

Department of Computer Science Technical Reports

No abstract provided.

Analysis Of A Two Level Asynchronous Algorithm For Pdes, John R. Rice, Dan C. Marineseu

Department of Computer Science Technical Reports

No abstract provided.

An Optimal Parallel Algorithm For Preemptive Job Scheduling That Minimizes Maximum Lateness, Susan Rodger

Department of Computer Science Technical Reports

No abstract provided.

Composite Graph Coloring Algorithms And Applications, Stephen Hong Seng Yek, Billy E. Gillett

Computer Science Technical Reports

A vertex-composite graph is a graph that can have unequal chromaticities on its vertices. Vertex-composite graph coloring or composite graph coloring involves coloring each vertex of a composite graph with consecutive colors according to the vertex's chromaticity with no two vertices adjacent to one another having the same color(s).

New heuristic algorithms including the use of the saturation degree method have been developed in this research. All eleven heuristic algorithms including Clementson and Elphick algorithms were then tested using random composite graphs with five different chromaticity distributions. The best algorithm which uses the least average colors from the experiment is …

A Parallel Distributed Approach To Parsing Natural Language Deterministically, Stan C. Kwasny

All Computer Science and Engineering Research

The Determinism Hypothesis (Marcus, 1980) has given rise to much debate. The hypothesis makes explicit the idea that Natural Language interpretation need not depend in any fundamental way on the use of pseudo-parallelism or backtracking. We are exploring the consequences of this hypothesis in attempting to develop approaches to parsing which integrates current work in parallel distributed adaptive networks. We follow the basic approach of "Wait-and-See" parsing (WASP) which has shown the Natural Language interpretation of all but some varieties of "garden-path" sentences can be deterministically performed using a stack, a buffer for sentence constituents, and partitioned packets of rules. …

A Graph Browser With Zoom And Roam For Allegro Common Lisp, Steve B. Cousins, J. Andrew Fingerhut

All Computer Science and Engineering Research

This report describes an object-oriented tool that has been developed for viewing graphs on a Macintosh II computer using Allegro Common Lisp. The tool is useful for visualizing data which can be represented in tree or graph form. The graphs can be viewed for far away to get a global view, and from close up so that the labels on the vertices can be discerned. Scrolling can be performed at a nearly infinite number of resolutions, and a search feature makes it easy to find any node rapidly. Although the 'information space' on which the graph is logically plotted is …

A User Guide To The Algorithm Mapper: A System For Modeling And Evaluating Parallel Applications/Architecture Pairs, C. E. Houstis, Elias N. Houstis, John R. Rice, S. M. Samartizis, D.L. Alexandrakis

Department of Computer Science Technical Reports

No abstract provided.