Digital Commons Network^™

Parti Primitives For Unstructured And Block Structured Problems, Alan Sussman, Joel Saltz, Raja Das, S. Gupta, Dimitri Mavriplis, Ravi Ponnusamy

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

This paper describes a set of primitives (PARTI) developed to efficiently execute unstructured and block structured problems on distributed memory parallel machines. We present experimental data from a 3-D unstructured Euler solver run on the Intel Touchstone Delta to demonstrate the usefulness of our methods.

Benchmarking The Cm-5 For Image Processing Applications, Ravi V. Shankar, Ravi Ponnusamy, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

This paper presents benchmarking results for image processing algorithms on the Connection Machine model CM-5 and compares them with the results from the CM-2 and the Sun-4. Image processing algorithms with varying communication and computational requirements were implemented, tested and timed. The performance and the scalabilty of the CM-5 were analyzed and compared with that of the CM-2.

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanjay Ranka, Seema Hiranandani

Electrical Engineering and Computer Science - All Scholarship

A large class of scientific and engineering applications may be classified as irregular and loosely synchronous from the perspective of parallel processing. We present a partial classification of such problems. This classification has motivated us to enhance Fortran D to provide language support for irregular, loosely synchronous problems. We present techniques for parallelization of such problems in the context of Fortran D.

