While it has long been recognized that a team of individual learning agents can be greater than the sum of its parts, recent work has shown that larger teams are not necessarily more effective than smaller ones. In this paper, we study why and under which conditions certain team structures promote effective learning for a population of individual learning agents. We show that, depending on the environment, some team structures help agents learn to specialize into specific roles, resulting in more favorable global results. However, large teams create credit assignment challenges that reduce coordination, leading to large teams performing poorly compared to smaller ones. We support our conclusions with both theoretical analysis and empirical results.

For problems requiring cooperation, many multiagent systems implement solutions among either individual agents or across an entire population towards a common goal. Multiagent teams are primarily studied when in conflict; however, organizational psychology (OP) highlights the benefits of teams among human populations for learning how to coordinate and cooperate. In this paper, we propose a new model of multiagent teams for reinforcement learning (RL) agents inspired by OP and early work on teams in artificial intelligence. We validate our model using complex social dilemmas that are popular in recent multiagent RL and find that agents divided into teams develop cooperative pro-social policies despite incentives to not cooperate. Furthermore, agents are better able to coordinate and learn emergent roles within their teams and achieve higher rewards compared to when the interests of all agents are aligned.

WiFi backscatter communication has been proposed to enable battery-free sensors to transmit data using WiFi networks. The main advantage of WiFi backscatter technologies over RFID is that data from their tags can be read using existing WiFi infrastructures instead of specialized readers. This can potentially reduce the complexity and cost of deploying battery-free sensors. Despite extensive work in this area, none of the existing systems are in widespread use today. We hypothesize that this is because WiFi-based backscatter tags do not scale well and their range and capabilities are limited when compared with RFID. To test this hypothesis we conduct several real-world experiments.

MAC-layer frame aggregation has significantly improved the efficiency of IEEE 802.11n/ac networks by placing multiple MAC-layer data units in a large PHY-layer frame. In this paper, we focus on finding the optimal length of an Aggregated MAC Protocol Data Unit (A-MPDU) in order to maximize throughput. This problem has proved to be extremely challenging because of the chain of dependencies between consecutive A-MPDUs due to software retransmissions and because error rates can be higher in the later part of the A-MPDU.

Although a variety of rate adaptation algorithms have been proposed for 802.11 networks, sampling-based algorithms are preferred and used in practice because they only require frame loss information which is available on all devices. Unfortunately, sampling can impose significant overheads because it may lead to excessive frame loss or the inefficient operation of frame aggregation algorithms. In this paper, we design a novel Neural network-based Rate Adaptation algorithm, called NeuRA. NeuRA, significantly improves the efficiency of probing in sampling-based algorithms by using neural network models to predict the expected throughput of many rates,rather than sampling their throughput.

WiFi backscatter communication has the potential to enable battery-free sensors which can transmit data using a WiFi network. In order for WiFi backscatter systems to be practical they should be compatible with existing WiFi networks without any hardware or software modifications. Moreover, they should work with networks that use encryption. In this paper, we present WiTAG which achieves these requirements, making the implementation and deployment of WiFi backscatter communication more practical. In contrast with existing systems which utilize the physical layer for backscatter communication, we take a different approach by leveraging features of the MAC layer to communicate. WiTAG is designed to send data by selectively interfering with subframes (MPDUs) in an aggregated frame (A-MPDU). This enables standard compliant communication using modern, open or encrypted 802.11n and 802.11ac networks without requiring hardware or software modifications to any devices. We implement WiTAG using off-the-shelf components and evaluate its performance in line-of-sight and non-line-of-sight scenarios. We show that WiTAG achieves a throughput of up to 4 Kbps without impacting other devices in the network.

Despite the ubiquity of WiFi devices, Bluetooth is widely used for communication in low-power, low data-rate devices. This is because Bluetooth consumes much less power than WiFi which results in longer battery life. The higher power consumption of WiFi devices is due to overheads from either establishing or maintaining connections with the access point. Surprisingly, Bluetooth devices require nearly three times as much energy to transmit a bit of data at the physical layer than WiFi devices.

