GPU has become the de facto device to accelerate widespread machine learning and general purpose computing applications. Sharing a GPU is increasingly important to achieve higher throughput and better resource utilization. However, existing GPU sharing adopts either coarse-grained collocation approaches or interference-unaware spatial partition strategies that produce suboptimal results. In this paper, we propose FedCM, a kernel-level, collocation-based GPU sharing scheme to establish a federated use of compute and on-chip memory resources. FedCM evaluates the collocation potential of ready kernels and dispatches them in a way to maximize system throughput. During collocated execution, FedCM adopts kernel-wise management to arbitrate cache usage via customizing cache policies. The evaluation of our implementation on the off-the-shelf GPUs demonstrates that FedCM improves the overall throughput by 48.3% and 17.4%, compared to standard sharing baseline and prior state-of-the-art, respectively.

Spatial accelerators are promising to satiate the growing demands for performance and energy efficiency in deep neural networks (DNNs). Due to the speed gap between onchip compute cores and off-chip memory bandwidth, common DNNs suffer from poor operational intensity and are increasingly memory-bound. While operator fusion has shown potential in alleviating this bottleneck, existing approaches suffer from two key limitations. They rely on predefined fusion templates before tensor mapping and impose tile constraints during mapping. As a result, they overlook the potential of fusing more operators and lead to sub-optimal performance. In this paper, we propose a segment fusion dataflow optimization framework called SFD. Central to this framework is the dataflow abstraction that enables template-free operator fusion after mapping and supports tile constraint relaxation through tile scheduling. Based on this abstraction, we first introduce a memory-centric mapper, which defines a design space and incorporates an algorithm to facilitate design space exploration (DSE). Then we propose an analytical network segmenter, which leverages mapping results to analyze tensor lifetimes and on-chip memory usage, fusing operators into variable-length segments. Finally, we introduce a dependency-aware tile scheduler, which develops a priority queue for each segment to ensure correct execution order. Extensive experiments with different DNNs demonstrate SFD achieves$1.4 \times$to$2.2 \times$speedup for spatial accelerators over state-of-the-art fusion frameworks.

Conventional heterogeneous computing systems built on PCIe interconnects suffer from inefficient fine-grained host-device interactions and complex programming models. In recent years, many proprietary and open cache-coherent interconnect standards have emerged, among which compute express link (CXL) prevails in the open-standard domain after acquiring several competing solutions. Although CXL-based coherent heterogeneous computing holds the potential to fundamentally transform the collaborative computing mode of CPUs and XPUs, research in this direction remains hampered by the scarcity of available CXL-supported platforms, immature software/hardware ecosystems, and unclear application prospects. This paper presents Cohet, the first CXL-driven coherent heterogeneous computing framework. Cohet decouples the compute and memory resources to form unbiased CPU and XPU pools which share a single unified and coherent memory pool. It exposes a standard malloc/mmap interface to both CPU and XPU compute threads, which share a single per-process page table for user applications, leaving the OS dealing with smart memory allocation, page auto-migration, and management of heterogeneous resources. This design significantly simplifies heterogeneous parallel programming to a level comparable to homogeneous programming. To facilitate Cohet research, we also present a fullsystem cycle-level simulator named SimCXL, which is capable of modeling all CXL sub-protocols and device types. SimCXL has been rigorously calibrated against a real CXL testbed with various CXL memory and accelerators, showing an average simulation error of 3 %. Our evaluation reveals that CXL.cache reduces latency by 68 % and increases bandwidth by$14.4 \times$compared to DMA transfers at cacheline granularity. Building upon these insights, we demonstrate the benefits of Cohet with two killer apps, which are remote atomic operation (RAO) and remote procedure call (RPC). Compared to PCIe-NIC design, CXL-NIC achieves a 5.5 to$40.2 \times$speedup for RAO offloading and an average speedup of$\mathbf{1. 8 6} \times$for$\mathbf{R P C}$(de)serialization offloading.

Efficient video generation models are increasingly vital for multimedia synthetic content generation. Leveraging the Transformer architecture and the diffusion process, video DiT models have emerged as a dominant approach for high-quality video generation. However, their multi-step iterative denoising process incurs high computational cost and inference latency, which limits their practical deployment in large-scale and interactive multimedia applications. Caching, a widely adopted optimization method in DiT models, leverages the redundancy in the diffusion process to skip computations in different granularities (e.g., step, cfg, block). Nevertheless, existing caching methods are limited to single-granularity strategies, struggling to balance generation quality and inference speed in a flexible manner. In this work, we propose MixCache, a training-free caching-based framework for efficient video DiT inference. MixCache first distinguishes the interference and boundary between different caching strategies, and then introduces a context-aware cache triggering strategy to determine when caching should be enabled, along with an adaptive hybrid cache decision strategy for dynamically selecting the optimal caching granularity. Extensive experiments on diverse models demonstrate that MixCache can significantly accelerate video generation (e.g., 1.94× speedup on Wan 14B, 1.97× speedup on HunyuanVideo) while delivering both superior generation quality and inference efficiency compared to baseline methods.

Compute eXpress Link (CXL) has emerged as a key enabler of memory disaggregation for future heterogeneous computing systems to expand memory on-demand and improve resource utilization. However, CXL is still in its infancy stage and lacks commodity products on the market, thus necessitating a reliable system-level simulation tool for research and development. In this paper, we propose CXL-DMSim1, an open-source full-system simulator to simulate CXL disaggregated memory systems with high fidelity at a gem5-comparable simulation speed. CXL-DMSim incorporates a flexible CXL memory expander model along with its associated device driver, and CXL protocol support with CXL.io and CXL.mem. It can operate in both app-managed mode and kernel-managed mode, with the latter using a dedicated NUMA-compatible mechanism. The simulator has been rigorously verified against a real hardware testbed with both FPGA- and ASIC-based CXL memory devices, which demonstrates the qualification of CXL-DMSim in simulating the characteristics of various CXL memory devices at an average simulation error of 3.4%. The experimental results using LMbench and STREAM benchmarks suggest that the CXL-FPGA memory exhibits a ~2.88× higher latency than local DDR while the CXL-ASIC latency is ~2.18×; CXL-FPGA achieves 45-69% of local DDR memory bandwidth, whereas the number for CXL-ASIC is 82-83%. The study also reveals that CXL memory can significantly enhance the performance of memory-intensive applications, improved by 23× at most with limited local memory for Viper key–value database and approximately 60% in memory-bandwidth-sensitive scenarios such as MERCI. Moreover, the simulator’s observability and expandability are showcased with detailed case-studies, highlighting its great potential for research on future CXL-interconnected hybrid memory pool.

In federated recommendation systems, model poisoning attacks aim to manipulate the gradient information of multiple target items sent back from local clients to the central server, with the goal of abnormally increasing their exposure across the system. Existing multi-target attack approaches directly manipulate multiple target items and apply a uniform attack strategy to all target items, which may lead to suboptimal promotion effectiveness. To address this issue, we introduce ProitMTA, a novel multi-target model poisoning attack framework that introduces proxy items and provides tailored attack strategies for target items. ProitMTA employs a three-stage process that balances the promotion of multiple target items while preserving recommendation quality. First,proxy item generationuses a Gaussian Mixture Model to create proxy items that represent diverse attack strategies. Second,proxy attack constructiondesigns customized gradient manipulation strategies for each proxy item. Finally,proxy-based target item attacktransfers these strategies to actual target items, enhancing their promotion while minimizing the negative impact on system performance. Through comprehensive experiments on multiple base federated recommendation frameworks and diverse real-world datasets, we demonstrate that ProitMTA outperforms existing attack methods, achieving higher success rates in target item promotion with minimal system-wide performance degradation. Our research highlights the vulnerability of federated recommendation systems when facing multi-target poisoning attacks and underscores the importance of researching effective defense mechanisms We have released our code athttps://github.com/zdy769243418/ProitMTA.

Cross-domain sequential recommendation (CSR) has garnered significant attention. Current federated frameworks for CSR leverage information across multiple domains but often rely on user alignment, which increases communication costs and privacy risks. In this work, we propose FedCSR, a novel federated cross-domain sequential recommendation framework that eliminates the need for user alignment between platforms. FedCSR fully utilizes cross-domain knowledge to address the key challenges related to data heterogeneity both inter- and intra-platform. To tackle the heterogeneity of data patterns between platforms, we introduce Model Contrastive Learning (MCL) to reduce the gap between local and global models. Additionally, we design Sequence Contrastive Learning (SCL) to address the heterogeneity of user preferences across different domains within a platform by employing tailored sequence augmentation techniques. Extensive experiments conducted on multiple real-world datasets demonstrate that FedCSR achieves superior performance compared to existing baseline methods.

Today, DNN inference is widely adopted, with numerous inference services being spawned from scratch across instances in scenarios such as spot serving, serverless scaling and edge computing, where frequent start-stops are required. In this work, we first delve into the inference workflow and uncover the origins of cold start when invoking a DNN model. Specifically, DNN execution is blocked by the kernel loading process to prepare the code object executing on GPU at the DL primitive library (e.g., cuDNN and MIOpen). To tackle this, we propose PASK, a kernel loading and reusing middleware to mitigate the widespread cold start issue. Unlike the reactive kernel scheduling policy used by existing frameworks, PASK adopts a proactive strategy to interleave code loading, kernel issuing and GPU computation to achieve higher hardware utilization. To further reduce the loading overhead, PASK recycles existing loaded kernels to accomplish the DNN operator, rather than introducing new kernels for every layer. Meanwhile, PASK categorically organizes the cached kernels to efficiently find the applicable kernel for reuse and thus minimize incurred runtime overhead. We implement and evaluate PASK atop of open source DNN inference engine and primitive library on off-the-shelf GPUs. Experiments demonstrate PASK is capable of alleviating the cold start overhead of popular DNN models with $5.62 \times$ speedup on average.

Scheduling determines the execution order and time of operations in program. The order is related to operation dependencies, including data and resource dependencies. Data dependencies are intrinsic in programs, while resource dependencies are determined by scheduling methods. Existing scheduling methods lack an accurate and complete operation dependency graph (ODG), leading to poor performance. In this paper, we propose an ODG-based scheduling method for HLS with GNN and RL. We adopt GNN to perceive accurate relations between operations. We use the relations to guide an RL agent in building a complete ODG. We perform feedback-guided iterative scheduling with the graph to converge to a high-quality solution. Experiments show that our method reduces 23.8% and 16.4% latency on average, compared with the latest GNN-based and RL-based methods, respectively.

Secure data deduplication in edge computing has emerged as a pivotal technique to enhance the cost-efficiency and data security of cloud storage infrastructures. However, the prevailing methodologies predominantly rely on resource-intensive cryptographic operations, resulting in substantial communication and computation overheads. In this paper, we introduce SDXE: a secure data deduplication framework that leverages cloud-edge collaborative computing through Intel's Software Guard Extensions (SGX). It can strike a balance between system performance and data security by harnessing SGX to protect sensitive operations, circumventing the need for conventional cryptographic algorithms. Additionally, we propose a hierarchical storage strategy predicated on data temperature, alongside a version-based two-level fingerprint index structure, to optimize data storage efficiency and enhance transfer performance. Comparing with the typical cryptography-based cloud-edge collaborative secure deduplication schemes, our experimental results demonstrate that SDXE can significantly enhance data communication efficiency with high data security, achieving a remarkable$9.25 \times$upload throughput in client-edge stage,$3.44 \times$upload throughput in edge-cloud stage and$2.96 \times$download throughput.

Predictable dynamic allocation of Persistent Memory (PM) is pivotal to enable flexible and maintainable software design in PM-aware real-time systems. Existing PM allocators suffer from significant variability in the response times of allocation/deallocation operations. Furthermore, although there exist several real-time allocators for DRAM, designers of PM allocators have to tackle the additional challenging problem of crash consistency in order to fully utilize the non-volatile nature of PM. In this paper, we present RT-PMalloc, a novel persistent memory allocator designed for soft real-time applications in server environments where bounded allocation latency is critical. RT-PMalloc builds upon Makalu and introduces three targeted optimizations-profile-guided pre-allocation, constant-time header indexing, and refactored block clearing-to improve response time predictability while preserving crash consistency. Our evaluation shows that RT-PMalloc reduces worst-case allocation latency by up to 85.65% compared to the state-of-the-art PM allocator and maintains tighter latency bounds under multi-threaded workloads. These results demonstrate the feasibility of predictable dynamic PM management for modern soft real-time systems.

Memory tiering is a solution to classify the increasing data for real-time analysis in hierarchical storage management based on its usage patterns and importance.However, traditional storage tiering methods that utilize static thresholds or heuristics are rigid and inefficient, while most existing AI methods use overly complex prediction models, which cost a lot of resources in training and classifying.To address these issues, we propose RABBIT, a Rarely Accessed Blocks Based Intelligent Tiering method for tiered-aware deduplication memory systems.It introduces a monitoring process that can track file-level access features in real systems, predicts which memory layer each data blocks should enter with a daily updated decision tree model, and dynamically migrates the chosen data in a corresponding post-process with error correction mechanism.Meanwhile, a block-level global deduplication scheme is used to ensure that only unique data blocks occupy space in the entire tiered memory system and save storage resources.We build a three-layers and four-layers architecture to evaluate our RABBIT design with block-level I/O traces and real-world workloads and prove RABBIT to be a highly scalable method.Compared with stateof-the-art storage tiering methods, our experimental results show that RABBIT can reduce the average per block latency by 16.89% to 21.84% with a higher access hit rate and save storage capacity by 8.7% to 21.4% for learning access features at the block-level and file-level, respectively.

The occasional nature of I/O bursts in production clusters makes the substantial and expensive SSD internal hardware resources (e.g., computation and memory resources) always underutilized, resulting in cost inefficiency.Open-Channel SSD (OCSSD), as a pioneering solution, removes the SSD internal resources but rather leverages the host-side resources to serve I/O requests.Unfortunately, it faces adoption obstacles due to the heavy resource contention with user applications, hampered host-SSD collaboration, and proprietary firmware leakage risks.Tackling these challenges, we propose XHarvest, a new cost-efficient and high-performance SSD architecture, which harnesses compute express link (CXL) and trusted execution environment (TEE) to facilitate dynamic, efficient, and secure host resource harvesting.It reserves moderate SSD internal resources to isolate SSD internal tasks and applications under regular I/O loads while coping with occasional I/O bursts via dynamic host resource harvesting.To this end, XHarvest executes the firmware within the host-side TEE without disclosing sensitive

Pipeline parallelism has emerged as a predominant approach for deploying large language models (LLMs) across distributed nodes, owing to its lower communication overhead compared to tensor parallelism. While demonstrating high throughput in request serving, pipeline parallelism often faces performance limitations caused by pipeline bubbles, which are primarily resulted from imbalanced computation delays across batches. Existing methods like Sarathi-Serve attempt to address this through hybrid scheduling of chunked prefill and decode tokens with a fixed token budget. However, such methods may still experience significant fluctuations, arising either from insufficient prefill tokens or uneven distribution of decode tokens, ultimately leading to computational imbalance.

The increasing interconnectivity of HPC systems has highlighted the need for efficient application migration across different environments. Containers, widely adopted for this purpose, simplify deployment but often fail to deliver optimal performance due to the separated build and execution container workflow. This leads to generic container images that miss out on system-specific software stack advantages, a challenge we define as the adaptability issue.

Unlike traditional rasterization rendering, ray tracing is a groundbreaking technology that has revolutionized the realistic rendering of images, marking a significant leap forward. However, achieving real-time ray tracing in dynamic scene applications remains a challenging task. This difficulty arises primarily from the substantial technical bottlenecks related to the frequent need for reconstructing or incrementally updating acceleration structures essential for efficient ray calculations.

We introduce WildVideo, an open-world benchmark dataset designed to address how to assess hallucination of Large Multi-modal Models (LMMs) for understanding video-language interaction in the wild. Our WildVideo comprehensively tests the perceptual, cognitive, and contextual comprehension hallucination of LMMs through both single-turn and multi-turn open-ended question-answering (QA) tasks on videos captured from two human perspectives (i.e. first-person view and third-person view). We define 9 distinct tasks that challenge LMMs across multi-level perceptual tasks (e.g., static and dynamic perception), multi-aspect cognitive tasks (e.g., commonsense, world knowledge), and multi-faceted contextual comprehension tasks (e.g., contextual ellipsis, cross-turn retrieval). The benchmark consists of 1,318 meticulously curated videos, supplemented with 13,704 single-turn QA pairs and 1,585 multi-turn dialogues (up to 5 turns). We evaluated 14 commonly-used LMMs on WildVideo, revealing significant hallucination issues of current LMMs, highlighting substantial gaps in their current capabilities.

Scheduling determines the execution order and time of operations in a program. The order is related to operation dependencies, including data and resource dependencies. Data dependency is intrinsic in a program, showing operation data flow. Resource dependency is determined by scheduling methods, resolving operation resource contention. Existing scheduling methods focus on data dependency, rather than building and exploiting operation dependency graph (ODG) with extra resource dependency. As ODG contains all dependencies determining operation execution order, it provides global program information, facilitating efficient scheduling. In this work, we propose ODGS, a dependency-aware scheduling method for high-level synthesis with graph neural network (GNN) and reinforcement learning (RL). We adopt GNN to perceive accurate relations between operations. We use the relations to guide an RL agent in building a complete ODG. We perform feedback-guided iterative scheduling with ODG to converge to a high-quality solution. Experiments show that our method reduces 16.4% latency and 26.5% resource usage on average, compared with the latest RL-based method. Moreover, we reduce an average 2.9% latency over the GNN-based method under the same resource usage. The same resource usage is obtained by improving the GNN-based method with manual resource constraint tuning. Without tuning, its basic version consumes an average 237.6% more resources than our method.

