Computer Sciences Commons^™

Market-Based Resource Control For Mobile Agents, Jonathan Bredin, David Kotz, Daniela Rus

Computer Science Technical Reports

Mobile agents are programs that can migrate from machine to machine in a heterogeneous, partially disconnected network. As mobile agents move across a network, they consume resources. We discuss a system for controlling the activities of mobile agents that uses electronic cash, a banking system, and a set of resource managers. We describe protocols for transactions between agents. We present fixed-pricing and dynamic-pricing policies for resources. We focus on and analyze the sealed-bid second-price auction as a mechanism for dynamic pricing.

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

Computer Science Technical Reports

This paper describes the functionality of ViC*, a compiler for a variant of the data-parallel language C* with support for out-of-core data. The compiler translates C* programs with shapes declared outofcore, which describe parallel data stored on disk. The compiler output is a SPMD-style program in standard C with I/O and library calls added to efficiently access out-of-core parallel data. The ViC* compiler also applies several program transformations to improve out-of-core data layout and access.

Computing Dense Clusters On-Line For Information Organization, Javed Aslam, Katya Pelekhov, Daniela Rus

Computer Science Technical Reports

We present and analyze the off-line star algorithm for clustering static information systems and the on-line star algorithm for clustering dynamic information systems. These algorithms partition a document collection into a number of clusters that is naturally induced by the collection. We show a lower bound on the accuracy of the clusters produced by these algorithms. We use the random graph model to show that both star algorithms produce correct clusters in time Theta(V + E). Finally, we provide data from extensive experiments.

Approximating Disjoint-Path Problems Using Greedy Algorithms And Packing Integer Programs, Stavros G. Kolliopoulos, Clifford Stein

Computer Science Technical Reports

In the edge(vertex)-disjoint path problem we are given a graph $G$ and a set ${\cal T}$ of connection requests. Every connection request in ${\cal T}$ is a vertex pair $(s_i,t_i),$ $1 \leq i \leq K.$ The objective is to connect a maximum number of the pairs via edge(vertex)-disjoint paths. The edge-disjoint path problem can be generalized to the multiple-source unsplittable flow problem where connection request $i$ has a demand $\rho_i$ and every edge $e$ a capacity $u_e.$ All these problems are NP-hard and have a multitude of applications in areas such as routing, scheduling and bin packing. Given the hardness …

Performing Out-Of-Core Ffts On Parallel Disk Systems, Thomas H. Cormen, David M. Nicol

Computer Science Technical Reports

The Fast Fourier Transform (FFT) plays a key role in many areas of computational science and engineering. Although most one-dimensional FFT problems can be solved entirely in main memory, some important classes of applications require out-of-core techniques. For these, use of parallel I/O systems can improve performance considerably. This paper shows how to perform one-dimensional FFTs using a parallel disk system with independent disk accesses. We present both analytical and experimental results for performing out-of-core FFTs in two ways: using traditional virtual memory with demand paging, and using a provably asymptotically optimal algorithm for the Parallel Disk Model (PDM) of …

Generating, Visualizing And Evaluating High Quality Clusters For Information Organization, Javed Aslam, Katya Pelekhov, Daniela Rus

Computer Science Technical Reports

We present and analyze the star clustering algorithm. We discuss an implementation of this algorithm that supports browsing and document retrieval through information organization. We define three parameters for evaluating a clustering algorithm to measure the topic separation and topic aggregation achieved by the algorithm. In the absence of benchmarks, we present a method for randomly generating clustering data. Data from our user study shows evidence that the star algorithm is effective for organizing information.

Multimedia Data Analysis Using Imagetcl (Extended Version), Charles B. Owen, Fillia Makedon

Computer Science Technical Reports

ImageTcl is an new system which provides powerful Tcl/Tk based media scripting capabilities similar to those of the ViewSystem and Rivl in a unique environment that allows rapid prototyping and development of new components in the C++ language. Powerful user tools automate the creation of new components as well as the addition of new data types and file formats. Applications using ImageTcl at the Dartmouth Experimental Visualization Laboratory (DEVLAB) include multiple stream media data analysis, automatic image annotation, and image sequence motion analysis. ImageTcl combines the high speed of compiled languages with the testing and parameterization advantages of scripting languages.

Multiple Media Stream Data Analysis: Theory And Applications (Extended Version), Charles B. Owen, Fillia Makedon

Computer Science Technical Reports

