Network design is a storied discipline with a decades-long history of impact and relevance, ranging from telephony networks in the 1950s to modern networks optimized for distributed ML training in the 2020s. Despite this rich history, there are surprising shortcomings in the available analysis and design tools. To name a few: (1) designers often need to reimplement known techniques to evaluate new networks (2) even basic network performance metrics (e.g., sparsest cut or bisection bandwidth) are not easy to visually analyze, resulting in inadvertent errors in published literature, (3) modern techniques for network topology synthesis under various constraints are not easily accessible, and (4) comprehensive comparisons across all known previous network designs is cumbersome. In this work, we introduce an online tool - Library of Networks- that addresses these shortcomings by combining two key functionalities in a unified tool for network design and analysis. First, Library of Networks implements a database of known network topologies that serves as a design pool from which network designers can browse/select networks that satisfy their design requirements. In addition, it enables researchers to comprehensively compare with prior designs without the implementation burden. Second, Library of Networks implements a broad (and expandable) collection of analysis and synthesis routines/kernels that can be used to analyze/generate networks. The analysis kernels in the initial release of the tool include basic performance metrics, deadlock-free routing, highthroughput routing, VC assignment, cycle-level simulation, collective communication scheduling, and area/power estimation. Each of these analysis implementations are easily reusable for new network designs because of the integrated tool design. Library of Networks also supports network synthesis via optimization for objective-seeking design-space exploration. We believe that the tool will be of wide interest to academic researchers, students, and designers in industry.

Basic Local Alignment Search Tool (BLAST/BLASTP) [3], often referred to as the Google of biological research [9], is widely used to query a large database to find homologous gene/protein sequences. Though there have been attempts to accelerate BLASTP, the protein sequence alignment tool, on GPUs, they remain slower than CPU/multicore-based multi-threaded implementations. In this paper, we introduce BLAZE, a GPU-accelerated drop-in replacement for BLASTP that produces identical results while achieving speedups over both multithreaded and GPU-accelerated implementations.

Over the past few decades, network topology design for general purpose, shared memory multicores has been primarily driven by human experts who use their insights to arrive at network designs that balance the competing goals of performance requirements (e.g., latency, bandwidth) and cost constraints (e.g., router radix, router counts). On the other hand, there have been automatic NoC synthesis methods for SoCs to optimize for application-specific communication and objectives such as resource usage or power. Unfortunately, these techniques do not lend themselves to the general-purpose context, where directly applying these previous NoC synthesis techniques in the general-purpose context yields poor results, even worse than expert-designed networks. We design and develop an automatic network design methodology – NetSmith– to design networks for general-purpose, shared memory multicores that comprehensively outperform expert-designed networks.

Deep neural networks (DNNs), while enormously popular, continue to place ever higher compute demand for which GPUs provide specialized matrix multipliers called tensor cores. To reduce the compute demand via sparsity, Nvidia Ampere’s tensor cores support 2:4 structured sparsity in the filters (i.e., two non-zeros out of four values) which provides uniform 50% sparsity without any load imbalance issues. Consequently, the sparse tensor cores maintain (input or output) operand stationarity, which is fundamental for avoiding high-overhead hardware, requiring only one extra 4-1 multiplexer per multiply-accumulate unit (MAC). However, 2:4 sparsity is limited to 2x improvements in performance and energy without loss of accuracy, whereas unstructured sparsity provides 5-6x opportunity albeit while causing load imbalance. Previous papers on unstructured sparsity incur high hardware overhead (e.g., buffering, crossbars, scatter-gather networks, and address calculators) mainly due to sacrificing operand stationarity in favor of load balance. To avoid adding high overheads to the highly-efficient tensor cores, we propose Eureka, an efficient tensor core for unstructured sparsity. Eureka addresses load imbalance via three contributions: (1) Our key insight is that a slight weakening of output stationarity achieves load balance most of the time while incurring only a modest hardware overhead. Accordingly, we propose single-step uni-directional displacement (SUDS), where a filter element’s multiplication can either occur in its original position or be displaced to a vacant MAC in the adjacent row below while the accumulation occurs in the original row to restore output stationarity. SUDS is an offline technique for inference. (2) We provide an optimal algorithm for work assignment for SUDS. (3) To achieve fewer bubbles in the tensor core’s systolic pipeline due to the irregularity of unstructured sparsity, we propose offline systolic scheduling to group together the sparse filters with similar, statically-known execution times (based on the number of non-zeros). Our evaluation shows that Eureka achieves 4.8x and 2.4x speedups, and 3.1x and 1.8x energy reductions over dense and 2:4 sparse (Ampere) implementations, respectively, and incurs area and power overheads of 6% and 11.5%, respectively, over Ampere.

