Physical Sciences and Mathematics Commons^™

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 …

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

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 …

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.

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.

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.

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 …

A Detailed Simulation Model Of The Hp 97560 Disk Drive, David Kotz, Song Bac Toh, Sriram Radhakrishnan

Computer Science Technical Reports

We implemented a detailed model of the HP 97560 disk drive, to replicate a model devised by Ruemmler and Wilkes (both of Hewlett-Packard, HP). Our model simulates one or more disk drives attached to one or more SCSI buses. The design is broken into three components: a test driver, the disk model itself, and the discrete-event simulation support. Thus, the disk model can be easily extracted and used in other simulation environments. We validated our model using traces obtained from HP, using the same "demerit" measure as Ruemmler and Wilkes. We obtained a demerit percentage of 3.9%, indicating that our …

A 2-3/4-Approximation Algorithm For The Shortest Superstring Problem, Chris Armen, Clifford Stein

Computer Science Technical Reports

Given a collection of strings S={s_1,...,s_n} over an alphabet Sigma, a superstring alpha of S is a string containing each s_i as a substring, that is, for each i, 1<=i<=n, alpha contains a block of |s_i| consecutive characters that match s_i exactly. The shortest superstring problem is the problem of finding a superstring alpha of minimum length. The shortest superstring problem has applications in both computational biology and data compression. The problem is NP-hard [GallantMS80]; in fact, it was recently shown to be MAX SNP-hard [BlumJLTY91]. Given the importance of the applications, several heuristics and approximation algorithms have been proposed. Constant factor approximation algorithms have been given in [BlumJLTY91] (factor of 3), [TengY93] (factor of 2-8/9), [CzumajGPR94] (factor of 2-5/6) and [KosarajuPS94] (factor of 2-50/63). Informally, the key to any algorithm for the shortest superstring problem is to identify sets of strings with large amounts of similarity, or overlap. While the previous algorithms and their analyses have grown increasingly sophisticated, they reveal remarkably little about the structure of strings with large amounts of overlap. In this sense, they are solving a more general problem than the one at hand. In this paper, we study the structure of strings with large amounts of overlap and use our understanding to give an algorithm that finds a superstring whose length is no more than 2-3/4 times that of the optimal superstring. We prove several interesting properties about short periodic strings, allowing us to answer questions of the following form: given a string with some periodic structure, characterize all the possible periodic strings that can have a large amount of overlap with the first string.

Efficiency And Stability Issues In The Numerical Computation Of Fourier Transforms And Convolutions On The 2-Sphere, D M. Healy Jr, S S. B. Moore, D Rockmore

Computer Science Technical Reports

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the sphere. In this paper we present a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. We also discuss implementational considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. This discussion is supplemented with numerical experiments from our implementation in C on a DecStation 5000. These results give strong indications that the algorithm is both reliable and efficient for a large …

Parallel Computer Needs At Dartmouth College, David Kotz, Fillia Makedon, Matt Bishop, Scot Drysdale, Don Johnson, Takis Metaxas

Computer Science Technical Reports

To determine the need for a parallel computer on campus, a committee of the Graduate Program in Computer Science surveyed selected Dartmouth College faculty and students in December, 1991, and January, 1992. We hope that the information in this report can be used by many groups on campus, including the Computer Science graduate program and DAGS summer institute, Kiewit's NH Supercomputer Initiative, and by numerous researchers hoping to collaborate with people in other disciplines.

We found significant interest in parallel supercomputing on campus. An on-campus parallel supercomputing facility would not only support numerous courses and research projects, but would provide …

Fast Greedy Triangulation Algorithms, Matthew T. Dickerson, Robert L. Scot Drysdale, Scott A. Mcelfresh, Emo Welzl

Computer Science Technical Reports

The greedy triangulation of a set $S$ of $n$ points in the plane is the triangulation obtained by starting with the empty set and at each step adding the shortest compatible edge between two of the points, where a compatible edge is defined to be an edge that crosses none of the previously added edges. In this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time $O(n \log n)$ and space $O(n)$ for points uniformly distributed over any convex shape. A variant of this algorithm should be fast for some other distributions. As part …

Quickest Paths: Faster Algorithms And Dynamization, Dimitrios Kagaris, Grammati E. Pantziou, Spyros Tragoudas, Christos D. Zaroliagis

Computer Science Technical Reports

Given a network $N=(V,E,{c},{l})$, where $G=(V,E)$, $|V|=n$ and $|E|=m$, is a directed graph, ${c}(e) > 0$ is the capacity and ${l}(e) \ge 0$ is the lead time (or delay) for each edge $e\in E$, the quickest path problem is to find a path for a given source--destination pair such that the total lead time plus the inverse of the minimum edge capacity of the path is minimal. The problem has applications to fast data transmissions in communication networks. The best previous algorithm for the single--pair quickest path problem runs in time $O(r m+r n \log n)$, where $r$ is the number …

