Physical Sciences and Mathematics Commons^™

Lower And Upper Bounds On Internal-Wave Frequencies In Stratified Rotating Fluids, Benoit Cushman-Roisin

Dartmouth Scholarship

According to classical theories, the frequencies of internal-gravity waves in stratified rotating fluids must lie between the Brunt-Väisälä frequency (a measure of the vertical density stratification) and the Coriolis frequency (equal to twice the rotation rate about the vertical axis). It is shown here that, in the case of the Earth's rotation where the pole-to-pole axis of rotation is almost everywhere not parallel to the local vertical, the range of realizable frequencies is broader. New formulas are derived for the lower and upper bounds of the frequencies.

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 …

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 …

On The Orbital Period Of The New Cataclysmic Variable Euve J2115-586, Stephane Vennes, Dayal T. Wickramasinghe, John R. Thorstensen, Damian J. Christian, Michael S. Bessell

Dartmouth Scholarship

We have obtained phase-resolved spectroscopy (3660-6040 Å) of the recently discovered cataclysmic variable EUVE J21 15-586 using the 74-inch telescope at Mount Stromlo Observatory. The radial velocity is modulated over a period of 110.8 min with a possible one-cycle-per-day alias of 102.8 min, and a semiamplitude of ≍270 km s^-1 at Hβ and ≍390 km s^-1 at He II λ4686. The spectroscopic appearance (H I Balmer, Ca II, He I, He II emission lines), the orbital period, and the velocity amplitude indicate that this cataclysmic variable is probably an AM Her type; the absence of cyclotron humps indicates …

High Quality Alias Free Image Rotation, Charles B. Owen, Fillia Makedon

Dartmouth Scholarship

This paper presents new algorithms for the rotation of images. The primary design criteria for these algorithms is very high quality. Common methods for image rotation, including convolutional and separable approaches, are examined and shown to exhibit significant high frequency aliasing problems. A new resampling filter design methodology is presented which minimizes the problem for conventional convolution-based image rotation. The paper also presents a new separable image rotation algorithm which exhibits improved performance in term of reduction in artifacts and an efficient $O(N^{2} log N)$ running time.

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.

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.

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 …

File-Access Characteristics Of Parallel Scientific Workloads, Nils Nieuwejaar, David Kotz, Apratim Purakayastha, Carla Schlatter Ellis, Michael L. Best

Dartmouth Scholarship

Phenomenal improvements in the computational performance of multiprocessors have not been matched by comparable gains in I/O system performance. This imbalance has resulted in I/O becoming a significant bottleneck for many scientific applications. One key to overcoming this bottleneck is improving the performance of multiprocessor file systems. \par The design of a high-performance multiprocessor file system requires a comprehensive understanding of the expected workload. Unfortunately, until recently, no general workload studies of multiprocessor file systems have been conducted. The goal of the CHARISMA project was to remedy this problem by characterizing the behavior of several production workloads, on different machines, …

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 …

The Mass Distribution In The Nearby Universe, Luiz N. Da Costa, Wolfram Freudling, Gary Wegner, Riccardo Giovanelli

Dartmouth Scholarship

We present a new reconstruction of the mass density and the peculiar velocity fields in the nearby universe using recent measurements of Tully-Fisher distances for a sample of late spirals. We find significant differences between our reconstructed fields and those obtained in earlier work: overdensities tend to be more compact while underdense regions, consisting of individual voids, are more abundant. Our results suggest that voids observed in redshift surveys of galaxies represent real voids in the underlying matter distribution. While we detect a bulk velocity of ~300 km s^-1, within a top-hat window 6000 km s^-1 in …

The Peculiar Motions Of Early-Type Galaxies In Two Distant Regions. I. Cluster And Galaxy Selection, Gary Wegner, Matthew Colless, Glenn Baggley, Roger L. Davies

Dartmouth Scholarship

The EFAR project is a study of 736 candidate elliptical galaxies in 84 clusters lying in two regions, toward Hercules-Corona Borealis and Perseus-Pisces-Cetus, at distances cz ~ 6000-15,000 km s^-1^. In this paper (the first of a series), we present an introduction to the EFAR project and describe in detail the selection of the clusters and galaxies in our sample. Fundamental data for the galaxies and clusters are given, including accurate new positions for each galaxy and redshifts for each cluster. The galaxy selection functions are determined by using diameters measured from Schmidt sky survey images for 2185 galaxies in …

Flexibility And Performance Of Parallel File Systems, David Kotz, Nils Nieuwejaar

Dartmouth Scholarship

As we gain experience with parallel file systems, it becomes increasingly clear that a single solution does not suit all applications. For example, it appears to be impossible to find a single appropriate interface, caching policy, file structure, or disk-management strategy. Furthermore, the proliferation of file-system interfaces and abstractions make applications difficult to port. \par We propose that the traditional functionality of parallel file systems be separated into two components: a fixed core that is standard on all platforms, encapsulating only primitive abstractions and interfaces, and a set of high-level libraries to provide a variety of abstractions and application-programmer interfaces …

