Hardware support for fault-driven page migration and on-demand memory allocation along with the advancements in unified memory runtime in modern graphics processing units (GPUs) simplify the memory management in discrete CPU-GPU heterogeneous memory systems and ensure higher programmability. GPUs adopt to accelerate general purpose applications as they are now an integral part of heterogeneous computing platforms ranging from supercomputers to commodity cloud platforms. However, data-intensive applications face the challenge of device-memory oversubscription as the limited capacity of bandwidth-optimized GPU memory fails to accommodate their increasing working sets. Performance overhead under memory oversubscription comes from the thrashing of memory pages over slow CPU-GPU interconnect. Depending on the diverse computing and memory access pattern, each application demands special attention from memory management. As a result, the responsibility of effectively utilizing the plethora of memory management techniques supported by GPU programming libraries and runtime falls squarely on the application programmer. This paper presents a smart runtime that leverages the faults and page-migration information to detect underlying patterns in CPU-GPU interconnect traffic. Based on the online workload characterization, the extended unified memory runtime dynamically chooses and employs a suitable policy from a wide array of memory management strategies to address the issues with memory oversubscription. Experimental evaluation shows that this smart adaptive runtime provides 18% and 30% (geometric mean) performance improvement across all benchmarks compared to the default unified memory runtime under 125% and 150% device memory oversubscription, respectively.

Error correction and fault tolerance have become pivotal considerations as conventional memories scale and emerging memories come to market. The common thread in these reliability challenges is that deep scaling reveals outliers in the memory system, which are responsible for the vast majority of faults. These cells, which may be attributed to process variation or undetected fabrication defects, tend to be more vulnerable to various forms of crosstalk, read- and write-disturbance, and even radiation-induced faults. By tracking faults in memory cells, identifying the worst offenders, and mitigating their effects accordingly, we can design dramatically improved fault tolerance techniques that are tuned to the fault characteristics of the memory at hand. A critical piece is the development of scalable and fault tolerance registries to track and retain critical information about these faults. The fault registries must be able to function in the faulty memory they protect, operate efficiently at the cell/bit-level, and handle extreme fault rates. Using the knowledge of faulty locations, our fault tolerance techniques applied to conventional main memories like DRAM and endurance-limited memories like flash and phase-change memory improve reliability, endurance, and lifetime by orders of magnitude while maintaining performance and energy efficiency.

Achieving resilience in extreme-scale environments, while minimizing energy consumption, is a daunting challenge. At extreme scale, however, the classic checkpoint-restart approach or replication for recovery techniques become inadequate. In this paper, we propose a novel application-aware elastic resilience model, dShadowing, for extreme-scale environments, as an efficient and scalable alternative to checkpointing, pure replication and re-execution. The basic tenet of this model is a dShadow, which is a derivative of its associated main process, whose functional and non-functional attributes are derived to achieve high tolerance to failure, at a minimum energy cost, while closely adhering to QoS requirements. Contrary to current schemes, dShadowing assumes heterogeneous environments, where cores fail independently, but non-identically. The experiment’s results show that dShadowing model can achieve on average over 20% reduction in energy consumption and expected completion time, in comparison to a baseline shadowing model that considers cores fail uniformly. The results also demonstrate the flexibility of the dShadowing model and the ability to tolerate failure at scale adaptively and efficiently.

The use of hardware encryption and new memory technologies such as phase change memory (PCM) are gaining popularity in a variety of server applications such as cloud systems. While PCM provides energy and density advantages over conventional DRAM memory, it faces endurance challenges. Such challenges are exacerbated when employing memory encryption as the stored data is essentially randomized, losing data similarity and reducing or eliminating the effectiveness of energy and endurance oriented encoding techniques. This results in increasing dynamic energy consumption and accelerated wear out. In this article, we propose CASTLE, a technique for in-memory encryption to leverage this encryption process to improve reliability in the presence of endurance faults. We also propose TOWERs for CASTLE that improve reliability as well as energy for encrypted data through a novel application of compression and encoding. CASTLE and TOWERs are compatible with error-correction codes (ECC) and error correction pointers (ECP), the standard for mitigating endurance faults in PCM. When combining CASTLE and TOWERS, we achieve an average lifetime improvement of over 45× compared to SECDED ECC, 7.1× compared to SECRET, and 3.6× compared to the leading partition-and-flip fault-tolerance approach (AEGIS) for the same area overhead.

Efficient memory sharing among multiple compute engines plays an important role in shaping the overall application performance on CPU-GPU heterogeneous platforms. Unified Virtual Memory (UVM) is a promising feature that allows globally-visible data structures and pointers such that the GPU can access the physical memory space on the CPU side, and take advantage of the host OS paging mechanism without explicit programmer effort. However, a key requirement for the guaranteed performance is effective hardware support of address translation. Particularly, we observe that GPU execution suffers from high TLB miss rates in a UVM environment, especially for irregular and/or memory-intensive applications. In this paper, we propose simple yet effective compression mechanisms for address translations to improve GPU TLB hit rates. Specifically, we explore and leverage the TLB compressibility during the execution of GPU applications to design efficient address translation compression with minimal runtime overhead. Experimental results across 22 applications indicate that our proposed approach significantly improves GPU TLB hit rates, which translate to 12% average performance improvement. Particularly, for 16 irregular and/or memory-intensive applications, the performance improvements achieved reach up to 69.2%, with an average of 16.3%.

Reliability-aware speedup models study the expected speedup of a parallel application as a function of the number of processors, on a platform susceptible to processor failures. Existing works in this area have developed models using checkpoint-restart (without replication) as the only fault tolerance mechanism, and have studied the upper bound on the number of processors beyond which the application speedup starts to degrade due to increasing likelihood of failure. In this work, we develop speedup models in which replication, specifically dual replication, is also employed for resilience. We demonstrate that the upper bound on the number of processors to execute a perfectly parallel application using dual replication is of the order λ^-^2 where λ is the individual processor failure rate. We also compare the dual replication model with that of no-replication. Specifically, we found that, given the same hardware resources, replication starts offering better speedup just before the upper bound on the number of processors for no-replication is reached. Taken together, our results indicate that replication can significantly enhance reliability-aware speedup models by i) pushing the number of processors that yield the optimal speedup to a much higher value than what is possible without replication, and ii) improving on the optimal speedup possible through checkpoint-restart alone.

To maintain appropriate yields in deeply scaled technologies requires fault-tolerance of increasingly high fault rates. These fault rates far exceed traditional general approaches such as ECC, particularly when faults accrue over time. Effective fault tolerance at such high fault rates requires detailed bit-level knowledge of the location of faulty cells. We provide a solution to this problem in the form of a space efficient, bit-level fault map called FLOWER. FLOWER utilizes Bloom filters to provide detailed fault characterization for a relatively small overhead. We demonstrate how FLOWER can enable improved fault tolerance at high fault rates by enhancing existing fault tolerance proposals and yielding 10–100x improvements. Using in-memory processing, FLOWER can maintain a less than 2% performance overhead at 10E-4 fault rates with less than 2% loss of memory density to report bit-level faults with high accuracy. Using a tuned novel hashing technique called MinCI, FLOWER for memory achieves considerably lower false positives than with disk-level hashing techniques at a fraction of the performance overhead. With a new technique to protect against errors during in-memory operations, PETAL bits, FLOWER can remain resilient against random errors while efficiently targeting predictable errors. Furthermore, we propose a new fault tolerance scheme called FaME, which provides ultra-efficient bit-level sparing by using the FLOWER fault map to identify the location of faults. FLOWER+FaME can achieve 14x longer PCM memory lifetime with half the area overhead versus SECDED ECC.

Unified Memory in heterogeneous systems serves a wide range of applications. However, limited capacity of the device memory becomes a first order performance bottleneck for data-intensive general-purpose applications with increasing working sets. The performance overhead under memory oversubscription depends on the memory access pattern of the corresponding workload. While a regular application with sequential, dense memory access suffers from long latency write-backs, performance of a irregular application with sparse, seldom access to large data-sets degrades due to page thrashing. Although smart spatio-temporal prefetching and large page eviction yield good performance in general, remote zero-copy access to host-pinned memory proves to be beneficial for irregular, data-intensive applications. Further, new generation GPUs introduced hardware access counters to delay page migration and reduce memory thrashing. However, the responsibility of deciding what strategy is the best fit for a given application relies heavily on the programmer based on thorough understanding of the memory access pattern through intrusive profiling. In this work, we propose a programmer-agnostic runtime that leverages the hardware access counters to automatically categorize memory allocations based on the access pattern and frequency. The proposed heuristic adaptively navigates between remote zero-copy access to host-pinned memory and first-touch page migration based on the trade-off between low latency remote access and high-bandwidth local access. We show that although designed to address memory oversubscription, our scheme has no impact on performance when working sets fit in the device-local memory. Experimental results show that our scheme provides performance improvement of 22% to 78% for irregular applications under 125% memory oversubscription compared to the state of the art. At the same time, regular applications are not impacted by the framework.

In this paper, we propose a new parallelism model denoted as MPI * X and suggest a linear algebra-based graph analytics system, namely, Graphite, which effectively employs it. MPI * X promotes thread-based partitioning to distribute computation and communication across threads on a cluster of machines, while eliminating the need for unnecessary thread synchronizations. Consequently, it contrasts with the traditional MPI + X parallelism model , which utilizes process-based partitioning to distribute data among processes as a way to scale out on a cluster of machines (the MPI part), then splits each partition into subpartitions among the threads of each process as a method to scale up within a machine (the X part). Besides adopting MPI * X, Graphite is NUMA-aware. In particular, it assigns threads to partitions in a way that exploits CPU and memory affinity, alongside leveraging faster MPI shared memory transport. Moreover, it adopts a variant of the popular GAS (Gather, Apply, and Scatter) computing model, thus decoupling the computation of partitions from the communication of partial results. Lastly, it supports thread-level asynchrony, which does not only overlap the computation with communication, but further interleaves multiple communications. We compared Graphite against GraphPad, Gemini, and LA3 graph analytics systems in an HPC environment using different graph applications. Results show that Graphite is roughly up to 3X faster than these state-of-the-art systems.

This paper presents Triply Compressed Sparse Column (TCSC), a novel compression technique designed specifically for matrix-vector operations where the matrix as well as the input and output vectors are sparse. We refer to these operations as SpMSpV2. TCSC compresses the nonzero columns and rows of a highly sparse matrix representing a large real-world graph. During this compression, it encodes the sparsity patterns of the input and output vectors within the compressed representation of the sparse matrix itself. Consequently, it aligns the compressed indices of the input and output vectors with those of the compressed matrix columns and rows, thus eliminating the need for extra indirections when SpMSpV2operations access the vectors. This results in fewer cache misses, greater space efficiency and faster execution times. We evaluate TCSC's performance and show that it is more space and time efficient compared to CSC and DCSC, with up to 11× speedup. We integrate TCSC into GraphTap, our suggested linear algebra-based distributed graph analytics system. We compare GraphTap against GraphPad and LA3, two state-of-the-art linear algebra-based distributed graph analytics systems, using different dataset scales and numbers of processes. GraphTap is up to 7× faster than these systems due to TCSC and the resulting communication efficiency.

Spintronic domain wall memories (DWMs) are prone to alignment faults, which cannot be protected by traditional error correction techniques. To solve this problem, we propose a new technique called derived error correction coding (DECC). We construct metadata from the data and shift state of the DWM, on demand, using a novel transverse read (TR). TR reads in an orthogonal direction to the DWM access point and can determine the number of ones in a DWM. Errors in the metadata correspond to shift-faults in the DWM. Rather than storing the metadata, it is created on-demand and protected by storing parity bits. Repairing the metadata with ECC allows restoration of DWM alignment and ensures correct operation. Through these techniques, our shift-aware error correction approaches provide a lifetime of over 15 years with a similar performance, while reducing area and energy by 370% and 52%, versus the state-of-the-art, for a 32-bit nanowire.

In-memory checkpointing has increased in popularity over the years because it significantly improves the time to take a checkpoint. It is usually accomplished by placing all or part of a processor's checkpoint into the local memory of a remote node within the cluster. If, however, the checkpointed node and the node containing its checkpoint both fail in quick succession, recovery using in-memory checkpoints becomes impossible. In this paper, we explore the problem of placing in-memory checkpoints among nodes whose individual failure likelihoods are not identical. We provide theoretical results on the optimal way to place in-memory checkpoints such that the probability of occurrence of a catastrophic failure, i.e. failure of a node as well as the node containing its checkpoint, is minimized. Using the failure logs spread over 5 years of a 49,152 node supercomputer, we show that checkpoint placement schemes that utilize knowledge of node failure likelihoods, and are guided by the theoretical results we provide, can significantly reduce the total number of such catastrophic failures when compared with placement schemes that are oblivious of the heterogeneity in nodes based on their failure likelihoods.

Memory capacity in GPGPUs is a major challenge for data-intensive applications with their ever increasing memory requirement. To fit a workload into the limited GPU memory space, a programmer needs to manually divide the workload by tiling the working set and perform user-level data migration. To relieve the programmer from this burden, Unified Virtual Memory (UVM) was developed to support on-demand paging and migration, transparent to the user. It further takes care of the memory over-subscription issue by automatically performing page replacement in an oversubscribed GPU memory situation. However, we found that naïve handling of page faults can cause orders of magnitude slowdown in performance. Moreover, we observed that although prefetching of data from CPU to GPU can hide the page fault latency, the difference among various prefetching mechanisms can lead to drastically different performance results. To this end, we performed extensive experiments on GeForceGTX 1080ti GPUs with PCI-e 3.0 16x to discover that there exists an effective prefetch mechanism to enhance locality in GPU memory. However, as the GPU memory is filled to its capacity, such prefetching mechanism quickly proves to be counterproductive due to locality unaware eviction policy. This necessitates the design of new eviction policies that are aware of the hardware prefetcher semantics. We propose two new programmer-agnostic, locality-aware pre-eviction policies which leverage the mechanics of existing hardware prefetcher and thus incur no additional implementation and performance overhead. We demonstrate that combining the proposed tree-based pre-eviction policy with the hardware prefetcher provides an average of 93% and 18.5% performance speed-up compared to LRU based 4KB and 2MB page replacement strategies, respectively. We further examine the memory access pattern of GPU workloads under consideration to analyze the achieved performance speed-up.

Scaling limitations of conventional and emerging memories has provided the impetus for the increased focus on reliability techniques to overcome associated physical limitations of non-perfect devices. However, despite these reliability advances, critical challenges remain to be solved as new memory types and memory vulnerabilities arise. There continues to be no simulator with extended reliability models for easy comparison of existing and newly developed techniques nor simple integration of innovative new reliability concepts and failure modes. The mission of our simulator, PremSim, is to provide a framework which solves these fundamental limitations. While PremSim can function using memory traces, it was also designed from the ground-up to be fully integrated with several external simulators including the Structural Simulation Toolkit (SST) as a memory backend. It can connect to other detailed memory backends such as DRAMSim2 for detailed energy and timing. Further, it provides modes which give estimated lifetime for endurance-limited memories, as well as the provable correction capability per row for a given fault distribution. To perform these calculations in a reasonable time window and to remain compatible with abstract full-system simulators, we also provide and verify novel abstractions. Additionally, we show case studies of how different fault mitigation strategies can be modeled effectively in PremSim including solutions at the page, row, word, and bit-level granularity of next-generation traditional and emerging faulty memories.

Big graph analytics is gaining a widespread momentum across different fields, including biology, computer vision, social networks, recommendation systems and transportation logistics, to mention just a few. Distributed systems for graph analytics are utilized as a mean to process big graphs. To distribute and balance computation and communication loads within a distributed graph analytics system, graph partitioning algorithms can be leveraged. In this paper, we propose Revolver, a machine learning-based graph partitioning algorithm. In particular, Revolver uses reinforcement learning and label propagation to efficiently and effectively carry out the task of graph partitioning. It employs a vertex-centric approach where each vertex in a graph is associated with an autonomous agent responsible for assigning a suitable partition to the vertex. In addition, it uses label propagation to evaluate the decency of partitioning. Evaluation results show that Revolver can produce highly balanced and localized partitions compared to three popular and state-of-the-art graph partitioning algorithms.

Phase change memory (PCM) has recently emerged as a promising technology to meet the fast growing demand for large capacity memory in computer systems, replacing DRAM that is impeded by physical limitations. Multi-level cell (MLC) PCM offers high density with low per-byte fabrication cost. However, despite many advantages, such as scalability and low leakage, the energy for programming intermediate states is considerably larger than programming single-level cell PCM. In this paper, we study encoding techniques to reduce write energy for MLC PCM when the encoding granularity is lowered below the typical cache line size. We observe that encoding data blocks at small granularity to reduce write energy actually increases the write energy because of the auxiliary encoding bits. We mitigate this adverse effect by 1) designing suitable codeword mappings that use fewer auxiliary bits and 2) proposing a new Word-Level Compression (WLC) which compresses more than 91% of the memory lines and provides enough room to store the auxiliary data using a novel restricted coset encoding applied at small data block granularities. Experimental results show that the proposed encoding at 16-bit data granularity reduces the write energy by 39%, on average, versus the leading encoding approach for write energy reduction. Furthermore, it improves endurance by 20% and is more reliable than the leading approach. Hardware synthesis evaluation shows that the proposed encoding can be implemented on-chip with only a nominal area overhead.

With the increase in scale of HPC systems, the frequency of system wide failures is expected to increase. The performance of Coordinated Checkpoint/Restart (C/R), the traditional fault tolerance technique, degrades under high failure rates because of frequent global rollbacks, which themselves are susceptible to failures. We propose CoLoR, a fault tolerance scheme that i)requires only the failing process to recover, ii)overlaps reexecution with restart, and iii)avoids the cumulative effect of successive failures. Our theoretical analysis reveals that such a scheme results in lower expected completion time than coordinated C/R. We also provide a proof-of-concept implementation in MPI using receiver based message logging and colocated rescuer (CoLoR)processes, and evaluate its performance on several HPC benchmarks. Our experimental results, combined with observations from the theoretical analysis, show that CoLoR can outperform both traditional C/R and replication over a large range of system sizes, without using extra logger nodes.

