This paper develops a plug-and-play reusable LogGP model that can be used to predict the runtime and scaling behavior of different MPI-based pipelined wavefront applications running on modern parallel platforms with multi-core nodes. A key new feature of the model is that it requires only a few simple input parameters to project performance for wavefront codes with different structure to the sweeps in each iteration as well as different behavior during each wavefront computation and/or between iterations. We apply the model to three key benchmark applications that are used in high performance computing procurement, illustrating that the model parameters yield insight into the key differences among the codes. We also develop new, simple and highly accurate models of MPI send, receive, and group communication primitives on the dual-core Cray XT system. We validate the reusable model applied to each benchmark on up to 8192 processors on the XT3/XT4. Results show excellent accuracy for all high performance application and platform configurations that we were able to measure. Finally we use the model to assess application and hardware configurations, develop new metrics for procurement and configuration, identify bottlenecks, and assess new application design modifications that, to our knowledge, have not previously been explored.

Significant improvement to visual quality for real-time 3D graphics requires modeling of complex illumination effects like soft-shadows, reflections, and diffuse lighting interactions. The conventional Z-buffer algorithm driven GPU model does not provide sufficient support for this improvement. This paper targets the entire graphics system stack and demonstrates algorithms, a software architecture, and a hardware architecture for real-time rendering with a paradigm shift to ray-tracing. The three unique features of our system called Copernicus are support for dynamic scenes, high image quality, and execution on programmable multicore architectures. The focus of this paper is the synergy and interaction between applications, architecture, and evaluation. First, we describe the ray-tracing algorithms which are designed to use redundancy and partitioning to achieve locality. Second, we describe the architecture which uses ISA specialization, multi-threading to hide memory delays and supports only local coherence. Finally, we develop an analytical performance model for our 128-core system, using measurements from simulation and a scaled-down prototype system. More generally, this paper addresses an important issue of mechanisms and evaluation for challenging workloads for future processors. Our results show that a single 8-core tile (each core 4-way multithreaded) can be almost 100% utilized and sustain 10 million rays/second. Sixteen such tiles, which can fit on a 240 mm2chip in 22 nm technology, make up the system and with our anticipated improvements in algorithms, can sustain real-time rendering. The mechanisms and the architecture can potentially support other domains like irregular scientific computations and physics computations.

Summary form only given. This talk provides a 20-year perspective on the use of analytic models to design of a wide range of commercially important architectures and systems with complex behavior. These systems include resources with highly bursty and/or correlated packet arrivals, communication protocols with complex routing and blocking of messages, resources that are configured for a very high probability (e.g., 0.9999) of providing immediate service to each arriving client, and complex large-scale grid/Internet applications. The examples illustrate some guiding principles for model development, and show that the models can be relatively easy to develop. More importantly, the models can be highly accurate - often more accurate than simulation, and sometimes more accurate than the system implementation! The examples also illustrate that the models can provide unique insight into system design as well as significant new system functionality. In other words, analytic models are a key tool for competitive systems engineering. Time permitting, the talk includes some important observations about workload models, and some ways to avoid key pitfalls in simulation.

In this paper, we present a comprehensive performance evaluation of TCP NewReno and TCP Vegas with and without ACK thinning for static multihop wireless IEEE 802.11 networks. Opposed to previous studies, we consider not only IEEE 802.11 operating in ad hoc mode with 2 Mbit/s bandwidth, but also with 5.5 Mbit/s and 11 Mbit/s bandwidths. Simulation results using ns-2 show that TCP Vegas achieves between 15% and 83% more goodput and between 57% and 99% fewer packet retransmissions than TCP NewReno. Considering fairness among multiple TCP flows, we show that using TCP Vegas results in between 21% and 95% fairness improvement compared to TCP NewReno. The reduced amount of packet retransmissions of TCP Vegas also leads to significant savings of energy consumption. The paper gives insight on the particular reasons for such performance advantages of TCP Vegas in comparison to TCP NewReno.

This paper characterizes the query behavior of peers in a peer-to-peer (P2P) file sharing system. In contrast to previous work, which provides various aggregate workload statistics, we characterize peer behavior in a form that can be used for constructing representative synthetic workloads for evaluating new P2P system designs. In particular, the analysis exposes heterogeneous behavior that occurs on different days, in different geographical regions (i. e., Asia, Europe, and North America) or during different periods of the day. The workload measures include the fraction of connected sessions that are passive (i. e., issue no queries), the duration of such sessions, and for each active session, the number of queries issued, time until first query, query interarrival time, time after last query, and distribution of query popularity. Moreover, the key correlations in these workload measures are captured in the form of conditional distributions, such that the correlations can be accurately reproduced in a synthetic workload. The characterization is based on trace data gathered in the Gnutella P2P system over a period of 40 days. To characterize system-independent user behavior, we eliminate queries that are specific to the Gnutella system software, such as re-queries that are automatically issued by some client implementations to improve system responsiveness.

