Computer Sciences Commons^™

Deciding Finiteness For Matrix Groups Over Function Fields, Robert Beals, Daniel N. Rockmore, Ki-Seng Tan

Computer Science Technical Reports

Let S be any finite subset GLn(F(t)) where F is a field. In this paper we give algorithms to decide if the group generated by S is finite. In the case of characteristic zero, slight modifications of earlier work of Babai, Beals and Rockmore [1] give polynomial time deterministic algorithms to solve this problem. The case of positive characteristic turns out to be more subtle and our algorithms depend on a structure theorem proved here, generalizing a theorem of Weil. We also present a fairly detailed analysis of the size of finite subgroups in this case and give bounds which …

Integration Methods For N-Body Problems, D. I. Okunbor

Computer Science Technical Reports

Particle simulation studies the time evolution of the dynamical state of a system of interacting particles by the computation of trajectories of particles based on the numerical integration of the Newton equations of motion. This approach is widely used in biomolecular modeling to study, for example, proteins; and in astrophysics to study gravitational N-body system. The dimension of this system of equations of motion is in the order of tens of thousands. To solve this system involves an enormous amount of computer time. Several techniques have been advanced to reduce the computational complexity of this problem. Some of which are: …

Ph.D. Thesis Proprosal: Transportable Agents, Robert S. Gray

Computer Science Technical Reports

One of the paradigms that has been suggested for allowing efficient access to remote resources is transportable agents. A transportable agent is a named program that can migrate from machine to machine in a heterogeneous network. The program chooses when and where to migrate. It can suspend its execution at an arbitrary point, transport to another machine and resume execution on the new machine. Transportable agents have several advantages over the traditional client/server model. Transportable agents consume less network bandwidth and do not require a connection between communicating machines -- this is attractive in all networks and particularly attractive in …

Software Testing Paradigms, A. Subramaniam, G. Zobrist

Computer Science Technical Reports

The development of software follows a series of steps adopted from the Classical Life Cycle approach. Amongst all the steps, Software testing demands a lot of attention considering the amount of effort applied in it. There are various techniques by which a software can be tested. A review of techniques available are discussed. A methodology that can be applied to software testing has also been suggested. This document can be used by a programmer to select the technique for software testing and also assists in providing a narrowed view to the vast number of techniques available for software testing.

Discovery Of Integrity Relationships In Relational Databases, D. Harrier, D. C. St. Clair

Computer Science Technical Reports

The use of database management system integrity constraints has been a powerful tool in raising the quality of data within an application subject database. Unfortunately, the successful use of integrity constraints requires that the database administrator has implemented the constraint before data are inserted into the database.

The results of this research provide a methodology for discovering previously unknown integrity relationships in a relational database. The methodology uses the principles of knowledge discovery from the artificial intelligence community, and Quinlan's ID3 machine learning algorithm as the discovery tool. Experimental results are provided that demonstrate how the methodology can be applied.

From Formal Security Specifications To Executable Assertions - A Distributed Systems Preliminary Study, C. Serban, B. Mcmillin

Computer Science Technical Reports

A security policy for a distributed system can be checked for compliance at run-time, as the system executes, using assertions embedded in software. This paper presents the concept of run-time security assurance, according to a given security policy for a given distributed system, along with mechanisms for its usage. A model problem illustrates the implementation of executable security assertions and their run-time validation on histories (traces) of events.

Expanding The Potential For Disk-Directed I/O, David Kotz

Computer Science Technical Reports

As parallel computers are increasingly used to run scientific applications with large data sets, and as processor speeds continue to increase, it becomes more important to provide fast, effective parallel file systems for data storage and for temporary files. In an earlier work we demonstrated that a technique we call disk-directed I/O has the potential to provide consistent high performance for large, collective, structured I/O requests. In this paper we expand on this potential by demonstrating the ability of a disk-directed I/O system to read irregular subsets of data from a file, and to filter and distribute incoming data according …

Content-Based Image Retrieval: Color And Edges, Robert S. Gray

Computer Science Technical Reports

One of the tools that will be essential for future electronic publishing is a powerful image retrieval system. The author should be able to search an image database for images that convey the desired information or mood; a reader should be able to search a corpus of published work for images that are relevant to his or her needs. Most commercial image retrieval systems associate keywords or text with each image and require the user to enter a keyword or textual description of the desired image. This text-based approach has numerous drawbacks -- associating keywords or text with each image …

