Processing-in-Memory (PIM) aims to address the costly data movement between processing elements and memory subsystem, by computing simple operations inside DRAM in parallel. The large capacity, wide activation size during cell access, and the maturity of DRAM technology, make this technology a great choice for PIM techniques. Nonetheless, vulnerability to process variation and noises, internal leakage of the cells, and high latency in cell access, limit the utilization of processing in DRAMs for real-world applications. This work proposes a fast PIM technique, called WISEDRAM, which leverages one row of special cells, called X-cells, to enable in-DRAM bulk-bitwise operations. Unlike previous approaches, WISEDRAM retains the conventional DRAM cell access procedure, thereby ensuring the reliability of cell access for reads and writes at a level equivalent to that of conventional DRAMs. Compared with the state-of-the-art, WISEDRAM exhibits $22 \%$ reduction in average bitwise computation latency and a $71 \%$ improvement in XOR operation execution speed, while imposing an area overhead of $1.6 \%$.

In-memory computing (IMC) paradigm reduces costly and inefficient data transfer between memory modules and processing cores by implementing simple and parallel operations inside the memory subsystem. SRAM, the fastest memory structure in the memory hierarchy, is an appropriate platform to implement IMC. However, the main challenges of implementing IMC in SRAM are the limited operations and unreliable accuracy due to environmental noise and process variations. This work proposes a low-latency, energy-efficient, and noise-robust IMC technique, called Bitwise In-Memory Accelerator using 6T-SRAM Structure (BIMAX). BIMAX performs parallel bitwise operations (i.e., (N)AND, (N)OR, NOT, X(N)OR) as well as row-copy with the capability of writing the computation result back to a target memory row. BIMAX functionality is based on an imbalanced differential sense amplifier (SA) that reads and writes data from and into multiple 6T-SRAM cells. The simulations show BIMAX performs these operations with 52.7% lower energy dissipation compared to the state-of-the-art IMC technique, with 5.7% average higher performance rate. Furthermore, BIMAX is about 5.4× more robust against environmental noises compared to the state-of-the-art.

Memory hierarchy in Graphics Processing Units (GPUs) is conventionally designed to provide high bandwidth rather than low latency. In particular, because of the high tolerance to load-to-use latency (i.e., the time that warps wait for data fetched by memory loads), GPU L1D caches are optimized for density, capacity, and low power with latencies that are often orders of magnitude longer than conventional CPU caches. However, there are many important classes of data-parallel applications (e.g., graph, tree, priority queue processing, and sparse deep learning applications) that benefit from lower load-to-use latency than that offered by modern GPUs due to their inherent divergence and low effective Thread-Level Parallelism (TLP). This article introduces an innovative on-chip cache hierarchy that incorporates a decoupled L1D cache with reduced latency (LoTUS) and its management scheme. LoTUS is a minimally sized fully associative cache placed in each GPU subcore that captures the primary working set of data-parallel applications. It exploits conventional high-performance low-density SRAM cells and dramatically reduces load-to-use latency. We also propose an intelligent extension of LoTUS, called LoTUSage, which employs a lightweight learning-based model to predict the utility of caching requests in LoTUS. Evaluation results show that LoTUS and LoTUSage improve the average performance by 23.9% and 35.4% and reduce the average energy consumption by 27.8% and 38.5%, respectively, for the applications suffering from high load-to-use stalls with negligible area and power overheads.

The increasing density of DRAM chips has led to heightened susceptibility of memory cells to bit-flips. Rowhammer and Rowpress attacks on DRAMs have obtained significant attention due to their effectiveness in compromising system security and data integrity. A substantial portion of the previously proposed techniques for detecting rowhammer attacks focus on counting the number of row activations. However, these methods suffer from several limitations, including high overheads, lack of consideration for environmental conditions during DRAM operation, and limited tunability to detect rowpress attacks. To address these challenges, this work introduces a novel low-overhead built-in DRAM sensor designed specifically for detecting and locating rowhammer and rowpress attacks. The core idea behind the sensor is to utilize an additional non-operational DRAM sensor cell for each row. This auxiliary cell experiences the same potential rowhammer attacks as the other cells within that row. The sensor operates by controlling an extra precharged match-line based on the charge stored in the sensor cells. This sensor not only detects rowhammer attacks but also other environmental conditions that may impact DRAM cells retention time, such as temperature elevation or changes in operating voltage. Simulation results demonstrate that the proposed sensor detects all of the rowhammer attacks in the presence of process variation with a variance of up to 7.5% in circuit parameters. Furthermore, the area overhead introduced by the sensor remains about 1%, making it a promising solution for enhancing DRAM security with the minimum memory structure change.

This paper proposes Blenda, a dynamically-partitioned memory-cache blend architecture for giga-scale die-stacked DRAMs. Blenda architects the stacked DRAM partly as memory and partly as cache, and dynamically adjusts each part's size to workloads' demands. The memory part hosts hot data objects and serves requests to them efficiently (i.e., without metadata overheads). The cache part captures transient data and filters requests to bandwidth-limited off-chip DRAM. Blenda provides three key contributions: (i) Blenda partitions stacked DRAM's capacity in a workload-aware manner: different workloads enjoy different memory-cache configurations. (ii) Blenda is reactive: the configuration is adjusted to workloads' phases dynamically and application-transparently: no reboot or user involvement are needed. (iii) Blenda gracefully transitions among configurations: no data invalidation is required upon most reconfigurations. We simulate 15 diverse big-data workloads running on a state-of-the-art processor and show that Blenda outperforms the best-performing prior architecture by 34%. Blenda's total storage overhead is less than 100 bytes per core.

Graphics Processing Units (GPUs) are the accelerator of choice in a variety of application domains, because they can accelerate massively parallel workloads and can be easily programmed using general-purpose programming frameworks such as CUDA and OpenCL. Each Streaming Multiprocessor (SM) contains an L1 data cache (L1D) to exploit the locality in data accesses. L1D misses are costly for GPUs for two reasons. First, L1D misses consume a lot of energy as they need to access the L2 cache (L2) via an on-chip network and the off-chip DRAM in case of L2 misses. Second, L1D misses impose performance overhead if the GPU does not have enough active warps to hide the long memory access latency. We observe that threads running on different SMs share 55% of the data they read from the memory. Unfortunately, as the L1Ds are in the non-coherent memory domain, each SM independently fetches data from the L2 or the off-chip memory into its L1D, even though the data may be currently available in the L1D of another SM. Our goal is to service L1D read misses via other SMs, as much as possible, to cut down costly accesses to the L2 or the off-chip DRAM. To this end, we propose a new data-sharing mechanism, called Cross-Core Data Sharing (CCDS) . CCDS employs a predictor to estimate whether the required cache block exists in another SM. If the block is predicted to exist in another SM’s L1D, then CCDS fetches the data from the L1D that contain the block. Our experiments on a suite of 26 workloads show that CCDS improves average energy and performance by 1.30× and 1.20×, respectively, compared to the baseline GPU. Compared to the state-of-the-art data-sharing mechanism, CCDS improves average energy and performance by 1.37× and 1.11×, respectively.

Abstract. Field-Programmable Gate Arrays (FPGAs) employ a large number of SRAM cells to provide a flexible routing architecture which have a significant impact on the FPGA’s area and power consumption. This flexible routing allows for a rather easy realization of the desired functionality, but our evaluations show that the full routing flexibility is not required in many occasions. In this work, we focus on what is actually needed and introduce a new switch-box realization what we call Turn-Restricted Switch-Boxes which supports only a subset of possible turns. The proposed method increases the utilization rate of FPGA switch-boxes by eliminating the unemployed resources. Experimental evaluations confirm that the area and average power consumption can be reduced by 12.8% and 14.1%, on average, respectively and the FPGA routing susceptibility to SEU and MBU can be improved by 18.2%, on average, by imposing negligible performance. 1

The performance and capacity of solid-state drives (SSDs) are continuously improving to meet the increasing demands of modern data-intensive applications. Unfortunately, communication between the SSD controller and memory chips (e.g., 2D/3D NAND flash chips) is a critical performance bottleneck for many applications. SSDs use a multi-channel shared bus architecture where multiple memory chips connected to the same channel communicate to the SSD controller with only one path. As a result, path conflicts often occur during the servicing of multiple I/O requests, which significantly limits SSD parallelism. It is critical to handle path conflicts well to improve SSD parallelism and performance.

DRAM is the most mature and widely-utilized memory structure as main memory in computing systems. However, energy dissipation and latency of DRAM are two of the most serious limiting factors of this technology. All DRAM main operations are initiated by a Precharge phase, which is time-consuming and power-hungry. This work proposes a novel DRAM cell access scheme that entirely eliminates Precharge phase from DRAM read, write, and refresh operations, with a very slight modification in commodity DRAM structure. The proposed DRAM design, called CoolDRAM, operates using a single extra cell row as reference cells. CoolDRAM reduces energy dissipation by about 34% on average, with a negligible area overhead of about 0.4%. The robustness of CoolDRAM against process variation and environmental noises is 61× and 1.78 × of the state-of-the-art, respectively, while maintaining the same power consumption and latency.

Graphics Processing Units (GPUs) utilize memory hierarchy and Thread-Level Parallelism (TLP) to tolerate off-chip memory latency, which is a significant bottleneck for memory-bound applications. However, parallel threads generate a large number of memory requests, which increases the average memory latency and degrades cache performance due to high contention. Prefetching is an effective technique to reduce memory access latency, and prior research shows the positive impact of stride-based prefetching on GPU performance. However, existing prefetching methods only rely on fixed strides. To address this limitation, this paper proposes a new prefetching technique, Snake, which is built upon chains of variable strides, using throttling and memory decoupling strategies. Snake achieves 80% coverage and 75% accuracy in prefetching demand memory requests, resulting in a 17% improvement in total GPU performance and energy consumption for memory-bound General-Purpose Graphics Processing Unit (GPGPU) applications.

L1 instruction(L1-l) cache misses are a source of performance bottleneck. While many instruction prefetchers have been proposed, most of them leave a considerable potential uncovered. In 2011, Proactive Instruction Fetch (PIF) showed that a hardware prefetcher could effectively eliminate all instruction-cache misses. However, its enormous storage cost makes it impractical. Consequently, reducing the storage cost was the main research focus in instruction prefetching in the past decade. Several instruction prefetchers, including RDIP and Shotgun, were proposed to offer PIF-level performance with significantly lower storage overhead. However, our findings show that there is a considerable performance gap between these proposals and PIF. While these proposals use different mechanisms for prefetching, the performance gap is mainly not because of the mechanism, and instead, is due to not having sufficient storage. We make the case that the key to designing a powerful and cost-effective instruction prefetcher is choosing a metadata record and microarchitecting the prefetcher to minimize the storage. Our proposal, MANA, offers PIF-level performance with 15.7x lower storage cost. MANA outperforms RDIP and Shotgun by 12.5 and 29%, respectively. We also evaluate a version of MANA with no storage overhead and show that it offers 98% of the peak performance benefits.

To alleviate costly data communication among processing cores and memory modules, parallel processing-in-memory (PIM) is a promising approach which exploits the huge available internal memory bandwidth. High capacity, wide row size, and maturity of DRAM technology, make DRAM an alluring structure for PIM. However, dense layout, high process variation, and noise vulnerability of DRAMs make it very challenging to apply PIM for DRAMs in practice. This work proposes a PIM structure which eliminates these DRAM limitations, exploiting a precharge-free DRAM (PF-DRAM) structure. The proposed PIM structure, called PIPF-DRAM, performs parallel bitwise operations only by modifying control signal sequences in PF-DRAM, with almost zero structural and circuit modifications. Comparing the state-of-the-art PIM techniques, PIPF-DRAM is 4.2× more robust to process variation, 4.1% faster in average cycle time of operations, and consumes 66.1% less energy.

Graphics Processing Units (GPUs) are widely-used accelerators for data-parallel applications. In many GPU applications, GPU memory bandwidth bottlenecks performance, causing underutilization of GPU cores. Hence, disabling many cores does not affect the performance of memory-bound workloads. While simply power-gating unused GPU cores would save energy, prior works attempt to better utilize GPU cores for other applications (ideally compute-bound), which increases the GPU’s total throughput. In this paper, we introduce Morpheus, a new hardware/software co-designed technique to boost the performance of memory-bound applications. The key idea of Morpheus is to exploit unused core resources to extend the GPU last level cache (LLC) capacity. In Morpheus, each GPU core has two execution modes: compute mode and cache mode. Cores in compute mode operate conventionally and run application threads. However, for the cores in cache mode, Morpheus invokes a software helper kernel that uses the cores’ on-chip memories (i.e., register file, shared memory, and L1) in a way that extends the LLC capacity for a running memory-bound workload. Morpheus adds a controller to the GPU hardware to forward LLC requests to either the conventional LLC (managed by hardware) or the extended LLC (managed by the helper kernel). Our experimental results show that Morpheus improves the performance and energy efficiency of a baseline GPU architecture by an average of 39% and 58%, respectively, across several memory-bound workloads. Morpheus’ performance is within 3% of a GPU design that has a quadruple-sized conventional LLC. Morpheus can thus contribute to reducing the hardware dedicated to a conventional LLC by exploiting idle cores’ on-chip memory resources as additional cache capacity.

Graphics Processing Units (GPUs) employ a shared memory, a software-managed cache for programmers, in each streaming multiprocessor to accelerate data sharing among the threads in a thread block. Although 60% of the shared memory space is underutilized, on average, there are some workloads that demand higher shared memory capacities. Therefore, improving shared memory utilization while satisfying the needs of shared memory intensive workloads is challenging. We make a key observation that the lifetime of each shared memory address is significantly shorter than the execution time of a thread block. In this paper, we first propose Off-Chip Shared Memory (OSM) that allocates shared memory space in the off-chip memory, and accelerates accesses to it via a small on-chip cache. Using an 8 KB cache for shared memory addresses, OSM provides almost the same performance as the baseline GPU that uses 96 KB on-chip shared memory. OSM improves GPU performance in two ways. First, it allocates higher shared memory capacities in the off-chip memory, and improves thread-level parallelism (TLP). Second, it designs a unified cache for shared memory and global address spaces, providing more caching space for global memory address space even for the workloads with high shared memory utilization. Our experimental results show an average 21% and 18% IPC improvement compared to the baseline and the state-of-the-art architectures.