DRAM technology scaling has the undesirable side effect of degrading cell reliability. One such concern of deeply scaled DRAMs is the increased coupling between adjacent cells, commonly referred to as crosstalk. High access frequency of certain rows in the DRAM may cause data loss in cells of physically adjacent rows due to crosstalk. The malicious exploit of this crosstalk by repeatedly accessing a row to induce this effect is known as row hammering. Additionally, inadvertent row hammering may also occur due to the natural weighted nature of applications' access patterns. In this paper, we analyze the efficiency of existing approaches for mitigating wordline crosstalk and demonstrate that they have been conservatively designed. Given the unbalanced nature of DRAM accesses, a small group of dynamically allocated counters in banks can deterministically detect "hot" rows and mitigate crosstalk. Based on our findings, we propose a Counter-based Adaptive Tree (CAT) approach to mitigate wordline crosstalk using adaptive trees of counters to guide appropriate refreshing of vulnerable rows. The key idea is to tune the distribution of the counters to the rows in a bank based on the memory reference patterns. In contrast to deterministic solutions, CAT utilizes fewer counters, making it practically feasible to be implemented on-chip. Compared to existing probabilistic approaches, CAT more precisely refreshes rows vulnerable to crosstalk based on their access frequency. Experimental results on workloads from four benchmark suites show that CAT reduces the Crosstalk Mitigation Refresh Power Overhead in quad-core systems to 7%, which is an improvement over the 21% and 18% incurred in the leading deterministic and probabilistic approaches, respectively. Moreover, CAT incurs very low performance overhead (~0.5%). Hardware synthesis evaluation shows that CAT can be implemented on-chip with only a nominal area overhead.

Nanophotonic networks, a potential candidate for future networks on-chip, have been challenged for their reliability due to several device-level limitations. One of the main issues is that fabrication errors (a.k.a. process variations) can cause devices to malfunction, rendering communication unreliable. For example, the microring resonator, a preferred optical modulator device, may not resonate at the designated wavelength under process variations (PVs), leading to communication errors and bandwidth loss. This article proposes a series of solutions to the wavelength drifting problem of microrings and subsequent bandwidth loss problem of an optical network, due to PVs. The objective is to maximize network bandwidth through proper arrangement among microrings and wavelengths with minimum power requirements. Our arrangement, called “MinTrim,” solves this problem using simple integer linear programming, adding supplementary microrings, and allowing flexible assignment of wavelengths to network nodes as long as the resulting network presents maximal bandwidth. Each step is shown to improve bandwidth provisioning with lower power requirements. Evaluations on a sample network show that a baseline network could lose more than 40% bandwidth due to PVs. Such loss can be recovered by MinTrim to produce a network with 98.4% working bandwidth. In addition, the power required for arranging microrings is 39% lower than the baseline. Therefore, MinTrim provides an efficient PV-tolerant solution to improving the reliability of on-chip photonics.

Low latency is critical for emerging data-intensive real-time analytic and interactive single-wave applications. As the complexity and heterogeneity of cloud computing continue to increase, so will the frequency of errors, which will manifest themselves in unpredictable ways with a significant impact on the correctness of the computing and responsiveness of cloud services. In this paper, we propose a new data-centric computational model to improve the responsiveness of the data-intensive applications to crash faults and augment its ability to deal with silent errors to ensure computational accuracy. The basic tenet of the proposed model is a task replication scheme, which interweaves the processing of a replicated data split among multiple distributed tasks, with each task consuming data at a different offset. In the absence of a failure, the concurrent execution of the tasks ensures complete processing of the data split, with a significant reduction in the total execution time. In the case of an error, however, the remaining tasks take over the execution of the unfinished work and finish on time. The proposed scheme also guarantees timely detection and correction of silent data corruptions along with crash faults. We demonstrate the effectiveness of our scheme by extending Hadoop's MapReduce code base as a case study. Results show a performance improvement of 50% over Hadoop's Speculative Execution when dealing with crash-faults and an improvement of 33% when dealing with silent errors in case of no failure.

Emerging non-volatile memories have many advantages over conventional memory. Unfortunately, many are susceptible to write endurance challenges, resulting in stuck-at faults. Existing mitigation methods statically partition and invert data within a block containing such faults (partition-and-flip) to ensure data is written to match stuck-at cells such that they may remain in service. Unfortunately, these schemes have limited fault tolerance capabilities and require the assumption that their auxiliary bits are fault free. We propose a dynamic partitioning scheme that improves the number of tolerated stuck-at faults and simultaneously protects auxiliary bits. Dynamic partitioning can significantly improve the fault tolerance over existing static partitioning approaches with an equal number of auxiliary bits. Moreover, it can often still improve fault tolerance while reducing the number of auxiliary bits. Compared to flip-N-write and Aegis, a leading mitigation scheme, dynamic partitioning can achieve 7-72% and 5-53 x lower write error rates, respectively, for the same capacity overhead with a stuck-at-fault rate of 10-3.

Phase change memory is a promising alternative to conventional memories such as DRAM due to its density and non-volatility. Unfortunately, reliability is still a challenge as limited write endurance, exacerbated by process variation, leads to increasing numbers of stuck-at faults over the memory's lifetime. Error-correcting Pointers (ECP) is a popular proposal to mitigate stuck-at faults by recording the addresses and the values of faulty bits in order to extend the memory lifetime. In this paper, we propose Yoda, a method to extend ECP with one or a small number of additional encoding bits in order to dramatically improve the effectiveness and guaranteed fault correction capability of ECP. Our simulation results demonstrate that Yoda has a 3.0× improvement in fault coverage compared to a fault-aware ECP with a similar overhead, while also providing a 2.5-3.0× improvement over state-of-the-art schemes with comparable complexity.

GPUs have been widely adopted in data centers to provide acceleration services to many applications. Sharing a GPU is increasingly important for better processing throughput and energy efficiency. However, quality of service (QoS) among concurrent applications is minimally supported. Previous efforts are too coarse-grained and not scalable with increasing QoS requirements. We propose QoS mechanisms for a fine-grained form of GPU sharing. Our QoS support can provide control over the progress of kernels on a per cycle basis and the amount of thread-level parallelism of each kernel. Due to accurate resource management, our QoS support has significantly better scalability compared with previous best efforts. Evaluations show that, when the GPU is shared by three kernels, two of which have QoS goals, the proposed techniques achieve QoS goals 43.8% more often than previous techniques and have 20.5% higher throughput.

Designing reliable systems using scaled Spin-Transfer Torque Random Access Memory (STT-RAM) has become a significant challenge as the memory technology feature size is scaled down. The introduction of a more prominent read disturbance is a key contributor in this reliability challenge. However, techniques to address read disturbance are often considered in a vacuum that assumes other concerns like transient read errors (false reads) and write faults do not occur. This paper studies several techniques that leverage ECC to mitigate persistent errors resulting from read disturbance and write faults of STT-RAM while still considering the impact of transient errors of false reads. In particular, we study three policies to enable better-than-conservative read disturbance mitigation. The first policy, write after error (WAE), uses ECC to detect errors and write back data to clear persistent errors. The second policy, write after persistent error (WAP), filters out false reads by reading a second time when an error is detected leading to trade-off between write and read energy. The third policy, write after error threshold (WAT), leaves cells with incorrect data behind (up to a threshold) when the number of errors is less than the ECC capability. To evaluate the effectiveness of the different schemes and compare with the simple previously proposed scheme of writing after every read (WAR), we model these policies using Markov processes. This approach allows the determination of appropriate bit error rates in the context of both persistent and transient errors to accurately estimate the system reliability and the energy consumption of different error correction approaches. Our evaluations show that each of these policies provides benefits for different error scenarios. Moreover some approaches can save energy by an average of 99.5%, while incurring the same reliability as other approaches.

Studies show that non-graphics programs can be less optimized for the GPU hardware, leading to significant resource under-utilization. Sharing the GPU among multiple programs can effectively improve utilization, which is particularly attractive to systems where many applications require access to the GPU (e.g., cloud computing). However, current GPUs lack proper architecture features to support sharing. Initial attempts are preliminary: They either provide only static sharing, which requires recompilation or code transformation, or they do not effectively improve GPU resource utilization. We propose Simultaneous Multikernel (SMK), a fine-grain dynamic sharing mechanism, that fully utilizes resources within a streaming multiprocessor by exploiting heterogeneity of different kernels. We propose several resource allocation strategies to improve system throughput while maintaining fairness. Our evaluation shows that for shared workloads with complementary resource occupancy, SMK improves GPU throughput by 52% over non-shared execution and 17% over a state-of-the-art design.

This paper describes Concurrent Migration of Multiple Pages (CMMP), a new hardware-software mechanism for managing hybrid main memory (DRAM+PCM). CMMP migrates multiple pages concurrently without significantly affecting the memory bandwidth available to applications. CMMP provides a simple interface for the OS to observe memory access patterns. CMMP reduces PCM-to-DRAM transfer bandwidth by copying blocks on-demand. It also reduces DRAM-to-PCM bandwidth by suppressing the transfer of untouched blocks back to PCM. Compared to a state-of-the-art page migration approach for hybrid memory, CMMP improves performance by 14% and reduces energy consumption by 29% on average.

Emerging persistent memories (PM) such as PCM or STT-MRAM promise to make up for the shortcomings of DRAM which undergoes a scaling problem and a wasteful refresh power consumption. Hence, a future system memory is anticipated to be a hybrid of DRAM and PM. For such a system to achieve better performance, it is paramount to exploit the heterogeneity of memory access latencies with page swaps that place hot pages in faster, smaller DRAM and cold pages in slower, larger PM. The goal of this paper is to study the impact of a hardware-based page swap in a hybrid memory on the application performance. To this end, we propose a simple analytical model that evaluates the profitability of a page swap by considering a distribution ratio of memory requests between two memories and a varying access latency to each memory. By comparing the outcome of the model to the architecture simulation performance, we show that the proposed model is a useful tool to analyze the behavior of a page swap. Also, we propose and evaluate a model-guided, hardware-driven page swap mechanism which regulates page swaps online. Our experimental results show that the model appraises the profitability of a page swap with an accuracy of 90.9% for the studied workloads. Meanwhile, the model-guided page swap improves IPC performance, on average, by 28.9% and 13.3% compared to no page swap and static page swap schemes. In addition, our model-guided page swap dramatically reduces the number of page swaps by up to 17.3× over static page swap schemes, thus improving performance.

In a multicore system, many applications share the last-level cache (LLC) and memory bandwidth. These resources need to be carefully managed in a coordinated way to maximize performance. DRAM is still the technology of choice in most systems. However, as traditional DRAM technology faces energy, reliability, and scalability challenges, nonvolatile memory (NVM) technologies are gaining traction. While DRAM is read/write symmetric (a read operation has comparable latency and energy consumption as a write operation), many NVM technologies (such as Phase-Change Memory, PCM) experience read/write asymmetry: write operations are typically much slower and more power hungry than read operations. Whether the memory’s characteristics are symmetric or asymmetric influences the way shared resources are managed. We propose two symmetry-agnostic schemes to manage a shared LLC through way partitioning and memory through bandwidth allocation. The proposals work well for both symmetric and asymmetric memory. First, an exhaustive search is proposed to find the best combination of a cache way partition and bandwidth allocation. Second, an approximate scheme, derived from a theoretical model, is proposed without the overhead of exhaustive search. Simulation results show that the approximate scheme improves weighted speedup by at least 14% on average (regardless of the memory symmetry) over a state-of-the-art way partitioning and memory bandwidth allocation. Simulation results also show that the approximate scheme achieves comparable weighted speedup as a state-of-the-art multiple resource management scheme, XChange, for symmetric memory, and outperforms it by an average of 10% for asymmetric memory.

Phase-change memory (PCM) has emerged as a candidate that overcomes the physical limitations faced by DRAM and NAND flash memory. While PCM has desirable properties in terms of scalability and density, it suffers from limited endurance. Repeated writes cause PCM cells to wear out and get permanently stuck at a specific value. Recovering from stuck-at faults through a proactive error correcting scheme is essential for the widespread adoption of PCM. In this paper, we propose Symbol Shifting as a practical technique to increase the number of faults that an error correcting code can cover in single and multilevel cells memory chips. Since stuck-at cells can still be read, errors are manifested only when a worn-out cell is to be programmed with a symbol value different than the value it is stuck at. After a write operation fails for a given block of data, another write operation is attempted with all original data symbols shifted to another memory level. Shifting the data is likely to bring the number of errors within the nominal capability of the deployed error correcting code. Requiring only one additional auxiliary cell, Symbol Shifting can increase the number of faults that an error correcting code can cover by up to double the nominal capability and extends the lifetime by up to 37 percent.

Nonvolatile memory technologies such as Spin-Transfer Torque Random Access Memory (STT-RAM) and Phase Change Memory (PCM) are emerging as promising replacements to DRAM. Before deploying STT-RAM and PCM into functional systems, a number of challenges still remain must be addressed. Specifically, both require relatively high write energy, STT-RAM suffers from high bit error rates and PCM suffers from low endurance. A common solution to overcome those challenges is to minimize the number of bits changed per write. In this paper, we propose and evaluate the hybrid coset encoder to efficiently improve and balance the bit flip reduction for biased and unbiased data. The main core of the coset encoder consists of biased and unbiased vectors which maps the data input to a larger set of data vectors. Subsequently, the intermediate data vector that yields the least number of differences when compared to the currently stored data is selected. Our evaluation shows that hybrid coset encoder reduces bit flips by up to 25 percent over a baseline differential writing scheme. Further, our proposed scheme reduces bit flips by up to 20 percent over the leading bit-flip minimization scheme for biased data, while achieving very low decoding overhead similar to the Flip-N-Write scheme.

Computer architecture research relies on software simulation to evaluate processor performance. Single-threaded simulators have unacceptable simulation times when modeling complex architectures with hundreds of cores. While parallelizing a simulator can improve performance, parallel simulators face the issue of synchronizing threads, which forces them to trade performance for accuracy. We study relaxed synchronization policies for parallel architecture simulators and introduce the weighted-tuple synchronization policy. Weighted-tuple is a distributed synchronization scheme which improves upon existing policies. We evaluate weighted-tuple for two parallel simulator settings: multicore simulation and network-on-chip simulation. For the multicore setting using weighted-tuple synchronization, average simulation time is reduced by$8$percent over barrier synchronization; error is also reduced by$28$percent. For network-on-chip simulation, weighted-tuple synchronization improves simulation speed by$42$percent with an$0.3$percent error increase compared to the barrier baseline.

Register files are a key data storage unit that impacts instruction throughput for graphics processing units (GPUs). Typically, GPU register files are quite large to accommodate many concurrent threads and are implemented using the same SRAM technology as the on-chip cache. We propose contextrf, a new register file architecture that efficiently leverages register files with nonuniform access characteristics, including hybrid SRAM/DRAM (S/D) and spintronic domain-wall memories (DWMs). Contextrf allows greater-capacity register files to be implemented in the same area within the GPU, with reduced power consumption. We also propose contextPreRF, a hardware preswitch scheme to hide switching delays-as soon as a register request is queued, the nonuniform access memories containing the corresponding register are sent a preemptive switch request. Thus, our scheme transparently hides the penalties of switching between register contexts. After replacing the register file SRAM with S/D, we can reduce energy by 37%, with a 1.4% average performance drop. Employing DWM, we reduce register file energy by 74%, with a 0.4% average performance penalty. For the denser DWM, we model converting the saved area into additional registers, cache, and shared memory-this improves performance by 13.5% over the baseline SRAM register file.

Racetrack memory (RM), a spintronic domain-wall non-volatile memory has recently received attention as a high-capacity replacement for various structures in the memory system from secondary storage through caches. The main advantage of RM is an improved density and like other non-volatile memory structures, the static power of RM is dramatically lower than conventional CMOS memories. However, a major challenge of employing RM in universal memory components is the added access latency and dynamic energy consumption caused by shifts to align the data of interest with an access port. We propose multilane Racetrack caches (MRC), a RM last level cache design utilizing lightweight compression combined with independent shifting. MRC allows cache lines mapped to the same Racetrack structure to be accessed in parallel when compressed, mitigating potential shifting stalls in the RM cache. Our results demonstrate that unlike previously proposed RM caches, an isocapacity MRC cache replacement can outperform SRAM caches while providing energy improvement over STT-MRAM caches. In particular, MRC improves performance by 5% and reduces energy by 19% compared to an isocapacity baseline RM cache resulting in an energy delay product improvement of 25%.

Networks-on-chip (NoCs) have become a leading energy consumer in modern multi-core processors, with a considerable portion of this energy originating from the large number of virtual channel (FIFO) buffers. While emerging memories have been considered for many architectural components such as caches, the asymmetric access properties and relatively small size of network-FIFOs compared to the required peripheral circuitry has led to few such replacements proposed for NoCs. In this paper, we propose control schemes that leverage the\shift-register" nature of spintronic domain-wall memory (DWM) to replace conventional memory buffers for the NoC. Our results indicate that the best shift-based scheme utilizes a dual-nanowire approach to ensure that reads and writes can be more effectively aligned with access ports for simultaneous access in the same cycle. Our approach provides a 2.93X speedup over a DWM buffer using a traditional FIFO memory control scheme with a 1.16X savings in energy. Compared to a SRAM-FIFO it exhibits an 8% message latency degradation versus a 56% energy reduction. The resulting approach achieves a 53% reduction in energy delay product compared to SRAM and a 42% reduction in energy delay product versus STT-MRAM.

Nonvolatile memory technologies such as Phase Change Memory (PCM) and Spin-Transfer Torque Random Access Memory (STT-RAM) are emerging as promising replacements to DRAM. Before deploying STT-RAM and PCM into functional systems, a number of challenges still remain. Specifically, both require relatively high write energy, STT-RAM suffers from high bit error rates and PCM suffers from low endurance. A common solution to overcome those challenges is to minimize the number of bits changed per write. In this work, we introduce Pseudo-Random Encoding Scheme (PRES) to minimize the number of bit changes during memory writes. PRES maps the write data vector into an intermediate highly random set of data vectors. Subsequently, the intermediate data vector that yields the least number of differences when compared to the currently stored data is selected. Our evaluation shows that PRES reduces bit flips by up to 25% over a baseline differential writing scheme. Further, PRES reduces bit flips by 15% over the leading bit-flip minimization scheme, while decreasing encoding and decoding complexities by more than 90%.

NoCs (networks-on-chip) are commonly proposed as scalable on-chip interconnects for current and future CMPs (chip multi-processors) and many-core systems. While scalable, the lack of global control can create routing inefficiencies detrimental to the overall network latency. Recently, NoCs have been proposed that allow flits to traverse multiple network switches in a single cycle. This requires a more global view of control to allow routers along the path of a packet to configure their switches collectively. In this paper, we propose a reservation based circuit-switching design, MSCS, which provides simplified global control and multi-hop traversal while reducing latency. MSCS performs network control once per network dimension for the lifetime of a packet, while the leading methods require multiple arbitration steps depending on contention in the network. Furthermore, MSCS can perform control for a packet prior to the availability of resources through reservations, while previous schemes only perform control on-demand. Overall, MSCS can reduce the buffer size by 50% over the leading multi-hop scheme while maintaining a nominal latency improvement (1.4%). With the same buffer resources per port, MSCS achieves a 12.7% latency improvement.