Exploring The Use Of I/O Nodes For Computation In A Mimd Multiprocessor, David Kotz, Ting Cai

Computer Science Technical Reports

As parallel systems move into the production scientific computing world, the emphasis will be on cost-effective solutions that provide high throughput for a mix of applications. Cost-effective solutions demand that a system make effective use of all of its resources. Many MIMD multiprocessors today, however, distinguish between ``compute'' and ``I/O'' nodes, the latter having attached disks and being dedicated to running the file-system server. This static division of responsibilities simplifies system management but does not necessarily lead to the best performance in workloads that need a different balance of computation and I/O. Of course, computational processes sharing a node with …

Disk-Directed I/O For An Out-Of-Core Computation, David Kotz

Computer Science Technical Reports

New file systems are critical to obtain good I/O performance on large multiprocessors. Several researchers have suggested the use of collective file-system operations, in which all processes in an application cooperate in each I/O request. Others have suggested that the traditional low-level interface (read, write, seek) be augmented with various higher-level requests (e.g., read matrix), allowing the programmer to express a complex transfer in a single (perhaps collective) request. Collective, high-level requests permit techniques like two-phase I/O and disk-directed I/O to significantly improve performance over traditional file systems and interfaces. Neither of these techniques have been tested on anything other …

Parallel Algorithm Derivation And Program Transformation In A Preprocessing Compiler For Scientific Languages: The Psi Project And Hpf, L. R. Mullin, Thom Mcmahon

Computer Science Technical Reports

Scientific Programming and subsequent compilation is significantly complicated when programs are expected to perform on one or many processors for any size or dimensional problem. Scientific languages, although sophisticated and powerful, have been slow to evolve from their Von Neumann scalar by scalar operations to monolithic data parallel functions, e.g. Fortran 90/95. The structure of an array and corresponding architectural topology to which the arrays are mapped, may provide ways to increase portability and scalability of designs. This paper presents how the Psi(w) Calculus in conjunction with a useful algebra that provides convolutions, permutations, and scalar operations, is being used …

On Programming Scientific Applications In A Functional Language Extended By A \L' - Calculus Subsystem For Array Operations, L. R. Mullin, Werner Kluge

Computer Science Technical Reports

This paper discusses some of the pros and cons of extending functional languages by high-level array operations similar to those that are available in APL. This extension is based on the lp~calculus, an algebra of arrays which provides a small set of essential array operations defined in terms of dimensionalities, shapes and indexing functions. Since these operations specify context-free substitutions of array expressions by others, the lpcalculus fits perfectly into a functional programming paradigm.

In order to demonstrate the programming techniques made possible by the lp-calculus, we study a functional program for the approximation of numerical solutions of partial differential …

Dartcvl: The Dartmouth C Vector Library, Thomas H. Cormen, Sumit Chawla, Preston Crow, Melissa Hirschl, Roberto Hoyle, Keith D. Kotay, Rolf H. Nelson, Nils Nieuwejaar, Scott M. Silver, Michael B. Taylor, Rajiv Wickremesinghe

Computer Science Technical Reports

As a class project, we implemented a version of CVL, the C Vector Library, on a DECmpp 12000/Sx 2000, which is equivalent to the MasPar MP-2 massively parallel computer. We compare our implementation, DartCVL, to the University of North Carolina implementation, UnCvl.

DartCVL was designed for the MP-2 architecture and UnCvl was designed for the MP-1. Because the MasPar MP-1 and MP-2 are functionally equivalent, both DartCVL and UnCvl will run on either. Differences in the designs of the two machines, however, may lead to different software design decisions. DartCVL differs from UnCvl in two key ways. First, DartCVL uses …

Program Modeling And Control Synthesis For Robotic Manipulators, Ramiz N. Ballou, Arlan R. Dekock, David D. Ardayfio

Computer Science Technical Reports

The control and programming methodology of industrial robots is becoming increasingly important. The speed and accuracy of data generation, and the performance of the robot are considered the most important factors in robotics control. This paper presents and discusses algorithms that solve for the inverse solution for a given point in space at a very high speed based on the top down abstract method. The algorithms are independent of any specific type of manipulator configuration or programming language. The algorithms were implemented for the IBM-PC™ using the FORTRAN language to control the Armdroid™ robot. The program generates 500 sets of …