Modern computing devices employ High-Bandwidth Memory (HBM) to meet their memory bandwidth requirements. An HBM-enabled device consists of multiple DRAM layers stacked on top of one another next to a compute chip (e.g. CPU, GPU, and FPGA) in the same package. Although such HBM structures provide high bandwidth at a small form factor, the stacked memory layers consume a substantial portion of the package's power budget. Therefore, power-saving techniques that preserve the performance of HBM are desirable. Undervolting is one such technique: it reduces the supply voltage to decrease power consumption without reducing the device's operating frequency to avoid performance loss. Undervolting takes advantage of voltage guardbands put in place by manufacturers to ensure correct operation under all environmental conditions. However, reducing voltage without changing frequency can lead to reliability issues manifested as unwanted bit flips. In this paper, we provide the first experimental study of real HBM chips under reduced-voltage conditions. We show that the guardband regions for our HBM chips constitute 19% of the nominal voltage. Pushing the supply voltage down within the guardband region reduces power consumption by a factor of 1.5X for all bandwidth utilization rates. Pushing the voltage down further by 11% leads to a total of2.3X power savings at the cost of unwanted bit flips. We explore and characterize the rate and types of these reduced-voltage-induced bit flips and present a fault map that enables the possibility of a three-factor trade-off among power, memory capacity, and fault rate.

Although DRAM capacity and bandwidth have increased sharply by the advances in technology and standards, its latency and energy per access have remained almost constant in recent generations. The main portion of DRAM power/energy is dissipated by Read, Write, and Refresh operations, all initiated by a Precharge phase. Precharge phase not only imposes a large amount of energy consumption, but also increases the delay of closing a row in a memory block to open another one. By reduction of row-hit rate in recent workloads, especially in multi-core systems, precharge rate increases which exacerbates DRAM power dissipation and access latency. This work proposes a novel DRAM structure, called Precharge-Free DRAM (PF-DRAM), that eliminates the Precharge phase of DRAM. PF-DRAM uses the charge on bitlines from the previous Activation phase, as the starting point for the next Activation. The difference between PF-DRAM and conventional DRAM structure is limited to precharge and equalizer circuitry and simple modifications in sense amplifier, which are all limited to subarray level. PF-DRAM is compatible with the mainstream JEDEC memory standards like DDRx and HBM, with minimum modifications in memory controller. Furthermore, almost all of the previously proposed power/energy reduction techniques in DRAM are still applicable to PF-DRAM for further improvement. Our experimental results on a 8GB memory system running SPEC CPU2017 and PARSEC2.1 workloads show an average of 35.3% memory power consumption reduction (up to 54.2%) achieved by the system using PF-DRAM with respect to the system using conventional DRAM. Moreover, the overall performance is improved by 8.6%, in average (up to 24.3%). According to our analysis, all such improvements are achieved for less than 9% area overhead.

Stencil codes (a.k.a. nearest-neighbor computations) are widely used in image processing, machine learning, and scientific applications. Stencil codes incur nearest-neighbor data exchange because the value of each point in the structured grid is calculated as a function of its value and the values of a subset of its nearest-neighbor points. When running on Graphics Processing Unit (GPUs), stencil codes exhibit a high degree of data sharing between nearest-neighbor threads. Sharing is typically implemented through shared memories, shuffle instructions, and on-chip caches and often incurs performance overheads due to the redundancy in memory accesses. In this article, we propose Neighbor Data (NeDa), a direct nearest-neighbor data sharing mechanism that uses two registers embedded in each streaming processor (SP) that can be accessed by nearest-neighbor SP cores. The registers are compiler-allocated and serve as a data exchange mechanism to eliminate nearest-neighbor shared accesses. NeDa is embedded carefully with local wires between SP cores so as to minimize the impact on density. We place and route NeDa in an open-source GPU and show a small area overhead of 1.3%. The cycle-accurate simulation indicates an average performance improvement of 21.8% and power reduction of up to 18.3% for stencil codes in General-Purpose Graphics Processing Unit (GPGPU) standard benchmark suites. We show that NeDa’s performance is within 13.2% of an ideal GPU with no overhead for nearest-neighbor data exchange.

We empirically evaluate an undervolting technique, i.e., underscaling the circuit supply voltage below the nominal level, to improve the power-efficiency of Convolutional Neural Network (CNN) accelerators mapped to Field Programmable Gate Arrays (FPGAs). Undervolting below a safe voltage level can lead to timing faults due to excessive circuit latency increase. We evaluate the reliability-power trade-off for such accelerators. Specifically, we experimentally study the reduced-voltage operation of multiple components of real FPGAs, characterize the corresponding reliability behavior of CNN accelerators, propose techniques to minimize the drawbacks of reduced-voltage operation, and combine undervolting with architectural CNN optimization techniques, i.e., quantization and pruning. We investigate the effect ofenvironmental temperature on the reliability-power trade-off of such accelerators. We perform experiments on three identical samples of modern Xilinx ZCU102 FPGA platforms with five state-of-the-art image classification CNN benchmarks. This approach allows us to study the effects of our undervolting technique for both software and hardware variability. We achieve more than 3X power-efficiency (GOPs/W ) gain via undervolting. 2.6X of this gain is the result of eliminating the voltage guardband region, i.e., the safe voltage region below the nominal level that is set by FPGA vendor to ensure correct functionality in worst-case environmental and circuit conditions. 43% of the power-efficiency gain is due to further undervolting below the guardband, which comes at the cost of accuracy loss in the CNN accelerator. We evaluate an effective frequency underscaling technique that prevents this accuracy loss, and find that it reduces the power-efficiency gain from 43% to 25%.

The frontend stalls caused by instruction and BTB misses are a significant source of performance degradation in server processors. Prefetchers are commonly employed to mitigate frontend bottleneck. However, next-line prefetchers, which are available in server processors, are incapable of eliminating a considerable number of L1 instruction misses. Temporal instruction prefetchers, on the other hand, effectively remove most of the instruction and BTB misses but impose significant area overhead.Recently, an old idea of using BTB-directed instruction prefetching is revived to address the limitations of temporal instruction prefetchers. While this approach leads to prefetchers with low area overhead, it requires significant changes to the frontend of a processor. Moreover, as this approach relies on the BTB content for prefetching, BTB misses stall the prefetcher, and likely lead to costly instruction misses. Especially as instruction misses are usually more expensive than BTB misses, the dependence of instruction prefetching to the BTB content is harmful to workloads with very large instruction footprints. Moreover, BTB-directed instruction prefetchers, as proposed in prior work, cannot be applied to variable-length ISAs.In this work, we showcase the harmful effects of making instruction prefetchers depend on the BTB content. Moreover, we divide the frontend bottleneck into three categories and use a divide-and-conquer approach to propose simple and effective solutions for each one. Sequential misses can be covered by an accurate and timely sequential prefetcher named SN4L, a lightweight discontinuity prefetcher named Dis eliminates discontinuity misses, and the BTB misses are reduced by pre-decoding the prefetched blocks. We also discuss how our proposal can be used for variable-length ISAs with low storage overhead. Our proposal, SN4L+ Dis+BTB, imposes the same area overhead as the state-of-the-art BTB-directed prefetcher, and at the same time, outperforms it by 5% on average and up to 16%.

Applications extensively use data objects with a regular and fixed layout, which leads to the recurrence of access patterns over memory regions. Spatial data prefetching techniques exploit this phenomenon to prefetch future memory references and hide the long latency of DRAM accesses. While state-of-the-art spatial data prefetchers are effective at reducing the number of data misses, we observe that there is still significant room for improvement. To select an access pattern for prefetching, existing spatial prefetchers associate observed access patterns to either a short event with a high probability of recurrence or a long event with a low probability of recurrence. Consequently, the prefetchers either offer low accuracy or lose significant prediction opportunities. We identify that associating the observed spatial patterns to just a single event significantly limits the effectiveness of spatial data prefetchers. In this paper, we make a case for associating the observed spatial patterns to both short and long events to achieve high accuracy while not losing prediction opportunities. We propose Bingo spatial data prefetcher in which short and long events are used to select the best access pattern for prefetching. We propose a storage-efficient design for Bingo in such a way that just one history table is needed to maintain the association between the access patterns and the long and short events. Through a detailed evaluation of a set of big-data applications, we show that Bingo improves system performance by 60% over a baseline with no data prefetcher and 11% over the best-performing prior spatial data prefetcher.

Graphics Processing Units (GPUs) are widely used as the accelerator of choice for applications with massively data-parallel tasks. However, recent studies show that GPUs suffer heavily from resource underutilization, which, combined with their large static power consumption, imposes a significant power overhead. One of the most power-hungry components of a GPU—the execution units—frequently experience idleness when (1) an underutilized warp is issued to the execution units, leading to partial lane idleness, and (2) there is no active warp to be issued for the execution due to warp stalls (e.g., waiting for memory access and synchronization). Although large in total, the idle time of execution units actually comes from short but frequent stalls, leaving little potential for common power saving techniques, such as power-gating. In this article, we propose ITAP , a novel idle-time-aware power management technique, which aims to effectively reduce the static energy consumption of GPU execution units. By taking advantage of different power management techniques (i.e., power-gating and different levels of voltage scaling), ITAP employs three static power reduction modes with different overheads and capabilities of static power reduction. ITAP estimates the idle period length of execution units using prediction and peek-ahead techniques in a synergistic way and then applies the most appropriate static power reduction mode based on the estimated idle period length. We design ITAP to be power-aggressive or performance-aggressive, not both at the same time. Our experimental results on several workloads show that the power-aggressive design of ITAP outperforms the state-of-the-art solution by an average of 27.6% in terms of static energy savings, with less than 2.1% performance overhead. However, the performance-aggressive design of ITAP improves the static energy savings by an average of 16.9%, while keeping the GPU performance almost unaffected (i.e., up to 0.4% performance overhead) compared to the state-of-the-art static energy savings mechanism.

Triple Modular Redundancy (TMR) is a historical and long-time-used approach for masking various kinds of faults. By employing redundancy and analyzing the results of three separate executions of the same program, TMR is able to attain excellent levels of reliability. While TMR provides a desirable level of reliability, it suffers from the high power consumption of the redundant hardware, a severe detriment to its broad adoption. The energy consumption of TMR can be mitigated if its operations are divided into two stages, and one stage is dropped in the absence of fault. Such an approach, which is evaluated in recent research, however, quickly fails in the presence of permanent faults, as we show in this paper. In this work, we introduce Reactive TMR, a novel energy-efficient approach for tolerating both transient and permanent faults. The key idea is to detect and deactivate faulty components and re-assign their tasks to functioning ones. Using a combination of static scheduling and dynamic task-management, our method decouples tasks from cores that are susceptible to result in a faulty execution; hence, it instinctively tolerates permanent faults and improves both reliability and energy-efficiency. Through a detailed evaluation, we show that our proposal reduces the energy consumption of baseline TMR by 30 percent while preserving its reliability. As compared to the state-of-the-art proposal for TMR, our method, while maintaining the energy consumption, augments hard-fault-tolerance to the system.

Graphics Processing Units (GPUs) employ large register files to accommodate all active threads and accelerate context switching. Unfortunately, register files are a scalability bottleneck for future GPUs due to long access latency, high power consumption, and large silicon area provisioning. Prior work proposes hierarchical register file to reduce the register file power consumption by caching registers in a smaller register file cache. Unfortunately, this approach does not improve register access latency due to the low hit rate in the register file cache. In this article, we propose the Latency-Tolerant Register File (LTRF) architecture to achieve low latency in a two-level hierarchical structure while keeping power consumption low. We observe that compile-time interval analysis enables us to divide GPU program execution into intervals with an accurate estimate of a warp’s aggregate register working-set within each interval. The key idea of LTRF is to prefetch the estimated register working-set from the main register file to the register file cache under software control, at the beginning of each interval, and overlap the prefetch latency with the execution of other warps. We observe that register bank conflicts while prefetching the registers could greatly reduce the effectiveness of LTRF. Therefore, we devise a compile-time register renumbering technique to reduce the likelihood of register bank conflicts. Our experimental results show that LTRF enables high-capacity yet long-latency main GPU register files, paving the way for various optimizations. As an example optimization, we implement the main register file with emerging high-density high-latency memory technologies, enabling 8× larger capacity and improving overall GPU performance by 34%.

Non-Volatile Memory (NVM) technology is a promising solution to fulfill the ever-growing need for higher capacity in the main memory of modern systems. Despite having many great features, however, NVM’s poor write performance remains a severe obstacle, preventing it from being used as a DRAM alternative in the main memory. Most of the prior work targeted optimizing writes at the main memory side and neglected the decisive role of upper-level cache management policies on reducing the number of writes. In this article, we propose a novel cache management policy that attempts to maximize write-coalescing in the on-chip SRAM last-level cache (LLC) for the sake of reducing the number of costly writes to the off-chip NVM. We decouple a few physical ways of the LLC to have a dedicated and exclusive storage for the dirty blocks after being evicted from the cache and before being sent to the off-chip memory. By displacing dirty blocks in exclusive storage, they are kept in the cache based on their rewrite distance and are evicted when they are unlikely to be reused shortly. To maximize the effectiveness of exclusive storage, we manage it as a Cuckoo Cache to offer associativity based on the various applications’ demands. Through detailed evaluations targeting various single- and multi-threaded applications, we show that our proposal reduces the number of writebacks by 21%, on average, over the state-of-the-art method and enhances both performance and energy efficiency.