Power consumption of main memory has become a critical concern and has led to proposals to employ emerging non-volatile memories (NVMs) to replace or augment DRAM. This paper proposes Space Oblivious COmpression (SOCO), an in-place lightweight compression mechanism particularly designed for reducing NVM-based main-memory energy rather than saving space. SOCO can significantly reduce the number of bits written to save considerable energy for NVM-based main memories. By relaxing the goal of a conventional compression, the proposed approach practically eliminates memory addressing and management overheads incurred by compression techniques designed to save space. Our experiments show that SOCO provides more than 50% reduction in bits written, resulting in 23% and 34% energy savings for Spin-transfer Torque (STT)-MRAM and Phase Change Memory (PCM), respectively.

For memory-intensiv e workloads with large memory footprints, superpages are effective to avoid address translation overhead, which can be a critical performance bottleneck. A superpage is a large virtual memory page that is mapped to an equivalently-sized amount of contiguous physical memory pages. Superpage mapping assumes physical memory does not contain retired pages, which is an important technique to improve memory resilience: the OS avoids allocating physical pages that have detected errors. Retired pages create unusable "holes" in the physical memory. We show that even a small percentage of retired pages makes it very difficult to find enough contiguous memory to form superpages. To address this problem, we propose GTSM, or gap-tolerant sequential mapping, that allows superpages to be formed even in the presence of retired physical pages. A new page table format is also proposed to support GTSM. This format has similar storage efficiency as traditional superpaging to hold address translations in the last-level cache. To further compress the page table and improve cache hit rates for address translation in large memory footprint workloads, we also propose an extended format that reduces the page table size by 50%. In comparison to an ideal memory without any retired physical pages, we show that our technique, with retired pages, achieves nearly 96.8% of the performance of traditional 2MB superpaging.

Phase Change Memory (PCM) and spin-transfer torque random access memory (STT-RAM) are emerging as new memory technologies to replace DRAM and NAND flash that are impeded by physical limitations. Programming PCM cells degrades their endurance while programming STT-RAM cells incurs a high bit error rate. Accordingly, several schemes have been proposed to service write requests while programing as few memory cells as possible. Nevertheless, those schemes did not address the asymmetry in programming memory cells that characterizes both PCM and STT-RAM. For instance, writing a bit value of 0 on PCM cells is more detrimental to endurance than 1 while writing a bit value of 1 on STT-RAM cells is more prone to error than 0. In this paper, we propose CAFO as a new cost aware flip reduction scheme. Essentially, CAFO encompasses a cost model that computes the cost of servicing write requests through assigning different costs to each cell that requires programming. Subsequently, CAFO encodes the data to be written into a form that incurs less cost through its cost aware encoding module. Overall, CAFO is capable of cutting down the write cost by up to 65% more than existing schemes.

As an emerging technology to empower on-chip communication of future many-core processors, optical crossbars achieve low uniform latency by providing non-blocking one-hop connectivity. Conventional token-based arbitration limits throughput by token injection rates so that large throughput are delivered by over provisioning optical channels, consuming significant optical power. In this paper, we propose pipelined distributed global arbitration for multiple-write multiple-read optical crossbars to improve energy efficiency without downgrading performance. Multiple requests for the same channel can be granted at the same cycle as long as no traffic conflicts occur. The proposed global arbitration scheme enables a scalable arbiter design which parallelizes the arbitration process and simplifies arbiter logic for low arbitration latency, low power and high network throughput. Our simulation results show that, the proposed design reduces execution time by 5% and power consumption by 20% using only 50% of channels and 75% of micro rings as in the best known baseline.

Co-simulation of computer architecture elements at different levels of abstraction and fidelity is becoming an increasing necessity for efficient experimentation and research. We propose reciprocal abstraction for computer architecture cosimulation, which allows the integration of simulation methods that utilize different levels of abstraction and fidelity of simulation. Further, reciprocal abstraction avoids the need to conduct detailed evaluations of individual computer architecture components entirely in a vacuum, which can lead to significant inaccuracies from ignoring the system context. Moreover, it allows an exploration of the impact on the full system resulting from design choices in the detailed component model. We demonstrate the potential inaccuracies of isolated component simulation. Using reciprocal abstraction, we integrate a parallel cycle-level networkon- chip (NoC) component into a detailed but more coarse-grain full system simulator.We show that co-simulation using reciprocal abstraction of the cycle-level network model reduces packet latency error compared to the more abstract network model by 69% on average. Additionally, as simulating a detailed network at the cycle-level can greatly increase simulation time over an abstract model, we implemented detailed network simulator using a GPU coprocessor. The CPU+GPU can reduce simulation time for the reciprocal abstraction co-simulation by 16% for a 256-core target machine and 65% for a 512-core target machine.

The size of main memory in modern computers is approaching energy and scalability limits. Combining DRAM and non-volatile memory (NVM) has been proposed to increase capacity and reliability, and to decrease energy consumption. Software-managed hybrid memory is a promising way to incorporate NVM in main memory due to its architectural simplicity. However, there are significant performance issues caused by interference due to data migration between DRAM and NVM and a lack of effective migration policies. To aid in the development of migration policies and hardware mechanisms for incorporating NVM in main memory, we propose new analysis and simulation techniques to understand the behavior of software-managed hybrid memory. These techniques allow us to characterize the overhead experienced by requests in the memory hierarchy and identify the factors that limit performance in software-managed hybrid memory. Using our techniques, we show that queuing delays at the NVM banks and NVM bus are the main limiting factors, and that there is significant potential to improve performance with better migration policies.

General-purpose computing on Graphics Processing Units (GPGPUs) became increasingly popular for a wide range of applications beyond traditional graphic rendering workloads. GPGPU exploits parallelism in applications via multithreading to hide memory latencies, and handles control complexity by barrier synchronizations. Warp scheduling algorithms have been optimized to increase memory latency hiding capability, improve cache behavior, or alleviate branch divergence. To date, there is no scheduler that accounts for the synchronization behavior among warps under the presence of multiple warp schedulers. In this paper, we develop a warp scheduling algorithm that is synchronization aware. The key observation is that excessive stall cycles may be introduced due to synchronizing warps residing in different warp schedulers. We propose that schedulers coordinate with each other to avoid warps from being blocked on a barrier for overly long. Such coordination will dynamically reorder the execution sequence of warps so that they are issued in proximity when a barrier is encountered. Performance evaluations demonstrate that our proposed coordinated schedulers can improve the performance of synchronization-rich benchmarks by 10% on average when compared to the state-of-the-art non-coordinating schedulers.

With their potential for high scalability and density, resistive memories are foreseen as a promising technology that overcomes the physical limitations confronted by charge-based DRAM and flash memory. Yet, a main burden towards the successful adoption and commercialization of resistive memories is their low cell reliability caused by process variation and limited write endurance. Typically, faulty and worn-out cells are permanently stuck at either ‘0’ or ‘1’. To overcome the challenge, a robust error correction scheme that can recover from many hard faults is required. In this paper, we propose and evaluate RDIS , a novel scheme to efficiently tolerate memory stuck-at faults. RDIS allows for the correct retrieval of data by recursively determining and efficiently keeping track of the positions of the bits that are stuck at a value different from the ones that are written, and then, at read time, by inverting the values read from those positions. RDIS is characterized by a very low probability of failure that increases slowly with the relative increase in the number of faults. Moreover, RDIS tolerates many more faults than the best existing scheme—by up to 95 percent on average at the same overhead level.

The current trend to move from homogeneous to heterogeneous multicore systems provides compelling opportunities for achieving performance and energy efficiency goals. Running multiple threads in multicore systems poses challenges on meeting limited shared resources, such as memory bandwidth. We propose an optimization approach that includes an Integer Linear Programming (ILP) optimization model and a scheme to dynamically determine thread-to-core assignment. We present simulation analysis that shows energy savings and performance gains for a variety of workloads compared to state-of-the-art schemes. We implemented and evaluated a prototype of our thread assignment approach at user level, leveraging Linux scheduling and performance-monitoring capabilities.

Simulation is a critical tool for evaluating processor and program performance and behavior in newly proposed computer architectures. When modeling target machines with hundreds or thousands of cores, parallel simulation approaches are an increasingly popular method to reduce the long simulation times inherent in single-threaded simulation. Unfortunately, synchronization forces a tradeoffs between performance and fidelity in these parallel simulators. In this work, we study the link between synchronization violations and architectural metric error in the form of CPI error. Further, we introduce weighted-tuple synchronization, a new distributed synchronization scheme that improves error-delay for parallel simulation. Each core periodically selects a group of synchronization targets, forming a synchronization tuple. The lead core then waits for the other cores to catch up. Selection occurs randomly, but is weighted to favor cores which cause more synchronization violations. With weighted-tuple synchronization and a synchronization interval of 100 cycles, average error delay improves over barrier synchronization by 41% and over random-pair synchronization by 35%.

As HPC systems continue to grow to meet the requirements of tomorrow's exascale-class systems, two of the biggest challenges are power consumption and system resilience. On current systems, the dominant resilience technique is checkpoint/restart. It is believed, however, that this technique alone will not scale to the level necessary to support future systems. Therefore, alternative methods have been suggested to augment checkpoint/restart -- for example process replication. In this paper we address both resilience and power together, this is in contrast to much of the competed work which does so independently. Using an analytical model that accounts for both power consumption and failures, we study the performance of checkpoint and replication-based techniques on current and future systems and use power measurements from current systems to validate our findings. Lastly, in an attempt to optimize power consumption for replication, we introduce a new protocol termed shadow replication which not only reduces energy consumption but also produces faster response times than checkpoint/restart and traditional replication when operating under system power constraints.

State-of-the-art chip multiprocessor (CMP) proposals emphasize general optimizations designed to deliver computing power for many types of applications. Potentially, significant performance improvements that leverage application-specific characteristics such as data access behavior are missed by this approach. In this paper, we demonstrate how scalable and high-performance parallel systems can be built by classifying data accesses into different categories and treating them differently. We develop a novel compiler-based approach to speculatively detect a data classification termed practically private, which we demonstrate is ubiquitous in a wide range of parallel applications. Leveraging this classification provides efficient solutions to mitigate data access latency and coherence overhead in today’s many-core architectures. While the proposed data classification scheme can be applied to many micro-architectural constructs including the TLB, coherence directory, and interconnect, we demonstrate its potential through an efficient cache coherence design. Specifically, we show that the compiler-assisted mechanism reduces an average of 46% coherence traffic and achieves up to 12%, 8%, and 5% performance improvement over shared, private, and state-of-the-art NUCA-based caching, respectively, depending on scenarios.

DRAM stores information in electric charge. Because DRAM cells lose stored charge over time due to leakage, they have to be “refreshed” in a periodic manner to retain the stored information. This refresh activity is a source of increased energy consumption as the DRAM density grows. It also incurs nontrivial performance loss due to the unavailability of memory arrays during refresh. This paper first presents a comprehensive measurement-based characterization study of the cell-level data retention behavior of modern low-power DRAM chips. About 99.7% of the cells could retain the stored information for longer than 1 s at a high temperature. This average cell retention behavior strongly indicates that we can deeply reduce the energy and performance penalty of DRAM refreshing with proper system support. The second part of this paper, accordingly, develops two practical techniques to reduce the frequency of DRAM refresh operations by excluding a few leaky memory cells from use and by skipping refreshing of unused DRAM regions. We have implemented the proposed techniques completely in the Linux OS for experimentation, and measured performance improvement of up to 17.2% with the refresh operation reduction of 93.8% on smartphone like low-power platforms.

Phase-Change Memory (PCM) has emerged as a promising low-power candidate to replace DRAM in main memory. Hybrid memory architecture comprised of a large PCM and a small DRAM is a popular solution to mitigate undesirable characteristics of PCM writes. Because PCM writes are much slower than reads, writebacks from the last-level cache consume a large portion of memory bandwidth, and thus, impact performance. Effectively utilizing shared resources, such as the last-level cache and the memory bandwidth, is crucial to achieving high performance for multi-core systems. Although existing memory bandwidth allocation schemes improve system performance, no current approach uses writeback information to partition bandwidth for hybrid memory. We use a writeback-aware analytic model to derive the allocation strategy for bandwidth partitioning of phase-change memory. From the derivation of the model, Writeback-aware Bandwidth Partitioning (WBP) is proposed as a new runtime mechanism to partition PCM service cycles among applications. WBP uses a partitioning weight to indicate the importance of writebacks (in addition to LLC misses) to bandwidth allocation. A companion Dynamic Weight Adjustment (DWA) scheme dynamically selects the partitioning weight to maximize system performance. Simulation results show that WBP and DWA improve performance by 24.9% (weighted speedup) over bandwidth partitioning schemes that do not take writebacks into consideration in a 8-core system.

This work explores a method for efficient pre-allocation of circuits in network-on-chip (NoC) to reduce communication latency and improve performance. Circuit pre-allocation eliminates the time cost of circuit establishment by using request messages to reserve the circuits for their anticipated reply messages. Requests reserve circuits in a priority order rather than for a particular time slot, avoiding delays or blocking even if the newly requested circuits conflict with previously reserved ones. Benchmark simulations show speedup in execution time of up to 16%, with an average of 8% for communication sensitive benchmarks, over a leading proposal in pre-configuring circuits.

Write bandwidth is an inherent performance bottleneck for Phase Change Memory (PCM) for two reasons. First, PCM cells have long programming time, and second, only a limited number of PCM cells can be programmed concurrently due to programming current and write circuit constraints,

Phase-change memory (PCM) has emerged as a candidate that overcomes the physical limitations faced by DRAM and NAND flash memory. While PCM has desirable properties in terms of scalability and energy, it suffers from limited endurance. Repeated writes cause PCM cells to wear out and get permanently stuck at either 0 or 1. Recovering from stuck-at faults through a proactive error correction scheme is essential for the widespread adoption of PCM. In this paper, we propose data inversion as a practical technique to increase the number of faults that an error correction code can cover. Since stuck-at cells can still be read, errors are manifested only when a worn-out cell is programmed with a bit value different than the value it is stuck at. After a write operation fails for a given block of data, data inversion attempts another write operation with all original data bits inverted. Inverting the data is likely to bring the number of errors within the nominal capability of the deployed error correction code. Requiring only one additional auxiliary bit, data inversion can double the capability of an error correction code and extends the lifetime by up to 34.5%.

Limited PCM write bandwidth is a critical obstacle to achieve good performance from hybrid DRAM/PCM memory systems. The write bandwidth is severely restricted in PCM devices, which harms application performance. Indeed, as we show, it is more important to reduce PCM write traffic than to reduce PCM read latency for application performance. To reduce the number of PCM writes, we propose a DRAM cache organization that employs compression. A new delta compression technique for modified data is used to achieve a large compression ratio. Our approach can selectively and predictively apply compression to improve its efficiency and performance. Our approach is designed to facilitate adoption in existing main memory compression frameworks. We describe an instance of how to incorporate delta compression in IBM's MXT memory compression architecture when used for DRAM cache in a hybrid main memory. For fourteen representative memory-intensive workloads, on average, our delta compression technique reduces the number of PCM writes by 54.3%, and improves IPC performance by 24.4%.

Traversing the page table during virtual to physical address translation causes pipeline stalls when misses occur in the translation-lookaside buffer (TLB). State-of-the-art translation proposals typically optimize a single aspect of translation performance (e.g., translation sharing, context switch performance, etc.) with potential trade-offs of additional hardware complexity, increased translation latency, or reduced scalability. In this article, we propose the partial sharing TLB (PS-TLB), a fast and scalable solution that reduces off-chip translation misses without sacrificing the timing-critical requirement of on-chip translation. We introduce the partial sharing buffer (PSB) which leverages application page sharing characteristics using minimal additional hardware resources. Compared to the leading TLB proposal that leverages sharing, PS-TLB provides a more than 45% improvement in translation latency with a 9% application speedup while using fewer storage resources. In addition, the page classification and PS-TLB architecture provide further optimizations including an over 30% reduction of interprocessor interrupts for coherence, and reduced context switch misses with fewer resources compared with existing methods.

Segregating networks-on-chips (NoCs) into data and control planes yields several opportunities for improving power and performance in chip-multiprocessor systems (CMPs). This article describes a hybrid packet/circuit switched multiplane network optimized to reduce latency in order to improve system performance and/or reduce system energy. Unlike traditional circuit preallocation techniques which require timestamps to reserve circuit resources, this article proposes an order-based preallocation scheme . By enforcing the order in which resources are scheduled and utilized rather than a fixed time, the NoC can take advantage of messages that arrive early while naturally tolerating message delays due to contention. Ordered circuit establishment is presented using two techniques. First, Déjà Vu switching preestablishes circuits for data messages once a cache hit is detected and prior to the requested data becoming available. Second, using Red Carpet Routing , circuits are proactively reserved for a return data message as a request message traverses the NoC. The reduced communication latency over configured circuits enable system performance improvement or saving NoC energy by reducing voltage and frequency without sacrificing performance. In simulations of 16 and 64 core CMPs, Déjà Vu switching enabled average NoC energy savings of 43% and 53% respectively. On the other hand, simulations of communication sensitive benchmarks using Red Carpet Routing show speedup in execution time of up to 16%, with an average of 10% over a purely packet switched NoC and an average of 8% over preconfiguring circuits using Déjà Vu switching .

State-of-the-art chip multiprocessor (CMP) proposals emphasize optimization to deliver computing power across many types of applications. Potentially significant performance improvements that leverage application specific characteristics such as data access behavior are missed by this approach. In this paper, we demonstrate that using fairly simple and inexpensive static analysis, data can be classified into private and shared. In addition, we develop a novel compiler-based approach to speculatively detect a third classification: practically private. We demonstrate that practically private data is ubiquitous in parallel applications and leveraging this classification provides opportunities to benefit performance. While this proposed data classification scheme can be applied to many micro-architectural constructs including the TLB, coherence directory and interconnect, we demonstrate its potential through an efficient cache coherence design. Specifically, we show that the compiler-assisted mechanism reduces an average of 46% coherence traffic and achieves up to 13%,9%, and 5% performance improvement over shared, private, and state-of-the-art NUCA-based caching, respectively depending on scenarios.

