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 …

Galley: A New Parallel File System For Parallel Applications, Nils Nieuwejaar

Dartmouth College Ph.D Dissertations

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. Most multiprocessor file systems provide applications with a conventional Unix-like interface, allowing the application to access those 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 application and library programmers to use knowledge about their I/O to exploit that parallelism. In addition to providing an insufficient interface, most current multiprocessor file systems are optimized for a …

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.

Mri On The Fly: Accelerating Mri Imaging Using Lda Classification With Ldb Feature Extraction, Y Joy Ko, Michael B. Taylor

Dartmouth College Undergraduate Theses

To improve MRI acquisition time, we explored the uses of linear discriminant analysis (LDA), and local discriminant bases (LDB) for the task of classifying MRI images using a minimal set of signal acquisitions. Our algorithm has both off-line and on-line components. The off-line component uses the k-basis algorithm to partition a set of training images (all from a particular region of a patient) into classes. For each class, we find a basis by applying the best basis algorithm on the images in that class. We keep these bases to be used by the on-line process. We then apply LDB to …

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.

The Panda Array I/O Library On The Galley Parallel File System, Joel T. Thomas

Dartmouth College Undergraduate Theses

The Panda Array I/O library, created at the University of Illinois, Urbana-Champaign, was built especially to address the needs of high-performance scientific applications. I/O has been one of the most frustrating bottlenecks to high performance for quite some time, and the Panda project is an attempt to ameliorate this problem while still providing the user with a simple, high-level interface. The Galley File System, with its hierarchical structure of files and strided requests, is another attempt at addressing the performance problem. My project was to redesign the Panda Array library for use on the Galley file system. This project involved …

Object Oriented Scenes For Virtual Light, Jonathan A. Moore

Dartmouth College Undergraduate Theses

Ray tracing is one of many way to use a computer to generate an image. Ray tracers produce images by simulating light. Eliminating the details that might distract one from the interesting parts of ray tracing algorithms was purpose of my thesis project. The software I have written can be divide into three parts: the virtual frame buffer, the support classes and the ray tracing abstract base classes. The virtual frame buffer class, vfb, provides a simple means of rendering and studying the final image produced by a graphical algorithm. The support classes provide an elegant notation for the equations …

Implementation And Analysis Of Software Based Fault Isolation, Scott M. Silver

Dartmouth College Undergraduate Theses

Extensible applications rely upon user-supplied, untrusted modules to extend their functionality. To remain reliable, applications must isolate themselves from user modules. One method places each user module in a separate address space (process), which uses hardware virtual memory support to isolate the user process. Costly inter-process communication, however, prohibits frequent communication between the application and the untrusted module. We implemented and analyzed a software method for isolating an application from user modules. The technique uses a single address space. We provide a logical address space and per-module access to system resources for each module. Our software technique is a two-step …

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). …

Segmenting Workstation Screen Images, Denis M. Serenyi

Dartmouth College Undergraduate Theses

No abstract provided.

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 …