In this paper we examine the impact of router based congestion control mechanisms in the presence of uncooperative traffic. We consider two classes of control mechanisms: (1) fair queuing mechanisms (FRED, DRR, CSFQ) and (2) feedback based mechanisms (ERAF, NBP). Within the subclass of feedback based mechanisms we distinguish between binary feedback mechanisms (ERAF) and rate feedback mechanisms (NBP). The criteria we use for our comparison are: efficiency, fairness, convergence and scalability. Our results indicate that the feedback based mechanisms are able to shield responsive traffic competing with uncooperative traffic on a single link with the same efficiency as the fair queuing mechanisms. For more complex topologies, the feedback based mechanisms offer better bandwidth allocations than the fair queuing mechanisms alone.

Two techniques underlie the design of commonly used search-tree algorithms: move commonly accessed items closer to the root (move-to-front) and keep the tree balanced (keep-it-balanced). The move-to-front technique tries to improve the performance for the common case by reducing the number of operations required to retrieve commonly accessed items. The keep-it-balanced technique tries to improve worst-case performance by reducing the maximum number of operations required to look up an item in the tree. In this paper, we evaluate these techniques in the presence of a cache hierarchy. As representatives of move-to-front algorithms we use splay trees. As representatives of keep-it-balanced algorithms we use B-Trees and B*-Trees. In addition to classic versions of these techniques, we evaluate variants that have been optimized for a cache hierarchy. To drive our evaluation, we use a suite of synthetic datasets that were constructed to elucidate the dierences between these techniques. These datasets vary primarily in the degree of locality found in the request stream and the operation mix. The major result of this paper is a qualitative performance dierence analysis of the two classes of algorithms based on the expected data input characteristics. Based on this analysis we can predict which algorithm performs faster for a large class of input datasets. We also present guidelines for choosing implementation parameters in the presence of a cache hierarchy for all algorithms considered. I.

Growth and usage trends for large decision support databases indicate that there is a need for architectures that scale the processing power as the dataset grows. To meet this need, several researchers have recently proposed active disk architectures which integrate substantial processing power and memory into disk units. In this paper, we evaluate Active Disks for decision support databases. First, we compare the performance of Active Disks with that of existing scalable server architectures: SMP-based conventional disk farms and commodity clusters of PCs. Second, we evaluate the impact of several design choices on the performance of Active Disks. We focus on the performance impact of interconnect bandwidth, amount of disk memory and disk-to-disk communication architecture on decision support workloads. Our results show that for identical disks, number of processors and I/O interconnect, Active Disks provide better price/performance than both SMP-based conventional disk farms and commodity cluster. Experiments evaluating the impact of design alternatives in Active Disk architectures indicate that: (1) for configurations up to 64 disks, a dual fibre channel arbitrated loop interconnect is sufficient even for the most communication-intensive decision support tasks: (2) most decision support task do not require a large amount of memory: and (3) direct disk-to-disk communication is necessary for achieving good performance on tasks that repartition all (or a large fraction of) their dataset.

In this paper, we present the design and implementation of Dodo, an efficient user-level system for harvesting idle memory in off-the-shelf clusters of workstations. Dodo enables data-intensive applications to use remote memory in a cluster as an intermediate cache between local memory and disk. It requires no modifications to the operating system and/or processor firmware and is hence portable to multiple platforms. Further, the memory recruitment policy used by Dodo is designed to minimize any delays experienced by the owner of desktop machines whose memory is harvested by Dodo. Our implementation of Dodo is operational and currently runs on Linux 2.0.35. For communication, Dodo can use either UDP/IP or U-Net, the low-latency user-level network architecture developed by von Eicken et al. (1995). We evaluated the performance improvements that can be achieved by using Dodo for two real applications and three synthetic benchmarks. Our results show that speedups obtained for an application are highly dependent on its I/O access pattern and data set sizes. Significant speedups (between 2 and 3) were obtained for applications whose working sets are larger than the local memory on a workstation but smaller than aggregate memory available on the cluster and for applications that can benefit from the zero-seek nature of remote memory.

We propose router mechanisms to regulate unresponsive best-effort traffic. By unresponsive traffic we mean flows that do not reduce their sending rate in response to congestion. The goal of the proposed mechanisms is to drop undeliverable packets as close to the periphery of the network as possible. The key ideas of our approach are: (1) edge routers keep track of incoming flows and their arrival rates; (2) core routers use random early detection (RED) for queue management and generate rate-limited source quenches on packet drops to advice sources to reduce their sending rates; and (3) edge routers snoop an source quenches passing through them and use them to control per-flow regulators. Regulators adjust their maximum sending rate using a multiplicative-decrease, additive-increase discipline. A decrease is triggered by the arrival of a source quench; an increase is triggered by non-arrival of source quenches for a time period. We examine the impact of these mechanisms for a variety of simulated network topologies and traffic patterns.