With their potential for high scalability and density, resistive memories are foreseen as a promising technology that overcomes the physical limitations confronted by charge-based DRAM and flash memory. Yet, a main burden towards the successful adoption and commercialization of resistive memories is their low cell reliability caused by process variation and limited write endurance. Typically, faulty and worn-out cells are permanently stuck at either `0' or `1'. To overcome the challenge, a robust error correction scheme that can recover from many hard faults is required. In this paper, we propose and evaluate RDIS, a novel scheme to efficiently tolerate memory stuck-at faults. RDIS allows for the correct retrieval of data by recursively determining and efficiently keeping track of the positions of the bits that are stuck at a value different from the ones that are written, and then, at read time, by inverting the values read from those positions. RDIS is characterized by a very low probability of failure that increases slowly with the relative increase in the number of faults. Moreover, RDIS tolerates many more faults than the best existing scheme-by up to 95% on average at the same overhead level.

The emerging on-chip optical interconnection has become a promising candidate for future network design because of its advantages in high bandwidth density, low propagation delay and dynamic power consumption. However, a key challenge of on-chip optics is the high static power consumption which dominates the total network power. Hence, it is imperative to design an energy-efficient optical network architecture with high throughput while consuming low static power. In conventional optical crossbars, static channel allocation results in low channel utilization and network throughput, while full channel sharing requires a significant number of microrings, which incurs high static power.

We investigate the routing of communications in chip multiprocessors (CMPs). The goal is to find a valid routing in the sense that the amount of data routed between two neighboring cores does not exceed the maximum link bandwidth while the power dissipated by communications is minimized. Our position is at the system level: we assume that several applications, described as task graphs, are executed on a CMP, and each task is already mapped to a core. Therefore, we consider a set of communications that have to be routed between the cores of the CMP. We consider a classical model, where the power consumed by a communication link is the sum of a static part and a dynamic part, with the dynamic part depending on the frequency of the link. This frequency is scalable and it is proportional to the throughput of the link. The most natural and widely used algorithm to handle all these communications is XY routing: for each communication, data is first forwarded horizontally, and then vertically, from source to destination. However, if it is allowed to use all Manhattan paths between the source and the destination, the consumed power can be reduced dramatically. Moreover, some solutions may be found while none existed with the XY routing. In this paper, we compare XY routing and Manhattan routing, both from a theoretical and from a practical point of view. We consider two variants of Manhattan routing: in single-path routing, only one path can be used for each communication, while multi-paths routing allows to split a communication between different routes. We establish the NP-completeness of the problem of finding a Manhattan routing that minimizes the dissipated power, we exhibit the minimum upper bound of the ratio power consumed by an XY routing over power consumed by a Manhattan routing, and finally we perform simulations to assess the performance of Manhattan routing heuristics that we designed.

Nanophontonic networks, a potential candidate for future networks on-chip, have been challenged for their reliability due to several device-level limitations. One of the main issues is that fabrication errors (a.k.a. process variations) can cause devices to malfunction, rendering communication unreliable. For example, microring resonator, a preferred optical modulator device, may not resonate at the designated wavelength under process variations (PV), leading to communication errors and bandwidth loss. This paper proposes a series of solutions to the wavelength drifting problem of microrings and subsequent bandwidth loss problem of an optical network, due to PV. The objective is to maximize network bandwidth through proper arrangement among microrings and wavelengths with minimum power requirement. Our arrangement, called “MinTrim”, solves this problem using simple integer linear programming, adding supplementary microrings and allowing flexible assignment of wavelengths to network nodes as long as the resulting network presents maximal bandwidth. Each step is shown to improve bandwidth provisioning with lower power requirement. Evaluations on a sample network show that a baseline network could lose more than 40% bandwidth due to PV. Such loss can be recovered by MinTrim to produce a network with 98.4% working bandwidth. In addition, the power required in arranging microrings is 39% lower than the baseline. Therefore, MinTrim provides an efficient PV-tolerant solution to improving the reliability of on-chip phontonics.

In chip-multiprocessors (CMPs) the network-on-chip (NoC) carries cache coherence and data messages. These messages may be classified into critical and non-critical messages. Hence, instead of having one interconnect plane to serve all traffic, power can be saved if the NoC is split into two planes: a fast plane dedicated to the critical messages and a slower, more power-efficient plane dedicated only to the non-critical messages. This split, however, can be beneficial to save energy only if system performance is not significantly degraded by the slower plane. In this work we first motivate the need for a timely delivery of the "non-critical" messages. Second, we propose Déjà Vu switching, a simple algorithm that enables reducing the voltage and frequency of one plane while reducing communication latency through circuit switching and support of advance, possibly conflicting, circuit reservations. Finally, we study the constraints that govern how slow the power-efficient plane can operate without negatively impacting system performance. We evaluate our design through simulations of 16 and 64 core CMPs. The results show that we can achieve an average NoC energy savings of 43% and 53%, respectively.

The current trend to move from homogeneous to heterogeneous multi-core systems promises further performance and energy-efficiency benefits. A typical future heterogeneous multi-core system includes two distinct types of cores, such as high performance sophisticated ("large'') cores and simple low-power ("small'') cores. In those heterogeneous platforms, execution phases of application threads that are CPU-intensive can take best advantage of large cores, whereas I/O or memory intensive execution phases are best suited and assigned to small cores. However, it is crucial that the assignment of threads to cores satisfy both the computational and memory bandwidth constraints of the threads. We propose an optimization approach to determine and apply the most energy efficient assignment of threads with soft real-time performance and memory bandwidth constraints in a multi-core system. Our approach includes an ILP (Integer Linear Programming) optimization model and a scheme to dynamically change thread-to-core assignment, since thread execution phases may change over time. In comparison to state-of-art dynamic thread assignment schemes, we show energy savings and performance gains for a variety of workloads, while respecting thread performance and memory bandwidth requirements.

Phase-Change Memory (PCM) has emerged as a promising low-power main memory candidate to replace DRAM. The main problems of PCM are that writes are much slower and more power hungry than reads, write bandwidth is much lower than read bandwidth, and limited write endurance. Adding an extra layer of cache, which is logically the last-level cache (LLC), can mitigate the drawbacks of PCM. However, writebacks from the LLC might (a) overwhelm the limited PCM write bandwidth and stall the application, (b) shorten lifetime, and (c) increase energy consumption. Cache partitioning and replacement schemes are important to achieve high throughput for multi-core systems. However, we noted that no existing partitioning and replacement policy takes into account the writeback information. This paper proposes two writeback-aware schemes to manage the LLC for PCM main memory systems. Writeback-aware Cache Partitioning (WCP) is a runtime mechanism that partitions a shared LLC among multiple applications. Unlike past partitioning schemes, our scheme considers the reduction in cache misses as well as writebacks. Write Queue Balancing (WQB) replacement policy manages the cache partition of each application intelligently so that the writebacks are distributed evenly among PCM write queues. In this way, applications rarely stall due to unbalanced PCM write traffic among write queues. Our evaluation shows that WCP and WQB result in, on average, 21% improvement in throughput, 49% reduction in PCM writes, and 14% reduction in energy over a state-of-the-art cache partitioning scheme.

The 12 papers in this special issue focus on energy efficient computing applications and technologies.

Reducing data access latency is vital to achieving performance improvements in computing. For chip multiprocessors (CMPs), data access latency depends on the organization of the memory hierarchy, the on-chip interconnect, and the running workload. Several network-on-chip (NoC) designs exploit communication locality to reduce communication latency by configuring special fast paths or circuits on which communication is faster than the rest of the NoC. However, communication patterns are directly affected by the cache organization and many cache organizations are designed in isolation of the underlying NoC or assume a simple NoC design, thus possibly missing optimization opportunities. In this work, we take a codesign approach of the NoC and cache organization. First, we propose a hybrid circuit/packet-switched NoC that exploits communication locality through periodic configuration of the most beneficial circuits. Second, we design a Unique Private (UP) caching scheme targeting the class of interconnects which exploit communication locality to improve communication latency. The Unique Private cache stores the data that are mostly accessed by each processor core in the core's locally accessible cache bank, while leveraging dedicated high-speed circuits in the interconnect to provide remote cores with fast access to shared data. Simulations of a suite of scientific and commercial workloads show that our proposed design achieves a speedup of 15.2 and 14 percent on a 16-core and a 64-core CMP, respectively, over the state-of-the-art NoC-Cache codesigned system that also exploits communication locality in multithreaded applications.

Data access latency, a limiting factor in the performance of chip multiprocessors, grows significantly with the number of cores in nonuniform cache architectures with distributed cache banks. To mitigate this effect, we use a compiler-based approach to leverage data access locality, choose an optimized data placement and efficiently configure the on-chip network. The proposed experimental compiler framework employs novel compilation techniques to discover and represent multithreaded memory access patterns (MMAPs). At runtime, symbolic MMAPs are resolved and used by a partitioning algorithm to choose a partition of allocated memory blocks among the forked threads in the analyzed application. This partition is used to enforce data ownership by associating the data with the core that executes the thread owning the data. Based on the partition, the communication pattern of the application can be extracted. We demonstrate how this information can be used in an experimental architecture to accelerate applications. In particular, our compiler assisted data partitioning approach shows a 20 percent speedup over shared caching and 5 percent speedup over the closest runtime approximation, first touch. By leveraging the communication pattern we can achieve a comparable performance to a system that uses a complex centralized network configuration system at runtime. Thus, our final system saves significant runtime complexity and achieves an 5.1 percent additional speedup through the addition of the reconfigurable network.

Non-volatile memories, such as Flash and Phase-Change Memory, are replacing other memory and storage technologies. Although these new technologies have desirable energy and scalability properties, they are prone to wear-out due to excessive write operations. Because wear-out is an important phenomenon, a number of endurance management schemes have been proposed. There is a trade-off between what techniques to use, depending on the range of bit cell lifetime within a device. This range in cell durability arises from effects due to process variation. In this paper, we describe modeling techniques to analyze trade-offs for endurance management based on the anticipated distribution of cell lifetime. This analysis considers two general endurance strategies (physical capacity degradation and physical sparing) under four distributions of cell lifetime (constant, linear, normal, and bimodal). The modeling techniques can be used to determine how much redundancy is needed when a sparing endurance strategy is adopted. With the correct choice of technique, the device lifetime can be doubled.

In chip multiprocessors (CMPs), data access latency depends on the memory hierarchy organization, the on-chip interconnect (NoC), and the running workload. Reducing data access latency is vital to achieving performance improvements and scalability of threaded applications. Multithreaded applications generally exhibit sharing of data among the program threads, which generates coherence and data traffic on the NoC.

This paper describes Cache Equalizer (CE), a novel distributed cache management scheme for large-scale chip multiprocessors (CMPs). Our work is motivated by large asymmetry in cache sets' usages. CE decouples the physical locations of cache blocks from their addresses for the sake of reducing misses caused by destructive interferences. Temporal pressure at the on-chip last-level cache is continuously collected at a group (comprised of cache sets) granularity, and periodically recorded at the memory controller to guide the placement process. An incoming block is consequently placed at a cache group that exhibits the minimum pressure. Simulation results using a full-system simulator demonstrate that CE achieves an average L2 miss rate reduction of 13.6% over a shared NUCA scheme and by as much as 46.7% for the benchmark programs we examined. Furthermore, evaluations showed that CE outperforms related cache designs.

This paper studies the problem of mapping streaming applications that can be modeled by a series-parallel graph, onto a 2-dimensional tiled CMP architecture. The objective of the mapping is to minimize the energy consumption, using dynamic voltage scaling techniques, while maintaining a given level of performance, reflected by the rate of processing the data streams. This mapping problem turns out to be NP-hard, but we identify simpler instances, whose optimal solution can be computed by a dynamic programming algorithm in polynomial time. Several heuristics are proposed to tackle the general problem, building upon the theoretical results. Finally, we assess the performance of the heuristics through a set of comprehensive simulations.

Phase Change Memory (PCM) is an emerging technology that has been recently considered as a cost-effective and energy-efficient alternative to traditional DRAM main memory. Due to the high energy consumption of writes and limited number of write cycles, reducing the number of writes to PCM can result in considerable energy savings and endurance improvement. In this paper, we introduce the concept of useless write-backs, which occur when a dirty cache line that belongs to a dead memory region is evicted from the cache (a dead region is a memory location that is not used again by a program). Since the evicted data is not used again, the write-back can be safely avoided to improve endurance and energy consumption. This paper presents a limit study on the improvement that passing information to the memory system about useless writebacks has on the endurance and energy consumption of systems based on PCM main memory. We developed algorithms to measure the number of useless write-backs to PCM for three different types of memory regions and we present an energy model to determine the maximum energy savings that could potentially be achieved through such a scheme. Our results show that avoiding useless write-backs can save up to 19.8% of energy and improve endurance by up to 26.2%.

Software simulation is the primary tool used for evaluation of processor design. Simulation offers better accuracy than analytical models and is an important evaluation step before actually fabricating a chip. Unfortunately, simulator speeds are slow -- a conventional cycle-accurate simulator will be unable to keep up with increasing core counts in modern processor design. Parallel simulation is one method for improving simulation speeds. Two major areas of parallel simulation research are multithreaded simulators and FPGAs as simulation accelerators. Multithreaded simulators can only extract coarse-grained parallelism and must sacrifice accuracy in order to scale well. FPGA-based simulators can extract fine-grained parallelism, but are expensive and difficult to program. We propose using GPUs for architectural simulation, which can take advantage of a high degree of fine-grained parallelism. In addition, they are inexpensive and easier to program compared to FPGAs. To demonstrate our ideas, we implement a trace-driven many-cache simulator using NVIDIA's CUDA toolkit. GPU-accelerated cache simulation displays remarkable scaling with number of simulated caches when compared to serial CPU-only simulation.

Many resources are shared among the cores of chip-multiprocessors (CMPs), in particular on-chip caches and memory systems. Efficient intra-chip communication is necessary for efficient resource sharing and the performance of such systems, especially in future CMPs with hundreds or thousands of cores. Current Free-space optical networks-on-chip (NoCs) provide the potential to avoid the reduced wire performance and degraded signal integrity facing electronic networks. However, current proposals utilize fixed direction lasers and mirrors to realize one-hop all-to-all connectivity, which results in difficulties scaling to larger numbers of processors. In this paper we present two-hop optical strategies that provide better performance over the one-hop strategy while improving on both the required resources and scalability for future large scale CMPs.

Multi-core processors are effective for reducing energy consumption in computer systems, since modern multi- core chips allow for power management of individual cores. However, multiple cores impose higher demand on the memory subsystem, which is extremely power hungry. In addition to the small steps towards managing power in DRAMs, Phase-Change Memory (PCM) has emerged as a low-power alternative that is especially helpful for energy-aware embedded real-time systems. However, there are three drawbacks to PCM: its high latency, high energy consumption when writing, and low endurance. In real-time systems, the impact of PCM's high access latency is of special interest, as it has a negative effect on the number of deadlines that are met by the system. In this paper, we examine the memory subsystem and add a real-time scheduler for prioritizing requests at the bottleneck resource, the PCM controller. Adding support for external priorities, we use rate monotonic (RM) and earliest deadline first (EDF) prioritization at the PCM and show that it does reduce the number of deadline misses, but not sufficiently. We examine two additional schemes for prioritizing PCM requests (critical read boosting and read over write). We show that the scheduler of the PCM controller has a significant influence on the percentage of missed deadlines: critical read boosting and read over write can reduce the percentage of missed deadlines by 80% in the best case with negligible energy overhead.

The performance of chip multiprocessors (CMPs) is dependent on the data access latency, which is highly dependent on the design of the on-chip interconnect (NoC) and the organization of the memory caches. However, prior research attempts to optimize the performance of the NoC and cache mostly in isolation of each other. In this work we present a NoC-aware cache design that focuses on communication locality; a property both the cache and NoC affect and can exploit.

This poster describes an intra-tile cache set balancing strategy that exploits the demand imbalance across sets within the same L2 cache bank. This strategy retains some fraction of the working set at underutilized sets so as to satisfy far-flung reuses. It adapts to phase changes in programs and promotes a very flexible sharing among cache sets referred to as many-from-many sharing. Simulation results using a full system simulator demonstrate the effectiveness of the proposed scheme and show that it compares favorably with related cache designs on a 16-way tiled CMP platform.

Data access latency, a limiting factor in the performance of chip multiprocessors, grows significantly with the number of cores in non-uniform cache architectures with distributed cache banks. To mitigate this effect, it is necessary to leverage the data access locality and choose an optimum data placement. Achieving this is especially challenging when other constraints such as cache capacity, coherence messages and runtime overhead need to be considered. This paper presents a compiler-based approach used for analyzing data access behavior in multi-threaded applications. The proposed experimental compiler framework employs novel compilation techniques to discover and represent multi-threaded memory access patterns (MMAPs). At run time, symbolic MMAPs are resolved and used by a partitioning algorithm to choose a partition of allocated memory blocks among the forked threads in the analyzed application. This partition is used to enforce data ownership by associating the data with the core that executes the thread owning the data. We demonstrate how this information can be used in an experimental architecture to accelerate applications. In particular, our compiler assisted approach shows a 20% speedup over shared caching and 5% speedup over the closest runtime approximation, "first touch".

Simulation of new multi- and many-core systems is becoming an increasingly large bottleneck in the design process. This paper presents the ACME design automation tool flow that facilitates the hardware emulation of newly proposed large multi-core interconnection networks on FPGAs to mitigate the slowdowns of single threaded event driven simulation. The tool is aimed at computer and network architects who have knowledge of digital design but may not be comfortable with hardware description languages and synthesis flows. ACME uses a graphical entry that allows a mix of hardware components with software algorithms written in C, each with a user defined latency and throughput in terms of system cycles. ACME automatically generates a cycle accurate hardware emulator as a Xilinx Platform Studio project, which integrates synthesized hardware blocks with embedded soft-core processors that execute the C code. Our results demonstrate that for 16-core and 64-core cycle accurate packet switching networks, the FPGA-based emulation is faster than Simics-based software simulation by 2.5x and 14.6x, respectively.

The introduction of Phase-Change Memory (PCM) as a main memory technology has great potential to achieve a large energy reduction. PCM has desirable energy and scalability properties, but its use for main memory also poses challenges such as limited write endurance with at most 107writes per bit cell before failure. This paper describes techniques to enhance the lifetime of PCM when used for main memory. Our techniques are (a) writeback minimization with new cache replacement policies, (b) avoidance of unnecessary writes, which write only the bit cells that are actually changed, and (c) endurance management with a novel PCM-aware swap algorithm for wear-leveling. A failure detection algorithm is also incorporated to improve the reliability of PCM. With these approaches, the lifetime of a PCM main memory is increased from just a few days to over 8 years.