Spede: A Simple Programming Environment For Distributed Execution (Users' Manual), James Gochee

Dartmouth College Undergraduate Theses

Traditional single processor computers are quickly reaching their full computational potentials. The quest for faster and faster chips have brought technology to the point where the laws of physics are hampering future gains. Significant gains in speed must therefore come from using multiple processors instead of a single processor. This technology usually represents itself in the form of a parallel computer, such as the Connection Machine Model 5. Recently however, much interest has been focused on software that organizes single processor computers to behave like a parallel computer. This is desirable for sites which have large installations of workstations, since …

Spede: Simple Programming Environment For Distributed Execution, James Gochee

Dartmouth College Undergraduate Theses

One of the main goals for people who use computer systems, particularly computational scientists, is speed. In the quest for ways to make applications run faster, engineers have developed parallel computers, which use more than one CPU to solve a task. However, many institutions already posses significant computational power in networks of workstations. Through software, it is possible to glue together clusters of machines to simulate a parallel environment. SPEDE is one such system, designed to place the potential of local machines at the fingertips of the programmer. Through a simple interface, users design computational objects that can be linked …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 8, Number 1, January 1992, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A ten page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

A Prototype Document Image Analysis System For Technical Journals, George Nagy, Sharad C. Seth, Mahesh Viswanathan

School of Computing: Faculty Publications

Intelligent document segmentation can bring electronic browsing within the reach of most users. The authors show how this is achieved through document processing, analysis, and parsing the graphic sentence.

Lessons From Massively Parallel Applications On Message Passing Computers, Geoffrey C. Fox

Northeast Parallel Architecture Center

We review a decade's work on message passing MIMD parallel computers in the areas of hardware, software and applications. We conclude that distributed memory parallel computing works, and describe the implications of this for future portable software systems.

Static And Runtime Algorithms For All-To-Many Personalized Communication On Permutation Networks, Sanjay Ranka, Jhy-Chun Wang, Geoffrey C. Fox

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

With the advent of new routing methods, the distance to which a message is sent is becoming relatively less and less important. Thus, assuming no link contention, permutation seems to be an efficient collective communication primitive. In this paper we present several algorithms for decomposing all-to-many personalized communication into a set of disjoint partial permutations. We discuss several algorithms and study their effectiveness from the view of static scheduling as well as runtime scheduling. An approximate analysis shows that with n processors and assuming that every processor sends and receives d messages to random destinations, our algorithm can perform the …

On Hamiltonian Line Graphs, Zhi-Hong Chen

Scholarship and Professional Work - LAS

No abstract provided.

Energy-Related Feature Abstraction For Handwritten Digit Recognition, Thomas H. Fuller Jr.

All Computer Science and Engineering Research

Most handwritten character recognizers use either graphical (static) or first-order dynamic data. Our research speculates that the mental signal to write a digit might be partially encoded as an energy profile. We used artificial neural networks (ANN) to analyze energy-related features (first and second time derivatives) of handwritten digits of 20 subjects and later 40 subjects. An experimenal environment was developed on a NeXTstation with a real-time link to a pen-based GO computer. Although such an experiment cannot confirm an energy profile encoded in the writer, it did indicate the usefulness of energy-related features by recognizing 94.5% of the 600 …

A Study Of The Methodologies Currently Available For The Maintenance Of The Knowledge-Base In An Expert System, Kai Teh

Theses: Doctorates and Masters

This research studies currently available maintenance methodologies for expert system knowledge bases and taxonomically classifies them according to the functions they perform. The classification falls into two broad categories. These are: (1) Methodologies for building a more maintainable expert system knowledge base. This section covers techniques applicable to the development phases. Software engineering approaches as well as other approaches are discussed. (2) Methodologies for maintaining an existing knowledge base. This section is concerned with the continued maintenance of an existing knowledge base. It is divided into three subsections. The first subsection discusses tools and techniques which aid the understanding of …

Software Support For Irregular And Loosely Synchronous Problems, Alok Choudhary, Geoffrey C. Fox, Sanja Ranka, Seema Hiranandani

Northeast Parallel Architecture Center

A large class of scientific and engineering applications may be classified as irregular and loosely synchronous from the perspective of parallel processing. We present a partial classification of such problems. This classification has motivated us to enhance Fortran D to provide language support for irregular, loosely synchronous problems. We present techniques for parallelization of such problems in the context of Fortran D.

Scheduling Regular And Irregular Communication Patterns On The Cm-5, Ravi Ponnusamy, Rajeev Thakur, Alok Choudhary, Geoffrey C. Fox

Northeast Parallel Architecture Center

In this paper, we study the communication characteristics of the CM-5 and the performance effects of scheduling regular and irregular communication patterns on the CM-5. We consider the scheduling of regular communication patterns such as complete exchange and broadcast. We have implemented four algorithms for complete exchange and studied their performances on a 2D FFT algorithm. We have also implemented four algorithms for scheduling irregular communication patterns and studied their performance on the communication patterns of several synthetic as well as real problems such as the conjugate gradient solver and the Euler solver.

Which Applications Can Use High Performance Fortran And Fortran-D: Industry Standard Data Parallel Languages?, Alok Choudhary, Geoffrey C. Fox, Tomasz Haupt, S. Ranka

Northeast Parallel Architecture Center

In this paper, we present the first, preliminary results of HPF/Fortran-D language analysis based on compiling and running benchmark applications using a prototype implementation of HPF/Fortran-D compiler. The analysis indicate that the HPF is a very convenient tool for programming many applications on massively parallel and/or distributed systems. In addition, we cumulate experience on how to parallelize irregular problems to extend the scope of Fortran-D beyond HPF and suggest future extensions to the Fortran standard.

Compiling Distribution Directives In A Fortran 90d Compiler, Zeki Bozkus, Alok Choudhary, Geoffrey C. Fox, Sanjay Ranka

Northeast Parallel Architecture Center

Data Partitioning and mapping is one of the most important steps of in writing a parallel program; especially data parallel one. Recently, Fortran D, and subsequently, High Performance Fortran (HPF) have been proposed to allow users to specify data distributions and alignments for arrays in programs. This paper presents the design of a Fortran 90D compiler that takes a Fortran 90D program as input and produces a node program + message passing calls for distributed memory machines. Specifically, we present the design of the Data Partitioning Module that processes the alignment and distribution directives and illustrate what are the important …

Porting Chorus To The Pa-Risc: Booting, Jon Inouye, Ravi Konuru, Jonathan Walpole, Marion Hakanson

Computer Science Faculty Publications and Presentations

We started out with the low level Tut (HP-CX 2.0) boot code. One of our goals was to reuse as much of this code as possible, which would reduce the amount of low level code we would have to debug. This was very important, especially fiince the RP 9000/834 has a very complex I/O architecture and we lacked any sophisticated debugging tools. Writing the PA-Chorus boot code involved modifying the Tut code to match the Chorus startup sequence. In the remainder of this section, we present an overview of the PA-RISC boot mechanisms and the Chorus startup sequence. Sectlon 2 …

Porting Chorus To The Pa-Risc: Building, Debugging, Testing And Validation, Ravi Konuru, Marion Hakanson, Jon Inouye, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System to the Hewlett-Packard 9000 Series 800 workstation. This document describes the environment for building the Chorus kernel, the various kernel tests, and the debugging environment used for porting the Chorus operating system to the HP PA-RISC.

The information contained in this paper will be of interest to people who wish to:

• Use the PA-Chorus kernel for development and/or modification, • Know about the build environment for Chorus kernel on PA-RISC, • Know about the PA-Chorus approach to debugging, • …

Porting Chorus To The Pa-Risc: Overall Evaluation, Jonathan Walpole, Marion Hakanson, Jon Inouye, Ravi Konuru

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System kernel to the Hewlett-Packard 9000 Series 800 workstation. This document summarizes the matches and mis-matches between Chorus and the PA-RISC and outlines the general lessons learned during the project.

This document is intended for people who are interested in (a) the separation of machinedependent micro-kernel code from machine-independent micro-kernel code, (b) the interaction between operating system design and the PA-RISC architecture, and (c) the portability ofthe Chorus operating system.

The first report in the series, Porting Chorus to the PA-RISe: …

Porting Chorus To The Pa-Risc: Project Overview, Jonathan Walpole, Marion Hakanson, Jon Inouye, Ravi Konuru

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System to the Hewlett-Packard 9000 Series 800 workstation. This document presents an overview of the project, and outlines the other reports in the series and the relationships between them.

Porting The Chorus Supervisor And Related Low-Level Functions To The Pa-Risc, Ravi Konuru, Marion Hakanson, Jon Inouye, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This document is part of a series of reports describing the design decisions made in porting the Chorus Operating System to the Hewlett-Packard 9000 Series 800 workstation.

The Supervisor is the name given by Chorus to a collection of low-level functions that are machine dependent and have to be implemented when Chorus is ported from one machine to another. The Supervisor is responsible for interrupt, trap and exception handling, managing low-level thread initialization, context switch, kernel initialization, managing simple devices (timer and console) and offering a low-level debugger. This document describes the port of the Supervisor and related low-level functions. …

Query Optimization In Oodb, Hwee Hwa Pang, Hongjun Lu, Beng Chin Ooi

Research Collection School Of Computing and Information Systems

In object-oriented databases, relationships are generally maintained explicitly. The partial result of a retrieved object can be used to efficiently retrieve related objects. Instead of optimizing joins as in relational database systems, pointer chasing is optimized in object-oriented database systems. Further, semantics inherent in the object-oriented database, like superclass-subclass relationships and composite-component relationships between object classes, must be realised. In this paper, we describe our initial result in query optimization in an object-oriented database system. Semantic query transformation is used to preprocess the query. semantically optimized query is then translated into a query evaluation plan which comprises method invocations that …

Smimd - A Synchronous Multiple Instruction Multiple Data Computer Architecture, Cathy C. Roberts

Computer Science Theses & Dissertations

This thesis assesses the feasibility of utilizing a hypercube interconnect topology to link a heterogeneous processor array in a very long instruction word (VLIW) computer architecture. The research focused upon the selection of a suitable arrangement of processors for the computer and the subsequent demonstration of the architecture's capability to handle simple loop iterations. Previous attempts at VLIW computer design are summarized, the new SMIMD architecture is presented, and suggestions for future research are given. The thesis concludes with results of the initial performance evaluations of the architecture design.

System Design Quality And Efficiency Of System Analysts: An Automated Case Tool Versus A Manual Method, Satomi H. Sugishita

UNF Graduate Theses and Dissertations

The purpose of the current research study is to find out if CASE tools help to increase the software design quality and efficiency of system analysts and designers when they modify a system design document. Results of the experimental data analysis show that only the experience level of subjects had an effect on quality of their work. Results indicated that the design methods, either CASE tools or manual, do not have a significant effect on quality of the modification task nor the efficiency of system analysts and designers.

The Complexity Of Software Testing, J. Paul Myers Jr.

Computer Science Faculty Research

The futility of using a general-purpose metric to characterise 'the' complexity of a program has been argued to support the design of specific metrics for the different stages of the software life-cycle. An analysis of the module testing activity is performed, providing evidence of the absurdity of all-purpose metrics, as well as a methodical means with which to measure testing complexity. Several standard metrics are seen to serve as component measures for the intricacies of testing. The methodology is applied to compare traditional and adaptive means of testing. It is shown that previous informal arguments asserting the superiority of adaptive …

Distributed Ray Casting For High-Speed Volume Rendering, Patricia L. Brightbill

Theses and Dissertations

The volume rendering technique known as ray casting or ray tracing is notoriously slow for large volume sizes, yet provides superior images. A technique is needed to accelerate ray tracing volumes without depending on special purpose or parallel computers. The realization and improvements in distributed computing over the past two decades has motivated its use in this work. This thesis explores a technique to speedup ray casting by distributed programming. The work investigates the possibility of dividing the volume among general purpose workstations and casting rays (using Levoy's front-to-back algorithm) through each subvolume independently. The final step being the composition …

Semi-Supervised Adaptive Resonance Theory (Smart2), Christopher J. Merz, William E. Bond, Daniel C. St. Clair

Computer Science Faculty Research & Creative Works

Adaptive resonance theory (ART) algorithms represent a class of neural network architectures which self-organize stable recognition categories in response to arbitrary sequences of input patterns. The authors discuss incorporation of supervision into one of these architectures, ART2. Results of numerical experiments indicate that this new semi-supervised version of ART2 (SMART2) outperformed ART for classification problems. The results and analysis of runs on several data sets by SMART2, ART2, and backpropagation are analyzed. The test accuracy of SMART2 was similar to that of backpropagation. However, SMART2 network structures are easier to interpret than the corresponding structures produced by backpropagation.

Formation Of Clusters And Resolution Of Ordinal Attributes In Id3 Classification Trees, Chaman Sabharwal, Keith R. Hacke, Daniel C. St. Clair

Computer Science Faculty Research & Creative Works

Many learning systems have been designed to construct classification trees from a set of training examples. One of the most widely used approaches for constructing decision trees is the ID3 algorithm [Quinlan 1986]. Decision trees are ill-suited to handle attributes with ordinal values. Problems arise when a node representing an ordinal attribute has a branch for each value of the ordinal attribute in the training set. This is generally infeasible when the set of ordinal values is very large. Past approaches have sought to cluster large sets of ordinal values before the classification tree is constructed [Quinlan 1986; Lebowitz 1985; …

The A.D.E. Taxonomy Of Spreadsheet Application Development, Maria Jean Hall

Theses: Doctorates and Masters

Spreadsheets are a major application in end-user computing, one of the fastest growing areas of computing. Studies have shown that 30% of spreadsheet applications contain errors. As major decisions are often made with the assistance of spreadsheets, the control of spreadsheet applications is a matter of concern to enduser developers, managers, EDP auditors and computer professionals.

The application of appropriate controls to the spreadsheet development process requires prior categorisation of the spreadsheet application. The special-purpose A.D.E. (Application, Development, Environment) taxonomy of spreadsheet application development was evolved by mathematical taxonomic methods to categorise spreadsheet development projects to facilitate their management and …

Applying Metrics To Rule-Based Systems, Paul Doyle, Renaat Verbruggen

Other

Since the introduction of software measurement theory in the early seventies it has been accepted that in order to control software it must first be measured. Unambiguous and reproducible measurements are considered to be the most useful in controlling software productivity, costs and quality, and diverse sets of measurements are required to cover all aspects of software. This paper focuses on measures for rule-based language systems and also describes a process for developing measures for other non-standard 3GL development tools. This paper uses KEL as an example and the method allows the re-use of existing measures and indicates if and …