Physical Sciences and Mathematics Commons^™

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 …

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 …

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 …

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 …

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.

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 …

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 …

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

Computer Science Technical Reports

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 …

An Rpc Mechanism For Transportable Agents, Saurab Nog, Sumit Chawla, David Kotz

Computer Science Technical Reports

Transportable agents are autonomous programs that migrate from machine to machine, performing complex processing at each step to satisfy client requests. As part of their duties agents often need to communicate with other agents. We propose to use remote procedure call (RPC) along with a flexible interface definition language (IDL), to add structure to inter-agent communication. The real power of our Agent RPC comes from a client-server binding mechanism based on flexible IDL matching and from support for multiple simultaneous bindings. Our agents are programmed in Agent Tcl; we describe how the Tcl implementation made RPC particularly easy to implement. …

Fast Compression Of Transportable Tcl Scripts, Robert S. Gray

Computer Science Technical Reports

An information agent is charged with the task of searching a collection of electronic resources for information that is relevant to the user's current needs. These resources are often distributed across a network and can contain tremendous quantities of data. One of the paradigms that has been suggested for allowing efficient access to such resources is transportable agents -- the agent is sent to the machine that maintains the information resource; the agent executes on this remote machine and then returns its results to the local machine. We have implemented a transportable agent system that uses the Tool Command Language …

A Performance Comparison Of Tcp/Ip And Mpi On Fddi, Fast Ethernet, And Ethernet, Saurab Nog, David Kotz

Computer Science Technical Reports

Communication is a very important factor affecting distributed applications. Getting a close handle on network performance (both bandwidth and latency) is thus crucial to understanding overall application performance. We benchmarked some of the metrics of network performance using two sets of experiments, namely roundtrip and datahose. The tests were designed to measure a combination of network latency, bandwidth, and contention. We repeated the tests for two protocols (TCP/IP and MPI) and three networks (100 Mbit FDDI (Fiber Distributed Data Interface), 100 Mbit Fast Ethernet, and 10 Mbit Ethernet). The performance results provided interesting insights into the behaviour of these networks …

Transportable Information Agents, Robert Gray, Daniela Rus, David Kotz

Computer Science Technical Reports

We have designed and implemented autonomous software agents. Autonomous software agents navigate independently through a heterogeneous network. They are capable of sensing the network configuration, monitoring software conditions, and interacting with other agents. Autonomous agents are implemented as transportable programs, e.g., programs that are capable of suspending execution, moving to a different machine, and starting from where they left off. We illustrate the intelligent behavior of autonomous agents in the context of distributed information-gathering tasks.

Compositional Reasoning Is Not Possible In Determining The Solvability Of Consensus, Prasad Jayanti

Computer Science Technical Reports

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. In our model, shared-memory consists of a sequence of cells and supports a specific set of operations. Prior research on consensus focussed on its solvability in shared-memories supporting specific operations. In this paper, we investigate the following general question: Let OP1 and OP2 be any two sets of operations such that each set includes read and write operations. Suppose there is no consensus protocol for N …