Dynamic RAM (DRAM) has been the best technology for main memory for over thirty years. In embedded space applications, radiation hardened DRAM is needed because gamma rays cause transient errors; such rad-hard memories are extremely expensive and power hungry, leading to lower life (or increased battery weight) for satellite and other devices operating in space. Despite these problems, DRAM has been the technology of choice because it has better performance and it scales well. New, more energy efficient, non-volatile, scalable, radiation resistant memory technologies are now available, namely phase-change memory (PCM), making the DRAM choice much less compelling. However, current approaches require changes to PCM device internal circuitry, the operating system and/or the CPU cache-memory organization/interface. This paper presents a new, practical, detailed architecture, called PMMA, to effectively use PCM for main memory in next-generation embedded space systems. We designed PMMA avoiding changes to commodity PCM devices, the operating system, and the existing CPU cache-memory interface, enabling plug-in replacement of a conventional DRAM main memory by one constructed with PMMA. Our architecture incorporates novel mechanisms to address PCM’s limitations including expensive write operations, asymmetric read/write latency, and limited endurance. In our evaluation we show that PMMA achieves a 60% improvement in energy-delay over a conventional DRAM main memory.

This paper derives simple, yet fundamental formulas to describe the interplay between parallelism of an application, program performance, and energy consumption. Given the ratio of serial and parallel portions in an application and the number of processors, we derive optimal frequencies allocated to the serial and parallel regions in an application to either minimize the total energy consumption or minimize the energy-delay product. The impact of static power is revealed by considering the ratio between static and dynamic power and quantifying the advantages of adding to the architecture capability to turn off individual processors and save static energy. We further determine the conditions under which one can obtain both energy and speed improvement, as well as the amount of improvement. While the formulas we obtain use simplifying assumptions, they provide valuable theoretical insights into energy-aware processor resource management. Our results form a basis for several interesting research directions in the area of energy-aware multicore processor architectures.

As the Internet grows, both the number of rules in packet filtering databases and the number of prefixes in IP lookup tables inside the router are growing. The packet processing engine is a critical part of the Internet router as it is used to perform packet forwarding (PF) and packet classification (PC). In both applications, processing has to be at wire speed. It is common to use hash-based schemes in packet processing engines; however, the downside of classic hashing techniques such as overflow and worst case memory access time, has to be dealt with. Implementing hash tables using set associative memory has the property that each bucket of a hash table can be searched in one memory cycle outperforming the conventional Ternary CAMs in terms of power and scalability.

The goal of Wireless Sensor Networks is to extract useful global information from individual sensor readings, which are typically collected and aggregated over a spanning tree. However, the spanning tree structure is not robust against communication errors; a low-quality (i.e., high-error-rate) wireless link close to the tree root may result in a high rate of global information loss. Therefore, many schemes have been proposed to achieve fault-tolerant aggregation. Intuitively, using timely link-quality information, which is gathered by continuous monitoring and error-rate measurement of network links, improves the performance of fault-tolerant aggregation schemes. In this paper, we show that this intuition is not always true. In particular, we show that using link-quality information in an intuitive but wrong way results in degraded performance in some schemes, and therefore, care should be taken in using link-quality information. We also show that some schemes make better usage of link-quality information than others, and some schemes are more robust to errors in link-quality estimation than others. We support our findings by an extensive simulation study, and we focus on the (more general) class of fault-tolerant duplicate-sensitive aggregation schemes.

This paper proposes DCC (Dynamic Cache Clustering), a novel distributed cache management scheme for large-scale chip multiprocessors. Using DCC, a per-core cache cluster is comprised of a number of L2 cache banks and cache clusters are constructed, expanded, and contracted dynamically to match each core's cache demand. The basic trade-offs of varying the on-chip cache clusters are average L2 access latency and L2 miss rate. DCC uniquely and efficiently optimizes both metrics and continuously tracks a near-optimal cache organization from many possible configurations. Simulation results using a full-system simulator demonstrate that DCC outperforms alternative L2 cache designs.

In this paper we explore compiler techniques for achieving efficient communications on circuit switching interconnection networks. We propose a compilation framework for identifying communication patterns and compiling these patterns as network configuration directives. This has the potential of providing significant performance benefits when connections can be established in the network prior to the actual communications. The framework includes a flexible and powerful communication pattern representation scheme that captures the property of communication patterns and allows manipulation of these patterns. In this way, communication phases can be identified within the application. Additionally, we extend the classification of static and dynamic communications to include persistent communications. Persistent communications are a subclass of dynamic communications that remain unchanged for large segments of the application execution. An experimental compiler has been developed to implement the framework. This compiler is capable of detecting both static and persistent communications within an application. We show that for the NAS Parallel Benchmarks, 100% of the point-to-point communications can be classified as either static or persistent and 100% of the collectives are either static or persistent with the exception of IS. Simulation-based performance analysis demonstrates the benefit of using our compiler techniques for achieving efficient communications in multiprocessor systems.

Denial-of-service (DoS) attacks remain a challenging problem in the Internet. By making resources unavailable to intended legitimate clients, DoS attacks have resulted in significant loss of time and money for many organizations, thus, many DoS defense mechanisms have been proposed. In this paper we propose live baiting, a novel approach for detecting the identities of DoS attackers. Live baiting leverages group-testing theory, which aims at discovering defective members in a population using the minimum number of dasiadasiatestspsilapsila. This leverage allows live baiting to detect attackers using low state overhead without requiring models of legitimate requests nor anomalous behavior. The amount of state needed by live baiting is in the order of number of attackers not number of clients. This saving allows live baiting to scale to large services with millions of clients. We analyzed the coverage, effectiveness (detection time, false positive and false negative probabilities), and efficiency (memory, message overhead, and computational complexity) of our approach. We validated our analysis using NS-2 simulations modeled after real Web traces.

Enabling circuit switching in multiprocessor systems has the potential to achieve more efficient communication with lower cost compared to packet/wormhole switching. However, in order to accomplish this efficiently, assistance from the compiler is required to reveal the communication pattern in the parallel application. In this paper we present symbolic expression analysis techniques in a MPI parallel compiler. Symbolic expression analysis allows the identification and representation of the communication pattern and also assists in the determination of communication phases in MPI parallel applications at compile-time. We demonstrate that using the compiler analysis based on symbolic expression analysis to determine the communication pattern and phases provides an average of 2.6 times improvement in message delay over a threshold-based runtime system for our benchmarks with a maximum improvement of 9.7 times.

In wireless sensor networks (WSN) node failures are typically detected using a heartbeat application, where a neighbor detects a failed node when it misses successive short messages (ldquoheartbeatsrdquo) that should have been sent by the failed node. However, wireless links are usually lossy, hence, to distinguish node failures from intermittent link failures, the threshold on the number of missed heartbeats is usually set to a large number, incurring in a long delay for declaring a node dead. In this paper we present ldquoGroupBeatrdquo an accurate node failure detection system for WSN and propose the ldquoCommunication By Signalingrdquo scheme as an energy-efficient low-overhead implementation of GroupBeat.

Multi-radio (multi-interface, multi-channel) 802.11 and sensor networks have been proposed to increase network capacity and to reduce energy consumption, to name only a few of their applications. They are vulnerable, however, to jamming attacks, in which attackers block communication by radio int

Jamming is a serious security problem in wireless networks. Recently, software-based channel hopping has received attention as a jamming countermeasure. In particular, proactive, or periodic, channel hopping has been studied more extensively than reactive hopping. In this paper, we address the question of which of the two defense strategies, namely proactive and reactive channel-hopping, provides better jamming resiliency than the other? in the context of single-and multi-radio wireless devices. In the single-radio context, we develop theoretical models to analyze the blocking probability for combinations of defense and attack strategies. In the multi-radio setting, we formulate the jamming problem as a max-min game and show through simulation that the game outcome depends on the payoff function. Our results show that reactive defense provides better jamming tolerance than proactive when considering communication availability. However, both reactive and proactive defenses have almost the same performance when energy efficiency is considered as a performance metric.

This paper deals with energy-aware real-time system scheduling using dynamic voltage scaling (DVS) for energy-constrained embedded systems that execute variable and unpredictable workloads. The goal is to design DVS schemes to minimize the expected energy consumption of the whole system while meeting the deadlines of the tasks. Researchers have attempted to take advantage of stochastic information about workloads to achieve better energy savings, and accordingly, various stochastic DVS schemes have been proposed. However, the existing stochastic DVS schemes are based on much simplified power models that assume unrestricted continuous frequency, well-defined power/frequency relation, and no speed change overhead. When these schemes are used in practice, they need to be patched in order to comply with realistic power models. Experiments show that some of such DVS schemes perform even worse than certain non-stochastic DVS schemes. Furthermore, even for stochastic schemes that were shown experimentally to outperform non-stochastic schemes, it is not clear how well they perform compared to the optimal solution, which is yet to be found. In this work, we provide a unified practical approach for obtaining optimal (or provably close to optimal) stochastic inter-task, intra-task, and hybrid DVS schemes under realistic power models in which the processor only provides a set of discrete speeds, no assumption is made on power/frequency relation, and speed change overhead is considered. We also evaluate the existing DVS schemes by comparing them with our DVS schemes.

We study link scheduling in networks with small router buffers, with the goal of minimizing the guaranteed packet loss rate bound for each ingress-egress traffic aggregate (connection). Given a link scheduling algorithm (a service discipline and a packet drop policy), the guaranteed loss rate for a connection is the loss rate under worst-case routing and bandwidth allocations for competing traffic. Under simplifying assumptions, we show that a local min-max fairness property with respect to apportioning loss events among the connections sharing each link, and a condition on the correlation of scheduling decisions at different links are two necessary and (together) sufficient conditions for optimality in the minimization problem. Based on these conditions, we introduce a randomized link-scheduling algorithm called rolling priority where packet scheduling at each link relies exclusively on local information. We show that RP satisfies both conditions and is therefore optimal.

This paper presents a technique to visualize the communication pattern of a parallel application at different points during its execution. Unlike existing tools that show the communication pattern for the entire application, our tool breaks this communication pattern down into components to allow the more detailed study of application execution. These patterns are not merely snapshots or windows of the execution but rather are tied to specific code structures comprised of loops in the application. Our technique leverages our compiler, which adds instructions into the code to record where communications and code artifacts occur during execution. This information is stored into a trace format, which is read by our visualization tool. The visualization tool can graphically represent the communication pattern and message volume to allow a user to analyze and optimize the execution. As an example, we show how this information can be used to optimize the execution time and reduce the message delay of applications executed on a system enhanced with optical circuit switch interconnections.

This paper proposes a specialized memory structure called CA-RAM (content addressable random access memory) to accelerate search operations present in many important real-world applications. Search operations can occupy a significant portion of total execution time and energy consumption, while posing a difficult performance problem to tackle using traditional memory hierarchy concepts. In essence, CA-RAM is a direct hardware implementation of the well-known hashing technique. Searchable records are stored in CA-RAM at a location determined by a hash function, defined on their search key. After a database has been built, looking up a record in CA-RAM typically involves a single memory access followed by a parallel key matching operation. Compared with a conventional CAM (content addressable memory) solution, CA-RAM capitalizes on dense SRAM and DRAM designs, and achieves comparable search performance while occupying much smaller area and consuming significantly less power. This paper presents detailed design aspects of CA-RAM, to be integrated in future general-purpose and application-specific processors and systems. To further motivate and justify our approach, we present two real examples of using CA-RAM to build a high-performance search accelerator targeting: IP address lookup in core routers and trigram lookup in a large speech recognition system

Embedded systems serve an emerging and diverse set of applications. As a result, more computational and storage capabilities are added to accommodate ever more demanding applications. Unfortunately, adding more resources typically comes on the expense of higher energy costs. New chip design with Multiple Clock Domains (MCD) opens the opportunity for fine-grain power management within theprocessor chip. When used with dynamic voltage scaling (DVS), we can control the voltage and power of each domain independently. A significant power and energy improvement has been shown when using MCD design in comparison to managing a single voltage domain for the whole chip, as in traditional chips with global DVS.

Streaming applications have become increasingly important and widespread, and they will be running on soon- to-be-prevalent chip multiprocessors (CMPs). We address the problem of energy-aware scheduling of streaming applications, which are represented by task graphs, on a CMP using on/off and dynamic voltage scaling (DVS) on a per-processor basis. The goal is to minimize the energy consumption of streaming applications while satisfying two typical quality-of-service (QoS) requirements, namely, throughput and response time. To the best of our knowledge, this paper is the first work to tackle this problem. We make a key observation: the trade-off between static power and dynamic power should play a critical role in both parallel processing and pipelining that are used to reduce energy consumption in the scheduling process. Based on this observation, we propose two scheduling algorithms, Scheduling 1D and Scheduling 2D, for linear and general task graphs, respectively. The proposed algorithms exploit the difference between the two QoS requirements and perform processor allocation, task mapping and task speed scheduling simultaneously. Experimental results show that the proposed algorithms can achieve significant energy savings (e.g., 24% on average for 70 nm technology) over the baseline that only considers the response time requirement.

Fat-tree based system area networks have been widely adopted in high performance computing clusters. In such systems, the routing is often deterministic and the traffic demand is usually uncertain and changing. In this paper, we study routing performance on fat-tree based system area networks with deterministic routing under the assumption that the traffic demand is uncertain. The performance of a routing algorithm under uncertain traffic demands is characterized by the oblivious performance ratio that bounds the relative performance of the routing algorithm and the optimal routing algorithm for any given traffic demand. We consider both single path routing where the traffic between each source-destination pair follows one path, and multi-path routing where multiple paths can be used for the traffic between a source-destination pair. We derive lower bounds of the oblivious performance ratio of any single path routing scheme for fat-tree topologies and develop single path oblivious routing schemes that achieve the optimal oblivious performance ratio for commonly used fat-tree topologies. These oblivious routing schemes provide the best performance guarantees among all single path routing algorithms under uncertain traffic demands. For multi-path routing, we show that it is possible to obtain a scheme that is optimal for any traffic demand (an oblivious performance ratio of 1) on the fat-tree topology. These results quantitatively demonstrate that single path routing cannot guarantee high routing performance while multi-path routing is very effective in balancing network loads on the fat-tree topology.

Main memory has become one of the largest contributors to overall energy consumption and offers many opportunities for power/energy reduction. In this paper, we propose a Power-Aware Cached-DRAM (PA-CDRAM) organization that integrates a moderately sized cache directly into a memory chip. We use this near-memory cache to turn a memory bank off immediately after it is accessed to reduce power consumption.We modify the operation and structure of cached DRAM (CDRAM) with the goal of reducing energy consumption while retaining the performance advantage for which CDRAM was originally proposed. In this paper, we describe our PA-CDRAM organization and show how to incorporate it into Rambus memory. We evaluate the approach using a cycle accurate processor and memory simulator. Our results show that PA-CDRAM achieves up to 84% (28% on average) improvement in the energy-delay product and up to 76% (19% on average) savings in energy when compared to a time-out power management technique.

A new class of low diameter interconnections (LDI) is proposed for high-performance computer systems that are augmented with circuit switching networks. In these systems, the network is configured to match the communication patterns of applications, when these patterns exhibit temporal locality, and to embed a logical topology to route traffic that does not exhibit locality. The new LDI topology is a surprisingly simple directed graph which minimizes the network diameter for a given node degree and number of nodes. It can be easily embedded in circuit switching networks to route random traffic with high bandwidth and low latency

Many real-time systems, such as battery-operated embedded devices, are energy constrained. A common problem for these systems is how to reduce energy consumption in the system as much as possible while still meeting the deadlines; a commonly used power management mechanism by these systems is dynamic voltage scaling (DVS). Usually, the workloads executed by these systems are variable and, more often than not, unpredictable. Because of the unpredictability of the workloads, one cannot guarantee to minimize the energy consumption in the system. However, if the variability of the workloads can be captured by the probability distribution of the computational requirement of each task in the system, it is possible to achieve the goal of minimizing the expected energy consumption in the system. In this paper, we investigate DVS schemes that aim at minimizing expected energy consumption for frame-based hard real-time systems. Our investigation considers various DVS strategies (i.e., intra-task DVS, inter-task DVS, and hybrid DVS) and both an ideal system model (i.e., assuming unrestricted continuous frequency, well-defined power-frequency relation, and no speed change overhead) and a realistic system model (i.e., the processor provides a set of discrete speeds, no assumption is made on power-frequency relation, and speed change overhead is considered). The highlights of the investigation are two practical DVS schemes: Practical PACE (PPACE) for a single task and Practical Inter-Task DVS (PITDVS2) for general frame-based systems. Evaluation results show that our proposed schemes outperform and achieve significant energy savings over existing schemes.

In wireless mobile adhoc networks (MANETs) channel and energy capacities are scarce resources, a lot of energy-efficient routing protocols for MANETs have been previously proposed to take into consideration the nodes’ residual energies when establishing routes between source-destination pairs. In this paper we are not trying to introduce a new routing algorithm to be added to the already proposed stack of energy-efficient protocols, but rather, we identify a problem in cost-based energy-efficient routing for MANETs, we call this problem "Flooding Waves". We show that the "Flooding Waves" is a serious problem in dense networks, to the extent that the excessive energy overhead consumed in these waves can outweigh the gain achieved by energy-efficient path selection. We propose the "Delayed-Forwarding" as a solution for this problem. We provide both a simulation analysis and a simple theoretical framework to validate and support this solution.

By violating MAC-layer protocols, the jamming attack aims at blocking successful communication among wireless nodes. Wireless sensor networks (WSNs) are highly vulnerable to jamming because of reliance on shared wireless medium, constrained per-sensor resources, and high risk of sensor compromise. Moreover, base stations of WSNs are single points of failure and, thus, attractive jamming targets. To tackle base-station jamming, replication of base stations as well as jamming evasion, by relocation to unjammed locations, have been proposed. In this paper, we propose Honeybees, an energy-aware defense framework against base-station jamming attack in WSNs. Honeybees efficiently combines replication and evasion to allow WSNs to continue delivering data for a long time during a jamming attack. We present three defense strategies: reactive, proactive, and hybrid, in the context of multi-hop WSN deployment. Through simulation, we show the interaction of these strategies with different attack tactics as well as the effect of system and attack parameters. We found that our honeybees framework struck an energy-efficient balance between replication and evasion that outperformed both separate mechanisms. Specifically, hybrid honeybees outperformed replication and evasion at low and intermediate number of attackers and gracefully degraded to high attack intensity