WiFi-based backscatter systems provide the potential to deliver battery-free sensors (tags) which can transmit data using a WiFi network. Existing backscatter systems have several problems which make them impractical to deploy and operate using existing WiFi networks. First, they require software or hardware modifications to WiFi access points and devices. Second, they do not work with WiFi networks that use a security protocol such as WPA. Third, they interfere with existing WiFi communication because they reflect their signal to another channel without implementing channel sensing. In this paper, we present WiTAG which addresses these problems, making the implementation and deployment of backscatter systems significantly more practical. In contrast with existing systems that build tags to communicate using the physical layer, we take a radically different approach by building tags that leverage features of the MAC layer to communicate. We design tags which can selectively interfere with subframes (MPDUs) in an aggregated frame (A-MPDU). This enables standard compliant communication using modern 802.11n and 802.11ac networks with minimal infrastructure and without requiring hardware or software modifications to any devices. The evaluation of our prototype system shows that with a client and an access point that are 8 meters apart, a tag can achieve data rates of 40 Kbps when located anywhere between the two devices.

The IEEE 802.11 standard has become the dominant protocol for Wireless Local Area Networks (WLANs). In a span of 20 years, the speed of these networks has increased from 1 Mbps to more than 1 Gbps. Today's Wi-Fi networks may consist of a variety of client devices, ranging from slow legacy 802.11a/b/g to modern and fast 802.11n/ac devices. We describe preliminary findings from a large-scale study obtained from 448 Google Wifi and Google OnHub access points with 2,975 clients. We focus on characterizing the maximum achievable bitrate of heterogeneous wireless links. We also determine the average physical-layer bitrate used on the down link (AP to client) and compare it with the maximum supported bitrate. We find that about 75% of 802.11n and 50% of 802.11ac client devices operate at 75% of their maximum or more and that the bitrates of the remaining devices can be very far from their maximum. These low bitrates could significantly reduce the throughput of high-bitrate devices.

The trend towards global applications and services has created an increasing demand for transaction processing on globally-distributed data. Many database systems, such as Spanner and CockroachDB, support distributed transactions but require a large number of wide-area network roundtrips to commit each transaction and ensure the transaction's state is durably replicated across multiple datacenters. This can significantly increase transaction completion time, resulting in developers replacing database-level transactions with their own error-prone application-level solutions.

Previous work has shown that benchmark and application performance in public cloud computing environments can be highly variable. Utilizing Amazon EC2 traces that include measurements affected by CPU, memory, disk, and network performance, we study commonly used methodologies for comparing performance measurements in cloud computing environments. The results show considerable flaws in these methodologies that may lead to incorrect conclusions. For instance, these methodologies falsely report that the performance of two identical systems differ by 38% using a confidence level of 95%. We then study the efficacy of the Randomized Multiple Interleaved Trials (RMIT) methodology using the same traces. We demonstrate that RMIT could be used to conduct repeatable experiments that enable fair comparisons in this cloud computing environment despite the fact that changing conditions beyond the user's control make comparing competing alternatives highly challenging.

Video streaming applications generate a large fraction of Internet traffic. Much of this content is delivered over HTTP using standard web servers. Unlike other types of web workloads, HTTP video streaming workloads are typically disk bound, and therefore an important problem is that of optimizing disk access.

Key-value storage systems are an integral part of many data centre applications, but as demand increases so does the need for high performance. This has motivated new designs that use Remote Direct Memory Access (RDMA) to reduce communication overhead. Current RDMA-enabled key-value stores (RKVSes) target workloads involving small values, running on dedicated servers on which no other applications are running. Outside of these domains, however, there may be other RKVS designs that provide better performance. In this paper, we introduce Nessie, an RKVS that is fully client-driven, meaning no server process is involved in servicing requests. Nessie also decouples its index and storage data structures, allowing indices and data to be placed on different servers. This flexibility can decrease the number of network operations required to service a request. These design elements make Nessie well-suited for a different set of workloads than existing RKVSes. Compared to a server-driven RKVS, Nessie more than doubles system throughput when there is CPU contention on the server, improves throughput by 70 percent for PUT-oriented workloads when data value sizes are 128 KB or larger, and reduces power consumption by 18 percent at 80 percent system utilization and 41 percent at 20 percent system utilization compared with idle power consumption.