A conventional video file contains a single temporally-ordered sequence of video frames. Clients requesting on-demand streaming of such a file receive (all or intervals of) the same content. For popular tiles that receive many requests during a file playback time, scalable streaming protocols based on multicast or broadcast have been devised. Such protocols require server and network bandwidth that grow much slower than linearly with the file request rate. This paper considers "nonlinear" video content in which there are parallel sequences of frames. Clients dynamically select which branch of the video they wish to follow, sufficiently ahead of each branch point so as to allow the video to he delivered without jitter. An example might be "choose-your-own-ending" movies. With traditional scalable delivery architectures such as movie theaters or TV broadcasting, such personalization of the delivered video content is very difficult or impossible. It becomes feasible, in principle at least, when the video is streamed to individual clients over a network. This paper analyzes the minimal server bandwidth requirements, and proposes and evaluates practical scalable delivery protocols, for on-demand streaming of nonlinear media.

Previous scalable protocols for downloading large, popular files from a single server include batching and cyclic multicast. With batching, clients wait to begin receiving a requested file until the beginning of its next multicast transmission, which collectively serves all of the waiting clients that have accumulated up to that point. With cyclic multicast, the file data is cyclically transmitted on a multicast channel. Clients can begin listening to the channel at an arbitrary point in time, and continue listening until all of the file data has been received. This paper first develops lower bounds on the average and maximum client delay for completely downloading a file, as functions of the average server bandwidth used to serve requests for that file, for systems with homogeneous clients. The results show that neither cyclic multicast nor batching consistently yields performance close to optimal. New hybrid download protocols are proposed that achieve within 15 % of the optimal maximum delay and 20 % of the optimal average delay in homogeneous systems. For heterogeneous systems in which clients have widely-varying achievable reception rates, an additional design question concerns the use of high rate transmissions, which can decrease delay for clients that can receive at such rates, in addition to low rate transmissions that can be received by all clients. A new scalable download protocol for such systems is proposed, and its performance is compared to that of alternative protocols as well as to new lower bounds on maximum client delay. The new protocol achieves within 25 % of the optimal maximum client delay in all scenarios considered.

The Least Attained Service (LAS) scheduling policy, when used for scheduling packets over the bottleneck link of an Internet path, can greatly reduce the average flow time for short flows while not significantly increasing the average flow time for the long flows that share the same bottleneck. No modification of the packet headers is required to implement the simple LAS policy. However, previous work has also shown that a drawback of the LAS scheduler is that, when link utilization is greater than 70%, long flows experience large jitter in their packet transfer times as compared to the conventional First-Come-First-Serve (FCFS) link scheduling. This paper proposes and evaluates new differentiated LAS scheduling policies that reduce the jitter for long flows that are identified as "priority" flows.To evaluate the new policies, we develop analytic models to estimate average flow transfer time as a function of flow size, and average packet transmission time as a function of position in the flow, for the single-bottleneck "dumbbell topology" used in many ns simulation studies. Models are developed for FCFS scheduling, LAS scheduling, and each of the new differentiated LAS scheduling policies at the bottleneck link. Over a wide range of configu-rations, the analytic estimates agree very closely with the ns estimates. Thus, the analytic models can be used instead of simulation for comparing the policies with respect to mean flow transfer time (as a function of flow size) and mean packet transfer time. Furthermore, an initial discrepancy between the analytic and simulation estimates revealed errors in the parameter values that are often specified in the widely used ns Web workload generator. We develop an improved Web workload specification, which is used to estimate the packet jitter for long flows (more accurately than with previous simulation workloads).Results for the scheduling policies show that a particular policy, LAS-log, greatly improves the mean flow transfer time for priority long flows while providing performance similar to LAS for the ordinary flows. Simulations show that the LAS-log policy also greatly reduces the jitter in packet delivery times for the priority flows.

Recent scalable multicast streaming protocols for on-demand delivery of media content offer the promise of greatly reduced server and network bandwidth. However, a key unresolved issue is how to design scalable content distribution systems that place replica servers closer to various client populations and route client requests and response streams so as to minimize the total server and network delivery cost. This issue is significantly more complex than the design of distribution systems for traditional Web files or unicast on-demand streaming, for two reasons. First, closest server and shortest path routing does not minimize network bandwidth usage; instead, the optimal routing of client requests and server multicasts is complex and interdependent. Second, the server bandwidth usage increases with the number of replicas. Nevertheless, this paper shows that the complex replica placement and routing optimization problem, in its essential form, can be expressed fairly simply, and can be solved for example client populations and realistic network topologies. The solutions show that the optimal scalable system can differ significantly from the optimal system for conventional delivery. Furthermore, simple canonical networks are analyzed to develop insights into effective heuristics for near-optimal placement and routing. The proposed new heuristics can be used for designing large and heterogeneous systems that are of practical interest. For a number of example networks, the best heuristics produce systems with total delivery cost that is within 16% of optimality.