The Denial-of-Service (DoS) attack remains a challenging problem in the current Internet. In a DoS defense mechanism, a honeypot acts as a decoy within a pool of servers, whereby any packet received by the honeypot is most likely an attack packet. We have previously proposed the roaming honeypots scheme to enhance this mechanism by camouflaging the honey-pots within the server pool, thereby making their locations highly unpredictable. In roaming honeypots, each server acts as a honeypot for some periods of time, or honeypot epochs, the duration of which is determined by a pseudo-random schedule shared among servers and legitimate clients. In this paper, we propose a honeypot back-propagation scheme to trace back attack sources when attacks occur. Based on this scheme, the reception of a packet by a roaming honeypot triggers the activation of a DAG of honeypot sessions rooted at the honeypot under attack towards attack sources. The formation of this tree is achieved in a hierarchical fashion: first at the autonomous system (AS) level and then at the router level within an AS if needed. The proposed scheme supports incremental deployment and provides deployment incentives for ISPs. Through ns-2 simulations, we show how the proposed scheme enhances the performance of a vanilla Pushback defense by obtaining accurate attack signatures and acting promptly once an attack is detected

In this paper we describe a compiler framework which can identify communication patterns for MPI-based parallel applications. This has the potential of providing significant performance benefits when connections can be established in the network prior to the actual communication operation. Our compiler uses a flexible and powerful communication pattern representation scheme that can capture the property of communication patterns and allows manipulations of these patterns. In this way, communication phases can be detected and logically separated within the application. Additionally, we extend the classification of static and dynamic communication patterns and operations to include persistent communications. Persistent communications appear dynamically, however, they remain unchanged for large segments of the application execution. Our compiler is capable of detecting both static and persistent communication patterns within an application. We show that for the NAS parallel benchmarks, 100% of the point-to-point communications can be classified as either static or persistent and, with the exception of IS, 100% of the collective were either static or persistent. By comparison to application trace data, the predicted LBMHD, CG and MG communication patterns have been verified.

We consider the problem of packet scheduling in a network with small router buffers. The objective is to provide a statistical bound on the worst-case packet loss rate for a traffic aggregate (connection) routed along any network path, given maximum permissible link utilization (load). This problem is argued to be of interest in networks providing statistical loss-rate guarantees to ingress-egress connections with fixed bandwidth demands. We introduce a scheduling algorithm for networks using per packet transmission reservation. Reservations allow loss guarantees at the aggregate level to hold for individual flows within the aggregate. The algorithm employs randomization and traffic regulation at the ingress, and batch local scheduling at the links. It ensures that a large fraction of packets from each connection are consistently subject to small loss probability at every link. These packets are therefore likely to survive long paths. To obtain the desired loss-rate bound, we analyze the performance of the algorithm under global routing and bandwidth allocation scenarios that maximize the loss rate of a connection routed along an arbitrary network path. We compare the bound to that obtained using the scheduling algorithm that combines the FCFS service discipline and the drop-tail policy. We find that the proposed algorithm significantly improves the constraints on link utilization and path length necessary to achieve strong loss-rate guarantees

This paper presents an efficient hardware architecture for scheduling connections on a fat-tree interconnection network for parallel computing systems. Our technique utilizes global routing information to select upward routing paths so that most conflicts can be resolved. Thus, more connections can be successfully scheduled compared with a local scheduler. As a result of applying our technique to two-level, three-level and four-level fat-tree interconnection networks of various sizes in the range of 64 to 4096 nodes, we observe that the improvement of schedulability ratio averages 30% compared with greedy or random local scheduling. Our technique is also scalable and shows increased benefits for large system sizes.

In wireless sensor networks (WSNs), the users' objective is to extract useful global information by collecting individual sensor readings. Conventionally, this is done using in-network aggregation on a spanning tree from sensors to data sink. However, the spanning tree structure is not robust against communication errors; when a packet is lost, so is a complete subtree of values. Multipath routing can mask some of these errors, but on the other hand, may aggregate individual sensor values multiple times. This may produce erroneous results when dealing with duplicate-sensitive aggregates, such as SUM, COUNT, and AVERAGE. In this paper, we present and analyze two new fault tolerant schemes for duplicate-sensitive aggregation in WSNs: (1) cascaded ridesharing and (2) diffused ridesharing. These schemes use the available path redundancy in the WSN to deliver a correct aggregate result to the data sink. Compared to state-of-the-art, our schemes deliver results with lower root mean square (RMS) error and consume much less energy and bandwidth. RideSharing can consume as much as 50% less resources than hash-based schemes, such as SKETCHES and synopsis diffusion, while achieving lower RMS for reasonable link error rates

Managing energy consumption has become vitally important to battery-operated portable and embedded systems. Dynamic voltage scaling (DVS) reduces the processor's dynamic power consumption quadratically at the expense of linearly decreasing the performance. When reducing energy with DVS for real-time systems, one must consider the performance penalty to ensure that deadlines can be met. In this paper, we introduce a novel collaborative approach between the compiler and the operating system (OS) to reduce energy consumption. We use the compiler to annotate an application's source code with path-dependent information called power-management hints (PMHs). This fine-grained information captures the temporal behavior of the application, which varies by executing different paths. During program execution, the OS periodically changes the processor's frequency and voltage based on the temporal information provided by the PMHs. These speed adaptation points are called power-management points (PMPs). We evaluate our scheme using three embedded applications: a video decoder, automatic target recognition, and a sub-band tuner. Our scheme shows an energy reduction of up to 57% over no power-management and up to 32% over a static power-management scheme. We compare our scheme to other schemes that solely utilize PMPs for power-management and show experimentally that our scheme achieves more energy savings. We also analyze the advantages and disadvantages of our approach relative to another compiler-directed scheme.

We study the problem of minimizing energy consumption in real-time embedded systems that execute variable workloads and are equipped with processors having dynamic voltage scaling (DVS) capabilities. This problem is about how to decide tasks' running speeds (speed schedule) before they are scheduled to execute. In this paper, we show that it is possible to incorporate the dynamic behavior of the tasks into the speed schedule to, along with the dynamic slack reclamation technique, minimize the expected (total) energy consumption in the system.

Main memory has become one of the largest contributors to overall energy consumption and offers many opportunities for power/energy reduction. In this paper, we propose a power-aware cached-DRAM (PA-CDRAM) organization that integrates a moderately sized cache directly into a memory module. We use this near-memory cache to turn a memory bank off immediately after it is accessed to reduce power consumption. We modify the structure of cached DRAM (CDRAM) with the goal of reducing energy consumption while retaining the performance advantage for which CDRAM was originally proposed. We evaluate the approach using a cycle accurate processor and memory simulator. Our results show that PACDRAM achieves up to 84% (28% on average) improvement in the energy-delay product and up to 76% (19% on average) savings in energy when compared to a time-out power management technique.

Abstract Power conservation has become a key design issue for many sys-tems, including clusters deployed for embedded systems, where

The interconnect plays a key role in both the cost and performance of large-scale HPC systems. The cost of future high-bandwidth electronic interconnects mushrooms due to expensive optical transceivers needed between electronic switches. We describe a potentially cheaper and more power-efficient approach to building high-performance interconnects. Through empirical analysis of HPC applications, we find that the bulk of inter-processor communication (barring collectives) is bounded in degree and changes very slowly or never. Thus we propose a two-network interconnect: An Optical Circuit Switching (OCS) network handling long-lived bulk data transfers, using optical switches; and a secondary lower-bandwidth Electronic Packet Switching (EPS) network. An OCS could be significantly cheaper, as it uses fewer optical transceivers than an electronic network. Collectives and transient communication packets traverse the electronic network. We present compiler techniques and dynamic run-time policies, using this two-network interconnect. Simulation results show that our approach provides high performance at low cost.

In wireless adhoc networks, channel and energy capacities are scarce resources. However, the design of the IEEE 802.11 DCF protocol leads to an inefficient utilization of these resources. We introduce BLAM, a new battery level aware MAC protocol, which is developed from an energy-efficiency point of view to extend the useful lifetime of an adhoc network. We modify the IEEE 802.11 DCF protocol to enable BLAM to tune the random deferring time for fresh and collided data packets dynamically, based on the node's energy. We show that BLAM can achieve an increase of 15% in network lifetime and an increase of about 35% in the total number of received packets.

We consider the maximization of network throughput in buffer-constrained optical networks using aggregate bandwidth allocation and reservation-based transmission control. Assuming that all flows are subject to loss-based TCP congestion control, we quantify the effects of buffer capacity constraints on bandwidth utilization efficiency through contention-induced packet loss. The analysis shows that the ability of TCP flows to efficiently utilize successful reservations is highly sensitive to the available buffer capacity. Maximizing the bandwidth utilization efficiency under buffer capacity constraints thus requires decoupling packet loss from contention-induced blocking of transmission requests. We describe a confirmed (two-way) reservation scheme that eliminates contention-induced loss, so that no packets are dropped at the network's core, and loss can be incurred only at the adequately buffer-provisioned ingress routers, where it is exclusively congestion-induced. For the confirmed signaling scheme, analytical and simulation results indicate that TCP aggregates are able to efficiently utilize the successful reservations independently of buffer constraints.

In current embedded systems, one of the major concerns is energy conservation. The dynamic voltage-scheduling (DVS) framework, which involves dynamically adjusting the voltage and frequency of the CPU, has become a well studied technique. It has been shown that if a task's computational requirement is only known probabilistically, there is no constant optimal speed for the task and the expected energy consumption is minimized by gradually increasing speed as the task progresses citelorchsmith. It is possible to find the optimal speed schedule if we assume continuous speed and a well defined power function, which are assumptions that do not hold in practice. In this paper, we study the problem from a practical point of view, that is, we study the case of discrete speeds and make no restriction on the form of the power functions. Furthermore, we take into account processor idle power and speed change overhead, which were ignored in previous similar studies. We present a fully polynomial time approximation scheme (FPTAS), which has performance guarantees and usually obtains solutions very close to the optimal solution in practice. Our evaluation shows that our algorithm performs very well and generally obtains solutions within 0.1.

The slack time in real-time systems can be used by recovery schemes to increase system reliability as well as by frequency and voltage scaling techniques to save energy. Moreover, the rate of transient faults (i.e., soft errors caused, for example, by cosmic ray radiations) also depends on system operating frequency and supply voltage. Thus, there is an interesting trade-off between system reliability and energy consumption. This work first investigates the effects of frequency and voltage scaling on the fault rate and proposes two fault rate models based on previously published data. Then, the effects of energy management on reliability are studied. Our analysis results show that, energy management through frequency and voltage scaling could dramatically reduce system reliability, and ignoring the effects of energy management on the fault rate is too optimistic and may lead to unsatisfied system reliability.

Honeypots have been proposed to act as traps for malicious attackers. However, because of their deployment at fixed (thus detectable) locations and on machines other than the ones they are supposed to protect, honeypots can be avoided by sophisticated attacks. We propose roaming honeypots, a mechanism that allows the locations of honeypots to be unpredictable, continuously changing, and disguised within a server pool. A (continuously changing) subset of the servers is active and providing service, while the rest of the server pool is idle and acting as honeypots. We utilize our roaming honeypots scheme to mitigate the effects of service-level DoS attacks, in which many attack machines acquire service from a victim server at a high rate, against back-end servers of private services. The roaming honeypots scheme detects and filters attack traffic from outside a firewall (external attacks), and also mitigates attacks from behind a firewall (internal attacks) by dropping all connections when a server switches from acting as a honeypot into being active. Through ns-2 simulations, we show the effectiveness of our roaming honeypots scheme. In particular, against external attacks, our roaming honeypots scheme provides service response time that is independent of attack load for a fixed number of attack machines.

In this paper we address the issue of controlling transmission power in power-aware ad hoc networks. Previous work that minimizes the transmission power does not consider both the energy consumed in collision resolution and the energy disbursed to overcome the interference resulting from neighboring nodes. We investigate the basic transmission power control for the 802.11 MAC protocols in which the control frames and the data frames can be transmitted at different power levels. A collision model together with an interference model of a uniformly distributed network is constructed. Based on these models, the end-to-end network throughput and the total energy consumption of the network are examined. For a network with a given node density, our results show the optimal transmission power for control messages and for data messages that will yield maximum throughput and minimum energy consumption per message.

Wireless networks have a constraint on their functional lifetime. This is due to the limited energy capacity of batteries powering the wireless nodes. For extending the lifetime of such battery-operated networks, we present a scheme for dynamically selecting the transmission rate for each node in the network. The transmission rate is based on the available energy budget in each node's battery. The goal is to increase the network capability of delivering more packets. The rate selection for each node is subject to satisfying a QoS timing constraint on the packet delivery time. Through adaptively varying each node's rate, we extended the lifetime 10 times on average more transmitting at a maximum rate and delivered on average 7.5 times more data packets. When compared with a scheme that transmits data at a lower rates independent of the battery levels, our scheme delivers up to 12% more packets for the same available total energy.

We address power-aware scheduling of periodic tasks to reduce CPU energy consumption in hard real-time systems through dynamic voltage scaling. Our intertask voltage scheduling solution includes three components: 1) a static (offline) solution to compute the optimal speed, assuming worst-case workload for each arrival, 2) an online speed reduction mechanism to reclaim energy by adapting to the actual workload, and 3) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that our reclaiming algorithm alone outperforms other recently proposed intertask voltage scheduling schemes. Our speculative techniques are shown to provide additional gains, approaching the theoretical lower-bound by a margin of 10 percent.

We describe how to exploit the scheduling slack in a real-time system to reduce energy consumption and achieve fault tolerance at the same time. During failure-free operation, a task takes checkpoints to enable recovery from failure. Additionally, the system exploits the slack to conserve energy by reducing the processor speed. If a task fails, it will restart from a saved checkpoint and execute at maximum speed to guarantee that the deadlines are met. We show that the number of checkpoints and their placements interact in subtle ways with the power management policy. We study two checkpoint placement policies for aperiodic tasks and analytically derive the optimal number of checkpoints to conserve energy under each. This optimal number allows the CPU speed to be slowed down to the level that yields minimum energy consumption, while still guaranteeing recoverability of tasks under each checkpointing policy. The results show that traditional periodic checkpointing is not the best policy for the combined purpose of conserving energy and guaranteeing recovery. Instead, better energy savings are possible through a nonuniform distribution of checkpoints that takes into account the energy consumption and reliability factors. Depending on the amount of slack and the checkpointing overhead, energy can be reduced by up to 68 percent under nonuniform checkpointing. We also demonstrate the applicability of these checkpoint placement policies to periodic tasks.

In a complex, heterogeneous network environment, such as the Internet, packets traversing different networks may be subjected to different treatments and may face different traffic loads across the routing path. This paper addresses the key issue of how to assign delay budgets to each network node along the routing path so that the end-to-end delay requirements of the supported applications are met. First, we describe a methodology to compute for a given flow a set of feasible per-node delays for the class of delay-based servers. We then formalize an optimal per-node delay assignment problem which takes into consideration the workload across the routing path. The solution, for homogeneous and heterogeneous networks, is provided. The resulting solution is optimal, but its implementation overhead is relatively high. To overcome this shortcoming, we propose two heuristics, EPH() and LBH(), to approximate the optimal strategy. EPH() uses the equi-partition concept to compute initial delay values and adjust these delay values to meet the end-to-end delay requirements. LBH() uses a relaxation factor to distribute the load proportionally across all nodes on the routing path. A simulation-based comparative analysis shows that the heuristics perform closely to the optimal schemes.

Power aware computing has become popular, recently and many techniques have been proposed to manage processor energy consumption for traditional real-time applications. In this paper, we are concerned mainly with the AND/OR model of real-time applications that have different execution paths consisting of different tasks. The contribution of this paper is twofold. First, we propose a greedy slack stealing algorithm to deal with applications represented by AND/OR graphs and prove its correctness in terms of meeting the timing constraints. Then, using statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and, thus, the overhead) while ensuring that the application meets its timing constraints. Some practical issues are also considered, such as shared memory access contention and idle energy consumption. The performance of the algorithms is analyzed with respect to processor energy savings. The results surprisingly show that the greedy slack stealing scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system or when there are only a few (four to six) voltage/speed levels.

In the context of battery-powered real-time systems three constraints need to be addressed: energy; deadlines; and task rewards. Many future real-time systems will count on different software versions, each with different rewards, time and energy requirements, to achieve a variety of QoS-aware tradeoffs. We propose a solution that allows the device to run the most valuable task versions while still meeting all deadlines and without depleting the energy. Assuming that the battery is rechargeable, we also propose: (a) a static solution that maximizes the system value assuming a worst-case scenario (i.e., worst-case task execution times); and (b) a dynamic scheme that takes advantage of the extra energy in the system when worst-case scenarios do not happen. Three dynamic policies are shown to make better use of the recharging energy while improving the system value.

The Pfair algorithms are optimal for independent periodic real-time tasks executing on a multiple-resource system. However, they incur a high scheduling overhead by making scheduling decisions in every time unit to enforce proportional progress for each task. In this paper, we will propose a novel scheduling algorithm, boundary fair (BF), which makes scheduling decisions and enforces fairness to tasks only at period boundaries. The BF algorithm is also optimal in the sense that it achieves 100% system utilization. Moreover, by making scheduling decisions at period boundaries, BF effectively reduces the number of scheduling points. Theoretically, the BF algorithm has the same complexity as that of the Pfair algorithms. But, in practice, it could reduce the number of scheduling points dramatically (e.g., up to 75% in our experiments) and thus reduce the overall scheduling overhead, which is especially important for online scheduling.

Rate-monotonic scheduling (RMS) is a widely used real-time scheduling technique. This paper proposes RBound, a new admission control for RMS. RBound has two interesting properties. First, it achieves high processor utilization under certain conditions. We show how to obtain these conditions in a multiprocessor environment and propose a multiprocessor scheduling algorithm that achieves a near optimal processor utilization. Second, the framework developed for RBound remains close to the original RMS framework (that is, task dispatching is still done via a fixed-priority scheme based on the task periods). In particular, we show how RBound can be used to guarantee a timely recovery in the presence of faults and still achieve high processor utilization. We also show how RBound can be used to increase the processor utilization when aperiodic tasks are serviced by a priority exchange server or a deferrable server.

The need for supporting dynamic real-time environments where changes in workloads occur frequently requires a scheduling framework that: (1) explicitly addresses overload conditions, (2) allows the system to achieve graceful degradation while guaranteeing the deadlines of the most critical tasks in the system, and (3) supports an efficient runtime selection mechanism capable of determining the load to be shed from the system to handle the overload. In this paper, we propose a novel scheduling framework for a real-time environment that experiences dynamic workload changes. This framework is capable of adjusting the system workload in incremental steps under overloaded conditions such that the most critical tasks in the system are always scheduled and the total value of the system is maximized. Each task has an assigned criticality value and consists of two parts, a mandatory part and an optional part. A timely answer is available after the mandatory part completes execution and its value may be improved by executing the entire optional part. The process of selecting tasks (mandatory or optional parts) to discard while maximizing the value of the system requires the exploration of a potentially large number of combinations. Since an optimal solution is too time-consuming to be computed online, an approximate algorithm is executed incrementally whenever the processor would otherwise be idle, progressively refining the quality of the solution. This scheme allows the scheduler to handle overloads with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the most critical tasks in the system. Simulation results show that few stages of the algorithm need to be executed for achieving a performance with near-optimal results.