To increase throughput the 802.11n standard introduced several physical layer transmission features including a short guard interval wider channels, and MIMO. Since obtaining peak throughput depends on choosing the combination of physical layer features (configuration) best suited for the channel conditions, the large number of configurations greatly complicates the decision. A deeper understanding of relationships between configurations under a variety of channel conditions should simplify the choices and improve the performance of algorithms selecting configurations. Examples of such algorithms include: rate and channel width adaptation, frame aggregation, and MIMO setting optimization.

In this paper, we describe the design, implementation and evaluation of a new framework for the trace-based evaluation of 802.11n networks, which we call T-SIMn. We first develop novel techniques for collecting and processing traces for 802.11n networks that incorporate Frame Aggregation (FA). We then demonstrate that the simulator portion of our framework (SIMn) accurately simulates throughput for one, two and three-antenna Physical Layer Data Rates in 802.11n with FA. Finally, we evaluate the T-SIMn framework (including trace collection) by collecting traces using an iPhone which is representative of a wide variety of one antenna devices. We show that our framework can be used to accurately simulate these scenarios and we demonstrate the fidelity of SIMn by uncovering problems with our initial evaluation methodology. We expect that the T-SIMn framework will be suitable for easily and fairly comparing algorithms that must be optimized for different and varying 802.11n channel conditions which are challenging to evaluate experimentally. These include rate adaptation, frame aggregation and channel bandwidth adaptation algorithms. git

Typical VM consolidation approaches re-pack VMs into fewer physical machines, resulting in energy and cost savings [13, 19, 23, 40]. Recent work has explored a just-in time approach to VM consolidation by transitioning VMsto an inactive state when idle and activating them on the arrival of client requests[17, 21]. This leads to increased VM density at the cost of an increase in client request latency (called miss penalty). The VM density so obtained, although greater, is still limited by the number of VMs that can be hosted in the one inactive state. If idle VMs were hosted in multiple inactive states, VM density can be increased further while ensuring small miss penalties. However, VMs in different inactive states have different capacities, activation times, and resource requirements.

Rate adaptation algorithms (RAAs) in 802.11 networks can have a significant impact on network throughput. In order to attempt to maximize throughput, these algorithms dynamically adapt to inferred changes in the channel being used. Evaluating and comparing rate adaptation algorithms is extremely challenging due to the variability of channel conditions. Recent work on developing and evaluating new RAAs has used traces to increase the realism of simulators. We propose a new framework for the trace-driven evaluation of RAAs (called T-RATE) in which we collect and process traces in environments where interference is caused by WiFi and non-WiFi devices. T-RATE enables a more comprehensive evaluation of RAAs in environments that are representative of those in which 802.11 devices are actually used. A key to our approach is that we capture, in traces, information that is relevant to RAAs regarding how channel conditions affect channel access and channel error rates. Our approach minimizes the use of wireless channel models and achieves highly realistic results under a wider variety of scenarios than previously possible. Our evaluation of T-RATE demonstrates it can be used to collect and process traces to accurately evaluate a variety of RAAs under more diverse and representative channel conditions than previously possible.

Past work has shown that disk prefetching can be an effective technique for improving the performance of disk bound workloads. However, the performance gains are highly dependent on selecting a prefetch size that is appropriate for a specific system and workload. Using a prefetch size that is too small can lead to poor overall disk throughput, whereas prefetch sizes that are too large can lead to data being evicted before it can be used by a subsequent request.

Large amounts of Internet streaming video traffic are being delivered using HTTP to leverage the existing web infrastructure. A fundamental issue in HTTP streaming concerns the granularity of video objects used throughout the HTTP ecosystem (including clients, proxy caches, CDN nodes, and servers). A video may be divided into many files (called chunks), each containing only a few seconds of video at one extreme, or stored in a single unchunked file at the other.