Convolutional neural networks (CNNs) are emerging as powerful tools for image processing in important commercial applications. We focus on the important problem of improving the latency of image recognition. While CNNs are highly amenable to prefetching and multithreading to avoid memory latency issues, CNNs’ large data – each layer’s input, filters, and output – poses a memory bandwidth problem. While previous work captures only some of the enormous data reuse, full reuse implies that the initial input image and filters are read once from off-chip and the final output is written once off-chip without spilling the intermediate layers’ data to off-chip. We propose Occam to capture full reuse via four contributions. First, we identify the necessary conditions for full reuse. Second, we identify the dependence closure as the sufficient condition to capture full reuse using the least on-chip memory. Third, because the dependence closure is often too large to fit in on-chip memory, we propose a dynamic programming algorithm that optimally partitions a given CNN to guarantee the least off-chip traffic at the partition boundaries for a given on-chip capacity. While tiling is well-known, our contribution determines the optimal cross-layer tiles. Occam’s partitions reside on different chips, forming a pipeline so that a partition’s filters and dependence closure remain on-chip as different images pass through (i.e., each partition incurs off-chip traffic only for its inputs and outputs). Finally, because the optimal partitions may result in an unbalanced pipeline, we propose staggered asynchronous pipelines (STAPs) that replicate bottleneck stages to improve throughput by staggering mini-batches across replicas. Importantly, STAPs achieve balanced pipelines without changing Occam’s optimal partitioning. Our simulations show that, on average, Occam cuts off-chip transfers by 21× and achieves 2.04× and 1.21× better performance, and 33% better energy than the base case, respectively. Using a field-programmable gate array (FPGA) implementation, Occam performs 6.1× and 1.5× better, on average, than the base case and Layer Fusion, respectively.

Recent breakthroughs in machine learning (ML) have sparked hardware innovation for efficient execution of the emerging ML workloads. For instance, due to recent refine-ments and high-performance implementations, well-established gradient boosting decision tree (GBT) models (e.g., XGBoost) have demonstrated their dominance in commercially-important contexts, such as table-based datasets (e.g., relational databases and spreadsheets). Unfortunately, GBT training and inference are time-consuming (e.g., several hours of training for large datasets). Despite their importance, GBTs have not been targeted for hardware acceleration as much as neural networks. We propose Booster, a novel accelerator for GBTs based on their unique characteristics. We observe that the dominant steps of GBT training and inference (accounting for 90-98% of time) involve simple, fine-grained, independent operations on small-footprint data structures (e.g., histograms and shallow trees) - i.e., GBT is on-chip memory bandwidth-bound. Unfortunately, existing multicores and GPUs do not support massively-parallel data structure accesses that are irregular and data-dependent. By employing a scalable sea-of-small-SRAMs approach and an SRAM bandwidth-preserving mapping of data record fields to the SRAMs called group-by-field mapping, Booster achieves significantly more parallelism (e.g., 3200-way parallelism) than multicores and GPUs. In addition, Booster employs a redun-dant data representation that significantly lowers the memory bandwidth demand. Our simulations reveal that Booster achieves 11.4x and 6.4x speedups for training, and 45x and 22x (21x and 11x) speedups for offline (online) inference, over an ideal 32-core multicore and an ideal GPU, respectively. Based on ASIC synthesis of FPGA-validated RTL using 45 nm technology, we estimate a Booster chip to occupy 60 mm2of area and dissipate 23 W when operating at 1-G Hz clock speed.