Graphics Processing Units (GPUs) employ large register files to accommodate all active threads and accelerate context switching. Unfortunately, register files are a scalability bottleneck for future GPUs due to long access latency, high power consumption, and large silicon area provisioning. Prior work proposes hierarchical register file, to reduce the register file power consumption by caching registers in a smaller register file cache. Unfortunately, this approach does not improve register access latency due to the low hit rate in the register file cache. In this paper, we propose the Latency-Tolerant Register File (LTRF) architecture to achieve low latency in a two-level hierarchical structure while keeping power consumption low. We observe that compile-time interval analysis enables us to divide GPU program execution into intervals with an accurate estimate of a warp's aggregate register working-set within each interval. The key idea of LTRF is to prefetch the estimated register working-set from the main register file to the register file cache under software control, at the beginning of each interval, and overlap the prefetch latency with the execution of other warps. Our experimental results show that LTRF enables high-capacity yet long-latency main GPU register files, paving the way for various optimizations. As an example optimization, we implement the main register file with emerging high-density high-latency memory technologies, enabling 8X larger capacity and improving overall GPU performance by 31% while reducing register file power consumption by 46%.

Big-data server applications frequently encounter data misses, and hence, lose significant performance potential. One way to reduce the number of data misses or their effect is data prefetching. As data accesses have high temporal correlations, temporal prefetching techniques are promising for them. While state-of-the-art temporal prefetching techniques are effective at reducing the number of data misses, we observe that there is a significant gap between what they offer and the opportunity. This work aims to improve the effectiveness of temporal prefetching techniques. We identify the lookup mechanism of existing temporal prefetchers responsible for the large gap between what they offer and the opportunity. Existing lookup mechanisms either not choose the right stream in the history, or unnecessarily delay the stream selection, and hence, miss the opportunity at the beginning of every stream. In this work, we introduce Domino prefetching to address the limitations of existing temporal prefetchers. Domino prefetcher is a temporal data prefetching technique that logically looks up the history with both one and two last miss addresses to find a match for prefetching. We propose a practical design for Domino prefetcher that employs an Enhanced Index Table that is indexed by just a single miss address. We show that Domino prefetcher captures more than 90% of the temporal opportunity. Through detailed evaluation targeting a quad-core processor and a set of server workloads, we show that Domino prefetcher improves system performance by 16% over the baseline with no data prefetcher and 6% over the state-of- the-art temporal data prefetcher.

Phase Change Memory (PCM) is one of the most promising candidates to be used at the main memory level of the memory hierarchy due to poor scalability, considerable leakage power, and high cost/bit of DRAM. PCM is a new resistive memory that is capable of storing data based on resistance values. The wide resistance range of PCM allows for storing multiple bits per cell (MLC) rather than a single bit per cell (SLC). Unfortunately, higher density of MLC PCM comes at the expense of longer read/write latency, higher soft error rate, higher energy consumption, and earlier wearout compared to the SLC PCM. Some studies suggest removing the most error-prone level to mitigate soft error and write latency of MLC PCM, hence introducing a less dense memory called Tri-Level memory. Another scheme, called M-Metric, proposes a new read metric to address the soft error problem in MLC PCM. In order to deal with the limited lifetime of PCM, some extra storage per memory line is required to correct permanent hard errors (stuck-at faults). Since the extra storage is used only when permanent faults occur, it has a low utilization for a long time before hard errors start to occur. In this article, we utilize the extra storage to improve the read/write latency in a 2-bit MLC PCM using a relaxation scheme for reading and writing the cells for intermediate resistance levels. More specifically, we combine the most time-consuming levels (intermediate resistance levels) to reduce the number of resistance levels (making a Tri-Level PCM) and therefore improve write latency. We then store some error correction metadata in the extra storage section to successfully retrieve the exact data values in the read operation. We also modify the Tri-Level PCM cell to increase its read latency when the M-Metric scheme is used. Evaluation results show that the proposed scheme improves read latency by 57.2%, write latency by 56.1%, and overall system performance (IPC) by 26.9% over the baseline. It is noteworthy that combining the proposed scheme and FPC compression method improves read latency by 75.2%, write latency by 67%, and overall system performance (IPC) by 37.4%.

Server workloads operate on large volumes of data. As a result, processors executing these workloads encounter frequent L1-D misses. In a many-core processor, an L1-D miss causes a request packet to be sent to an LLC slice and a response packet to be sent back to the L1-D, which results in high overhead. While prior work targeted response packets, this work focuses on accelerating the request packets. Unlike aggressive OoO cores, simpler cores used in many-core processors cannot hide the latency of L1-D request packets. We observe that LLC slices that serve L1-D misses are strongly temporally correlated. Taking advantage of this observation, we design a simple and accurate predictor. Upon the occurrence of an L1-D miss, the predictor identifies the LLC slice that will serve the next L1-D miss and a circuit will be set up for the upcoming miss request to accelerate its transmission. When the upcoming miss occurs, the resulting request can use the already established circuit for transmission to the LLC slice. We show that our proposal outperforms data prefetching mechanisms in a many-core processor due to (1) higher prediction accuracy and (2) not wasting valuable off-chip bandwidth, while requiring significantly less overhead. Using full-system simulation, we show that our proposal accelerates serving data misses by 22 percent and leads to 10 percent performance improvement over the state-of-the-art network-on-chip.

Advances in semiconductor technology enable integrating tens of cores on a single chip. Providing quality-of-service (QoS) for communication flows in complex embedded applications is critical. In this paper, we present a new approach for designing guaranteed service (GS) networks-on-chip by introducing a new arbitration algorithm and differentiating high and low priority traffic flows in best-effort (BE) networks. An analytical model is provided to compute accurate performance bound parameters in the network with the new arbitration. When the flows have the same priorities in a switch, the new algorithm acts exactly the same as the basic round robin arbitration. It works as a superset of the basic algorithm, when the flows have different priorities. The proposed method helps designers to easily equip traditional BE networks with effective hard QoS, changing it to a GS network. This is done without the need to get involved in the designing complexity of traditional GS networks and still benefit from the superior properties of BE networks. We show substantial improvement in performance bounds for high priority flows (more than 40% in delay and 80% in bandwidth, on average) compared to the known approaches.

In the era of big data, the capability of computer systems must be enhanced to support 2.5 quintillion byte/day data delivery. Among the components of a computer system, main memory has a great impact on overall system performance. DRAM technology has been used over the past four decades to build main memories. However, the scalability of DRAM technology has faced serious challenges. To keep pace with the ever-increasing demand for larger main memory, some new alternative technologies have been introduced. Phase change memory (PCM) is considered as one of such technologies for substituting DRAM. PCM offers some noteworthy properties such as low static power consumption, nonvolatility, and capability of storing more than one bit per cell (multilevel cell, or MLC). However, the short lifetime and long access latency of PCM (specifically MLC PCM) require feasible and efficient solutions. In this article, based on the observation that applications access a significant number of read-friendly data blocks, we propose Express Read to prevent the MLC PCM read circuit to spend unnecessary time sensing the cells of a memory block. A read-friendly data block (RFDB) is composed of only “11” and “00” bit pairs, and thus upon sensing the most significant bit of a cell, the read operation can be early terminated to reduce the MLC read time and power consumption. Moreover, we increase the number of RFDBs using two simple techniques to better exploit the benefits of Express Read. Results obtained from full-system simulation near 6% performance improvement and 21% energy gain, on average, over the baseline system.

The energy consumption for processing modern workloads is challenging in data centers. Due to the large datasets of cloud workloads, the miss rate of the L1 data cache is high, and with respect to the energy efficiency concerns, such misses are costly for memory instructions because lower levels of memory hierarchy consume more energy per access than the L1. Moreover, large last-level caches are not performance effective, in contrast to traditional scientific workloads. The aim of this article is to propose a large L1 data cache, called Domino, to reduce the number of accesses to lower levels in order to improve the energy efficiency. In designing Domino, we focus on two components that use the on-chip area and are not energy efficient, which makes them good candidates to use their area for enlarging the L1 data cache. Domino is a highly associative cache that extends the conventional cache by borrowing the prefetcher and last-level-cache storage budget and using it as additional ways for data cache. In Domino, the additional ways are separated from the conventional cache ways; hence, the critical path of the first access is not altered. On a miss in the conventional part, it searches the added ways in a mix of parallel-sequential fashion to compromise the latency and energy consumption. Results on the Cloudsuite benchmark suite show that read and write misses are reduced by 30%, along with a 28% reduction in snoop messages. The overall energy consumption per access is then reduced by 20% on average (maximum 38%) as a result of filtering accesses to the lower levels.

CPU-GPU heterogeneous systems are emerging are emerging as architectures of choice for high-performance energy-efficient computing. Designing on-chip interconnects for such systems is challenging: CPUs typically benefit greatly from optimizations that reduce latency, but rarely saturate bandwidth or queueing resources. In contrast, GPUs generate intense traffic that produces local congestion, harming CPU performance. Congestion-optimized interconnects can mitigate this problem through larger virtual and physical channel resources. However, when there is little traffic, such networks become suboptimal due to higher unloaded packet latencies and critical path delays. We argue for a reconfigurable network that can activate additional channels under high load/congestion and shut them off when the network is unloaded. However, these additional resources consume more power, making it difficult to statically provision a power budget for the network. We propose Elastic Network Reconfiguration, wherein we aggressively reduce voltage to free power budget to activate additional channels. Our key observation is that, under high load, the reduced queueing due to additional channels more than compensates for the increase in per-hop latency of the reduced clock frequency. We introduce BiNoCHS as a voltage-scalable NoC that specifically targets CPU-GPU heterogeneous systems and employs elastic network reconfiguration to maintain a constant power budget while adapting between latency- and congestion-optimized modes.

The placement of the Last Level Cache (LLC) banks in the GPU on-chip network can significantly affect the performance of memory-intensive workloads. In this paper, we attempt to offer a placement methodology for the LLC banks to maximize the performance of the on-chip network connecting the LLC banks to the streaming multiprocessors in GPUs. We argue that an efficient placement needs to be derived based on a novel metric that considers the latency hiding capability of the GPUs through thread level parallelism. To this end, we propose a throughput aware metric, called Effective Latency Impact (ELI). Moreover, we define an optimization problem to formulate our placement approach based on the ELI metric mathematically. To solve this optimization problem, we deploy a heuristic solution as this optimization problem is NP-hard. Experimental results show that our placement approach improves the performance by up to 15.7% compared to the state-of-the-art placement.

Server workloads benefit from execution on many-core processors due to their massive request-level parallelism. A key characteristic of server workloads is the large instruction footprints. While a shared last-level cache (LLC) captures the footprints, it necessitates a low-latency network-on-chip (NOC) to minimize the core stall time on accesses serviced by the LLC. As strict quality-of-service requirements preclude the use of lean cores in server processors, we observe that even state-of-the-art single-cycle multi-hop NOCs are far from ideal because they impose significant NOC-induced delays on the LLC access latency, and diminish performance. Most of the NOC delay is due to per-hop resource allocation. In this paper, we take advantage of proactive resource allocation (PRA) to eliminate per-hop resource allocation time in single-cycle multi-hop networks to reach a near-ideal network for servers. PRA is undertaken during (1) the time interval in which it is known that LLC has the requested data, but the data is not yet ready, and (2) the time interval in which a packet is stalled in a router because the required resources are dedicated to another packet. Through detailed evaluation targeting a 64-core processor and a set of server workloads, we show that our proposal improves system performance by 12% over the state-of-the-art single-cycle multi-hop mesh NOC.

Main burdens to the DRAM scalability are leakage and charge storage restrictions. Phase Change Memory (PCM) is being known as a promising candidate for the replacement of DRAM among competitive non-volatile memories. However, this memory suffers from low cell reliability due to limited write endurance. This problem can lead to some memory cells permanently stuck at either '0' or '1'. Therefore, a robust error recovery scheme is needed to overcome this problem and recover from hard errors. State-of-the-art solutions apply error correction and recovery techniques at inter- line or intra-line level. Precisely, they can improve PCM endurance either by remapping failed lines to spares (in inter-line level schemes) or by using data-block partitioning and bit- inversion scheme (in intra-line level schemes). Although techniques of the latter type are effective, proper partitioning of data blocks and spreading out faults across different groups are required. In this paper, we propose and evaluate a novel intra-line level scheme that statically partition a data-block into some groups and efficiently recover multi-bit stuck-at faults per partition. This method benefits from the advantage of a simple shifting mechanism in order to increase the chance of storing data in presence of failed cells. Evaluation results for multi- threaded workloads show enhancement in the number of recoverable failures and improvement of lifetime over existing techniques.

CPU-GPU heterogeneous systems are emerging as architectures of choice for high-performance energy-efficient computing. Designing on-chip interconnects for such systems is challenging; CPUs typically benefit greatly from optimizations that reduce latency, but rarely saturate bandwidth or queueing resources. In contrast, GPUs generate intense traffic that produces local congestion, harming CPU performance. Congestion-optimized interconnects can mitigate this problem through larger virtual and physical channel resources. However, when there is little traffic, such networks become suboptimal due to higher unloaded packet latencies and critical path delays. We argue for a reconfigurable network that can activate additional channels under high load/congestion and shut them off when the network is unloaded. However, these additional resources consume more power, making it difficult to statically provision a power budget for the network. We introduce BiNoCHS, a reconfigurable voltage-scalable on-chip network for heterogeneous systems. Under CPU-dominated low-traffic conditions, BiNoCHS operates at nominal-voltage and high clock frequency with a topology optimized for low hop count, maximizing CPU performance. Under high-traffic GPU and mixed workloads, it transitions to a near-threshold mode, activating additional routers/channels and non-minimal adaptive routing to resolve congestion. Our evaluation shows that BiNoCHS improves CPU/GPU performance by 57% / 34% over a latency-optimized network under congested conditions, while improving CPU performance by 28% over high-bandwidth design in unloaded conditions.

