Digital Commons Network^™

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; …

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 …

Some Developments In Information Technology In The Irish Hotel And Catering Industry, Sean Connell, Elaine Sunderland, Ciaran Mcdonnell

Conference papers

This paper describes the current and potential future use of computers in the Hospitality Industry in Ireland. It briefly outlines two research projects which are being carried out in the Dublin College of Catering in the application of computers to the Industry.

Parallel Error Tolerance Scheme Based On The Hill Climbing Nature Of Simulated Annealing, Bruce M. Mcmillin, Chul-Eui Hong

Computer Science Faculty Research & Creative Works

In parallelizing simulated annealing in a multicomputer, maintaining the global state S involves explicit message traffic and is a critical performance bottleneck. One way to mitigate this bottleneck is to amortize the overhead of these state updates over as many parallel state changes as possible. Using this technique introduces errors in the calculated cost C(S) of a particular state S used by the annealing process. Analytically derived bounds are placed on this error in order to assure convergence to the correct result. The resulting parallel simulated annealing algorithm dynamically changes the frequency of global updates as a function of the …

Methods For Calculating Solar Position And Day Length Including Computer Programs And Subroutines, M L. Roderick

Resource management technical reports

The theory of calculating solar position is described. Using this theory, a number of computing routines are prepared in the C programming language. These routines are suitable for users who program in C, and have an ANSI compatible C compiler. These routines are fully documented, with both the underlying theory, and code particulars, and may be used as a stand alone reference. The source code has also been published in appendix B of the report.

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.

Experimentation With Proof Methods For Non-Horn Sets, Christopher J. Merz, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

Two Resolution Proof Strategies Developed by Peterson Are Implemented by Modifying Otter, an Existing Automated Theorem Prover. the Methods, Lock-T Refutation and LNL-T Refutation, Are Generalizations of Unit Refutation and Input Resolution, Respectively, to Non-Horn Sets and Represent Independent, Equivalent but Opposite Ways of Searching. the Algorithms Used Are based on a Corrected Version of the Foundational Work. the Strategies Have Been Tested on Various Non-Horn Challenge Problems from the Tarskian Geometry and the Non-Obvious Problem, with the Results Being in Some Cases Quite Favorable When Compared to Other Resolution Techniques.

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 …

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: 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: Virtual Memory Manager, Jon Inouye, Marion Hakanson, Ravi Konuru, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This document describes the port ofthe Chorus virtual memory manager to the Hewlett-Packard Precision Architecture rusc (PA-RISC) workstation. The information contained in this paper will be of interest to people who:

• intend to port the Chorus virtual memory section. • intend to port a virtual memory design to the Hewlett-Packard PA-RISC.

The reader is strongly encouraged to read the following PA-Chorus documents before reading this document:

• Technical Report CSE-92-3, Porting Chorus to the PA-RISC: Project Overview

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 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 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. …

On Hamiltonian Line Graphs, Zhi-Hong Chen

Scholarship and Professional Work - LAS

No abstract provided.

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 …

Proving Functionally Difficult Problems Through Model Generation, Richard Rankin, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

Satchmo [MA88] is a Theorem Prover Implemented in Prolog Which Attempts to Provide Satisfiability Checking through Model Generation. This Paper Gives a Brief Introduction to SATCHMO and Reports Extensions to the Original Work Which Allow SATCHMO to Solve Problems Previously Considered to Be Finitely Unprovable within the SATCHMO System. the Specific Problems Are from [PE86, MO85, LU85] and Were Designed to Convert Simple Propositional Logic Problems into Functionally Difficult First Order Problems. Although the Benefits of using the SATCHMO System Are Many, the Fact that It Could Not Offer Proofs for a Set of Problems Provable in Other Systems is …

Fault-Tolerant Concurrent Branch And Bound Algorithms Derived From Program Verification, Hanan Lutfiyya, Aggie Sun, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

An important aspect which is often overlooked in software design of distributed environments is that of fault tolerance. Many methodologies in the past have attempted to provide fault tolerance efficiently but have never been successful at eliminating explicit time and space redundancy. One approach for providing fault tolerance is through examining the behavior and properties of the application and deriving executable assertions that detect faults. Our work focuses on transforming the assertions of a verification proof of a program to executable assertions. These executable assertions may be embedded in the program to create a fault-tolerant program. It is also shown …

Executing Multidatabase Transactions, Mansoor Ansari, Marek Rusinkiewicz, Linda Ness, Amit P. Sheth

Kno.e.sis Publications

In a multidatabase environment, the traditional transaction model has been found to be too restrictive. Therefore, several extended transaction models have been proposed in which some of the requirements of transaction, such as isolation or atomicity, are optional. The authors describe one of such extensions, the flexible transaction model and discuss the scheduling of transactions involving multiple autonomous database systems managed by heterogeneous DBMS.

The scheduling algorithm for flexible transactions is implemented using L.0, a logically parallel language which provides a framework for concisely specifying the multidatabase transactions and for scheduling them. The key aspects of a flexible transaction specification, …

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 …

How To Encrypt /Usr/Dict/Words In About A Second, Peter Su, Matt Bishop

Computer Science Technical Reports

We present an implementation of the Data Encryption Standard on the Connection Machine architecture. The DES encryption algorithm is ideally suited to the Connection Machine because it consists of bit serial operations, and thousands of encryptions can be done in parallel, independently of one another. Thus, our code encrypts passwords about ten times faster than the fastest competition that we know about. In addition, the nature of the Connection Machine's architecture is such that some of the optimizations that make DES run much faster on conventional architectures have no effect on the performance of the Connection Machine. Our comparison of …

Concurrent Local Search For Fast Proximity Algorithms On Parallel And Vector Architectures, Peter Su

Computer Science Technical Reports

This paper presents a fast algorithm for solving the all-nearest-neighbors problem. The algorithm uses a data parallel style of programming which can be efficiently utilized on a variety of parallel and vector architectures [4,21,26]. I have implemented the algorithm in C on one such architecture, the Cray Y-MP. On one Cray CPU, the implementation is about 19 times faster than a fast sequential algorithm running on a Sparc workstation. The main idea in the algorithm is to divide the plane up into a fixed grid of cells, or buckets. When the points are well distributed, the algorithm processes each query …

On The De Bruijn Torus Problem, Glenn Hurlbert, Garth Isaak

Computer Science Technical Reports

A (kn;n)k-de Bruijn Cycle is a cyclic k-ary sequence with the property that every k-ary n-tuple appears exactly once contiguously on the cycle. A (kr, ks; m, n)k-de Bruijn Torus is a k-ary krXks toroidal array with the property that every k-ary m x n matrix appears exactly once contiguously on the torus. As is the case with de Bruijn cycles, the 2-dimensional version has many interesting applications, from coding and communications to pseudo-random arrays, spectral imaging, and robot self-location. J.C. Cock proved the existence of such tori for all m, n, and k, and Chung, Diaconis, and Graham asked …

Grounding Via Scanning: Cooking Up Roles From Scratch, Doug Blank, Michael Gasser

Computer Science Faculty Research and Scholarship

No abstract provided.