Computer Sciences Commons^™

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.

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 …

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 …

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.

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 …

Generalized Ffts - A Survey Of Some Recent Results, David K. Maslen, Daniel N. Rockmore

Dartmouth Scholarship

In this paper we survey some recent work directed towards generalizing the fast Fourier transform (FFT). We work primarily from the point of view of group representation theory. In this setting the classical FFT can be viewed as a family of efficient algorithms for computing the Fourier transform of either a function defined on a finite abelian group, or a bandlimited function on a compact abelian group. We discuss generalizations of the FFT to arbitrary finite groups and compact Lie groups.

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.

Issues And Obstacles With Multimedia Authoring, Fillia Makedon, Samuel A. Rebelsky, Matthew Cheyney, Charles Owen, Peter Gloor

Dartmouth Scholarship

Unlike traditional authoring, multimedia authoring involves making hard choices, forecasting technological evolution and adapting to software and hardware technology changes. It is, perhaps, an unstable field of endeavor for an academic to be in. Yet, it is important that academics are, in fact, part of this process. This paper discusses some of the common threads shared by three dissimilar cases of multimedia authoring which we have experimented with, that of multimedia conference proceedings, multimedia courseware development and multimedia information kiosks. We consider these applications from an academic point of view and review the benefits and pitfalls of academic development while …

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

Dartmouth Scholarship

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, \em 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 …

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the input). For …

On-Line And Dynamic Shortest Paths Through Graph Decompositions, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

Computer Science Technical Reports

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our …

Parallel Max Cut Approximations, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove …

Wavelet Localization Of The Radon Transform, Tim Olson, Joe Destefano

Computer Science Technical Reports

In this paper we develop an algorithm which significantly reduces radiation exposure in x-ray tomography, when a local region of the body is to be imaged. The algorithm uses the properties of wavelets to essentially localize the Radon transform. The algorithm differs from previous algorithms for doing local tomography because it recovers an approximation to the original image, not the image modulo the nullspace of the local tomography operator, or the Lambda transform of the image. This is possible because we do not truly invert the interior Radon transform, but rather sample the Radon transform sparsely away from the local …

Off-Line Cursive Handwriting Recognition Using Style Parameters, Berrin A. Yanikoglu, Peter A. Sandon

Computer Science Technical Reports

We present a system for recognizing off-line cursive English text, guided in part by global characteristics of the handwriting. A new method for finding the letter boundaries, based on minimizing a heuristic cost function, is introduced. The function is evaluated at each point along the baseline of the word to find the best possible segmentation points. The algorithm tries to find all the actual letter boundaries and as few additional ones as possible. After size and slant normalizations, the segments are classified by a one hidden layer feedforward neural network. The word recognition algorithm finds the segmentation points that are …

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Dartmouth Scholarship

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present for the first time a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, and turning off parity, file caching, and prefetching. We summarize recent theoretical and empirical work that justifies the need for these capabilities. In addition, we sketch an organization for a parallel file …

Throughput Of Existing Multiprocessor File Systems (An Informal Study), David Kotz

Computer Science Technical Reports

Fast file systems are critical for high-performance scientific computing, since many scientific applications have tremendous I/O requirements. Many parallel supercomputers have only recently obtained fully parallel I/O architectures and file systems, which are necessary for scalable I/O performance. Scalability aside, I show here that many systems lack sufficient absolute performance. I do this by surveying the performance reported in the literature, summarized in an informal table.

Accurate Verification Of Five-Axis Numerically Controlled Machining, Jerome L. Quinn

Dartmouth College Ph.D Dissertations

Current automated machining systems are composed of a number of components to aid in bringing a surface from design to physical completion. Numerically controlled (NC) milling machines are used to cut parts out of stock. Programming these machines to cut a desired surface is still largely a matter of experienced human participation. Therefore, the need exists to verify that tool programs produce the desired part.

We present recent developments in the verification of NC tool programs. Many of these methods rely on approximating the stock material as vectors whose lengths reflect the amount of uncut material at any point. This …

Efficient Parallel Algorithms For Some Tree Layout Problems, J Diaz, A Gibbons, Grammati E. Pantziou, M Serna, Paul G. Spirakis, J Toran

Computer Science Technical Reports

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two algorithms in NC. The first solves the minimum length linear arrangement problem for unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM processors. The second algorithm solves the minimum cut arrangement for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and $O(n^2 /\log n)$ CREW PRAM processors.

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Computer Science Technical Reports

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

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

Computer Science Technical Reports

No abstract provided.