Emerging non-volatile memories (NVMs) are notable candidates for replacing traditional DRAMs. Although NVMs are scalable, dissipate lower power, and do not require refreshes, they face new challenges including shorter lifetime and security issues. Efforts toward securing the NVMs against probe attacks pose a serious downside in terms of lifetime. Cryptography algorithms increase the information density of data blocks and consequently handicap the existing lifetime enhancement solutions like Flip-N-Write. In this paper, based on the insight that compression can relax the constraints of lifetime-security trade-off, we propose CryptoComp, an architecture that, taking the advantage of block size reduction after compression, aims to enhance the memory system lifetime and security. Our idea is to limit the avalanche effect caused by encryption algorithms in a lower space through compression and selective encryption. This way, for highly compressible data blocks, we follow a fully-encryption approach while for poorly compressible data blocks, we rely on a non-deterministic fine-grain selective-encryption mechanism. Additionally, a simple and block-oriented wear-leveling scheme is presented to fairly distribute the bit flips on memory cells. Our experimental results show 3.59$\times$and 3.66$\times$lifetime improvements over two state-of-the-art schemes, DEUCE and i-NVMM, while imposing a negligible performance degradation of 2.1 percent, on average.

The failure of Dennard scaling has led to the utilization wall that is the source of dark silicon and limits the percentage of a chip that can actively switch within a given power budget. To address this issue, a structure is needed to guarantee the limited power budget along with providing sufficient flexibility and performance for different applications with various communication requirements. In this article, we present a general-purpose platform for future many-core Chip-Multiprocessors (CMPs) that benefits from the advantages of clustering, Network-on-Chip (NoC) resource sharing among cores, and power gating the unused components of clusters. We also propose two task mapping methods for the proposed platform in which active and dark cores are dispersed appropriately, so that an excess of power budget can be obtained. Our evaluations reveal that the first and second proposed mapping mechanisms respectively reduce the execution time by up to 28.6% and 39.2% and the NoC power consumption by up to 11.1% and 10%, and gain an excess power budget of up to 7.6% and 13.4% over the baseline architecture.

Limited endurance problem and low cell reliability are main challenges of phase change memory (PCM) as an alternative to DRAM. To further prolong the lifetime of a PCM device, there exist a number of techniques that can be grouped in two categories: 1) reducing the write rate to PCM cells, and 2) handling cell failures when faults occur. Our experiments confirm that during write operations, an extensive non-uniformity in bit ips is exhibited. To reduce this non-uniformity, we present byte-level shifting scheme (BLESS) which reduces write pressure over hot cells of blocks. Additionally, this shifting mechanism can be used for error recovery purpose by using the MLC capability of PCM and manipulating the data block to recover faulty cells. Evaluation results for multi-threaded workloads reveal 14-25% improvement in lifetime over existing state-of-the-art schemes.

Modern computer systems require fast, large and reliable memories to handle information explosion. With this goal in mind, not only deployment of main memories with new technologies are necessary, but also adopting innovative solutions for addressing newfound challenges must be considered as a priority. Recently, phase change memory (PCM) appeared as a preferred candidate for substituting DRAM. PCM with non-volatility, low static power consumption and storing multiple level cells (MLC) capability has opened a new way to the future of memories. Although PCM presents considerable potentials, its short lifetime is a critical concern. Worse still, adopting multiple bits per cell capability degrades the lifetime of PCM more quickly. Hence, convincing the industry for massive production of PCM needs effective and pragmatic solutions. In this paper, we extend the lifetime of a MLC PCM main memory by relying on two strategies: postponing the occurrence of stuck-at failures, and effectively tolerating hard errors. Our scheme postpones the occurrence of hard errors by converting blocks from MLC to SLC mode using byte-level compression. Employing some pointers, the proposed method attempts to cover hard errors by fitting a compressed block either in its physical line location or elsewhere in the page. Full-system and statistical evaluation of the proposed solution shows 48% lifetime improvement of the memory system along with 9% IPC improvement, compared to a state-of-the-art design.

The continuance of Moore's law and failure of Dennard scaling force future chip multiprocessors (CMPs) to have considerable dark regions. How to use up available dark resources is an important concern for computer architects. In harmony with these changes, we must revise processor allocation schemes that severely affect the performance of a parallel on-chip system. A suitable allocation algorithm should reduce runtime and increase the power efficiency with proper thermal distribution to avoid hotspots. With this motivation, this paper proposes a power-efficient and high performance general purpose infrastructure for which a Dark Silicon Aware Processor Allocation (DSAPA) scheme is proposed which targets future many-core systems. To obtain high performance, we suggest a tunable-clustered mesh with the capability of sharing NoC resources in each cluster. We also employ a buffer-level power gating technique is used to improve power efficiency. Evaluation results reveal that the maximum achieved performance and power consumption improvements are 38.7% and 29.4% for multi-threaded workloads over the equivalent conventional design.

This paper quantifies the difference in resource demand between modern and classic NoC workloads. In the paper, we show that modern workloads are able to better utilize higher numbers of VCs and smaller C factors in order to attain performance and energy efficiency. This is because of the high throughput and possible local congestions in their traffic pattern. As a result, such workloads are more suitable for concurrency and redundancy energy reduction techniques where the voltage and frequency are reduced simultaneously and the increased power budget is used for introducing additional resources to the network in order to improve the performance.

Execution units in GPGPU consume much static power. However, reducing the static power of execution units is not clear based on two reasons. First, the very long idle time of execution units in GPGPU is fragmented in to many short periods. Second, these units are very critical to total performance. In this paper, we propose a method to reduce the static power without any performance overhead. We utilize out-of-order execution of instructions to make the idle period of execution units much longer. Experimental results show that our proposal improves over the state-of-the-art in terms of power and performance by 25% and 8%, on average, respectively.

Adaptive routing algorithms help balancing the resource utilization in different parts of the network and hence, prevent a resource becoming the performance bottleneck while other resources are still under-utilized. In this paper, we present a novel approach, called Preemptive Waiting, which is applied to Odd-Even routing algorithm (PWOE). PWOE postpones the saturation traffic rate of NoC by 13.4% compared to OE, under synthetic traffic loads.

Emerging cloud workloads in today's modern data centers have large memory footprints that make the processor's caches to be ineffective. Since L1 data cache is in the critical path, high data cache miss rates degrade the performance. To fix the issue in traditional workloads, data prefetchers predict the needed data to hide the memory latency and ultimately improve performance. In this paper, we focus on the L1 data cache to answer the question on why state-of-the-art prefetching methods are inefficient for modern workloads in terms of performance and energy consumption? This is because L1 cache is the most important player affecting the processor performance. Results show that, on the one hand, these workloads suffer from low temporal locality and address repetition, and their consecutive accesses exhibit better spatial locality compared with the traditional workloads. On the other hand, miss patterns are spatially irregular and there is little opportunity to eliminate repetitive miss patterns. Because of these reasons, prefetching methods have poor performance and, with respect to more accesses to the lower memory levels, it is not energy efficient to use prefetchers for modern workloads.

Phase Change Memory (PCM) devices are one of the known promising technologies to take the place of DRAM devices with the aim of overcoming the obstacles of reducing feature size and stopping ever growing amounts of leakage power. In exchange for providing high capacity, high density, and nonvolatility, PCM Multilevel Cells (MLCs) impose high write energy and long latency. Many techniques have been proposed to resolve these side effects. However, read performance issues are usually left behind the great importance of write latency, energy, and lifetime. In this article, we focus on read performance and improve the critical path latency of the main memory system. To this end, we exploit striping scheme by which multiple lines are grouped and lie on a single MLC line array. In order to achieve more performance gain, an adaptive ordering mechanism is used to sort lines in a group based on their read frequency. This scheme imposes large energy and lifetime overheads due to its intensive demand for higher write bandwidth. Thus, we equipped our design with a grouping/pairing write queue to synchronize write-back requests such that all updates to an MLC array occur at once. The design is also augmented by a directional write scheme that takes benefits of the uniformity of accesses to the PCM device—caused by the large DRAM cache—to determine the writing mode (striped or nonstriped). This adaptation to write operations relaxes the energy and lifetime overheads. We improve the read latency of a 2-bit MLC PCM memory by more than 24% (and Instructions Per Cycle (IPC) by about 9%) and energy-delay product by about 20% for a small lifetime degradation of 8%, on average.

The eleven papers in this special section focus on both system- and circuit-level aspects of emerging memory and storage technologies. The overwhelmingly increasing demand for both storage and computation necessitates revisiting the traditional memory subsystems used in processors and storage systems to take advantage of emerging memory technologies. Dynamic Random Access Memory (DRAM) and Static Random Access Memory (SRAM) have been ubiquitously used for decades as main memory and as on-chip cache, respectively. Scaling and power issues of these traditional memory technologies have led to significant investment in emerging memory technologies. On the other hand, fundamental limitations of mechanical disk drives have brought great attention to further explore the design space of solid-state drives (SSDs). The promising features of emerging memory technologies such as low power consumption, increased performance, lower susceptibility to particle strikes, and higher bit density have prompted researchers to seek new organizations in the different memory-hierarchy levels, to propose new circuitry and algorithms to improve performance and reduce power consumption, and to develop new schemes to enhance system reliability.

Chip multiprocessors (CMPs) require a low-latency interconnect fabric network-on-chip (NoC) to minimize processor stall time on instruction and data accesses that are serviced by the last-level cache (LLC). While packet-switched mesh interconnects sacrifice performance of many-core processors due to NoC-induced delays, existing circuit-switched interconnects do not offer lower network delays as they cannot hide the time it takes to set up a circuit. To address this problem, this work introduces CIMA-a hybrid circuit-switched and packet-switched mesh-based interconnection network that affords low LLC access delays at a small area cost. CIMA uses virtual cut-through (VCT) switching for short request packets, and benefits from circuit switching for longer, delay sensitive response packets. While a request is being served by the LLC, CIMA attempts to set up a circuit for the corresponding response packet. By the time the request packet is served and the response gets ready, a circuit has already been prepared, and as a result, the response packet experiences short delay in the network. A detailed evaluation targeting a 64-core CMP running scale-out workloads reveals that CIMA improves system performance by 21 percent over the state-of-the-art hybrid circuit-packet-switched network.

The emergence of new memory technologies provides us with opportunity to enhance the properties of existing memory architectures. One such technology is Phase Change Memory (PCM) which boasts superior scalability, power savings, non-volatility, and a performance competitive to Dynamic Random Access Memory (DRAM). In this paper, we propose a write buffer architecture for Solid-State Drives (SSDs) which attempts to exploit PCM as a DRAM alternative while alleviating its issues such as long write latency, high write energy, and finite endurance. To this end and based on thorough I/O characterization of desktop and enterprise applications, we propose a hybrid DRAM-PCM SSD cache design with an intelligent data movement scheme. This architecture manages to improve energy efficiency while enhancing performance and endurance. To study the design trade-offs between energy, performance, and endurance, we augmented Microsoft's DiskSim SSD model with a detailed hybrid cache using PCM and DRAM parameters from a rigorous survey of device prototypes. We study the design choices of implementing different PCM and DRAM arrays to achieve the best trade-off between energy and performance. The results display up to 77 percent power savings compared to a DRAM cache and up to percent reduction in request response time for a variety of workloads, while greatly improving disk endurance.

Emerging nonvolatile memory technologies, such as spin-transfer torque RAM or resistive RAM, can increase the capacity of the last-level cache (LLC) in a latency and power-efficient manner. These technologies endure 109-1012writes per cell, making a nonvolatile cache (NV-cache) with a lifetime of dozens of years under ideal working conditions. However, nonuniformity in writes to different cache lines considerably reduces the NV-cache lifetime to a few months. Writes to cache lines can be made uniformly by wear-leveling. A suitable wear-leveling for NV-cache should not incur high storage and performance overheads. We propose a novel, simple, and effective wear-leveling technique with negligible performance overhead of <;0.4% for memory-intensive workloads. Our proposal consists of two mechanisms: 1) a wear-leveling mechanism within each cache set that slightly increases main memory write-back traffic and LLC miss rate and 2) a novel technique to reduce cache interset variation which causes minimum interference with normal cache operation. Using these mechanisms, we show that the lifetime of the NV-cache is boosted up to 13× for different cache configurations.

Network-on-Chip (NoC) is a key element in the total power consumption of a chip multiprocessor. Dynamic Voltage Scaling is a promising method for power saving in NoCs since it contributes to reduction in both static and dynamic power consumptions. In this paper, we propose a novel scheme to reduce on-chip network power consumption when the number of Virtual Channels (VCs) with active allocation requests per cycle is less than the number of total VCs. In our method, we introduce a reconfigurable arbitration logic which can be configured to have multiple latencies and hence, multiple slack times. The increased slack times are then used to reduce the supply voltage of the routers in order to reduce the power consumption. By using this method, we manage to save power by up to 45.7% compared to a baseline architecture without any performance loss.

Disk traces are typically used to analyze real-life workloads and for replay-based evaluations. This approach benefits from capturing important details such as varying behavior patterns, bursty activity, and diurnal patterns of system activity, which are often missing from the behavior of workload synthesis tools. However, accurate capture of such details requires recording traces containing long durations of system activity, which are difficult to use for replay-based evaluation. One way of solving the problem of long storage trace duration is the use of disk simulators. While publicly available disk simulators can greatly accelerate experiments, they have not kept up with technological innovations in the field. The variety, complexity, and opaque nature of storage hardware make it very difficult to implement accurate simulators. The alternative, replaying the whole traces on real hardware, suffers from either long run-time or required manual reduction of experimental time, potentially at the cost of reduced accuracy. On the other hand, burstiness, auto-correlation, and complex spatio-temporal properties of storage workloads make the known methods of sampling workload traces less effective.