Spatial accelerators are domain-specific architectures to elevate performance and energy efficiency for deep neural networks (DNNs). They also bring a large number of schedule parameters to determine computation and data movement patterns of DNNs. Previous works formulate the schedule problem as design space exploration or integer linear programming. However, these advanced techniques face the challenge of efficiency or scalability. In this article, we propose Ceiba, which is a deep reinforcement learning-based DNN scheduler for spatial accelerators. Ceiba observes the running DNN computation as well as the spatial architecture to make schedule decisions. Then, Ceiba receives a reward to learn and produce the best-fit policy. To provide efficient and scalable scheduling, Ceiba constructs a DNN-architecture-specific action space. It is defined by upper and lower bounds to exclude invalid and sub-optimal schedule candidates. Extensive experiments demonstrate that Ceiba generally provides better performance for spatial accelerators under a fixed number of searching steps or a fixed amount of time. Specifically, Ceiba achieves an average 2.2× speedup for the Simba accelerator, compared with the state-of-the-art scheduler. When scaling the batch size and the hardware architecture up by 64×, the performance gains of Ceiba are 1.8× and 1.2× on average, respectively. Moreover, Ceiba exhibits better scalability for the Eyeriss accelerator.

Program behavior comprises operation dependency and resource requirement. They impact the performance of scheduling in high-level synthesis (HLS). Most existing scheduling methods focus on one aspect, resulting in poor performance. In this article, we propose PBS, a program behavior-aware scheduling method for HLS. We leverage a hybrid state encoding scheme to facilitate the comprehensive learning of program behaviors. Moreover, we propose bi-directional GNN and multiresolution aggregation schemes for learning complex operation dependency behavior. These schemes are integrated in an RL framework to iteratively improve scheduling solutions toward low latency and resource usage. Experiments show that PBS provides an average 32.7%, 26.3%, and 25.9% latency reductions, compared with the SDC, GNN-based, and RL-based methods, respectively.

Ray tracing has emerged as a powerful technique for generating visually stunning and realistic images compared to rasterization. With the continuous advancements in computer hardware, modern GPUs have integrated specialized ray tracing acceleration units to enhance rendering capabilities further. However, achieving realtime ray tracing presents a challenge in dynamic scenes, where spatial data structures used for accelerated rendering must be reconstructed or updated when there are changes in the scene primitives. This paper introduces QuickTree, a novel Bounding Volume Hierarchy (BVH) construction engine based on the linear BVH (LBVH) optimization algorithm. QuickTree addresses the challenge of dynamic scenes support by employing a highly parallel and pipelined system design. This innovative approach ensures fast construction speed. QuickTree demonstrates significant performance improvements. Compared to the currently fastest MergeTree, it has increased construction speed by 10% and reduced area by 45% compared to RayCore, which has the smallest chip area.

While designed for massive parallelism, GPUs are frequently suffering from low thread occupancy and limited data throughput, which are typically attributed to constrained on-chip resources, such as shared memory and register file. To alleviate the pressure, last-level cache (LLC) is being substantially enlarged to support continuously growing computation and to shrink the off-chip data traffic. Nevertheless, applications can be challenging to fully utilize the excessive LLC spaces. Towards the issue, we propose to manage partial LLC in an software way instead to expand precious shared memory (SMEM), named as SMILE, helping to alleviate the low thread occupancy. SMILE splits the monolithic LLC into normal data cache and new software region, with the latter being to extend the limited SMEM. For adapting to diverse application characteristics, SMILE enables multiple splitting grades and determines the appropriate partition via online profiling. Experimental results show that SMILE achieves average performance improvements of 14.7% and 8.4% respectively, compared to the default baseline and prior state-of-the-art.

Deduplication is a highly efficient data reduction technique to improve storage efficiency and save costs. However, the deduplication performance is severely affected by the limited main memory capacity and the disk access bottleneck for the increasing chunk index lookup. In this paper, we propose Multi-Stage Dynamic Cuckoo Filters (MDCF) to speed up index lookup in deduplication systems. Firstly, MDCF modifies the deletion algorithm of standard cuckoo filter to solve the potential problem that it could not identify whether a cell is empty or not. Secondly, MDCF adjusts the insertion algorithm and expands capacity for the increasing load at bucket level or cuckoo filter level. What is more, MDCF integrates a BitSet and CountingSet for each bucket, which significantly reduces the memory overhead and improves the search efficiency without affecting the false positive rate. The experimental results show that compared with DCF, the query, insertion and deletion efficiency of MDCF are improved by about 55.5%, 20.0% and 21.4% respectively. While MDCF's false positive rate was 49.4% lower than that of DBF. And the data backup throughput can be increased by about 163.0% with MDCF to accelerate index lookup.

Spatial accelerator is a specialized hardware to provide noticeable performance speedup for tensor computations. It also brings a challenge to map tensor computations on spatial accelerators. Auto-tuning compiler is one of the most promising directions for tensor mapping. However, existing auto-tuning compilers suffer from either numerous invalid and inefficient programs or inaccurate evaluation of incomplete programs, leading to sub-optimal performance.In this paper, we propose Soter, a novel auto-tuning tensor compilation framework for spatial accelerators. The key is to perform exploration in a both valid and efficient program design space and perform optimization according to accurate evaluation of complete programs. First, we design an analytical model to generate a high-quality program design space, which excludes invalid and inefficient programs. Second, we design an automatic program tuner to efficiently explore the program space and avoid evaluating incomplete programs. Finally, we coordinate the model and the tuner to further improve the quality of program space. The program space is identified by the model and is updated during the exploration of tuner. On average, Soter achieves 2.1× to 3.5× speedup over the state-of-the-art tensor compilers. Moreover, Soter shows better scalability for larger-scale tensor computations and spatial architectures.

Network devices targeting to implement data-intensive applications often require the outstanding performance of symmetric encryption, when dealing with multiple concurrent requests from multiple users. Despite the numerous works on high-performance implementation of AES and SM4, hybrid architectures with lossless throughput when the key changes have not been proposed. In this paper, we propose a unified fully-pipelined architecture of AES and SM4 targeting high-performance Galois/Counter Mode application scenarios. The architecture is able to maintain the consistent throughput of input and output datastreams with changeable keys. Compared with state-of-the-art works implemented with the TSMC 65nm process, our design can reduce the area by 26.83% by using a shared composite S-box. With the one-hot S-box, our design can reduce power consumption by 30.93% and increase throughput by 34.21%.

Spiking Neural Network (SNN) is an effective tool for the simulation of neuronal dynamics as well as the understanding of brain structure and functions. However, scaling up SNN for large-scale simulations poses significant computational demands that necessitate the supercomputers. The advent of distributed simulation introduces the requirement of SNN partition and process mapping, which becomes a critical challenge in the context of large-scale distributed SNN simulations. In this paper, we propose an Area-based partition and Topology-aware process Mapping (ATM) strategy to balance the computation workload while coping with the heterogeneity of communication interconnect. We first model the computation workload and communication volume of the SNN simulation according to its biological features. Based on this model, we design an area-based SNN partition strategy to balance the computation workload. Subsequently, we introduce a topology-aware strategy for process mapping, Bottleneck Fulfilling (BF), tailored specifically for collective communication paradigms. Experiments are conducted on an HPC cluster with a multi-area model of the marmoset brain. The results demonstrate that the proposed approach achieves up to 2.2x speedup compared with the baseline on 290 compute nodes.

Recently, the sparsely-gated Mixture-Of-Experts (MoE) architecture has garnered significant attention. To benefit a wider audience, fine-tuning MoE models on more affordable clusters, which are typically a limited number of bandwidthconstrained GPU nodes, holds promise. However, it is non-trivial to apply existing cost-effective fine-tuning approaches to MoE models, due to the increased ratio of data to computation. In this paper, we introduce APTMoE, which employs affinityaware pipeline parallelism for fine-tuning MoE models on bandwidth-constrained GPU nodes. We propose an affinity-aware offloading technique that enhances pipeline parallelism for both computational efficiency and model size, and it benefits from a hierarchical loading strategy and a demand-priority scheduling strategy. To improve the computation efficiency and reduce the data movement volume, the hierarchical loading strategy designs three loading phases and efficiently allocates computation across GPUs and CPUs during these phases, leveraging different levels of expert popularity and computation affinity. With the aim of alleviating the mutual interference among the three loading phases and maximizing the bandwidth utilization, the demand-priority scheduling strategy proactively and dynamically coordinates the loading execution order. Experiments demonstrate that APTMoE outperforms existing methods in most cases. Particularly, APTMoE successfully fine-tunes a 61.2B MoE model on 4 Nvidia A800 GPUs(40GB) and achieves up to $33 \%$ throughput improvement compared to the SOTA method.

Training large models for modern recommendation systems requires a substantial number of computational devices and extended periods. Since it is essential to store model checkpoints throughout the training progress for accuracy debugging or mitigating potential failures, checkpointing systems are widely used. However, given that recommendation models can scale to hundreds of gigabytes or more, existing solutions often introduce significant overhead in terms of both storage and I/O. In this paper, we present IncrCP, a checkpointing system specifically designed for recommendation models. Given that only a small fraction of model parameters are modified in each iteration, IncrCP creatively leverages the incremental checkpointing strategy and overcomes the inherent slow recovery problem. To support recovering all states throughout the training process, while also ensuring efficient storage utilization and rapid recovery, IncrCP proposes the 2-D chunk approach. It proactively records changed parameters in the training process as well as their indexes, extracts parameters according to duplicated indexes as independent chunk files, and then orchestrates these chunks in the 2-dimensional linked list. In this way, IncrCP achieves fast recovery by loading less unnecessary parameters and performing less deduplication during recovery. Furthermore, IncrCP includes a selective extraction approach to reduce I/O by avoiding worthless extractions and a concatenate approach to reduce random disk access when recovery. Evaluations show that IncrCP achieves up to 6.6× recovery speedup compared to the naive incremental strategy and saves storage space by 60.4% with slight overhead compared to another recovery-friendly strategy.

The mapping of tensor computation is a complex and important process for spatial accelerators. Today's mapping works depend on hand-tuned kernel libraries or search-based heuristics from human experts. The former is time-intensive while the latter easily leads to sub-optimal performance. In this paper, we propose TensorMap, a deep reinforcement learning (RL)-based mapping framework for tensor computations on spatial accelerators. We propose a sequential generation mode for mapping optimization and construct a coarse-grained action space to reduce the complexity of the mapping search space. An efficient policy network is devised to optimize mapping primitives in the RL-based search. We then propose a stop signal that is sampled fromBernoullidistribution to facilitate multi-level loop unrolling for spatial accelerators. Finally, a genetic algorithm is employed to further refine the optimized mappings. In the experiments, we demonstrate TensorMap's ability for different spatial accelerators with various tensor computations. On TPU, TensorMap provides 2.6$\times$, 2.7$\times$, and 2.4$\times$better energy-delay product (EDP) on average compared with FlexTensor, Ansor, and AMOS respectively. On Eyeriss, TensorMap provides 2.1$\times$, 1.8$\times$, and 1.7$\times$better EDP on average compared with FlexTensor, Ansor, and AMOS respectively.

The dot-product$\sum _{i=1}^{N} A_{i}\times B_{i}$is one of the most frequently used operations for a wide variety of high-performance computing (HPC) and artificial intelligence (AI) applications. However, for large-scale algorithms, such as acrshort GEMM and acrshort FFT, independent additions are necessary to accumulate the results of length-limited dot-product in order to form the final result, thus increasing latency and overhead. Hence, we proposed a dot-product-dual-accumulate (DPDAC) architecture capable of performing$\left({\sum _{i=1}^{N=1,2,4} A_{i}\times B_{i} + \sum _{j=1}^{M=1,2} C_{j}}\right)$on a wide range of formats. The proposed architecture supports both single-path and dual-path execution. The single path is designed for performing acrshort DP acrshort FMA or DPDAC of lower formats, while dual-path supports parallel operations for single-precision (SP) addition and 2-term SP or acrshort TF32 dot-product or 4-term acrshort HP or BF16 dot-product. Moreover, numerical precision conversion is also supported by the proposed architecture, allowing for the conversion of numbers to higher or lower formats. The proposed DPDAC has been demonstrated to significantly reduce the overhead in comparison to discrete designs that utilize multiple single-mode acrshort FP units to achieve the same functionalities. Furthermore, when compared to the state-of-the-art multiple-precision designs, the proposed architecture has been shown to support a wide range of formats and a greater variety of operations with lower costs.

Previous post-processing studies on rainfall forecasts using numerical weather prediction (NWP) mainly focus on statistics-based aspects, while learning-based aspects are rarely investigated. Although some manually-designed models are proposed to raise accuracy, they are customized networks, which need to be repeatedly tried and verified, at a huge cost in time and labor. Therefore, a self-supervised neural architecture search (NAS) method without significant manual efforts called AdaNAS is proposed in this study to perform rainfall forecast post-processing and predict rainfall with high accuracy. In addition, we design a rainfall-aware search space to significantly improve forecasts for high-rainfall areas. Furthermore, we propose a rainfall-level regularization function to eliminate the effect of noise data during the training. Validation experiments have been performed under the cases ofNone,Light,Moderate,HeavyandViolenton a large-scale precipitation benchmark named TIGGE. Finally, the average mean-absolute error (MAE) and average root-mean-square error (RMSE) of the proposed AdaNAS model are 0.98 and 2.04 mm/day, respectively. Additionally, the proposed AdaNAS model is compared with other neural architecture search methods and previous studies. Compared results reveal the satisfactory performance and superiority of the proposed AdaNAS model in terms of precipitation amount prediction and intensity classification. Concretely, the proposed AdaNAS model outperformed previous best-performing manual methods with MAE and RMSE improving by 80.5% and 80.3%, respectively.

Ray tracing has been regarded as the future of graphics rendering technology for a long time. However, interactive ray tracing still faces challenges, especially in mobile devices, such as high computational intensity and multiple branches. In this brief, we aim to maximize overall efficiency by leveraging all forms of potential parallelism, including task, basic block, loop, and pipeline levels. We present multilevel parallel ray tracing accelerator (MPRTA), an innovative mobile accelerator that offers high performance and optimal efficiency for ray tracing. Experimental results indicate that MPRTA is$1.67\times $more efficient than the currently best-reported mobile accelerator.

Personalized Federated Learning (FL) handles the data heterogeneous problem by tailoring local models for each distributed data owner. Previous studies first train a highly-adaptable global model and then transfer it for personalization. However, the additional training aggravates burden of resource-limited end devices. Training a personalized local sub-network is a promising efficient solution. It normally prunes the global model by parameters’ scalar magnitude. In this paper, we found that the vector magnitude, i.e. the parameter stability, could further promote personalized FL. Driven by the local data characteristics, the values of some model parameters are hardly changed in their updates. But they consume the same resources as the changed ones. Thus, we propose Star-PFL, a STability-AwaRe algorithm for efficient FL Personalization. In Star-PFL, the data owner focuses on training non-stabilized parameters, and decreases the resource wastes on stabilized ones. Experimental results on two real-world biomedical datasets demonstrate that Star-PFL improves the accuracy (3.1%↑) and decreases the resource costs (communication 36.3%↓, computation 18.3%↓) than 5 typical baselines. The code is available at https://github.com/Guoyeting/Star-PFL.

We propose GreDedup, a greedy algorithm based application-aware data routing strategy for distributed deduplication, which can achieve a good tradeoff between high global deduplication ratio and scalable performance by reducing the communication overhead and avoiding disk bottleneck. We extract semantic information to classify backup files, and use the greedy algorithm to route files with the same type to as few storage servers as possible with the help of application tables. In intra-node deduplication, we maintain a unique chunk fingerprint index for each file type to reduce disk access times. We perform experiments to compare GreDedup with state-of-the-art alternatives under public datasets. The results show that GreDedup can achieve high global deduplication ratio almost the same as the high overhead scheme, but its write performance even exceeds that of the low overhead method with good load balancing.

存储系统是计算机的核心,在人工智能、大数据、云计算和物联网等新兴战略产业的可持续发展中起着重要作用。随着处理器和网络设备性能不断提高,存储软件栈成为限制数据密集型系统性能的主要因素。近年来,新型存储设备因其打破“内存墙”的能力而受到广泛关注。这些设备包括支持块寻址的闪存设备、支持字节寻址的非易失性存储器、存算一体化设备以及大容量光存储。构建高吞量、低延迟和高可靠性的大规模存储系统,需要对算法、软件设计和硬件的持续创新。这些创新可以应对大规模、高性能复杂结构系统构建中存在的挑战,还可以增加相关系统的构建和应用经验,加快大数据处理系统的开发速度。 研究人员一直致力于解决“内存墙”问题,并改进相关软硬件生态系统,从而在新型存储系统设计和应用方面取得很大进展,包括但不限于以下方面:

The task of situation recognition aims to solve the visual reasoning problem with the ability to predict the activity happening (salient action) in an image and the nouns of all associated semantic roles playing in the activity. This poses severe challenges due to long-tailed data distributions and local class ambiguities. Prior works only propagate the local noun-level features on one single image without utilizing global information. We propose a Knowledge-aware Global Reasoning (KGR) framework to endow neural networks with the capability of adaptive global reasoning over nouns by exploiting diverse statistical knowledge. Our KGR is a local-global architecture, which consists of a local encoder to generate noun features using local relations and a global encoder to enhance the noun features via global reasoning supervised by an external global knowledge pool. The global knowledge pool is created by counting the pairwise relationships of nouns in the dataset. In this paper, we design an action-guided pairwise knowledge as the global knowledge pool based on the characteristic of the situation recognition task. Extensive experiments have shown that our KGR not only achieves state-of-the-art results on a large-scale situation recognition benchmark, but also effectively solves the long-tailed problem of noun classification by our global knowledge.