Transportable Agents Support Worldwide Applications, David Kotz, Robert Gray, Daniela Rus

Dartmouth Scholarship

Worldwide applications exist in an environment that is inherently distributed, dynamic, heterogeneous, insecure, unreliable, and unpredictable. In particular, the latency and bandwidth of network connections varies tremendously from place to place and time to time, particularly when considering wireless networks, mobile devices, and satellite connections. Applications in this environment must be able to adapt to different and changing conditions. We believe that transportable autonomous agents provide an excellent mechanism for the construction of such applications. We describe our prototype transportable-agent system and several applications.

Worldwide applications exist in an environment that is inherently distributed, dynamic, heterogeneous, insecure, unreliable, and unpredictable. …

Determining An Out-Of-Core Fft Decomposition Strategy For Parallel Disks By Dynamic Programming, Thomas H. Cormen

Dartmouth Scholarship

We present an out-of-core FFT algorithm based on the in-core FFT method developed by Swarztrauber. Our algorithm uses a recursive divide-and-conquer strategy, and each stage in the recursion presents several possibilities for how to split the problem into subproblems. We give a recurrence for the algorithm's I/O complexity on the Parallel Disk Model and show how to use dynamic programming to determine optimal splits at each recursive stage. The algorithm to determine the optimal splits takes only Theta(lg^2 N) time for an N-point FFT, and it is practical. The out-of-core FFT algorithm itself takes considerably longer.

Autonomous And Adaptive Agents That Gather Information, Daniela Rus, Robert Gray, David Kotz

Dartmouth Scholarship

We have designed and implemented autonomous software agents. Autonomous software agents navigate independently through a heterogeneous network of computers. They can sense the state of the network, monitor software conditions, and interact with other agents. 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 illustrate the intelligent and adaptive behavior of autonomous agents in distributed information-gathering tasks.

Ffts For The 2-Sphere-Improvements And Variations, D M. Healy, D Rockmore, Sean S.B. Moore