In this paper, we examine the availability and utility of idle memory in workstation clusters.We attempt to answer the following questions.First, how much of the total memory in a workstation cluster can be expected to be idle?This provides an estimate of the opportunity for hosting guest data.Second, how much memory can be expected to be idle on individual workstations?This helps determine the recruitment policy -how much memory should be recruited on individual hosts?Third, what is the distribution of memory idle-times?This indicates how long guest data can be expected to survive; applications that access their data-sets frequently within the expected life-time of guest data are more likely to benefit from exploiting idle memory.Fourth, how much performance improvement can be achieved for offthe-shelf clusters without customizing the operating system and/or the processor firmware?Finally, how long and how frequently might a user have to wait to reclaim her machine if she volunteers to host guest pages on her machine?This helps answer the question of social acceptability.To answer the questions relating to the availability of idle memory, we have analyzed two-week long traces from two workstation pools with different sizes, locations, and patterns of use.To evaluate the expected benefits and costs, we have simulated five data-intensive applications (0.5 GB-5 GB) on these workstation pools.

Several application and technology trends indicate that it might be both profitable and feasible to move computation closer to the data that it processes. In this paper, we evaluate Active Disk architectures which integrate significant processing power and memory into a disk drive and allow application-specific code to be downloaded and executed on the data that is being read from (written to) disk. The key idea is to offload bulk of the processing to the diskresident processors and to use the host processor primarily for coordination, scheduling and combination of results from individual disks. To program Active Disks, we propose a stream-based programming model which allows disklets to be executed efficiently and safely. Simulation results for a suite of six algorithms from three application domains (commercial data warehouses, image processing and satellite data processing) indicate that for these algorithms, Active Disks outperform conventional-disk architectures.

. In this chapter, we present a history-based access-control mechanism that is suitable for mediating accesses from mobile code. The key idea behind history-based access-control is to maintain a selective history of the access requests made by individual programs and to use this history to improve the differentiation between safe and potentially dangerous requests. What a program is allowed to do depends on its own behavior and identity in addition to currently used discriminators like the location it was loaded from or the identity of its author/provider. History-based access-control has the potential to significantly expand the set of programs that can be executed without compromising security or ease of use. We describe the design and implementation of Deeds, a history-based access-control mechanism for Java. Access-control policies for Deeds are written in Java, and can be updated while the programs whose accesses are being mediated are still executing. 1 Introduction...

Efficient data combination over wide area networks is hard as these networks have large variations in available bandwidth. We examine the utility of changing the location of combination operations as a technique to adapt to variations in network bandwidth. We try to answer the following questions. First, does relocation of operators provide a significant performance improvement? Second, is online relocation useful or does a one-time positioning at start-up time provide most if not all the benefits? If online relocation is useful, how frequently should it be done and is global knowledge of network performance required or can local knowledge and local relocation of operators be sufficient? Fourth, does the effectiveness of operator relocation depend on the ordering of the combination operations. That is, are certain ways of ordering more amenable to adaptation than others? Finally, how do the results change as the number of data sources changes?.

No abstract available.

There are two major challenges for a high performance remote sensing database. First, it must provide low latency retrieval of very large volumes of spatio temporal data. This requires effective declustering and placement of a multidimensional dataset onto a large disk farm. Second, the order of magnitude reduction in data size due to post processing makes it imperative, from a performance perspective, that the post processing be done on the machine that holds the data. This requires careful coordination of computation and data retrieval. The paper describes the design, implementation and evaluation of Titan, a parallel shared nothing database designed for handling remote sensing data. The computational platform for Titan is a 16 processor IBM SP-2 with four fast disks attached to each processor. Titan is currently operational and contains about 24 GB of AVHRR data from the NOAA-7 satellite. The experimental results show that Titan provides good performance for global queries and interactive response times for local queries.

In this paper, we examine the utility of exploiting idle workstations for parallel computation. We attempt to answer the following questions. First, given a workstation pool, for what fraction of time can we expect to find a cluster of $k$ workstations available? This provides an estimate of the opportunity for parallel computation. Second, how stable is a cluster of free machines and how does the stability vary with the size of the cluster? This indicates how frequently a parallel computation might have to stop for adapting to changes in processor availability. Third, what is the distribution of workstation idle-times? This information is useful for selecting workstations to place computation on. Fourth, how much benefit can a user expect? To state this in concrete terms, if I have a pool of size S, how big a parallel machine should I expect to get for free by harvesting idle machines. Finally, how much benefit can be achieved on a real machine and how hard does a parallel programmer have to work to make this happen? To answer the workstation-availability questions, we have analyzed 14-day traces from three workstation pools. To determine the equivalent parallel machine, we have simulated the execution of a group of well-known parallel programs on these workstation pools. To gain an understanding of the practical problems, we have developed the system support required for adaptive parallel programs as well as an adaptive parallel CFD application. (Also cross-referenced as UMIACS-TR-96-80)