This paper presents a new model for multiple media stream data analysis as well as descriptions of some applications of this model in development at Dartmouth College. This model formalizes the exploitation of correlations between multiple, potentially heterogeneous, media streams in support of numerous application areas. The goal of the technique is to determine temporal and spatial alignments which optimize a correlation function and indicate commonality and synchronization between media streams. It also provides a framework for comparison of media in unrelated domains. Applications such as text-to-speech alignment, functional magnetic resonance imaging, speaker localization, and degraded media realignment are described.

On-Line File Caching, Neal E. Young

Computer Science Technical Reports

Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost, maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache, pay the retrieval cost, and choose files to remove from the cache so that the total size of files in the cache is at most k. This problem generalizes previous paging and caching problems by allowing objects of arbitrary …

Performing Bmmc Permutations Efficiently On Distributed-Memory Multiprocessors With Mpi, Thomas H. Cormen

Computer Science Technical Reports

This paper presents an architecture-independent method for performing BMMC permutations on multiprocessors with distributed memory. All interprocessor communication uses the MPI function MPI_Sendrecv_replace(). The number of elements and number of processors must be powers of 2, with at least one element per processor, and there is no inherent upper bound on the ratio of elements per processor. Our method transmits only data without transmitting any source or target indices, which conserves network bandwidth. When data is transmitted, the source and target processors implicitly agree on each other's identity and the indices of the elements being transmitted. A C-callable implementation of …

A Split-Phase Interface For Parallel File Systems, Sanjay Khanna, David Kotz

Computer Science Technical Reports

We describe the effects of a new user-level library for the Galley Parallel File System. This library allows some pre-existing sequential programs to make use of the Galley Parallel File System with minimal modification. It permits programs to efficiently use the parallel file system because the user-level library groups accesses together. We examine the performance of our library, and we show how code needs to be modified to use the library.

On The Power Of Multi-Objects, Prasad Jayanti, Sanjay Khanna

Computer Science Technical Reports

In the standard ``single-object'' model of shared-memory computing, it is assumed that a process accesses at most one shared object in each of its steps. In this paper, we consider a more powerful variant---the ``multi-object'' model---in which each process may access *any* finite number of shared objects atomically in each of its steps. We present results that relate the synchronization power of a type in the multi-object model to its synchronization power in the single-object model. Although the types fetch&add and swap have the same synchronization power in the single-object model, Afek, Merritt, and Taubenfeld showed that their synchronization powers …

Agdb: A Debugger For Agent Tcl, Melissa Hirschl, David Kotz

Computer Science Technical Reports

The Agent Tcl language is an extension of Tcl/Tk that supports distributed programming in the form of transportable agents. AGDB is a debugger for the Agent Tcl language. AGDB mixes of traditional and distributed debugging facilities. Traditional debugging features include breakpoints (line-specific, conditional, and once-only), watch conditions and variables, and interrupts. Distributed-debugging features address issues inherent in distributed programming such as migration and communication. These capabilities make debugging distributed programs difficult because they add complexities like race conditions to the set of problems a program can encounter. This paper discusses how AGDB uses distributed debugging features to debug agents.

Automatic Video Pause Detection Filter, Xiaowen Liu, Charles B. Owen, Fillia S. Makedon

Computer Science Technical Reports

Increasing interest in multimedia research has been drawn upon the development of video indexing and content-based image retrieval techniques. In this report, we proposed several pause detection algorithms, which instead of searching for significant visual transitions, the algorithms detect significant pauses in video streams. A realization of the algorithms was implemented using ImageTcl toolkit developed at Dartmouth Experimental Visualization Laboratory. In addition to proposing and studying the effectiveness of the pause detection algorithms, another major goal will be to incorporate our algorithms into ImageTcl and test the stability and applicability of the ImageTcl environment. Priliminary experiments showed relatively good results …

Asml: Automatic Site Markup Language 1.03, Charles B. Owen, Fillia Makedon, Glen Frank, Michael Kenyon

Computer Science Technical Reports

Creation of large and complex World Wide Web sites is hampered by the "page at a time" approach of many tools and the programming knowledge and custom software development required for automated solutions. This report describes the development of the Automatic Site Markup Language (ASML). ASML is a new markup language designed to produce large, complicated web sites which can include dynamic content. ASML extends HTML with new, high-level features while still preserving complete compatibility with common browser and server technologies. It has powerful indexing and searching facilities, and enables the automatic translation of document formats. Most importantly, ASML provides …

An Efficient Scheme For A Distributed Video Retrieval System For Remote Users, Fillia Makedon, James Matthews, Charles Owen, Samuel Rebelsky

