Physical Sciences and Mathematics Commons^™

A 2-2/3 Approximation 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 data compression and computational biology. In data compression, the problem is a part of a general model of string compression proposed by Gallant, Maier and Storer (JCSS '80). Much of the recent interest in the problem is due to its application to DNA sequence assembly. The problem has been shown to be NP-hard; in fact, it was shown by Blum et al.(JACM '94) to be MAX SNP-hard. The first O(1)-approximation was also due to Blum et al., who gave an algorithm that always returns a superstring no more than 3 times the length of an optimal solution. Several researchers have published results that improve on the approximation ratio; of these, the best previous result is our algorithm ShortString, which achieves a 2 3/4-approximation (WADS '95). We present our new algorithm, G-ShortString, which achieves a ratio of 2 2/3. It generalizes the ShortString algorithm, but the analysis differs substantially from that of ShortString. Our previous work identified classes of strings that have a nested periodic structure, and which must be present in the worst case for our algorithms. We introduced machinery to descibe these strings and proved strong structural properties about them. In this paper we extend this study to strings that exhibit a more relaxed form of the same structure, and we use this understanding to obtain our improved result.

Information Retrieval, Information Structure, And Information Agents, Daniela Rus, Devika Subramanian

Computer Science Technical Reports

This paper presents a customizable architecture for software agents that capture and access information in large, heterogeneous, distributed electronic repositories. The key idea is to exploit underlying structure at various levels of granularity to build high-level indices with task-specific interpretations. Information agents construct such indices and are configured as a network of reusable modules called structure detectors and segmenters. We illustrate our architecture with the design and implementation of smart information filters in two contexts: retrieving stock market data from Internet newsgroups, and retrieving technical reports from Internet ftp sites.

A Rosat Hri Observation Of The Supernova Remnant G109.1 – 1.0, Alan P. Hurford, Robert A. Fesen

Dartmouth Scholarship

We present results of a search using ROSAT HRI data for X-ray spatial substructures in the galactic supernova remnant G109.1 – 1.0 which might indicate a connection between the remnant’s bright X-ray blob and its X-ray pulsar, 1E2259 + 586. A 0.1 – 2.4 keV HRI image, created by combining separate 28- and 22-ks pointings, reveals the presence of a few small-scale X-ray features, including a NE-SW emission ridge in the remnant’s X-ray blob. Two diffuse knots in the X-ray blob, previously suggested as being aligned with the X-ray pulsar, appear to be statistical fluctuations in the Einstein HRI data. …

An Api For Choreographing Data Accesses, Elizabeth A.M. Shriver, Leonard F. Wisniewski

Computer Science Technical Reports

Current APIs for multiprocessor multi-disk file systems are not easy to use in developing out-of-core algorithms that choreograph parallel data accesses. Consequently, the efficiency of these algorithms is hard to achieve in practice. We address this deficiency by specifying an API that includes data-access primitives for data choreography. With our API, the programmer can easily access specific blocks from each disk in a single operation, thereby fully utilizing the parallelism of the underlying storage system. Our API supports the development of libraries of commonly-used higher-level routines such as matrix-matrix addition, matrix-matrix multiplication, and BMMC (bit-matrix-multiply/complement) permutations. We illustrate our API …

Complexity Analysis Of Two Permutations Used By Fast Cosine Transform Algorithms, Sean S.B. Moore, Leonard F. Wisniewski

Computer Science Technical Reports

Recently developed fast cosine transform (FCT) algorithms require fewer operations than any other known general algorithm. Similar to related fast transform algorithms (e.g., the FFT), these algorithms permute the data before, during, or after the computation of the transform. The choice of this permutation may be an important consideration in reducing the complexity of the permutation algorithm. In this paper, we derive the complexity to generate the permutation mappings used in these FCT algorithms for power-of-2 data sets by representing them as linear index transformations and translating them into combinational circuits. Moreover, we show that one of these permutations not …

Finding Real-Valued Single-Source Shortest Paths In O(N^3) Expected Time, Stavros G. Kolliopoulos, Clifford Stein

Computer Science Technical Reports

Given an $n$-vertex directed network $G$ with real costs on the edges and a designated source vertex $s$, we give a new algorithm to compute shortest paths from $s$. Our algorithm is a simple deterministic one with $O(n^2 \log n)$ expected running time over a large class of input distributions. The shortest path problem is an old and fundamental problem with a host of applications. Our algorithm is the first strongly-polynomial algorithm in over 35 years to improve upon some aspect of the running time of the celebrated Bellman-Ford algorithm for arbitrary networks, with any type of cost assignments.

Expanding The Potential For Disk-Directed I/O, David Kotz

Dartmouth Scholarship

As parallel computers are increasingly used to run scientific applications with large data sets, and as processor speeds continue to increase, it becomes more important to provide fast, effective parallel file systems for data storage and for temporary files. In an earlier work we demonstrated that a technique we call disk-directed I/O has the potential to provide consistent high performance for large, collective, structured I/O requests. In this paper we expand on this potential by demonstrating the ability of a disk-directed I/O system to read irregular subsets of data from a file, and to filter and distribute incoming data according …

Enwrich: A Compute-Processor Write Caching Scheme For Parallel File Systems, Apratim Purakayastha, Carla Schlatter Ellis, David Kotz

Dartmouth Scholarship

Many parallel scientific applications need high-performance I/O. Unfortunately, end-to-end parallel-I/O performance has not been able to keep up with substantial improvements in parallel-I/O hardware because of poor parallel file-system software. Many radical changes, both at the interface level and the implementation level, have recently been proposed. One such proposed interface is \em collective I/O, which allows parallel jobs to request transfer of large contiguous objects in a single request, thereby preserving useful semantic information that would otherwise be lost if the transfer were expressed as per-processor non-contiguous requests. Kotz has proposed \em disk-directed I/O as an efficient implementation technique for …

Interfaces For Disk-Directed I/O, David Kotz

Computer Science Technical Reports

In other papers I propose the idea of disk-directed I/O for multiprocessor file systems. Those papers focus on the performance advantages and capabilities of disk-directed I/O, but say little about the application-programmer's interface or about the interface between the compute processors and I/O processors. In this short note I discuss the requirements for these interfaces, and look at many existing interfaces for parallel file systems. I conclude that many of the existing interfaces could be adapted for use in a disk-directed I/O system.

Structured Permuting In Place On Parallel Disk Systems, Leonard F. Wisniewski

Computer Science Technical Reports

The ability to perform permutations of large data sets in place reduces the amount of necessary available disk storage. The simplest way to perform a permutation often is to read the records of a data set from a source portion of data storage, permute them in memory, and write them to a separate target portion of the same size. It can be quite expensive, however, to provide disk storage that is twice the size of very large data sets. Permuting in place reduces the expense by using only a small amount of extra disk storage beyond the size of the …

Process Migration For Heterogeneous Distributed Systems, Matt Bishop, Mark Valence, Leonard F. Winiewski

Computer Science Technical Reports

The policies and mechanisms for migrating processes in a distributed system become more complicated in a heterogeneous environment, where the hosts may differ in their architecture and operating systems. These distributed systems include a large quantity and great diversity of resources which may not be fully utilized without the means to migrate processes to the idle resources. In this paper, we present a graph model for single process migration which can be used for load balancing as well as other non-traditional scenarios such as migration during the graceful degradation of a host. The graph model provides the basis for a …

Fast Spherical Transforms On Distance Transitive Graphs, J R. Driscoll, D M. Healy Jr, D Rockmore

Computer Science Technical Reports

No abstract provided.

Determination Of Malmquist Bias And Selection Effects From Monte Carlo Simulations, Wolfram Freudling, Luiz N. Da Costa, Gary Wegner, Riccardo Giovanelli

Dartmouth Scholarship

Maps of the peculiar velocity field derived from distance relations are affected by Malmquist type bias and selection effects. Because of the large number of interdependent effects, they are in most cases difficult to treat analytically. Monte Carlo simulations are used to understand and evaluate these effects. In these simulations the "true" spatial distribution and relevant properties of galaxies as well as selection effects and observational uncertainties are realistically modeled. The results of the simulation can be directly applied to correct observed peculiar velocity maps. The simulation is used to investigate biases in samples of measured peculiar velocities by Lynden-Bell …

Disk-Directed I/O For An Out-Of-Core Computation, David Kotz

Dartmouth Scholarship

New file systems are critical to obtain good I/O performance on large multiprocessors. Several researchers have suggested the use of \em collective\/ file-system operations, in which all processes in an application cooperate in each I/O request. Others have suggested that the traditional low-level interface (\tt read, write, seek) be augmented with various higher-level requests (e.g., \em read matrix). Collective, high-level requests permit a technique called \em disk-directed I/O\/ to significantly improve performance over traditional file systems and interfaces, at least on simple I/O benchmarks. In this paper, we present the results of experiments with an “out-of-core” LU-decomposition program. Although its …

Discovery Of Extreme-Ultraviolet Radiation From The Seyfert Galaxy Ton S180 (=Euve J0057−223), Stéphane Vennes, Elisha Polomski, Stuart Bowyer, John R. Thorstensen

Dartmouth Scholarship

We report the detection of intense EUV radiation from the Seyfert 1 galaxy Ton S180. The source EUVE J0057-223, discovered in the Extreme-Ultraviolet Explorer all-sky survey, is only 25'' away from its optical counterpart, well within the position error circle. We present a complete broadband energy distribution of Ton S180 using infrared (IRAS), optical, ultraviolet (IUE) and X-ray (ROSAT) flux measurements, and we find that the measured EUV flux, corrected for neutral hydrogen and helium absorption in the Galaxy, suggests the presence of a strong EUV to soft X-ray flux excess. We briefly discuss …

Deciding Finiteness For Matrix Groups Over Function Fields, Robert Beals, Daniel N. Rockmore, Ki-Seng Tan

Computer Science Technical Reports

Let S be any finite subset GLn(F(t)) where F is a field. In this paper we give algorithms to decide if the group generated by S is finite. In the case of characteristic zero, slight modifications of earlier work of Babai, Beals and Rockmore [1] give polynomial time deterministic algorithms to solve this problem. The case of positive characteristic turns out to be more subtle and our algorithms depend on a structure theorem proved here, generalizing a theorem of Weil. We also present a fairly detailed analysis of the size of finite subgroups in this case and give bounds which …

Oscillons: Resonant Configurations During Bubble Collapse, E J. Copeland, M Gleiser, H R. Müller

Dartmouth Scholarship

Oscillons are localized, non-singular, time-dependent, spherically-symmetric solutions of nonlinear scalar field theories which, although unstable, are extremely long-lived. We show that they naturally appear during the collapse of subcritical bubbles in models with symmetric and asymmetric double-well potentials. By a combination of analytical and numerical work we explain several of their properties, including the conditions for their existence, their longevity, and their final demise. We discuss several contexts in which we expect oscillons to be relevant. In particular, their nucleation during cosmological phase transitions may have wide-rangingconsequences.

A Multiple Discrete Pass Algorithm On A Dec Alpha 2100, Scott R. Cushman

Dartmouth College Undergraduate Theses

No abstract provided.

Simulation Of A Video-On-Demand System, Song Bac Toh

Dartmouth College Undergraduate Theses

This paper presents a simulation study of a video-on-demand system. The focus of the study is the effectiveness of different caching strategies on a video-on-demand system with two levels of cache, RAM and disks, in front of a tape library. Using an event-driven simulator, I show that caching was helpful in increasing the service capacity of the system. On-demand caching showed its advantages especially when the requests were clustered around a few popular titles (in other words, there was temporal locality).

Tias: A Transportable Intelligent Agent System, Kenneth Harker

Dartmouth College Undergraduate Theses

In recent years, there has been an explosive growth in the amount of information available to our society. In particular, the amount of information available on-line through vast networks like the global Internet has been growing at a staggering rate. This growth rate has by far exceeded the rate of growth in network speeds, as has the number of individuals and organizations seeking access to this information. There is thus a motivation to find abstract methods of manipulating this on-line data in ways that both serve the needs of end users efficiently and use network resources intelligently. In lieu of …

Ph.D. Thesis Proprosal: Transportable Agents, Robert S. Gray

Computer Science Technical Reports

One of the paradigms that has been suggested for allowing efficient access to remote resources is transportable agents. A transportable agent is a named program that can migrate from machine to machine in a heterogeneous network. The program chooses when and where to migrate. It can suspend its execution at an arbitrary point, transport to another machine and resume execution on the new machine. Transportable agents have several advantages over the traditional client/server model. Transportable agents consume less network bandwidth and do not require a connection between communicating machines -- this is attractive in all networks and particularly attractive in …

Low-Level Interfaces For High-Level Parallel I/O, Nils Nieuwejaar, David Kotz

Dartmouth Scholarship

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 three extensions to the interface that support \em strided, \em …

Exploring The Use Of I/O Nodes For Computation In A Mimd Multiprocessor, David Kotz, Ting Cai

Dartmouth Scholarship

As parallel systems move into the production scientific-computing world, the emphasis will be on cost-effective solutions that provide high throughput for a mix of applications. Cost-effective solutions demand that a system make effective use of all of its resources. Many MIMD multiprocessors today, however, distinguish between “compute” and “I/O” nodes, the latter having attached disks and being dedicated to running the file-system server. This static division of responsibilities simplifies system management but does not necessarily lead to the best performance in workloads that need a different balance of computation and I/O. \par Of course, computational processes sharing a node with …

Expanding The Potential For Disk-Directed I/O, David Kotz

Computer Science Technical Reports

As parallel computers are increasingly used to run scientific applications with large data sets, and as processor speeds continue to increase, it becomes more important to provide fast, effective parallel file systems for data storage and for temporary files. In an earlier work we demonstrated that a technique we call disk-directed I/O has the potential to provide consistent high performance for large, collective, structured I/O requests. In this paper we expand on this potential by demonstrating the ability of a disk-directed I/O system to read irregular subsets of data from a file, and to filter and distribute incoming data according …

Content-Based Image Retrieval: Color And Edges, Robert S. Gray

Computer Science Technical Reports

One of the tools that will be essential for future electronic publishing is a powerful image retrieval system. The author should be able to search an image database for images that convey the desired information or mood; a reader should be able to search a corpus of published work for images that are relevant to his or her needs. Most commercial image retrieval systems associate keywords or text with each image and require the user to enter a keyword or textual description of the desired image. This text-based approach has numerous drawbacks -- associating keywords or text with each image …

Exploring The Use Of I/O Nodes For Computation In A Mimd Multiprocessor, David Kotz, Ting Cai

Computer Science Technical Reports

As parallel systems move into the production scientific computing world, the emphasis will be on cost-effective solutions that provide high throughput for a mix of applications. Cost-effective solutions demand that a system make effective use of all of its resources. Many MIMD multiprocessors today, however, distinguish between ``compute'' and ``I/O'' nodes, the latter having attached disks and being dedicated to running the file-system server. This static division of responsibilities simplifies system management but does not necessarily lead to the best performance in workloads that need a different balance of computation and I/O. Of course, computational processes sharing a node with …

The Orbital Period Of The Pre-Cataclysmic Binary Re 2013+400 And A Study Of The Atmosphere Of The Dao White Dwarf Primary, M. A. Barstow, M. R. Burleigh, T. A. Fleming, J. B. Holberg, D. Koester, M. C. Marsh, S. R. Rosen, R. G.M. Rutten, S. Sakai, R. W. Tweedy, G. Wegner

Dartmouth Scholarship

Several pre-cataclysmic binaries, comprising a hot white dwarf with a red dwarf companion, have been discovered as a result of the optical identification of EUV sources from the ROSAT all-sky survey. The optical spectra have the steep blue continuum and Balmer absorption typical of a hot white dwarf, but there are bright, narrow emission lines of H I (and sometimes He I and Ca II) superimposed. An intense campaign of follow-up observations has been devoted to these binary systems. So far, only RE 2013+400 has exhibited any measurable changes in the radial velocities of the emission components, from which it …

Disk-Directed I/O For An Out-Of-Core Computation, David Kotz

Computer Science Technical Reports

New file systems are critical to obtain good I/O performance on large multiprocessors. Several researchers have suggested the use of collective file-system operations, in which all processes in an application cooperate in each I/O request. Others have suggested that the traditional low-level interface (read, write, seek) be augmented with various higher-level requests (e.g., read matrix), allowing the programmer to express a complex transfer in a single (perhaps collective) request. Collective, high-level requests permit techniques like two-phase I/O and disk-directed I/O to significantly improve performance over traditional file systems and interfaces. Neither of these techniques have been tested on anything other …

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 …

Dartcvl: The Dartmouth C Vector Library, Thomas H. Cormen, Sumit Chawla, Preston Crow, Melissa Hirschl, Roberto Hoyle, Keith D. Kotay, Rolf H. Nelson, Nils Nieuwejaar, Scott M. Silver, Michael B. Taylor, Rajiv Wickremesinghe

Computer Science Technical Reports

As a class project, we implemented a version of CVL, the C Vector Library, on a DECmpp 12000/Sx 2000, which is equivalent to the MasPar MP-2 massively parallel computer. We compare our implementation, DartCVL, to the University of North Carolina implementation, UnCvl.

DartCVL was designed for the MP-2 architecture and UnCvl was designed for the MP-1. Because the MasPar MP-1 and MP-2 are functionally equivalent, both DartCVL and UnCvl will run on either. Differences in the designs of the two machines, however, may lead to different software design decisions. DartCVL differs from UnCvl in two key ways. First, DartCVL uses …