As a decentralized training paradigm, Federated learning (FL) promises data privacy by exchanging model parameters instead of raw local data. However, it is still impeded by the resource limitations of end devices and privacy risks from the ‘curious’ cloud. Yet, existing work predominately ignores that these two issues are non-orthogonal in nature. In this article, we propose a joint design (i.e., AHFL) that accommodates both the efficiency expectation and privacy protection of clients towards high inference accuracy. Based on a cloud-edge-end hierarchical FL framework, we carefully offload the training burden of devices to one proximate edge for enhanced efficiency and apply a two-level differential privacy mechanism for privacy protection. To resolve the conflicts of dynamical resource consumption and privacy risk accumulation, we formulate an optimization problem for choosing configurations under correlated learning parameters (e.g., iterations) and privacy control factors (e.g., noise intensity). An adaptive algorithmic solution is presented based on performance-oriented resource scheduling, budget-aware device selection, and adaptive local noise injection. Extensive evaluations are performed on three different data distribution cases of two real-world datasets, using both a networked prototype and large-scale simulations. Experimental results show that AHFL relieves the end's resource burden (w.r.t. computation time 8.58%$\downarrow$, communication time 59.35%$\downarrow$and memory consumption 43.61%$\downarrow$) and has better accuracy (6.34%$\uparrow$) than 3 typical baselines under the limited resource and privacy budgets. The code for our implementation is available athttps://github.com/Guoyeting/AHFL.

In this article, a new multiple-mode floating-point fused multiply–add (FMA) unit is proposed for deep learning processors. The proposed design supports three functional modes—normal FMA mode, mixed FMA mode, and dual FMA mode—and four types of precision—single-precision (SP), half-precision (HP), BFloat16 (BF16), and TensorFloat-32 (TF32)—based on the practical requirements of deep learning applications. In the normal FMA mode, conventional FMA operations, one SP operation or two parallel HP operations, are performed every clock cycle. In the mixed FMA mode and dual FMA mode, mixed-precision operations, the fused multiply–accumulate and the dot-product, are implemented, respectively. Specifically, the product of lower precision multiplication can be accumulated to a higher precision addend. Compared with the mixed FMA mode, the throughput is doubled in the dual FMA mode due to the full utilization of the multiplier operand bandwidth. In addition to FMA operations, numerical precision conversion (NPCvt) is also supported in this work: higher precision FMA results can be converted into lower precision numbers, corresponding to the datatype transform in the datapath of deep neural network (DNN) training. The FMA design presented herein uses both the segmentation and reusing methods to trade off performance, such as throughput and latency, against area, and power. Compared with the state-of-the-art multiple-precision FMA unit, the proposed design supports more types of floating-point operation and NPCvt, with higher throughput and lower hardware overhead.

Persistent memory (PM) offers byte-addressable persistence with high random access performance close to DRAM. The special characteristics of PM have brought new opportunities and challenges to design file systems. Intuitively, file systems are IO-intensive and the computation overhead is negligible. Whereas, PM dramatically improves IO performance and we observe that the computation overhead of metadata operations in PM file systems is becoming increasingly non-negligible. Furthermore, with the heavy computation overhead in metadata operations, the CPU is easy to be saturated under a highly concurrent workload. Fortunately, due to abundant computation resources, SIMD technology provides potential opportunities to accelerate metadata operations for PM file systems. In this paper, we present an SIMD-accelerated metadata management scheme for PM file systems. Specifically, we design the SIMD-aware data structures and algorithms involved in metadata operations for PM file systems to accelerate metadata operations. In addition, to take the full performance of SIMD and leverage the compatibility of SIMD instructions and PM, we perform operations on PM directly to eliminate the overhead of data interaction between PM and DRAM. We implement a prototype called SPFS, and our evaluation demonstrates that SPFS can outperform other tested PM file systems in a variety of test scenarios.

This paper proposes a locality-aware Oblivious RAM (ORAM) primitive, named Green ORAM, which exploits spatial locality of data in the physical memory for reducing ORAM overheads. The Green ORAM is novel consisting of three policies. The first is row-guided label allocation used for mapping spatial locality onto ORAM tree to reduce the number of memory commands. The second is segment-based path replacement able to improve the data locality within the path in the ORAM tree in order to remove the redundant memory accesses. The third is multi-path write-back able to improve the data locality between different paths in order to obtain theoretical best stash hit rate. Notably, the Green ORAM still maintains the security as we analyzed. Experimental results show that Green ORAM achieves a 28.72% access latency reduction, and a 19.06% memory energy consumption reduction on average, compared with the state-of-the-art String ORAM.

Persistent memory (PM) has always been used in combination with DRAM to configure hybrid main memory systems that can obtain both the high performance of DRAM and large capacity of PM. There are critical management challenges in data placement, memory concurrency and workload scheduling for the concurrent execution of multiple application workloads. But the non-negligible performance gap between DRAM and PM makes the existing application-agnostic management strategies inefficient in reaching the full potential of hybrid memory. In this paper, we propose a series of application aware optimization strategies, including application aware data placement, adaptive thread allocation and inter-application interference avoiding, to improve the concurrent performance of different application workloads on hybrid memory. Finally, we provide the performance evaluation for our application aware solutions on real hybrid memory hardware with some comprehensive benchmark suites. Our experimental results show that the duration of multi-application concurrent execution on hybrid memory can be reduced by at most 60.7% for application aware data placement, 37.7% for adaptive thread allocation and 34.8% for workload scheduling with inter-application interference avoiding, respectively. And the additive effects of all these three optimization methods can reach 62.8% performance improvement with negligible overheads.

Abstract Cloud storage is a fundamental component of the cloud computing system, which significantly affects the overall performance and quality of service of the cloud. Cloud storage servers face the challenge of imbalanced workloads. According to our observations on the time series generated by cloud storage, we found that the imbalance workloads will dramatically increase the tail latency of data access in the multi-tenant scenario. The intuitive solution is to periodicity detect the imbalance storage nodes and re-balance the loads. However, there are four challenges to accurately detect load of storage in the cloud with multiple tenants since the load may change frequently in cloud. This paper proposes PrecisePeriod, a precise periodicity detection algorithm customized for multi-tenant cloud storage. It removes outliers through data preprocessing, employs the discrete wavelet transform to remove high-frequency noise while keeping frequency domain information, computes the candidate periodicity queue using the autocorrelation function, and determines precise period through periodicity verification. Then, we design a cloud storage load balancing scheduling strategy based on PrecisePeriod, and the evaluation shows that the PrecisePeriod scheduling significantly reduces tail latency while only bringing $$1-2\%$$ 1-2% overhead.

This paper explores resource allocation strategy in the Baidu Over The Edge system to enable mobile edge computing (MEC) datacenters to effectively support cloud-native services downstream to the network edge. There are many challenges to this issue. First, MEC datacenters are resource-constrained to fully meet resource demands. Second, previous works regard the resource requirements of each service as an indivisible unit, resulting in idle MEC resources, even if the resources can meet the demands of some microservices decoupled by the service. Third, they are confined to optimize the allocation for a single slot, failing to adapt to the dynamic demands. To improve resource utilization, we propose performability-aware resource allocation (PARA), a PARA on the edges for cloud-native services. It takes microservices as the unit of resource allocation and allows services to perform with degraded services when only part of microservices' demands are met. It also considers dependency among microservices, dynamic resource requirements, and resource supply characteristics of MEC and cloud. Performability is a unified performance-reliability measure for evaluating such degradable systems. To maximize the long-term overall performability, we model the resource optimization problem and then develop an online greedy heuristic algorithm. The algorithm predicts services' resource demands and then adapts the online allocation. The experimental results show that PARA reduces the reallocation overhead by 47.7%–53.6%, and improves the long-term overall performability by 23.14%–43.25% of existing state-of-the-art works.

The healthcare industry faces challenges regarding the security and efficiency of data management for patient health records (PHRs). We propose SafePHR: a secure and efficient medical data service with application aware deduplication in fog-to-multicloud encrypted storage. It introduces a fog-to-multicloud cooperative storage model, which combines low-latency and high-safety local fog with unlimited capacity and built-in disaster recovery in remote multi-cloud to enhance eHealth data management. It also provides an application aware secure deduplication scheme to improve the data traffic and space efficiency of cloud storage for encrypted PHRs using variants of convergent encryption. Then, it further enhances the resiliency and security of cloud storage by striping encrypted data across multiple cloud vendors with a fault-tolerant coding scheme. Compared with the state-of-the-art of cloud-assisted eHealth systems, our experiments demonstrate that SafePHR can ensure data confidentiality of deduplication, achieve a competitive low cloud storage space overhead, and improve system performance with high fault-tolerance capability.

Phase Change Memory (PCM) can directly connect persistent memory to main memory bus, while it achieves high read throughput and low standby power, the critical concerns are its poor write performance and limited durability. A naturally in-spired design is the hybrid memory architecture that fuses DRAM and PCM, so as to exploit the positive aspects of both types of memory. Unfortunately, existing solutions are seriously challenged by the limited main memory size, which is the primary bottleneck of in-memory computing. In this paper, we introduce a novel Content Aware Hybrid DRAM-PCM memory system framework—CAHRAM, which exploits deduplication to improve line sharing with high memory efficiency. It reduces write traffic to hybrid memory by removing unnecessary duplicate line writes, thereby further enhancing the write endurance of PCM. And it also substantially extends available free memory space by coalescing redundant lines in hybrid memory. We also design a reference-based page migration technique to minimize the access overheads caused by the performance gap between DRAM and PCM. Compared with the state-of-the-art in a hybrid memory simulator, our experiment results show that CAHRAM can achieve the highest I/O performance and the longest PCM lifetime with the competitive efficiencies in space and energy.

The recent algorithms for math word problems (MWP) neglect to use outside knowledge not present in the problems.Most of them only capture the word-level relationship and ignore to build hierarchical reasoning like the human being for mining the contextual structure between words and sentences.In this paper, we propose a Reasoning with Pre-trained Knowledge and Hierarchical Structure (RPKHS) network, which contains a pre-trained knowledge encoder and a hierarchical reasoning encoder.Firstly, our pretrained knowledge encoder aims at reasoning the MWP by using outside knowledge from the pre-trained transformer-based models.Secondly, the hierarchical reasoning encoder is presented for seamlessly integrating the wordlevel and sentence-level reasoning to bridge the entity and context domain on MWP.Extensive experiments show that our RPKHS significantly outperforms state-of-the-art approaches on two large-scale commonly-used datasets, and boosts performance from 77.4% to 83.9% on Math23K, from 75.5 to 82.2% on Math23K with 5-fold cross-validation and from 83.7% to 89.8% on MAWPS.More extensive ablations are shown to demonstrate the effectiveness and interpretability of our proposed method.

Routing is one of the most time-consuming stages in the FPGA design flow. Parallelization can accelerate the routing process but suffering from load imbalance, further resulting in a low scalability. In this paper, we propose a load balance-centric parallel router in a distributed computing environment. First, we explore regular and irregular region partitioning so that routing tasks are assigned to different cores for static load balance before parallel routing. Second, we explore message propagation and task migration between underloaded and overloaded cores so that load balance can be dynamically maintained at parallel routing runtime. Finally, we demonstrate the effectiveness of the parallel router using large-scale Titan designs. Experimental results show that our parallel router achieves about 17 × speedup on average using 32 cores, compared with VTR 8 router.

As a large number of emerging graph applications spread across different domains, the need for processing massive concurrent graph jobs (CGJs) is increasing. However, existing graph processing systems designed for a single job cannot efficiently tackle multiple CGJs, where they suffer from interfering memory access patterns and inefficient property management. In this paper, we introduce Krill, a compiler and runtime system for processing concurrent graph jobs. We propose an SAP model, which decouples graph structure, algorithm, and property. In the compiler, we propose leveraging the property buffer to easily write and manage property data. In the runtime system, we propose a novel technique named graph kernel fusion to reduce memory accesses, which fuses all the jobs and processes them as a whole. Experimental results show our system significantly reduces the number of memory accesses for CGJs by more than 6x compared with the baseline, and achieves up to 6.76x speedup with 3.84x shorter response latency than GraphM, the state-of-the-art concurrent graph processing system.

Due to massive thread-level parallelism, GPUs have become an attractive platform for accelerating large-scale data parallel computations, such as graph processing. However, achieving high performance for graph processing with GPUs is non-trivial. Processing graphs on GPUs introduces several problems, such as load imbalance, low utilization of hardware unit, and memory divergence. Although previous work has proposed several software strategies to optimize graph processing on GPUs, there are several issues beyond the capability of software techniques to address. In this article, we present GraphPEG, a graph processing engine for efficient graph processing on GPUs. Inspired by the observation that many graph algorithms have a common pattern on graph traversal, GraphPEG improves the performance of graph processing by coupling automatic edge gathering with fine-grain work distribution. GraphPEG can also adapt to various input graph datasets and simplify the software design of graph processing with hardware-assisted graph traversal. Simulation results show that, in comparison with two representative highly efficient GPU graph processing software framework Gunrock and SEP-Graph, GraphPEG improves graph processing throughput by 2.8× and 2.5× on average, and up to 7.3× and 7.0× for six graph algorithm benchmarks on six graph datasets, with marginal hardware cost.

Big Data platforms recently employ resource management systems, such as YARN, Mesos, and Google Borg, to provision computational resources. These systems adopt containerization to share the computing resources in a multi-tenant setting with low performance overhead and interference. However, it may be observed that tenants often interfere with each other on the underlying Big Data File Systems (BDFS), e.g., Hadoop File System, which have been widely deployed as a persistent layer in current data centers. A solution with systematic generality is to containerize BDFS itself to isolate and allocate its IO sources to multiple tenants. To this end, we conduct analysis on the ineffectiveness of proportionally sharing BDFS IO resource via containerization. This ineffectiveness is due to the scheduler of containerization in “pseudo-starvation” status, in which most of IO requests are backlogged in BDFS rather than in containerization scheduler. Without enough backlogged IO requests, existing schedulers might have to maximize device utilization rather than enforce proportional sharing policy. To resolve this ineffectiveness issue, we develop a cross-layer system calledBDFS-Container, which containerizes BDFS at the Linux block IO level. Central to BDFS-Container, we propose and design a proactive IOPS throttling-based mechanism namedIOPS Regulator, which achieves a trade-off between maximizing IO utilization and accurately proportional IO sharing. The evaluation results show that our method can improve proportionally sharing BDFS IO resources by 74.4 percent on average.

Emerging nonvolatile memories (NVMs), while exhibiting great potential to be DRAM alternatives, are vulnerable to security attacks. Secure NVM designs demand data persistence on top of traditional confidentiality and integrity protection. A simple adaption of existing secure memory designs would incur non-negligible overheads, including performance degradation, NVM lifetime reduction, and energy consumption increase. In this article, we propose CacheTree to address the integrity verification overhead for secure NVMs. By constructing extra Merkle trees (MTs) on top of metadata cache, CacheTree helps to authenticate the volatile cache contents, which enables the adoption of write-back policy and prevents frequent NVM writes in persisting metadata. We then adopt CacheTree to address the integrity verification in secure NVM, in particular, the overheads in persisting message authentication codes (for protecting the integrity of user data at memory line level) and persisting the main MT (for protecting the integrity of the whole memory space). Our experimental results show that CacheTree, with less than 0.5% storage overhead, achieves up to 20.1% performance improvement, 44.3% lifetime increase, and 43.7% energy consumption reduction over the state-of-the-art solutions.

Routing is a very complex process in the field programmable gate array (FPGA) CAD flow. The increase of both FPGA size and design complexity leads to a long routing time hindering the productivity. In this article, we propose a more effective parallel router that combines static and dynamic load balance in parallel routing for FPGAs. First, we explore hierarchical region partitioning to assign routing tasks to different cores for static load balance. Then, we coordinate message propagation and task migration at runtime so that load balance between cores can be dynamically maintained in parallel routing. Finally, we combine static and dynamic load balance in the parallel routing for a higher degree of parallelism. Our parallel router performs on the multicore distributed-memory systems and the communication between cores is through message passing interface messages. We demonstrate the effectiveness of our parallel router using large-scale Titan designs. On average, our parallel router can scale up to 32 cores to achieve about 17× speedup with slight loss of quality, compared with the latest VTR 8 router.

In recent years, erasure codes have become the de facto standard for data protection in large scale distributed cloud storage systems at the cost of an affordable storage overhead. However, traditional erasure coding schemes, such as Reed-Solomon codes, suffer from high reconstruction cost and I/Os. The recent past has seen a plethora of efforts to optimize the tradeoff between the reconstruction cost, I/Os and storage overhead. Quiet different from all prior studies, in this paper, our erasure coding technique makes the first attempt to take advantage of the unequal failure rates across the disks/nodes to optimize the system reliability and reconstruction performance. Specifically, our proposed technique, the Unequal Failure Protection based Local Reconstruction Code (UFP-LRC) divides the data blocks into several unequal-sized groups with local parities, assigning the data blocks stored on more failure-prone disks/nodes into the smaller-sized group, so as to provide unequal failure protection for each group. In this way, by exploiting the nonuniform local parity degrees, the proposed UFP-LRC enables the data blocks that are stored on more failure-prone disks/nodes to tolerate a greater number of failures while suffering from less repair cost than others, leading to a substantial improvement of the overall reliability and repair performance for cloud storage systems. We perform numerical analysis and build a prototype storage system to verify our approach. The analytical results show that the UFP-LRC technique gradually outperforms LRC along the increase of failure rate ratio. Also, extensive experiments show that, when compared to LRC, UFP-LRC is able to achieve a 10 to 15 percent improvement in throughput, and an 8 to 12 percent reduction in decoding latency, while retaining a comparable overall reliability.

It is promising to deploy CNN inference on local end-user devices for high-accuracy and time-sensitive applications. Model parallelism has the potential to provide high throughput and low latency in distributed CNN inference. However, it is non-trivial to use model parallelism as the original CNN model is inherently tightly-coupled structure. In this article, we propose DeCNN, a more effective inference approach that uses decoupled CNN structure to optimize model parallelism for distributed inference on end-user devices. DeCNN is novel consisting of three schemes. Scheme-1 is structure-level optimization. It exploits group convolution and channel shuffle to decouple the original CNN structure for model parallelism. Scheme-2 is partition-level optimization. It is based on channel group to partition the convolutional layers, and then leverages input-based method to partition the fully connected layers, further exposing high degree of parallelism. Scheme-3 is communication-level optimization. It uses inter-sample parallelism to hide communications for better performance and robustness, especially in the weak network connections. We use ImageNet classification task to evaluate the effectiveness of DeCNN on a distributed multi-ARM platform. Notably, when using the number of devices from 1 to 4, DeCNN can accelerate the inference of large-scale ResNet-50 by 3.21×, and reduce 65.3 percent memory footprint, with 1.29 percent accuracy improvement.

