| NW Lab for Integrated Systems |
24 MAY 91 |
42 pages |
| Authors:
Larry Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
 | This report gives an overview of the research and development projects supported by the VLSI Architectures and CAD contract between DARPA and the University of Washington's Northwest Laboratory for Integrated Systems. Because most of these scientific and engineering accomplishments have been reported on in the technical literature, this report serves primarily as a introduction to the topics. Emphasis here is on overall directions, motivation, and describing what has been achieved. ... |
|
| Advanced Numerical Techniques of Performance Evaluation. Volume 1 |
JUN 90 |
277 pages |
| Authors:
UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Partial contents: PRESTO - A System for Object-oriented Parallel Programming; The Performance of Parallel Computer Systems; The PRESTO User's Manual; An Open Environment for Building Parallel Programming Systems. |
|
| Advanced Numerical Techniques of Performance Evaluation. Volume 2 |
JUN 90 |
502 pages |
| Authors:
UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The conservative (Bryant-Chandy-Misra) parallel simulation paradigm was originally developed in a distributed system setting. However, the recent widespread availability of relatively inexpensive, medium-scale shared memory multiprocessors encourages a re-examination of traditional approaches to its implementation. Many of the obstacles to good performance, such as communication delay, sub-optimal model partitioning, artificial blocking, and the high cost of deadlock avoidance, deadlock detection, and deadlock recovery, can be reduced or even eliminated in ... |
|
| Amorphization in Zr3Al Irradiated with 1-MeV e(-) and Kr(+) |
90 |
|
| Authors:
J. Koike; P. R. Okamoto; L. E. Rehn; M. Meshii; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
 | In situ electron microscopy is used to study irradiation-induced amorphization in Zr3Al from 10 to 295 K by 1-MeV electrons and at 295 K with 1- MeV Kr(+); the onset of amorphization is observed when the long-range order parameter decreases substantially with both electron and Kr(+); diffuse streaks are observed in the diffraction pattern prior to amorphization; this is attributed to a softening of the shear elastic constant, C'=(C11-C12)/2, due ... |