Computer Science Technical Reports

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most 0(N log2 N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. These claims are supported by …

A Test Of The Lauer-Postman Bulk Flow, Riccardo Giovanelli, Martha P. Haynes, Gary Wegner, Luiz N. Da Costa

Dartmouth Scholarship

We use Tully-Fisher distances for a sample of field late spiral galaxies to test the Lauer & Postman result suggestive of a bulk flow with respect to the cosmic microwave background reference frame, of amplitude of +689 km s^-1 in the direction l = 343°, b = +52°. A total of 432 galaxies are used, subdivided between two cones, of 30° semiaperture each and pointed toward the apex and antapex of the LP motion, respectively. The peculiar velocities in the two data sets are inconsistent with a bulk flow of the amplitude claimed by Lauer & Postman. When combined …

On The Existence Of Schedules That Are Near-Optimal For Both Makespan And Total Weighted Completion Time, Cliff Stein, Joel Wein

Computer Science Technical Reports

We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted completion time at most twice that of the optimal possible. We then refine the analysis, yielding variants of this theorem with improved constants, and give some algorithmic consequences of the technique.

Discovery Of A White Dwarf Companion (Ms0354.6-3650 = Euve J0356-366) To A G2v Star, Damian J. Christian, Stephane Vennes, John R. Thorstensen, Mihalis Mathioudakis

Dartmouth Scholarship

We present x-ray, ultraviolet, and optical observations of the mysterious EUV/soft x-ray source EUVE J0356-336 (= MS0354.6-3650). Initial Einstein observations identified this source with a cluster of galaxies, but the relatively high source count rate in the Extreme Ultraviolet Explorer (EUVE) 100 Å band and the lack of variability hinted that EUVE J0356-3650 might be a white dwarf; the UK Schmidt plate of the field surrounding this object found a 12.45 magnitude G2V star that could hide a compact companion. This hypothesis was confirmed in an IUE ultraviolet spectrum that shows the definite signature of a hydrogen-rich white dwarf (DA). …

Mobile Agents For Mobile Computing, Robert Gray, David Kotz, Saurab Nog, Daniela Rus, George Cybenko

Computer Science Technical Reports

Mobile agents are programs that can move through a network under their own control, migrating from host to host and interacting with other agents and resources on each. We argue that these mobile, autonomous agents have the potential to provide a convenient, efficient and robust programming paradigm for distributed applications, particularly when partially connected computers are involved. Partially connected computers include mobile computers such as laptops and personal digital assistants as well as modem-connected home computers, all of which are often disconnected from the network. In this paper, we describe the design and implementation of our mobile-agent system, Agent Tcl, …

Dartflow: A Workflow Management System On The Web Using Transportable Agents, Ting Cai, Peter A. Gloor, Saurab Nog

Computer Science Technical Reports

Workflow management systems help streamline business processes and increase productivity. This paper describes the design and implementation of the DartFlow workflow management system. DartFlow uses Web-browser embedded Java applets as its front end and transportable agents as the backbone. While Java applets provide a safe and platform independent GUI, the use of transportable agents makes DartFlow highly flexible and scalable. This paper describes the design and implementation of DartFlow, as well as a workflow application that exploits DartFlow's agent-based design.

The Galley Parallel File System, Nils Nieuwejaar, David Kotz

Computer Science Technical Reports

Most current multiprocessor file systems are designed to use multiple disks in parallel, using the high aggregate bandwidth to meet the growing I/O requirements of parallel scientific applications. Many multiprocessor file systems provide applications with a conventional Unix-like interface, allowing the application to access multiple disks transparently. This interface conceals the parallelism within the file system, increasing the ease of programmability, but making it difficult or impossible for sophisticated programmers and libraries to use knowledge about their I/O needs to exploit that parallelism. In addition to providing an insufficient interface, most current multiprocessor file systems are optimized for a different …

Absence Of Open Strings In A Lattice-Free Simulation Of Cosmic String Formation, Julian Borrill

Dartmouth Scholarship

Lattice-based string formation algorithms can, at least in principle, be reduced to the study of the statistics of the corresponding aperiodic random walk. Since in three or more dimensions such walks are transient, this approach necessarily generates a population of open strings. To investigate whether open strings are an artifact of the lattice we develop an alternative lattice-free simulation of string formation. Replacing the lattice with a graph generated by a minimal dynamical model of a first-order phase transition we obtain results consistent with the hypothesis that the energy density in string is due to a scale-invariant Brownian distribution of …

An Optical And X-Ray Study Of Abell 576, A Galaxy Cluster With A Cold Core, Joseph J. S. Mohr, Margaret J. Geller, Daniel G. Fabricant, Gary Wegner, John Thorstensen, Douglas O. Richstone

Dartmouth Scholarship

We analyze the galaxy population and dynamics of the galaxy cluster A576; the observational constraints include 281 redshifts (230 new), R- band CCD galaxy photometry over a 2 h^-1^ Mpc x 2 h^-1^ Mpc region centered on the cluster, an Einstein IPC X-ray image, and an Einstein MPC X-ray spectrum. We focus on an 86% complete magnitude-limited sample (R_23.5_ < 17) of 169 cluster galaxies. The cluster galaxies with emission lines in their spectra have a larger velocity dispersion and are significantly less clustered on this 2 h^-1^ Mpc scale than galaxies without emission lines. We show that excluding the emission-line galaxies from the cluster sample decreases the velocity dispersion by 18% and the virial mass estimate by a factor of 2. The central cluster region contains a nonemission galaxy population and an intracluster medium which is significantly cooler (σ_core_ = 387_-105_^+250^ km s^-1^ and T_x_ = 1.6_-0.3_^+0.4^ keV at 90% confidence) than the global populations (σ = 977_-96_^+124^ km s^- 1^ for the nonemission population and T_X_ > 4 keV at 90% confidence). Because (1) the low-dispersion galaxy population is no more luminous than the global population and (2) the evidence for a cooling flow is weak, we suggest that the core of A576 may contain the remnants of …

The Expected Lifetime Of Single-Address-Space Operating Systems, David Kotz, Preston Crow

Dartmouth Scholarship

Trends toward shared-memory programming paradigms, large (64-bit) address spaces, and memory-mapped files have led some to propose the use of a single virtual-address space, shared by all processes and processors. To simplify address-space management, some have claimed that a 64-bit address space is sufficiently large that there is no need to ever re-use addresses. Unfortunately, there has been no data to either support or refute these claims, or to aid in the design of appropriate address-space management policies. In this paper, we present the results of extensive kernel-level tracing of the workstations on our campus, and discuss the implications for …

Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young

Dartmouth Scholarship

Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for $K > 2$. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times …

File-Access Characteristics Of Parallel Scientific Workloads, Nils Nieuwejaar, David Kotz, Apratim Purakayastha, Carla Schlatter Ellis, Michael Best

Computer Science Technical Reports

Phenomenal improvements in the computational performance of multiprocessors have not been matched by comparable gains in I/O system performance. This imbalance has resulted in I/O becoming a significant bottleneck for many scientific applications. One key to overcoming this bottleneck is improving the performance of parallel file systems.

The design of a high-performance parallel file system requires a comprehensive understanding of the expected workload. Unfortunately, until recently, no general workload studies of parallel file systems have been conducted. The goal of the CHARISMA project was to remedy this problem by characterizing the behavior of several production workloads, on different machines, at …

A Queuing Analysis Of Bandwidth Allocation Schemes For Compressed Video, Saurab Nog, Carl J. Beckmann

Computer Science Technical Reports

Video and audio compression techniques allow continuous media streams to be transmitted at bit rates that are a function of the delivered quality of service. Digital networks will be increasingly used for the transmission of such continuous media streams. This paper describes an admission control policy in which the quality of service is negotiated at stream initiation, and is a function of both the desired quality of service and the available bandwidth resources. The advantage of this approach is the ability to robustly service large numbers of users, while providing increased quality of service during low usage periods. Several simple …