Computer Science Technical Reports

The new era of digital video and multimedia technologies has created the potential for large libraries of digital video. With this new technology come the challenges of creating usable means by which such large and diverse depositories of digital information (digital libraries) can be efficiently queried and accessed so that (a) the response is fast, (b) the communication over the Internet is minimal and (c) the retrieval is characterized by high precision and recall. In this paper we discuss how existing digital video editing tools, together with data compression techniques, can be combined to create a fast, accurate and cost …

Automated Parallelization Of Discrete State-Space Generation, David M. Nicol, Gianfranco Ciardo

Computer Science Technical Reports

We consider the problem of generating a large state-space in a distributed fashion. Unlike previously proposed solutions that partition the set of reachable states according to a hashing function provided by the user, we explore heuristic methods that completely automate the process. The first step is an initial random walk through the state space to initialize a search tree, duplicated in each processor. Then, the reachability graph is built in a distributed way, using the search tree to assign each newly found state to classes assigned to the available processors. Furthermore, we explore two remapping criteria that attempt to balance …

Multiprocessor Out-Of-Core Ffts With Distributed Memory And Parallel Disks, Thomas H. Cormen, Jake Wegmann, David M. Nicol

Computer Science Technical Reports

This paper extends an earlier out-of-core Fast Fourier Transform (FFT) method for a uniprocessor with the Parallel Disk Model (PDM) to use multiple processors. Four out-of-core multiprocessor methods are examined. Operationally, these methods differ in the size of "mini-butterfly" computed in memory and how the data are organized on the disks and in the distributed memory of the multiprocessor. The methods also perform differing amounts of I/O and communication. Two of them have the remarkable property that even though they are computing the FFT on a multiprocessor, all interprocessor communication occurs outside the mini-butterfly computations. Performance results on a small …

Cross-Input Amortization Captures The Diffuse Adversary, Neal E. Young

Computer Science Technical Reports

Koutsoupias and Papadimitriou recently raised the question of how well deterministic on-line paging algorithms can do against a certain class of adversarially biased random inputs. Such an input is given in an on-line fashion; the adversary determines the next request probabilistically, subject to the constraint that no page may be requested with probability more than a fixed $\epsilon>0$. In this paper, we answer their question by estimating, within a factor of two, the optimal competitive ratio of any deterministic on-line strategy against this adversary. We further analyze randomized on-line strategies, obtaining upper and lower bounds within a factor of …

Efficient Parallel Algorithms On Reconfigurable Mesh Architectures, His-Chieh Lee, Fikret Ercal

Computer Science Technical Reports

This dissertation describes a number of novel parallel algorithms for solving maze-routing problems and string matching problems on a proposed reconfigurable mesh architecture.

Section I reviews the field of reconfigurable parallel computing. This includes an introduction to a number of reconfigurable architectures proposed in the literature and a list of references to the current literature on algorithms in the field of reconfigurable computing.

Section II presents a number of time-efficient algorithms to solve the mazerouting problem. Maze-routing algorithms are used in VLSI routing and robot path planning. In that section, definitions for absolute shortest path (ASP), shortest duplex-path (SDP), shortest …

Parallel Fast Multipole Algorithms For N-Body Simulations, Jui-Lin Lu, Daniel Okunbor

Computer Science Technical Reports

The computer simulation of N-Body problems has a wide range of applications. It is known that simulations can take years to complete. This can be greatly improved by using efficient algorithms in force calculations and in applying the computing power of parallel computers to the problem. A tremendous amount of work has been devoted to parallelization of the fast multipole algorithm (FMA) which is one of the fastest algorithms in force calculations. However, most parallel implementations target a specific machine. We developed an efficient communication scheme for parallel FMA in a message passing environment and implemented it by using Message …

The Dark Side Of Risk (What Your Mother Never Told You About Time Warp), David M. Nicol, Xiaowen Liu

Computer Science Technical Reports

This paper is a reminder of the danger of allowing ``risk'' when synchronizing a parallel discrete-event simulation: a simulation code that runs correctly on a serial machine may, when run in parallel, fail catastrophically. This can happen when Time Warp presents an ``inconsistent'' message to an LP, a message that makes absolutely no sense given the LP's state. Failure may result if the simulation modeler did not anticipate the possibility of this inconsistency. While the problem is not new, there has been little discussion of how to deal with it; furthermore the problem may not be evident to new users …

A Critique Of The Telecommunications Description Language (Ted), Brian J. Premore, David M. Nicol, Xiaowen Liu