Vector Layout In Virtual-Memory Systems For Data-Parallel Computing, Thomas H. Cormen

Computer Science Technical Reports

In a data-parallel computer with virtual memory, the way in which vectors are laid out on the disk system affects the performance of data-parallel operations. We present a general method of vector layout called banded layout, in which we divide a vector into bands of a number of consecutive vector elements laid out in column-major order, and we analyze the effect of the band size on the major classes of data-parallel operations. We find that although the best band size varies among the operations, choosing fairly small band sizes—at most a track—works well in general.

Videoscheme: A Programmable Video Editing System For Automation And Media Recognition, James Matthews, Peter Gloor, Fillia Makedon

Computer Science Technical Reports

The recent development of powerful, inexpensive hardware and software support had made digital video editing possible on personal computers and workstations. To date the video editing application category has been dominated by visual, easy-to-use, direct manipulation interfaces. These systems bring high-bandwidth human-computer interaction to a task formerly characterized by slow, inflexible, indirectly-operated machines. However, the direct manipulation computer interfaces are limited by their manual nature, and can not easily accommodate algorithmically- defined operations. This paper proposes a melding of the common direct manipulation interfaces with a programming language which we have enhanced to manipulate digital audio and video. The result …

Practical Prefetching Techniques For Multiprocessor File Systems, David Kotz, Carla Schlatter Ellis

Dartmouth Scholarship

Improvements in the processing speed of multiprocessors are outpacing improvements in the speed of disk hardware. Parallel disk I/O subsystems have been proposed as one way to close the gap between processor and disk speeds. In a previous paper we showed that prefetching and caching have the potential to deliver the performance benefits of parallel file systems to parallel applications. In this paper we describe experiments with practical prefetching policies that base decisions only on on-line reference history, and that can be implemented efficiently. We also test the ability of these policies across a range of architectural parameters.

Multiprocessor File System Interfaces, David Kotz

Dartmouth Scholarship

Increasingly, file systems for multiprocessors are designed with parallel access to multiple disks, to keep I/O from becoming a serious bottleneck for parallel applications. Although file system software can transparently provide high-performance access to parallel disks, a new file system interface is needed to facilitate parallel access to a file from a parallel application. We describe the difficulties faced when using the conventional (Unix-like) interface in parallel applications, and then outline ways to extend the conventional interface to provide convenient access to the file for parallel programs, while retaining the traditional interface for programs that have no need for explicitly …

Building Segment Trees In Parallel, Peter Su, Scot Drysdale

Computer Science Technical Reports

The segment tree is a simple and important data structure in computational geometry [7,11]. We present an experimental study of parallel algorithms for building segment trees. We analyze the algorithms in the context of both the PRAM (Parallel Random Access Machine) and hypercube architectures. In addition, we present performance data for implementations developed on the Connection Machine. We compare two different parallel alforitms, and we also compare our parallel algorithms to a good sequential algorithm for doing the same job. In this way, we evaluate the overall efficiency of our parallel methods. Our performance results illustrates the problems involved in …

Algorithms For Closest Point Problems: Practice And Theory, Peter Su

Computer Science Technical Reports

This paper describes and evaluates know sequential algorithms for constructing planar Voronoi diagrams and Delaunay triangulations. In addition, it describes a new incremental algorithm which is simple to understand and implement, but whose performance is competitive with all known methods. The experiments in this paper are more than just simple benchmarks, they evaluate the expected performance of the algorithms in a precise and machine independent fashion. Thus, the paper also illustrates how to use experimental tools to both understand the behaviour of different algorithms and to guide the algorithm design process.

Formal Implementation Of High-Level Languages For Data-Parallel Programming, Deb Banerjee

Dartmouth College Ph.D Dissertations

The success of parallel architectures has been limited by the lack of high-level parallel programming languages and useful programming models. The data-parallel model of programming has been demonstrated to be useful and natural on a wide variet of parallel architectures. This dissertation presents a set of formal techniques for compiling high- level languages based on data-parallelism.

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 …

Multiprocessor File System Interfaces, David Kotz

Dartmouth Scholarship

MIMD multiprocessors are increasingly used for production super-computing. Supercomputer applications often have tremendous file I/O requirements. Although newer I/O sub-systems, which attach multiple disks to the multiprocessor, permit parallel file access, file system software often has insufficient support for parallel access to the parallel disks, which is necessary for scalable performance. Most existing multiprocessor file systems are based on the conventional file system interface (which has operations like open, close, read, write, and seek). Although this provides the familiar file abstraction, it is difficult to use for parallel access to a file. Scalable applications must cooperate to read or write …