In this paper we outline some potential applications of resource-aware scheduling to high-performance metacomputing applications and describe requirements associated with the use of mobility for resource-aware scheduling. Programs that use mobility as a mechanism to adapt to resource changes have three requirements that are not shared with other mobile programs. Firstly, they need to monitor the level and quality of resources in their operating environment. Secondly, they need to be able to react to changes in resource availability. Thirdly, they need to be able to control the way in which resources are used on their behalf (by libraries and other support code). In this paper, we describe the design and implementation of Sumatra, an extension of Java that supports resource-aware mobile programs. We also describe the design and implementation of a distributed resource monitor that provides the information required by Sumatra programs. Finally, we present a prototype resource-aware data intensive program that combines and composes weather images from multiple geographically distributed sources. © 1997 John Wiley & Sons, Ltd.

A rule-based program consists of a set of if-then rules and a tuple-space. The rules are the code for the program and the tuple-space contains the data being processed by the program. Previous efforts to parallelize rule-based programs have achieved limited speedups. The main reason for these disappointing results is a high frequency of barrier synchronizations. Since little work is done between successive barrier synchronizations, the number of processors that can be effectively utilized is bounded. Even though required by language semantics, a large fraction of the barrier synchronizations are not necessary for most programs. This paper proposes a pair of simple language extensions that allow an implementation to efficiently detect and eliminate redundant barrier synchronizations. Simulation results based on a real implementation show that for a set of five benchmarks, this scheme is able to eliminate between 95.6% and 99.9% of the barrier synchronizations. This results in a multipli...

Overlapping memory accesses with computations is a standard technique for improving performance on modern architectures, which have deep memory hierarchies. In this paper, we present a compiler technique for overlapping accesses to secondary memory (disks) with computation. We have developed an Interprocedural Balanced Code Placement (IBCP) framework, which performs analysis on arbitrary recursive procedures and arbitrary control flow and replaces synchronous I/O operations with a balanced pair of asynchronous operations. We demonstrate how this analysis is useful for applications which perform frequent and large accesses to secondary memory, including applications which snapshot or checkpoint their computations or out-of-core applications. 1 Introduction Modern architectures have large number of memory hierarchies. Processors have one or two levels of cache, followed by primary memory (RAM), secondary memory (disks) and tertiary memory. The cost of data access increases rapidly with ...

\f e conslcier the problem of efficiently couphrrg multiple cfataparakl programs at Irrntime.We propose an approach that establishes mappings between data structures m different flat a-parallel programs and implements a user-specified com wmencv model.Mappings are established at rnntlrne and can be added and deleted while the programs being coupled are in execution.Mappings, or the icleutity of the processors involved, do not ha~,r TObe kno~vn at compile-time or even link-time.Pro,gramh ran be m adc to interact tvith different granularities of interaction without requiring any re-cociing.A-priori knowledge of consistency requirements allows buffering of data as well as concurrent execution of the coupled applications.Efficient data movement is achii=w=d b~-p] e-computing an optimized schedule.~~e describe our ])lorotype mrpiernent,atiou and evaluate lts performance us-LMga wt of svnthetrc "benchmarks.\Ve examme the varlat]on of performance with varlatlon in t he conslstenc} reqrrme-[nent W+ demonstrate That the cost of' the tlexibiht}-pro-~,lded hl our coupling scheme is not prolubltl~,e whel L ronpared with a monolithic program that performs the sam~ computatlou.1

Article Free Access Share on Collection oriented match Authors: Anurag Acharya School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PAView Profile , Milind Tambe School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PAView Profile Authors Info & Claims CIKM '93: Proceedings of the second international conference on Information and knowledge managementDecember 1993 Pages 516–526https://doi.org/10.1145/170088.170411Published:01 December 1993Publication History 4citation319DownloadsMetricsTotal Citations4Total Downloads319Last 12 Months25Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Considerable work has been done on parallelizing compilers for production languages, but the results are inadequate for tasks with large-scale parallelism. It is argued that explicitly parallel production languages are necessary for such tasks. PPL (Parallel Production Language), an explicitly parallel production language, is described. PPL is closely related to the OPS family of languages and is based primarily on OPS5.>

The authors examine the suitability of message-passing computers for parallel implementations of production systems. Two mappings for production systems on these computers, one targeted toward fine-grained message-passing machines and the other targeted toward medium-grained machines, are presented. Simulation results for the medium-grained mapping are presented, and it is shown that it is possible to exploit the available parallelism and to obtain reasonable speedups. The authors perform a detailed analysis of the results and suggest solutions for some of the problems.>

One of the techniques used to tackle the increasing complexity of testing VLSI circuits is to incorporate built-in self-test (BIST) structures. However, incorporation of such BIST structures calls for increased area overhead due to additional logic gates and interconnections. It is very important to keep this area overhead to a minimum. The authors present a simple graph model of the area overhead minimization problem, for circuits into which BIST modifications are to be incorporated. Although the graph model does not account for a mixed type of BIST structure usage, it can be extended to include them at the cost of increased complexity.>