Physical Sciences and Mathematics Commons^™

Transportable Agents, Keith D. Kotay, David Kotz

Dartmouth Scholarship

As network information resources grow in size, it is often most efficient to process queries and updates at the site where the data is located. This processing can be accomplished by using a traditional client-server network interface, which constrains the client to the set of queries supported by the server, or requires the server to send all data to the client for processing. The former is inflexible; the latter is inefficient. Transportable agents, which support the movement of the client computation to the location of the remote resource, have the potential to be more flexible and more efficient. Transportable agents …

Orbital Studies Of The Cataclysmic Variables Cz Orionis, V1193 Orionis And Bz Ursae Majoris, F. A. Ringwald, J. R. Thorstensen, R. M. Hamwey

Dartmouth Scholarship

Time-resolved spectroscopy reveals the orbital periods of three cataclysmic variables. CZ Ori has an orbital period of 0.2189 d. This is within 3 per cent of a prediction relating orbital period and dwarf nova outburst decline time. We find the M2.5 ± 1.0 secondary, and infer an absolute magnitude for CZ Ori in RKc of 8.5 ± 1.0 and a distance of 260 ± 110 pc. V1193 Ori, also called Hamuy's Blue Variable, has an orbital period of 0.165 d. In 1988, Ha emission line profile variations suggested red star illumination. In 1989, this line's red wing flared at orbital …

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

Computer Science Technical Reports

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, 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 are …

A Data-Parallel Programming Library For Education (Dapple), David Kotz

Computer Science Technical Reports

In the context of our overall goal to bring the concepts of parallel computing into the undergraduate curriculum, we set out to find a parallel-programming language for student use. To make it accessible to students at all levels, and to be independent of any particular hardware platform, we chose to design our own language, based on a data-parallel model and on C++. The result, DAPPLE, is a C++ class library designed to provide the illusion of a data-parallel programming language on conventional hardware and with conventional compilers. DAPPLE defines Vectors and Matrices as basic classes, with all the usual C++ …

Multimedia Authoring, Development Environments, And Digital Video Editing, Fillia Makedon, James W. Matthews, Charles B. Owen, Samuel A. Rebelsky

Dartmouth Scholarship

Multimedia systems integrate text, audio, video, graphics, and other media and allow them to be utilized in a combined and interactive manner. Using this exciting and rapidly developing technology, multimedia applications can provide extensive benefits in a variety of arenas, including research, education, medicine, and commerce. While there are many commercial multimedia development packages, the easy and fast creation of a useful, full-featured multimedia document is not yet a straightforward task.

This paper addresses issues in the development of multimedia documents, ranging from user-interface tools that manipulate multimedia documents to multimedia communication technologies such as compression, digital video editing and …

Building Multimedia Proceedings: The Roles Of Video In Interactive Electronic Conference Proceedings, Samuel A. Rebelsky, Fillia Makedon, James Matthews, Charles Owen, Laura Bright, Kenneth Harker, Nancy Toth

Computer Science Technical Reports

Modern computer systems have changed the way that conference proceedings can be presented and archived. No longer are researchers limited by printed text; electronic proceedings allow one to search the proceedings, add and share annotations, and create paths of related concepts through the proceedings. These additional capabilities extend the opportunities and benefit the thought processes of actual conference participants and the new virtual participants who experience the conference through the electronic proceedings.