In this paper, we study how web-server architecture and implementation affect performance when trying to obtain high throughput on a 4-core system servicing static content. We focus on static content as a growing numbers of servers are dedicated to workloads comprised of songs, photos, software, and videos chunked for HTTP downloads. Two representative static-content workloads are used: one serviced entirely from the file-system cache and the other requires significant disk I/O. We focus on 4-core systems as: 1) it is a widely used configurations in data-centers and cloud services, 2) recent studies show large SMP systems may operate more efficiently when subdivided into smaller subsystems, 3) understanding performance with a smaller number of cores is essential before scaling to a larger number of cores, 4) and 4-cores may be sufficient for many web servers.

Recent increases in live and on-demand video streaming have dramatically changed the Internet landscape. In North America, Netflix alone accounts for 28% of all and 33% of peak downstream Internet traffic on fixed access links, with further rapid growth expected [26]. This increase in streaming traffic coincides with the steady adoption of HTTP for use in video streaming. Many streaming video providers, such as Apple, Adobe, Akamai, Netflix and Microsoft, now use HTTP to stream content [5]. Therefore, it is critical that we understand the impact of this emerging workload on web servers. Unlike other web content, a recent study [13] of streaming video shows that even small infrequent latency spikes, manifested as buffering related pauses, can result in shorter viewing times especially during live broadcasts. Unfortunately, no appropriate benchmarks exist to evaluate web servers under HTTP video streaming workloads.

In three-tiered web applications, some form of admission control is required to ensure that throughput and response times are not significantly harmed during periods of heavy load. We propose Q-Cop, a prototype system for improving admission control decisions that considers a combination of the load on the system, the number of simultaneous queries being executed, the actual mix of queries being executed, and the expected time a user may wait for a reply before they or their browser give up (i.e., time out). Using TPC-W queries, we show that the response times of different types of queries can vary significantly depending not just on the number of queries being processed but on the mix of other queries that are running simultaneously. We develop a model of expected query execution times that accounts for the mix of queries being executed and integrate this model into a three-tiered system to make admission control decisions. Our results show that this approach makes more informed decisions about which queries to reject and as a result significantly reduces the number of requests that time out. Across the range of workloads examined an average of 47% fewer requests are unsuccessful than the next best approach.

Kernel-based group unicast has been suggested as an efficient mechanism for transmitting the same data to multiple recipients. In this paper, we present a new system call, sendgroup(), which also supports per-recipient private data, but only uses a single inkernel copy of the shared data. We assess the performance of the new system call using micro-benchmarks on three different operating systems. Further, we incorporate sendgroup() into a popular multimedia server and demonstrate an efficiency improvement of ~45% in a representative live-broadcasting scenario. These results show that the new system call is applicable in real-world scenarios, and that its usage can lead to significant performance improvements. Moreover, we demonstrate how Amdahl's Law, when applied to the results of the micro-benchmarks, along with precise analysis of the cost of sending packets, can be used to accurately predict the impact of sendgroup() on this server.

Abstract Babylon is a collection of tools and services that provide a 100% Java‐compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features such as object migration, asynchronous method invocation, and remote class loading, while providing an easy‐to‐use interface. Additionally, Babylon enables Java applications to seamlessly create and interact with remote objects, while protecting those objects from other applications by implementing access restrictions and separate namespaces. The implementation of Babylon centers around dynamic proxies, a feature first available in Java 1.3, that allow proxy objects to be created at runtime. Dynamic proxies play a key role in achieving the goals of Babylon. The potential cluster computing benefits of the system are demonstrated with experimental results, which show that sequential Java applications can achieve significant performance benefits from using Babylon to parallelize their work across a cluster of workstations. Copyright © 2008 John Wiley & Sons, Ltd.

In this paper, we extensively tune and then compare the performance of web servers based on three different server architectures. The μserver utilizes an event-driven architecture, Knot uses the highly-efficient Capriccio thread library to implement a thread-per-connection model, and WatPipe uses a hybrid of events and threads to implement a pipeline-based server that is similar in spirit to a staged event-driven architecture (SEDA) server like Haboob.