A New Approach To Automatic Target Recognition Using Wavelet Transforms, Anitha Panapakkam, S. N. Balakrishnan, Daniel St. Clair

Computer Science Technical Reports

Automatic Target Recognition (ATR) systems have significant impact in defense applications. There is a continuing need to develop new and robust techniques to handle the increasingly complex ATR problem. The objectives of this thesis are two-fold. First a new technique to be used for ATR is developed and secondly an integrated ATR system to investigate and combine all subsystems is developed. In this thesis, we have developed a new technique for the feature extraction stage of ATR problem using wavelet transforms. Wavelet transforms have been one of the widely investigated areas of research in the past few years. The promising …

Performance Monitoring Of Hybrid Intelligent Systems, Nariman Abdel Baky, Fikret Ercal

Computer Science Technical Reports

Development of an automated system to enable the ongoing monitoring and control of the performance of HIS is a step towards increasing the confidence and security with which ordinary users will perceive AI-based Systems. The main objective of this research was to develop a prototype intelligent system to perform this monitoring. The proposed monitming system integrates performance metrics for the HIS's components with heuristics for evaluating data quality by checking data types, data ranges, percentage of missing data and the composition of data. The research demonstrated the possibility of developing such system and the feasibility of using it for a …

Ccsp - A Formal System For Distributed Program Debugging, Hanan Lutfiyya, Bruce Mcmillin, Beth Arrowsmith, Cristina Serban

Computer Science Technical Reports

One major problem with programming in a parallel/distributed environment is the difficulty in debugging the programs owing to the complex interactions of their component processes. Complete knowledge of the program's state is not generally attainable in a distributed system. This paper presents a distributed system for debugging distributed programs that allows for the execution and evaluation of embedded assertions expressed in Hoare's CSP [6]. We show examples of the use of this system, prove its correctness, and describe how the system can be used for the more general case of ensuring an application's correctness at run-time.

Disk-Directed I/O For Mimd Multiprocessors, David Kotz

Computer Science Technical Reports

Many scientific applications that run on today's multiprocessors are bottlenecked by their file I/O needs. Even if the multiprocessor is configured with sufficient I/O hardware, the file-system software often fails to provide the available bandwidth to the application. Although libraries and improved file-system interfaces can make a significant improvement, we believe that fundamental changes are needed in the file-server software. We propose a new technique, disk-directed I/O, that flips the usual relationship between server and client to allow the disks (actually, disk servers) to determine the flow of data for maximum performance. Our simulations show that tremendous performance gains are …

A Data-Parallel Programming Library For Education (Dapple), David Kotz

Computer Science Technical Reports

In the context of our overall goal to bring the concepts of parallel computing into the undergraduate curriculum, we set out to find a parallel-programming language for student use. To make it accessible to students at all levels, and to be independent of any particular hardware platform, we chose to design our own language, based on a data-parallel model and on C++. The result, DAPPLE, is a C++ class library designed to provide the illusion of a data-parallel programming language on conventional hardware and with conventional compilers. DAPPLE defines Vectors and Matrices as basic classes, with all the usual C++ …

Distributed Scheduling In Finite Capacity Networks, Perry Fizzano, Clifford Stein

Computer Science Technical Reports

We consider the problem of scheduling unit-sized jobs in a distributed network of processors. Each processor only knows the number of jobs it and its neighbors have. We give an analysis of intuitive algorithm and prove that the algorithm produces schedules that are within a logarithmic factor of the length of the optimal schedule given that the optimal schedule is sufficiently long.

Building Multimedia Proceedings: The Roles Of Video In Interactive Electronic Conference Proceedings, Samuel A. Rebelsky, Fillia Makedon, James Matthews, Charles Owen, Laura Bright, Kenneth Harker, Nancy Toth

Computer Science Technical Reports

Modern computer systems have changed the way that conference proceedings can be presented and archived. No longer are researchers limited by printed text; electronic proceedings allow one to search the proceedings, add and share annotations, and create paths of related concepts through the proceedings. These additional capabilities extend the opportunities and benefit the thought processes of actual conference participants and the new virtual participants who experience the conference through the electronic proceedings.