Networks-on-Chip (NoCs) play a crucial role in the performance of Chip Multi-Processors (CMPs). Routers are one of the main components determining the efficiency of NoCs. As various applications have different communication characteristics and hence, buffering requirements, it is difficult to make proper decisions in this regard in the design time. In this paper, we propose a traffic-aware reconfigurable router which can adapt its buffers structure to the changes in the traffic of the network. Our proposed router manages to achieve up to 18.8% and 44.4% improvements in terms of postponing saturation rate under synthetic traffic patterns, and average packet latency for PARSEC applications, respectively, with respect to the conventional state-of-the-art router.

With current memory scalability challenges, Phase-Change Memory (PCM) is viewed as an attractive replacement to DRAM. The preliminary concern for PCM applicability is its limited write endurance that results in fast wear-out of memory cells. Worse, process variation in the deep-nanometer regime increases the variation in cell lifetime, resulting in an early and sudden reduction in main memory capacity due to the wear-out of a few cells. Recent studies have proposed redirection or correction schemes to alleviate this problem, but all suffer poor throughput or latency. In this article, we show that one of the inefficiency sources in current schemes, even when wear-leveling algorithms are used, is the nonuniform write endurance limit incurred by process variation, that is, when some memory pages have reached their endurance limit, other pages may be far from their limit. In this line, we present a technique that aims to displace a faulty page to a healthy page. This technique, called On-Demand Page Paired PCM (OD3P, for short), when applied at page level, can improve PCM time-to-failure by 20% on average for different multithreaded and multiprogrammed workloads while also improving IPC by 14% on average compared to previous page-level techniques. The comparison between line-level OD3P and previous line-level techniques reveals about 2× improvement of lifetime and performance.

Future GPUs should have larger L2 caches based on the current trends in VLSI technology and GPU architectures toward increase of processing core count. Larger L2 caches inevitably have proportionally larger power consumption. In this article, having investigated the behavior of GPGPU applications, we present an efficient L2 cache architecture for GPUs based on STT-RAM technology. Due to its high-density and low-power characteristics, STT-RAM technology can be utilized in GPUs where numerous cores leave a limited area for on-chip memory banks. They have, however, two important issues, high energy and latency of write operations, that have to be addressed. Low retention time STT-RAMs can reduce the energy and delay of write operations. Nevertheless, employing STT-RAMs with low retention time in GPUs requires a thorough study on the behavior of GPGPU applications. Based on this investigation, we have architectured a two-part STT-RAM-based L2 cache with low-retention (LR) and high-retention (HR) parts. The proposed two-part L2 cache exploits a dynamic threshold regulator (DTR) to efficiently regulate the write threshold for migration of the data blocks from HR to LR, based on the behavior of the applications. Also, a Data and Access type Aware Cache Search mechanism (DAACS) is hired for handling the search of the requested data blocks in two parts of the cache. The STT-RAM L2 cache architecture proposed in this article can improve IPC by up to 171% (20% on average), and reduce the average consumed power by 28.9% compared to a conventional L2 cache architecture with equal on-chip area.

Phase change memory (PCM) has rapidly progressed and surpassed dynamic random-access memory in terms of scalability and standby energy efficiency. While PCM cell size is marching toward the minimum achievable feature size, recent prototypes effectively improve device scalability by storing multiple bits per cell. Unfortunately, the density advantage of multilevel cell (MLC) PCM devices comes at the cost of higher latency and energy consumption as well as low resilience to soft errors because of resistance drift. To address these challenges, we propose variable resistance spectrum MLC PCM (VR-PCM), a simple microarchitectural technique to handle main memory access mechanisms with more efficient drift-aware MLC PCM access operations. VR-PCM relies on the observation that data patterns at various granularities are nonuniformly distributed across memory transactions when running various workloads. Motivated by this observation, VR-PCM reconfigures PCM resistance spectrum partitioning into nonuniform regions that are then assigned to the binary data patterns based on their occurrence frequency. Using full-system evaluation of an MLC PCM main memory with conservative resistance drift model, we show that VR-PCM tailored for high-density MLCs delivers considerable improvements in performance (13.25%), energy (21.2%), and lifetime (1.77 x ), on average.

Solid State Drives (SSDs) have recently emerged as a high speed random access alternative to classical magnetic disks. To date, SSD designs have been largely based on multi-channel bus architecture that confronts serious scalability problems in high-end enterprise SSDs with dozens of flash memory chips and a gigabyte host interface. This forces the community to rapidly change the bus-based inter-flash standards to respond to ever increasing application demands. In this paper, we first give a deep look at how different flash parameters and SSD internal designs affect the actual performance and scalability of the conventional architecture. Our experiments show that SSD performance improvement through either enhancing intra-chip parallelism or increasing the number of flash units is limited by frequent contentions occurred on the shared channels. Our discussion will be followed up by presenting and evaluating a network-based protocol adopted for flash communications in SSDs that addresses design constraints of the multi-channel bus architecture. This protocol leverages the properties of interconnection networks to attain a high performance SSD. Further, we will show and discuss that using this communication paradigm not only helps to obtain better SSD backend latency and throughput, but also to lower the variance of response time compared to the conventional designs. In addition, greater number of flash chips can be added with much less concerns on board-level signal integrity challenges including channels' maximum capacitive load, output drivers' slew rate, and impedance control.

Due to the growing demand for large memories, using emerging technologies such as Phase Change Memories (PCM) are inevitable. PCM with appropriate scalability, power consumption and multiple bits per cell storage capability is a probable candidate for substituting DRAM. Although storing multiple bits per cell seems to be a rational response to large memory demands, there is a significant problem to achieve this goal. Resistance drift problem is an important reliability concern that is coupled to a multi-level cell PCM (MLC PCM) memory system. In this paper, we propose a memory system architecture that, by exploiting the benefits of compression, converts resistance drift prone blocks to drift resilient blocks in order to protect the memory system from resistance drift. Evaluations on a full-system simulator, consisting of a quad-core ALPHA CMP and a banked PCM memory, show that our proposed approach provides up to 9.8× reduction in bit error rate, an average of 8% reduction in energy consumption, and 21% IPC improvement.

Core specialization is a promising solution to the dark silicon challenge. This approach trades off the cheaper silicon area with energy-efficiency by integrating a selection of many diverse application-specific cores into a single billion-transistor multicore chip. Each application then activates the subset of cores that best matches its processing requirements. These cores act as a customized application-specific CMP for the application. Such an arrangement of cores requires some special on-chip inter-core communication treatment to efficiently connect active cores. In this paper, we propose a reconfigurable network-on-chip that leverages the routers of the dark portion of the chip to customize the topology for the powered cores at any time. To this end, routers of the dark parts of the chip are used as bypass switches that can directly connect distant active nodes in the network. Our experimental results show considerable reduction in energy consumption and latency of on-chip communication.

With current memory scalability challenges, Phase Change Memory (PCM) is viewed as an attractive replacement to DRAM. The preliminary concern for PCM applicability is its limited write endurance that is highly affected by process variation in nanometer regime. This increases the variation in cell lifetime resulting in early and sudden reduction in main memory capacity due to wear-out of few cells. When some memory pages reach their endurance limits, other pages may be far from their limits even when using a perfect wear-leveling. Recent studies have proposed redirection or correction schemes to alleviate this problem, but all suffer from poor throughput or latency. On contrary, we present On-Demand Page Paired PCM (OD3P), a technique that mitigates the problem of fast failure of pages by redirecting them onto other healthy pages, leading to gradual capacity degradation. Compared to a state-of-the-art error correction scheme for PCM, our experiments indicated that OD3P can improve PCM time-to-failure and system performance (IPC) by 12% and 14%, respectively, under multi-threaded and multi-programmed workloads.

In this paper, having investigated the behavior of GPGPU applications, we present an efficient L2 cache architecture for GPUs based on STT-RAM technology. With the increase of processing cores count, larger on-chip memories are required. Due to its high density and low power characteristics, STT-RAM technology can be utilized in GPUs where numerous cores leave a limited area for on-chip memory banks. They have however two important issues, high energy and latency of write operations, that have to be addressed. Low data retention time STT-RAMs can reduce the energy and delay of write operations. However, employing STT-RAMs with low retention time in GPUs requires a thorough investigation on the behavior of GPGPU applications based on which the STT-RAM based L2 cache is architectured. The STT-RAM L2 cache architecture proposed in this paper, can improve IPC by more than 100% (16% on average) while reducing the average consumed power by 20% compared to a conventional L2 cache architecture with equal on-chip area.

In this paper, we study the problem of resistance drift in an MLC Phase Change Memory (PCM) and propose a solution to circumvent its thermally-affected accelerated rate in 3D CMPs. Our scheme is based on the observation that instead of alleviating the problem of resistance drift by using large margins or error correction codes, the PCM read circuit can be reconfigured for tolerating most of the resistance drift errors in a dynamic manner. Through detailed characterization of memory access patterns for 22 applications, we propose an efficient mechanism to facilitate such reliable read scheme via tolerating (a) early-cycle resistance drifts by using narrow margins so that considerably saving energy of writes and improving cell endurance, and (b) late-cycle resistance drifts by accurately estimating resistance thresholds that separate states for sensing. Evaluations on a true 3D architecture, consisting of a 4-core CMP and a banked 2-bit PCM memory, show that our proposal provides 106× lower error rate compared to the state-of-the-art designs of PCMs.

Although phase change memory with multi-bit storage capability (known as MLC PCM) offers a good combination of high bit-density and non-volatility, its performance is severely impacted by the increased read/write latency. Regarding read operation, access latency increases almost linearly with respect to cell density (the number of bits stored in a cell). Since reads are latency critical, they can seriously impact system performance. This paper alleviates the problem of slow reads in the MLC PCM by exploiting a fundamental property of MLC devices: the Most-Significant Bit (MSB) of MLC cells can be read as fast as SLC cells, while reading the Least-Significant Bits (LSBs) is slower. We propose Striped PCM (SPCM), a memory architecture that leverages this property to keep MLC read latency in the order of SLC's. In order to avoid extra writes onto memory cells as a result of striping memory lines, the proposed design uses a pairing write queue to synchronize write-back requests associated with blocks that are paired in striping mode. Our evaluation shows that our design significantly improves the average memory access latency by more than 30% and IPC by up to 25% (10%, on average), with a slight overhead in memory energy (0.7%) in a 4-core CMP model running memory-intensive benchmarks.

Network-on-Chip (NoC) paradigm has emerged as a revolutionary methodology to integrate numerous IP blocks on a single chip. The achievable performance of adopting NoCs is constrained by the performance limitation mainly imposed by the metal wires that are the physical realization of communication channels. According to the International Technology Roadmap for Semiconductors (ITRS) report, new interconnect paradigms providing huge bandwidth is in need for future products. The current wired channels have limited bandwidth, and consequently, they limit the performance enhancements that NoC architectures can provide. Optical interconnects are capable of achieving better performance via high-speed high-bandwidth point-to-point connections, if their cost overhead can be mitigated. In this paper, we evaluate the performance of opto-electrical multistage NoC architectures which use a sample-based flow prediction method at hardware level with minimum communication and area overhead to predict heavily communicating flows. Our evaluation of the proposed structure demonstrates its superior functionality in terms of throughput, latency, and energy dissipation with respect to traditional NoC architectures.

In Solid-State Drives (SSDs) with tens of flash chips and highly parallel architecture, we can speed up I/O operations by well-utilizing resources during page allocation. Proposals already exist for using static page allocation which does not balance the IO load and its efficiency depends on access address patterns. To our best knowledge, there have been no research thus far to show what happens if one or more internal resources can be freely allocated regardless of the request address. This paper explores the possibility of using different degrees of dynamism in page allocation and identifies key design opportunities that they present to improve SSD's characteristics.

In this paper, we propose a hybrid packet-circuit switching for networks-on-chip to benefit from the advantages of both switching mechanisms. Integrating circuit and packet switching into a single NoC is achieved by partitioning the link bandwidth and router data-path and control-path elements into two parts and allocating each part to one of the switching methods. In this NoC, during injection in the source node, packets are initially forwarded on the packet-switched sub-network, but keep requesting a circuit towards the destination node. The circuit-switched part, at each cycle, collects the circuit construction requests, performs arbitration among the conflicting requests, and constructs circuits over the unallocated circuit-switched sub-network links. Unlike traditional circuit-switching, the circuit end point in this NoC is not necessarily the packet destination, rather the circuits can be terminated in any intermediate node between the packet source and destination nodes. At that node, the packet may either travel over another circuit (in case of successful circuit request) or continue its path over the packet-switched part. Therefore, packets may switch between the two sub-networks several times during their life-time in the network. Circuit construction is handled by a low-latency and low-cost setup network. To keep the complexity of the circuit construction low, the circuits are restricted to span within a neighborhood of d hops of the requesting node. The experimental results show considerable improvement in energy and latency over a traditional packet-switched NoC.

Real-time (RT) communication support is a critical requirement for many complex embedded applications which are currently targeted to Network-on-chip (NoC) platforms. In this paper, we present novel methods to efficiently calculate worst case bandwidth and latency bounds for RT traffic streams on wormhole-switched NoCs with arbitrary topology. The proposed methods apply to best-effort NoC architectures, with no extra hardware dedicated to RT traffic support. By applying our methods to several realistic NoC designs, we show substantial improvements (more than 30 percent in bandwidth and 50 percent in latency, on average) in bound tightness with respect to existing approaches.