Recognizing the importance of whole genome alignment (WGA), the National Institutes for Health maintains LASTZ, a sequential WGA application. As genomic data grows, there is a compelling need for scalable, high-performance WGA. Unfortunately, high-sensitivity, `gapped' alignment which uses dynamic programming (DP) is slow, whereas faster alignment with ungapped filtering is often less sensitive. We develop FastZ, a GPU-accelerated, gapped WGA software which matches gapped LASTZ in sensitivity. FastZ employs a novel inspector-executor scheme in which (a) the lightweight inspector elides DP traceback except in common, extremely short alignments, where the inspector performs limited, eager traceback to eliminate the executor, and (b) executor trimming avoids unnecessary work. Further, FastZ employs register-based cyclic-buffering to drastically reduce memory traffic, and groups DP problems by size for load balance. FastZ running on an RTX 3080 GPU and our multicore implementation of LASTZ achieve 111x and 20x speedups over the sequential LASTZ, respectively.

Causal consistency has emerged as an attractive middle-ground to architecting cloud storage systems, as it allows for high availability and low latency, while supporting semantics stronger than eventual consistency. However, causally-consistent cloud storage systems have seen limited deployment in practice. A key factor is these systems employ full replication of all the data in all the data centers (DCs), incurring high cost. A simple extension of current causal systems to support partial replication by clustering DCs into rings incurs availability and latency problems. We propose Karma, the first system to enable causal consistency for partitioned data stores while achieving the cost advantages of partial replication without the availability and latency problems of the simple extension. Our evaluation with 64 servers emulating 8 geo-distributed DCs shows that Karma (i) incurs much lower cost than a fully-replicated causal store (obviously due to the lower replication factor); and (ii) offers higher availability and better performance than the above partial-replication extension at similar costs.

Recent Spectre attacks exploit hardware speculative execution to read forbidden data. The attacks speculatively load forbidden data in misspeculated paths creating a side channel via the microarchitectural state which is not cleaned up after a misspeculation. The side channel then leaks the data. We focus on the most-challenging Spectre variant (Spectre-v1) which exploits sandboxing through bounds checking. Because the forbidden data can be accessed in only three ways only one of which remains challenging (Spectre-v1), whereas the data can be leaked through numerous side channels all of which must be plugged, preventing the access in the first place is more practical. Recent hardware schemes plug some side channels but incur significant complexity and performance loss and remain susceptible to other side channels. Most current software mitigations are architecture-dependent, have performance or semantic uncertainty problems, or both. We propose a compiler-based mitigation, called Secure Automatic Bounds Checking (SABC), which uses a simple sequence of three instructions to prevent forbidden access. The instructions have straightforward semantics and are found in all 32- and 64-bit architectures. An alternative, architecture-independent technique that leverages process boundaries– site isolation – incurs 1.8x memory overhead and 30% performance overhead over the baseline with no isolation. SABC is architecture-independent, has assured semantics, incurs little performance overhead, and renders current and future side channels useless for Spectre-v1.

Advances in machine learning (ML) have ignited hardware innovations for efficient execution of the ML models many of which are memory-bound (e.g., long short-term memories, multi-level perceptrons, and recurrent neural networks). Specifically, inference using these ML models with small batches, as would be the case at the Cloud edge, has little reuse of the large filters and is deeply memory-bound. Simultaneously, processing-in or -near memory (PIM or PNM) is promising unprecedented high-bandwidth connection between compute and memory. Fortunately, the memory-bound ML models are a good fit for PIM. We focus on digital PIM which provides higher bandwidth than PNM and does not incur the reliability issues of analog PIM. Previous PIM and PNM approaches advocate full processor cores which do not conform to PIM's severe area and power constraints. We describe Newton, a major DRAM maker's upcoming accelerator-in-memory (AiM) product for machine learning, which makes the following contributions: (1) To satisfy PIM's area constraints, Newton (a) places a minimal compute of only multiply-accumulate units and buffers in the DRAM which avoids the full-core area and power overheads of previous work and thus makes PIM feasible for the first time, and (b) employs a DRAM-like interface for the host to issue commands to the PIM compute. The PIM compute is rate-matched to the internal DRAM bandwidth and employs a non-intuitive, global input vector buffer shared by the entire channel to capture input reuse while amortizing buffer area cost. To the host, Newton's interface is indistinguishable from regular DRAM without any offloading overheads and PIM/non-PIM mode switching, and with the same deterministic latencies even for floating-point commands. (2) To prevent the PIM-host interface from becoming a bottleneck, we include three optimizations: commands which gang multiple compute operations both within a bank and across banks; complex, multi-step compute commands - both of which save critical command bandwidth; and targeted reduction of tFAWoverhead. (3) To capture output vector reuse with reasonable buffering, Newton employs an unusually-wide interleaved layout for the matrix. Our simulations running state-of-the-art neural networks show that building on a realistic HBM2E-like DRAM, Newton achieves 10x and 54x average speedup over a non-PIM system with infinite compute that perfectly uses the external DRAM bandwidth and a realistic GPU, respectively.

Remote Direct Memory Access (RDMA) fabrics such as InfiniBand and Converged Ethernet report latency shorter by a factor of 50 than TCP. As such, RDMA is a potential replacement for TCP in datacenters (DCs) running low-latency applications, such as Web search and memcached. InfiniBand’s Shared Receive Queues (SRQs), which use two-sided send/recv verbs (i.e., channel semantics ), reduce the amount of pre-allocated, pinned memory (despite optimizations such as InfiniBand’s on-demand paging (ODP)) for message buffers. However, SRQs are limited fundamentally to a single message size per queue, which incurs either memory wastage or significant programmer burden for typical DC traffic of an arbitrary number (level of burstiness) of messages of arbitrary size. We propose remote indirect memory access (RIMA) , which avoids these pitfalls by providing (1) network interface card (NIC) microarchitecture support for novel queue semantics and (2) a new “verb” called append . To append a sender’s message to a shared queue, the receiver NIC atomically increments the queue’s tail pointer by the incoming message’s size and places the message in the newly created space. As in traditional RDMA, the NIC is responsible for pointer lookup, address translation, and enforcing virtual memory protections. This indirection of specifying a queue (and not its tail pointer, which remains hidden from senders) handles the typical DC traffic of an arbitrary sender sending an arbitrary number of messages of arbitrary size. Because RIMA’s simple hardware adds only 1--2 ns to the multi-\mu s message latency, RIMA achieves the same message latency and throughput as InfiniBand SRQ with unlimited buffering. Running memcached traffic on a 30-node InfiniBand cluster, we show that at similar, low programmer effort, RIMA achieves significantly smaller memory footprint than SRQ. However, while SRQ can be crafted to minimize memory footprint by expending significant programming effort, RIMA provides those benefits with little programmer effort. For memcached traffic, a high-performance key-value cache ( FastKV ) using RIMA achieves either 3× lower 96 th-percentile latency or significantly better throughput or memory footprint than FastKV using RDMA.

Though Remote Direct Memory Access (RDMA) promises to reduce datacenter network latencies significantly compared to TCP (e.g., 10x), end-to-end congestion control in the presence of incasts is a challenge. Targeting the full generality of the congestion problem, previous schemes rely on slow, iterative convergence to the appropriate sending rates (e.g., TIMELY takes 50 RTTs). Several papers have shown that even in oversubscribed datacenter networks most congestion occurs at the receiver. Accordingly, we propose a divide-and-specialize approach, called Dart, which isolates the common case of receiver congestion and further subdivides the remaining in-network congestion into the simpler spatially-localized and the harder spatially-dispersed cases. For receiver congestion, we propose direct apportioning of sending rates (DASR) in which a receiver for n senders directs each sender to cut its rate by a factor of n, converging in only one RTT. For the spatially-localized case, Dart provides fast (under one RTT) response by adding novel switch hardware for in-order flow deflection (IOFD) because RDMA disallows packet reordering on which previous load balancing schemes rely. For the uncommon spatially-dispersed case, Dart falls back to DCQCN. Small-scale testbed measurements and at-scale simulations, respectively, show that Dart achieves 60% (2.5x) and 79% (4.8x) lower 99t'-percentile latency, and similar and 58% higher throughput than InfiniBand, and TIMELY and DCQCN.

Convolutional neural networks (CNNs) are emerging as powerful tools for image processing. Recent machine learning work has reduced CNNs' compute and data volumes by exploiting the naturally-occurring and actively-transformed zeros in the feature maps and filters. While previous semi-sparse architectures exploit one-sided sparsity either in the feature maps or the filters, but not both, a recent fully-sparse architecture, called Sparse CNN (SCNN), exploits two-sided sparsity to improve performance and energy over dense architectures. However, sparse vector-vector dot product, a key primitive in sparse CNNs, would be inefficient using the representation adopted by SCNN. The dot product requires finding and accessing non-zero elements in matching positions in the two sparse vectors -- an inner join using the position as the key with a single value field. SCNN avoids the inner join by performing a Cartesian product capturing the relevant multiplications. However, SCNN's approach incurs several considerable overheads and is not applicable to non-unit-stride convolutions. Further, exploiting reuse in sparse CNNs fundamentally causes systematic load imbalance not addressed by SCNN. We propose SparTen which achieves efficient inner join by providing support for native two-sided sparse execution and memory storage. To tackle load imbalance, SparTen employs a software scheme, called greedy balancing, which groups filters by density via two variants, a software-only one which uses whole-filter density and a software-hardware hybrid which uses finer-grain density. Our simulations show that, on average, SparTen performs 4.7x, 1.8x, and 3x better than a dense architecture, one-sided sparse architecture, and SCNN, respectively. An FPGA implementation shows that SparTen performs 4.3x and 1.9x better than a dense architecture and a one-sided sparse architecture, respectively.

It is very hard to coordinate changes across independently administered cloud services in a dependable manner due to several features of its service-oriented architecture: (i) services are often unaware of how a change will affect other services; (ii) impacted services may respond to changes in diverse ways; and (iii) the asynchronous nature of cross-service communication can introduce subtle errors. To tackle these challenges, our major contribution in this paper is a platform for Automated Change COoRDination (ACCORD) across independently administered cloud services. ACCORD (i) provides the abstractions and protocols for services to explicitly register direct dependencies on shared resources and automatically tracks cross-service transitive dependencies; (ii) allows each service to specify custom change coordination policies; and (iii) enables dependable change coordination in several real-world use-cases with minimal overhead to cloud administrators.

The technology-push of die stacking and application pull of Big Data machine learning analytics (BMLA) have created a unique opportunity for processing-near-memory (PNM). This paper makes four contributions: (1) While previous PNM work explores general MapReduce workloads, we identify three application characteristics of most BMLAs: (a) irregular-and-compute-light (i.e., perform only a few operations per input word which include data-dependent branches and indirect memory accesses); (b) compact (i.e., the relevant portion of the input data and the intermediate live data for each thread are small); and (c) memory-row-dense (i.e., process the input data without skipping over many bytes). These characteristics, except for irregularity, are necessary for bandwidth-and energy-efficient PNM, irrespective of the architecture. (2) Based on these characteristics, we propose memory optimizations for a "sea of simple MIMD cores (SSMC)" PNM architecture, called Millipede, which (pre) fetches and operates on entire memory rows to exploit BMLAs' row-density. Instead of this row-oriented access and compute-schedule, traditional multicores opportunistically improve row locality while fetching and operating on cache blocks. (3) Millipede employs well-known MIMD execution to handle BMLAs' irregularity, and sequential prefetch of input data to hide memory latency. In Millipede, however, one corelet prefetches a row for all the corelets which may stray far from each other due to their MIMD execution. Consequently, a leading corelet may prematurely evict the prefetched data before a lagging corelet has consumed the data. Millipede employs cross-corelet flow-control to prevent such eviction. (4) Millipede further exploits its flow-controlled prefetch for frequency scaling based on coarse-grain compute-memory rate-matching which decreases (increases) the processor clock speed when the prefetch buffers are empty (full). Using simulations, we compare PNM architectures to show that Millipede improves performance and energy, by 135% and 27% over a GPGPU with prefetch, and by 35% and 36% over SSMC with prefetch, when all three PNM architectures use the same resources (i.e., number of cores and on-processor-die memory) and identical die-stacking.

Despite much recent progress, Web page latencies over cellular networks remain much higher than those over wired networks. Proxies that execute Web page JavaScript (JS) and push objects needed by the client can reduce latency. However, a key concern is the scalability of the proxy which must execute JS for many concurrent users. In this paper, we propose to scale the proxies, focusing on a design where the proxy's execution is solely to push the needed objects and the client completely executes the page as normal. Such redundant execution is a simple, yet effective approach to cutting network latencies, which dominate page load delays in cellular settings. We develop whittling, a technique to identify and execute in the proxy only the JS code necessary to identify and push the objects required for the client page load, while skipping other code. Whittling is closely related to program slicing, but with the important distinction that it is acceptable to approximate the program slice in the proxy given the client's complete execution. Experiments with top Alexa Web pages show NutShell can sustain, on average, 27\% more user requests per second than a proxy performing fully redundant execution, while preserving, and sometimes enhancing, the latency benefits.

Accelerators have emerged as an important component of modern cloud, datacenter, and HPC computing environments. However, launching tasks on remote accelerators across a network remains unwieldy, forcing programmers to send data in large chunks to amortize the transfer and launch overhead. By combining advances in intra-node accelerator unification with one-sided Remote Direct Memory Access (RDMA) communication primitives, it is possible to efficiently implement lightweight tasking across distributed-memory systems. This paper introduces Extended Task Queuing (XTQ), an RDMA-based active messaging mechanism for accelerators in distributed-memory systems. XTQ's direct NIC-to-accelerator communication decreases inter-node GPU task launch latency by 10-15% for small-to-medium sized messages and ameliorates CPU message servicing overheads. These benefits are shown in the context of MPI accumulate, reduce, and allreduce operations with up to 64 nodes. Finally, we illustrate how XTQ can improve the performance of popular deep learning workloads implemented in the Computational Network Toolkit (CNTK).

File system performance is critical for overall performance of Big Data workloads. Typically, Big Data file systems consist of dual layers; a local node-level file system and a global file system. This paper presents the design and implementation of MorphStore, a local file system design that significantly improves performance when accessing large files by using two key innovations. First, MorphStore uses a load-adaptive I/O access scheduling technique that dynamically achieves the benefits of striping at low load and the throughput benefits of replication at high loads. Second, MorphStore uses a utility-driven replication to maximize the utility of replication capacity by allocating replication capacity to popular read-mostly files. Experiments reveal that MorphStore achieves 8% to 12% higher throughput while using significantly less replication for workloads that access large files. If we consider the performance-capacity tradeoff of file systems built on static techniques such as JBOD, RAID-0 and RAID-1 MorphStore extends the Pareto frontier to achieve better performance at the same replication capacity.

The mapping of MPI processes to compute nodes on a supercomputer can have a significant impact on communication performance. For high performance computing (HPC) applications with iterative communication, rich offline analysis of such communication can improve performance by optimizing the mapping. Unfortunately, current practices for at-scale HPC consider only the communication graph and network topology in solving this problem. We propose Routing Algorithm aware Hierarchical Task Mapping (RAHTM) which leverages the knowledge of the routing algorithm to improve task mapping. RAHTM achieves high quality mappings by combining (1) a divide-and-conquer strategy to achieve scalability, (2) a limited search of mappings, and (3) a linear programming based routing-aware approach to evaluate possible mappings in the search space. RAHTM achieves 20% reduction in the communication time and 9% reduction in the overall execution time for three communication-heavy benchmarks scaled up to 16,384 processes on a Blue Gene/Q platform.

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.

The need for fast address translation within tight time constraints (before L1 tag check but after effective address computation) imposes many design constraints. The freedom from such constraints can potentially lead to lower TLB energy costs. In this paper, we observe that (1) data accesses commonly use base-displacement addressing modes in which the effective address is computed as the sum of a base and a displacement, and (2) the effective page numbers are predictable once the base address is known. Further, it is easy to cache address translations alongside the predicted page numbers thus enabling speculative address translation that can filter accesses to the TLB. The two observations enable our PreTrans design in which (a) a speculative translation is available based solely on the base address, and (b) the translation is available simultaneously with the effective (virtual) address. PreTrans replaces most of the energy-expensive CAM-lookups for TLB access with RAM lookups, which translates to significant power improvements in the TLB.

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.

Die-stacking technology allows conventional DRAM to be integrated with processors. While numerous opportunities to make use of such stacked DRAM exist, one promising way is to use it as a large cache. Although previous studies show that DRAM caches can deliver performance benefits, there remain inefficiencies as well as significant hardware costs for auxiliary structures. This paper presents two innovations that exploit the bursty nature of memory requests to streamline the DRAM cache. The first is a low-cost Hit-Miss Predictor (HMP) that virtually eliminates the hardware overhead of the previously proposed multi-megabyte Miss Map structure. The second is a Self-Balancing Dispatch (SBD) mechanism that dynamically sends some requests to the off-chip memory even though the request may have hit in the die-stacked DRAM cache. This makes effective use of otherwise idle off-chip bandwidth when the DRAM cache is servicing a burst of cache hits. These techniques, however, are hampered by dirty (modified) data in the DRAM cache. To ensure correctness in the presence of dirty data in the cache, the HMP must verify that a block predicted as a miss is not actually present, otherwise the dirty block must be provided. This verification process can add latency, especially when DRAM cache banks are busy. In a similar vein, SBD cannot redirect requests to off-chip memory when a dirty copy of the block exists in the DRAM cache. To relax these constraints, we introduce a hybrid write policy for the cache that simultaneously supports write-through and write-back policies for different pages. Only a limited number of pages are permitted to operate in a write-back mode at one time, thereby bounding the amount of dirty data in the DRAM cache. By keeping the majority of the DRAM cache clean, most HMP predictions do not need to be verified, and the self balancing dispatch has more opportunities to redistribute requests (i.e., only requests to the limited number of dirty pages must go to the DRAM cache to maintain correctness). Our proposed techniques improve performance compared to the Miss Map-based DRAM cache approach while simultaneously eliminating the costly Miss Map structure.

Recent work has examined using application-specific knowledge of streaming communication to optimize network routing (for throughput/performance) and/or design (for simpler hardware). Previous techniques have assumed that the communication streams are directly mapped to networks-on-chip. In contrast, this paper explores the use of communication transformations (TransCom) to achieve higher throughput via better network load balance and more efficient network utilization while retaining the communication semantics of the original streaming application. Specifically, we propose two transformations: stream fission and stream fusion. (While fission and fusion transformations have been applied to computation in streaming programs, we are the first to propose these transformations for stream communication.) Fission splits communication streams in to multiple streams that may be routed over independent network paths to achieve better network load balance. Fusion targets multicast communication and fuses multiple streams to effectively capture the well-known benefits of tree-based multicast, which include more efficient link utilization. Both techniques can be integrated in an integer linear program formulation that is solved at compile time. Evaluations with a suite of StreamIT benchmarks show that TransCom achieves significant performance improvement (nearly 60% on average) over prior application-specific (non-transformed) routing techniques.

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.

Transactional memory (TM) has been proposed to address some of the programmability issues of chip multiprocessors. Hardware implementations of transactional memory (HTMs) have made significant progress in providing support for features such as long transactions that spill out of the cache, and context switches, page and thread migration in the middle of transactions. While essential for the adoption of HTMs in real products, supporting these features has resulted in significant state overhead. For instance, TokenTM adds at least 16 bits per block in the caches which is significant in absolute terms, and steals 16 of 64 (25%) memory ECC bits per block, weakening error protection. Also, the state bits nearly double the tag array size. These significant and practical concerns may impede the adoption of HTMs, squandering the progress achieved by HTMs. The overhead comes from tracking the thread identifier and the transactional read-sharer count at the Ll-block granularity. The thread identifier is used to identify the transaction, if only one, to which an Ll-evicted block belongs. The read-sharer count is used to identify conflicts involving multiple readers (i.e., write to a block with non-zero count). To reduce this overhead, we observe that the thread identifiers and read-sharer counts are not needed in a majority of cases. (1) Repeated misses to the same blocks are rare within a transaction (i.e., locality holds). (2) Transactional read-shared blocks that both are evicted from multiple sharers' Lis and are involved in conflicts are rare. Exploiting these observations, we propose a novel HTM, called LiteTM, which completely eliminates the count and identifier and uses software to infer the lost information. Using simulations of the STAMP benchmarks running on 8 cores, we show that LiteTM reduces TokenTM's state overhead by about 87% while performing within 4%, on average, and 10%, in the worst case, of TokenTM.

Emerging solid-state storage media can significantly improve storage performance and energy. However, the high cost-per-byte of solid-state media has hindered wide-spread adoption in servers. This paper proposes a new, cost-effective architecture - SieveStore - which enables the use of solid-state media to significantly filter access to storage ensembles. Our paper makes three key contributions. First, we make a case for highly-selective, storage-ensemble-level disk-block caching based on the highly-skewed block popularity distribution and based on the dynamic nature of the popular block set. Second, we identify the problem of allocation-writes and show that selective cache allocation to reduce allocation-writes - sieving - is fundamental to enable efficient ensemble-level disk-caching. Third, we propose two practical variants of SieveStore. Based on week-long block access traces from a storage ensemble of 13 servers, we find that the two components (sieving and ensemble-level caching) each contribute to SieveStore's cost-effectiveness. Compared to unsieved, ensemble-level disk-caches, SieveStore achieves significantly higher hit ratios (35%-50% more, on average) while using only 1/7th the number of SSD drives. Further, ensemble-level caching is strictly better in cost-performance compared to per-server caching.

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.

Pipelined processor cores are conventionally designed to accommodate the critical paths in the critical pipeline stage(s) in a single clock cycle, to ensure correctness. Such conservative design is wasteful in many cases since critical paths are rarely exercised. Thus, configuring the pipeline to operate correctly for rarely used critical paths targets the uncommon case instead of optimizing for the common case. In this study, we describe Trifecta-an architectural technique that completes common-case, subcritical path operations in a single cycle but uses two cycles when the critical path is exercised. This increases slack for both single-and two-cycle operations and offers a unique advantage under process variation. In contrast with existing mechanisms that trade power or performance for yield, Trifecta improves the yield while preserving performance and power. We applied this technique to the critical pipeline stages of a superscalar out-of-order (OoO) and a single issue in-order processor, namely instruction issue and execute, respectively. Our experiments show that the rare two-cycle operations result in a small decrease (5% for integer and 2% for floating-point benchmarks of SPEC2000) in instructions per cycle. However, the increased delay slack causes an improvement in yield-adjusted-throughput by 20% (12.7%) for an in-order (InO) processor configuration.

Streaming is emerging as an important programming model for multicores. Streaming provides an elegant way to express task decomposition and inter-task communication, while hiding laborious orchestration details such as load balancing, assignment (of stream computation to nodes) and computation/communication scheduling from the programmer. This paper develops a novel communication optimization for streaming applications based on the observation that streaming computations typically involve large, systematic data transfers between known communicating pairs of nodes over extended periods of time. From the above observation, we advocate a family of routing algorithms that expend some over overheads to compute disjoint paths for stream communication. Disjoint-path routing is an attractive design point because (a) the overheads of discovering disjoint paths are amortized over large periods of time and (b) the benefits of disjoint path routing are significant for bandwidth-sensitive streaming applications. We develop one instance of disjoint-path routing called tentacle routing-a backtracking, best-effort technique. On a 4 times 4 (6 times 6) system, tentacle routing results in 55% (84%) and 28% (41%) mean throughput improvement for high-network-contention streaming applications, and for all streaming applications, respectively.

Researchers have proposed clustered microarchitectures for performance and energy effciency. Typically, clustered microarchitectures offer fast, local bypassing between instructions within clusters but global bypasses are slower. Traditional clustered microarchitectures (TCM) are implemented by partitioning the register file and associated functional

Microfluidics has enabled lab-on-a-chip technology to miniaturize and integrate biological and chemical analyses to a single chip comprising channels, valves, mixers, heaters, separators, and sensors. Recent papers have proposed programmable labs-on-a-chip as an alternative to traditional application-specific chips to reduce design effort, time, and cost. While these previous papers provide the basic support for programmability, this paper identifies and addresses a practical issue, namely, fluid volume management. Volume management addresses the problem that the use of a fluid depletes it and unless the given volume of a fluid is distributed carefully among all its uses, execution may run out of the fluid before all its uses are complete. Additionally, fluid volumes should not overflow (i.e., exceed hardware capacity) or underflow (i.e., fall below hardware resolution). We show that the problem can be formulated as a linear programming problem (LP). Because LP's complexity and slow execution times in practice may be a concern, we propose another approach, called DAGSolve, which over-constrains the problem to achieve linear complexity while maintaining good solution quality. We also propose two optimizations, called cascading and static replication, to handle cases involving extreme mix ratios and numerous fluid uses which may defeat both LP and DAGSolve. Using some real-world assays, we show that our techniques produce good solutions while being faster than LP.

Crossbar arbitration - which determines the allocation of output ports to packets in the input queues - is a performance-critical stage in the overall performance of routers for input-queued networks. The overall performance of crossbar arbitration depends on two metrics: (a) matching power - the ability of the arbiter to maximize the number of matches between requesting inputs and free outputs and (b) arbitration throughput - the number of such matches per unit time. Ideally, crossbar arbitration should maximize both metrics. Unfortunately, implementing high performance matching schemes compromises arbitration throughput. Similarly, simpler arbitration mechanisms that deliver high arbitration throughput offer lower matching power. The major contribution of this paper is the design of a table-lookup based crossbar arbitration mechanism - TabArb - that delivers superior matching and high arbitration throughput for minimal-routed, two dimensional mesh and torus networks. The two key innovations of TabArb are: (a) it forwards multiple requests from each input port to multiple output ports to expose adequate matching potential and (b) it employs precomputed tables that store maximum cardinality matches for all possible request combinations. Our technique improves the saturation throughput of adaptive routed mesh network by 14.8%. It offers little improvement for the DOR router due to limited opportunity.

Advances in microfluidic research has enabled lab-on-a-chip (LoC) technology to achieve miniaturization and integration of biological and chemical analyses to a single chip comprising channels, valves, mixers, heaters, separators, and sensors. These miniature instruments appear to offer the rare combination of faster, cheaper, and higher-precision analyses in comparison to conventional bench-scale methods. LoCs have been applied to diverse domains such as proteomics, genomics, biochemistry, virology, cell biology, and chemical synthesis. However, to date LoCs have been designed as application-specific chips which incurs significant design effort, turn-around time, and cost, and degrades designer and user productivity. To address these limitations, we envision a programmable LoC (PLoC) and propose a comprehensive fluidic instruction set, called AquaCore Instruction Set (AIS), and a fluidic microarchitecture, called AquaCore, to implement AIS. We present four key design aspects in which the AIS and AquaCore differ from their computer counterparts, and our design decisions made on the basis of the implications of these differences. We demonstrate the use of the PLoC in a range of domains by hand-compiling real-world microfluidic assays in AIS, and show a detailed breakdown of the execution times for the assays and an estimate of the chip area.

The role of the operating system (OS) in managing shared resources such as CPU time, memory, peripherals, and even energy is well motivated and understood [23]. Unfortu-nately, one key resource|lower-level shared cache in chip multi-processors|is commonly managed purely in hardware by rudimentary replacement policies such as least-recently-used (LRU). The rigid nature of the hardware cache manage-ment policy poses a serious problem since there is no single best cache management policy across all sharing scenarios. For example, the cache management policy for a scenario where applications from a single organization are running under \\best eort " performance expectation is likely to be dierent from the policy for a scenario where applications from competing business entities (say, at a third party data center) are running under a minimum service level expecta-tion. When it comes to managing shared caches, there is an inherent tension between \nexibility and performance. On one hand, managing the shared cache in the OS oers im-mense policy \nexibility since it may be implemented in soft-ware. Unfortunately, it is prohibitively expensive in terms of performance for the OS to be involved in managing tempo-rally ne-grain events such as cache allocation. On the other hand, sophisticated hardware-only cache management tech-niques to achieve fair sharing or throughput maximization have been proposed. But they oer no policy \nexibility. This paper addresses this problem by designing architec-tural support for OS to eciently manage shared caches with a wide variety of policies. Our scheme consists of a hard-ware cache quota management mechanism, an OS interface and a set of OS level quota orchestration policies. The hard-ware mechanism guarantees that OS-specied quotas are en-forced in shared caches, thus eliminating the need for (and the performance penalty of) temporally ne-grained OS in-tervention. The OS retains policy \nexibility since it can tune the quotas during regularly scheduled OS interventions. We demonstrate that our scheme can support a wide range of policies including policies that provide (a) passive per-

Minimizing latency and maximizing throughput are important goals in the design of routing algorithms for interconnection networks. Ideally, we would like a routing algorithm to (a) route packets using the minimal number of hops to reduce latency and preserve communication locality, (b) deliver good worst-case and average-case throughput and (c) enable low-complexity (and hence, low latency) router implementation. In this paper, we focus on routing algorithms for an important class of interconnection networks: two dimensional (2D) mesh networks. Existing routing algorithms for mesh networks fail to satisfy one or more of design goals mentioned above. Variously, the routing algorithms suffer from poor worst case throughput (ROMM by Nesson, and Johnsson (1995), DOR by Sullivan and Bashkow, 1977), poor latency due to increased packet hops (VALIANT by Valiant and Brebner (1981)) or increased latency due to hardware complexity (minimal-adaptive by Duato, (1993), Upadhyay, Varavithya and Mohapatra, (1997)). The major contribution of this paper is the design of an oblivious routing algorithm-O1TURN-with provable near-optimal worst-case throughput, good average-case through-put, low design complexity and minimal number of network hops for 2D-mesh networks, thus satisfying all the stated design goals.

Network performance in tightly-coupled multiprocessors typically degrades rapidly beyond network saturation. Consequently, designers must keep a network below its saturation point by reducing the load on the network. Congestion control via source throttling-a common technique to reduce the network load-prevents new packets from entering the network in the presence of congestion. Unfortunately, prior schemes to implement source throttling either lack vital global information about the network to make the correct decision (whether to throttle or not) or depend on specific network parameters, or communication patterns. This paper presents a global-knowledge-based, self-tuned, congestion control technique that prevents saturation at high loads across different communication patterns for k-ary n-cube networks. Our design is composed of two key components. First, we use global information about a network to obtain a timely estimate of network congestion. We compare this estimate to a threshold value to determine when to throttle packet injection. The second component is a self-tuning mechanism that automatically determines appropriate threshold values based on throughput feedback. A combination of these two techniques provides high performance under heavy load, does not penalize performance under light load, and gracefully adapts to changes in communication patterns.

The performance of both serial and parallel implementations of matrix multiplication is highly sensitive to memory system behavior. False sharing and cache conflicts cause traditional column-major or row-major array layouts to incur high variability in memory system performance as matrix size varies. This paper investigates the use of recursive array layouts to improve performance and reduce variability. Previous work on recursive matrix multiplication is extended to examine several recursive array layouts and three recursive algorithms: standard matrix multiplication and the more complex algorithms of Strassen (1969) and Winograd. While recursive layouts significantly outperform traditional layouts (reducing execution times by a factor of 1.2-2.5) for the standard algorithm, they offer little improvement for Strassen's and Winograd's algorithms. For a purely sequential implementation, it is possible to reorder computation to conserve memory space and improve performance between 10 percent and 20 percent. Carrying the recursive layout down to the level of individual matrix elements is shown to be counterproductive; a combination of recursive layouts down to canonically ordered matrix tiles instead yields higher performance. Five recursive layouts with successively increasing complexity of address computation are evaluated and it is shown that addressing overheads can be kept in control even for the most computationally demanding of these layouts.

One-track performance in tightly-coupled multiprocessors typically, degrades rapidly beyond network saturation. Consequently, designers must keep a network below its saturation point by reducing the load on the network. Congestion control via source throttling-a common technique to reduce the network load-presents new packets from entering the network in the presence of congestion. Unfortunately, prior schemes to implement source throttling either lack vital global information about the network to make the correct decision (whether to throttle or not) or depend on specific network parameters, network topology or communication pattern. This paper presents a global-knowledge-based, self-tuned, congestion control technique that prevents saturation at high loads across different network configurations and commutation pattern. Our design is composed of two key components. First, we use global information about a network to obtain a timely estimate of network congestion. We compare this estimate to a threshold value to determine when to throttle packet injection. The second component is a self-tuning mechanism that automatically determines appropriate threshold values based on throughput feedback. A combination of these two techniques provides high performance under heavy load does not penalize performance under light load, and gracefully adapts to changes in communication patterns.

Programming languages that provide multidimensional arrays and a flat linear model of memory must implement a mapping between these two domains to order array elements in memory.This layout function is fixed at language definition time and constitutes an invisible, non-programmable array attribute.In reality, modem memory systems are architecturally hierarchical rather than flat, with substantial differences in performance among different levels of the hierarchy.This mismatch between the model and the true architecture of memory systems can result in low locality of reference and poor performance.Some of this loss in performance can be recovered by re-ordering computations using transformations such as loop tiling.We explore nonlinear array layout functions as an additional means of improving locality of reference.For a benchmark suite composed of dense matrix kernels, we show by timing and simulation that two specific layouts (4D and Morton) have low implementation costs (2-5% of total running time) and high performance benefits (reducing execution time by factors of 1.1-2.5);that they have smooth performance curves, both across a wide range of problem sizes and over representative cache architectures; and that recursion-based control structures may be needed to tilly exploit their potential.

Matrix multiplication is an important kernel in linear algebra algorithms, and the performance of both serial and parallel implementations is highly dependent on the memory system behavior. Unfortunately, due to false sharing and cache conflicts, traditional column-major or row-major array layouts incur high variability in memory system performance as matrix size varies. This paper investigates the use of recursive array layouts for improving the performance of parallel recursive matrix multiplication algorithms. We extend previous work by Frens and Wise on recursive matrix multiplication to examine several recursive array layouts and three recursive algorithms: standard matrix multiplication, and the more complex algorithms of Strassen and Winograd. We show that while recursive array layouts significantly outperform traditional layouts (reducing execution times by a factor of 1.2--2.5) for the standard algorithm, they offer little improvement for Strassen's and Winograd's algorithms; ...

Strassen's algorithm for matrix multiplication gains its lower arithmetic complexity at the expense of reduced locality of reference, which makes it challenging to implement the algorithm efficiently on a modern machine with a hierarchical memory system. We report on an implementation of this algorithm that uses several unconventional techniques to make the algorithm memory-friendly. First, the algorithm internally uses a non- standard array layout known as Morton order that is based on a quad-tree decomposition of the matrix. Second, we dynamically select the recursion truncation point to minimize padding without affecting the performance of the algorithm, which we can do by virtue of the cache behavior of the Morton ordering. Each technique is critical for performance, and their combination as done in our code multiplies their effectiveness. Performance comparisons of our implementation with that of competing implementations show that our implementation often outperforms the alternative techniques (up to 25%). However, we also observe wide variability across platforms and across matrix sizes, indicating that at this time, no single implementation is a clear choice for all platforms or matrix sizes. We also note that the time required to convert matrices to/from Morton order is a noticeable amount of execution time (5% to 15%). Eliminating this overhead further reduces our execution time.