We consider the problem of providing vehicular Internet access using roadside 802.11 access points. We build on previous work in this area [18, 8, 5, 11] with an extensive experimental analysis of protocol operation at a level of detail not previously explored. We report on data gathered with four capture devices from nearly 50 experimental runs conducted with vehicles on a rural highway. Our three primary contributions are: (1) We experimentally demonstrate that, on average, current protocols only achieve 50% of the overall throughput possible in this scenario. In particular, even with a streamlined connection setup procedure that does not use DHCP, high losses early in a vehicular connection are responsible for the loss of nearly 25% of overall throughput, 15% of the time. (2) We quantify the effects of ten problems caused by the mechanics of existing protocols that are responsible for this throughput loss; and (3) We recommend best practices for using vehicular opportunistic connections. Moreover, we show that overall throughput could be significantly improved if environmental information was made available to the 802.11 MAC and to TCP. The central messagein this paper is that wireless conditions in the vicinity of a roadside access point are predictable, and by exploiting this information, vehicular opportunistic access can be greatly improved.

Applications requiring high-speed TCP/IP processing can easily saturate a modern server. We and others have previously suggested alleviating this problem in multiprocessor environments by dedicating a subset of the processors to perform network packet processing. The remaining processors perform only application computation, thus eliminating contention between these functions for processor resources. Applications interact with packet processing engines (PPEs) using an asynchronous I/O (AIO) programming interface which bypasses the operating system. A key attraction of this overall approach is that it exploits the architectural trend toward greater thread-level parallelism in future systems based on multi-core processors. In this paper, we conduct a detailed experimental performance analysis comparing this approach to a best-practice configured Linux baseline system.

Babylon v2.0 is a collection of tools and services that provide a 100% Java compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features like object migration, asynchronous method invocation and remote class loading while providing an easy-to-use interface. Additionally, Babylon v2.0 enables Java applications to seamlessly create and interact with remote objects while protecting those objects from other applications by implementing access restrictions and separate name spaces. This paper describes the most important programming features of the Babylon v2.0 system, using a heat diffusion example to show how they are used in practice. The potential cluster computing benefits of the system are demonstrated with experimental results which show that sequential Java applications can achieve significant performance benefits from using Babylon v2.0 to parallelize their work across a cluster of workstations

Babylon v2.0 is a collection of tools and services that provide a 100% Java compatible environment for developing, running and managing parallel, distributed and mobile Java applications. It incorporates features like object migration, asynchronous method invocation and remote class loading while providing an easy-to-use interface. The implementation of Babylon v2.0 exploits dynamic proxies, a feature added to Java 1.3 that allows runtime creation of proxy objects. This paper shows how Babylon v2.0 exploits dynamic proxies to implement several key features without the need for special language or virtual machine extensions, preprocessors, or compilers. The resulting Babylon programs are portable across all Java virtual machines, and the development process is simplified by removing the extra steps needed to invoke external stub compilers and incorporate the generated code into an application. This simplification also allows remote objects to be created for any class that supports an interface to its methods, even if source code is not available

virtual environment (DVE) have become increasingly popular. Many DVE implementations use a client-server architecture that requires the server to send the same data to all members of a collaborating or interacting group. This type of group communication operation is often implemented by sending data from the server to each recipient in a unicast fashion. The problem with this approach is that the cost of communication at the server does not scale very well with the number of participants because the application requires significant interaction with the operating system, network stack and drivers for each individual send. In this paper, we first propose a general analytic framework for predicting how group communication performance impacts DVE server capacity. We then conduct an experimental evaluation to determine the extent to which using a kernel-based group communication mechanism reduces the cost of group send operations. Lastly, we use the measurements obtained from these experiments to demonstrate how to apply the analytic framework by determining the extent to which the kernel-based group communication mechanism permits example applications to scale to more users.

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not collecting much garbage during each cycle. On the other hand, collecting garbage too infrequently can result in applications that execute with a large amount of virtual memory (i.e., with a large footprint) and suffer from increased execution times due to paging.In this article, we use a large set of Java applications and the highly tuned and widely used Boehm-Demers-Weiser (BDW) conservative mark-and-sweep garbage collector to experimentally examine the extent to which the frequency of garbage collection impacts an application's execution time, footprint, and pause times. We use these results to devise some guidelines for controlling garbage collection and heap growth in a conservative garbage collector in order to minimize application execution times. Then we describe new strategies for controlling garbage collection and heap growth that impact not only the frequency with which garbage collection occurs but also the points at which it occurs. Experimental results demonstrate that when compared with the existing approach used in the standard BDW collector, our new strategy can significantly reduce application execution times.Our goal is to obtain a better understanding of how to control garbage collection and heap growth for an individual application executing in isolation. These results can be applied in a number of high-performance computing and server environments, in addition to some single-user environments. This work should also provide insights into how to make better decisions that impact garbage collection in multiprogrammed environments.

