Distributed memory caching systems (e.g., memcached) offer tremendous performance improvements for multi-tiered applications compared to architectures that directly access the storage layer. Unfortunately, the performance improvements are artificially limited by load imbalance in the memcached server pool. Specifically, we show that skewed key popularity induces significant load imbalance, which in turn can cause significant degradation in the tail (i.e., 90+th %ile) latency. Based on this understanding, we design and implement SPORE -- an augmented memcached variant which uses self-adapting, popularity-based replication to mitigate the effects of such load imbalance. SPORE uses reactive internal key renaming as a basic mechanism to efficiently achieve replication without excessive communication and/or coordination among servers and clients. Further, our SPORE design offers the same consistency model (with added time-bounds on write propagation) as a system with memcached. Based on evaluations on a "wimpy-node" testbed and on Amazon EC2, we show that SPORE achieves significantly higher performance than the baseline memcached.

Cloud computing holds the exciting potential of elastically scaling computation to match time-varying demand, thus eliminating the need to provision for peak demand. However, the uncertainty of variable loads necessitate the use of margins - servers that must be held active to absorb unpredictable potential load bursts - which can be a significant fraction of overall cost. Further, naively switching to an on-demand cloud model can actually degrade true costs (server costs that would be incurred even if margin costs disappeared) because of the fundamental economic rule wherein on-demand services/goods cost more compared to reserved services/goods where the user bears some commitment. On-demand customers pay a premium in exchange for not undertaking the fixed-cost risk that committed customers undertake. This paper addresses the twin challenges of minimizing margin costs and true costs in an Infrastructure-as-a-Service (IaaS) cloud. Our paper makes the following two contributions. First, rather than use a fixed margin, we observe that the margin may be selectively used depending on load levels. Based on the above observation, we develop ShrinkWrap-opt which is a dynamic programming algorithm that achieves optimal margin cost while satisfying the desired (statistical) response time guarantees. Second, we propose commitment straddling - the selective use of some reserved machines in conjunction with on-demand machines - to achieve optimal true-cost. Simulations with real Web server load traces using the Amazon EC2 cost model reveal that our techniques save between 13% and 29% (21% on average) in cost while satisfying response-time targets.

Cloud computing holds the exciting potential of elastically scaling computation to match time-varying demand, thus eliminating the need to provision for peak demand to satisfy response-time requirements. Moreover, cloud vendors often offer several commitment levels for their machine instances (e.g., users can choose to pay an upfront premium for the discounted hourly usage price). Because cost is a major concern that may limit the cloud adoption, two key challenges are to determine (a) the number of machines to provision and (b) the commitment level at which the machine instances should be acquired, to minimize cost while satisfying response-time targets. This paper address the above two challenges in an Infrastructure-as-a-Service (IaaS) cloud. Our simulations with real Web server load traces reveal that our techniques offer a cost reduction between 13% and 29% (21% on average) under Amazon EC2 pricing models.

As chip multiprocessors scale the number of on chip cores, the superior scalability of multihop networks compared to buses and crossbars makes multihop networks the choice interconnection strategy. However, a significant part of the networks' energy is consumed in the buffers used to handle link contention via back pressured routing. Recent work proposes to apply well-known backpressure less routing techniques, which eliminate buffers, and hence buffer power(static and dynamic), at the cost of some misrouting/dropping upon link contention (misrouted/dropped flits are eventually recovered/retransmitted). At low loads, misrouting (dropping)is rare and hence backpressure less routing performs well. Unfortunately, backpressure less routers incur significant misrouting/dropping under high loads and saturate at lower throughputs than back pressured networks, resulting in poorer performance and energy. We make the key observation that because load varies significantly across applications, back pressureless and back pressured networks are not robust in performance-energy across the spectrum of high and low loads. That is, at high loads backpressure less networks suffer considerable performance and energy disadvantage compared to back pressured networks, and the energy disadvantage reverse sat low loads. To address this robustness issue, we propose a novel adaptive flow control (AFC) router which dynamically adapts between back pressured and backpressure less flow control. AFC employs three novel mechanisms, namely local contention thresholds, gossip-induced mode-switch, and lazy VCallocation. The first mechanism maximizes performance (and minimizes energy) in the common case, and the second mechanism ensures correctness in corner cases. The third mechanism exploits flit-by-flit routing in AFC's back pressured mode to simplify VC allocation and reduces the buffer requirements by a factor of two in AFC's back pressured mode. Simulations using commercial workloads and SPLASH-2 confirm AFC'srobustness by showing that AFC achieves performance and energy that are closer to that of the better of backpressure and backpressure less networks.

In deep submicron technology, wire delay is no longer negligible and is gradually becoming a dominant factor of system performance. Several state-of-the-art architectural synthesis flows have already adopted the distributed register architecture to cope with the increasing wire delay by allowing multicycle communication. In this paper, we formulate channel and register allocation within a refined regular distributed register architecture, named RDR-GRS, as a problem of simultaneous data transfer routing and scheduling for minimizing global interconnect resources. We also present an innovative algorithm with both spatial and temporal considerations. It features both a concentration-oriented path router gathering wire-sharable data transfers and a channel-based time scheduler resolving contentions for wires in a channel, which are in spatial and temporal domain, respectively. The experimental results show that the proposed algorithm can significantly outperform existing related works.

This paper presents a method to save energy for mobile systems that perform content-based image retrieval (CBIR). CBIR is a computation-intensive application and a resource-constrained mobile system may save energy by offloading computation to a grid-powered server. We develop three offloading schemes based on different conditions to save energy for CBIR on mobile systems. We implement a CBIR algorithm on an HP iPAQ hw6945 and physically measure the energy savings.

We present an adaptive loading scheme to save energy for content based image retrieval (CBIR) in a mobile system. In CBIR, images are represented and compared by high-dimensional vectors called features. Loading these features into memory and comparing them consumes a significant amount of energy. Our method adaptively reduces the features to be loaded into memory for each query image. The reduction is achieved by estimating the difficulty of the query and by reusing cached features in memory for subsequent queries. We implement our method on a PDA and obtain overall energy reduction of 61.3% compared with an existing CBIR implementation.