Computer Sciences Commons^™

An Implementation Of The Vesta Parallel File System Api On The Galley Parallel File System, Matthew P. Carter, David Kotz

Computer Science Technical Reports

To demonstrate the flexibility of the Galley parallel file system and to analyze the efficiency and flexibility of the Vesta parallel file system interface, we implemented Vesta's application-programming interface on top of Galley. We implemented the Vesta interface using Galley's file-access methods, whose design arose from extensive testing and characterization of the I/O requirements of scientific applications for high-performance multiprocessors. We used a parallel CPU, parallel I/O, out-of-core matrix-multiplication application to test the Vesta interface in both its ability to specify data access patterns and in its run-time efficiency. In spite of its powerful ability to specify the distribution of …

A Framework For World Wide Web Client-Authentication Protocols, Cem Paya

Dartmouth College Undergraduate Theses

Existing client-authentication protocols deployed on the World Wide Web today are based on conventional distributed systems and fail to address the problems specific to the application domain. Some of the protocols restrict the mobility of the client by equating user identity to a machine or network address, others depend on sound password management strategies, and yet others compromise the privacy of the user by transmitting personal information for authentication. We introduce a new framework for client-authentication by separating two goals that current protocols achieve simultaneously: 1. Maintain persistent sense of identity across different sessions. 2. Prove facts about the user …

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

Dartmouth Scholarship

This paper presents asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on the Parallel Disk Model proposed by Vitter and Shriver. A BMMC permutation maps a source index to a target index by an affine transformation over GF(2), where the source and target indices are treated as bit vectors. The class of BMMC permutations includes many common permutations, such as matrix transposition (when dimensions are powers of 2), bit-reversal permutations, vector-reversal permutations, hypercube permutations, matrix reblocking, Gray-code permutations, and inverse Gray-code permutations. The upper bound improves upon the asymptotic …

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.

Task Scheduling In Networks, Cynthia Phillips, Clifford Stein, Joel Wein

Dartmouth Scholarship

Scheduling a set of tasks on a set of machines so as to yield an efficient schedule is a basic problem in computer science and operations research. Most of the research on this problem incorporates the potentially unrealistic assumption that communication between the different machines is instantaneous. In this paper we remove this assumption and study the problem of network scheduling, where each job originates at some node of a network, and in order to be processed at another node must take the time to travel through the network to that node.

Our main contribution is to give approximation algorithms …

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.

The Self-Organizing Desk, Daniela Rus, Peter De Santis

Dartmouth Scholarship

The self-organizing desk is a system that enhances a physical desk-top with electronic information. It can remember, organize, update, and manipulate the information contained in the documents on a desk. The system consists of a simple robot eye that can survey the desk, a module for smart extraction of information from the images taken by the robot, a module for representing this information in multiple views, and a module that allows a user to interact with this information.

Fast Discrete Polynomial Transforms With Applications To Data Analysis For Distance Transitive Graphs, J. R. Driscoll, D. M. Healy, D. N. Rockmore

Dartmouth Scholarship

Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. These sorts of transforms find important applications in areas such as medical imaging and signal processing.

In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system …

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 …

Agent Tcl: A Flexible And Secure Mobile-Agent System, Robert S. Gray

Dartmouth College Ph.D Dissertations

A mobile agent is an autonomous program that can migrate under its own control from machine to machine in a heterogeneous network. In other words, the program can suspend its execution at an arbitrary point, transport itself to another machine, and then resume execution from the point of suspension. Mobile agents have the potential to provide a {\em single, general framework} in which a wide range of distributed applications can be implemented efficiently and easily. Several challenges must be faced, however, most notably reducing migration overhead, protecting a machine from malicious agents (and an agent from malicious machines), and insulating …

The Complexity Of Clerkship Scheduling, Jonathan Feldman

Dartmouth College Undergraduate Theses

Medical students must complete a clerkship program in their fourth year. Individual students have preferences for the clerkships to which they are assigned. However, individual hospitals also have capacities on how many students may be assigned to each clerkship. The problem of scheduling medical students to clerkships is formalized. The problem is then placed in a theoretical framework, and the most general case of Clerkship Scheduling is proven NP-hard. A detailed approximation algorithm is given, and an implementation of this algorithm is discussed and tested.

Admission Control Policies For Internet File Transfer Protocols, Simon Holmes A Court

Dartmouth College Undergraduate Theses

Server congestion is a major cause of frustration with the Internet. It is not uncommon for a server with a new release of popular software to be swamped by many times more clients than it can possibly handle. Current Internet file transfer protocols, namely FTP and HTTP, do not have any policy to regulate client admission. In this thesis we are concerned with server admission policies that will improve clients' experience with servers under heavy load. Using a purpose-built network simulator, we compare the prevalent protocols with two new protocols that include policies taken from processor scheduling. By applying more …

An Information Retrieval System For Performing Hierarchical Document Clustering, Eric Hagen

Dartmouth College Undergraduate Theses

This thesis presents a system for web-based information retrieval that supports precise and informative post-query organization (automated document clustering by topic) to decrease real search time on the part of the user. Most existing Information Retrieval systems depend on the user to perform intelligent, specific queries with Boolean operators in order to minimize the set of returned documents. The user essentially must guess the appropriate keywords before performing the query. Other systems use a vector space model which is more suitable to performing the document similarity operations which permit hierarchical clustering of returned documents by topic. This allows "post query" …

Self-Organizing File Cabinet, Dawn Lawrie

Dartmouth College Undergraduate Theses

This thesis presents a self-organized file cabinet. This file cabinet uses electronic information to augment the physical world. By using a scanner to transform documents into electronic files, the self-organized file cabinet can index the documents on visual and textual information. The self-organized file cabinet helps the user find the documents at a later date. The focus of this thesis is on the design and evaluation of the self-organized file cabinet. User studies show that this tool is natural to use.

Klz: A Prototype X Protocol Compression System, Ka-Tak Lo

Dartmouth College Undergraduate Theses

One of the most commonly used graphics protocol is the X Protocol, enabling programs to display graphics images. When running the X Protocol over the network, a lot of structured data (messages with fields) need to be transmitted. Delays can be detected by human users when connected through a low-bandwidth network. The solution is to compress the X protocol. XRemote, a network version of the X Protocol, uses Dictionary-based compression. In XRemote, strings are recorded in the dictionary. When a string repeats, its index in the dictionary is transmitted. Higher Bandwidth X (HBX) uses statistical modeling techniques instead. A context …

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 …

Transportable Information Agents, Daniela Rus, Robert Gray, David Kotz

Dartmouth Scholarship

Transportable agents are autonomous programs. They can move through a heterogeneous network of computers under their own control, migrating from host to host. They can sense the state of the network, monitor software conditions, and interact with other agents or resources. The network-sensing tools allow our agents to adapt to the network configuration and to navigate under the control of reactive plans. In this paper we describe the design and implementation of the navigation system that gives our agents autonomy. We also discuss the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.

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

Dartmouth Scholarship

Many scientific applications that run on today's multiprocessors, such as weather forecasting and seismic analysis, 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 enhanced 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, to allow the disk servers to determine the flow of data for maximum performance. Our simulations show that tremendous performance gains are possible both for simple reads …