A common requirement of many Internet services is to send exactly the same data to a number of hosts at the same time. Without IP-level multicast, this form of group communication is realized by unicasting the data to each desired host. Although this approach is portable and easy to implement, it is extremely inefficient for the sending host. In this paper, we propose a kernel-based technique to efficiently facilitate unicast send operations for group communication with only minimal additions to the sending operating system interface and implementation. We present the design and prototype implementation of our approach and experimentally demonstrate the significant performance improvements it provides. Additionally, we conduct experiments to decompose the processing costs in the network stack and show that the biggest cost reductions are not necessarily due to reduced memory copying.

In systems that support garbage collection a tension exists between collecting garbage too frequently and not collecting garbage frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not collecting much garbage during each cycle. On the other hand, collecting garbage too infrequently can result in applications that execute with a large amount of virtual memory (i.e., with a large footprint) and suffer from increased execution times due to paging. In this paper we use a large collection of Java applications and the highly tuned and widely used BoehmDemers -Weiser conservative garbage collector to experimentally examine the extent to which the frequency of garbage collection impacts an application's execution time, footprint, and pause times. We use these results to devise some guidelines for controlling garbage collection and heap growth in a conservative garbage collector in order to minimize application execution times. Then we describe new strategies for controlling garbage collection and heap growth that impact not only the frequency with which garbage collection occurs but also the points at which garbage collection occurs. Experimental results demonstrate that when compared with the existing approach our new strategy can significantly reduce application execution times. 1

This paper introduces time-lined TCP (TLTCP). TLTCP is a protocol designed to provide TCP-friendly delivery of time-sensitive data to applications that are loss-tolerant, such as streaming media players. Previous work on unicast delivery, of streaming media over the Internet proposes using UDP and performs congestion control at the user level by regulating the application's sending rate. TLTCP, on the other hand is intended to be implemented at the transport level, and is based on TCP with modifications to support time-lines. Instead of treating all data as a byte stream TLTCP allows the application to associate data with deadlines. TLTCP sends data in a similar fashion to TCP with the deadline for a section of data has elapsed; at which point the now obsolete data is discarded in favor of new data. As a result, TLTCP supports TCP-friendly delivery of streaming media by retaining much of TCP's congestion control functionality. We describe an API for TLTCP that involves augmenting the recvmsg and sendmsg socket calls. We also describe how streaming media applications that use various encoding schemes like MPEG-1 can associate data with deadlines and use TLTCP's API. We use simulations to examine the behavior of TLTCP under a wide range of networks and workloads. We find that it indeed performs time-lined data delivery and under most circumstances the bandwidth is shared equally, among completing TLTCP and TCP flows. Moreover those scenarios under which TLTCP appears to be unfriendly are those under which TCP flows competing only with other TCP flows do not share bandwidth equitably.

The rapid proliferation of the World-Wide Web has been due to the seamless access it provides to information that is distributed both within organizations and around the world. In this paper, we describe the design and implementation of a system, called Ajents, which provides the software infrastructure necessary to support a similar level of seamless access to organization-wide or world-wide heterogeneous computing resources. Ajents introduces class libraries which are written entirely in Java and that run on any standard compliant Java virtual machine. These class libraries implement and combine several important features that are essential to supporting distributed and parallel computing using Java. These features include: the ability to easily create objects on remote hosts, to interact with those objects through either synchronous or asynchronous remote method invocations, and to freely migrate objects to heterogeneous hosts. While some of these features have been implemented in other systems, Ajents provides support for the combination of all of these features using techniques that permit them to operate together in a fashion that is more transparent and/or and less restrictive than existing systems. Our experimental results show that in our test environment: we are able to achieve good speedup on a sample parallel application; the overheads introduced by our implementation do not adversely affect remote method invocation times; and (somewhat surprisingly) the cost of migration does not greatly impact the execution time of an example application. Copyright © 2000 John Wiley & Sons, Ltd.