In this paper, we discuss the construction of electronic conference proceedings, highlighting the role of talks and other presentations (and, particularly, the audio and video of these talks …

Distributed Scheduling In Finite Capacity Networks, Perry Fizzano, Clifford Stein

Computer Science Technical Reports

We consider the problem of scheduling unit-sized jobs in a distributed network of processors. Each processor only knows the number of jobs it and its neighbors have. We give an analysis of intuitive algorithm and prove that the algorithm produces schedules that are within a logarithmic factor of the length of the optimal schedule given that the optimal schedule is sufficiently long.

Incremental Equational Programming, Samuel A. Rebelsky

Computer Science Technical Reports

This paper extends Equational Programming (EP)—a declarative, symbolic programming language—to allow programs to manipulate incrementally defined and modified input terms and to avoid repeated work when evaluating these incremental terms. This paper represents two key aspects of this extension: a notation for representing revision and a modification to EP's runtime library to accomodate this notation. Unlike Field's method of incremental term rewriting, which is designed for more general but less efficient term-rewriting systems, this paper's method accomodates EP's restrictions (in particular, EP's decision to disallow overlapping rules) so that it may take advantage of EP's speed.

Efficient Parallel Algorithms For Closest Point Problems, Peter Su

Dartmouth College Ph.D Dissertations

This dissertation develops and studies fast algorithms for solving closest point problems. Algorithms for such problems have applications in many areas including statistical classification, crystallography, data compression, and finite element analysis. In addition to a comprehensive empirical study of known sequential methods, I introduce new parallel algorithms for these problems that are both efficient and practical. I present a simple and flexible programming model for designing and analyzing parallel algorithms. Also, I describe fast parallel algorithms for nearest-neighbor searching and constructing Voronoi diagrams. Finally, I demonstrate that my algorithms actually obtain good performance on a wide variety of machine architectures. …

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 …

Characterizing Parallel File-Access Patterns On A Large-Scale Multiprocessor, Apratim Purakayastha, Carla Schlatter Ellis, David Kotz, Nils Nieuwejaar, Michael Best

Dartmouth Scholarship

Rapid increases in the computational speeds of multiprocessors have not been matched by corresponding performance enhancements in the I/O subsystem. To satisfy the large and growing I/O requirements of some parallel scientific applications, we need parallel file systems that can provide high-bandwidth and high-volume data transfer between the I/O subsystem and thousands of processors. \par Design of such high-performance parallel file systems depends on a thorough grasp of the expected workload. So far there have been no comprehensive usage studies of multiprocessor file systems. Our CHARISMA project intends to fill this void. The first results from our study involve an …

Hypergraph Partitioning Algorithms, Tom Leighton, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

We present the first polynomial time approximation algorithms for the balanced hypergraph partitioning problem. The approximations are within polylogarithmic factors of the optimal solutions. The choice of algorithm involves a time complexity/approximation bound tradeoff. We employ a two step methodology. First we approximate the flux of the input hypergraph. This involves an approximate solution to a concurrent flow problem on the hypergraph. In the second step we use the approximate flux to obtain approximations for the balanced bipartitioning problem. Our results extend the approximation algorithms by Leighton-Rao on graphs to hypergraphs. We also give the first polylogarithmic times optimal approximation …

Improved Algorithms For Bipartite Network Flow, Ravindra K. Ahuja, James B. B. Orlin, Clifford Stein, Robert E. Tarjan

Dartmouth Scholarship

In this paper, network flow algorithms for bipartite networks are studied. A network G = (V,E) is called bipartite if its vertex set V can be partitioned into two subsets V_1 and V_2 such that all edges have one endpoint in V_1 and the other in $V_2 $. Let $n = |V|, n_1 = |V_1 | , n_2 = |V_2 |, m = |E| and assume without loss of generality that n_1 \leqslant n_2. A bipartite network is called unbalanced if n_1 \ll n_2 $ and balanced otherwise. (This notion is necessarily imprecise.) It is shown that several maximum flow …

A Multiprocessor Extension To The Conventional File System Interface, Nils Nieuwejaar, David Kotz

Computer Science Technical Reports

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 an extension which supports strided and nested-strided I/O requests.

Chromium(Vi) Reduction By Ascorbate: Role Of Reactive Intermediates In Dna Damage In Vitro, D M. Stearns, K D. Courtney, P H. Giangrande, L S. Phieffer, Karen E. Wetterhahn

Dartmouth Scholarship

Reaction of chromium(VI) with one equivalent of ascorbate was studied by electron paramagnetic resonance spectroscopy in the presence of 0.10 M 5,5-dimethyl-1-pyrroline-1-oxide (DMPO) at room temperature in 0.10 M (N-[2-hydroxyethyl]piperazine-N'-[2-ethanesulfonic acid]) (HEPES) and 0.05 M tris(hydroxymethyl)aminomethane hydrochloride (Tris-HCl) buffers (pH 7.0 room temperature). Chromium(V), ascorbyl radical, and carbon-based DMPO-radical adducts were observed. A higher level of Cr(V) was observed in HEPES buffer and a higher level of the DMPO-radical adducts was observed in Tris-HCl buffer. Chromium-DNA binding studies were carried out in vitro for calf thymus DNA incubated with Cr(VI) and ascorbate in both buffers at 37 degrees C. Higher …

A New Approach To The Minumum Cut Problem, David R. Karger, Clifford Stein

Computer Science Technical Reports

No abstract provided.

Dynamic File-Access Characteristics Of A Production Parallel Scientific Workload, David Kotz, Nils Nieuwejaar

Computer Science Technical Reports

Multiprocessors have permitted astounding increases in computational performance, but many cannot meet the intense I/O requirements of some scientific applications. An important component of any solution to this I/O bottleneck is a parallel file system that can provide high-bandwidth access to tremendous amounts of data in parallel to hundreds or thousands of processors. Most successful systems are based on a solid understanding of the characteristics of the expected workload, but until now there have been no comprehensive workload characterizations of multiprocessor file systems. We began the CHARISMA project in an attempt to fill that gap. We instrumented the common node …

A Detailed Simulation Model Of The Hp 97560 Disk Drive, David Kotz, Song Bac Toh, Sriram Radhakrishnan

Computer Science Technical Reports

We implemented a detailed model of the HP 97560 disk drive, to replicate a model devised by Ruemmler and Wilkes (both of Hewlett-Packard, HP). Our model simulates one or more disk drives attached to one or more SCSI buses. The design is broken into three components: a test driver, the disk model itself, and the discrete-event simulation support. Thus, the disk model can be easily extracted and used in other simulation environments. We validated our model using traces obtained from HP, using the same "demerit" measure as Ruemmler and Wilkes. We obtained a demerit percentage of 3.9%, indicating that our …

A 2-3/4-Approximation Algorithm 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 computational biology and data compression. The problem is NP-hard [GallantMS80]; in fact, it was recently shown to be MAX SNP-hard [BlumJLTY91]. Given the importance of the applications, several heuristics and approximation algorithms have been proposed. Constant factor approximation algorithms have been given in [BlumJLTY91] (factor of 3), [TengY93] (factor of 2-8/9), [CzumajGPR94] (factor of 2-5/6) and [KosarajuPS94] (factor of 2-50/63). Informally, the key to any algorithm for the shortest superstring problem is to identify sets of strings with large amounts of similarity, or overlap. While the previous algorithms and their analyses have grown increasingly sophisticated, they reveal remarkably little about the structure of strings with large amounts of overlap. In this sense, they are solving a more general problem than the one at hand. In this paper, we study the structure of strings with large amounts of overlap and use our understanding to give an algorithm that finds a superstring whose length is no more than 2-3/4 times that of the optimal superstring. We prove several interesting properties about short periodic strings, allowing us to answer questions of the following form: given a string with some periodic structure, characterize all the possible periodic strings that can have a large amount of overlap with the first string.

Efficiency And Stability Issues In The Numerical Computation Of Fourier Transforms And Convolutions On The 2-Sphere, D M. Healy Jr, S S. B. Moore, D Rockmore

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 sphere. In this paper we present a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. We also discuss implementational considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. This discussion is supplemented with numerical experiments from our implementation in C on a DecStation 5000. These results give strong indications that the algorithm is both reliable and efficient for a large …

Parallel Computer Needs At Dartmouth College, David Kotz, Fillia Makedon, Matt Bishop, Scot Drysdale, Don Johnson, Takis Metaxas

Computer Science Technical Reports

To determine the need for a parallel computer on campus, a committee of the Graduate Program in Computer Science surveyed selected Dartmouth College faculty and students in December, 1991, and January, 1992. We hope that the information in this report can be used by many groups on campus, including the Computer Science graduate program and DAGS summer institute, Kiewit's NH Supercomputer Initiative, and by numerous researchers hoping to collaborate with people in other disciplines.

We found significant interest in parallel supercomputing on campus. An on-campus parallel supercomputing facility would not only support numerous courses and research projects, but would provide …

Bmmc Permutations On A Decmpp 12000/Sx 2000, Kristin Bruhl

Dartmouth College Undergraduate Theses

Increasingly, modern computing problems, including many scientific and business applications, require huge amounts of data to be examined, modified, and stored. Parallel computers can be used to decrease the time needed to operate on such large data sets, by allowing computations to be performed on many pieces of data at once. For example, on the DECmpp machine used in our research, there are 2048 processors in the parallel processor array. The DECmpp can read data into each of these processors, perform a computation in parallel on all of it, and write the data out again, theoretically decreasing the execution time …

Human Creativity Through Computer Gaming, Christine Mcgavran

Dartmouth College Undergraduate Theses

No abstract provided.

Teaching Parallel Computing To Freshmen, Donald Johnson, David Kotz, Fillia Makedon

Dartmouth Scholarship

Parallelism is the future of computing and computer science and should therefore be at the heart of the CS curriculum. Instead of continuing along the evolutionary path by introducing parallel computation “top down” (first in special junior-senior level courses), we are taking a radical approach and introducing parallelism at the earliest possible stages of instruction. Specifically, we are developing a completely new freshman-level course on data structures that integrates parallel computation naturally, and retains the emphasis on laboratory instruction. This will help to steer our curriculum as expeditiously as possible toward parallel computing.

Our approach is novel in three distinct …

The Cataclysmic Variable Hx Pegasi = Pg 2337 + 123: Caught On The Rise To Maximum, F. A. Ringwald

Dartmouth Scholarship

A radial velocity study of the Hα emission line of the cataclysmic variable HX Peg = PG 2337 + 123 shows that its orbital period is 0.2008 ± 0.0005 d (4.82 h). Magnitudes from Harvard College Observatory archive plates suggest that it is either a dwarf nova or a VY Scl star. The quiescent spectrum shows KIλλ 7665, 7699 Å in absorption, consistent with the presence of an unusual subdwarf-K mass-losing star.

At the beginning of the second night of the run, O Iλ 7773 Å was in absorption. Near midnight, the continuum rose rapidly into maximum, …

Fast Greedy Triangulation Algorithms, Matthew T. Dickerson, Robert L. Scot Drysdale, Scott A. Mcelfresh, Emo Welzl

Computer Science Technical Reports

The greedy triangulation of a set $S$ of $n$ points in the plane is the triangulation obtained by starting with the empty set and at each step adding the shortest compatible edge between two of the points, where a compatible edge is defined to be an edge that crosses none of the previously added edges. In this paper we present a simple, practical algorithm that computes the greedy triangulation in expected time $O(n \log n)$ and space $O(n)$ for points uniformly distributed over any convex shape. A variant of this algorithm should be fast for some other distributions. As part …

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. Typical proposals require the single address space to contain all process-private data, shared data, and stored files. To simplify management of an address space where stale pointers make it difficult to re-use addresses, 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 …

Dynamics Of Weak First Order Phase Transitions, Marcelo Gleiser

Dartmouth Scholarship

The dynamics of weak vs. strong first order phase transitions is investigated numerically for 2+1 dimensional scalar field models. It is argued that the change from a weak to a strong transition is itself a (second order) phase transition, with the order parameter being the equilibrium fractional population difference between the two phases at the critical temperature, and the control parameter being the coefficient of the cubic coupling in the free-energy density. The critical point is identified, and a power law controlling the relaxation dynamics at this point is obtained. Possible applications are briefly discussed.

A Special Class Of Almost Disjoint Families, Thomas E. Leathrum

Dartmouth Scholarship

The collection of branches (maximal linearly ordered sets of nodes) of the tree ${}^{<\omega}\omega$ (ordered by inclusion) forms an almost disjoint family (of sets of nodes). This family is not maximal -- for example, any level of the tree is almost disjoint from all of the branches. How many sets must be added to the family of branches to make it maximal? This question leads to a series of definitions and results: a set of nodes is {\it off-branch} if it is almost disjoint from every branch in the tree; an {\it off-branch family} is an almost disjoint family of off-branch sets; ${\frak o}=\min\{|{\Cal O}|: {\Cal O}$ is a maximal off-branch family$\}$. Results concerning $\frak o$ include: (in ZFC) ${\frak a}\leq{\frak o}$, and (consistent with ZFC) $\frak o$ is not equal to any of the standard small cardinal invariants $\frak b$, $\frak a$, $\frak d$, or ${\frak c}=2^\omega$. Most of these consistency results use standard forcing notions -- for example, $Con({\frak b}={\frak a}<{\frak o}={\frak d}={\frak c})$ comes from starting with a model of $ZFC+CH$ and adding $\omega_2$-many Cohen reals. Many interesting open questions remain, though -- for example, $Con({\frak o}<{\frak d})$.

Quickest Paths: Faster Algorithms And Dynamization, Dimitrios Kagaris, Grammati E. Pantziou, Spyros Tragoudas, Christos D. Zaroliagis

Computer Science Technical Reports

Given a network $N=(V,E,{c},{l})$, where $G=(V,E)$, $|V|=n$ and $|E|=m$, is a directed graph, ${c}(e) > 0$ is the capacity and ${l}(e) \ge 0$ is the lead time (or delay) for each edge $e\in E$, the quickest path problem is to find a path for a given source--destination pair such that the total lead time plus the inverse of the minimum edge capacity of the path is minimal. The problem has applications to fast data transmissions in communication networks. The best previous algorithm for the single--pair quickest path problem runs in time $O(r m+r n \log n)$, where $r$ is the number …