In this article, we consider analytical techniques for predicting detailed performance characteristics of a single shared memory parallel program for a particular input. Analytical models for parallel programs have been successful at providing simple qualitative insights and bounds on program scalability, but have been less successful in practice for providing detailed insights and metrics for program performance (leaving these to measurement or simulation). We develop a conceptually simple modeling technique called deterministic task graph analysis that provides detailed performance prediction for shared-memory programs with arbitrary task graphs, a wide variety of task scheduling policies, and significant communication and resource contention. Unlike many previous models that are stochastic models, our model assumes deterministic task execution times (while retaining the use of stochastic models for communication and resource contention). This assumption is supported by a previous study of the influence of nondeterministic delays in parallel programs.We evaluate our model in three ways. First, an experimental evaluation shows that our analysis technique is accurate and efficient for a variety of shared-memory programs, including programs with large and/or complex task graphs, sophisticated task scheduling, highly nonuniform task times, and significant communication and resource contention. The results also show that the deterministic assumption is crucial to permit accurate and yet efficient analysis of these programs. Second, we use three example programs to illustrate the predictive capabilities of the model. In two cases, broad insights and detailed metrics from the model are used to suggest improvements in load-balancing and the model quickly and accurately predicts the impact of these changes. In the third case, the model provides novel insights into the impact of program design changes that improve communication locality as well as load-balancing, via new (but general-purpose) metrics. Finally, we present results from a comparison of our model and representative stochastic models, and use these to characterize the conditions under which a deterministic model or stochastic models would be appropriate.

Previous analytic models of TCP Vegas throughput have been developed for loss-free (all-Vegas) networks. This work develops a simple and accurate analytic model for the throughput of a TCP Vegas bulk transfer in the presence of packet loss, as a function of average round trip time, minimum round trip time, and loss rate for the transfer. Similar models have previously been developed for TCP Reno. However, several aspects of TCP Vegas need to be treated differently than their counterparts in Reno. The proposed model captures the key innovative mechanisms that Vegas employs during slow start, congestion avoidance, and congestion recovery. The results include (1) a simple, validated model of TCP Vegas throughput that can be used for equation-based rate control of other flows such as UDP streams, (2) a simple formula to determine, from the measured packet loss rate, whether the network buffers are overcommitted and thus the TCP Vegas flow cannot reach the specified target lower threshold on throughput, (3) new insights into the design and performance of TCP Vegas, and (4) comparisons between TCP Vegas and TCP Reno including new insights regarding incremental deployment of TCP Vegas.

Previous scalable on-demand streaming protocols do not allow clients to recover from packet loss. This paper develops new protocols that: (1) have a tunably short latency for the client to begin playing the media; (2) allow heterogeneous clients to recover lost packets without jitter as long as each client's cumulative loss rate is within a tunable threshold; and (3) assume a tunable upper bound on the transmission rate to each client that can be as small as a fraction (e.g., 25%) greater than the media play rate. Models are developed to compute the minimum required server bandwidth for a given loss rate and playback latency. The results of the models are used to develop the new protocols and assess their performance. The new protocols, Reliable Periodic Broadcast and Reliable Bandwidth Skimming, are simple to implement and achieve nearly the best possible scalability and efficiency for a given set of client characteristics and desirable/feasible media quality. Furthermore, the results show that the new reliable protocols that transmit to each client at only twice the media play rate have similar performance to previous protocols that require clients to receive at many times the play rate.

This paper develops and validates an efficient analytical model for evaluating the performance of shared memory architectures with ILP processors. First, we instrument the SimOS simulator to measure the parameters for such a model and we find a surprisingly high degree of processor memory request heterogeneity in the workloads. Examining the model parameters provides insight into application behaviors and how they interact with the system. Second, we create a model that captures such heterogeneous processor behavior, which is important for analyzing memory system design tradeoffs. Highly bursty memory request traffic and lock contention are also modeled in a significantly more robust way than in previous work. With these features, the model is applicable to a wide range of architectures and applications. Although the features increase the model complexity, it is a useful design tool because the size of the model input parameter set remains manageable, and the model is still several orders of magnitude quicker to solve than detailed simulation. Validation results show that the model is highly accurate, producing heterogeneous per processor throughputs that are generally within 5 percent and, for the workloads validated, always within 13 percent of the values measured by detailed simulation with SimOS. Several examples illustrate applications of the model to studying architectural design issues and the interactions between the architecture and the application workloads.

This paper develops a performance model that is used to control the adaptive execution the ATR code for solving large stochastic optimization problems on computational grids. A detailed analysis of the execution characteristics of ATR is used to construct the performance model that is then used to specify (a) near-optimal dynamic values of parameters that govern the distribution of work, and (b) a new task scheduling algorithm. Together, these new features minimize ATR execution time on any collection of compute nodes, including a varying collection of heterogeneous nodes. The new adaptive code runs up to eight-fold faster than the previously optimized code, and requires no input parameters from the user to guide the distribution of work. Furthermore, the modeling process led to several changes in the Condor runtime environment, including the new task scheduling algorithm, that produce significant performance improvements for master-worker computations as well as possibly other types of grid applications.

