Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 18 of 18
Full-Text Articles in Physical Sciences and Mathematics
Market-Based Resource Control For Mobile Agents, Jonathan Bredin, David Kotz, Daniela Rus
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
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
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
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
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
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
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
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
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
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
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
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
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
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 …
An Efficient Scheme For A Distributed Video Retrieval System For Remote Users, Fillia Makedon, James Matthews, Charles Owen, Samuel Rebelsky
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 …
Asml: Automatic Site Markup Language 1.03, Charles B. Owen, Fillia Makedon, Glen Frank, Michael Kenyon
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 …
Automated Parallelization Of Discrete State-Space Generation, David M. Nicol, Gianfranco Ciardo
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
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 …