Routing is a very time-consuming stage in the FPGA design flow, significantly hindering the productivity. This article proposes CPRS, a coarse-grained parallel routing scheme in a distributed computing environment. First, we partition entire routing region to guide the assignment of nets for parallel processing. The partitioning is a recursive fashion, and at each recursive partitioning, the region is partitioned into two subregions forming three subsets of nets. The first subset consists of potentially dependent nets and they are distributed in different subregions. The remaining two subsets consist of potentially independent nets and they are distributed in their own subregions. Second, we route the nets of first subset in serial and process the remaining two subsets in parallel. The parallel processing is a coarse-grained fashion, which is implemented by MPI parallel programming model. Finally, we explore the optimization of both partitioning and parallel processing to further improve the overall speedup of parallel routing. In addition, we adopt MPI message to synchronize the intermediate results between different cores in parallel routing for a feasible solution. Experiments use a set of commonly used benchmarks to demonstrate the effectiveness of CPRS. Notably, CPRS achieves about 18× speedup on average using 32 processor cores with minor loss of quality, compared with the VTR 7.0 serial router. There is about 1.6× improvement over the state-of-the-art parallel router.

In this paper, we present a serial-equivalent parallel router for FPGAs on modern multi-core processors. We are based on the inherent net order of serial router to schedule all the nets into a series of stages, where the non-conflicting nets are scheduled in same stage and the conflicting nets are scheduled in different stages. We explore the parallel routing of non-conflicting nets on multi-core processors for a significant speedup. We perform the data synchronization of conflicting stages using MPI-based message queue for a feasible routing solution. Note that load balance is always used to guide the multi-core parallel routing. Experimental results show that our parallel router provides about 19.13× speedup on average using 32 processor cores comparing to the serial router. Notably, our parallel router generates exactly the same wirelength as the serial router satisfying serial equivalency.

With the prosperity of artificial intelligence, neural networks have been increasingly applied in healthcare for a variety of tasks for medical diagnosis and disease prevention. Mobile wearable devices, widely adopted by hospitals and health organizations, serve as emerging sources of medical data and participate in the training of neural network models for accurate model inference. Since the medical data are privacy-sensitive and non-shareable, federated learning has been proposed to train a model across decentralized data, which involves each mobile device running a training task with its own data in parallel. However, due to the ever-increasing size and complexity of modern neural network models, it becomes inefficient, and may even infeasible, to perform training tasks on wearable devices that are resource-constrained. In this paper, we propose a FEderated Edge Learning system, FEEL, for efficient privacy-preserving mobile healthcare. Specifically, we design an edge-based training task offloading strategy to improve the training efficiency. Further, we build our system on the basis of federated learning to make use of distributed user data to improve the inference performance. In addition, during model training, we provide a differential privacy scheme to strengthen the privacy protection. A prototype system has been implemented to evaluate the training efficiency, inference performance and noise sensitivity, respectively. And the results have demonstrated that our proposal could train models in an efficient and privacy-preserving way.

RAID-6 is gradually replacing RAID-5 as the dominant form of disk arrays due to its capability of tolerating concurrent failures of any two disks, as well as the case of encountering an uncorrectable read error during recovery. Implementing a RAID-6 system relies on some erasure coding schemes, and so far the most representative solutions are EVENODD codes [1], RDP codes [2] and Liberation codes [3], none of which has emerged as a clear "all-around" winner. In this paper, we are interested in revealing the undiscovered potential of the Liberation codes, since these codes have the following attractive features: (a) they have the best update performance, (b) they have better scalability, and (c) they are open-sourced and publicly available, as well as the following drawbacks: fair encoding performance and, more importantly, relatively poor decoding performance. Specificly, we present novel optimal encoding and decoding algorithms for the Liberation codes by introducing an alternative, geometric presentation of these codes. The proposed algorithms completely eliminate redundant computations during the encoding and decoding procedures by extracting and reusing common expressions between the two types of parity constraints, and do not involve any matrix operations on which the original algorithms are based. Our experiment results show that compared with the original solution, the proposed encoding and decoding algorithms reduce the number of XOR's by up to 16 percent and 15 ~20 percent respectively, and the encoding and decoding throughputs are increased by 22.3 percent and at most 155 percent respectively. Moreover, the encoding complexity reaches the theoretical lower bound, while the decoding complexity is also very close to the theoretical lower bound.

MOTIVATION: RNA secondary structure plays a vital role in fundamental cellular processes, and identification of RNA secondary structure is a key step to understand RNA functions. Recently, a few experimental methods were developed to profile genome-wide RNA secondary structure, i.e. the pairing probability of each nucleotide, through high-throughput sequencing techniques. However, these high-throughput methods have low precision and cannot cover all nucleotides due to limited sequencing coverage. RESULTS: Here, we have developed a new method for the prediction of genome-wide RNA secondary structure profile from RNA sequence based on the extreme gradient boosting technique. The method achieves predictions with areas under the receiver operating characteristic curve (AUC) >0.9 on three different datasets, and AUC of 0.888 by another independent test on the recently released Zika virus data. These AUCs are consistently >5% greater than those by the CROSS method recently developed based on a shallow neural network. Further analysis on the 1000 Genome Project data showed that our predicted unpaired probabilities are highly correlated (>0.8) with the minor allele frequencies at synonymous, non-synonymous mutations, and mutations in untranslated regions, which were higher than those generated by RNAplfold. Moreover, the prediction over all human mRNA indicated a consistent result with previous observation that there is a periodic distribution of unpaired probability on codons. The accurate predictions by our method indicate that such model trained on genome-wide experimental data might be an alternative for analytical methods. AVAILABILITY AND IMPLEMENTATION: The GRASP is available for academic use at https://github.com/sysu-yanglab/GRASP. SUPPLEMENTARY INFORMATION: Supplementary data are available online.

High-level synthesis (HLS) is important for compiling an application design onto field-programmable gate array (FPGA) but still faces challenges of balancing scalability and quality of results in the scheduling process. In this article, we propose an entropy-directed scheduling (EDS) algorithm that efficiently generates high-quality schedules for FPGA HLS. This article is novel in three ways. First, we make the first attempt to adopt entropy in the scheduling of HLS, which is an intuitive and robust measurement with lots of good analytic properties. Second, we creatively leverage the maximum entropy principle to describe the scheduling process, which is proved equivalent to the optimal solution in some particular cases. Third, we make EDS automatically analyze the input graph structure and leverage a three-stage scheduling process to obtain high-quality results. As a result, EDS has the lowest time complexity among existing scheduling algorithms and is flexible to solve both latency- and resource-constrained problems while satisfying other constraints. The experimental results show that for latency-constrained scheduling problem, EDS reduces up to 68% resource usage and is 294× faster than the force-directed scheduling algorithm. For resource-constrained scheduling problem, EDS obtains near-optimal solutions with an average speedup of 16 410× compared with ILP. To our best knowledge, this is the first EDS algorithm for FPGA HLS.

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13× speedup compared to the state-of-the-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.

With the advanced communication sensors are deployed into the modern connected vehicles (CVs), large amounts of traffic information can be collected in real-time, which gives the chance to explore the various techniques to control the routing of CVs in a ground traffic network. However, the control of CVs often suffers from energy inefficiency due to the constant changes of network capacity and traffic demand. In this paper, we propose a cost-based iterative framework, named EEPC, to explore the energy-efficient parallel control of connected vehicles. EEPC enables the control of CVs to iteratively generate a feasible solution, where the control of each vehicle is guided in an energy-efficient way routing on its own trajectory. EEPC eliminates the conflicts between CVs with a limited number of iterations and in each iteration, EEPC enables each vehicle to coordinate with other vehicles for a same road resource of the traffic network, further determining which vehicle needs the resource most. Note that at each iteration, the imposed cost is updated to guide the coordination between CVs while the energy is always used to guide the control of CVs in EEPC. In addition, we also explore the parallel control of CVs to improve the real-time performance of EEPC. We provide two parallel approaches, one is fine grain and the other is coarse grain. The fine grain performs the parallel control of single-vehicle routing while the coarse grain performs the parallel control of multi-vehicle routing. Note that fine grain adopts multi-threading techniques and coarse grain adopts MPI techniques. The simulation results show that the proposed EEPC can generate a feasible control solution. Notably, we also demonstrate that the generated solution is effective in eliminating the resource conflicts between CVs and in suggesting an energy-efficient route to each vehicle. To the best of our knowledge, this is the first work to explore energy-efficient parallel control of CVs.

State Machine Replication (SMR) is a fundamental fault tolerant technique for distributed systems. SMR traditionally requires sequential execution of commands at each replica node, so as to guarantee strong consistency among replicas. To achieve high performance at large scale cloud datacenters, SMR has been parallelized by employing multiple threads at each replica. In this paper, we propose SMR-X, a novel parallel SMR scheme, which realizes flexible mapping of commands for parallel executing at each replica. The mapping between clients' requests and work threads is dynamically adjusted according to the load level of work threads. Therefore, workloads of different threads can be well balanced and high system throughput can be achieved. The major challenge in our work lies in the inconsistency problem caused by dynamic changes in request-thread mapping. To cope with this, we design delicate mechanisms to synchronize mapping function, so that strong consistency among replicas can be guaranteed. The correctness of the proposed scheme is rigorously proved and its performance is evaluated via simulations. Simulation results show that SMR-X can achieve better load balance and lower access latency than existing parallel SMR schemes.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is limited due to higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on asymmetric multi-FPGA architectures. In this approach, the neural network mapping can be formulated as a resource allocation problem. We design a dynamic programming-based partitioning to solve this problem optimally. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Routing is a time-consuming step in the FPGA compilation flow. The parallelization of routing has the potential to reduce the time but imposes the dependent problem as the inherent order of nets. In this paper, we present Raparo, a resource-level angle-based parallel router. Raparo exploits angle-based region partitioning to drive the assignment of the nets for efficient parallel routing on the multi-core processor systems. Raparo parallelizes the routing at resource level rather than region level for the similar convergence as the serial router. Results show that Raparo can scale to 32 processor cores to provide about 16x speedup on average with acceptable impacts on the quality of results, comparing to the serial router.

In this paper, we propose Parrot, a more effective parallel routing approach that exploits angle-based space recursion partitioning for parallel FPGA routing. Parrot partitions entire routing region into two subregions such that all of the nets are assigned to three sets, where the first set consists of the nets that their terminal pins are distributed in two subregions and the other two sets consists of the nets that their terminal pins are located in their own respective subregions. Note that load balance is always used to guide the partitioning for a greater degree of parallelism. Moreover, all of the sets can be recursively partitioned in the same way to implement the scalable parallel routing and in each recursion, the first set is routed in serial before the other two sets are routed in parallel to generate the deterministic results. In addition, the synchronization overheads can be further reduced to improve the parallelism. Experimental results shows that Parrot can scale to 32 processor cores to provide about 16x speedup on average with acceptable impact on the quality of results. This is about 3x improvement over the state-of-the-art parallel router in terms of maximum average speedup.

Taxi demand prediction has recently attracted increasing research interest due to its huge potential application in large-scale intelligent transportation systems. However, most of the previous methods only considered the taxi demand prediction in origin regions, while ignoring the modeling of the specific situation of the destination passengers. In this paper, we present a more challenging task, called taxi origin-destination demand prediction, which aims at predicting the taxi demand between all origin-destination (OD) pairs in a future time interval. Its main challenges lie in how to effectively capture the diverse contextual information to learn the demand patterns. We address this problem with a novel Contextualized Spatial-Temporal Network (CSTN), which can effectively capture various context of taxi demand into a unified framework. Specifically, the proposed network consists of three components for the modeling of local spatial context (LSC), temporal evolution context (TEC) and global correlation context (GCC) respectively. Extensive experiments and evaluations on a large-scale dataset well demonstrate the significant superiority of our CSTN over other compared methods of taxi origin-destination demand prediction.

Crowd counting, aiming at estimating the total number of people in unconstrained crowded scenes, has increasingly received attention. But it is greatly challenged by the huge variation in people scale. In this paper, we propose a novel Multi-View Scale Aggregation Network (MVSAN), which handle the scale variation from feature, input and criterion view comprehensively. Firstly, we design a simple but effective Multi-Scale Feature Encoder, which exploits dilated convolution layers with various dilation rates to improve the representation ability and scale diversity of features. Secondly, we feed multiple scales of input images into networks to generate high-quality density maps in a coarse-to-fine manner. Finally, we propose a Multi-Scale Structural Similarity loss to force our networks to learn the local correlation of density maps. Extensive experiments on two standard benchmarks show that the proposed method can generate high-quality crowd density map and accurate count estimation, outperforming the state-of-the-art methods with a large margin.

The RΛ-Code is an efficient family of maximum distance separable (MDS) array codes of column distance 4, which involves two types of parity constraints: the row parity and the Λ parity formed by diagonal lines of slopes 1 and -1. Benefitting from the common expressions between the two parity constraints, the encoding and decoding complexities are distinctly lower than most (if not all) of other triple-erasure-correcting codes. It was left as an open problem generalizing the RΛ-Code to arbitrary column distances. In this paper, we present such a generalization, namely, we construct a family of MDS array codes being capable of correcting any prescribed number of erasures/errors by introducing multiple Λ parity constraints. Essentially, the generalized RΛ-Code is derived from a certain variant of the Blaum-Roth codes, and hence retains the error/erasure correcting capability of the latter. Compared with the Blaum-Roth codes, the generalized RΛ-Code has two advantages: a) by exploiting common expressions between row parity and different Λ parity constraints, and reusing the intermidate results during the syndrome calculations, it can encode and decode faster; and b) the memory footprint during encoding/decoding, and the I/O cost caused by degraded reads, are both reduced by 50%.

Although emerging non-volatile memories (NVMs) have been comprehensively studied to design next-generation memory systems, the symmetry of the crossbar structure adopted by most NVMs has not been addressed. In this work, we argue that crossbar-based NVMs can enable dual-addressing memory architecture, i.e., RC-NVM, to support both row- and column-oriented memory accesses for workloads with different access patterns. Through circuit-level analysis, we first prove that such a dual-addressing architecture is only practical with crossbar-based NVMs rather than DRAM. Then, we introduce the RC-NVM architecture from bank, chip and module levels, and propose RC-NVM aware memory controller. We also address the challenges to implement the end-to-end RC-NVM system. Especially, we design a novel protocol to solve the cache synonym problem with very little overhead. Finally, we introduce the deployment of RC-NVM for in-memory databases (IMDBs) and evaluate its performance with IMDBs and well-optimized general matrix multiply (GEMM) workloads. Experimental results show that with only 10 percent area overhead 1) the memory access performance of IMDBs can be improved up to 14.5X, and 2) for GEMM, RC-NVM naturally supports SIMD operations and outperforms the best tiled layout by 19 percent.

Deduplication has become a widely deployed technology in cloud data centers to improve IT resources efficiency. However, traditional techniques face a great challenge in big data deduplication to strike a sensible tradeoff between the conflicting goals of scalable deduplication throughput and high duplicate elimination ratio. We propose AppDedupe, an application-aware scalable inline distributed deduplication framework in cloud environment, to meet this challenge by exploiting application awareness, data similarity and locality to optimize distributed deduplication with inter-node two-tiered data routing and intra-node application-aware deduplication. It first dispenses application data at file level with an application-aware routing to keep application locality, then assigns similar application data to the same storage node at the super-chunk granularity using a handprinting-based stateful data routing scheme to maintain high global deduplication efficiency, meanwhile balances the workload across nodes. AppDedupe builds application-aware similarity indices with super-chunk handprints to speedup the intra-node deduplication process with high efficiency. Our experimental evaluation of AppDedupe against state-of-the-art, driven by real-world datasets, demonstrates that AppDedupe achieves the highest global deduplication efficiency with a higher global deduplication effectiveness than the high-overhead and poorly scalable traditional scheme, but at an overhead only slightly higher than that of the scalable but low duplicate-elimination-ratio approaches.

PIM (processing-in-memory) based hardware accelerators have shown great potentials in addressing the computation and memory access intensity of modern CNNs (convolutional neural networks). While adopting NVM (non-volatile memory) helps to further mitigate the storage and energy consumption overhead, adopting quantization, e.g., shift-based quantization, helps to tradeoff the computation overhead and the accuracy loss, integrating both NVM and quantization in hardware accelerators leads to sub-optimal acceleration. In this paper, we exploit the natural shift property of DWM (domain wall memory) to devise DWMAcc, a DWM-based accelerator with asymmetrical storage of weight and input data, to speed up the inference phase of shift-based CNNs. DWMAcc supports flexible shift operations to enable fast processing with low performance and area overhead. We then optimize it with zero-sharing , input-reuse , and weight-share schemes. Our experimental results show that, on average, DWMAcc achieves 16.6× performance improvement and 85.6× energy consumption reduction over a state-of-the-art SRAM based design.

Recognizing objects from simultaneously sensed photometric (RGB) and depth channels is a fundamental yet practical problem in many machine vision applications, such as robot grasping and autonomous driving. In this paper, we address this problem by developing a cross-modal attentional context (CMAC) learning framework, which enables the full exploitation of the context information from both RGB and depth data. Compared to existing RGB-D object detection frameworks, our approach has several appealing properties. First, it consists of an attention-based global context model for exploiting adaptive contextual information and incorporating this information into a region-based CNN (e.g., fast RCNN) framework to achieve improved object detection performance. Second, our CMAC framework further contains a fine-grained object part attention module to harness multiple discriminative object parts inside each possible object region for superior local feature representation. While greatly improving the accuracy of RGB-D object detection, the effective cross-modal information fusion as well as attentional context modeling in our proposed model provide an interpretable visualization scheme. Experimental results demonstrate that the proposed method significantly improves upon the state of the art on all public benchmarks.