This paper develops simple cost models for provisioning content distribution networks that use the simple and highly scalable bandwidth skimming protocol for streaming. New insight is obtained into: (1) how cost-effective proxy servers are in multicast streaming systems; (2) the most effective streaming protocol; and (3) the optimal proxy content, as a function of the system configuration and workload. A key result is that proxy servers are only cost effective if: (a) the origin server does not have a multicast capability; or (b) the file request rate is low, and thus multicast is not highly effective; or (c) the cost of a proxy server stream is a very small fraction (i.e., approximately 1/P) of the cost of an origin server stream, where P is the number of proxy servers and the cost of either type of stream includes both the server and network resource costs. For cases where proxy servers are cost effective, results in the paper provide the optimal proxy content and the most effective streaming protocol, as a function of a wide range of system configuration and workload parameters. In contrast to previous work, full file caching outperforms prefix caching over a significant region of this system design space, due to more efficient multicast streaming protocols as well as a more complete exploration of the practical system configuration space.

Recently proposed streaming protocols are able to deliver multimedia files on-demand with the required server bandwidth growing only logarithmically with the file request rate. The same efficiencies are achieved for network bandwidth if delivery is over a true broadcast channel. This paper considers the required network bandwidth for on-demand streaming over multicast delivery trees. We consider both simple canonical delivery trees, and more complex cases in which delivery trees are constructed using both existing and new algorithms for various randomly generated network topologies and client site locations. Our results quantify the potential savings from the use of multicast trees that are configured to minimize network bandwidth rather than the latency to the content server. Further, we show that it is possible to achieve reasonably close to the minimum possible bandwidth usage for both network and server simultaneously, with a practical on-demand streaming protocol.

Recently proposed scalable on-demand streaming protocols have previously been evaluated using a system cost measure termed the "required server bandwidth". For the scalable protocols that provide immediate service to each client when the server is not overloaded, this paper develops simple analytic models to evaluate two client-oriented quality of service metrics, namely (1) the mean client waiting time in systems where clients are willing to wait if a (well-provisioned) server is temporarily overloaded, and (2) the fraction of clients who balk (i.e., leave without receiving their requested media content) in systems where the clients will tolerate no or only very low service delays during a temporary overload. The models include novel approximate MVA techniques that appear to extend the range of applicability of customized AMVA to include questions focussed on state probabilities rather than on mean values, and to systems in which the operating points of interest do not include substantial client queues. For example, the new AMVA models accurately estimate the server bandwidth needed to achieve a balking rate as low as one in ten thousand. The analytic models can easily be applied to determine the server bandwidth needed for a given number of media files, anticipated total client request rate and file access frequencies, and target balking rate or mean wait. Results show that (a) scalable media servers that are configured with the "required server bandwidth" defined in previous work have low mean wait but may have unacceptably high client balking rates (i.e., greater than one in twenty), (b) for high to moderate client load, only a 10 - 50% increase in the previously defined required server bandwidth is needed to achieve a very low balking rate (e.g., one in ten thousand), and (c) media server performance (either mean wait or balking rate) degrades rapidly if the actual client load is more than 10% greater than the anticipated load.

This paper addresses open job scheduling questions for the challenge workloads that run on the large scale parallel systems at supercomputer centers. Simulation results for six recent one-month job traces from the NCSA Origin 2000 (O2K) system are used to evaluate (I) the experimentally tuned NCSA LSF* policy, (2) the FCFS-backfill policy, (3) the Priority-backfill policy with alternative priority functions and with limited pre-emption to provide immediate service to each arriving job, and (4) the spatial equipartitioning (EQspatial) policy with an optional modification to reduce the maximum waiting time for the largest jobs in the challenge workloads. Measurements on the O2K validate the simulation results for two of the policies. The priority-backfill policy with immediate service and a starvation-free priority measure that favors short jobs is shown to be the most promising if jobs cannot adapt to changing processor allocations at runtime, but EQspatial provides significantly better 95th percentile waiting time.

This paper presents an extensive analysis of the client workloads for educational media servers at two major U.S. universities. The goals of the analysis include providing data for generating synthetic workloads, gaining insight into the design of streaming content distribution networks, and quantifying how much server bandwidth can be saved in interactive educational environments by using recently developed multicast streaming methods for stored content.

Inspired by recent techniques for reliable bulk data distribution, this paper develops scalable protocols for reliable on-demand delivery of streaming media. Models are developed that quantify the best possible scalability for given client characteristics. The results of the models are used to guide the design and assess the performance of the proposed streaming techniques. The new protocols, RPB and RBS, are relatively simple to implement and achieve nearly the best possible scalability and efficiency for a given set of client characteristics and desirable/feasible media quality.

Two recent techniques for multicast or broadcast delivery of streaming media can provide immediate service to each client request, yet achieve considerable client stream sharing which leads to significant server and network bandwidth savings. The paper considers: 1) how well these recently proposed techniques perform relative to each other and 2) whether there are new practical delivery techniques that can achieve better bandwidth savings than the previous techniques over a wide range of client request rates. The principal results are as follows: First, the recent partitioned dynamic skyscraper technique is adapted to provide immediate service to each client request more simply and directly than the original dynamic skyscraper method. Second, at moderate to high client request rates, the dynamic skyscraper method has required server bandwidth that is significantly lower than the recent optimized stream tapping/patching/controlled multicast technique. Third, the minimum required server bandwidth for any delivery technique that provides immediate real-time delivery to clients increases logarithmically (with constant factor equal to one) as a function of the client request arrival rate. Furthermore, it is (theoretically) possible to achieve very close to the minimum required server bandwidth if client receive bandwidth is equal to two times the data streaming rate and client storage capacity is sufficient for buffering data from shared streams. Finally, we propose a new practical delivery technique, called hierarchical multicast stream merging (HMSM), which has a required server bandwidth that is lower than the partitioned dynamic skyscraper and is reasonably close to the minimum achievable required server bandwidth over a wide range of client request rates.