New technologies have brought about a proliferation of embedded systems, which vary from control systems to sensor networks to personal digital assistants. Many of the portable embedded devices run several applications, which typically have three constraints that need to be addressed: energy , deadline , and reward . However, many of these portable devices do not have powerful enough CPUs and batteries to run all applications within their deadlines. An optimal scheme would allow the device to run the most applications, each using the most amount of CPU cycles possible, without depleting the energy source while still meeting all deadlines. In this paper we propose a solution to this problem; to our knowledge, this is the first solution that combines the three constraints mentioned above. We devise two algorithms, an optimal algorithm for homogeneous applications (with respect to power consumption) and a heuristic iterative algorithm that can also accommodate heterogeneous applications (i.e., those with different power consumption functions). We show by simulation that our iterative algorithm is fast and within 1% of the optimal.

We investigate the compiler algorithms to support compiled communication in multiprocessor environments and study the benefits of compiled communication, assuming that the underlying network is an all-optical time-division-multiplexing (TDM) network. We present an experimental compiler, E-SUIF, that supports compiled communication for High Performance Fortran (HPF) like programs on all-optical TDM networks, and describe and evaluate the compiler algorithms used in E-SUIF. We further demonstrate the effectiveness of compiled communication on all-optical TDM networks by comparing the performance of compiled communication with that of a traditional communication method using a number of application programs.

The high power consumption of modern processors becomes a major concern because it leads to decreased mission duration (for battery-operated systems), increased heat dissipation, and decreased reliability. While many techniques have been proposed to reduce power consumption for uniprocessor systems, there has been considerably less work on multiprocessor systems. In this paper, based on the concept of slack sharing among processors, we propose two novel power-aware scheduling algorithms for task sets with and without precedence constraints executing on multiprocessor systems. These scheduling techniques reclaim the time unused by a task to reduce the execution speed of future tasks and, thus, reduce the total energy consumption of the system. We also study the effect of discrete voltage/speed levels on the energy savings for multiprocessor systems and propose a new scheme of slack reservation to incorporate voltage/speed adjustment overhead in the scheduling algorithms. Simulation and trace-based results indicate that our algorithms achieve substantial energy savings on systems with variable voltage processors. Moreover, processors with a few discrete voltage/speed levels obtain nearly the same energy savings as processors with continuous voltage/speed, and the effect of voltage/speed adjustment overhead on the energy savings is relatively small.

Real-time systems (RTS) are those whose correctness depends on satisfying the required functional as well as the required temporal properties. Due to the criticality of such systems, recovery from faults is an essential part of a RTS. In many systems, such as those supporting space applications, single event upsets (SEUs) are the prevalent type of faults; SEUs are transient faults and affect a single task at a time. We present a scheme to guarantee that the execution of real-time tasks can tolerate SEUs and intermittent faults assuming any queue-based scheduling technique. Three algorithms are presented to solve the problem of adding fault tolerance to a queue of real-time tasks by reserving sufficient slack in a schedule so that recovery can be carried out before the task deadline without compromising guarantees given to other tasks. The first algorithm is a dynamic programming optimal solution, the second is a linear-time heuristic for scheduling dynamic tasks, and the third algorithm comprises extensions to address queues with gaps between tasks (gaps are caused by precedence, resource, or timing constraints). We show through simulations that the heuristics closely approximate the optimal algorithm. Finally, we describe the implementation of the modified admission control algorithm, non-preemptive scheduler, and recovery mechanism in the FT-RT-Mach operating system.

Power aware computing has become popular recently and many techniques have been proposed to manage the energy consumption for traditional real-time applications. We have previously proposed (2001) two greedy slack sharing scheduling algorithms for such applications on multi-processor systems. In this paper, we are concerned mainly with real-time applications that have different execution paths consisting of different number of tasks. The AND/OR graph model is used to represent the application data dependence and control flow. The contribution of this paper is twofold. First, we extend our greedy slack sharing algorithm for traditional applications to deal with applications represented by AND/OR graphs. Then, using the statistical information about the applications, we propose a few variations of speculative scheduling algorithms that intend to save energy by reducing the number of speed changes (and thus the overhead) while ensuring that the applications meet the timing constraints. The performance of the algorithms is analyzed with respect to energy savings. The results obtained show that the greedy scheme is better than some speculative schemes and that the greedy scheme is good enough when a reasonable minimal speed exists in the system.

Duplex and triple modular redundancy (TMR) systems are used when a high-level of reliability is desired. Real-time systems for autonomous critical missions need such degrees of reliability, but energy consumption becomes a dominant concern when these systems are built from high-performance processors that consume a large budget of electrical power for operation and cooling. Examples where energy consumption and real time are of paramount importance include reliable computers onboard mobile vehicles, such as the Mars Rover, satellites, and other autonomous vehicles. At first inspection, a duplex system uses about two thirds of the components that a TMR system does, leading one to conclude that duplex systems are more energy-efficient. This paper shows that this is not always the case. We present an analysis of the energy efficiency of duplex and TMR systems when used to tolerate transient failures. With no power management deployed, the analysis supports the intuitive impression about the relative superiority of duplex systems in energy consumption. The analysis shows, however that the gap in energy consumption between the two types of systems diminishes with proper power management. We introduce the concept of an optimistic TMR system that offers the same reliability and performance as the traditional one, but at a fraction of the energy consumption budget. Optimistic TMR systems are competitive with respect to energy consumption when compared with a power-aware duplex system, can even exceed it in some situations, and have the added bonus of providing tolerance to permanent faults.

Typical real-time scheduling theory has addressed deadline and energy constraints as well as deadline and reward constraints simultaneously in the past. However we believe that embedded devices with varying applications typically have three constraints that need to be addressed: energy, deadline, and reward. These constraints play important roles in the next generation of embedded devices, since they provide users with a variety of QoS-aware trade-offs. An optimal scheme would allow the device to run the most critical and valuable applications, without depleting the energy source while still meeting all deadlines. In this paper we propose a solution to this problem for typical control systems, such as frame-based task sets. We devise two algorithms that closely approximate the optimal solution while taking only a fraction of the runtime of an optimal solution.

This paper addresses multicast routing in circuit-switched multihop optical networks employing wavelength-division multiplexing. We consider a model in which multicast communication requests are made and released dynamically over time. A multicast connection is realized by constructing a multicast tree which distributes the message from the source node to all destination nodes such that the wavelengths used on each link and the receivers and transmitters used at each node are not used by existing circuits. We show that the problem of routing and wavelength assignment in this model is, in general, NP-complete. However, we also show that for any given multicast tree, the wavelength assignment problem can be solved in linear time.

In this paper, we provide an efficient solution for periodic real-time tasks with (potentially) different power consumption characteristics. We show that a task T/sub i/ can run at a constant speed S/sub i/ at every instance without hurting optimality. We sketch an O(n/sup 2/ log n) algorithm to compute the optimal S/sub i/ values. We also prove that the EDF (Earliest Deadline First) scheduling policy can be used to obtain a feasible schedule with these optimal speed values.

In this paper we address power-aware scheduling of periodic hard real-time tasks using dynamic voltage scaling. Our solution includes three parts: (a) a static (off-line) solution to compute the optimal speed, assuming worst-case workload for each arrival, (b) an on-line speed reduction mechanism to reclaim energy by adapting to the actual workload, and (c) an online, adaptive and speculative speed adjustment mechanism to anticipate early completions of future executions by using the average-case workload information. All these solutions still guarantee that all deadlines are met. Our simulation results show that the reclaiming algorithm saves a striking 50% of the energy, over the static algorithm. Further our speculative techniques allow for an additional approximately 20% savings over the reclaiming algorithm. In this study, we also establish that solving an instance of the static power-aware scheduling problem is equivalent to solving an instance of the reward-based scheduling problem [1, 4] with concave reward functions.

The power consumption of modern high-performance processors is becoming a major concern because it leads to increased heat dissipation and decreased reliability. While many techniques have been proposed to reduce power consumption for uni-processors, there has been considerably less work on multi-processor systems. In this paper we focus on power-aware scheduling for multi-processor real-time systems. Based on the idea of slack sharing among processors, we propose two novel scheduling algorithms for task sets with and without precedence constraints. These scheduling techniques reclaim the time unused by a task to reduce the execution speed of future tasks, and thus reduce the total energy consumption of the system. Simulation results indicate that our algorithms achieve up to 60% energy savings on multi-processor systems with variable voltage processors.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part. The mandatory part must complete before the task's deadline, while a nondecreasing reward function is associated with the execution of the optional part, which can be interrupted at any time. Imprecise computation and Increased-Reward-with-Increased-Service models fall within the scope of this-framework. In this paper, we address the reward-based scheduling problem for periodic tasks. An optimal schedule is one where mandatory-parts complete in a timely manner and the weighted average reward is maximized. For linear and concave reward functions, which are most common, we 1) show the existence of an optimal schedule where the optional service time of a task is constant at every instance and 2) show how to efficiently compute this service time. We also prove the optimality of Rate Monotonic Scheduling (with harmonic periods), Earliest Deadline First, and Least Laxity First policies for the case of uniprocessors when used with the optimal service times we computed. Moreover, we extend our result by showing that any policy which can fully utilize all the processors is also optimal for the multiprocessor periodic reward-based scheduling. To show-that our optimal solution is pushing the limits of reward-based scheduling, we further prove that, when the reward functions are convex, the problem becomes NP-Hard. Our static optimal solution, besides providing considerable reward improvements over the previous suboptimal strategies, also has a major practical benefit. Run-time overhead is eliminated and existing scheduling disciplines may be used without modification with the computed optimal service times.

The imprecise computation (IC) model is a general scheduling framework that is capable of expressing the precision vs. timeliness tradeoff involved in many current real-time applications. In that model, each task comprises mandatory and optional parts. While allowing greater scheduling flexibility, the mandatory parts in the IC model still have hard deadlines, and hence they must be completed before the task's deadline, even in the presence of faults. In this paper, we address fault-tolerant (FT) scheduling issues for IC tasks. First, we propose two recovery schemes, namely immediate recovery and delayed recovery. These schemes can be readily applied to provide fault tolerance to the mandatory parts by scheduling the optional parts appropriately for recovery operations. After deriving the necessary and sufficient conditions for both schemes, we consider the FT-optimality problem, i.e. generating a schedule which is FT and whose reward is maximum among all possible FT schedules. For immediate recovery, we present and prove the correctness of an efficient FT-optimal scheduling algorithm. For delayed recovery, we show that the FT-optimality problem is NP-hard, and thus is intractable.

In many real-time communication applications, predictable and guaranteed timeliness is one of the critical components of the quality of service (QoS) requirements. In this paper, we propose a new real-time message model with both rate requirements and distance constraints. Two algorithms are presented to schedule dynamic real-time message streams in a TDMA (time division multiple access) frame based on different scheduling policies by making greedy choices or optimization choices. The performance of the two algorithms is evaluated and compared in terms of time complexity, acceptance ratio and scheduling jitter via simulation.

Proposes a novel scheduling framework for a real-time environment that experiences dynamic changes. This framework is capable of adjusting the system workload in incremental steps under overloaded conditions such that the most critical tasks in the system are always scheduled and the total value of the system is maximized. Each task has an assigned criticality value and consists of two parts: a mandatory part and an optional part. A timely answer is available after the mandatory part completes execution and its value may be improved by executing the entire optional part. Optional parts can be discarded in overloaded conditions. The process of selecting optional parts to discard while maximizing the value of the system requires the exploration of a potentially large number of combinations. Since this process is too time-consuming to be computed online, an approximate algorithm is executed incrementally whenever the processor would otherwise be idle, progressively refining the quality of the solution. This criterion allows the scheduler to handle overloads with low cost while maximizing the use of the available resources and without jeopardizing the temporal constraints of the most critical tasks in the system. Simulation results show that few stages of the algorithm need to be executed to achieve a performance with near-optimal results.

Real-time systems are being increasingly used in several applications which are time-critical in nature. Fault tolerance is an essential requirement of such systems, due to the catastrophic consequences of not tolerating faults. In this paper, we study a scheme that guarantees the timely recovery from multiple faults within hard real-time constraints in uniprocessor systems. Assuming earliest-deadline-first scheduling (EDF) for aperiodic preemptive tasks, we develop a necessary and sufficient feasibility-check algorithm for fault-tolerant scheduling with complexity O(n/sup 2/-/spl kappa/), where n is the number of tasks to be scheduled and /spl kappa/ is the maximum number of faults to be tolerated.

Many real-time multiprocessor scheduling techniques have been proposed to guarantee the timely execution of periodic preemptive real-time tasks. However timeliness is usually only guaranteed in the absence of faults, which may be unacceptable for some critical systems. We therefore address the problem of multiprocessor scheduling for preemptive real-time tasks so that the timeliness of the system can be guaranteed even in the presence of faults. This work focuses on global scheduling where tasks can migrate across processors. We consider two varieties of global multiprocessor scheduling: in the frame-based model, an aperiodic task set is scheduled to create a template (frame), and that schedule may be executed periodically. In the periodic model, each task in the set has a separate period, and is executed with no explicitly predetermined schedule. For each model, we show how to guarantee timely execution and recovery in the general case. We also propose solutions that improve upon this general case when all tasks require the same amount of time to recover from a fault.

Traditional TMR protocols assume either single, reliable voters for each triple-modular redundant unit (TMRU) or triplicated voters (one for each processor) for each TMRU. In the first case a voter is a single point of failure for the system. In the second case, many physical messages must be sent across the communication network for each logical data item. We examine some protocols which attempt to maintain the functionality of the triplicated voter TMR protocol while reducing the number of physical messages required by one third. Possible solutions are examined to the many issues that result from this reduction in communication. Three different reduced-communication triple-modular redundant (RTMR) protocols are considered, each of which makes different assumptions about the nature of the underlying computation.

To fully exploit the performance of optics in parallel processor interconnection networks, the connections must be entirely optical. This requires the use of circuit switching. Techniques such as time division multiplexing (TDM) can be used to provide a large number of circuits without the need for program directed control operations. We describe two protocols for dynamically establishing circuits in an interconnection network. We show how TDM can be used to multiplex communication for data and control purposes together in a single optical network. We explore the ability of the protocols and TDM to exploit locality in the communication pattern to improve performance.

Reward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part, with which a nondecreasing reward function is associated. Imprecise Computation and Increased-Reward-with-Increased-Service models fall within the scope of this framework. In this paper we address the reward-based scheduling problem for periodic tasks. For linear and concave reward functions we show: (a) the existence of an optimal schedule where the optional service time of a task is constant at every instance and (b) how to efficiently compute this service time. We also prove that RMS-h (RMS with harmonic periods), EDF and LLF policies are optimal when used with the optimal service times we computed, and that the problem becomes NP-Hard, when the reward functions are convex. Further, our solution eliminates run-time overhead, and makes possible the use of existing scheduling disciplines.

Even though real-time systems have the stringent constraint of completing tasks before their deadlines, many existing real-time operating systems do not implement fault tolerance capabilities. In this paper we summarize fault tolerant real-time scheduling policy for dynamic tasks with ready times and deadlines. Our focus in this paper is the implementation, which includes fault-tolerant scheduling, re-scheduling, and recovery mechanisms in the FT-RT-Mach operating system, a fault-tolerant version of RT-Mach. A real-time train control application is then implemented using the FT-RT-Mach operating system. Copyright © 1999 John Wiley & Sons, Ltd.

In this paper, we study distributed path reservation protocols for multiplexed all-optical interconnection networks. The path reservation protocols negotiate the reservation and establishment of connections that arrive dynamically to the network. These protocols can be applied to both wavelength division multiplexing (WDM) and time division multiplexing (TDM) networks. Two classes of protocols are discussed: forward reservation protocols and backward reservation protocols. Simulations of multiplexed two-dimensional torus interconnection networks are used to evaluate and compare the performance of the protocols and to study the impact of system parameters, such as the multiplexing degree and the network size, speed, and load, on both network throughput and communication delay. The simulation results show that, in most cases, the backward reservation schemes provide better performance than their forward reservation counterparts.

The authors study GRMS, a global scheduling scheme for rate monotonic tasks on a multiprocessor. Several admission control algorithms for GRMS are presented, both for hard and soft real-time tasks. The average performance of these admission control algorithms is compared with the performance of known partitioning schemes. The result of these comparisons outlines some situations where one scheme is preferable over the other. Partitioning schemes are better suited for hard real-time systems, while a global scheme is preferable for soft real-time systems.

This paper describes the design of a centralized controller/scheduler for a communication switch with a banyan switching fabric built using unbuffered switches. The controller accepts a set of connection requirements and identifies a non-conflicting subset that can be used to set the state of the switches for data transfer. The logic can be implemented using a relatively small number of gates and can be pipelined to provide rapid control of the switch fabric. The controller can be used with a replicated banyan network fabric that provides sufficient switching bandwidth.

We consider multihop communications on optical torus networks with time-division multiplexing where logical topologies are realized on top of the physical network to improve the communication performance. The logical topologies reduce the number of intermediate hops at the cost of a larger multiplexing degree. On the one hand, the larger multiplexing degree increases the packet communication time between hops. On the other hand, reducing the number of intermediate hops reduces the time spent at intermediate hops. We study the trade-off between the multiplexing degree and the number of intermediate hops. Specifically, we study four logical topologies ranging from the most dense logical all-to-all connections to the simplest logical torus topology on top of physical torus networks. We develop an analytical model that models the maximum throughput and the average packet delay of the multihop networks, verify the model through simulations, and study the performance and the impact of system parameters on the performance for these four topologies.

We consider the problem of realizing several common communication structures in the all-optical Partitioned Optical Passive Stars (POPS) topology. We show that, often, the obvious or "natural" method of implementing a communication pattern in the POPS does not efficiently utilize its communication capabilities. We present techniques which distribute the communication load uniformly in the POPS for four of the most common communication patterns (all-to-all personalized, global reduction operations, ring, and torus). We prove that these techniques provide optimal performance in the sense that they minimize the time required to deliver the messages from each node to its neighbors.