Many classes of applications require Quality of Service (QoS) guarantees from the system interconnect. In Networks-on-Chip (NoC) QoS guarantees usually translate into bandwidth and latency constraints for the traffic flows and require hardware support in the NoC fabric and its interfaces. In this article we present a novel NoC synthesis framework to automatically build networks that meet hard latency constraints of end-to-end traffic streams without requiring specialized hardware for the network components. The hard latency constraints are met by carefully designing the NoC topology and selecting the appropriate routes for flow using lean best-effort network components. We perform experiments on several System on Chip (SoC) benchmarks. We compared against a topology synthesis method with no support for real-time constraints and we show that the proposed method can produce topologies that can meet significantly tighter worst case latency constraints (on average 44%). We also show that the tightest worst case latency can be provided with little overhead on power consumption (on average 8.5%).

In this paper, we propose a reconfigurable NoC in which a customized topology for a given application can be implemented. In this NoC, the nodes are grouped into some clusters interconnected by a reconfigurable communication infrastructure. The nodes inside a cluster are connected by a fixed topology. From the traffic management perspective, this structure benefits from the interesting characteristics of the mesh topology (efficient handling of local traffic where each node communicates with its neighbors), while avoids its drawbacks (the lack of short paths between remotely located nodes). We then present a design flow that maps the frequently communicating tasks of a given application into the same cluster and exploits the reconfigurable connections to set up appropriate inter-cluster links. The evaluation results show the power- and performance-efficiency of the proposed NoC.

This paper presents a distributed run-time task synchronization method for multicore processors aiming to reduce the average power consumption of the chip and satisfy a given thermal constraint, while imposing no performance overhead. Being built on the game theory concepts, this is achieved by dynamically changing the frequency of each individual core based on its current workload iteratively until converging to an optimal point. In this work we target two thermal constraints: keeping (1) the core peak temperature and, (2) thermal gradient across the cores below a predefined threshold. The results show that the proposed framework can find the appropriate frequency for each core based on the optimization target, within an acceptable time.

This paper proposes three ILP-based static thermal-aware mapping algorithms for 3D Networks on Chip (NoC) to explore the thermal constraints and their effects on temperature and performance. Through complexity analysis, we show that the first algorithm, an optimal one, is not suitable for 3D NoC. Therefore, we develop two approximation algorithms and analyze their algorithmic complexities to show their proficiency. As the simulation results show, the mapping algorithms that employ direct thermal calculation to minimize the temperature reduce the peak temperature by up to 24% and 22%, for the benchmarks that have the highest communication rate and largest number of tasks, respectively. This comes at the price of a higher power-delay product. This exploration shows that considering power balancing early in the mapping algorithms does not affect the chip temperature. Moreover, it shows that considering the explicit performance constraint in the thermal mapping has no major effect on performance.

In this paper, we propose a processor allocation mechanism for run-time assignment of a set of communicating tasks of input applications onto the processing nodes of a Chip Multiprocessor (CMP), when the arrival order and execution lifetime of the input applications are not known a priori. This mechanism targets the on-chip communication and aims to reduce the power and latency of the NoC employed as the communication infrastructure. In this work, we benefit from the advantages of non-contiguous processor allocation mechanisms, by allowing the tasks of the input application mapped onto disjoint regions (sub-meshes) and then virtually connecting them by bypassing the router pipeline stages of the inter-region routers. The experimental results show considerable improvement over one of the best existing allocation mechanisms.

Programmable hardware is gaining popularity as it can keep pace with growing performance demand in tight power budget, design and test cost, and serious reliability concerns of future multiprocessor embedded systems. Compatible with this trend, Network-on-Chip, as a potential bottleneck of future multi-cores, should also support programmability. Here, we address this issue in design and implementation of routing algorithm for two-dimensional mesh. To this end, we allocate paths based on input traffic pattern and in parallel with customizing routing restriction for deadlock freedom. To achieve this, we propose extended turn model (ETM), a novel parametric deadlock-free routing for 2D meshes that generalize prior turn-based routing methods (e.g., odd-even) with great degree of freedoms. This model facilitates design of Mixed-Integer Linear Programming (MILP) approach, which considers channel dependency turns as independent variables and decides for both path allocation and routing restriction. We solve this problem by genetic algorithm and evaluate it using simulation experiments. Results reveal that application-aware ETM-based path allocation outperforms prior turn-based approaches under synthetic and real traffic loads.

Phase Change Memory (PCM) is emerging as a high-dense and power-efficient choice for future main memory systems. While PCM cell size is marching towards minimum achievable feature size, recent prototypes effectively improve device scalability by storing multiple bits per each cell. Unfortunately, Multi-Level Cell (MLC) PCM devices offer higher access time and energy when compared to Single-Level Cell (SLC) counterparts making it difficult to incorporate MLC in main memory. To address this challenge, we proposes Zero-value-based Morphable PCM, ZM-PCM for short, a novel MLC-PCM main memory architecture which tries incorporating benefits of both MLC and SLC devices within the same structure. ZM-PCM relies on the observation that zero value at various granularities is frequently occurred within main memory transactions when running PARSEC-2 programs. Motivated by this observation, ZM-PCM codes redundant zero MLC cells into limited bits that is storable in the SLC (or alternatively in devices with fewer bits) form with improved latency, energy, and lifetime with no reduction in available main memory capacity. We evaluate microarchitecture design of morphable PCM cell, coding and decoding algorithms and details of related circuits. We also introduce a simple area-efficient caching mechanism for fast cost-efficient access to coding metadata. Our evaluation on a quad-core CMP with 4GB 8-bit MLC PCM main memory shows that ZM-PCM morphs up to 93% (and 50% on average) of all memory cells with lower densities which directly turns in performance, power and lifetime enhancement.

As the semiconductor industry advances to the deep sub-micron and nano technology points, the on-chip components are more prone to the defects during manufacturing and faults during system operation. Consequently, fault tolerant techniques are essential to improve the yield of modern complex chips. We propose a fault-tolerant routing algorithm that keeps the negative effect of faulty components on the NoC power and performance as low as possible. Targeting intermittent faults, we achieve fault tolerance by employing a simple and fast mechanism composed of two processes: NoC monitoring and route adaption. Experimental results show the effectiveness of the proposed technique, in that it offers lower average message latency and power consumption and a higher reliability, compared to some related work.

A MOWNET is a wireless network that uses financial incentives to make different agents collaborate. In this paper, architecture is proposed to use MOWNETs for Internet service providing. Limited shared bandwidth is a substantial problem in wireless Internet access, which can be alleviated by increasing the number of base stations and decreasing the transmission power of each station. A promising approach to commercialize this idea is using financial incentives to encourage people to collaborate in building the network. Adding financial incentives to the network protocols and using anonymous relay agents incur substantial considerations in network design, which are considered in our protocol.

A task migration scheme for homogeneous chip multiprocessors (CMP) is presented in this paper. The proposed migration mechanism focuses on the communication sub-system and aims to reduce the total power consumption and latency of the network-on-chip (NoC). In this work, starting from an initial mapping, the tasks migrate to new cores in such a way that the distance between the end-point nodes of high-volume communication flows is reduced. Finding the new place for a task is done in a distributed manner by applying an iterative local search that relies on the local information of each task about its communication demand. The task migration procedure also includes a pre-migration step that aims to produce a high quality (i.e. closer to the optimum point) starting point for the main distributed algorithm. The experimental results under some synthetic and realistic CMP workloads show that this method can effectively adapt the mapping of the tasks to the on-chip communication pattern and improve the power consumption and performance of the on-chip networks.

Processor allocation in todays many core MPSoCs is a challenging task, especially since the order and requirements of incoming applications are unknown during design stage. To improve network performance, balance the workload across processing cores, or mitigate the effect of hot processing elements in thermal management methodologies, task migration is a method which has attracted much attention in recent years. Runtime task migration was first proposed in multicomputer with load balancing as the major objective. However, specific NoC properties such as limited amount of communication buffers, more sensitivity to implementation complexity, and tight latency and power consumption constraints bring new challenges in using task migration mechanisms in NoCs. As a consequence, the efficiency and applicability of traditional migration mechanisms (developed for multicomputers) are under question. Due to the limited resource budget in NoC-based MPSoCs as well as tight performance constraints of running applications, in this paper, we propose an efficient methodology based on virtual point-to-point (VIP for short) connections. These dedicated VIP connections provide low-latency and low-power paths for heavy communication flows created by task migration mechanisms. Analyzing the results show that the proposed scheme reduces message latency by 13% and migration latency by 14%, while 10% power savings can be achieved compared to the previously proposed task migration strategy (known as Gathering-Rout-Scattering) for mesh multiprocessors.

Networks-on-Chip (NoCs for short) are known as the most scalable and reliable on-chip communication architectures for multi-core SoCs with tens to hundreds IP cores. Proper mapping the IP cores on NoC tiles (or assigning threads to cores in chip multiprocessors) can reduce end-to-end delay and energy consumption. While almost all previous works on mapping consider higher priority for the application's flows with higher required bandwidth, a mapping strategy, presented in this paper, is introduced that considers multicast communication flows in addition to the normal unicast flows. To this end, multicast and unicast traffic flows are first characterized in terms of some new metrics which are then used for arranging communication flows based on their volume and priority. A heuristic approach is used to assign IP cores to NoC tiles. Simulation results for both synthetic and real applications show up to 49% (28% on average) performance improvement and 44% (22% on average) energy saving when compared to the best known mapping algorithm, nMap.

Grid-based networks (or grids for short), such as meshes and tori, have been the underlying topology for many multicomputers, and have been extensively studied in the past as a graph topology. In this paper, we investigate some topological properties of grids without boundary wrap-around (meshes) and with boundary wrap-around (tori). In particular, we study the problem of finding the number of nodes located at/within a given distance from a given node (surface area/volume) in the network and derive some expressions for computing such a number. Furthermore, we provide similar expressions that improve on previous results already reported in the literature for some special cases of grids, notably hypercubes and k-ary n-cubes. We also show some applications of the derived expressions in analytical performance modelling of some grid-based networks under uniform and hotspot traffic loads.

In this paper, a diverse range of routing algorithms is classified into a new family of routings called zone-ordered label-based routing algorithms. The proposed classification is based on three common steps (factors) for generating such routings, namely, graph labeling, deadlock-free zones, and zone ordering. The main goal of this classification is to define several new routing concepts and streamline the knowledge on routing algorithms. Following the classification, a novel methodology is proposed to generate routing algorithms for irregular networks. The methodology uses the three mentioned steps to generate deadlock-free routings. Consequently, the methodology-based routings fall into the category of zone-ordered label-based routings. However, the graph labeling method (first step) used in the methodology is based on multiple spanning tree construction on the network. The simulation results show that constructing further spanning trees may result in routing algorithm with better performance.

In this paper, we present a reconfigurable architecture for networks-on-chip (NoC) on which arbitrary application-specific topologies can be implemented. When a new application starts, the proposed NoC tailors its topology to the application traffic pattern by changing the inter-router connections to some predefined configuration corresponding to the application. It addresses one of the main drawbacks of the existing application-specific NoC optimization methods, i.e., optimization of NoCs based on the traffic pattern of a single application. Supporting multiple applications is a critical feature of an NoC when several different applications are integrated into a single modern and complex multicore system-on-chip or chip multiprocessor. The proposed reconfigurable NoC architecture supports multiple applications by appropriately configuring itself to a topology that matches the traffic pattern of the currently running application. This paper first introduces the proposed reconfigurable topology and then addresses the problems of core to network mapping and topology exploration. Further on, we evaluate the impact of different architectural attributes on the performance of the proposed NoC. Evaluations consider network latency, power consumption, and area complexity.

In this paper, we present a reconfigurable architecture for NoCs on which arbitrary application-specific topologies can be implemented. The proposed NoC can dynamically tailor its topology to the traffic pattern of different applications at run-time. The run-time topology construction mechanism involves monitoring the network traffic and changing the inter-node connections in order to reduce the number of intermediate routers between the source and destination nodes of heavy communication flows. This mechanism should also preserve the NoC connectivity. In this paper, we first introduce the proposed reconfigurable topology and then address the problem of run-time topology reconfiguration. Experimental results show that this architecture effectively improves the NoC power and performance over the existing conventional architectures.

Heterogeneity is one of the challenges in the current NoC design which forces designers to consider irregular topologies. Therefore, finding an optimal topology with minimum cost (minimum use of links, buffers, NIs, etc) and power consumption, and maximum flexibility can provide the best cost-performance trade-off. Irregular mesh is a topology which combines the benefits of regularity and advantage of irregularity. Routing algorithms especially those coupled with wormhole switching should deal with deadlock occurrences. Unlike deadlock avoidance-based schemes, deadlock detection and recovery-based routing schemes, do not restrict routing adaptability. In this paper, we modify irregular mesh architecture and add some extra mesh-like links to improve its performance using deadlock recovery routing. We evaluate the performance under three well-known deadlock recovery routing algorithms and different traffic patterns before and after the link insertion. Simulation results show the proposed method can noticeably reduce the number of detected deadlocks, average packet latency, routing table size at each node, and energy consumption.

Many researchers favor the mesh topology as the underlying topology of the communication infrastructure of modern SoCs because of its regularity and layout efficiency. However, variability in size and shape of modules used in systems-on-chip has resulted in the use of irregular meshes for practical NoCs. In this paper, we propose a deadlock free routing algorithm for irregular mesh NoCs. Experimental results confirm that the proposed algorithm exhibits a better performance in terms of message latency and power consumption compared to other known routing algorithms for irregular mesh NoCs.

End-to-end delay, throughput, energy consumption, and silicon area are the most important design metrics of networks-on-chip (NoCs). Although several analytical models have been previously proposed for predicting such metrics in NoCs, very few of them consider the effect of message waiting time in the buffers of network routers for predicting overall power consumptions and none of them consider structural heterogeneity of network routers. This paper introduces two inter-related analytical models to compute message latency and power consumption of NoCs with arbitrary topology, buffering structure, and routing algorithm. Buffer allocation scheme defines the buffering space for each individual channel of the NoC that can be homogenous (all channels having similar buffer structures) or heterogeneous (each channel having its own buffer structure). Here, the buffer allocation scheme can be either homogenous or heterogeneous. We assume no bandwidth sharing of virtual channels for a physical channel, and IP cores generate messages following a Poisson distribution. The results obtained from simulation experiments confirm that the proposed models exhibit acceptable accuracy for different network configurations operating under various working conditions. We have shown that basing our analysis on a Poisson traffic model is still useful for scenarios with real application workloads.