Motivated by experience gained during the validation of a recent Approximate Mean Value Analysis (AMVA) model of modern shared memory architectures, this paper re-examines the “standard” AMVA approximation for non-exponential FCFS queues. We find that this approximation is often inaccurate for FCFS queues with high service time variability. For such queues, we propose and evaluate: (1) AMVA estimates of the mean residual service time at an arrival instant that are much more accurate than the standard AMVA estimate, (2) a new AMVA technique that provides a much more accurate estimate of mean center residence time than the standard AMVA estimate, and (3) a new AMVA technique for computing the mean residence time at a “downstream” queue which has a more bursty arrival process than is assumed in the standard AMVA equations. Together, these new techniques increase the range of applications to which AMVA may be fruitfully applied, so that for example, the memory system architecture of shared memory systems with complex modern processors can be analyzed with these computationally efficient methods.

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.

The simplest video-on-demand (VOD) delivery policy is to allocate a new media delivery stream to each client request when it arrives. This policy has the desirable properties of “immediate service ” (there is minimal latency between the client request and

This paper develops a highly accurate LogGP model of a complex wavefront application that uses MPI communication on the IBM SP/2. Key features of the model include: (1) elucidation of the principal wavefront synchronization structure, and (2) explicit high-fidelity models of the MPI-send and MPI-receive primitives. The MPI-send/receive models are used to derive L, o, and G from simple two-node micro-benchmarks. Other model parameters are obtained by measuring small application problem sizes on four SP nodes. Results show that the LogGP model predicts, in seconds and with a high degree of accuracy, measured application execution time for large problems running on 128 nodes. Detailed performance projections are provided for very large future processor configurations that are expected to be available to the application developers. These results indicate that scaling beyond one or two thousand nodes yields greatly diminished improvements in execution time, and that synchronization delays are a principal factor limiting the scalability of the application.

This paper develops and validates an analytical model for evaluating various types of architectural alternatives for shared-memory systems with processors that aggressively exploit instruction-level parallelism. Compared to simulation, the analytical model is many orders of magnitude faster to solve, yielding highly accurate system-performance estimates in seconds. The model input parameters characterize the ability of an application to exploit instruction-level parallelism as well as the interaction between the application and the memory system architecture. A trace-driven simulation methodology is developed that allows these parameters to be generated over 100 times faster than with a detailed execution-driven simulator. Finally, this paper shows that the analytical model can be used to gain insights into application performance and to evaluate architectural design trade-offs.

Parallel algorithm designers need computational models that take first order system costs into account, but are also simple enough to use in practice. This paper introduces the LoPC model, which is inspired by the LogP model but accounts for contention for message processing resources in parallel algorithms on a multiprocessor or network of workstations. LoPC takes the L, o and P parameters directly from the LogP model and uses them to predict the cost of contention, C.This paper defines the LoPC model and derives the general form of the model for parallel applications that communicate via active messages. Model modifications for systems that implement coherent shared memory abstractions are also discussed. We carry out the analysis for two important classes of applications that have irregular communication. In the case of parallel applications with homogeneous all-to-any communication, such as sparse matrix computations, the analysis yields a simple rule of thumb and insight into contention costs. In the case of parallel client-server algorithms, the LoPC analysis provides a simple and accurate calculation of the optimal allocation of nodes between clients and servers. The LoPC estimates for these applications are shown to be accurate when compared against event driven simulation and against a sparse matrix computation on the MIT Alewife multiprocessor.

One of the open questions in the design of multimedia storage servers is in what order to serve incoming requests. Given the capability provided by the disk layout and scheduling algorithms to serve multiple streams simultaneously, improved request scheduling algorithms can reduce customer waiting times. This results in better service and/or lower customer loss. In this paper we define a new class of request scheduling algorithms, called Group-Guaranteed Server Capacity (GGSC), that preassign server channel capacity to groups of objects. We also define a particular formal method for computing the assigned capacities to achieve a given performance objective. We observe that the FCFS policy can provide the precise time of service to incoming customer requests. Under this assumption, we compare the performance of one of the new GGSC algorithms, GGSCW-FCFS, against FCFS and against two other recently proposed scheduling algorithms: Maximum Factored Queue length (MFQ), and the FCFS-n algorithm that preassigns capacity only to each of the n most popular objects. The algorithms are compared for both competitive market and captured audience environments.Key findings of the algorithm comparisons are that: (1) FCFS-n has no advantage over FCFS if FCFS gives time of service guarantees to arriving customers, (2) FCFS and GGSCW-FCFS are superior to MFQ for both competitive and captive audience environments, (3) for competitive servers that are configured for customer loss less than 10%, FCFS is superior to all other algorithms examined in this paper, and (4) for captive audience environments that have objects with variable playback length, GGSCW-FCFS is the most promising of the policies considered in this paper. The conclusions for FCFS-n and MFQ differ from previous work because we focus on competitive environments with customer loss under 10%, we assume FCFS can provide time of service guarantees to all arriving customers, and we consider the distribution of customer waiting time as well as the average waiting time.

New high-speed switched networks have reduced the latency of network page transfers significantly below that of local disk. This trend has led to the development of systems that use network-wide memory, or global memory, as a cache for virtual memory pages or file blocks. A crucial issue in the implementation of these global memory systems is the selection of the target nodes to receive replaced pages. Current systems use various forms of an approximate global LRU algorithm for making these selections. However, using age information alone can lead to suboptimal performance in two ways. First, workload characteristics can lead to uneven distributions of old pages across servers, causing increased contention delays. Second, the global memory traffic imposed on a node can degrade the performance of local jobs on that node.This paper studies the potential benefit and the potential harm of using load information, in addition to age information, in global memory replacement policies. Using an analytic queueing network model, we show the extent to which server load can degrade remote memory latency and how load balancing solves this problem. Load balancing requests can cause the system to deviate from the global LRU replacement policy, however. Using trace-driven simulation, we study the impact on application performance of deviating from the LRU replacement policy. We find that deviating from strict LRU, even significantly for some applications, does not affect application performance. Based upon these results, we conclude that global memory systems can gain substantial benefit from load balancing requests with little harm from suboptimal replacement decisions. Finally, we illustrate the use of the intuition gained from the model and simulation experiments by proposing a new family of algorithms that incorporate load considerations as well as age information in global memory replacement decisions.

New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer and access units in remote memory systems, page size is a key performance factor. Recently, page sizes of modern processors have been increasing in order to provide more TLB coverage and amortize disk access costs. Unfortunately, for high-speed networks, small transfers are needed to provide low latency. This trend in page size is thus at odds with the use of network memory on high-speed networks.This paper studies the use of subpages as a means of reducing transfer size and latency in a remote-memory environment. Using trace-driven simulation, we show how and why subpages reduce latency and improve performance of programs using network memory. Our results show that memory-intensive applications execute up to 1.8 times faster when executing with 1K-byte subpages, when compared to the same applications using full 8K-byte pages in the global memory system. Those same applications using 1K-byte subpages execute up to 4 times faster than they would using the disk for backing store. Using a prototype implementation on the DEC Alpha and AN2 network, we demonstrate how subpages can reduce remote-memory fault time; e.g., our prototype is able to satisfy a fault on a 1K subpage stored in remote memory in 0.5 milliseconds, one third the time of a full page.

The performance potential of run-to-completion (RTC) parallel processor scheduling policies is investigated by examining whether (1) application execution rate characteristics such as average parallelism (avg) and processor working set (PWS) and/or (2) limited preemption can be used to improve the performance of these policies. We address the first question by comparing policies (previous as well as new) that differ only in whether or not they use execution rate characteristics and by examining a wider range of the workload parameter space than previous studies. We address the second question by comparing a simple two-level queueing policy with RTC scheduling in the second level queue against RTC policies that don't allow any preemption and against dynamic equiallocation(EQ).

: The join of two relations is an important operation in database systems. It occurs frequently in relational queries, and join performance is a significant factor in overall system performance. Cost models for join algorithms are used by query optimizers to choose efficient query execution strategies. This paper presents an efficient analytical model of an important join method, the hybrid hash join algorithm, that captures several key features of the algorithm's performance -- including its intra--operator parallelism, interference between disk reads and writes, caching of disk pages, and placement of data on disk(s). Validation of the model against a detailed simulation of a database system shows that the response time estimates produced by the model are quite accurate. 1 Introduction Relational database systems organize information into a collection of tables. The relational join operator is used to relate information from two or more tables. Thus, joins are a frequently occurrin...

This paper develops detailed analytical performance models for k-ary n-cube networks with single-hit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz (1987). In contrast to previous performance studies of such networks, the system is modeled as a closed queueing network that: includes the effects of blocking and pipelining of messages in the network; allows for arbitrary source-destination probability distributions; and explicitly models the virtual channels used in the deadlock-free routing algorithm. The models are used to examine several performance issues for 2-D networks with shared-memory traffic. These results should prove useful for engineering high-performance systems based on low-dimensional k-ary n-cube networks.>

Current and emerging high-performance parallel com puter architectures generally implement one of two types of communication mechanisms: shared memory (SM) or message passing (MP). In this paper we propose a hybrid SM/MP architecture together with a hybrid SM/MP programming model, that we believe effectively combines the advantages of each system. The SM/MP architecture contains both a high-performance coherence protocol for shared memory, and message-passing primi tives that coexist with the coherence protocol but have no coherence overhead. The SM/MP programming model provides a framework for safely and effectively using the SM/MP communication primitives. We illustrate the use of the model and primitives to reduce communication overhead in SM systems.

Stochastic models are widely used for the performance evaluation of parallel programs and systems. The stochastic assumptions in such models exe intended to represent non-deterministic processing requirements as well as random delays due to inter-process communication end resource contention. In this paper, we provide compelling analytical and experimental evidence that in current and foreseeable shared-memory programs, communication delays introduce negligible variance into the execution time between synchronization points. Furthermore, we show using direct measurements of variance that other sources of randomness, particularly non-deterministic computational requirements, also do not introduce significant variance in many programs. We then use two examples to demonstrate the implications of these results for parallel program performance prediction models, as well as for general stochastic models of parallel systems.

The Scalable Coherent Interface (SCI) is an emerging IEEE standard that provides computer-bus-like services to a set of nodes via fast, unidirectional links. This paper presents the first detailed performance study of the SCI ring, using both analytical models and simulation. Performance is analyzed for uniform and nonuniform traffic, and the effect of the ring's flow control protocol is studied.

An accurate and efficient model of a commercial multiprocessor bus is developed. Four important characteristics of the bus design are modeled: asynchronous memory write operations; in-order delivery of responses to processor read requests; priority scheduling of memory responses; and upper bounds on the number of outstanding processor requests. A two-level hierarchical model employing both Markov chain and mean value analysis techniques for analyzing queueing networks is used. The model is shown to accurately predict measured system performance for two parallel program workloads that have different memory access characteristics. The results provide evidence that analytic queueing models can be extremely accurate in spite of simplifying assumptions required for model tractability. Model estimates are compared against detailed simulation of the bus to investigate in more detail the likely source of small model inaccuracies. The use of the analytical model for assessing system design tradeoffs is illustrated.>

We use mean value analysis models to compare representative hardware and software cache coherence schemes for a large-scale shared-memory system.Our goal is to identify the workloads for which either of the schemes is significantly better.Our methodology improves upon previous analytical studies and complements previous simulation studies by developing a common high-level workload model that is used to derive separate sets of lowlevel workload parameters for the two schemes.This approach allows an equitable comparison of the two schemes for a specific workload.Our results show that software schemes are comparable (in terms of processor efficiency) to hardware schemes for a wide class of programs.The only cases for which software schemes perform significantly worse than hardware schemes are when there is a greater than 15% reduction in hit rate due to inaccurate prediction of memory access conflicts, or when there are many writes in the program that are not executed at runtime.For relatively wellstructured and deterministic programs, on the other hand, software schemes perform significantly better than hardware schemes.

Scheduling policies for general purpose multiprogrammed multiprocessors are not well understood. This paper examines various policies to determine which properties of a scheduling policy are the most significant determinants of performance. We compare a more comprehensive set of policies than previous work, including one important scheduling policy that has not previously been examined. We also compare the policies under workloads that we feel are more realistic than previous studies have used. Using these new workloads, we arrive at different conclusions than reported in earlier work. In particular, we find that the “smallest number of processes first” (SNPF) scheduling discipline performs poorly, even when the number of processes in a job is positively correlated with the total service demand of the job. We also find that policies that allocate an equal fraction of the processing power to each job in the system perform better, on the whole, than policies that allocate processing power unequally. Finally, we find that for lock access synchronization, dividing processing power equally among all jobs in the system is a more effective property of a scheduling policy than the property of minimizing synchronization spin-waiting, unless demand for synchronization is extremely high. (The latter property is implemented by coscheduling processes within a job, or by using a thread management package that avoids preemption of processes that hold spinlocks.) Our studies are done by simulating abstract models of the system and the workloads.

The use of a special-purpose coprocessor for supporting message passing is proposed. An actual message-based operating system is partitioned into computation and communication parts, executing, respectively, on a host and a message coprocessor which interact through shared queues. Its performance is measured on a multiprocessor. Hardware support in the form of a special-purpose smart bus and smart shared memory is designed. The benefits of these components are demonstrated through analytical modeling using generalized timed Petri nets. The analysis shows good agreement with experimental results and indicates that substantial benefits may be obtained when the software is partitioned between host and the message coprocessor and when a small amount of special-purpose hardware is added.>

This paper proposes a set of efficient primitives for process synchronization in multiprocessors. The only assumptions made in developing the set of primitives are that hardware combining is not implemented in the inter-connect, and (in one case) that the interconnect supports broadcast.

This paper examines the effect of contention for a single shared semaphore protecting critical regions in a multiprocessor operating system on system performance as the number of processors increases. A simple queueing model is used to make predictions as a function of the expected demand for the semaphore by each processor. Measurements are then presented for 2 and 4 processor configurations of the CRAY X-MP running an experimental version of UNICOS. The measurements indicate that demand is highly dependent on the workload, and that contention can be somewhat higher than predicted by the model due to process scheduling effects and request interdependencies. One interesting point which is revealed in the measurement results, is that the UNIX scheduler gives preferential treatment to jobs that make frequent requests for the semaphore.

A family of dynamic cache-consistency-protocols for shared-bus multiprocessor systems is considered. A modeling approach, based on the specification and the iterative solution of sets of equations that express the mean values of interesting performance measures in terms of the mean values of certain model inputs, is presented. The equations are intuitive, in the sense that each can be explained simply in terms of the mechanics of the architecture being modeled. The solution technique is extremely efficient, requiring on the order of one second of CPU time for systems of arbitrary size. This makes it possible to explore a large design space quickly and interactively. The results are essentially as accurate as those of the previously existing techniques, which took hours on I-MIPS processors.>

The round-robin (RR) protocol, which uses statically assigned arbitration numbers to resolve conflict during an arbitration, is more robust and simpler to implement than previous distributed RR protocols that are based on rotating-aging priorities. The proposed first-come-first-served (FCFS) protocol uses partly static arbitration numbers, and is the first practical proposal for a FCFS arbiter known the authors. The proposed protocols have a better combination of efficiency, cost, and fairness characteristics than existing multiprocessor bus arbitration algorithms. Three implementations of the RR protocol, and two implementations of the FCFS protocol, are discussed. Simulation results are presented that address: (1) the practical potential for unfairness in the simpler implementation of the FCFS protocol: (2) the practical implications of the higher waiting-time variance in the RR protocol; and (3) the allocation of bus bandwidth among agents with unequal request rate in each protocol. The simulation results indicate that there is very little practical difference in the performance of the two protocols.>

This paper presents a preliminary performance analysis of a new large-scale multiprocessor: the Wisconsin Multicube. A key characteristic of the machine is that it is based on shared buses and a snooping cache coherence protocol. The organization of the shared buses and shared memory is unique and non-hierarchical. The two-dimensional version of the architecture is envisioned as scaling to 1024 processors.

In recent years there has been increasing interest in message-based operating systems, particularly in distributed environments. Such systems consist of a small message-passing kernel supporting a collection of system server processes that provide such services as resource management, file service, and global communications. For such an architecture to be practical, it is essential that basic messages be fast, since they often replace what would be a simple procedure call or “kernel call” in a more traditional system. Careful study of several operating systems shows that the limiting factor, especially for small messages, is typically not network bandwidth but processing overhead. Therefore, we propose using a special-purpose coprocessor to support message passing. Our research has two parts: First, we partitioned an actual message-based operating system into communication and computation parts interacting through shared queues and measured its performance on a multiprocessor. Second, we designed hardware support in the form of a special-purpose smart bus and smart shared memory and demonstrated the benefits of these components through analytical modeling using Generalized Timed Petri Nets. Our analysis shows good agreement with the experimental results and indicates that substantial benefits may be obtained from both the partitioning of the software and the addition of a small amount of special-purpose hardware.

Exact results are given for the processing power in a multibus multiprocessor with constant memory cycle times and geometric interrequest times. Both uniform and nonuniform memory accesses are considered. Such results have not previously been obtained. In order to derive these results we use a method of introducing time into Petri nets, called Generalized Timed Petri Nets (GTPN), that we have developed. We describe the GTPN and how it is applied to the multiprocessor interference question. We reach several new conclusions. A commonly used definition of processing power can lead to substantial underestimation of the true processing power of the system. If the real system has a constant memory access time and any number of buses, then assuming an exponential access time can lead to substantial errors when estimating processing power probability distributions. In multibus systems with only a few buses a critical memory interrequest time exists. Performance close to that with a crossbar is attainable when the interrequest time is larger than the critical value. Obtaining these results illustrates the advantages, for moderate size state spaces, of the GTPN over simulation with respect to both model design and running time.

We have developed a Generalized Timed Petri Net (GTPN) model for evaluating the performance of computer systems. Our model is a generalization of the TPN model proposed by Zuberek [1] and extended by Razouk and Phelps [2]. In this paper, we define the GTPN model and present how performance estimates are obtained from the GTPN. We demonstrate the use of our automated GTPN analysis techniques on the dining philosophers example. This example violates restrictions made in the earlier TPN models. Finally, we compare the GTPN to the stochastic Petri net (SPN) models. We show that the GTPN model has capabilities for modeling and analyzing parallel systems lacking in existing SPN models. The GTPN provides an efficient, easily used method of obtaining accurate performance estimates for models of computer systems which include both deterministic and geometric holding times.

We use an exact analytical technique, based on Generalized Timed Petri Nets (GTPNs), to study the performance of shared bus cache consistency protocols for multiprocessors. We develop a general framework within which the key characteristics of the Write-Once protocol and four enhancements that have been combined in various ways in the literature can be identified and evaluated. We then quantitatively assess the performance gains for each of the four enhancements. We consider three levels of data sharing in our workload models. One of the enhancements substantially improves system performance in all cases. Two enhancements are shown to have negligible effect over the range of workloads analyzed. The fourth enhancement shows a small improvement for low levels of sharing, but shows more substantial improvement as sharing is increased, if we assume a “good access pattern”. The effects of two architectural parameters, the blocksize and the main memory cycle time are also considered.

An environment to support designers in the modeling, analysis, and simulation of concurrent systems is described. It is shown how a fully nested structure model supports multilevel design and focuses attention on the interfaces between the modules which serve to encapsulate behavior. Using simple examples, it is shown how a formal graph model can be used to model behavior in three domains: control flow, data flow, and interpretation. The effectiveness of the explicit environment model in SARA is discussed and the capability to analyze correctness and evaluate performance of a system model is demonstrated. A description of the integral help designed into SARA shows how the designer can be offered consistent use of any new tool introduced to support the design process.