In this paper, we study distributed path reservation protocols for multiplexed all-optical interconnection networks. In such networks, a path for a connection is reserved such that transmitted data remains in the optical domain until it reaches its destination. The path reservation protocols negotiate the reservation and establishment of connections that arrive dynamically to the network. They can be applied to both wavelength division multiplexing (WDM) and time division multiplexing (TDM), which are two techniques that allow the large optical bandwidth to be shared among multiple connections. Two classes of protocols are discussed: forward reservation protocols and backward reservation protocols. Simulations of multiplexed 2-dimensional torus interconnection networks are used to evaluate and compare the performance of the protocols, and to study the impact of system parameters on both network throughput and communication delay. The simulation results show that the backward reservation schemes provide better performance than their forward reservation counterparts.

Real time systems are being increasingly used in several applications which are time critical in nature. Fault tolerance is an important requirement of such systems, due to the catastrophic consequences of not tolerating faults. We study a scheme that provides fault tolerance through scheduling in real time multiprocessor systems. We schedule multiple copies of dynamic, aperiodic, nonpreemptive tasks in the system, and use two techniques that we call deallocation and overloading to achieve high acceptance ratio (percentage of arriving tasks scheduled by the system). The paper compares the performance of our scheme with that of other fault tolerant scheduling schemes, and determines how much each of deallocation and overloading affects the acceptance ratio of tasks. The paper also provides a technique that can help real time system designers determine the number of processors required to provide fault tolerance in dynamic systems. Lastly, a formal model is developed for the analysis of systems with uniform tasks.

Reducing communication latency, which is a performance bottleneck in optically interconnected multiprocessor systems, is of prominent importance. A conventional approach for establishing connections in multiplexed networks uses a set of independent time slots (or virtual channels) along a path for each connection. This approach requires the use of switching devices capable of interchanging time slots, and thus introduces latency in addition to hardware and control complexity. We propose an approach to all-optical time division multiplexed (TDM) communications in multiprocessor systems. The idea is to establish a connection along a path using a set of time slots (or virtual channels) that are dependent on each other, so that no time slot interchanging is required. We compare the proposed approach with the conventional one in terms of the overall communication latency. We found that, despite the possibility that establishing a connection may take a longer time, the proposed approach will result in lower overall communication latency as it eliminates the delays introduced by the time slot interchanging switching devices.

While all-optical networks offer large bandwidth for transferring data, the control mechanisms to dynamically establish all-optical paths incur large overhead. In this paper, we consider the problem of adapting all-optical multiplexed networks in multiprocessor or multicomputer environment by using compiled communication as an alternative to dynamic network control. In compiled communication, the network resources are managed statically and therefore, run time control overhead is eliminated. In addition, complex offline algorithms can be incorporated to manage the network resources more efficiently. We studied several off-line connection scheduling algorithms for optimizing the multiplexing degree required to satisfy communication requests. The performance of compiled communication for communication patterns that can be determined at compile time in application programs is evaluated and compared with dynamically controlled communication assuming a two-dimmension torus topology. Our results show that the compiled communication out-performs the dynamic communication to a large degree for these communication patterns. Since most of the communication patterns in parallel applications can be determined at compile time, we conclude that compiled communication is an effective mechanism for all-optical network in multiprocessor environments.

Distributed-memory systems can incorporate thousands of processors at a reasonable cost. However, with an increasing number of processors in a system, fault detection and fault tolerance become critical issues. By replicating the computation on more than one processor and comparing the results produced by these processors, errors can be detected. During the execution of a program, due to data dependencies, typically not all of the processors in a multiprocessor system are busy at all times. Therefore processor schedules contain idle time slots and it is the goal of this work to exploit these idle time slots to schedule duplicated computation for the purpose of fault detection. We propose a compiler-assisted approach to fault detection in regular loops on distributed-memory systems. This approach achieves fault detection by duplicating the execution of statement instances. After carefully analyzing the data dependencies of a regular loop, selected instances of loop statements are duplicated in a way that ensures the desired fault coverage. We first present duplication strategies for fault detection and show that these strategies use idle processor times for executing replicated statements, whenever possible. Next, we present loop transformations to implement these fault-detection strategies. Also, a general framework for selecting appropriate loop transformations is developed. Experimental results performed on the CRAY-T3D show that the overhead of adding the fault detection capability is usually less than 25%, and is less than 10% when communication overhead is reduced by grouping messages.

A physical link can be time-multiplexed to create several time slots, each of which corresponding to a virtual link. A conventional approach establishes a connection along a path using a set of independent time slots (or virtual links) and thus requires the use of switching devices capable of interchanging time slots. This paper proposes a different approach to all-optical Time Division Multiplexed (TDM) communications in multiprocessor systems. The idea is to establish a connection along a path using a set of time slots (or virtual links) that are dependent on each other, so that no time-slot interchanging is required. It is found that, despite of the possibility that establishing a connection may take a longer time, the proposed approach will result in lower overall communication latency as it eliminates the delays introduced by the time-slot interchanging switching devices.>

We present a scheme to guarantee that the execution of real-time tasks can tolerate transient and intermittent faults assuming any queue-based scheduling technique. The scheme is based on reserving sufficient slack: in a schedule such that a task can be re-executed before its deadline without compromising guarantees given to other tasks. Only enough slack is reserved in the schedule to guarantee fault tolerance if at most one fault occurs within a time interval. This results in increased schedulability and a very low percentage of deadline misses even if no restriction is placed on the fault separation. We provide two algorithms to solve the problem of adding fault tolerance to a queue of real-time tasks. The first is a dynamic programming optimal solution and the second is a greedy heuristic which closely approximates the optimal.

In this paper, we consider a class of modular multiprocessor architectures in which spares are added to each module to cover for faulty nodes within that module, thus forming a fault-tolerant basic block (FTBB). In contrast to reconfiguration techniques that preserve the physical adjacency between active nodes in the system, our goal is to preserve the logical adjacency between active nodes by means of a routing algorithm which delivers messages successfully to their destinations. We introduce two-phase routing strategies that route messages first to their destination FTBB, and then to the destination nodes within the destination FTBB. Such a strategy may be applied to a variety of architectures including binary hypercubes and three-dimensional tori. In the presence of f faults in hypercubes and tori, we show that the worst case length of the message route is min {/spl sigma/+f, (K+1)/spl sigma/}+c where /spl sigma/ is the shortest path in the absence of faults, K is the number of spare nodes in an FTBB, and c is a small constant. The average routing overhead is much lower than the worst case overhead.

In this paper we consider the problem of reconfiguring processor arrays subject to computational loads that alternate between two modes. A strict mode is characterized by a heavy computational load and severe constraints on response time while a relaxed mode is characterized by a relatively light computational load and relaxed constraints on response time. In the strict mode, reconfiguration is performed by a distributed local algorithm in order to achieve fast recovery from faults. In the relaxed mode, a global reconfiguration algorithm is used to restore the system to a state that maximizes the probability that future faults occurring in subsequent strict modes will be repairable. Several new results are given for this problem. Efficient reconfiguration algorithms are described for a number of general classes of architectures. These general algorithms obviate the need for architecture-specific algorithms for architectures in these classes. We show that it is unlikely that similar algorithms can be obtained for related classes of architectures since the reconfiguration problem for these classes is NP-complete. Finally, a general approximation algorithm is described that can be used for any architecture. Experimental results are given, suggesting that our algorithms are very effective.>

Modern computer buses are typically organized by the three functions of data transfer, addressing, and arbitration/control. In this paper we present a fiber-based bus design which provides optical solutions for each of these functions. The design includes an all-optical addressing system, based on coincident pulse addressing, which eliminates the latency contribution and bandwidth limitation associated with electronic address decoding. The control system uses time-of-flight relationships between a priority chain and a feedback waveguide to implement fully distributed asynchronous and self-timed bus arbitration.>

Different multiple redundancy schemes for fault detection and correction in computational arrays are proposed and analyzed. The basic idea is to embed a logical array of nodes onto a processor/switch array such that d processors, 1/spl les/d/spl les/4, are dedicated to the computation associated with each node. The input to a node is directed to the d processors constituting that node, and the output of the node is computed by taking a majority vote among the outputs of the d processors. The proposed processor/switch array (PSVA) is versatile in the sense that it may be configured as a nonredundant system or as a system which supports double, triple or quadruple redundancy. It also allows for spares to be distributed in the PSVA in a way that permits spare sharing among nodes, thus enhancing the overall system reliability. In addition to choosing the required degree of redundancy, the flexibility of the PSVA architecture allows for the embedding of redundant arrays onto defective PSVA's and for run-time reconfiguration to avoid faulty processors and switches. Different embedding and reconfiguration algorithms are presented and analyzed using Markov chain techniques, using probability arguments, and via simulation.>

We study the problem of network embeddings in 2-D array architectures in which each row and column of processors are interconnected by a bus. These architectures are especially attractive if optical buses are used that allow simultaneous access by multiple processors through either wavelength division multiplexing or message pipelining, thus overcoming the bottlenecks caused by the exclusive access of buses. In particular, we define S-trees to include both binary X-trees and pyramids, and present two embeddings of X-trees into 2-D processor arrays with spanning buses. The first embedding has the property that all neighboring nodes in X-trees are mapped to the same bus in the target array, thus allowing any two neighbors in the embedded S-trees to communicate with each other in one routing step. The disadvantage of this embedding is its relatively high expansion cost. In contrast, the second embedding has an expansion cost approaching unity, but does not map all neighboring nodes in X-trees to the same bus. These embeddings allow all algorithms designed for binary trees, pyramids, as well as X-trees to be executed on the target arrays.>

Time division multiplexed multistage interconnection networks (TDM-MIN's) are proposed for multiprocessor communications. Connections required by an application are partitioned into a number of subsets, called mappings, such that connections in each mapping can be established in an MIN without conflict. Switch settings for establishing connections in each mapping are determined and stored in shift registers. By repeatedly changing switch settings, connections in each mapping are established for a time slot in a round-robin fashion. Thus, all connections required by an application may be established in an MIN in a time division multiplexed way. TDM-MIN's can emulate a completely connected network using N time slots. It can also emulate regular networks such as rings, meshes, cube-connected-cycles (CCC), binary trees, and n-dimensional hypercubes using 2, 4, 3, 4, and n time slots, respectively. The problem of partitioning an arbitrary set of requests into a minimal number of mappings is NP-hard. Simple heuristic algorithms are presented and their performances are shown to be close to optimal. The flexibility of TDM-MIN's allows for the support of run-time requests through dynamic reconfigurations. The techniques are especially suitable for hybrid electro-optical systems with optical interconnects.>

Communication overhead can significantly impact the performance execution of programs on distributed-memory systems.

An optical communication structure is proposed for multiprocessor arrays which exploits the high communication bandwidth of optical waveguides. The structure takes advantage of two properties of optical signal transmissions on waveguides, namely, unidirectional propagation and predictable propagation delays per unit length. Because of these two properties, time-division multiplexing (TDM) of messages has the same effect as message pipelining on optical waveguides. Two TDM approaches are proposed, and the combination of the two is used in the design of the optical communication structure. Analysis and simulation results are given to demonstrate the communication effectiveness of the system. A clock distribution method is proposed to address potential synchronization problems. Feasibility issues with current and future technologies are discussed.>

Two types of algorithms are considered, namely, local algorithms and global algorithms. In a local algorithm, no processors need to know the status of all other processors in the system. The recovery process is distributed among the processors with each processor using extremely local knowledge. With these properties, the reconfiguration algorithm may achieve fast recovery and real time response but many sacrifice the optimal use of redundancy. In contrast, the goal of a global algorithm is to optimize the use of redundancy with respect to some fault tolerance criteria. This, however, requires global knowledge about other processors in the system and often necessitates extensive changes in the configuration of the system. For unmaintained, long-life systems, local fault tolerance algorithms have the advantages of fast recovery, while global fault tolerance algorithms provide better reliability and longer life expectancy. Fortunately, under certain conditions, it is possible to combine the advantages of the two types of algorithms. These conditions are described.>

During the past decade, systolic arrays have been designed for a wide variety of scientific applications, which are based on highly parallel linear system manipulations. Partitioning and mapping of systolic algorithms has been a key issue for real implementations, in terms of both cost and manageability. The authors demonstrate the mapping of triangular systolic array algorithms onto a one-dimensional ring of processors, so that the resulting architecture features an asymptotically optimal utilization factor in pipelined operation. fee problems of least squares system identification and FIR filtering using QR-decomposition via Givens rotations are used as a vehicle for the demonstration of uni- and bi-directional dataflow algorithms on systolic rings.>

An optical communication structure for multipro­ ceSsor arrays that exploits the high communication bahdwidth of optical waveguides is proposed. The struc­ turle takes advantage of two properties of optical signal trqnsmissions on waveguides. Namely. unidirectional pfppagation and predictable propagation delays per unit length. Two novel time-division mUltiplexing approaches are proposed for non SIM D environments to obtain a communication bandwidth comparable to that of mes­ sage pipe lining in SIMD environments. Analysis and simulation results are given to evaluate the communica­ tion effectiveness of the system. A clock distribution method is also proposed to address potential synchroni­ zation problems. Finally. feasibility issues with current andfuture technologies are discussed.

Consideration is given to fault tolerant systems that are built from modules called fault tolerant basic blocks (FTBBs), where each module contains some primary nodes and some spare nodes. Full spare utilization is achieved when each spare within an FTBB can replace any other primary or spare node in that FTBB. This, however, may be prohibitively expensive for larger FTBBs. Therefore, it is shown that for a given hardware overhead more reliable systems can be designed using bigger FTBBs without full spare utilization than using smaller FTBBs with full spare utilization. Sufficient conditions for maximizing the reliability of a spare allocation strategy in an FTBB for a given hardware overhead are presented. The proposed spare allocation strategy is applied to two fault tolerant reconfiguration schemes for binary hypercubes. One scheme uses hardware switches to replace a faulty node, and the other scheme uses fault tolerant routing to bypass faulty nodes in the system and deliver messages to the destination node.>

The concept of pipelined buses for parallel architectures diverges from the conventional exclusive access buses and offers both possibilities and challenges for significantly improving the efficiency of interprocessor communications in parallel computers. The authors present an efficient embedding of pyramids in array processors with pipelined buses. The embedding has the property that all the neighboring nodes in the pyramid are mapped to the same bus. Thus, any two neighbors in the embedded pyramid can communicate with each other using a single bus cycle.>

A new switching method, called short-circuit switching, is proposed for multistage interconnection networks. It combines the advantages of both message switching and circuit switching methods currently used. An analytical model for predicting the delay time of networks with short-circuits is presented under the assumption of infinite queue length and fixed message length. To remove these assumptions, several simulations were conducted comparing the performance of circuit, short-circuit, and message switchings. These results show that, in multistage interconnection networks, short-circuit switching outperforms message and circuit switchings.

A novel technique, the multiple ripple propagation technique, is presented for mapping and h*w grid into a w*h grid such that the dilation cost is 2, i.e. such that any two neighboring nodes in the first grid are mapped onto two nodes in the second grid that are separated by a distance of at most 2. The technique is then used as a basic tool for mapping any rectangular source grid into a square target grid with the dilation two property preserved. The ratio of the number of nodes in the source grid to the number of nodes in the target grid, called the expansion cost, is shown to be always less than 1.2. This is a significant improvement over the previously suggested techniques, where the expansion cost could be bounded by 1.2 only if the dilation cost was allowed to be as high as 18.>

Optical waveguides allow for enhanced bandwidth, loosened loading constraints and large physical distribution of computing resources. Moreover, optics enjoy a unique property that is not shared with electronics, namely the unidirectional propagation of signals. It is this property that is exploited in this paper to increase the effective bandwidth of optical buses. Specifically, a space-multiplexing technique for pipelined messages on optical buses is introduced and analysed. It is shown that pipelined buses support arbitrary routeing permutations in synchronous systems with only linear hardware complexity. Further, a bus arbitration protocol which extends the technique to asynchronous systems is presented. The pipelining of control and data signals represents a significant departure from the conventional exclusive access discipline which characterises bus-interconnected multiprocessors. By relaxing the exclusive access requirement, space multiplexing can support the design of large-scale, distributed, tightly coupled multiprocessor systems.

The idea of grouping the nonzero elements of a sparse matrix into a few stripes that are almost parallel is applied to the design of a systolic accelerator for sparse matrix operations. This accelerator is then integrated into a complete systolic system for the solution of large sparse linear systems of equations. The design demonstrates that the application of systolic arrays is not limited to regular computations, and that computationally irregular problems can be solved on systolic networks if local storage is provided in each systolic cell for buffering the irregularity in the data movement and for absorbing the irregularity in the computation.>

Many iterative algorithms for the solution of large linear systems may be effectively vectorized if the diagonal of the matrix is surrounded by a large band of zeroes, whose width is called the zero stretch. In this paper, a multicolor numbering technique is suggested for maximizing the zero stretch of irregularly sparse matrices. The technique, which is a generalization of a known multicoloring algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to n /2σ, where 2σ is the number of colors used in the algorithm. For triangular meshes, it is shown that σ ≤ 3, and that it is possible to obtain σ = 2 by applying a simple backtracking scheme.

The general question addressed in this study is: are regular networks suitable for sparse matrix computations? More specifically, we consider a special purpose self-timed computational array that is designed for a specific dense matrix computation. We add to each cell in the network the capability of recognizing and skipping operations that involve zero operands, and then ask how efficient is this resulting network for sparse matrix computation? In order to answer this question, it is necessary to study the effect of data interlock on the performance of self-timed networks. For this, the class of pseudosystolic networks is introduced as a hybrid class between systolic and self-timed networks. Networks in this class are easy to analyze, and provide a means for the study of the worst case performance of self-timed networks. The well known concept of computation fronts is also generalized to include irregular flow of data, and a technique based on the propagation of such computation fronts is suggested for the estimation of the processing time and the communication time of pseudosystolic networks.

The main objective of this paper is to provide a methodology for the simulation of systolic architectures by applying a model that was previously suggested for the verification of systolic networks.This methodology is meant to be used for the computational assessment of such networks in the cases when formal verification is difficult.A simple language is presented to express a system of sequence equations that models the operation of the network.Then a syntax directed interpreter is developed to solve this system for specific forms of the inputs and produce the corresponding outputs.A systolic Cholesky decomposition network is introduced and used to illustrate the simulation technique.

A mathematical model for systolic architectures is suggested and used to verify the operation of certain systolic networks. The data items appearing on the communication links of such a network at successive time units are represented by data sequences and the computations performed by the network cells are modeled by a system of difference equations involving operations on the various data sequences. The input/output descriptions, which describe the global effect of the computations performed by the network, are obtained by solving this system of difference equations. This input/output description can then be used to verify the operation of the network. The suggested verification technique is applied to four different systolic networks proposed in the literature.