In the aftermath of earthquakes, floods, and other disasters, photos are increasingly playing more significant roles, such as finding missing people and assessing disasters, in rescue and recovery efforts. These disaster photos are taken in real time by the crowd, unmanned aerial vehicles, and wireless sensors. However, communications equipment is often damaged in disasters, and the very limited communication bandwidth restricts the upload of photos to the cloud center, seriously impeding disaster rescue endeavors. Based on edge computing, we propose Echo, a highly time-efficient disaster rescue framework. By utilizing the computing, storage, and communication abilities of edge servers, disaster photos are preprocessed and analyzed in real time, and more specific visuals are immensely helpful for conducting emergency response and rescue. This article takes the search for missing people as a case study to show that Echo can be more advantageous in terms of disaster rescue. To greatly conserve valuable communication bandwidth, only significantly associated images are extracted and uploaded to the cloud center for subsequent facial recognition. Furthermore, an adaptive photo detector is designed to utilize the precious and unstable communication bandwidth effectively, as well as ensure the photo detection precision and recall rate. The effectiveness and efficiency of the proposed method are demonstrated by simulation experiments.

Field Programmable Gate Arrays (FPGAs) are reconfigurable architectures able to provide a good balance between energy efficiency and flexibility with respect to CPUs and ASICs. The main drawback in using FPGAs, however, is their timing-consuming routing process, significantly hindering the designer productivity. An emerging solution to this problem is to accelerate the routing by parallelization. Existing attempts of parallelizing the FPGA routing either do not fully exploit the parallelism or suffer from an excessive quality loss. Massive parallelism using GPUs has the potential to solve this issue but faces non-trivial challenges. To cope with these challenges, this paper explores GPU-accelerated routing approach for FPGAs. We leverage the idea of problem size reduction by limiting the single-net routing in a small subgraph rather than in an entire graph, further enabling the GPU-friendly shortest path algorithm to be used in FPGA routing. We maintain the convergence after problem size reduction by using the dynamic expansion of the routing resource subgraph, where the routing region of subgraph will be progressively expanded to find a feasible solution to each net. In addition, we are based on a GPU platform to explore the fine-grained single-net parallel routing in three ways and propose a hybrid approach to combine the static and dynamic parallelization for better speedup in FPGA routing. To explore the coarse-grained multi-net parallelization, We propose a dynamic programming-based partitioning algorithm to parallelize the routing of multiple nets while generating the equivalent routing results as the original single-net routing. Experimental results show that our proposed approach can provide an average of about 21.53× speedup on a single GPU with a tolerable loss in the routing quality and maintain a scalable speedup on large-scale routing resource graphs. To our knowledge, this is the first work to demonstrate the effectiveness of GPU-accelerated routing for FPGAs.

FPGA is reconfigurable architecture able to implement a good trade-off in terms of energy, performance, and flexibility. However, the main drawback in using FPGAs is their very long routing time. Multi-core processors are now ubiquitous, making parallelism an increasingly attractive direction to accelerate the routing time. In this paper, we propose a task-level distributed parallel router that exploits conflict-aware box expansion and equal-sized grid partitioning for parallel FPGA routing. In box expansion, we adopt net bounding box to limit the search space of routing and based on current congestion state among nets, we design conflict-aware box expansion to optimize the serial routing time and provide more non-conflicting nets to obtain significant parallelism. In grid partitioning, we employ equal-sized grid to partition the overall routing region, where the nets in same grid are routed in serial and the grids are processed in parallel. Specifically, the nets distributed in multiple grids can be used to balance the workloads among processor cores. Experiments show that the parallel implementation scales to an average speedup of about 21 × using 32 processor cores compared to state-of-the-art VPR router.

Serial equivalency can provide easier regression testing and customer support in production-grade CAD software. While existing parallel routing techniques have become sufficiently advanced to accelerate the execution time, support for serial equivalency has been very limited or ignored due to it was considered costly. In this paper, we propose serial-equivalent parallel routing for FPGAs. We use an optimal dependency-aware scheduling to facilitate serial equivalency of parallel routing algorithm. This capability enables the same answer as the serial version of the parallel algorithm, regardless of how many processing cores are used. We also validate this property across different hardware platforms. Further experimental results show that we achieve a 14.27x speedup on the MPI-based distributed parallel computer and a 19.65x speedup on the GPU-based massively parallel machine. To our knowledge, it is the first parallel routing with a serial equivalency guarantee.

Placement is probably the most critical process in the FPGA design flow. The demand for high performance continues to increase, but existing placers are still faced with numerous challenges including very long runtime, poor scalability, and restricted space exploration. In this paper we propose a novel timing-driven placement algorithm called BoxPlacer, which is supported by the force directed concept. BoxPlacer firstly uses a simple policy to create the initial box for placement. Then a force-directed iterative scheme is used to reduce the box size and determine the global placement. At last, the same concept is employed to eliminate the overlaps between reduced boxes to ensure the legalization in detailed placement. Notice that timing is always used to drive the placement in BoxPlacer. We demonstrate the effectiveness of our BoxPlacer by comparing the experimental results with that produced by the academic simulated annealing-based placer. Notably, our BoxPlacer achieves on average about 8x runtime advantage with 9% smaller critical path delay and 6% shorter wirelength.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single-FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is very limited due to they require higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on an asymmetric multi-FPGA architecture. Relative to the state-of-the-art single-FPGA resource reuse for large-scale DNNs, we consider multi-FPGA fashion to strive for higher performance. In this fashion, the neural network mapping problem can be formulated as a resource allocation problem, and a dynamic programming-based partitioning is designed to solve this problem optimally. Notice that the network topology and communication bandwidth of multiple FPGAs are always used to guide the partitioning to boost the performance while satisfying the constraints of resource-performance trade-off in a single FPGA. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Packing is one of the most critical stages in the FPGA physical syntheses flow. In this paper, we propose DP-Pack, a distributed parallel packing approach. DP-Pack consists of two primary steps. First, all of the minimal circuit units are assigned into several subsets where the conflicting units are located in the same subset and the non-conflicting units are distributed in different subsets. Then, the non-conflicting subsets are partitioned by round robin such that the number of subsets in each processor core is equal approximately, leading to good load balance in parallel packing. Second, the parallelization between processor cores is implemented by the MPI-based message queue in a distributed platform. Note that DP-Pack has been integrated into the VTR 7.0 tool. Experimental results show that our DP-Pack scales to 8 processor cores to provide about 1.4~3.2× runtime advantages with acceptable quality degradation, comparing to the academic state-of-the-art AAPack.

Ever increasing DRAM capacity has fostered the development of in-memory databases (IMDB). The massive performance improvements provided by IMDBs have enabled transactions and analytics on the same database. In other words, the integration of OLTP (on-line transactional processing) and OLAP (on-line analytical processing) systems is becoming a general trend. However, conventional DRAM-based main memory is optimized for row-oriented accesses generated by OLTP workloads in row-based databases. OLAP queries scanning on specified columns cause so-called strided accesses and result in poor memory performance. Since memory access latency dominates in IMDB processing time, it can degrade overall performance significantly. To overcome this problem, we propose a dual-addressable memory architecture based on non-volatile memory, called RC-NVM, to support both row-oriented and column-oriented accesses. We first present circuit-level analysis to prove that such a dual-addressable architecture is only practical with RC-NVM rather than DRAM technology. Then, we rethink the addressing schemes, data layouts, cache synonym, and coherence issues of RC-NVM in architectural level to make it applicable for IMDBs. Finally, we propose a group caching technique that combines the IMDB knowledge with the memory architecture to further optimize the system. Experimental results show that the memory access performance can be improved up to 14.5X with only 15% area overhead.

In-memory databases (IMDBs) store all working data in main memory, which makes memory accesses become the dominant factor of the whole system performance. Micro-architectural studies of mainstream in-memory on-line transaction processing (OLTP) systems show that more than half of the execution time goes to memory stalls. Moreover, for IMDBs that adopt aggressive transaction compilation optimizations, data misses from the last-level cache (LLC) are responsible for the majority of the overall stall time. In this paper, through profiling analysis of IMDBs we observe that index access misses dominate LLC data misses. Based on the key observation that adjacent keys tend to follow similar traversal paths in ordered index searches, we propose the path prefetching to mitigate LLC misses induced by ordered index searches, which records mappings between keys and their traversal paths and then generate prefetches for future same/adjacent keys. Experimental results show that for ordered index searches the proposed path prefetcher provides an average speedup of 27.4% over the baseline with no prefetching.

FPGAs are reconfigurable architectures that can offer large performance and energy improvements over general purpose processors. However, compiling an application design onto the underlying FPGA device takes commonly too much time to allow efficient design turnaround times, significantly hindering designer productivity. Routing is always a very timing-consuming and critical process in FPGA compilation flow. To reduce FPGA routing time, parallel techniques have become more popular in recent years. In this paper, we propose a fine-grained GPU-based parallel routing approach that enables high concurrent single-net parallel routing for large-scale FPGAs. The proposed approach is novel in three ways. The first is Scheme-1. We route a single net only on its own bounding box rather than entire routing resource graph and then selectively expand its bounding box to make sure that single-net routing has a feasible solution. The second is Scheme-2. We impose a GPU thread to each node and perform path searching in dynamic programming algorithm on all the nodes simultaneously for single-net parallel routing on a single GPU. Note that these nodes are distributed in the bounding box of single net. The third is optimized Scheme-2. We attempt to partition single-net routing box into several sub-boxes, each of which is processed in a shared memory of GPU to enable high scalability and parallelism. Our evaluation with ten large designs from the academic VTR benchmark suite shows that our approach of combining the approximation of VPR 7.0 router (Scheme-1) and its parallelization (optimized Scheme-2) provides a 1.57x speedup improvement compared to the best parallelization-only approach of the original VPR 7.0 router, though at a small quality deterioration.

Routing is probably the most time-consuming stage in the FPGA compilation flow. While parallelization has the potential to reduce the routing time, load imbalance still arises in parallel routing process, resulting in the degradations of speedup and quality of results. Furthermore, when scaling the number of processing cores, load imbalance will become more severe in parallel routing. In this paper, we explore load balance-aware parallel routing to obtain significant speedup. To study load balance problem, we implement a basic MPI-based parallel routing framework on multi-core distributed-memory platform. This framework provides two dynamic partitioning algorithms and both of them can automatically maintain the load balance of parallel routing at runtime. The first is the heuristic algorithm and it is able to assign more nets to fast MPI processes by removing an equal number of nets from slow MPI processes. The second algorithm selects the re-partitioning of the nets for all the MPI processes at each iteration, further leading to a good load balance during parallel routing. The key idea of these two algorithms is to analyze the behaviours of previous iteration to guide the parallelization of next iteration. Results show that the effectiveness and efficiency of the two algorithms in multi-core distributed-memory parallel routing framework. Notably, our parallel router can achieve about 6× speedup on average using 8 MPI processes, comparing to the serial router. This is a 1.2× improvement over a state-of-the-art multi-core parallel router.

Apache Spark is a lightning-fast unified analytics engine for large-scale data processing. When executing an application with Spark, it runs many jobs in parallel. These jobs are divided into stages based on the shuffle boundary. However, shuffling data across the stages in a cluster is time-consuming because it will place significant burden on operating system on both the source and the destination by requiring many remote files and network I/Os. Meanwhile, the latest Spark is based on Netty which is written with Java Sockets and will produce a large number of data copies during the shuffle phase. This has become the major bottleneck for Apache Spark and motivates us to use RDMA technology to accelerate data shuffle. RDMA, with the function of zero-copy transfers, reducing latency and CPU overhead, can reduce stress on operating system during the shuffle phase and improve the throughput of the whole system. In this paper, we present a high-performance RDMA-based design for accelerating data shuffle in Apache Spark framework by providing tiering memory pool and different mechanisms to transfer messages of different sizes. The experimental results show that compared to the default Spark running with IP over InfiniBand (IPoIB), our proposed design can achieve up to 89.8% performance improvement for Spark RDD operation benchmarks (e.g., GroupBy and SortBy), up to 49% performance improvement for iterative algorithms (e.g., TriangleCount and SVM in SparkBench). And the evaluation results also show that our RDMA-based design slightly outperforms Crail-Spark-IO, a recent open-source Spark shuffle plugin from IBM.

Given a scientific collaboration network, how can we find a group of collaborators with high research indicator (e.g., h-index) and diverse research interests? Given a social network, how can we identify the communities that have high influence (e.g., PageRank) and also have similar interests to a specified user? In such settings, the network can be modeled as a multi-valued network where each node has d ($d \ge 1$) numerical attributes (i.e., h-index, diversity, PageRank, similarity score, etc.). In the multi-valued network, we want to find communities that are not dominated by the other communities in terms of d numerical attributes. Most existing community search algorithms either completely ignore the numerical attributes or only consider one numerical attribute of the nodes. To capture d numerical attributes, we propose a novel community model, called skyline community, based on the concepts of k-core and skyline. A skyline community is a maximal connected k-core that cannot be dominated by the other connected k-cores in the d-dimensional attribute space. We develop an elegant space-partition algorithm to efficiently compute the skyline communities. Two striking advantages of our algorithm are that (1) its time complexity relies mainly on the size of the answer s (i.e., the number of skyline communities), thus it is very efficient if s is small; and (2) it can progressively output the skyline communities, which is very useful for applications that only require part of the skyline communities. Extensive experiments on both synthetic and real-world networks demonstrate the efficiency, scalability, and effectiveness of the proposed algorithm.

To avoid the exhaustive search over locations and scales, current state-of-the-art object detection systems usually involve a crucial component generating a batch of candidate object proposals from images. In this paper, we present a simple yet effective approach for segmenting object proposals via a deep architecture of recursive neural networks (ReNNs), which hierarchically groups regions for detecting object candidates over scales. Unlike traditional methods that mainly adopt fixed similarity measures for merging regions or finding object proposals, our approach adaptively learns the region merging similarity and the objectness measure during the process of hierarchical region grouping. Specifically, guided by a structured loss, the ReNN model jointly optimizes the cross-region similarity metric with the region merging process as well as the objectness prediction. During inference of the object proposal generation, we introduce randomness into the greedy search to cope with the ambiguity of grouping regions. Extensive experiments on standard benchmarks, e.g., PASCAL VOC and ImageNet, suggest that our approach is capable of producing object proposals with high recall while well preserving the object boundaries and outperforms other existing methods in both accuracy and efficiency.

Deduplication has become essential in disk-based backup systems, but there have been few long-term studies of backup workloads. Most past studies either were of a small static snapshot or covered only a short period that was not representative of how a backup system evolves over time. For this article, we first collected 21 months of data from a shared user file system; 33 users and over 4,000 snapshots are covered. We then analyzed the dataset, examining a variety of essential characteristics across two dimensions: single-node deduplication and cluster deduplication. For single-node deduplication analysis, our primary focus was individual-user data. Despite apparently similar roles and behavior among all of our users, we found significant differences in their deduplication ratios. Moreover, the data that some users share with others had a much higher deduplication ratio than average. For cluster deduplication analysis, we implemented seven published data-routing algorithms and created a detailed comparison of their performance with respect to deduplication ratio, load distribution, and communication overhead. We found that per-file routing achieves a higher deduplication ratio than routing by super-chunk (multiple consecutive chunks), but it also leads to high data skew (imbalance of space usage across nodes). We also found that large chunking sizes are better for cluster deduplication, as they significantly reduce data-routing overhead, while their negative impact on deduplication ratios is small and acceptable. We draw interesting conclusions from both single-node and cluster deduplication analysis and make recommendations for future deduplication systems design.

Both traditional coarse-grained and fine-grained Flash Translation Layer schemes are unsuitable for ultra-large SSDs. They produce overmuch mapping entries which fail to be kept in embedded DRAM completely and can suffer severely from low spatial and temporal localities. In this paper, we propose a novel KV-FTL for ultra-large SSDs, which mostly maps logical addresses to physical addresses via a simple hash function, while handles hash collisions and out-of-place data updates by the traditional manner, i.e., the mapping table. Our KV-FTL can accelerate address translation by avoiding loading mapping table from flash memory to DRAM, thus improve performance; as well as reduce the write-traffic incurred by the mapping table, thus extend the lifespan of SSDs. Experimental results show that our KV-FTL facilitates SSDs to survive longer lifespan by a factor of up to 18.7% with an average of 13.6%; improves read performance ranging from 18.4% to 50.7% with an average of 39% with optimization, and in the case of extremely intensive requests, improves the access performance for requests with an average of 47%.

Emerging non-volatile memories enable persistent memory, which offers the opportunity to directly access persistent data structures residing in main memory. In order to keep persistent data consistent in case of system failures, most prior work relies on persist ordering constraints which incurs significant overheads. Strand persistency minimizes persist ordering constraints. However, there is still no proposed persistent memory design based on strand persistency due to its implementation complexity. In this work, we propose a novel persistent memory system based on strand persistency, called SPMS. SPMS consists of cacheline-based strand group tracking components, a volatile strand buffer and ultra-capacitors incorporated in persistent memory modules. SPMS can track each strand and guarantee its atomicity. In case of system failures, committed strands buffered in the strand buffer can be flushed back to persistent memory within the residual energy window provided by the ultra-capacitors. Our evaluations show that SPMS outperforms the state-of-the-art persistent memory system by 6.6% and has slightly better performance than the baseline without any consistency guarantee. What's more, SPMS reduces the persistent memory write traffic by 30%, with the help of the strand buffer.

Routing is a time-consuming process in the FPGA design flow. Parallelization is a promising direction to accelerate the routing. While synchronous parallelization can converge a feasible solution, the ideal speedup is rarely achieved due to excessive communication overheads. Asynchronous parallelization can provide an almost linear speedup, but it is difficult to converge in the limited number of iterations due to net dependency. In this paper we propose SAPRoute, which coordinates synchronous and asynchronous parallelism on distributed multiprocessing environment to accelerate the routing for FPGAs. The objective is to boost the more speedup of parallel routing algorithm under the requirement of convergence. To the best of our knowledge, this is the first work to study the impact of synchronization and asynchronization during parallelization. Experimental results show that our approach have negligible explicit synchronization overhead and achieves significant speedup improvement over a set of commonly used benchmarks. Notably, SAPRoute produces the speedup of 24.27× on average compared to the default serial solution.