In this paper, we discuss the construction of electronic conference proceedings, highlighting the role of talks and other presentations (and, particularly, the audio and video of these talks …

Incremental Equational Programming, Samuel A. Rebelsky

Computer Science Technical Reports

This paper extends Equational Programming (EP)—a declarative, symbolic programming language—to allow programs to manipulate incrementally defined and modified input terms and to avoid repeated work when evaluating these incremental terms. This paper represents two key aspects of this extension: a notation for representing revision and a modification to EP's runtime library to accomodate this notation. Unlike Field's method of incremental term rewriting, which is designed for more general but less efficient term-rewriting systems, this paper's method accomodates EP's restrictions (in particular, EP's decision to disallow overlapping rules) so that it may take advantage of EP's speed.

R-By-C Crozzle: An Np-Hard Problem, Michelle Gower, Ralph Wilkerson

Computer Science Technical Reports

In an Auslralian magazine, a monetary prize is awarded to the person with the best answer to a word puzzle called a Crozzle. Each valid placement of given words into a 10x 15 grid is given a score, and the best answer is the placement with the largest score. Various search techniques have been utilized lo solve this problem. No one has shown whether there is a polynomial-time algorithm to find the best Crozzle. This paper proves that the Crozzle is in NP. It also creates a similar word puzzle, called R-by-C Crozzle, by lifting the constraint on the grid …

Hypergraph Partitioning Algorithms, Tom Leighton, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

We present the first polynomial time approximation algorithms for the balanced hypergraph partitioning problem. The approximations are within polylogarithmic factors of the optimal solutions. The choice of algorithm involves a time complexity/approximation bound tradeoff. We employ a two step methodology. First we approximate the flux of the input hypergraph. This involves an approximate solution to a concurrent flow problem on the hypergraph. In the second step we use the approximate flux to obtain approximations for the balanced bipartitioning problem. Our results extend the approximation algorithms by Leighton-Rao on graphs to hypergraphs. We also give the first polylogarithmic times optimal approximation …

A Multiprocessor Extension To The Conventional File System Interface, Nils Nieuwejaar, David Kotz

Computer Science Technical Reports

As the I/O needs of parallel scientific applications increase, file systems for multiprocessors are being designed to provide applications with parallel access to multiple disks. Many parallel file systems present applications with a conventional Unix-like interface that allows the application to access multiple disks transparently. By tracing all the activity of a parallel file system in a production, scientific computing environment, we show that many applications exhibit highly regular, but non-consecutive I/O access patterns. Since the conventional interface does not provide an efficient method of describing these patterns, we present an extension which supports strided and nested-strided I/O requests.

Eighth-Order Explicit Symplecticrunge-Kutta-Nyström Integrators, Daniel I. Okunbor, Eric J. Lu

Computer Science Technical Reports

We consider the solution of Hamiltonian dynamical systems by constructing eighth-order explicit symplectic Runge-Kutta-Nyström integrators. The application of highorder integrators may be important in areas such as in astronomy. They require large number of function evaluations, which make them computationally expensive and easily susceptible to errors. The integrators developed in this paper require 17 function evaluations as opposed to the 26-stage (effectively 24) eighth-order explicit symplectic Runge-Kutta-Nyström method derived by Calvo and Sanz-Serna. Numerical tests using the 2-Body and the sine-Gordon problems indicate that our methods are comparable to that of Calvo and Sanz-Serna and Yoshida.

A New Approach To The Minumum Cut Problem, David R. Karger, Clifford Stein

Computer Science Technical Reports

No abstract provided.

Dynamic File-Access Characteristics Of A Production Parallel Scientific Workload, David Kotz, Nils Nieuwejaar

Computer Science Technical Reports

Multiprocessors have permitted astounding increases in computational performance, but many cannot meet the intense I/O requirements of some scientific applications. An important component of any solution to this I/O bottleneck is a parallel file system that can provide high-bandwidth access to tremendous amounts of data in parallel to hundreds or thousands of processors. Most successful systems are based on a solid understanding of the characteristics of the expected workload, but until now there have been no comprehensive workload characterizations of multiprocessor file systems. We began the CHARISMA project in an attempt to fill that gap. We instrumented the common node …

How To Program In Ccsp, Beth Arrowsmith

Computer Science Technical Reports

No abstract provided.

Teaching The Practice Of Formal Methods In Distributed Computing Systems - A Module, Beth Arrowsmith, Bruce Mcmillin

Computer Science Technical Reports

No abstract provided.