In this paper, we aim to improve the performance and power metrics of packet-switched network-on-chips (NoCs) and benefits from the scalability and resource utilization advantages of NoCs and superior communication performance of point-to-point dedicated links. The proposed method sets up the virtual point-to-point (VIP) connections over one virtual channel (which bypasses the entire router pipeline) at each physical channel of the NoC. We present two schemes for constructing such VIP circuits. In the first scheme, the circuits are constructed for an application based on its task-graph at design time. The second scheme addresses constructing the connections at run-time using a light-weight setup network. It involves monitoring the NoC traffic in order to detect heavy communication flows and setting up a VIP connection for them using a run-time circuit construction mechanism. The proposed mechanism is compared to a traditional packet-switched NoC and some modern switching mechanisms and the results show a significant reduction in the network power and latency over the other considered NoCs.

In this paper, we propose a novel on-chip communication scheme by dividing the resources of a traditional packet-switched network-on-chip between a packet-switched and a circuit-switched sub-network. The former directs packets according to the traditional packet-switching mechanism, while the latter forwards packets over circuits which are directly established between two non-adjacent nodes by bypassing the intermediate routers. A packet may switch between the sub-networks several times to reach its destination. The circuits are set up using a low-latency and low-cost setup-network. The network resources are split between the two sub-networks using Spatial-Division Multiplexing (SDM). The work aims to improve the power and performance metrics of Network-on-Chip (NoC) architectures and benefits from the power and scalability advantage of packet-switched NoCs and superior communication performance of circuit-switching. The evaluation results show a significant reduction in power and latency over a traditional packet-switched NoC.

Many Networks-on-Chip (NoC) applications exhibit one or \nmore critical traffic flows that require hard Quality of Service \n(QoS). Guaranteeing bandwidth and latency for such real time \nflows is crucial. In this paper, we present novel methods to \nefficiently calculate worst-case bandwidth and latency bounds \nand thereby provide hard QoS guarantees. Importantly, the \nproposed methods apply even to best-effort NoC architectures, \nwith no extra hardware dedicated to QoS support. By applying \nour methods to several realistic NoC designs, we show \nsubstantial improvements (on average, more than 30% in \nbandwidth and 50% in latency) in bound tightness with respect \nto existing approaches.1

Large Multi-Processor Systems-on-Chip use Networks-on-Chip with a high degree of reusability and scalability for message communication. Therefore, network infrastructure is a crucial element affecting the overall system performance. On the other hand, technology improvements may lead to much energy consumption in micro-routers of an on-chip network. This necessitates an exhaustive analysis of NoCs for future designs. This paper presents a comprehensive analytical model to predict message latency for different data flows traversing across the network. This model considers channel buffers of multiple flits which were not previously studied in NoC context. Also, architectural descriptions of the overall consumed power in the network components are extracted considering message arrival and service rates. The results obtained from simulation experiments confirm that the proposed performance and power models exhibit good accuracy for various network configurations and workloads.

This paper investigates a class of mobile wireless sensor networks that are not connected most of the times. The characteristics of these networks is inherited from both delay tolerate networks (DTN) and wireless sensor networks. First, delay-tolerant wireless sensor networks (DTWSN) are introduced. Then, three main problems in the design space of these networks are discussed: Routing, data gathering, and neighbor discovery. An approach is proposed for deployment of DTWSNs based on the traditional opportunistic broadcast in delay tolerant networks with on-off periods. The delay and the throughput of the routing scheme were investigated in the DTN literature. However, the energy consumption was not studied thoroughly, which is focused here. Neighbor discovery in a sparse network could be a major source of energy consumption. Therefore, energy per contact measure is evaluated analytically based on the distribution of physical link duration. The results for 2D constant velocity model and random waypoint model are reported and the average PLD is suggested as an appropriate choice of beacon interval.

In this paper, we propose a packet-switched network-on-chip (NoC) architecture which can provide a number of low-power, low-latency virtual point-to-point connections for communication flows. The work aims to improve the power and performance metrics of packet-switched NoC architectures and benefits from the power and resource utilization advantages of NoCs and superior communication performance of point-to-point dedicated links. The virtual point-to-point connections are set up by bypassing the entire router pipeline stages of the intermediate nodes. This work addresses constructing the virtual point-to-point connections at run-time using a light-weight setup network. It involves monitoring the NoC traffic in order to detect heavy communication flows and setting up a virtual point-to-point connection for them using a run-time circuit construction mechanism. The evaluation results show a significant reduction in power and latency over a traditional packet-switched NoC.

Irregular networks provide more scalability and better cost-performance for network-based parallel computing systems. There has been much work done on developing routing algorithms for this class of networks. In this paper, a general methodology for generating deadlock-free routing algorithms for irregular networks is proposed. It not only introduces three novel efficient routing algorithms, but also covers the three best-known routing algorithms already proposed for irregular networks in the literature, namely up/down, left/right, and L-turn routing algorithms. As revealed by simulation results, the performance of the six routing algorithms mainly depends on network topology and different scenarios some of proposed routing algorithms exhibit superior performance.

In this paper, we consider the problem of searching a network for intruders. We propose a strategy for capturing the intruder in the popular interconnection topology, the star network. According to the proposed strategy, a team of collaborative software agents are responsible for capturing a hostile intruder (e.g. a virus). These agents asynchronously move along the network links and the intruder has the capability of escaping arbitrarily fast.

In a large system, it is neither economical nor efficient to equip each node with a copy of the resource, and it is desirable to distribute the copies of the resource so that certain performance measure is obtained. In this paper we consider the problem of distributing resources in the edge product of networks. The algorithms presented in this paper make use of the known placements for the basic graphs composing the product graph. Therefore, in these placements we avoid the additional costs needed for deploying and rescaling the network.

Future system-on-chip (SoC) designs will need efficient on-chip communication architectures that can provide efficient and scalable data transport among the intellectual properties (IPs). Designing and optimizing SoCs is an increasingly difficult task due to the size and complexity of the SoC design space, high cost of detailed simulation, and several constraints that the design must satisfy. For efficient design of SoCs, an efficient mapping of IPs onto networks-on-chip (NoCs) is highly desirable. Towards this end, we have presented PERMAP, a performance-aware mapping algorithm which maps the IPs onto a generic NoC architecture such that the average communication delay is minimized. This is accomplished by a performance analytical model which can be used for any arbitrary network topology with wormhole routing. The algorithm is used for mapping a video application onto a tile-based NoC and experimental results show that PERMAP is fast and robust.

During the recent years, 2D mesh network-onchip has attracted much attention due to its suitability for VLSI implementation. The 2-dimensional de Bruijn topology for network-on-chip is introduced in this paper as an attractive alternative to the popular simple 2D mesh NoC. Its cost is equal to that of the simple 2D mesh but it has a logarithmic diameter. We compare the proposed network and the popular mesh network in terms of power consumption and network performance. Compared to the equal sized simple mesh NoC, the proposed de Bruijn-based network has better performance while consuming less energy.

In this paper, a 2D shuffle-exchange based mesh topology, or 2D SEM (shuffle-exchange mesh) for short, is presented for network-on-chips. The proposed two-dimensional topology applies the conventional well-known shuffle-exchange structure in each row and each column of the network. Compared to an equal sized mesh which is the most common topology in on-chip networks, the proposed shuffle-exchange based mesh network has smaller diameter but for an equal cost. Simulation results show that the 2D SEM effectively reduces the power consumption and improves performance metrics of the on-chip networks with regard to the conventional mesh topology.

OTIS-based architectures appear to have the potential to be an interesting option for future generations of multiprocessing systems. In this paper, we propose a new adaptive unicast routing algorithm and four software-based (unicast-based) broadcast algorithms for the wormhole switched OTIS-hypercube. We then present an empirical performance evaluation of these algorithms in OTIS-hypercube for different topologies, message length and traffic loads.

Broadcast is among the most primitive collective communication operations of any interconnection network. Broadcast algorithms for the mesh topology have been widely reported in the literature. However, most existing algorithms have been studied in one-port and within limited conditions, such as light traffic loads. In contrast, this study simulates the broadcast operations, taking into account a wide range of traffic loads. Also, the performance evaluation of meshes in the presence of unicast and broadcast traffic is presented in this paper. To the best of our knowledge, this study is the first to consider the issue of broadcast latency at both the network and node levels. A new model for broadcast in all-port wormhole-routed meshes is proposed. The model is based on the Extended Dominating Nodes algorithm (EDN). Results are shown from a simulation study confirming that the new 2way-EDN broadcast algorithm exhibits superior performance over some existing algorithms.

So far, many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube,torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the a forementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.

Recent studies have revealed that on-chip interconnects neither is wire plentiful nor is bandwidth cheap. Based on the results of these studies, in physical design of multiprocessor system-on-chip (MPSoCs), both the wiring density constraint and routing of wires are controversial issues, and there is a trade-off between the network bandwidth and wiring limitations. Therefore, in this paper, we introduce a new topology, named mesh connected crossbars (MCC), to enhance the communication bandwidth between processing elements; the proposed topology, also, has significant topological advantages over traditional torus- and mesh-based NoCs. Furthermore, we study the topological properties of MCCs and propose deterministic and fully adaptive deadlock-free routing algorithms in an attempt to evaluate the performance of MCC in different working conditions. The simulation results show that under constant wiring conditions, MCC exhibits higher performance and consumes lower energy in comparison with equivalent torus or mesh networks.

Network-on-chip (NoC) has been proposed as a solution for addressing the design challenges of future high-performance nanoscale architectures. Thus, it is of crucial importance for a designer to have access to last methods for evaluating the performance of on-chip networks. To this end, we present a Markovian model for evaluating the latency and energy consumption of on-chip networks. We compute the average delay due to path contention, virtual channel and crossbar switch arbitration using a queuing-based approach, which can capture the blocking phenomena of wormhole switching quite accurately. The model is then used to estimate the power consumption of all routers in NoCs. The performance results from the analytical models are validated with those obtained from a synthesizable VHDL-based cycle accurate simulator. Comparison with simulation results indicate that the proposed analytical model is quite accurate and can be used as an efficient design tool by SoC designers.

The necklace hypercube has recently been introduced as an attractive alternative to the well-known hypercube. Previous research on this network topology has mainly focused on topological properties, VLSI and algorithmic aspects of this network. Several analytical models have been proposed in the literature for different interconnection networks, as the most cost-effective tools to evaluate the performance merits of such systems. This paper proposes an analytical performance model to predict message latency in wormhole-switched necklace hypercube interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has been shown to be the most effective for necklace hypercube networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions.

A core mapping method for reconfigurable network-on-chip (NoC) architectures is presented in this paper. In most of the existing methods, mapping is carried out based on the traffic characteristics of a single application. However, several different applications are implemented and integrated in the modern complex system-on-chips which should be considered by mapping methods. In the proposed method, the reconfiguration (which is achieved by embedding programmable switches between routers of a mesh-based NoC) allows us to dynamically change the network topology in order to adapt it with the running application and optimize the power and performance metrics. The presented network architecture can be configured as an application- specific topology, while it still holds the benefits of the regular NoC topologies such as modularity and predictable electrical properties. The experimental results show that this method can effectively adapt the NoC to the running application and improve the power consumption and performance of the system.

In this paper, we propose the first comprehensive mathematical performance model for product networks where fully adaptive routing is applied. Besides the generality of this model which makes it suitable to be used for any product graph, our analysis shows that the proposed model exhibits high accuracy. Simulation results show the validity and accuracy of the model even in heavy traffic and saturation region, where other models have severe problems for prediction.

Topology control protocols construct a logical topology out of the physical communication graph. Logical topology is maintained by logical neighbor lists in every node. Logical topology is used by several upper-layer protocols as a substantial communication map and is prone to link breakages due to node mobility which compels the periodic re-execution of the topology control protocol in so called "Hello" intervals. The problem addressed in this paper is determining the maximum "Hello " interval preserving the connectivity with high probability which is not extensively concerned yet. The simplest form of topology control, homogeneous topology control, is chosen for start. Two connectivity requirements and statistical topology lifetime (STL) are defined. Then, temporal properties of the topology are studied in terms of STL analysis. Finally, an estimation method for evaluation of STL is proposed and based on the method the STL of several scenarios is estimated. The results are compared to the results of extensive simulations which confirm the accuracy of the proposed method.

The widespread application of deep sub-micron and multilayer routing techniques makes the interconnection parasitic influence become the main factor to limit the performance of VLSI circuits. Therefore, fast and accurate 3D capacitance extraction is essential for ultra deep sub-micron design (UDSM) of integrated circuits. Parallel processing provides an approach to reducing the simulation turn-around time. In this paper, we present parallel formulations for 3D capacitance extraction based on P-FFT algorithm, on a personal computer (PC) or on a network of PCs. We implement both vector and parallel versions of 3D capacitance extraction algorithm simultaneously and evaluate our implementation quality in terms of speed up achieved.

The necklace hypercube has recently been introduced as an attractive alternative to the well-known hypercube. Previous research on this network topology has mainly focused on topological properties, VLSI and algorithmic aspects of this network. Several analytical models have been proposed in the literature for different interconnection networks, as the most cost-effective tools to evaluate the performance merits of such systems. This paper proposes an analytical performance model to predict message latency in wormhole-switched necklace hypercube interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has been shown to be the most effective for necklace hypercube networks. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions.

The utilization of the limited resources of a multiprocessor or multicomputer system is a primary performance issue crucial for the design of many scheduling algorithms. While many of the existing parallel machines benefit from a regular product network topology, almost none of the previous resource placement techniques have come to recognize and exploit this inherent regularity. This paper introduces some novel algorithms for deriving resource placement schemes in product networks based on the assumed perfect resource placement in their underling basic graphs.