Quantitative effects of Moore's Law have driven qualitative changes in FPGA architecture, applications, and tools. As a consequence, the existing EDA tools takes several hours or even days to implement the applications onto FPGAs. Typically, routing is a very time-consuming process in the EDA design flow. While several attempts have accelerated this process through parallelization, they still do not provide a strong parallel scheme for FPGA routing. In this paper we introduce a dependency-aware parallel approach, named Bamboo, to accelerate the routing time for FPGAs. With the dependency detection, Bamboo partitions the nets into multiple subsets, where the nets in the same subsets are independent, and the dependency only exists among different subsets. Specifically, the independent nets in the same subset are routed in parallel, and the subsets are processed in serial according to the original routing ordering. The partitioning problem is solved optimally using dynamic programming, and the parallelization is implemented by speculative parallelism on a single GPU. Experimental results show that our approach achieves an average of 15.13x speedup with negligible influence on the routing quality. Most importantly, it effectively maintains deterministic results and always produces the same results as the serial version.

The extremely strict code length constraint is the main drawback of lowest density, maximum-distance separable (MDS) array codes of distance greater than 3. To break away from the status quo, we proposed in [5] a family of lowest density MDS array codes of (column) distance 4, called XI-Code. Compared with the previous alternatives, XI-Code has lower encoding and decoding complexities, and much looser constraint on the code length, thus is much more practical. In this paper, we present a new family of lowest density MDS array codes of (column) distance 4, called RA-Code, which is derived from XI-Code, and outperforms the latter substantially in terms of encoding complexity, decoding complexity, and memory consumption during encoding/decoding. The inherent connection between RA-Code and XI-Code and how the former is derived from the latter may provide inspiration for the readers to derive new codes from other existing codes in a similar way.

Photos obtained via crowdsourcing can be used in image sensing for disaster management. Due to the weak communication environment after a disaster, it is difficult to transfer the huge amount of crowdsourced photos. To address this problem, we propose COCO, a content-aware crowdsourcing system that leverages edge computing to support real-time image sensing in disaster environment. COCO filters the crowdsourced images at the data source and only uploads the images that contain relevant objects which the application is interested in. We use a machine-learning based computer vision detector to understand the content of images. Considering the resource constraints of mobile devices, we implement the computer vision detector at the edge server which located in the close proximity to data source. As the unstable network bandwidth is normal in disaster environment, we propose an adaptive mechanism to further improve the sensing performance. We have implemented the COCO prototype which is evaluated via a real-world dataset. The experimental results demonstrate the effectiveness of COCO.

As the expected emerging Non-Volatile Memory (NVM) technologies, such as 3DXPoint, are in production, there has been a recent push in the big data processing community from storage-centric towards memory-centric. Generally, in large-scale systems, distributed memory management through traditional network with TCP/IP protocol exposes performance bottleneck. Briefly, CPU- centric network involves context switching, memory copy etc. Remote Direct Memory Access (RDMA) technology reveals the tremendous performance advantage over than TCP/IP: Allowing access to remote memory directly bypassing OS kernel. In this paper, we propose Megalloc, a distributed NVM allocator exposes NVMs as a shared address space of a cluster of machines based-on RDMA. Firstly, it makes memory allocation metadata accessed directly by each machine, allocating NVM in coarse-grained way; secondly, adopting fine-grained memory chunk for applications to read or store data; finally, it guarantees high distributed memory allocation performance.

Thread migration is ubiquitous in multi-core architectures. When a thread migrates to a new core, the branch information of the branch predictor on new core is absent, which will lead to the predictor won't work as intended until the warm-up finish. In this poster, we point out that, when a thread migrates to a new core, the warm-up time of branch predictors can be reduced by migrating branch history information from the source core to the target. In addition, we improve branch prediction accuracy by migrating branch history information including prediction tables and GHR. Moreover, several migration strategies are introduced to fully exploit the performance of branch predictor migration. Preliminary performance results shows that, compared to the experiment baseline which dosen't migrate any branch history information, branch prediction migration reduces MPKI of the branch predictor on new core by 43.46% on average.

The non-volatile memory (NVM) has the merits of byte-addressability, fast speed, persistency and low power consumption, which make it attractive to be used as main memory. Commonly, user process dynamically acquires memory through memory allocators. However, traditional memory allocators designed with in-place data writes are not appropriate for the non-volatile main memory (NVRAM) due to the limited endurance. In this article, first, we quantitatively analyze the wear-oblivious of DRAM-oriented designed allocator—glibc malloc and the inefficiency of wear-conscious allocator NVMalloc. Then, we propose WAlloc, an efficient wear-aware manual memory allocator designed for NVRAM: (1) decouples metadata and data management; (2) distinguishes metadata with volatility; (3) redirects the data writes around to achieve wear-leveling; (4) redesigns an efficient and effective NVM copy mechanism, bypassing the CPU cache partially and prefetching data explicitly. Finally, experimental results show that the wear-leveling of WAlloc outperforms that of NVMalloc about 30% and 60% under random workloads and well-distributed workloads, respectively. Besides, WAlloc reduces the average data memory writes in 64 bytes block by 1.5 times comparing with glibc malloc. With the fulfillment of data persistency, cache bypassing NVM copy is better than cache line flushing NVM copy with performance improvement circa 14%.

In recent years, erasure codes have become the de facto standard for data protection of large scale distributed cloud storage systems at the cost of an affordable storage overhead. While traditional erasure coding schemes, such as Reed-Solomon codes, suffer from high reconstruction cost and I/Os. The recent past has seen a plethora of efforts to optimize the tradeoff between the reconstruction cost, I/Os and storage overhead. Quietly different from all prior studies, in this paper, our erasure coding technology makes the first attempt to take advantage of the unequal failure rates across the disks/nodes to optimize the reconstruction performance and system reliability. Specifically, our proposed technology, the Unequal Failure Protection based Local Reconstruction Code (UFP-LRC) divides the data blocks into several unequal-sized groups with local parities, assigning the data blocks stored on more failure-prone disks/nodes into the smaller-sized group, so as to provide unequal failure protection for each group. In this way, by exploiting the nonuniform local parity degrees, the proposed UFP-LRC enables the data blocks that are stored on more failure-prone disks/nodes to tolerate a greater number of failures while suffer from less repair cost than others, leading to a substantial improvement of overall repair performance and reliability for cloud storage system. We perform numerical analysis and build a prototype storage system to verify our approach. The analytical results show that the UFPLRC technique gradually outperforms LRC along the increase of failure rate ratio. Also, extensive experiments show that, when compared to LRC, UFP-LRC is able to achieve a 10% to 13% improvement in throughput, and a 8% to 12% reduction in decoding latency, while retaining a comparable overall reliability.

To facilitate efficient context switches, GPUs usually employ a large-capacity register file to accommodate a massive amount of context information. However, the large register file introduces high power consumption, flowing to high leakage power SRAM cells. Emerging non-volatile STT-RAM memory has recently been studied as a potential replacement to alleviate the leakage challenge when constructing register files on GPUs. Unfortunately, due to the long write latency and high energy consumption associated with write operations in STT-RAM, simply replacing SRAM with STTRAM for register files would incur non-trivial performance overhead and only bring marginal energy benefits.

To address the high energy consumption issue of SRAM on GPUs, emerging Spin-Transfer Torque (STT-RAM) memory technology has been intensively studied to build GPU register files for better energy-efficiency, thanks to its benefits of low leakage power, high density, and good scalability. However, STT-RAM suffers from a reliability issue, read disturbance, which stems from the fact that the voltage difference between read current and write current becomes smaller as technology scales. The read disturbance leads to high error rates for read operations, which cannot be effectively protected by SECDEC ECC on large-capacity register files of GPUs.

NoSQL systems are deployed as the core components for delivering big data Web services today. With growing main memory capacity, we witness the growing interest and deployment of in-memory NoSQL services (IM-NoSQL), which are designed to maximize the utilization of DRAM for ultra low latency services. To address the volatility of DRAM for in-memory computing services, persistence and failure recovery are important functionality for IM-NoSQL. In this paper we report an extensive measurement study on the performance of persistence and recovery for IM-NoSQL. We evaluate the performance and effectiveness of several common mechanisms used for persistence and recovery in the presence of server crashes, such as snapshot and logging based approaches. Through this study, we are able to answer some of the most frequently asked questions in provisioning of IM-NoSQL services: (i) Can an IM-NoSQL system work effectively when the available memory is insufficient to load the whole dataset? (ii) What is the overhead of maintaining snapshot compared to logging? (iii) How fast an IM-NoSQL system can recover in the presence of failure? And (iv) how does an IM-NoSQL system respond to the different persistence models? We report our comprehensive measurement results on execution, persistence and recovery performance of Redis, a representative implementation of IM-NoSQL services.

High-Performance network technology, Remote Direct Memory Access (RDMA), has revealed its tremendous advantage over traditional TCP/IP. With its ultra-low latency and high bandwidth, RDMA has been extensively adopted in distributed environment, especially for in-memory key-value stores. However, although RDMA does provide the ability to interact with remote user space memory directly, memory copy still exists between data memory area and communication memory area with two-sided communication semantics in in-memory key-value store. In addition, using high performance one-sided communication semantics will expose memory totally, hence an inadvertent corrupt data operation could crash system. In this paper, we propose a tactful cache mechanism for RDMA-based in-memory key-value store -- InnerCache. Our design concerns two dimensions with respect to improve the system performance with two-sided communication semantics and make system less vulnerable. It merges one-sided and two-sided communication model through making communication memory cacheable. Experimental results show that InnerCache can efficiently improve the performance of RDMA-based in-memory key-value store.

Deduplication has become essential in disk-based backup systems, but there have been few long-term studies of backup workloads. Most past studies either were of a small static snapshot or covered only a short period that was not representative of how a backup system evolves over time. For this paper, we collected 21 months of data from a shared user file system; 33 users and over 4,000 snapshots are covered. We analyzed the data set for a variety of essential characteristics. However, our primary focus was individual user data. Despite apparently similar roles and behavior in all of our users, we found significant differences in their deduplication ratios. Moreover, the data that some users share with others had a much higher deduplication ratio than average. We analyze this behavior and make recommendations for future deduplication systems design.

To address the high energy consumption issue of SRAM on GPUs, emerging Spin-Transfer Torque (STT-RAM) memory technology has been intensively studied to build GPU register files for better energy-efficiency, thanks to its benefits of low leakage power, high density, and good scalability. However, STT-RAM suffers from the read disturbance issue, which stems from the fact that the voltage difference between read current and write current becomes smaller as technology scales. The read disturbance leads to high error rates for read operations, which cannot be effectively protected by the SEC-DED ECC on large-capacity register files of GPUs. Prior schemes (e.g., read-restore) to mitigate the read disturbance usually incur either non-trivial performance loss or excessive energy overhead, thus not applicable for the GPU register file design that aims to achieve both high performance and energy-efficiency. To combat the read disturbance, we propose a novel software-hardware co-designed solution (i.e., Red-Shield ), which consists of three optimizations to overcome the limitations of the existing solutions. First, we identify dead reads at compiling stage and augment instructions to avoid unnecessary restores. Second, we employ a small read buffer to accommodate register reads with high-access locality to further reduce restores. Third, we propose an adaptive restore mechanism to selectively pick the suitable restore scheme, according to the busy status of corresponding register banks. Experimental results show that our proposed design can effectively mitigate the performance loss and energy overhead caused by restore operations while still maintaining the reliability of reads.

Solid State Drives (SSDs) have been extensively deployed as the cache of hard disk-based storage systems. The SSD-based cache generally supplies ultra-large capacity, whereas managing so large a cache introduces excessive memory overhead, which in turn makes the SSD-based cache neither cost-effective nor energy-efficient. This work targets to reduce the memory overhead introduced by the replacement policy of SSD-based cache. Traditionally, data structures involved in cache replacement policy reside in main memory. While these in-memory data structures are not suitable for SSD-based cache any more since the cache is much larger than ever. We propose a memory-efficient framework which keeps most data structures in SSD while just leaving the memory-efficient data structure (i.e., a new bloom proposed in this work) in main memory. Our framework can be used to implement any LRU-based replacement policies under negligible memory overhead. We evaluate our proposals via theoretical analysis and prototype implementation. Experimental results demonstrate that, our framework is practical to implement most replacement policies for large caches, and is able to reduce the memory overhead by about$10 \times$.

NoSQL systems have become the vital components to deliver big data services in the Cloud. However, existing NoSQL systems rely on experienced administrators to configure and tune the wide range of configurable parameters in order to achieve high performance. In this paper, we present a policy-driven configuration management system for NoSQL systems, called PCM. PCM can identify workload sensitive configuration parameters and capture the tuned parameters for different workloads as configuration policies. PCM also can be used to analyze the range of configuration parameters that may impact on the runtime performance of NoSQL systems in terms of read and write workloads. The configuration optimization recommended by PCM can enable NoSQL systems such as HBase to run much more efficiently than the default settings for both individual worker node and entire cluster in the Cloud. Our experimental results show that HBase under the PCM configuration outperforms the default configuration and some simple configurations on a range of workloads with offering significantly higher throughput.

The non-volatile memory (NVM) has the illustrious merits of byte-addressability, fast speed, persistency and low power consumption, which make it attractive to be used as main memory. Commonly, user process dynamically acquires memory through memory allocators. However, traditional memory allocators designed with in-place data writes are not appropriate for non-volatile main memory (NVRAM) due to the limited endurance. For instance, the number of write operations is merely 108 times per PCM cell. In this paper, we quantitatively analyze the wear-oblivious of DRAM-oriented designed allocator-glibc malloc and the inefficiency of wear-conscious allocator-NVMalloc. For example, the average imbalance factor (the maximum/the average) of memory allocation is about 7.5 and 3, respectively. Based on our observations, we propose WAlloc, an efficient wear-aware manual memory allocator designed for NVRAM, decouples metadata and data, uses Less Allocated First Out allocation policy and redirects the data writes. Experimental results show that the wear-leveling of WAlloc outperforms that of NVMalloc about 30% and 60% under random workloads and well-distributed workloads, respectively. In addition, considering the trade-off between space and wear-leveling, WAlloc reduces average data memory writes in 64 bytes block by average 1.5X comparing with malloc with almost 8% extra space overhead.

NAND flash-based Solid State Drives (SSDs) have been widely deployed in data centers of cloud computing due to their high performance compared with hard disks, while the limited lifespan of flash memory makes SSDs not very suitable for write-intensive applications. Deduplication is an effective method used to reduce the write traffic of applications thus can be used to extend the lifespan of SSDs. However, traditional deduplication schemes rely on the time-consuming fingerprint computing process to find duplicated data, which may impair the write performance of SSDs. Accordingly, Pre-hashing was proposed to reduce the chances of fingerprint computing thus improving the performance of SSDs with deduplication, but at the cost of degrading deduplication rate. In this paper, we propose NF-Dedupe, a new deduplication scheme that needs no fingerprint computing for flash-based SSDs. NF-Dedupe determines whether a write page is duplicated or not by comparing the write page with its potential duplicated page read from underlying flash chips byte by byte, rather than relying on the comparison of fingerprints. As flash memory is known for its high parallelism and low read latency, reading a page from flash chip and comparing two pages byte by byte introduce lower overhead than the fingerprint computing does. We evaluate the NF-Dedupe via trace-driven simulations. Experimental results have shown that NF-Dedupe outperforms the other approaches and can achieve the deduplication rate ranging from 5.3% to 29.9% and the write latency is improved by a factor of up to 21% with an average of 12%.

Flash memory, especially NAND flash memory, has become a popular alternative for the design of storage system. Index schemes of conventional file systems do not take the flash memory characteristics into account and will cause poor performance. The current flash file systems work well only in the case of small capacity. To address the problem, we propose a new hybrid indexing scheme both in directory structure and file data index for NAND flash file system in this paper, which is called HIFFS (a Hybrid Index for Flash File System). HIFFS contains two components: hash tree directory and adaptive file data index. The hash tree directory uses a hash-based index to get better update performance and search efficiency. The adaptive file data index uses different file index strategy according to file size. The experiment results show that HIFFS outperforms the state-of-the-art file systems both in throughput.

Each cell of flash memory only survives a nominally given number of write/erasure cycles. Beyond the nominal lifespan, flash memory can still record digital information but the bit error rate increases rapidly with the increment of write/erase cycles. Erasure code is a conventional method used to recover corrupted data, but its redundant data produce a large number of additional writes, making the erasure code seem to be unsuitable for the write-sensitive flash memory. We argue that, erasure code influences the lifespan of flash memory in two conflicting directions: its inherent error correction capability enables the flash memory to survive beyond the nominal lifespan, while its redundant data wear out the lifespan of flash memory by increasing the write/erase cycles. This paper builds a theoretical model to analyze both the two aspects and demonstrates that the erasure code is able to extend the nominal lifespan of flash memory by as many as 30×.

Solid state drives (SSDs) are increasingly deployed to construct storage arrays (RAIDs) in enterprise environments. The design decisions in RAID are traditionally devised for HDD RAIDs, which cannot fully exploit the characteristics of SSDs. In particular, SSD lacks the ability to update pages in-place. Random writes in traditional parity-based RAIS (SSD RAID) systems that has static striping result in significantly more writes, degraded performance, and shortened SSD lifetime. By dynamically forming full stripes, log-based design originally proposed in HDD RAID can mitigate the write-hole problem caused by random writes. However, it needs a directory to record locations for all data blocks, resulting in large space overhead and consequently sacrificing addressing efficiency. In this paper, we propose CD-RAIS, a compromise between static striping and dynamic striping. CD-RAIS groups requests that are from different SSD drives and places their corresponding unnecessarily consecutive logical blocks in one stripe. It mitigates the write-hole problem, meanwhile remains the same addressing efficiency as static striping. To enable dynamic data striping fit SSDs, CD-RAIS performs lazy data invalidation and consolidates updates to parity blocks. CD-RAIS greatly alleviates the write request increase due to parity block update in RAIS. Our experimental results show that, for random write dominated workloads, CD-RAIS achieves 65% response time improvement and 31% longer SSD lifespan over traditional RAIS schemes.