|
| High Performance Computer Programming Environments |
30 SEP 88 |
10 pages |
| Authors:
Lawrence Snyder; David Notkin; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This one year grant had the primary goal the assessment of the Poker Parallel Programming environment and the planning and design of new parallel programming environment. These goals were achieved. The new programming environment, to be built on a software platform that permits rapid prototyping of alternative environments, was designed using a three level language abstraction. The central publications include the assessment of Poker, two papers on prototype graphic debugging ... |
|
| A Taxonomy of Synchronous Parallel Machines |
AUG 88 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| A new classificational scheme is presented which is consistent with Flynn's taxonomy but is more expressive. The crucial idea is to recognize that a reference stream is composed of both values and addresses; their treatment exposes critical features of an architecture. This insight, together with the accompanying formal mechanism built on top of it, enables a large variety of recently developed (since Flynn's work) machines to be distinguished, including VLIW, ... |
|
| A Model for Architectural Comparison |
APR 88 |
|
| Authors:
Sam Ho; Larry Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Recently, architectures for sequential computers have become a topic of much discussion and controversy. At the center of this storm is the Reduced Instruction Set Computer, or RISC, first described at Berkeley in 1980. While the merits of the RISC architecture cannot be ignored, its opponents have tried to do just that, while its proponents have expanded and frequently exaggerated them. This state of affairs has persisted to this day. ... |
|
| Poker (4.1): A Programmer's Reference Guide |
APR 88 |
97 pages |
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This document gives a succinct description of the facilities available with the Poker Parallel Programming Environment. The emphasis is on what is available rather than how to achieve particular results. Although the sections are self-contained, so that they may be referred to independently, there are a few things you should know: 1) Poker uses interactive graphics. The graphics are described in Section 2; the interaction is described in Section 3; ... |
|
| Experiences with Poker |
APR 88 |
12 pages |
| Authors:
David Notkin; David Socha; Lawrence Snyder; Mary L. Bailey; Bruce Forstall; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Experience from over five years of building nonshared memory parallel programs using the Poker Parallel Programming Environment has positioned us to evaluate our approach to defining and developing parallel programs. This paper presents the more significant results of our evaluation of Poker. The evaluation is driving our next effort in parallel programming environment; many of the results should be sufficiently general to apply to other related efforts. |
|
| Voyeur: Graphical Views of Parallel Programs |
APR 88 |
12 pages |
| Authors:
David Socha; Mary L. Bailey; David Notkin; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Voyeur is a prototype system that facilitates the construction of application-specific, visual views of parallel programs. These views range from textual views showing the contents of variables to graphical maps of the state of the computational domain of the program. These views have been instrumental in quickly detecting bugs that would have been difficult to detect otherwise. |
|
| Valiant's Maximum Algorithm with Sequential Memory Accesses |
APR 88 |
5 pages |
| Authors:
Robert Cypher; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper examines the performance of Valiant's PRAM algorithm for finding the maximum of a set of numbers, assuming that a modified PRAM model is used. The modified PRAM is like a standard CRCW PRAM, except that multiple read or write requests to a single memory location are handled sequentially. It is shown that using this model, Valiant's algorithm requires O(sqrt(N)) time to find the maximum of N numbers using ... |
|
| Parallel Debugging Using Graphical Views |
MAR 88 |
13 pages |
| Authors:
M. Bailey; D. Socha; D. Notkin; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Graphical views are essential for debugging parallel programs because of the large quantity of state information contained in parallel programs. Voyeur, a prototype system for creating graphical views of parallel programs, provides a cost-effective way to construct such views for any parallel programming system. We illustrate Voyeur by discussing four views created for debugging Poker programs. One is a general trace facility for any Poker program. The other three are ... |
|
| Practical Algorithms for Image Component Labeling on SIMD Mesh Connected Computers |
DEC 87 |
11 pages |
| Authors:
R. E. Cypher; L. Snyder; J. L. Sanz; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Two new parallel algorithms are presented for the problem of labeling the connected components of a binary image, which is also known as the connected ones problem. The machine model is an SIMD two-dimensional mesh connected computer consisting of an N x N array of processing elements, each containing a single pixel of an N x N image. Both new algorithms use a shrinking operation defined by Levialdi and have ... |
|
| Achieving Speedups for a Shared Memory Model Language on an SIMD parallel Computer |
SEP 87 |
22 pages |
| Authors:
Ray Greenlaw; Larry Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The potential for speeding up a shared memory model sequential programming language, APL, by using an idealized non-shared memory parallel computer is investigated. The authors simulated the running of APL's dyadic, reduction, and subscript operators on a 4-connected mesh SIMD parallel computer. The simulation results indicate that these operations can be sped up significantly using parallelism. These findings support the thesis that parallelism can speedup a majority of 'typical' APL ... |
|
| The Triangle: a Multiprocessor Architecture for Fast Curve and Surface Generation |
AUG 87 |
|
| Authors:
Thomas J. Holman; Tony DeRose; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper describes the architecture and operation of the Triangle, a pipelined, parallel multiprocessor architecture for the computation and rendering of line segments, conic sections, spline curves, triangular patch surfaces, and tensor product surfaces. Based on a generalization of de Casteljau's algorithm for computing points on Bezier curves, the Triangle can be used as an accelerator to dramatically enhance the performance of standard graphics workstations. Although there is a wide ... |
|
| Poker (4.0): A Programmer's Reference Guide |
AUG 87 |
86 pages |
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This document gives a succinct description of the facilities available with the Poker Programming Environment. The emphasis is on what is available rather than how to achieve particular results. Although the sections are self-contained, so that they may be referred to independently, there are a few things you should know: 1) Poker uses interactive graphics. The graphics are described in Section 2; the interaction is described in Section 3; 2) ... |
|
| The Hough Transform has O(N) Complexity on SIMD N x N Mesh Array Architectures |
JUL 87 |
|
| Authors:
R. E. Cypher; J. L. Sanz; L. Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper reports on new algorithms for computing the Hough transform on mesh array architectures. The mesh is fine-grained, consisting of an N x N array of processors, each holding a single pixel of the image. The mesh array operates in an SIMD mode. Several algorithms, differing in the techniques they use, their asymptotic complexity, or the architectural resources required, are presented for computing the Hough transform. The main algorithm ... |
|
| Parallel Programming Paradigms |
JUL 87 |
142 pages |
| Authors:
Philip A. Nelson; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Paradigms for the development of sequential algorithms, such as divide-and-conquer and the greedy method, are well known. Paradigms for the development of parallel algorithms, especially algorithms for non-shared memory MIMD machines, are not well known. These paradigms are important, not only as tools for the development of new algorithms, but also because algorithms using the same paradigm often have common properties that can be exploited by operations such as contraction. ... |
|
| Hypercube and Shuffle-Exchange Algorithms for Image Component Labeling |
APR 87 |
8 pages |
| Authors:
R. E. Cypher; J. L. Sanz; L. Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper presents algorithms for labeling the connected components of a binary image using a hypercube or shuffle-exchange computer. The algorithms label the components of an sq 1 + N x sq 1 + N pixel image in O(long sq of N) time using a hypercube or shuffle-exchange computer with N processors and a constant amount of memory per processor. The algorithms that are presented are the first to solve ... |
|
| Allocation Strategies for APL on the CHiP (Configurable Highly Parallel) Computer |
MAR 87 |
80 pages |
| Authors:
James L. Schaad; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This master's thesis describes a series of experiments in which APL programs were mapped onto the processor elements of nonshared memory parallel computers and their concurrent execution was simulated. The effects of selecting one of several different array allocation schemes, different data routing policies and several processor topologies are reported. The general question of executing 'shared memory programming languages' on nonshared memory parallel computers is briefly considered. (RH) |
|
| An Analysis of Multiple Grain CHiP Architectures |
28 FEB 87 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The major accomplishments of the Blue CHiP Project Multigrain Architecture Research and described in the areas of theory, algorithms, architecture software and VLSI. A multigauge architecture is a design for a standard von Neumann machine that permits the data path to be partitioned into subunits that can execute concurrently when the data values are small . Thus it is a method of achieving parallelism within the arithmetic/logic unit of a ... |
|
| A Transparent Coprocessor for Interprocessor Communication in an MIMD computer |
JAN 87 |
|
| Authors:
Thomas J. Holman; Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper presents the design of a high performance interprocessor communication coprocessor for non-shared memory MIMD architectures. The design provides efficient interprocessor communication by relieving the computational processor of all communication related activities and by minimizing the overhead of packet assembly and disassembly. A multiprocessing scheme with zero process switch time allows this coprocessor to handle many communication ports with no additional overhead. Logical ports, which allow many computational processes ... |
|
| Near-Optimal Speedup of Graphics Algorithms Using Multigauge Parallel Computers |
DEC 86 |
|
| Authors:
Tony D. DeRose; Lawrence Snyder; Chyan Yang; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| A multigauge computer can have its datapath split into independent datapaths that execute operations on small data concurrently. This paper explains how certain forms of multigauge processing can be implemented with little cost in hardware; we illustrate this low cost implementation by describing the multigauging of the Quarter Horse microprocessor; and the authors report on the practical applications from graphics for which 95% of the theoretically possible speedup is achieved ... |
|
| Programming N-Cubes with a Graphical Parallel Programming Environment Versus an Extended Sequential Language |
NOV 86 |
|
| Authors:
Kevin Gates; David Socha; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| We compare the writing and execution of programs written in Cosmic Cube C with programs written in the graphical parallel programming environment and language Poker. Our example programs, an implementation of a Cholesky algorithm for a banded matrix, were written in both languages and compiled into object codes that ran on the Cosmic Cube. However the program written in Poker is shorter, faster and easier to write, easier to debug, ... |
|
| Type Architectures, Shared Memory and the Corollary of Modest Potential |
JUL 86 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The influence of the programming language model to specifying parallelism is explained: the SOR algorithm is used as an illustration; the concept of type of computer architecture--an idealized machine specifying the language/architecture interface-- is introduced; it is observed that the paracomputer (=CRCW -PRAM) has frequently been used as a type architecture, but it is inadequate; Valiant's maximum finding algorithm, though optimal for the CRCW-PRAM is proved to be suboptimal in ... |
|
| Poker on the Cosmic Cube: The First Retargetable Parallel Programming Language and Environment |
JUN 86 |
|
| Authors:
Lawrence Snyder; David Socha; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This paper describes a technique for retargetting Poker, the first complete parallel programming environment, to new parallel architectures. The specifics are illustrated by describing the retarget of Poker to CalTech's Cosmic Cube. Poker requires only three features from the target architecture: MIMD operation, message passing inter-process communication, and a sequential language (e.g. C) for the processor elements. In return Poker gives the new architecture a complete parallel programming environment which ... |
|
| An Investigation Into the Design Costs of a Single Chip Multigauge Machine |
JUN 86 |
22 pages |
| Authors:
Lawrence Snyder; Chyan Yang; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Multigauge computers can operate either with their full datapath width or with the datapath split into separate narrower width machines. Such a concept has been previously shown to provide parallelism when the data values are small. This paper reports on the costs of gauge-shiftable computers. Specifically a single chip microprocessor, the 32-bit Quarter Horse machine, is redesigned to be gauge shiftable under software control to two 16-bit microprocessors. A complete ... |
|
| Programming Solutions to the Algorithm Contraction Problem |
APR 86 |
|
| Authors:
Philip A. Nelson; Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Algorithms for the parallel solution of problems are usually designed assuming an unlimited number of processors. Physical parallel machines have a fixed number of processors. The algorithm contraction problem arises when an algorithm requires more processors than are available on the physical machine. This document presents tools for comparing algorithm contractions based on bottle neck communication paths. The authors apply these tools to minimum, matrix product and sorting. |
|
| Programming Environments for Systolic Arrays |
FEB 86 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Although a systolic array is often thought of as a hard wired device, there are many reasons to want to program systolic algorithms. In this paper the problem of providing an efficacious programming environment is addressed. The difficulties of programming complex parallel algorithms are shown to be reduced by using a new concept of a parallel program which maximizes the use of graphical abstractions and minimizes the need for symbolic ... |
|
| The Blue Chip Project II |
31 DEC 85 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The major accomplishments of the Blue CHiP Project are described in the areas of theory, algorithms, architecture, software, and VLSI. Keywords include: Parallel computation, VLSI, CHiP computer, Pringle computer, Coordination, Contractions, Configurable high parallel computer, Wafer scale integration graph embeddings, Poker, and Parallel language. |
|
| A Non-Systolic Matrix Product Algorithm |
NOV 85 |
27 pages |
| Authors:
Philip A. Nelson; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Most parallel matrix-matrix product algorithms for MIMD architectures are systolic. These algorithms can be adapted to be used on a general purpose architecture, such as the CHiP or cube machines. When the processors already contain the matrices, the algorithm can still be used by modifying it to circulate the data as if it was being fed in from an external source. We present a non-systolic matrix product algorithm in which ... |
|
| Poker 3.1: A Programmer's Reference Guide |
SEP 85 |
|
| Authors:
Lawrence Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| This document gives a succinct description of the facilities available with the Poker Programming Environment. The emphasis is on what is available rather than how to achieve particular results. Poker uses interactive graphics. The usual programming language notion of a source program as a monolithic piece of symbolic text has been replaced in Poker by a database. Object programs (the compiled database) are emulated by Poker and snapshots of the ... |
|
| Supercomputers and VLSI: The Effect of Large Scale Integration on Computer Architecture |
AUG 1984 |
|
| Authors:
L. Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The use of VLSI technology to build supercomputers is analyzed in depth. The benefits of VLSI are reviewed, and the liabilities are explored thoroughly. The perimeter problem and the planarity problem are identified as being critical limits on architectural design. The CHiP architecture, a highly parallel computer designed with VLSI implementation in mind, is scrutinized in terms of how well it exploits the benefit fo VLSI and how well it ... |
|
| Parallel Programming and the Poker Programming Environment |
APR 1984 |
|
| Authors:
L. Snyder; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| Parallel programming is described as the conversion of an abstract, machine independent algorithm to a form, called a program, suitable for execution on a particular computer. The conversion activity is simplified where the form of the abstraction is close to the form required of the programming system. Fine mechanisms are identified as commonly occurring in algorithms specification. The Poker Parallel Programming Environment is known to support these five mechanisms conveniently; ... |
|
| Total System Design (TSD) Methodology Assessment |
JAN 1983 |
|
| Authors:
Gruia-Catalin Roman; M. J. Stucki; R. K. Israel; W. E. Ball; W. D. Gillett; UNIV OF WASHINGTON SEATTLE DEPT OF COMPUTER SCIENCE
|
| The report is concerned with the nature of and strategies involved in the identification of the hardware/software mix that comprises a distributed system. Current state-of-the-art in the areas of software engineering and hardware design/selection is consolidated under the unifying umbrella of a methodological framework called the Total System Design (TSD) Framework. A distributed systems design methodology, called the TSD Methodology, is proposed and illustrated in the context provided by two ... |
|
Reports by Corporate Author