Computer Science Technical Reports

TeD is an object-oriented description language designed to facilitate the modeling of large scale telecommunication networks, with simulation on parallel and distributed platforms. TeD models are mapped to the Georgia Tech Time Warp engine (GTW) for execution. In this paper we outline the features of TeD, pointing out its strengths and identifying characteristics that gave us trouble as we used TeD to model detailed networks. Our issues are motivated specifically by a model of TCP and a model of multicast resource allocation. Our intention is to illustrate by example what TeD can do, and characteristics that a potential TeD user …

Applications Of Parallel I/O, David Kotz

Computer Science Technical Reports

Scientific applications are increasingly being implemented on massively parallel supercomputers. Many of these applications have intense I/O demands, as well as massive computational requirements. This paper is essentially an annotated bibliography of papers and other sources of information about scientific applications using parallel I/O. It will be updated periodically.

Tuning Starfish, David Kotz

Computer Science Technical Reports

STARFISH is a parallel file-system simulator we built for our research into the concept of disk-directed I/O. In this report, we detail steps taken to tune the file systems supported by STARFISH, which include a traditional parallel file system (with caching) and a disk-directed I/O system. In particular, we now support two-phase I/O, use smarter disk scheduling, increased the maximum number of outstanding requests that a compute processor may make to each disk, and added gather/scatter block transfer. We also present results of the experiments driving the tuning effort.

A Fast Parallel Implementation Of The Wavelet Packet Best Basis Algorithm On The Mp-2 For Real-Time Mri, Sumit Chawla, Dennis M. Healy Jr

Computer Science Technical Reports

Adaptive signal representations such as those determined by best-basis type algorithms have found extensive application in image processing, although their use in real-time applications may be limited by the complexity of the algorithm. In contrast to the wavelet transform which can be computed in O(n) time, the full wavelet packet expansion required for the standard best basis search takes O(n log n) time to compute. In the parallel world, however, both transforms take O(log n) to compute when the number of processors equal the number of data elements, making the wavelet packet expansion attractive to implement. This note describes near …

Early Experiences In Evaluating The Parallel Disk Model With The Vic* Implementation, Thomas H. Cormen, Melissa Hirschl

Computer Science Technical Reports

Although several algorithms have been developed for the Parallel Disk Model (PDM), few have been implemented. Consequently, little has been known about the accuracy of the PDM in measuring I/O time and total time to perform an out-of-core computation. This paper analyzes timing results on a uniprocessor with several disks for two PDM algorithms, out-of-core radix sort and BMMC permutations, to determine the strengths and weaknesses of the PDM. The results indicate the following. First, good PDM algorithms are usually not I/O bound. Second, of the four PDM parameters, two (problem size and memory size) are good indicators of I/O …

A Declarative Approach To Understanding Program Behavior Through Program Visualization, Aggie Yee-Chun Sun, Bruce M. Mcmillin

Computer Science Technical Reports

A method is proposed to analyze the behavior of sequential algorithms. Most current methodologies are in the form of semantic analysis, domain decomposition or fixed point approximation. These tools, though useful in design, verification and testing, are not general enough to characterize the behavior at run-time without the aid of a correct set of specifications. In addition, a thorough understanding of the program and of the mathematical notations are necessary to use these tools effectively. The methodology described in this thesis is a general purpose tool which addresses and alleviates the problem of having to be an applications expert by …

Efficient String Matching Algorithms On Reconfigurable Mesh Architectures, His-Chieh Lee, Fikret Ercal

Computer Science Technical Reports

String matching problem received much attention over the years due to its importance in various applications such as text/file comparison, DNA sequencing, search engines, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of textual information presented on the world wide web and the research on DNA sequencing, this problem deserves special attention and any algorithmic or hardware improvements to speed up the process will benefit these important applications.

In this paper, we present three algorithms for string matching on reconfigurable mesh architectures. Given a text T of length n and a pattern P of …

Fast Algorithms For Maze Routing On An Rmesh, Fikret Ercal, H. C. Lee

Computer Science Technical Reports

The routing problem is one of the most widely studied problems in VLSI design. Mazerouting algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on Lee's algorithm is poor. In this paper, we propose time-efficient algorithms to solve the maze-routing problem on a reconfigurable mesh architecture. The constant-time algorithms presented include: (i) testing the existence of specific types of paths between two terminals, (ii) finding an absolute shortest path (ASP) and a shortest duplex-path (SDP). In addition, fast algorithms are presented for finding the shortest triplex-path (STP) and …