In this paper, a new graph product, called Edge Graph Product (EGP) is proposed by replacing each edge in the multiplicand graph by a copy of the multiplier graph via two candidate nodes. The edge product, unlike other products already proposed, results in a graph whose number of edges is numerical product of the number of the edges in the multiplicand and multiplier graphs, and the number of vertices is not equal to the numerical product of the number of vertices in the multiplicand and multiplier graphs. After formal definition of the new product, some basic properties of the product operator are studied. We then address Hamiltonian, Eulerian and routing properties of the new product, and we show that some of the recently proposed topologies fall within the family of edge product graphs.

In this paper, we show that by considering the factor of usage in instruction bundles in VLIW processors and using the slots filled with NOPs in bundles, we can improve the overall performance by reducing the total execution time of the program. By our proposed scheme, Combined Bundle Scheduling (CBS), we have gained better performance compared to that for the PDT scheme (Predicted Decision Tree scheduling) which is the best scheduling strategy known so far.

We study a class of interconnection networks for multiprocessors, called the Stretched-G network, which is based on the base graph G by replacing each edge of the base network with an array of processors. Two interesting features of the proposed topology are its area-efficient VLSI layout and superior scalability over the underlying base network while preserving most of its desirable properties. We conduct a general study on the topological properties of stretched networks. We first obtain their basic topological parameters, after that we present an optimal routing algorithm. We also present a unified approach to obtain the topological properties and the VLSI-layout of an arbitrary stretched network based on the properties of the corresponding base network G.

Partially adaptive routing algorithms are a useful category of routing algorithms due to their simple router logic and restricted adaptivity in selecting the next output channel towards the destination. Several partially adaptive routing algorithms on mesh and hypercube networks have been presented in the literature. But there is no study on evaluating the performance of these algorithms. This paper tries to compare the most important partially adaptive routing algorithms on the mesh and hypercube networks as the most popular topologies for multicomputers. The evaluation has been performed by the use of event driven simulator coded by C++ compiler.

Network-on-chip (NoC) has been proposed as an attractive alternative to traditional dedicated wires to achieve high performance and modularity. Power efficiency is one of the most important concerns in NoC architecture design. The choice of network topology is important in designing a low-power and high-performance NoC. In this paper, we propose the use of the WK-recursive networks to be used as the underlying topology in NoC. We have implemented VHDL hardware model of mesh and WK-recursive topologies and measured the latency results using simulation with these implementation. We also propose a novel approach in high level power modeling based on latency for these topologies and show that the power consumption of WK-recursive topology is less than that of the equivalent mesh on a chip.

Interconnect networks employing wormhole-switching play a critical role in shared memory multiprocessor systems-on-chip (MPSoC) designs, multicomputer systems and system area networks. Virtual channels greatly improve the performance of wormhole-switched networks because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Capturing the effects of virtual channel multiplexing has always been a crucial issue for any analytical model proposed for wormhole-switched networks. Dally has developed a model to investigate the behaviour of this multiplexing which have been widely employed in the subsequent analytical models of most routing algorithms suggested in the literature. It is indispensable to modify Daily's model in order to evaluate the performance of channel multiplexing in more general networks where restrictions such as timing constraints of input arrivals and finite buffer size of queues are common. In this paper we consider timing constraints of input arrivals to investigate the virtual channel multiplexing problem inherent in most current networks. The analysis that we propose is completely general and therefore can be used with any interconnect networks employing virtual channels. The validity of the proposed equations has been verified through simulation experiments under different working conditions

Different models for load balancing have been proposed before, each of which has its own features and advantages when considered for a specific scenario. Yet, nearly all of the existing techniques have assumed an oversimplified model of the system which is often not the case of the real world. In this paper, a new gradient based algorithm for dynamic load balancing on multiprocessors is proposed. This algorithm is an analogy of a classical physical model of a Particle & Plane system which operates based on the classic laws of physics dictated by the nature.

Many theoretical-based comparison studies, relying on the graph theoretical viewpoints with using structural and algorithmic properties, have been conducted for the hypercube and the star graph. None of these studies, however, considered real working conditions and implementation limits. We have compared the performance of the star and hypercube networks for different message length and virtual channels and considered two implementation constraints, namely the constant bisection bandwidth and constant node pin-out. We use two accurate analytical models already proposed for the star graph and hypercube and implement the parameter changes imposed by technological implementation constraints. The comparison results reveal that the star graph has a better performance compared to the equivalent hypercube under light traffic loads while the opposite conclusion is reached for heavy traffic loads. The hypercube with more channels compared to its equivalent star graph saturates later showing that it can bear heavier traffic loads

The star graph was introduced as an attractive alternative to the well-known hypercube and its properties have been well studied in the past. Most of these studies have focused on topological properties and algorithmic aspects of this network. Although several analytical models have been proposed in the literature for different interconnection networks, none of them have dealt with star graphs. This paper proposes the first analytical model to predict message latency in wormhole-switched star interconnection networks with fully adaptive routing. The analysis focuses on a fully adaptive routing algorithm which has shown to be the most effective for star graphs. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy under different operating conditions

Although several analytical models have been proposed in the literature for different interconnection networks with different routing algorithms, there is only one work dealing with partially adaptive routing algorithms. This paper proposes an accurate analytical model to predict message latency in wormhole-routed hypercube based networks using the partially adaptive routing algorithm. The results obtained from simulation experiments confirm that the proposed model exhibits a good accuracy for various network sizes and under different operating conditions

Many theoretical studies have compared the hypercube and star graphs from a graph theoretical viewpoint, under structural and algorithmic properties. None of these studies have, however, considered real working conditions and implementation constraints. In this paper, the hypercube and star graphs are compared in view of fault tolerance and technological implementation constraints. In order to realize a fair comparison, we use the unsafety-vector fault tolerant routing algorithm, recently introduced in (J. Al-Sadi et al., 2002) and (R. Rezazaad et al., 2004), for the hypercube and star graph. Under two implementation constraints, namely constant bisection bandwidth and constant node pin-out, we have compared the performance of the two networks for different fault rates. The results obtained through simulation experiments reveal that, in the presence of low fault rates, the star graph is of better performance than the hypercube.

We present a fault tolerant routing algorithm for the star graph. The algorithm is based on the concept of unsafety vectors originally proposed for binary n-cubes [J. Al-Sadi et al., (2002)]. Each node starts by computing a first level unsafely set, composed of the set of unreachable neighbours. lt then performs some exchanges with its neighbours to determine the unsafely nodes. After that all of the nodes have the addresses of all faulty nodes. Based on the information gathered in each node. Fault-tolerant routing between a source node and a destination node is realised.

Although several analytical models have been proposed in the literature for different interconnection networks with deterministic routing, very few of them have considered the effects of virtual channel multiplexing on network performance. This paper proposes a new analytical model to compute message latency in a general n-dimensional torus network with an arbitrary number of virtual channels per physical channel. Unlike the previous models proposed for toroidal-based networks, this model uses a combinatorial approach to consider all different possible cases for the source-destination pairs, thus resulting in an accurate prediction. The results obtained from simulation experiments confirm that the proposed model exhibits a high degree of accuracy for various network sizes, under different operating conditions, compared to a similar model proposed very recently, which considers virtual channel utilization in the k-ary n-cube network.

Abstract Several studies have examined the relative performance merits of the torus and hypercube taking into account the channel bandwidth constraints imposed by implementation technology. While the torus has been shown to outperform the hypercube under the constant wiring density constraint, the opposite conclusion has been reached when the constant pin‐out constraint is considered. However, these studies have assumed a pure uniform traffic pattern and deterministic routing. The ‘uniform traffic’ assumption is not always justifiable in practice as there are many real‐world parallel applications that exhibit non‐uniform traffic patterns, which can create unbalanced traffic such as hotspots in the network. This paper re‐examines the performance merits of the torus and hypercube in the presence of hotspot traffic. The comparative analysis is based on fully adaptive routing as this has been gaining popularity in recent practical multicomputers. Moreover, it uses a new cost model that takes into account the implementation cost of the network and its routers. The results reveal that for moderate and large system sizes, lower dimensionalk‐aryn‐cubes (e.g. 2D torus) always outperform their higher dimensional counterparts even under the pin‐out constraint. Copyright © 2004 John Wiley & Sons, Ltd.

Adding virtual channels to wormhole-routed networks greatly improves performance because they reduce blocking by acting as "bypass" lanes for non-blocked messages. Although several analytical models have been proposed in the literature for k-ary n-cubes with deterministic routing, most of them have not included the effects of virtual channel multiplexing on network performance. This paper proposes a new and simple analytical model to compute message latency in k-ary n-cubes with an arbitrary number of virtual channels. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions. The proposed model is then used to investigate the relative performance merits of two different organisations of virtual channels.

The k-ary n-cube has been used as the underlying topology for most practical multicomputers, and has been extensively studied in the past. We investigate some properties of this network. In particular, we study the problem of finding the number of nodes located i hops away from a given node (surface area) and the number of nodes located within i hops away from a given node (volume) in both the unidirectional and bidirectional k-ary n-cube, and have derived exact expressions calculating these numbers. These results are very useful when studying, for example, the spanning tree structure of the k-ary n-cube and the problem of resource placement in this network.

Several recent studies have revealed that deadlocks occur very infrequently in the network, especially when enough routing freedom is provided. Routing algorithms based on deadlock avoidance reserve some virtual channels or routing options to specifically deal with deadlocks, and as a result they are not utilized most of the time. Routing algorithms based on deadlock recovery allow messages to use all available virtual channels to cross the network, and efficiently handle infrequently occurred deadlocks. This paper describes a new analytical model of a true fully adaptive routing (TFAR) algorithm with software-based deadlock recovery in k-ary n-cubes. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.

Several analytical models of fully adaptive routing have recently been proposed for wormhole-routed k-ary n-cubes under the uniform traffic pattern. However, there has been hardly any model reported yet that deals with other important nonuniform traffic patterns, such as hot-spots. As a result, most studies have resorted to simulation when evaluating the performance merits of adaptive routing. In an effort to fill this gap, this paper describes the first analytical model of fully adaptive routing in k-ary n-cubes in the presence of hot-spot traffic. Results from simulation show close agreement with those predicted by the model.

Analytical models of fully adaptive routing for common wormhole-routed networks (e.g., hypercubes) under the uniform traffic pattern have recently been reported in the literature. However, many studies have revealed that the performance advantages of adaptive routing over deterministic routing is more noticeable when the traffic is nonuniform due to, for example, the existence of hot spots in the network. This paper proposes a new queueing model of fully adaptive routing in the hypercube in the presence of hot spot traffic. The analysis focuses on Duato's algorithm, but can easily be applied to other fully adaptive routing algorithms. Results from simulation experiments are presented to validate the model.

Several analytical models of deterministic routing in wormhole-routed k-ary n-cubes have already been reported in the literature. The performance characteristics of most fully-adaptive routing algorithms have often been analyzed by means of simulation and there is hardly any analytical model proposed for calculating message latency in wormhole-routed k-ary n-cubes using adaptive routing. The paper proposes an accurate analytical model to predict the message latency in wormhole-routed k-ary n-cubes with fully adaptive routing. The proposed model is general in that it exhibits a good degree of accuracy for various network configurations and under different operating conditions.

Several analytical models of fully adaptive routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used in the past, it is not always true in practice as there are many applications that exhibit non-uniform traffic patterns. There has not been so far any study that describes an analytical model of fully adaptive routing under permutation traffic patterns. This paper describes a new analytical model of fully adaptive routing in k-ary n-cubes in the presence of non-uniform traffic generated by matrix-transpose permutations, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a reasonable degree of accuracy under different working conditions.

Several analytical models of fully-adaptive routing have recently been proposed for wormhole-routed k-ary n-cubes under the uniform traffic pattern. However, there has been hardly any model reported yet that deals with other important non-uniform traffic patterns, such as hot spots. As a result, most studies have resorted to simulation when evaluating the performance merits of adaptive routing. This paper describes the first analytical model of fully-adaptive wormhole routing in k-ary n-cubes in the presence of hot spot traffic. Results from simulation show close agreement with those predicted by the model.

This paper introduces a parallel algorithm for computing an N=n!-point Lagrange interpolation on an n-star (n>2). It exploits several communication techniques on stars in a novel way which can be adapted for computing similar functions. The algorithm is optimal and consists of three phases: initialization, main and final. While there is no computation in the initialization phase, the main phase is composed of n!/2 steps, each consisting of four multiplications, four subtractions and one communication operation, and an additional step including one division and one multiplication. The final phase is carried out in (n-1) sub-phases each with O(log n) steps where each step takes three communications and one addition.

Several recent studies have revealed that pipelined circuit switching (PCS) can provide superior performance characteristics over wormhole routing. This paper proposes an original analytical model of PCS in k-ary n-cube networks augmented with virtual channel support. The model uses random walk theory to analyse the backtracking actions of the header flit during the path setup phase in PCS, and M/G/I queueing systems to compute the mean waiting time that a message experiences at a source before entering the network. Results from simulation experiments show close agreement to those predicted by the model.

Several analytical models of adaptive routing in wormhole-routed networks, including hypercubes, under the uniform traffic pattern have recently been proposed in the literature. However, there has been hardly any model reported yet that deals with other important non-uniform traffic patterns exhibited by many parallel applications. As a result, most existing studies have resorted to simulation when evaluating the performance merits of adaptive routing under non-uniform traffic conditions. This paper describes a new analytical model of adaptive routing in the hypercube in the presence of non-uniform traffic generated by matrix-transpose permutations, which is used in many matrix computation problems. Results obtained through simulation experiments show that the model exhibits a good degree of accuracy in predicting message latency under different working conditions.