We study the problem of processor scheduling for n parallel jobs applying the method of competitive analysis. We prove that for jobs with a single phase of parallelism, a preemptive scheduling algorithm without information about job execution time can achieve a mean completion time within $2-{2\over n+1}$ times the optimum. In other words, we prove a competitive ratio of $2-{2\over n+1}$. The result is extended to jobs with multiple phases of parallelism (which can be used to model jobs with sublinear speedup) and to interactive jobs (with phases during which the job has no CPU requirements) to derive solutions guaranteed to be within $4-{4\over n+1}$ times the optimum. In comparison with previous work, our assumption that job execution times are unknown prior to their completion is more realistic, our multiphased job model is more general, and our approximation ratio (for jobs with a single phase of parallelism) is tighter and cannot be improved. While this work presents theoretical results obtained using competitive analysis, we believe that the results provide insight into the performance of practical multiprocessor scheduling algorithms that operate in the absence of complete information.

A multiprocessor system is unlikely to have access to information about the execution characteristics of the jobs it is to schedule. In this work, we are interested in scheduling algorithms for batch jobs that require no such knowledge (such algorithms are called nonclairvoyant) . Preemptive scheduling (i.e., redistribution of processors) is important to reduce mean response time in multiprocessor systems, especially in the widely available network of workstations. Preemption is a method to adapt to the uncertain and changing nature of jobs and workloads. Unfortunately, preemption may incur large overheads if it is applied frequently. To account for the cost preemptions, we consider a number of simple scheduling algorithms classified by the number of preemptions they are allowed, ranging from none to an infinite number. The Equi-part...

Large-scale Non-Uniform Memory Access (NUMA) multiprocessors are gaining increased attention due to their potential for achieving high performance through the replication of relatively simple components. Because of the complexity of such systems, scheduling algorithms for parallel applications are crucial in realizing the performance potential of these systems. In particular, scheduling methods must consider the scale of the system, with the increased likelihood of creating bottlenecks, along with the NUMA characteristics of the system, and the benefits to be gained by placing threads close to their code and data.We propose a class of scheduling algorithms based on processor pools. A processor pool is a software construct for organizing and managing a large number of processors by dividing them into groups called pools. The parallel threads of a job are run in a single processor pool, unless there are performance advantages for a job to span multiple pools. Several jobs may share one pool. Our simulation experiments show that processor pool-based scheduling may effectively reduce the average job response time. The performance improvements attained by using processor pools increase with the average parallelism of the jobs, the load level of the system, the differentials in memory access costs, and the likelihood of having system bottlenecks. As the system size increasesr, while maintaining the workload composition and intensity, we observed that processor pools can be used to provide significant performance improvements. We therefore conclude that processor pool-based scheduling may be an effective and efficient technique for scalable systems.

Abstract Multiplictive inequalities for reliability bounds are derived, by observing that certain reliability measures are positively correlated. These inequalities can be used to obtain substantial improvements on available bounds for network reliability.

Abstract The probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all‐terminal reliability), when two nodes are to communicate (2‐terminal reliability), and when k specified nodes are to communicate (k‐terminal reliability); the latter case includes the first two. Each of these reliability measures is NP‐hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all‐terminal and 2‐terminal cases have been treated separately, and few results apply to the k‐terminal case. In this paper, we develop a simple strategy to obtain k‐terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all‐terminal, k‐terminal, and 2‐terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.

The scheduler used in an operating system is an important factor in the performance of the system under heavy load. This paper describes the scheduling philosophy employed in the UNIX operating system and outlines the standard scheduling strategies. Modified strategies which address deficiencies in the standard strategies are described. The effectiveness of these modified strategies is assessed by means of performance experiments.