NoSQL (Not only SQL) data stores become a vital component in many big data computing platforms due to its inherent horizontal scalability. HBase is an open-source distributed NoSQL store that is widely used by many Internet enterprises to handle their big data computing applications (e.g. Facebook h

While high density SSDs are increasingly adopted in enterprise computing environment, it remains a challenge to meet the high performance and reliability demands of server applications as well as the demands for longer system lifetime and high space utilization in such environment. Existing schemes often address these issues separately. In particular, deduplication schemes improve write performance and SSD lifetime while SSDbased RAID designs improve reliability and read performance. Naively integration of deduplication and RAID results in suboptimal designs. In this paper, we propose R-Dedup, a content-aware redundancy management scheme for SSD-based RAID storage. By combining deduplication with replication, R-Dedup evaluates system performance, reliability, endurance and space utilization, and dynamically manages replicas to achieve better trade off. Our experimental results show that R-Dedup achieves 18% and 20% improvements on read and write performance, respectively, and extends SSD lifetime by 20% with no reliability compromise.

This paper proposes stream model execution (SME), a new architectural technique that supports the efficient utilization of single-instruction multiple-data (SIMD) engines on general-purpose processors. SME adopts lightweight streaming processing as the intermediate representation. This process uses a hardware–software co-design approach to support efficient SIMD compilation and utilization. From a hardware perspective, the micro-architecture of SIMD engines is enabled for stream support to provide the key components to address the limitations of SIMD utilization, such as data rearrangement and non-consecutive memory access. Thus, sequential code can be compiled efficiently through a two-step procedure (i.e. C code → SME C code → vectorized code) and then executed by the SME hardware. Our experimental evaluation shows that SME can outperform previous optimization techniques by an average of 58% for multimedia kernels and 26% for applications.

Multicore architectures with Network-on-Chips (NoCs) have been widely recognized as the de facto design for the efficient utilization of the continuously increasing density of transistors on a chip. A key challenge in designing such an NoC-based multicore processor is maintaining cache coherence in an efficient manner. Directory-based protocols avoid the bandwidth overhead of snoop-based protocols, therefore scaling to a large number of cores. However, conventional directory structures add significant indirection delay to cache-to-cache accesses in larger multicore processor. In this article we propose a novel hardware coherence technique, called integrated coherence prediction (ICP). This approach adopts a prediction technique for managing shared data to reduce or eliminate the cache-to-cache delay in coherence accesses. ICP has two unique features that differ from previous coherence prediction techniques. First, ICP introduces a new integrated prediction scheme that combines two kinds of predictors: owner predictor, which predicts the data writers and avoids the indirection through directory, and data predictor, which predicts the access address and prefetches data from remote nodes directly. Second, ICP uses a request replication method to reduce the negative effect of wrong owner prediction operations, thus facilitating overall performance improvement. We present the design and implementation details of the ICP approach. Using detailed full-system simulations, we conclude that the ICP provides a cost-effective solution for designing high-performance multicore processors.

In personal computing devices that rely on a cloud storage environment for data backup, an imminent challenge facing source deduplication for cloud backup services is the low deduplication efficiency due to a combination of the resource-intensive nature of deduplication and the limited system resources. In this paper, we present ALG-Dedupe, an Application-aware Local-Global source deduplication scheme that improves data deduplication efficiency by exploiting application awareness, and further combines local and global duplicate detection to strike a good balance between cloud storage capacity saving and deduplication time reduction. We perform experiments via prototype implementation to demonstrate that our scheme can significantly improve deduplication efficiency over the state-of-the-art methods with low system overhead, resulting in shortened backup window, increased power efficiency and reduced cost for cloud backup services of personal storage.

Routing algorithms for cache-coherent NoCs only have limited VCs at their disposal, which poses challenges to the design of routing algorithms. Existing fully adaptive routing algorithms apply conservative VC re-allocation: only empty VCs can be re-allocated, which limits performance. We propose two novel flow control designs. First, whole packet forwarding (WPF) re-allocates a nonempty VC if the VC has enough free buffers for an entire packet. WPF does not induce deadlock if the routing algorithm is deadlock-free using conservative VC re-allocation. It is an important extension to several deadlock avoidance theories. Second, we extend Duato's theory to apply aggressive VC re-allocation on escape VCs without deadlock. Finally, we propose a design which maintains maximal routing flexibility with low hardware cost. For synthetic traffic, our design performs averagely 88.9 percent better than existing fully adaptive routing. Our design is superior to partially adaptive and deterministic routing.

Multicore designs have emerged as the dominant organization for future high-performance microprocessors. Communication in such designs is often enabled by Networks-on-Chip (NoCs). A new trend in such architectures is to fit a Message Passing Interface (MPI) programming model on NoCs to achieve optimal parallel application performance. A key issue in designing MPI over NoCs is communication protocol, which has not been explored in previous research. This article advocates a hardware-supported communication mechanism using a protocol-adaptive approach to adjust to varying NoC configurations (e.g., number of buffers) and workload behavior (e.g., number of messages). We propose the ADaptive Communication Mechanism (ADCM), a hybrid protocol that involves behavior similar to buffered communication when sufficient buffer is available in the receiver to that similar to a synchronous protocol when buffers in the receiver are limited. ADCM adapts dynamically by deciding communication protocol on a per-request basis using a local estimate of recent buffer utilization. ADCM attempts to combine both the advantages of buffered and synchronous communication modes to achieve enhanced throughput and performance. Simulations of various workloads show that the proposed communication mechanism can be effectively used in future NoC designs.

This paper proposes dynamic streamization model execution (DSME), a dynamic vectorization technique for single instruction multiple data (SIMD) engines on multicore architectures. The technique uses stream model as intermediate representation for programs to optimize the combination of computation and memory accesses of SIMD engines in general-purpose (GP) designs. DSME allows the dynamic placement of computations on different cores when they are not in use to utilize multiple SIMD engines. This study also discusses hardware extensions to existing GP processor designs as well as related compiler extensions that use the special hardware components. Our extensive experiments demonstrate that performance gains of DSME can be achieved.

Query processing over uncertain data streams, in particular top-$(k)$ query processing, has become increasingly important due to its wide application in many fields such as sensor network monitoring and internet traffic control. In many real applications, multiple top-$(k)$ queries are registered in the system. Sharing the results of these queries is a key factor in saving the computation cost and providing real-time response. However, due to the complex semantics of uncertain top-$(k)$ query processing, it is nontrivial to implement sharing among different top-$(k)$ queries and few works have addressed the sharing issue. In this paper, we formulate various types of sharing among multiple top-$(k)$ queries over uncertain data streams based on the frequency upper bound of each top-$(k)$ query. We present an optimal dynamic programming solution as well as a more efficient (in terms of time and space complexity) greedy algorithm to compute the execution plan of executing queries for saving the computation cost between them. Experiments have demonstrated that the greedy algorithm can find the optimal solution in most cases, and it can almost achieve the same performance (in terms of latency and throughput) as the dynamic programming approach.

Current NoCs are always designed without the consideration of programming models, bringing about a great challenge for exploiting parallelism. In this paper, we present a NoC design that take into account the well-known parallel programming model, message passing interface (MPI), to boost applications by exploiting all hardware features available in the NoC-based multicore architectures. Conventional MPI functions are normally implemented in software due to their enormity and complexity, resulting in large communication latencies. We propose a new hardware implementation of basic MPI primitives. The premise is that all other MPI functions can be efficiently built upon these three MPI primitives. Our design includes two important hardware features: the customized NoC design incorporating virtual buses (VB) into NoCs and the optimized MPI unit (MU) efficiently executing MPI-related transactions. Extensive experimental results have demonstrated that the proposed designs effectively boost the performance of MPI primitives.

Supporting cache coherence in current multicore processor still faces scalability and performance problems. This paper presents an optimized cache coherence design targeting at NoC-based multicore processors. It tries to achieve the best characteristics both of the snooping and of the directory-based protocols. With the observation of network traffic locality, we design a cache coherence that aims at local and remote access separately. At the first level, snooping is achieved within a cache group and at the second level of the protocol, the coarse directories provide the caches with information about which processors must be involved in first level snooping. To support efficient coherence broadcasting, we also propose a low latency, broadcast-enabled underlying NoC design. It incorporates light weight buses into NoCs, where the snooping protocol can be performed in a broadcast fashion. Extensive experimental results demonstrate that the proposed coherence design can achieve low complexity and high performance goals.

Solid-state drives (SSDs) are widely used in storage systems. However, algorithms adopted by existing operating systems generally consider the underlying devices as hard disks, and thus are rarely optimized for SSDs. In this paper, we focus on a classical research issue, the cache replacement policy, and design a new policy by taking the parallelism of SSDs into account.

Binary64 arithmetic is rapidly becoming inadequate to cope with today's large-scale computations due to an accumulation of errors. Therefore, binary128 arithmetic is now required to increase the accuracy and reliability of these computations. At the same time, an obvious trend emerging in modern processors is to extend their instruction sets by allowing single instruction multiple data (SIMD) execution, which can significantly accelerate the data-parallel applications. To address the combined demands mentioned above, this paper presents the architecture of a low-cost binary128 floating-point fused multiply add (FMA) unit with SIMD support. The proposed FMA design can execute a binary128 FMA every other cycle with a latency of four cycles, or two binary64 FMAs fully pipelined with a latency of three cycles, or four binary32 FMAs fully pipelined with a latency of three cycles. We use two binary64 FMA units to support binary128 FMA which requires much less hardware than a fully pipelined binary128 FMA. The presented binary128 FMA design uses both segmentation and iteration hardware vectorization methods to trade off performance, such as throughput and latency, against area and power. Compared with a standard binary128 FMA implementation, the proposed FMA design has 30 percent less area and 29 percent less dynamic power dissipation.

The market for cloud backup services in the personal computing environment is growing due to large volumes of valuable personal and corporate data being stored on desktops, laptops and smart phones. Source deduplication has become a mainstay of cloud backup that saves network bandwidth and reduces storage space. However, there are two challenges facing deduplication for cloud backup service clients: (1) low deduplication efficiency due to a combination of the resource-intensive nature of deduplication and the limited system resources on the PC-based client site, and (2) low data transfer efficiency since post-deduplication data transfers from source to backup servers are typically very small but must often cross a WAN. In this paper, we present AA-Dedupe, an application-aware source deduplication scheme, to significantly reduce the computational overhead, increase the deduplication throughput and improve the data transfer efficiency. The AA-Dedupe approach is motivated by our key observations of the substantial differences among applications in data redundancy and deduplication characteristics, and thus is based on an application-aware index structure that effectively exploits this application awareness. Our experimental evaluations, based on an AA-Dedupe prototype implementation, show that our scheme can improve deduplication efficiency over the state-of-art source-deduplication methods by a factor of 2-7, resulting in shortened backup window, increased power-efficiency and reduced cost for cloud backup services.

Current loop buffer has been mainly explored as an effective architectural technique for low-power execution in embedded processor. Another avenue, however, for exploiting loop buffer is to obtain its performance benefit. In this paper, we propose an application specific loop buffer organization for vectorized processing kernels, to achieve low-power and high-performance goals. The vectorized loop buffer (VLB) is simplified with single loop support for SIMD devices. Since significant data rearrangement overhead is required in order to use the SIMD capabilities, the VLB is specialized for zero-overhead implicit data permutation. We extend several instructions to the baseline ISA for programming and integrate it into an embedded processor for evaluation. Our results show that VLB improves the performance and power measures significantly compared to conventional SIMD devices.

NAND flash has some inherent peculiarities which increase the access delay seriously. We propose the Page to Block mapping Flash Translation Layer (PBFTL). Solid State Drives (SSDs) adopting PBFTL have lower response time. To achieve low response time for read requests, PBFTL adopts hybrid-level mapping scheme. But, hybrid-level FTL behaves awkwardly for write due to the high overhead of garbage collection. PBFTL takes two measures to optimize garbage collection. The first is to direct hot and cold data to separate blocks, which mitigates write amplification significantly. The second is to reduce the latency of reclaiming a block, which enables PBFTL to spend less time on garbage collection. User's requests are unlikely to be congested for a long time. Trace-driven simulations show that, PBFTL achieves low response for both read- and write-intensive workloads.

Providing resistance against hardware attacks is important to ensure trusted or secure computing. Approach of inter-chip authentication is proposed, which can be applied to detect malicious tamper to chips/components equipped on the circuit board. The proposed approach is to utilize the I/O physical timing characters to obtain a specified fingerprint for each specified chip on the board, and to check the validity of the chip by matching its fingerprint for later usage. To obtain the required fingerprint, an inner sampling logic is set after the I/O pins to get the timing characters reflected on the lines connected between the master chip and the slave chip to be verified. From the sampling result, the physical character associated with the slave chip is extracted and compared with the valid one. Because tampers will influence the physical character to distort the fingerprint, it has the abilities to detect tamper behaviors like chip replacement and faked signal injection. A logic analyzer and 8051-MCU based evaluation system is constructed. The test result shows that it can effectively identify the valid chip from the faked ones. Hence, the proposed approach can be deployed into the circuit board to protect the chips equipped on the board against hardware attacks.

Although semantic-based composition approaches have brought some comprehensive advantages such as higher precisions and recalls, they are far from the real practice and hard to be applied in real-world applications due to the several challenging issues such as performance issues of time-consuming ontology reasoning, exponentially expanded searching time in large service repositories, lack of available and consensus ontologies, and higher using thresholds for users who do not have much semantic knowledge. To reduce these issues, in this paper, we present an innovative composition technique by building an Extended Quick Service Query List (EQSQL) for supporting more efficient and more realistic service composition. In EQSQL, data structures are specially designed to record service information and their associated semantic concepts by in advance processing semantic-related computing during service publication period. Particularly, WordNet and semantic similarities among multiple heterogeneous ontologies are exploited in our developed algorithms for forming EQSQL. As a result, EQSQL-based planning algorithm can not only achieve a quick response for a composition request, but guarantee the semantic composition quality as well. More importantly, our approaches can be scalable to the large service repositories and also significantly alleviate users or developers from the burden of using complicated semantic service composition, thus making service composition easier and more realistic. Our final experiments further demonstrate the feasibility and the efficiency of our proposed approaches.

Network virtualization has been proposed as a powerful vehicle for running multiple customized networks on a shared infrastructure. Virtual network embedding is a critical step for network virtualization that deals with efficient mapping of virtual nodes and virtual links onto the substrate network resources. Previous work in virtual network embedding primarily focused on designing heuristic algorithms for static networks. Virtual network infrastructure should be reconfigured or redeployed in response to network growth. In this paper, we address the problem of optimally redeploying the existing virtual network infrastructure as the network evolves. This problem focus on minimizing the upgrading cost of virtual network, with satisfying node resource constraint and path delay constraint. It is shown that this problem is NP-hard. A heuristic algorithm is proposed and its effectiveness is validated by simulations evaluation.

SIMD devices have gained widespread acceptance in modern microprocessor designs for their superior performance for multimedia applications. However, there are three remaining limitations to the efficient utilization of SIMD devices in general-purpose computer systems: memory alignment, data reorganization and control flow. This paper presents SIF, an efficient SIMD interface framework that addresses these three shortcomings without modifying existing ISA. It is designed around a permutation vector register file (PVRF) and it adds new extended instructions to set internal permutation state in SIMD datapath rather than putting the permutation state setting bits in every instruction. The implicit permutation capability provided by PVRF results in zero overhead, which frees the handling of three limitations by using permutation instructions. To further reduce the state setting instructions in SIMD datapath, a technique that moves the workloads from SIMD pipeline into scalar pipeline is also introduced. With the help of proposed compilation algorithm, SIF can efficiently transform regular SIMD codes into SIF codes which make it easily integrated in all existing SIMD devices. We implemented these techniques in a vectorizing compiler and experimental results show that most of the permutation overhead instructions can be eliminated and distinct performance speedup can be achieved, which is 37% higher than current SIMD techniques on average.

The development of flash memory drives flash based SSD to enter into large-scale storage systems. The performance of SSD is highly dependent on the design of FTL. For the last few years, several FTL schemes have been proposed. Such as FAST, BAST, SAST etc. we design a novel FTL based on page-level mapping scheme. Since one of the major troubles of page-level mapping FTL is the unendurable memory consuming of the fine-grained mapping table. We propose a dedicated cache replacement policy called SRC to mitigate the memory pressure. Our FTL based on SRC is able to distinguish hot data from the cold. This capability highlights the garbage collection efficiency of page-level mapping schemes. As a result, the hot data-aware FTL reduces extra read/write operations by 10 times or more compared with FAST and BAST. As our FTL erases less blocks, the lifetime of SSD is extended by more than 30%. Further experiment shows that the hot data-aware FTL outperforms hybrid-level FTLs on workloads with varied read/write ratios.

The development of flash memory drives flash based SSDs to enter into enterprise-scale storage systems. As the kernel of SSD, flash translation layer (FTL) attracts many attentions. Generally, there are two types of FTLs according to the granularity of address mapping: block-level and page-level mapping FTLs. We focus on the latter one. Typically, page-level mapping scheme must employ a cache to alleviate the memory pressure introduced by the big mapping table. We argue that classic cache replacement policies aren't competent for the page table cache of FTLs. The major contribution of this work is to design a dedicated cache replacement policy called Two Filters (abbreviated as 2F) for page-level mapping FTLs. 2F aims at two goals. The first is higher hit ratio as all the replacement policies pursue. As 2F not only protects frequently accessed pages, but also protects sequentially accessed pages at little cost, it does achieve a higher hit ratio. The second goal is to distinguish hot pages from the cold. This goal is special for page table of FTLs. If hot and cold pages are directed to separate blocks, garbage collection will be more efficient. In order to achieve this goal, 2F employs two filters. One is used for containing sequentially accessed pages. Another is used for selecting hot pages. Trace driven simulations present that 2F outperforms classic replacement policies in both hit ratio and data classification.

Hash tree is a secure way to authenticate stored data. However, it is difficult to maintain a consistent state between the authentication result and data, which is necessary for permanent data storage of disk. Incremental node updating is proposed to solve such problem, it synchronizes data modification and authentication result with low cost. The reason is that the path from leaf node to root node of the tree can be very short, and each step on the path can be finished quickly as no sibling nodes are required. Thus, it greatly reduce additional disk I/O for authentication synchronization. Together with a low cost logging mechanism implemented by NVRAM, system can make fast recovery to still keep the required consistency after any failures. Related approach is elaborated, as well as testing results. Theoretical analysis and experimental simulations show that it is a practical and available way for mass data storage authentication.

This paper presents our replacement algorithm named RED for storage caches. RED is exclusive. It can eliminate the duplications between a storage cache and its client cache. RED is high performance. A new criterion Resident Distance is proposed for making an efficient replacement decision instead of Recency and Frequency. Moreover, RED is non-intrusive to a storage client. It does not need to change client software and could be used in a real-life system. Previous work on the management of a storage cache can attain one or two of above benefits, but not all of them. We have evaluated the performance of RED by using simulations with both synthetic and real-life traces. The simulation results show that RED significantly outperforms LRU, ARC, MQ, and is better than DEMOTE, PROMOTE for a wide range of cache sizes.

With the wide applications of data streams in many fields, such as sensor network monitoring and internet traffic control, query processing over data streams has become increasingly important. In these applications, multiple aggregate queries are registered in the system, and have different sliding window sizes and different frequency upper bounds. How to share the results of these queries is a challenge. Prior work studies how to detect common tasks of these queries and share the results by computing the common tasks only once. Hybrid scheduling first addressed this problem and used the earliest-deadline-first (EDF) method. However, this work did not present a method for computing the scheduling. We formulate the scheduling problem among multiple aggregate queries with different sliding window sizes and different frequency upper bounds over data streams and propose a combination rule to classify these queries. Then, we present an efficient scheduling algorithm to decide whether a query should be executed more often than necessary, as long as the interval between two consecutive executions is less than the frequency upper bound. We also combine our scheduling algorithm with EDF to handle under loaded and overloaded situations. An experimental study shows that our scheduling algorithms are more efficient than no scheduling and EDF in terms of the number of scanned tuples, the throughput and the latency.

To protect hard disk data confidentiality and integrity, AEIVV associates one unique IV with each disk sector; then, it applies authenticated encryption of AES-CCM to the protected sector and constructs hash tree upon IV storage. Through assuring IV to be trusted or un-tampered, data can be protected firmly. To make it an available way for disk protection, various optimizing measures are applied to quicken the running speed. With the emphasis of reducing extra latencies caused by protection, IV/MAC storage is allocated using interlaced layout to decrease seek time of disk I/O, IV checking penalty is reduced by buffering the frequently used hash tree nodes and IV/MAC values. Related approaches are elaborated, as well as experimental results. It shows that AEIVV is a practical and available way to build secure disk.

The ever-growing creation of data requires large-scale network storage systems. One of the key issues related such systems is how to place several petabytes of data among large number of devices. Itpsilas necessary to design a reliable, fair, adaptable data placement algorithm. All proposed approaches are oblivious to the reliability-based requirements of data in such systems. In this paper, we present a reliability-aware data placement algorithm for large-scale network storage systems. With considering the reliability-aware differences of storage devices and the reliability-based requirement of data, we formulate the problem as an integer programming to minimize the reliability cost and propose a polynomial-time algorithm to solve the problem. For each reliability level, we use a fair and adaptive data placement to distribute data. It can support arbitrary heterogeneous storage systems, distribute data in a fair way and allow an efficient adaptation to a changing set of devices. The theoretical analysis as well as the experimental study show that the approach can meet the reliability-based requirements of data, distribute data evenly among devices, and adapt well to the changes of devices.

As the performance gap between disks and processors continues to increase, dozens of cache replacement policies come up to handle the problem. Unfortunately, most of the policies are static. Nimrod Megiddo etc put forward a low overhead adaptive policy called ARC. It outperforms most of the static policies in most situations. But, ARC adapts itself to the workloads by the feedback of the missed pages. It hasn 't carried out the adaption before missed pages are discovered. We propose a high performance adaptive replacement policy. It adapts itself to the workloads by the feedback of the hit pages, so, it is more sensitive to the changes of the workloads than ARC. As the policy stares at the tails of the queues regardless of other pages, we name the policy as short-sighted adaptive replacement policy. The ARC usually regrets for the missed pages and wishes to rescue the neighborhood of them. However, SSARC endeavors to protect the would-be-reused pages from being replaced aggressively. So, it outperforms ARC in most situations. We compared SSARC with LRU, 2Q and ARC. The trace-driven experiments represent that SSARC gains higher performance.

An accurate and highly-efficient performance analysis approach is extremely important for the early-stage designs of network-on-chip. In this paper, the novel M/G/1/N queuing models for generic routers are proposed to analyze various packet blockings and then the performance analysis algorithm is presented to estimate some key metrics in terms of packet latency, buffer utilization, etc. For single-channel and multi-channel routers, the comparisons between analysis and observed results validate that the proposed approach with mean errors of 6.9% and 7.8% achieve the speed-ups of 240 and 210 times respectively. In our design methodology, this approach can not only effectively direct NoC synthesis process but also be conveniently applied to multi-objective optimizations to find the best mapping solutions. Categories and Subject Descriptors: B.4.3 [Hardware]: Input/Output and Data Communication-Interconnections. General Terms: Algorithms, Performance.

Interpretation and basic block translation (BBT) are two typical strategies for cold code emulation in a dynamic binary translation (DBT) system. More and more DBT systems employ BBT as the generated native code runs more efficient than the interpretation routines. We observe that BBT's high efficiency is based on those special hardware assists. With certain simple hardware techniques, interpretation could outperform BBT. In our pervious work, we proposed a hardware interpreted code cache (Pcache) mechanism to speedup interpretation by saving the decoded instruction information during interpretation. This light-weight code cache design could be extended to assist the hotspots translation, thus further reduce the DBT systems' overhead. We add the translation entry into the Pcache design thus saving most decoding operations during translation. We use eight SPEC 2000 integer benchmarks on our DBT simulator. Results show that the modified Pcache design causes a speedup of 1.94 according to the referenced DBT with basic interpretation and the interpretation based DBT system assisted by the modified Pcache performs more efficiently than the DBT system which employs BBT for the cold code.

A critical issue in service composition area is how to achieve an optimized overall end-to-end quality of service(QoS) requirements by effectively coordinating QoS constraints for individual service. However, this issue has not yet been well addressed. In this paper, we propose a novel method by employing a recursive bargaining Strategy to gradually remove QoS constraint violations for Optimizing service composition execution Path. Our method mainly exploits the hidden market competitive relationships which widely exist in real business world for developing a novel bargaining strategy. Based on this strategy, concessions can be made by service providers to offer better QoS values. By recursively using bargaining strategy, an initial execution path built by a local optimization policy for service composition, can be continually updated to be close to the optimal one by reselecting better service providers for meeting overall end-to-end QoS requirements. An experiment and evaluation have been made to demonstrate the feasibility and effectiveness of our proposed method.

Abstract— Dynamic binary translation (DBT) converts codes written for a source instruction set architecture (ISA) into optimized code for a target ISA. DBT has emerged as an important tool with real world applications. Interpretation is always adopted to handle the non-hotspot code in a two-stage DBT system. An important consideration in such DBT systems is the interpretation overhead. We investigate that repeated redecoding operations are the bottleneck of interpretation overhead. We propose interpreted code cache (Pcache), a hardware assist to save the information of the decoded instruction for reuse. We analyze and model Pcache performance via simulation on a DBT system simulator. Results from SPEC2000 integer benchmarks show that Pcache could significantly reduce redecoding operations and the overhead of interpretation in a DBT system. The speedup of interpretation is up to 17.12 on average with assist of Pcache. We also analyze the extra overhead caused by Pcache, which is neglectable compared to the performance gains.

Virtual disks (VD) are the main form of storage in today's virtual machine (VM) environments for they have many attractive features, such as encapsulation, mobility, isolation, etc. A typical virtual disk image usually has a large size of at least several gigabytes, a disadvantage that may limit its usage in many situations, such as fast software deployment in large-scale virtual machine environments, fast VM migration in local or distributed environments, etc. The COW (Copy-on-Write) virtual block device supported by many virtual machine monitors can split the traditional one-piece large-sized VD image into multiple smaller-sized VD images (COW disks). However, frequent or long-term software updates may result in large numbers of COW disks. Moreover, the accumulated large numbers of old-version COW disks (OCD) installed with old-version software may cause serious disk space wastage. In this paper, we propose two VD image reclamation approaches RPD and RMD to reclaim the OCDs so as to free the disk space taken by the old-version software and to maintain the number of COW disks in a specific range to ease the VD image management. Based on QEMU and Linux system, we have developed tools to implement the two approaches. Experiments show that the two VD image reclamation approaches can effectively reclaim the OCDs so as to be able to support frequent or long-term software updates in virtual machine environments.

Hash tree based disk storage integrity protection suffers from performance penalty and possible losing of consistency. FI-Tree deploys a fixed-structure tree and applies incremental-hash to tree node updating to solve the difficulties of performance and consistency. The biggest advantage of FI-Tree comes from that: to allow tree nodes to be cached to optimize performance, it can maintain consistency between the tree and the protected data with low cost at the same time. Basing on FI-Tree, TNSD constructs an instance of secure disk. TNSD associates one nonce with each data block to be protected, and applies FI-Tree to ensure the nonce to be un-tampered. In such way, data protection can be fulfilled with resistance against any attacks. Related approaches are elaborated, as well as testing results. Theoretical analysis and experimental simulation show that it is a practical and available way to build secure disk.

In this paper, we propose a demand-driven virtual disk (VD) prefetch mechanism-DPM to improve the performance of virtual machine (VM) at destination site for mobile personal computing environments. DPM uses an optimized COW (Copy-on-Write) virtual block device to split the traditional one-piece large-sized VD image into multiple small-sized SVDs (Software Virtual Disk) at a basic granularity of a single kind of software. Based on the fine-grained VD splitting, DPM uses an access frequency and priority-based prefetch target identifying - APTI algorithm to identify the SVDs of the being-used software by the user in real-time mode at destination site, and prefetches those SVDs by utilizing P2P transportation mechanism at background. We have built a prototype to realize DPM on Xen virtual machine monitor (VMM). Experiments on the prototype show that DPM can effectively improve the VM performance at an unexpected destination site without any cached VD state, supporting agile mobility of personal computing environments.

Abstract Scientific workflow is emerging as a promising scientific computing paradigm to offer the convenience for the scientists to resolve complex scientific problems. To successfully execute a scientific workflow, the workflow creation by depending on service discovery techniques should be made in the first place. Particularly, semantics have been proposed as a key to automatically solve service discovery issue for facilitating users to create a workflow. However, most of the semantic service discovery methods still remain at a low‐efficiency stage because they generally involve a large number of ontology reasoning that is often time consuming. To address this issue, we present an efficient service discovery method by building Quick Service Query list (QSQL) to support automated service discovery for creating a workflow. QSQL based on graph storage theory is an efficient service index list that is dynamically built by service publication algorithm. In QSQL, semantic relationships between the published services and all related ontology concepts can be processed in advance so that a large number of ontology reasoning can be avoided during service discovery. Further, our proposed discovery algorithm can efficiently select service models from QSQL to match a user query. The final experiments further demonstrate the feasibility and the efficiency of our proposed method. Copyright © 2009 John Wiley & Sons, Ltd.

We propose a shot-based interest point selection approach for effective and efficient near-duplicate search over a large collection of video shots. The basic idea is to eliminate the local descriptors with lower frequencies among the selected video frames from a shot to ensure that the shot representation is compact and discriminative. Specifically, we propose an adaptive frame selection strategy called furthest point voronoi (FPV) to produce the shot frame set according to the shot content and frame distribution. We describe a novel strategy named reference extraction (RE) to extract the shot interest descriptors from a keyframe with the support of the selected frame set. We demonstrate the effectiveness and efficiency of the proposed approaches with extensive experiments.

Current existing semantic composition methods mainly rely on ontology reasoning to support automated service composition. However, in reality, ontologies are generally unavailable or ontology reasoning is time-consuming; thus existing semantic composition methods are becoming impractical in the general service integration field. To address this problem, in this paper, we present an innovative composition technique by combining Wordnet with ontologies together to build an extended quick service query list (EQSQL) for supporting automated service composition. In EQSQL, data structures are designed particularly to record service information and their associated semantic concepts by previously processing semantic-related computing during service publication stage. Based on EQSQL, not only a quick response can be achieved, but the semantically-similar composition quality as well even if there is a lack of concrete domain-dependent ontologies for a user query.

Compared with single-issue general purpose processors (GPPs), extensible multi-issue/VLIW processors can exploit instruction-level parallelism, which are more suitable for computation intensive tasks. Moreover, they offer the ability of customizing computation accelerators for an application domain. In this paper, we present an automated methodology that customizes computation accelerators for the multi-issue/VLIW extensible processors, where several techniques are also proposed to optimize the design of an accelerator.

In large distributed storage systems, metadata is usually managed separately by a metadata server cluster. The partitioning of the metadata among the servers is of critical importance for maintaining efficient MDS operation and a desirable load distribution across the cluster. We present a dynamic directory partitioning (DDP) metadata management scheme, directory metadata and file metadata are managed in different ways, and the dynamically changing workload can be balanced by adjusting the metadata distribution on metadata servers. Our simulation results show that our approach, comparing with other metadata management strategies, has advantages in performance, scalability and adaptability.

Multicast is essential for wireless sensor network (WSN) applications. Existing multicast protocols in WSNs are often designed in a P2P pattern, assuming small number of destination nodes and frequent changes on network topologies. In order to truly adopt multicast in WSNs, we propose a base-station model- based multicast, SenCast, to meet the general requirements of applications. SenCast is scalable and energy-efficient for large group communications in WSNs. Theoretical analysis shows that SenCast is able to approximate the Minimum Nonleaf Nodes (MNN) problem to a ratio of ln\R\ (R is the set of all destinations), best known lowest bound. We evaluate our design through comprehensive simulations. Experimental results demonstrate that SenCast outperforms previous multicast protocols including the most recent work uCast.

Approach that integrates encryption and verification is proposed to protect hard disk data. For each data sector, MAC is calculated and the (data sector, MAC) pair is encrypted through the encryption key deduced from the secret root key and a unique nonce. By assuring the nonce to be trusted or untampered through hash tree, data can then be properly decrypted and authenticated. To achieve satisfiable performance, it applies stream cipher to offload the encryption cost, and adopts special structure hash tree with hot-access-windows to fulfill nonce checking efficiently. Ultimately, it can provide data protection with characteristics like solid resistance against any attacks, online working mode, low-level protecting, and high performance. Related model, approaches and system realization are elaborated, as well as testing results. Theoretical analysis and experimental simulations show that it is a practical and available way to build secure disk.

Current cache replacement policies mostly work at the block device level. Block level policies try to achieve better hit ratio by balancing the frequently and recently visited pages, however, further improvements can be realized by using file-system metadata. There are two reasons for this. First, sequential access of disk data is more quickly than non-sequential access, that is to say, the cache penalty of sequential blocks miss can be significantly lower than that of random blocks miss. Second, in most storage systems, files are stored and accessed sequentially. We notice this and propose a novel cache management policy, called bargain cache, which prefers to drop sequential pages by using the file-system metadata, so that hard disks could work under sequential access mode as much as possible. Simulation results show that our technique can efficiently reduce the cache miss penalty, thus improve the overall caching performance.

Current service composition and coordination still remain at large amount of manual processing stage, which has brought about low efficiency. In this paper, we present an efficient algorithm for abstract service discovery and a service instance selection method. Our algorithm firstly builds up the special data structures of ontology concepts based on graph storage theories when publishing abstract services. Then, these data structures form a quick service query list. In our algorithm, the large number of ontology reasoning is processed at service publication stage, thus we can make sure the quick query response in service discovery without much reasoning. In addition, our service instance selection methods based on OWL QoS ontology can enable grid resource sharing and coordination more flexible.

As an innovative distributed computing technique for sharing the memory resources in high-speed network, RAM Grid exploits the distributed free nodes, and provides remote memory for the nodes which are short of memory. One of the RAM Grid systems named DRACO, tries to provide cooperative caching to improve the performance of the user node which has mass disk I/O but lacks local memory. However, the performance of DRACO is constrained with the network communication cost. In order to hide the latency of remote memory access and improve the caching performance, we proposed using push- based prefetching to enable the caching providers to push the potential useful memory pages to the user nodes. Specifically, for each caching provider, it employs sequential pattern mining techniques, which adapts to the characteristics of memory page access sequences, on locating useful memory pages for prefetching. We have verified the effectiveness of the proposed method through system analysis and trace-driven simulations.

Within data grid environments, data replication is a general mechanism to improve performance and availability for distributed applications. However, it is a challenging problem to find the physical locations of multiple replicas of desired data efficiently in large-scale wide area data grid systems. In this paper, we proposed a new dynamic self-adaptive distributed replica location method - DSRL to solve the problem. In DSRL, each data element has a home node, which maintains the indices of the location information replicas. Home nodes are used to support locating multiple replicas of the same data element efficiently. Meanwhile, DSRL employs local location nodes which maintain the local replica information of data elements to support local query for local replicas. A dynamic mapping technique that can adapt to the joining or departing of home nodes is utilized to spread global replica location information evenly on location nodes. The correctness and properties of DSRL are presented and proved. Analysis and experiments show that DSRL can achieve low latency, good scalability, reliability, adaptability and ease of implementation.