Videoscheme: A Research, Authoring, And Teaching Tool For Multimedia, J Matthews, F Makedon, P Gloor

Computer Science Technical Reports

The availability of digital multimedia technology poses new challenges to researchers, authors, and educators, even as it creates new opportunities for rich communication. This paper suggests interactive computer programming as a fruitful approach to these challenges. VideoScheme, a prototype video programming environment, is described along with promising applications.

Efficient Sequential And Parallel Algorithms For The Negative Cycle Problem, Dimitris Kavvadias, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

We present here an algorithm for detecting (and outputting, if exists) a negative cycle in an $n$-vertex planar digraph $G$ with real edge weights. Its running time ranges from $O(n)$ up to $O(n^{1.5}\log n)$ as a certain topological measure of $G$ varies from $1$ up to $\Theta(n)$. Moreover, an efficient CREW PRAM implementation is given. Our algorithm applies also to digraphs whose genus $\gamma$ is $o(n)$.

Conference On A Disk: A Successful Experiment In Hypermedia Publishing (Extended Abstract), M Cheyney, P Gloor, D B. Johnson, F Makedon, J Matthews, P Metaxas

Computer Science Technical Reports

Academic conferences are a long-standing and effective form of multimedia communication. Conference participants can transmit and recieve information through sight, speech, gesture, text, and touch. This same-time, same-place communication is sufficiently valuable to justify large investments in time and travel funds. Printed conference proceedings are attempts to recapture the value of a life conference, but they are limited by a fragmented and inefficient approach to the problem. We addressed this problem in the multimedia proceedings of the DAGS'92 conference. The recently published CD-ROM delibers text, graphic, audio, and video information as an integrated whole, with extensive provisions for random access …

Job Scheduling In Rings, Perry Fizzano, Clifford Stein, David Karger, Joel Wein

Computer Science Technical Reports

We give distributed approximation algorithms for job scheduling in a ring architecture. In contrast to almost all other parallel scheduling models, the model we consider captures the influence of the underlying communications network by specifying that task migration from one processor to another takes time proportional to the distance between those two processors in the network. As a result, our algorithms must balance both computational load and communication time.

The algorithms are simple, require no global control, and work in a variety of settings. All come with small constant-factor approximation guarantees; the basic algorithm yields schedules of length at most …

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski

Computer Science Technical Reports

We give asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on parallel disk systems. In a BMMC permutation on N records, where N is a power of 2, each (lg N)-bit source address x maps to a corresponding (lg N)-bit target address y by the matrix equation y = Ax XOR c, where matrix multiplication is performed over GF(2). The characteristic matrix A is (lg N) x (lg N) and nonsingular over GF(2). Under the Vitter-Shriver parallel-disk model with N records, D disks, B records per block, and M …

The Design And Development Of Interactive Multimedia Conference Proceedings, Samuel A. Rebelsky, James Ford, Kenneth Harker, Fillia Makedon, P Takis Metaxas, Charles Owen

Computer Science Technical Reports

Many conferences are now providing electronic proceedings. Often, these proceedings are little more than electronic collections of documents put together in a standard software package, such as SuperBook or Acrobat. This means that few of these proceedings incorporate the full range of materials that a conference generates. Furthermore, because these general interfaces are not designed for conference proceedings, they do not provide all the features a conference warrants.

The interactive multimedia proceedings for the DAGS'92 Institute on Parallel Computation used an interface designed specifically for presenting conference materials and provided both talks (audio, video, and slides) and papers (in hypertext …

Scheduling In A Ring With Unit Capacity Links, Perry Fizzano, Clifford Stein

Computer Science Technical Reports

We consider the problem of scheduling unit-sized jobs on a ring of processors with the objective of minimizing the completion time of the last job. Unlike much previous work we place restrictions on the capacity of the network links connecting processors. We give a polynomial time centralized algorithm that produces optimal length schedules. We also give a simple distributed 2-approximation algorithm.

Vic*: A Preprocessor For Virtual-Memory C*, Thomas H. Cormen, Alex Colvin

Computer Science Technical Reports

This paper describes the functionality of ViC*, a compiler-like preprocessor for out-of-core C*. The input to ViC* is a C* program but with certain shapes declared \verb`outofcore`, which means that all parallel variables of these shapes reside on disk. The output is a standard C* program with the appropriate I/O and library calls added for efficient access to out-of-core parallel variables.