Graph Random Walks (GRWs) offer efficient approximations of key graph properties and have been widely adopted in many applications. However, GRW workloads are notoriously difficult to accelerate due to their strong data dependencies, irregular memory access patterns, and imbalanced execution behavior. While recent work explores FPGA-based accelerators for GRWs, existing solutions fall far short of hardware potential due to inefficient pipelining and static scheduling. This paper presents RidgeWalker, a high-performance GRW accelerator designed for datacenter FPGAs. The key insight behind RidgeWalker is that the Markov property of GRWs allows decomposition into stateless, fine-grained tasks that can be executed out-of-order without compromising correctness. Building on this insight, RidgeWalker introduces an asynchronous pipeline architecture with a feedback-driven scheduler grounded in queuing theory. This design enables perfect pipelining and adaptive load balancing. We prototype RidgeWalker on FPGAs and evaluate its performance across a range of GRW algorithms and real-world graph datasets. Experimental results demonstrate that RidgeWalker achieves an average speedup of 7.0× over state-of-the-art FPGA solutions and 8.1× over GPU solutions, with peak speedups of up to 71.0× and 22.9×, respectively. The source code is publicly available at https://github.com/Xtra-Computing/RidgeWalker.

Performance tuning is a persistent challenge in high-performance computing (HPC), where large codebases, architectural diversity, and limited evaluation budgets make manual optimization impractical. Modern compilers expose hundreds of optimization flags, yielding an enormous configuration space that existing autotuners explore inefficiently, often requiring thousands of costly trials.

Graph Neural Network (GNN) on streaming graphs has gained increasing popularity. However, its practical deployment remains challenging, as the inference process relies on Runtime Embedding Computation (RTEC) to capture recent graph changes. This process incurs heavyweight multi-hop graph traversal overhead, which significantly undermines computation efficiency. We observe that the intermediate results for large portions of the graph remain unchanged during graph evolution, and thus redundant computations can be effectively eliminated through carefully designed incremental methods. In this work, we propose an efficient framework for incrementalizing RTEC on streaming graphs.The key idea is to decouple GNN computation into a set of generalized, fine-grained operators and safely reorder them, transforming the expensive full-neighbor GNN computation into a more efficient form over the affected subgraph. With this design, our framework preserves the semantics and accuracy of the original full-neighbor computation while supporting a wide range of GNN models with complex message-passing patterns. To further scale to graphs with massive historical results, we develop a GPU-CPU co-processing system that offloads embeddings to CPU memory with communication-optimized scheduling. Experiments across diverse graph sizes and GNN models show that our method reduces computation by 64%-99% and achieves 1.7x-145.8x speedups over existing solutions.

Deep learning on 3D point clouds plays a vital role in a wide range of applications such as AR/VR visualization, 3D cloth virtual try-on, and game rendering. As some applications require low latency, the point cloud services are also deployed on datacenter with powerful GPUs. While the queries of point cloud services show various workload change patterns due to different degrees of sparsity, current batching-based serving schemes result in either long latency or low throughput. We propose a scheme called Volans to address the above challenges and effectively support point cloud services. Volans comprises a workload predictor, a topology deployer, and a progress-aware scheduler. The predictor grids the input query and estimates the workload changes. Afterward, the deployer splits the model into several stages and determines the batch size for each stage based on the workload changes. The scheduler reduces the QoS violation when queries run slower due to unpredicted workload spikes. Experiments show that Volans enhances the peak supported throughput by up to 31.1% while maintaining the required 99%-ile latencies compared to state-of-the-art techniques.

Large-scale approximate nearest neighbor search (ANNS) has become a fundamental operation in a wide range of modern applications, including recommendation systems and large language models. Partition-based indexes have emerged as a popular solution for billion-scale ANNS tasks, serving as the basis for many ANNS approaches. However, our analysis indicates that, to achieve optimal search performance on billion-scale datasets, an extremely large number of partitions (tens or even hundreds of millions) is often required for fine-grained partitioning of the feature space. Relying on full-precision distance calculations for constructing and querying such a large number of partitions imposes significant time costs. In this work, we propose a novel geometric distance inference mechanism that leverages geometric relationships to expedite distance computations between the vector and space partitions. By reusing intermediate or offline-computed distance information, this method substantially reduces the overhead of full-precision calculations. We also introduce a clustering paradigm for generating space partitions that incorporates this geometric distance pattern, which can be seamlessly integrated with other indexing schemes such as vector quantization and proximity graphs. Through detailed complexity analysis and extensive experiments on billion-scale datasets, we confirm the efficiency of our geometric index (GI) design. Empirical results show that GI-based solutions consistently surpass various baseline methods on search efficiency. In particular, they offer considerable acceleration (exceeding a factor of 2.0) at high recall levels (e.g., Recall10@10 = 95%) to partition-based solutions, while also demonstrating comparable or superior query throughput relative to leading graph-based indexes.

Optimizing tensor programs for deep learning inference is costly, often requiring hours of search over massive search spaces ($\gt 10^{10}$). Prior machine learning-guided approaches are stochastic and inefficient because they treat both the search and programs as black boxes, overlooking two key properties: (1) the search space is highly structured, with large regions of invalid or low-performing configurations, and (2) tensor programs exhibit analyzable patterns in memory access and pipelined execution. We present Texplorer, a deterministic tensor program optimizer that exploits these structures for robust and efficient search. Texplorer introduces a three-stage pruning algorithm to eliminate invalid, redundant, and inefficient candidates, shrinking the search space from billions to thousands. It replaces costly learned models with a lightweight analytical cost model that captures GPU pipeline and memory behavior, enabling accurate, training-free performance prediction and strong cross-operator generalization. Finally, Texplorer integrates pruning and cost modeling into a one-pass analytical evaluation pipeline that ranks all remaining candidates, enabling rapid convergence without iterative retraining or stochastic sampling. Across 121 operators and 11 DNNs on NVIDIA V100, A100, and H100 GPUs, Texplorer matches state-of-the-art performance while reducing search time by up to$300\times$. An enhanced variant,Texplorer$^+$, further improves performance by up to 3.1% with up to$72\times$faster tuning.

Content-addressable memory (CAM) is a type of fast memory unique in its ability to perform parallel searches of stored data based on content rather than specific memory addresses. They have been used in many domains, such as networking, databases, and graph processing. Field-programmable gate arrays (FPGAs) are an attractive platform for implementing CAMs because of their low latency, reconfigurability, and energy-efficient nature. However, such implementations also face significant challenges, including high resource utilization, limited scalability, and suboptimal performance due to the extensive use of look-up tables (LUTs) and block RAMs (BRAMs). These issues stem from the inherent limitations of FPGA architectures when handling the parallel operations required by CAMs, often leading to inefficient designs that cannot meet the demands of high-speed, data-intensive applications. To address these challenges, we propose a novel configurable CAM architecture that leverages the digital signal processing (DSP) blocks available in modern FPGAs as the core resource. By utilizing DSP blocks’ data storage and logic capabilities, our approach enables configurable CAM architecture with efficient multi-query support while significantly reducing search and update latency for data-intensive applications. The DSP-based CAM architecture offers enhanced scalability, higher operating frequency, and improved performance compared to traditional LUT and BRAM-based designs. In addition, we demonstrate the effectiveness of our proposed CAM architecture with a triangle counting application on real graphs. This innovative use of DSP blocks also opens up new possibilities for highperformance, data-intensive applications on FPGAs. Our proposed design is open-sourced at: https://github.com/Xtra-Computing/DSP_CAM/.

Learned activation functions in models like Kolmogorov-Arnold Networks (KANs) outperform fixed-activation architectures in terms of accuracy and interpretability; however, their computational complexity poses critical challenges for energy-constrained edge AI deployments. Conventional CPUs/GPUs incur prohibitive latency and power costs when evaluating higher order activations, limiting deployability under ultra-tight energy budgets. We address this via a reconfigurable lookup architecture with edge FPGAs. By coupling fine-grained quantization with adaptive lookup tables, our design minimizes energy-intensive arithmetic operations while preserving activation fidelity. FPGA reconfigurability enables dynamic hardware specialization for learned functions, a key advantage for edge systems that require post-deployment adaptability. Evaluations using KANs - where unique activation functions play a critical role—demonstrate that our FPGA-based design achieves superior computational speed and over 104times higher energy efficiency compared to edge CPUs and GPUs, while maintaining matching accuracy and minimal footprint overhead. This breakthrough positions our approach as a practical enabler for energy-critical edge AI, where computational intensity and power constraints traditionally preclude the use of adaptive activation networks.

With the rise of machine learning models, particularly generative models like sequence-to-vector models, there is a high demand for constructing efficient approximate nearest neighbor search (ANNS) indexes on the embedding vectors they generate. Despite the development of numerous indexes for efficient vector retrieval, the complex distributions of vectors generated by these models and their impact on ANNS tasks remain underexplored. In this work, we address the challenges faced by current advanced ANNS approaches when dealing with vectors characterized by imbalanced distributions, which negatively impact search efficiency. We identify the difficulty in indexing and searching certain vectors using previous ANNS graph indexes due to skewed distributions and propose a novel index, Vista, that improves efficiency by introducing dynamic index construction patterns based on vector distribution. Our experimental evaluation confirms Vista's efficiency advantage, demonstrating that on both public and industrial-grade real-world imbalanced datasets, Vista achieves several to tens of times performance improvement compared to advanced ANNS indexes while ensuring high search accuracy and good scalability.

For reasons such as privacy, there are use cases for language models at the edge. This has given rise to small language models targeted for deployment in resource-constrained devices where energy efficiency is critical. Spiking neural networks (SNNs) offer a promising solution due to their energy efficiency, and there are already works on realizing transformer-based models on SNNs. However, key operations like softmax and layer normalization (LN) are difficult to implement on neuromorphic hardware, and many of these early works sidestepped them. To address these challenges, we introduce Sorbet, a transformer-based spiking language model that is more neuromorphic hardware-compatible. Sorbet incorporates a novel shifting-based softmax called PTsoftmax and a BitShifting-based PowerNorm (BSPN), both designed to replace the respective energy-intensive operations. By leveraging knowledge distillation and model quantization, Sorbet achieved a highly compressed binary weight model that maintains competitive performance while achieving $27.16\times$ energy savings compared to BERT. We validate Sorbet through extensive testing on the GLUE benchmark and a series of ablation studies, demonstrating its potential as an energy-efficient solution for language model inference. Our code is publicly available at https://github.com/Kaiwen-Tang/Sorbet

Gradient Boosted Decision Trees (GBDTs) are classical machine learning algorithms widely employed in recommendation systems, database queries, etc. Due to the extensive memory access involved in histogram-based GBDT training methods, high-bandwidth GPUs have been widely adopted to accelerate the training. However, when handling millions of feature data, it requires significant memory to store the training data and histograms, posing challenges for training on limited GPU memories. In this paper, we develop a GPU-based GBDT framework named ScalaGBM, aiming to accelerate high-dimensional data training with less memory usage. We first employ a CSR-like data format and CSR-based histogram construction to reduce the memory occupation of the training data. Then, we reorganize the training workflow with a double buffer structure to reduce the overall memory consumption for the histogram. Finally, we develop multi-dimensional parallel histogram construction and global optimal split point reduction to speed up the training process. Experimental results demonstrate that ScalaGBM handles real-world datasets with over 100 million instances of 50 million features with a single commercial GPU while existing GBDT frameworks all run into out-of-memory errors. Meanwhile, ScalaGBM achieves a maximum speedup of 39× over state-of-the-art GBDT counterparts without sacrificing the training quality. The code is available at https://github.com/Xtra-Computing/thundergbm.

Efficient graph processing is critical in various modern applications, such as social network analysis, recommendation systems, and large-scale data mining. Traditional single-FPGA systems struggle to handle the increasing size and complexity of real-world graphs due to limitations in memory and computational resources. Existing multi-FPGA solutions face significant challenges, including high communication overhead caused by irregular data transfer patterns and workload imbalances stemming from skewed graph distributions. These inefficiencies hinder scalability and performance, highlighting a critical research gap. To address these issues, we introduce Clementi, an efficient multi-FPGA graph processing framework that features customized fine-grained pipelines for computation and cross-FPGA communication. Clementi uniquely integrates an accurate performance model for execution time prediction, enabling a novel scheduling method that balances workload distribution and minimizes communication overhead by overlapping communication and computation stages. Experimental results demonstrate that Clementi achieves speedups of up to 8.75× compared to state-of-the-art multi-FPGA designs, indicating significant improvements in processing efficiency as the number of FPGAs increases. This near-linear scalability underscores the framework' s potential to enhance graph processing capabilities in practical applications. Clementi is open-sourced at https://github.com/Xtra-Computing/Clementi.

Large language models (LLMs) have garnered substantial attention due to their promising applications in diverse domains. Nevertheless, the increasing size of LLMs comes with a significant surge in the computational requirements for training and deployment. Memristor crossbars have emerged as a promising solution, which demonstrated a small footprint and remarkably high energy efficiency in computer vision (CV) models. Memristors possess higher density compared to conventional memory technologies, making them highly suitable for effectively managing the extreme model size associated with LLMs. However, deploying LLMs on memristor crossbars faces three major challenges. First, the size of LLMs increases rapidly, already surpassing the capabilities of state-of-the-art memristor chips. Second, LLMs often incorporate multi-head attention blocks, which involve non-weight stationary multiplications that traditional memristor crossbars cannot support. Third, while memristor crossbars excel at performing linear operations, they are not capable of executing complex nonlinear operations in LLM such as softmax and layer normalization. To address these challenges, we present a novel architecture for the memristor crossbar that enables the deployment of state-of-the-art LLM on a single chip or package, eliminating the energy and time inefficiencies associated with off-chip communication. Our testing on BERT showed negligible accuracy loss. Compared to traditional memristor crossbars, our architecture achieves enhancements of up to in area overhead and in energy consumption. Compared to modern TPU/GPU systems, our architecture demonstrates at least a reduction in the area-delay product and a significant 69% energy consumption reduction.

Leveraging GPUs' high parallelism can significantly improve the real-time computation efficiency of streaming graph processing. However, when a large-scale graph exceeds GPU memory capacity, CPU-GPU cooperative processing often results in substantial and irregular CPU-to-GPU data transfer overhead. This stems from the extensive redundant graph accesses during continuous computation, which can hardly be addressed by existing solutions. In this work, we present Grapin, an out-of-memory GPU streaming graph processing system designed to minimize graph data transfer via two effective techniques for eliminating redundant accesses: (1) Extending advanced incremental processing algorithms to GPUs by converting their heavyweight data dependency processing into GPU-friendly forms, eliminating redundant graph accesses from the computation side; and (2) providing a lightweight yet efficient GPU hot subgraph management framework that finely caches the frequently accessed dynamic subgraphs in a vertex-centric manner. Experimental results demonstrate that Grapin can efficiently process large-scale streaming graphs with billions of edges on a single NVIDIA A5000 GPU. Enabling incremental computation reduces data transfer by 61%, and the integration of GPU hot subgraph reuse further reduces the remaining transfer by 72%, resulting in a total reduction of 89%. Compared with CPU-based solutions, Grapin achieves speedups ranging from 1.8x to 96.9x (17.9x on average).

While full-graph training is effective for graph learning, it typically demands substantial memory resources. Existing multi-GPU training frameworks struggle with scalability because they require retaining data for each layer within GPU memory. In this work, we presentHongTu, a memory-efficient system that supports out-of-memory full-graph GNN training on GPUs.HongTuoffloadsvertex data to CPU memory and employs partition parallelism training that splits and assigns large graphs to multiple GPUs. To reduce runtime memory consumption with optimal performance,HongTuutilizesa hybrid solution combining recomputation, caching, and computation-reordering, enabling efficient layer-wise intermediate data management. To address the increased communication caused by duplicated neighbor access among partitions,HongTuemploysa deduplicated communication framework that converts host-GPU transfers into more efficient inter/intra-GPU data access. Additionally,HongTutacklesthe load-imbalance issues in out-of-memory full-graph training, featuring a multi-objective graph partition algorithm that balances memory consumption and data transfer and maximizes the effectiveness of communication deduplication. Experiments on a 4×A100 GPU server show thatHongTucaneffectively train graphs with billion edges while reducing host-GPU data communication by 25% to 71%. Compared to the full-graph GNN system running on 16 CPU nodes,HongTuachievesspeedups ranging from 11.4× to 21.3×.

Spiking neural networks (SNNs) are well suited for resource-constrained applications as they do not need expensive multipliers. In a typical rate-encoded SNN, a series of binary spikes within a globally fixed time window is used to fire the neurons. The time window size is also the latency of the network in performing a single inference, as well as determining the overall energy efficiency of the model. The aim of this article is to reduce this while maintaining accuracy when converting artificial neural networks (ANNs) to their equivalent SNNs. The state-of-the-art conversion schemes yield SNNs with accuracies comparable with ANNs only for large window sizes. In this article, we start with understanding the information loss when converting from preexisting ANN models to standard rate-encoded SNN models. From these insights, we propose a suite of techniques that includes a novel SNN encoding scheme, a new spike generation model, an input channel expansion strategy, and a threshold training technique. Together, these methods enabled us to achieve state-of-the-art accuracies using the lowest latencies reported in the literature. In particular, our method achieved a top-1 SNN accuracy of 98.73% (using a single time step) on the MNIST dataset, 76.38% (with eight time steps) on the CIFAR-100 dataset, and 93.71% (eight time steps) on the CIFAR-10 dataset. On ImageNet, an SNN accuracy of 81.9% was achieved using 40 time steps.

Heterogeneous computing, which incorporates GPUs, NPUs, and FPGAs, is increasingly adopted to improve the efficiency of computer systems. However, this shift has given rise to significant security and privacy concerns, especially when the execution platform is remote. One way to tackle these challenges is to establish a trusted and isolated environment for remote program execution while maintaining minimal overhead and flexibility. While CPU-based trusted execution has been extensively explored and has found commercial success, extension to heterogeneous computing systems remains a challenge. This paper proposes a practical trusted execution environment design for ARM/FPGA System-on-Chip platforms, leveraging TrustZone’s unique characteristics. The design features a dedicated security controller within the ARM TrustZone, overseeing FPGA reconfiguration and managing communication between CPU cores and FPGA fabrics. This design involves a provisioning service $({\mathcal{P}})$ that enables application users $({\mathcal{U}})$ to establish trust in the FPGA fabric within cloud-based computing resources provided by the platform owner $({\mathcal{O}})$, running applications developed by third-party developers $({\mathcal{D}})$ and hardware manufactured by the device manufacturer $({\mathcal{M}})$. To ensure the security of our proposed system, we employ an automated protocol verifier, ProVerif, to validate its compliance with essential security requirements. Furthermore, we demonstrate the practicality of our system model by implementing a prototype application on the Xilinx MPSoC development board.

Attention mechanisms are becoming increasingly popular, being used in neural network models in multiple domains such as natural language processing (NLP) and vision applications, especially at the edge. However, attention layers are difficult to map onto existing neuro accelerators since they have a much higher density of non-linear operations, which lead to inefficient utilization of today's vector units. This work introduces NOVA, a NoC-based Vector Unit that can perform non-linear operations within the NoC of the accelerators, and can be overlaid onto existing neuro accelerators to map attention layers at the edge. Our results show that the NOVA architecture is up to 37.8x more power-efficient than state-of-the-art hardware approximators when running existing attention-based neural networks.

Recent advancements in neural network quantisation have yielded remarkable outcomes, with three-bit networks reaching state-of-the-art full-precision accuracy in complex tasks. These achievements present valuable opportunities for accelerating neural networks by computing in reduced precision. Implementing it on FPGAs can take advantage of bit-level reconfigurability, which is not available on conventional CPUs and GPUs. Simultaneously, the high data intensity of neural network processing has inspired computing-in-memory paradigms, including on FPGA platforms. By programming the effects of trained model weights as lookup operations in soft logic, the transfer of weight data from memory units can be avoided, alleviating the memory bottleneck. However, previous methods face poor scalability - the high logic utilisation limiting them to small networks/sub-networks of binary models with low accuracy. In this paper, we introduce Table Lookup Multiply-Accumulate (TLMAC) as a framework to compile and optimise quantised neural networks for scalable lookup-based processing. TLMAC clusters and maps unique groups of weights to lookup-based processing elements, enabling highly parallel computation while taking advantage of parameter redundancy. Further place and route algorithms are proposed to reduce LUT utilisation and routing congestion. We demonstrate that TLMAC significantly improves the scalability of previous related works. Our efficient logic mapping and high degree of reuse enables entire ImageNet-scale quantised models with full-precision accuracy to be implemented using lookup-based computing on one commercially available FPGA.

Large Language Models (LLMs) are increasingly used in various applications but are computationally complex and energy-consuming due to the high volume of off-chip memory accesses. Processing-in-Memory (PIM) has emerged as a potential solution for efficient inference. However, existing PIM accelerators designed for deep neural networks (DNNs) aren’t suitable for LLMs because of differences in operations, input sizes, and job completion times. This leads to performance issues like head-of-line blocking where an earlier job can monopolize resources at the expense of later jobs, and low resource utilization. To improve efficiency, a time-multiplex solution and job colocation accelerator could be beneficial. However, facilitating multi-job execution with in-memory acceleration is challenging due to limitations in memristor architecture, inefficiency of non-stationary weight programming, difficulty in dynamic partitioning of hardware resources, and complexity in dynamic job scheduling. This work proposes a PIM-based LLM accelerator to enable the concurrent LLM inference job execution. The experiment shows that IMI can significantly improve resource utilization as well as the rate of satisfying the service level requirements of jobs.

With the development of deep learning models, there has been growing research interest in spiking neural networks (SNNs) due to their energy efficiency resulting from their multiplier-less nature. The existing methodologies for SNN development include the conversion of artificial neural networks (ANNs) into equivalent SNNs or the emulation of ANNs, with two crucial challenges yet remaining. The first challenge involves preserving the accuracy of the original ANN models during the conversion to SNNs. The second challenge is to run complex SNNs with lower latencies. To solve the problem of high latency while maintaining high accuracy, we proposed a parallel spike-generation (PSG) method to generate all the spikes in a single timestep, while achieving a better model performance than the standard Integrate-and-Fire model. Based on PSG, we propose OneSpike, a highly effective framework that helps to convert any rate-encoded convolutional SNN into one that uses only one timestep without accuracy loss. Our OneSpike model achieves a state-of-the-art (for SNN) accuracy of 81.92% on the ImageNet dataset using just a single time step. To the best of our knowledge, this study is the first to explore converting multi-timestep SNNs into equivalent single-timestep ones, while maintaining accuracy. These results highlight the potential of our approach in addressing the key challenges in SNN research, paving the way for more efficient and accurate SNNs in practical applications.1

Approximate nearest neighbor search (ANNS) is crucial in various real-world applications, including recommendation systems, data mining, and image retrieval. To date, quantization-based algorithms have emerged as one of the most efficient solutions for ANNS on billion-scale datasets. However, the determination of the optimal number of clusters, a critical factor for peak data performance in quantization-based systems, remains inadequately explored. Previous works often propose numbers of clusters that are not optimal, and the absence of effective methodologies for tuning this parameter leads to suboptimal search performance due to the vast configuration space. In response to this challenge, this paper introduces a novel algorithm that automatically identifies the optimal number of clusters for billion-scale, quantization-based ANNS systems to maximize search efficiency. We propose an analytical model for evaluating retrieval performance, serving as the benchmark for optimizing cluster numbers in quantization-based indexes. Our algorithm applies iterative local adjustments to the ANNS index being constructed, progressively refining the number of clusters. We demonstrate the efficacy of our approach using the popular inverted index structure in quantization-based ANNS systems. Our findings indicate that: (1) By optimizing the number of clusters, the vanilla inverted index exhibits improved retrieval performance on billion-scale datasets when compared to existing state-of-the-art quantization-based methods; and (2) The additional computational overhead introduced by our optimization algorithm is minimal, even when applied to billion-scale datasets.

In-memory deep learning executes neural network models where they are stored, thus avoiding long-distance communication between memory and computation units, resulting in considerable savings in energy and time. In-memory deep learning has already demonstrated orders of magnitude higher performance density and energy efficiency. The use of emerging memory technology (EMT) promises to increase density, energy, and performance even further. However, EMT is intrinsically unstable, resulting in random data read fluctuations. This can translate to nonnegligible accuracy loss, potentially nullifying the gains. In this article, we propose three optimization techniques that can mathematically overcome the instability problem of EMT. They can improve the accuracy of the in-memory deep learning model while maximizing its energy efficiency. Experiments show that our solution can fully recover most models' state-of-the-art (SOTA) accuracy and achieves at least an order of magnitude higher energy efficiency than the SOTA.

Neuromorphic computing is promising to achieve unprecedented energy efficiency by emulating the human brain’s mechanism. Conventional neuromorphic accelerators employ split-and-merge method to map spiking neural networks’ inputs to surpass the fan-in capabilities of a single neuron core. However, this approach gives rise to the risk of accuracy compromise and extra core usage for the merging process. Moreover, it requires excessive data movement and clock cycles to aggregate spikes generated by partial sums instead of total sums obtained from different cores with substantial power and energy overhead. This work presents a novel approach to addressing the challenges imposed by the split-and-merge method. We propose an energy-efficient, reconfigurable neuromorphic processor that leverages several key techniques to mitigate the above issues. First, we introduce a partial sum router circuitry that enables in-network computing (INC), eliminating the need for extra merge cores. Second, we adopt software-defined Networks-on-Chip (NoCs) by leveraging predefined, efficient routing, eliminating power-hungry routing computation. At last, we incorporate fine-grained power gating and clock gating techniques for further power reduction. Experimental results from our test chip demonstrate the lossless mapping of the algorithm and exceptional energy efficiency, achieving an energy consumption of 1.63 pJ/SOP at 0.48 V. This energy efficiency represents a 22.4% improvement compared to the state-of-the-art results. Our proposed neuromorphic processor provides an efficient and flexible solution for neural network processing, mitigating the limitations of the traditional split-and-merge approach while delivering superior energy efficiency.

In this paper, we present OpenEmbedding, a distributed parameter server system for deep learning recommendation models (DLRM) workloads. In order to support rapid growth in the number of features and the model size (Terabytes are common) of DLRM workloads, OpenEmbedding takes advantage of emerging persistent memory (PMem) to address scalability and reliability issues in training DLRMs. Compared to DRAM, PMem can have much lower per-GB cost, higher density, and non-volatility, while with slightly low access performance to DRAM. OpenEmbedding uses DRAM as cache and PMem as storage for the sparse features and develops a simple but effective pipeline processing approach to optimize the access latency of the sparse features in PMem. For reliability, we develop a lightweight synchronous checkpointing scheme that is specially co-designed with the pipelined cache to reduce the run-time overhead of checkpointing. Our evaluations on a real-world industry workload consisting of billions of parameters demonstrate 1) the effectiveness of our PMem-aware optimizations, 2) checkpointing mechanism with near-zero run-time overhead to the training performance and 3) fast recovery with up to 3.97× speedup compared to the state-of-the-art. OpenEmbedding has been deployed in hundreds of scenarios in industry within 4Paradigm, and is open-sourced1.

Conventional neuromorphic accelerators primarily leverage split-merge method to accommodate a neural network that is beyond a single core's size, leading to possible accuracy loss, extra core usage and significant power and energy overhead. This work presents an energy-efficient, reconfigurable neuro-morphic processor to address the problem by (i) a partial sum router circuitry that enables in-network computing to remove the need of extra merge cores; (ii) software-defined Networks-on-Chip that eliminates the power-hungry routing compute and (iii) fine-grained power gating and clock gating technique for power reduction. Our test chip achieves lossless mapping as the algorithm and an energy efficiency of 1.7pJ/SOP at 0.5V, 19% lower than state-of-the-art result.

Graph dynamic random walks (GDRWs) have recently emerged as a powerful paradigm for graph analytics and learning applications, including graph embedding and graph neural networks. Despite the fact that many existing studies optimize the performance of GDRWs on multi-core CPUs, massive random memory accesses and costly synchronizations cause severe resource underutilization, and the processing of GDRWs is usually the key performance bottleneck in many graph applications. This paper studies an alternative architecture, FPGA, to address these issues in GDRWs, as FPGA has the ability of hardware customization so that we are able to explore fine-grained pipeline execution and specialized memory access optimizations. Specifically, we propose LightRW, a novel FPGA-based accelerator for GDRWs. LightRW embraces a series of optimizations to enable fine-grained pipeline execution on the chip and to exploit the massive parallelism of FPGA while significantly reducing memory accesses. As current commonly used sampling methods in GDRWs do not efficiently support fine-grained pipeline execution, we develop a parallelized reservoir sampling method to sample multiple vertices per cycle for efficient pipeline execution. To address the random memory access issues, we propose a degree-aware configurable caching method that buffers hot vertices on-chip to alleviate random memory accesses and a dynamic burst access engine that efficiently retrieves neighbors. Experimental results show that our optimization techniques are able to improve the performance of GDRWs on FPGA significantly. Moreover, LightRW delivers up to 9.55x and 9.10x speedup over the state-of-the-art CPU-based MetaPath and Node2vec random walks, respectively. This work is open-sourced on GitHub at https://github.com/Xtra-Computing/LightRW.

Full-graph training on graph neural networks (GNN) has emerged as a promising training method for its effectiveness. Full-graph training requires extensive memory and computation resources. To accelerate this training process, researchers have proposed employing multi-GPU processing. However the scalability of existing frameworks is limited as they necessitate maintaining the training data for every layer in GPU memory. To efficiently train on large graphs, we present HongTu, a scalable full-graph GNN training system running on GPU-accelerated platforms. HongTu stores vertex data in CPU memory and offloads training to GPUs. HongTu employs a memory-efficient full-graph training framework that reduces runtime memory consumption by using partition-based training and recomputation-caching-hybrid intermediate data management. To address the issue of increased host-GPU communication caused by duplicated neighbor access among partitions, HongTu employs a deduplicated communication framework that converts the redundant host-GPU communication to efficient inter/intra-GPU data access. Further, HongTu uses a cost model-guided graph reorganization method to minimize communication overhead. Experimental results on a 4XA100 GPU server show that HongTu effectively supports billion-scale full-graph GNN training while reducing host-GPU data communication by 25%-71%. Compared to the full-graph GNN system DistGNN running on 16 CPU nodes, HongTu achieves speedups ranging from 7.8X to 20.2X. For small graphs where the training data fits into the GPUs, HongTu achieves performance comparable to existing GPU-based GNN systems.

Spiking neural networks (SNNs) are attractive for energy-constrained use-cases due to their binarized activation, eliminating the need for weight multiplication. However, its lag in accuracy compared to traditional convolutional network networks (CNNs) has limited its deployment. In this paper, we propose CQ+ training (extended "clamped" and "quantized" training), an SNN-compatible CNN training algorithm that achieves state-of-the-art accuracy for both CIFAR-10 and CIFAR-100 datasets. Using a 7-layer modified VGG model (VGG-*), we achieved 95.06% accuracy on the CIFAR-10 dataset for equivalent SNNs. The accuracy drop from converting the CNN solution to an SNN is only 0.09% when using a time step of 600. To reduce the latency, we propose a parameterized input encoding method and a threshold training method, which further reduces the time window size to 64 while still achieving an accuracy of 94.09%. For the CIFAR-100 dataset, we achieved an accuracy of 77.27% using the same VGG-* structure and a time window of 500. We also demonstrate the transformation of popular CNNs, including ResNet (basic, bottleneck, and shortcut block), MobileNet v1/2, and Densenet, to SNNs with near-zero conversion accuracy loss and a time window size smaller than 60. The framework was developed in PyTorch and is publicly available.

Brain-inspired spiking neural networks (SNNs) replace the multiply-accumulate operations of traditional neural networks by integrate-and-fire neurons, with the goal of achieving greater energy efficiency. Specialized hardware implementations of those neurons clearly have advantages over general-purpose devices in terms of power and performance, but exhibit poor scalability when it comes to accelerating large neural networks. DeepFire2 introduces a hardware architecture which can map large network layers efficiently across multiple super logic regions in a multi-die FPGA. That gives more control over resource allocation and parallelism, benefiting both throughput and energy consumption. Avoiding the use of lookup tables to implement theANDoperations of an SNN, prevents the layer size to be limited by logic resources. A deep pipeline does not only lead to an increased clock speed of up to 600 MHz. We double the throughput and power efficiency compared to our previous version of DeepFire, which equates to an almost 10-fold improvement over other previous implementations. Importantly, we are able to deploy a large ImageNet model, while maintaining a throughput of over 1500 frames per second.

Quantum(-inspired) annealers show promise in solving combinatorial optimisation problems in practice. There has been extensive researches demonstrating the utility of D-Wave quantum annealer and quantum-inspired annealer, i.e., Fujitsu Digital Annealer on various applications, but few works are comparing these platforms. In this paper, we benchmark quantum(-inspired) annealers with three combinatorial optimisation problems ranging from generic scientific problems to complex problems in practical use. In the case where the problem size goes beyond the capacity of a quantum(-inspired) computer, we evaluate them in the context of decomposition. Experiments suggest that both annealers are effective on problems with small size and simple settings, but lose their utility when facing problems in practical size and settings. Decomposition methods extend the scalability of annealers, but they are still far away from practical use. Based on the experiments and comparison, we discuss the advantages and limitations of quantum(-inspired) annealers, as well as the research directions that may improve the utility and scalability of the these emerging computing technologies.

With the success of deep learning, there have been numerous efforts to build hardware for it. One approach that is gaining momentum is neuromorphic computing with spiking neural networks (SNNs), which are multiplication-free and open the possibility of using analog computing via novel technologies. However, to design effective and efficient hardware for such architectures, a fast and accurate software simulator is key. This article presents Simeuro, a fast and scalable system-level simulator for SNN models used in neuromorphic accelerators. The simulator uses spike-level details and configurable architectural constraints that are independent of the underlying hardware implementation. Simeuro supports a wide range of features including analog computing, novel memory (currently, RRAM is supported), and a full network-on-chip. The simulator can provide detailed simulation results such as routing statistics, energy consumption, delay, and accuracy of arbitrarily defined SNN architectures. Our simulator leverages a CPU-GPU hybrid environment to expedite the simulation by scaling out to multi-nodes equipped with multi-GPUs. We are able to conduct core simulations for a system-scale SNN chip of 20,000 neuromorphic cores on up to 512 A100 GPUs in a few minutes.

On-chip training improves model accuracy on personalised user data and preserves privacy. This work proposes REACT, an AI accelerator for wearables that has heterogeneous cores supporting both training and inference. REACT's architecture is NoC-centric, with weights, features and gradients distributed across cores, accessed and computed efficiently through software-configurable NoCs. Unlike conventional dynamic NoCs, REACT's NoCs have no buffer queues, flow control or routing, as they are entirely configured by software for each neural network. REACT's online learning realises upto 75% accuracy improvement, and is upto 25× faster and 520× more energy-efficient than state-of-the-art accelerators with similar memory and computation footprint.

The use of FPGAs for efficient graph processing has attracted significant interest. Recent memory subsystem upgrades including the introduction of HBM in FPGAs promise to further alleviate memory bottlenecks. However, modern multi-channel HBM requires much more processing pipelines to fully utilize its bandwidth potential. Due to insufficient resource efficiency, existing designs do not scale well, resulting in underutilization of the HBM facilities even when all other resources are fully consumed. In this paper, we propose ReGraph1, which customizes heterogeneous pipelines for diverse workloads in graph processing, achieving better resource efficiency, instantiating more pipelines and improving performance. We first identify workload diversity exists in processing graph partitions and classify them into two types: dense partitions established with good locality and sparse partitions with poor locality. Subsequently, we design two types of pipelines: Little pipelines with burst memory access technique to process dense partitions and Big pipelines tolerating random memory access latency to handle sparse partitions. Unlike existing monolithic pipeline designs, our heterogeneous pipelines are tailored for more specific workload characteristics and hence more lightweight, allowing the architecture to scale up more effectively with limited resources. We also present a graph-aware task scheduling method that schedules partitions to the right pipeline types, generates the most efficient pipeline combination and balances workloads. ReGraph surpasses state-of-the-art FPGA accelerators by 1.6×–5.9× in performance and 2.5×–12.3× in resource efficiency.

Neuromorphic computing chips consisting of crossbar arrays of emergent nonvolatile memory (NVM) have the potential of achieving both high energy efficiency and throughput as the low-power implementation of convolutional neural network (CNN) inference engines. However, such hardware has design constraints, such as its limited fan-in/fan-out and resource-inefficient mapping, that make the design and deployment of CNN on them challenging. As a result, the user has to design the CNN model with intricate knowledge of the hardware architecture and even cannot fit the models in the hardware for CNN with high resolution image input. In this article, we propose the use ofaggregated subnets, NC-net, which is a constrained form of the traditional layer structure, to solve these issues. With our method, we put forward an energy-efficient buffer- and analogue-to-digital converter and digital-to-analogue converter (ADC/DAC)-free architecture and a scalable end-to-end solution that automatically satisfies the hardware constraints of crossbar architectures, while optimizing the resource usage. In our solution, the exploration and deployment of a CNN for a neuromorphic crossbar hardware start with a design front end based onTensorFlow. Our automated design flow maps the NC-net network fromTensorFlowto the crossbar architecture. We tested our designs on both a simulator and a field-programmable gate array (FPGA) emulator with various benchmarks. In addition to general benchmarks, including MNIST, SVHN, CIFAR-10, and CIFAR-100, we tested our system on a real-world application, human detection with high resolution (224$\times $224) images as the input. Our system achieves the state-of-the-art accuracy for these benchmarks on the crossbar-based neuromorphic hardware, with an accuracy of more than 90% for the latter. It also yielded up to$4.25\times $improvement in the efficiency of spiking core usage compared to TrueNorth.

Driven by the demands of deep learning, many hardware accelerators, including GPUs, have begun to include specialized tensor processing units to accelerate matrix operations. However, general-purpose GPU applications that have little or no large dense matrix operations cannot benefit from these tensor units. This article proposes Tensorox, a framework that exploits the half-precision tensor cores available on recent GPUs for approximable, non deep learning applications. In essence, a shallow neural network is trained based on the input-output mapping of the function to be approximated. The key innovation in our implementation is the use of the small and dimension-restricted tensor operations in Nvidia GPUs to run multiple instances of the approximation neural network in parallel. With the proper scaling and training methods, our approximation yielded an overall accuracy that is higher than naïvely running the original programs with half-precision. Furthermore, Tensorox allows for the runtime adjustment of the degree of approximation. For the 10 benchmarks we tested, we achieved speedups from 2× to 112× compared to the original in single precision floating point, while maintaining the error caused by the approximation to below 10 percent in most applications.

FPGA has been an emerging computing infrastructure in datacenters benefiting from fine-grained parallelism, energy efficiency, and reconfigurability. Meanwhile, graph processing has attracted tremendous interest in data analytics, and its performance is in increasing demand with the rapid growth of data. Many works have been proposed to tackle the challenges of designing efficient FPGA-based accelerators for graph processing. However, the largely overlooked programmability still requires hardware design expertise and sizable development efforts from developers. ThunderGP , a high-level synthesis based graph processing framework on FPGAs, is hence proposed to close the gap, with which developers could enjoy high performance of FPGA-accelerated graph processing by writing only a few high-level functions with no knowledge of the hardware. ThunderGP adopts the gather-apply-scatter model as the abstraction of various graph algorithms and realizes the model by a built-in highly parallel and memory-efficient accelerator template. With high-level functions as inputs, ThunderGP automatically explores massive resources of multiple super-logic regions of modern FPGA platforms to generate and deploy accelerators, as well as schedule tasks for them. Although ThunderGP on DRAM-based platforms is memory bandwidth bounded, recent high bandwidth memory (HBM) brings large potentials to performance. However, the system bottleneck shifts from memory bandwidth to resource consumption on HBM-enabled platforms. Therefore, we further propose to improve resource efficiency of ThunderGP to utilize more memory bandwidth from HBM. We conduct evaluation with seven common graph applications and 19 graphs. ThunderGP on DRAM-based hardware platforms provides 1.9× ∼ 5.2× improvement on bandwidth efficiency over the state of the art, whereas ThunderGP on HBM-based hardware platforms delivers up to 5.2× speedup over the state-of-the-art RTL-based approach. This work is open sourced on GitHub at https://github.com/Xtra-Computing/ThunderGP .

Spiking neural networks (SNNs) significantly reduce energy consumption by replacing weight multiplications with additions. This makes SNNs suitable for energy-constrained platforms. However, due to its discrete activation, training of SNNs remains a challenge. A popular approach is to first train an equivalent CNN using traditional backpropagation, and then transfer the weights to the intended SNN. Unfortunately, this often results in significant accuracy loss, especially in deeper networks. In this paper, we propose CQ training (Clamped and Quantized training), an SNN-compatible CNN training algorithm with clamp and quantization that achieves near-zero conversion accuracy loss. Essentially, CNN training in CQ training accounts for certain SNN characteristics. Using a 7 layer VGG-* and a 21 layer VGG-19, running on the CIFAR-10 dataset, we achieved 94.16% and 93.44% accuracy in the respective equivalent SNNs. It outperforms other existing comparable works that we know of. We also demonstrate the low-precision weight compatibility for the VGG-19 structure. Without retraining, an accuracy of 93.43% and 92.82% using quantized 9-bit and 8-bit weights, respectively, was achieved. The framework was developed in PyTorch and is publicly available.

FPGAs have become emerging computing infrastructures for accelerating applications in datacenters. Meanwhile, high-level synthesis (HLS) tools have been proposed to ease the programming of FPGAs. Even with HLS, irregular data-intensive applications require explicit optimizations, among which multiple processing elements (PEs) with each owning a private BRAM-based buffer are usually adopted to process multiple data per cycle. Data routing, which dynamically dispatches multiple data to designated PEs, avoids data replication in buffers compared to statically assigning data to PEs, hence saving BRAM usage. However, the workload imbalance among PEs vastly diminishes performance when processing skew datasets. In this paper, we propose a skew-oblivious data routing architecture that allocates secondary PEs and schedules them to share the workload of the overloaded PEs at run-time. In addition, we integrate the proposed architecture into a framework called Ditto to minimize the development efforts for applications that require skew handling. We evaluate Ditto on five commonly used applications: histogram building, data partitioning, pagerank, heavy hitter detection and hyperloglog. The results demonstrate that the generated implementations are robust to skew datasets and outperform the state-of-the-art designs in both throughput and BRAM usage efficiency.

This paper proposes a set of methods that enables low precision posit ™ arithmetic to be successfully used for the training of generative adversarial networks (GANs) with minimal quality loss. We show that ultra low precision posits, as small as 6 bits, can achieve high quality output for the generation phase after training. We also evaluate floating-point (float) formats and compare them to 8-bit posits in the context of GAN training. Our scaling and adaptive calibration techniques are capable of producing superior training quality for 8-bit posits that surpasses 8-bit floats and matches the results of 16-bit floats. Hardware simulation results indicate that our methods have higher energy efficiency compared to both 16- and 8-bit float training systems.

FPGA has been an emerging computing infrastructure in datacenters benefiting from features of fine-grained parallelism, energy efficiency, and reconfigurability. Meanwhile, graph processing has attracted tremendous interest in data analytics, and its performance is in increasing demand with the rapid growth of data. Many works have been proposed to tackle the challenges of designing efficient FPGA-based accelerators for graph processing. However, the largely overlooked programmability still requires hardware design expertise and sizable development efforts from developers.

Spiking neural networks (SNN) with their ‘integrate and fire’ (I&F) neurons replace the hardware-intensive multiply-accumulate (MAC) operations in convolutional neural networks (CNN) with accumulate operations — not only making it easy to implement on FPGAs but also opening up the opportunities for energy-efficient hardware acceleration. In this paper, we propose DeepFire — the high-performance RTL IP — for accelerating convolutional SNN inference. The IP exploits various resources available on modern FPGAs, and it outperforms existing SNN implementations by more than 10× in terms of both frame per second (FPS) and performance per watt (FPS/Watt). Our design achieves up to 40.1kFPS and 28.3kFPS on MNIST and CIFAR-10/SVHN datasets with 99.14% and 81.8%/93.1% accuracies respectively. IP was evaluated with 7-series and Ultrascale+ FPGAs from Xilinx achieving Fmax of 375MHz and 500MHz respectively.

In this paper, we propose ThundeRiNG, a resource-efficient and high-throughput system for generating multiple independent sequences of random numbers (MISRN) on FPGAs. Generating MISRN can be a time-consuming step in many applications such as numeric computation and approximate computing. Despite that decades of studies on generating a single sequence of random numbers on FPGAs have achieved very high throughput and high quality of randomness, existing MISRN approaches either suffer from heavy resource consumption or fail to achieve statistical independence among sequences. In contrast, ThundeRiNG resolves the dependence by using a resource-efficient decorrelator among multiple sequences, guaranteeing a high statistical quality of randomness. Moreover, ThundeRiNG develops a novel state sharing among a massive number of pseudo-random number generator instances on FPGAs. The experimental results show that ThundeRiNG successfully passes the widely used statistical test, TestU01, only consumes a constant number of DSPs (less than 1% of the FPGA resource capacity) for generating any number of sequences, and achieves a throughput of 655 billion random numbers per second. Compared to the state-of-the-art GPU library, ThundeRiNG demonstrates a 10.62x speedup on MISRN and delivers up to 9.15x performance and 26.63x power efficiency improvement on two applications (pi estimation and Monte Carlo option pricing). This work is open-sourced on Github at https://github.com/Xtra-Computing/ThundeRiNG.

On-line decision augmentation (OLDA) has been considered as a promising paradigm for real-time decision making powered by Artificial Intelligence (AI). OLDA has been widely used in many applications such as real-time fraud detection, personalized recommendation, etc. On-line inference puts real-time features extracted from multiple time windows through a pre-trained model to evaluate new data to support decision making. Feature extraction is usually the most time-consuming operation in many OLDA data pipelines. In this work, we started by studying how existing in-memory databases can be leveraged to efficiently support such real-time feature extractions. However, we found that existing in-memory databases cost hundreds or even thousands of milliseconds. This is unacceptable for OLDA applications with strict real-time constraints. We therefore propose FEDB ( F eature E ngineering D ata b ase), a distributed in-memory database system designed to efficiently support on-line feature extraction. Our experimental results show that FEDB can be one to two orders of magnitude faster than the state-of-the-art in-memory databases on real-time feature extraction. Furthermore, we explore the use of the Intel Optane DC Persistent Memory Module (PMEM) to make FEDB more cost-effective. When comparing the proposed PMEM-optimized persistent skiplist to the FEDB using DRAM+SSD, PMEM-based FEDB can shorten the tail latency up to 19.7%, reduce the recovery time up to 99.7%, and save up to 58.4% total cost of a real OLDA pipeline.

This article presents GRAM (GPU-based Runtime Adaption for Mixed-precision) a framework for the effective use of mixed precision arithmetic for CUDA programs. Our method provides a fine-grain tradeoff between output error and performance. It can create many variants that satisfy different accuracy requirements by assigning different groups of threads to different precision levels adaptively at runtime . To widen the range of applications that can benefit from its approximation, GRAM comes with an optional half-precision approximate math library. Using GRAM, we can trade off precision for any performance improvement of up to 540%, depending on the application and accuracy requirement.

Feedback loops regulate various biological functions such as oscillations, bistability, and robustness. They play a significant role in developmental signalling and failure of feedback can lead to disease. Systematic analysis of feedback loops could be useful in understanding their properties and biological effects. We propose here a method to automatically analyze feedback loops in bio-pathways and synthesize temporal logic properties which describe their dynamics. Starting with an ordinary differential equations (ODEs) based model of a bio-pathway, for a chosen feedback loop present in the pathway, we use a convolutional neural network to classify the behaviours of the key components of the feedback according to templates specified in bounded linear temporal logic (BLTL). Once a template has been identified, we instantiate the symbolic variables appearing in the template and synthesize properties using a parameter estimation procedure based on sequential hypothesis testing. We have applied this framework to a number of bio-pathway models and validated that the synthesized properties faithfully describe the behaviours of the feedback loops.

The next wave of on-device AI will likely require energy-efficient deep neural networks. Brain-inspired spiking neural networks (SNN) has been identified to be a promising candidate. Doing away with the need for multipliers significantly reduces energy. For on-device applications, besides computation, communication also incurs a significant amount of energy and time. In this paper, we propose Shenjing, a configurable SNN architecture which fully exposes all on-chip communications to software, enabling software mapping of SNN models with high accuracy at low power. Unlike prior SNN architectures like TrueNorth, Shenjing does not require any model modification and retraining for the mapping. We show that conventional artificial neural networks (ANN) such as multilayer perceptron, convolutional neural networks, as well as the latest residual neural networks can be mapped successfully onto Shenjing, realizing ANNs with SNN’s energy efficiency. For the MNIST inference problem using a multilayer perceptron, we were able to achieve an accuracy of 96% while consuming just 1.26 mW using 10 Shenjing cores.

Modern file systems rely on the journaling mechanism to maintain crash consistency. The use of non-volatile memory (NVM) significantly improves the performance of journaling file systems. However, the superior performance of NVM will increase the likelihood of the journal filling up more often, thereby increasing the frequency of checkpointing. Together with the large amount of random checkpointing I/O found in most use cases, the checkpointing process becomes a new performance bottleneck. This paper proposes NV-Journaling, a strategy that reduces the frequency of checkpointing as well as reshapes the I/O pattern of checkpointing from one of random I/O to that which is more sequential I/O. NV-Journaling introduces fine-grained commits along with a cache-friendly NVM journaling layout that exploits the idiosyncrasies of NVM technology. Under this scheme, only the modified portion of a block, rather than the entire block, is written into the NVM journal device. Doing so significantly reduces checkpoint frequency and achieves better space utilization. NV-Journaling further reshapes the I/O pattern of checkpoint using a locality-aware checkpointing process. Checkpointed blocks are classified into hot and cold blocks. NV-Journaling maintains a hot block list to absorb repeated updates, and a cold bucket list to group blocks by their proximity on disk. When a checkpoint is required, cold buckets are selected such that blocks are sequentially flushed to the hard disk. We built a prototype of NV-Journaling by modifying the JBD2 layer in the Linux kernel and evaluated it using different workloads. Our experimental results show that NV-Journaling can improve performance by up to 4.3× compared to traditional journaling.

Neuromorphic chip with RRAM devices has been demonstrated as a promising computing platform for neural network-based applications. By directly mapping the weight matrices of neural networks onto RRAM-based crossbar arrays, high energy, and area efficiency can be achieved. However, the design of an RRAM-based neuromorphic chip faces many constraints due to the variability and limitations of RRAM. Simulation and emulation can help in the design of a neuromorphic chip prior to fabrication. However, software-based chip simulation on CPU is slow, especially for large-scale network-on-chip (NoC)-based chip design. In this paper, we present a hardware emulator on field-programmable gate array (FPGA) for an RRAM-based neuromorphic chip. Our emulator supports the emulation of static and dynamic variation of the RRAM-based crossbars used in the neural cores of a neuromorphic chip. Furthermore, an NoC is also implemented on FPGA to emulate the communication between the neural cores. Using the emulator, we show that effects, such as RRAM write and read noise and stuck-at faults affect the accuracy of an application on a neuromorphic chip. We also demonstrate the utility of the emulator in investigating NoC topologies, routing buffer depths, and neural core mappings.

According to the World Health Organization, cardio-vascular diseases accounts for 31% of all deaths worldwide in 2016. Detecting the onset of heart irregularities can potentially save many lives. The ubiquity of wearable devices opens up the possibility of having a heart disease detection at everyone's disposal. To enable this, low energy ECG classification is needed. Unlike previous methods of using signal processing or even deep learning networks, this paper is the first to propose a low cost means to detect abnormal ECG beat signals by first synthesizing temporal logic formulas from training signals, and then checking if the synthesized formulas by the input signal at runtime. Our results show that the method has a high accuracy in detecting abnormal ECG beats while requiring significantly lower computation resource. Compared to It takes only a state-of-the-art convolutional neural network approach, our method achieves a comparable accuracy but with 0.3% of memory, and millions of computation operations, hence energy, saved.

Precision tuning post-training is often needed for efficient implementation of deep neural networks especially when the inference implementation platform is resource constrained. While previous works have proposed many ad hoc strategies for this task, this paper describes a general method for allocating precision to trained deep neural networks data based on a property relating errors in a network. We demonstrate that the precision results of previous works for hardware accelerator or understanding cross layer precision requirement is subsumed by the proposed general method. It has achieved a 29% and 46% energy saving over the state-of-the-art search-based method for GoogleNet and VGG-19 respectively. Proposed precision allocation method can be used to optimize for different criteria based on hardware design constraints, allocating precision at the granularity of layers for very deep networks such as Resnet-152, which hitherto was not achievable.

Graph processing has attracted much attention recently due to its popularity in many big data analytic applications. With high performance and energy efficiency, FPGAs can be an attractive architecture for graph processing. A number of techniques such as caching using block RAMs (BRAMs) to reduce random accesses of global memory and multiple processing element (PE) instances for high throughput have been explored. OpenCL-based FPGAs natively support a high-level programming paradigm, providing good programmability to developers. However, challenges remain because the run-time dependency introduced by multiple PEs usually cannot be handled efficiently by OpenCL's high-level control granularity. In this paper, we propose a novel on-the-fly parallel data shuffling technique that can be implemented in OpenCL to solve this problem. We have integrated our shuffling technique to an edge-centric graph processing framework which achieves a throughput of more than 1,000 million traversed edges per second (MTEPS) on PageRank, SpMV, BFS and SSSP applications and is even better than existing RTL-based designs.

Approximate computing, a technique that forgoes quantifiable output accuracy in favor of performance gains, is useful for improving the energy efficiency of error-resilient software, especially in the embedded setting. The identification of program components that can tolerate error plays a crucial role in balancing the energy vs. accuracy trade off in approximate computing. Manual analysis for approximability is not scalable and therefore automated tools which employ static or dynamic analysis have been proposed. However, static techniques are often coarse in their approximations while dynamic efforts incur high overhead. In this work we present ApproxSymate, a framework for automatically identifying program approximations using symbolic execution. ApproxSymate first statically computes symbolic error expressions for program components and then uses a dynamic sensitivity analysis to compute their approximability. A unique feature of this tool is that it explores the previously not considered dimension of program path for approximation which enables safer transformations. Our evaluation shows that ApproxSymate averages about 96% accuracy in identifying the same approximations found in manually annotated benchmarks, outperforming existing automated techniques.

Advances in non-volatile resistive switching random access memory (RRAM) have made it a promising memory technology with potential applications in low-power and embedded in-memory computing devices owing to a number of advantages such as low-energy consumption, low area cost and good scaling. There have been proposals to employ RRAM in architecting chips for neuromorphic computing and artificial neural networks where matrix-vector multiplication can be computed in the analog domain in a single timestep. However, it is challenging to employ RRAM devices in neuromorphic chips owing to the non-ideal behavior of RRAM. In this article, we propose a cycle-accurate and scalable system-level simulator that can be used to study the effects of using RRAM devices in neuromorphic computing chips. The simulator models a spatial neuromorphic chip architecture containing many neural cores with RRAM crossbars connected via a Network-on-Chip (NoC). We focus on system-level simulation and demonstrate the effectiveness of our simulator in understanding how non-linear RRAM effects such as stuck-at-faults (SAFs), write variability, and random telegraph noise (RTN) can impact an application’s behavior. By using our simulator, we show that RTN and write variability can have adverse effects on an application. Nevertheless, we show that these effects can be mitigated through proper design choices and the implementation of a write-verify scheme.

In-memory data management systems have recently gained a lot of attraction due to cheaper and faster DRAM and other hardware advancement. However, these systems are either pure storage systems with online data query service, or just offline batch processing systems with data analytics functionality. Heavy data movement (e.g., data loading) occurs in order to analyze the data. In this paper, we propose an innovative in-memory data management system-MemepiC, which unifies both online data query and data analytics functionality, allowing low-latency storage service and efficient in-situ data analytics. We also explore the emerging RDMA technique in the context of in-memory data management systems, by designing an RDMA-based communication protocol for message delivery inside MemepiC, and proposing to overlap execution and RDMA communication. Extensive experiments are conducted to show the superior performance of MemepiC in terms of both the storage and the data analytics services, compared against other in-memory systems.

This paper describes a fault tolerant framework for distributed stencil computation on cloud-based GPU clusters. It uses pipelining to overlap the data movement with computation in the halo region as well as parallelises data movement within the GPUs. Instead of running stencil codes on traditional clusters and supercomputers, the computation is performed on the Amazon Web Service GPU cloud, and utilizes its spot instances to improve cost-efficiency. The implementation is based on a low-cost fault-tolerant mechanism to handle the possible termination of the spot instances. Coupled with a price bidding module, our stencil framework not only optimizes for performance but also for cost. Experimental results show that our framework outperforms the state-of-the-art solutions achieving a peak of 25 TFLOPS for 2-D decomposition running on 512 nodes. We also show that the use of spot instances yields good cost-efficiency, increasing the average TFLOPS/USD from 132 to 360.

An important class of applications computes on long-running or infinite streams of data, often with known fixed data rates. The latter is referred to as synchronous data flow ~(SDF) streams. These stream applications need to run on clusters or the cloud due to the high performance requirement. Further, they require live reconfiguration and reoptimization for various reasons such as hardware maintenance, elastic computation, or to respond to fluctuations in resources or application workload. However, reconfiguration and reoptimization without downtime while accurately preserving program state in a distributed environment is difficult. In this paper, we introduce Gloss, a suite of compiler and runtime techniques for live reconfiguration of distributed stream programs. Gloss, for the first time, avoids periods of zero throughput during the reconfiguration of both stateless and stateful SDF based stream programs. Furthermore, unlike other systems, Gloss globally reoptimizes and completely recompiles the program during reconfiguration. This permits it to reoptimize the application for entirely new configurations that it may not have encountered before. All these Gloss operations happen in-situ, requiring no extra hardware resources. We show how Gloss allows stream programs to reconfigure and reoptimize with no downtime and minimal overhead, and demonstrate the wider applicability of it via a variety of experiments.

Strassen's recursive algorithm for matrix-matrix multiplication has seen slow adoption in practical applications despite being asymptotically faster than the traditional algorithm. A primary cause for this is the comparatively weaker numerical stability of its results. Techniques that aim to improve the errors of Strassen stand the risk of losing any potential performance gain. Moreover, current methods of evaluating such techniques for safety are overly pessimistic or error prone and generally do not allow for quick and accurate comparisons. In this paper we present an efficient technique to obtain rigorous error bounds for floating point computations based on an implementation of unum arithmetic. Using it, we evaluate three techniques - exact dot product, fused multiply-add, and matrix quadrant rotation - that can potentially improve the numerical stability of Strassen's algorithm for practical use. We also propose a novel error-based heuristic rotation scheme for matrix quadrant rotation. Finally we apply techniques that improve numerical safety with low overhead to a LINPACK linear solver to demonstrate the usefulness of the Strassen algorithm in practice.

This paper presents an automatic tool-chain that efficiently computes the precision of floating point variables down to the bit level of the mantissa. Our toolchain uses a distributed algorithm that can analyze thousands of variables. We successfully used the tool to transform floating point signal processing programs to their arbitrary precision fixed-point equivalent, obtaining about 82% and 66% average reduction in resources when compared to the double precision and single precision versions, respectively.

Due to the coarse granularity of data accesses and the heavy use of latches, indices in the B-tree family are not efficient for in-memory databases, especially in the context of today's multi-core architecture. In this paper, we study the parallelizability of skip lists for the parallel and concurrent environment, and present PSL, a Parallel in-memory Skip List that lends itself naturally to the multi-core environment, particularly with non-uniform memory access. For each query, PSL traverses the index in a Breadth-First-Search (BFS) to find the list node with the matching key, and exploits SIMD processing to speed up this process. Furthermore, PSL distributes incoming queries among multiple execution threads disjointly and uniformly to eliminate the use of latches and achieve a high parallelizability. The experimental results show that PSL is comparable to a readonly index, FAST, in terms of read performance, and outperforms ART and Masstree respectively by up to 30% and 5x for a variety of workloads.

NAND flash memory is widely used for the secondary storage of computer systems. Theflash translation layer(FTL) is the firmware that manages and operates a flash-based storage device. One of the FTL's modules manages the RAM buffer of the flash device. Now this RAM buffer is sufficient to be used for both address mapping and data buffering. As the fastest component of the flash layer interface, effective management of this buffer has a significant impact on the performance of data storage and access. This paper proposes a novel scheme calledTreeFTLfor this purpose. TreeFTL organizes address translation pages and data storage pages in atree-likestructure in the RAM buffer. The tree enables TreeFTL to adapt to the access behaviors of workloads by dynamically adjusting the partitions for address mapping and data buffering. Furthermore, TreeFTL employs alightweightmechanism to evict the least-recently-used victim pages when the need arises. Our experiments show that TreeFTL is able to spend 46.6 and 49.0 percent less service time over various workloads than two state-of-the-art algorithms, respectively, for a 64 MB RAM buffer.

The widely adopted single-threaded OLTP model assigns a single thread to each static partition of the database for processing transactions in a partition. This simplifies concurrency control while retaining parallelism. However, it suffers performance loss arising from skewed workloads as well as transactions that span multiple partitions. In this paper, we present a dynamic single-threaded in-memory OLTP system, called LADS, that extends the simplicity of the single-threaded model. The key innovation in LADS is the separation of dependency resolution and execution into two non-overlapping phases for batches of transactions. After the first phase of dependency resolution, the record actions of the transactions are partitioned and ordered. Each independent partition is then executed sequentially by a single thread, avoiding the need for locking. By careful mapping of the tasks to be performed to threads, LADS is able to achieve a high degree of balanced parallelism. We evaluate LADS against H-Store, a partition-based database; DORA, a data-oriented transaction processing system; and SILO, a multi-core in-memory OLTP engine. The experimental study shows that LADS achieves up to 20x higher throughput than existing systems and exhibits better robustness with various workloads.

Approximate computing is a paradigm for trading off program accuracy to save energy in memory or computational resources. However, determining feasible program approximations is difficult to achieve. Popular solutions involve programmer in annotating instructions or data that can be approximated. Recently, program testing based techniques have also been explored. But these are computationally expensive and time consuming as they require running the applications many times over. In this paper, we propose PAC - Program Analysis for Approximation aware Compilation, a compiler framework to extract feasible approximation in a program. The state-of-the-art competitors only partition instructions or program data into accurate or approximable. In PAC, instructions and program data are assigned with a degree of accuracy required to maintain user specified Quality-of-Service (QoS) of an application. Such information allows the approximation to be fine-tuned in line with changes in the QoS requirements.

The increase in the capacity of main memory coupled with the decrease in cost has fueled the development of in-memory database systems that manage data entirely in memory, thereby eliminating the disk I/O bottleneck. However, as we shall explain, in the Big Data era, maintaining all data in memory is impossible, and even unnecessary. Ideally we would like to have the high access speed of memory, with the large capacity and low price of disk. This hinges on the ability to effectively utilize both the main memory and disk. In this paper, we analyze state-of-the-art approaches to achieving this goal for in-memory databases, which is called as “Anti-Caching” to distinguish it from traditional caching mechanisms. We conduct extensive experiments to study the effect of each fine-grained component of the entire process of “Anti-Caching” on both performance and prediction accuracy. To avoid the interference from other unrelated components of specific systems, we implement these approaches on a uniform platform to ensure a fair comparison. We also study the usability of each approach, and how intrusive it is to the systems that intend to incorporate it. Based on our findings, we propose some guidelines on designing a good “Anti-Caching” approach, and sketch a general and efficient approach, which can be utilized in most in-memory database systems without much code modification.

Directive-based programming approaches such as OpenMP and OpenACC have gained popularity due to their ease of programming. These programming models typically involve adding compiler directives to code sections such as loops in order to parallelize them for execution on multicore CPUs or GPUs. However, one problem with this approach is that existing compilers generate code directly from the annotated sections and do not make use of hardware-specific architectural features. As a result, the generated code is unable to fully exploit the capabilities of the underlying hardware. Alternatively, we propose a code generation framework in which linear algebraic operations in the annotated codes are recognized, extracted and mapped to optimized vendor-provided platform-specific library calls. We demonstrate that such an approach can result in better performance in the generated code compared to those which are generated by existing compilers. This is substantiated by experimental results on multicore CPUs and GPUs.

Sparse matrix-vector multiplication (SpMV) is an important kernel that is used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness due to the low arithmetic intensity of the kernel. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of bit-representation-optimized (BRO) compression formats for representing sparse matrices on GPUs. The proposed formats - BRO-CSR, BRO-ELL and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through the reduction of memory traffic. We also propose two other hybrid BRO formats which can potentially perform better than both HYB and BRO-HYB formats. Experimental results demonstrate that compared to uncompressed CSR and ELLPACK formats, our proposed compressed BRO-CSR and BRO-ELL formats are able to achieve average speedups of 2× and 1.4× respectively. Furthermore, we demonstrate that by using BRO-ELL, the preconditioned conjugate gradient method is able to achieve an average speedup of 1.3× over ELLPACK.

STT-RAM is an emerging NVRAM technology that promises high density, low energy and a comparable access speed to conventional SRAM. This paper proposes a hybrid L1 cache architecture that incorporates both SRAM and STT-RAM. The key novelty of the proposal is the exploition of the MESI cache coherence protocol to perform dynamic block reallocation between different cache partitions. Compared to the pure SRAM-based design, our hybrid scheme achieves 38% of energy saving with a mere 0.8% IPC degradation while extending the lifespan of STT-RAM partition at the same time.

Virtual memory is optimized for SRAM-based memory devices in which memory accesses are symmetric, i.e., the latency of read and write accesses are similar. Unfortunately, with the emergence of newer non-volatile memory (NVM) technologies that are denser and more energy efficient, this assumption is no longer valid. For example, STT-RAMs are known to have high write latencies and limited write endurance which the virtual memory is unaware of. A popular architecture is a hybrid cache that uses both SRAM and NVM. There are a number of proposals for such architectures at nearly all the levels of the cache. However, these proposals are often self-contained with monitoring and management schemes implemented with special hardware at the level where the cache is deployed. With moves to use NVM at several levels of the memory hierarchy, such solutions may lead to duplication and higher overheads. Worse, because the management algorithms implemented can be different at different levels of memory, it may lead to negative interference between them resulting in impaired efficiency.

The use of STT-RAM as on-chip caches has been widely studied. However, existing works focused mainly on single-level cell (SLC) design while the potential of multi-level cell (MLC) STT-RAM has not yet been fully explored. It is expected that MLC STT-RAM can achieve 2× the storage density of SLC and thus improves system performance. Unfortunately, at the device level, the two-step read/write scheme introduces performance and energy overhead. In this paper, we propose an architectural design to dynamically reconfigure the cache block size for a MLC STT-RAM last-level cache. Our approach place certain hot data chunks in smaller blocks so as to benefit from the lower latency and energy, while keeping the rest in larger blocks to maintain an overall hit rate. Experiment shows that our strategy reduces the performance and energy penalty of MLC STT-RAM caches with a slightly higher miss rate. On average, IPC is increased by 4.6% while energy consumption is reduced by 23.5% compared to the conventional MLC STT-RAM cache.

The approximation based programming paradigm is especially attractive for developing error-resilient applications, targeting low power embedded devices. It allows for program data to be computed and stored approximately for better energy efficiency. The duration of battery in the smartphones, tablets, etc. is generally more of a concern to users than an application's accuracy or fidelity beyond certain acceptable quality of service. Therefore, relaxing accuracy to improve energy efficiency is an attractive trade-off when permissible by the application's domain. Recent works suggest source code annotations and type qualifiers to facilitate safe approximate computation and data manipulation. It requires rewriting of programs or the availability of source codes for annotations. This may not be feasible as real-world applications tend to be large, with source code that is not readily available.

There are many domain libraries, but despite the performance benefits of compilation, domain-specific languages are comparatively rare due to the high cost of implementing an optimizing compiler. We propose commensal compilation, a new strategy for compiling embedded domain-specific languages by reusing the massive investment in modern language virtual machine platforms. Commensal compilers use the host language's front-end, use host platform APIs that enable back-end optimizations by the host platform JIT, and use an autotuner for optimization selection. The cost of implementing a commensal compiler is only the cost of implementing the domain-specific optimizations. We demonstrate the concept by implementing a commensal compiler for the stream programming language StreamJIT atop the Java platform. Our compiler achieves performance 2.8 times better than the StreamIt native code (via GCC) compiler with considerably less implementation effort.

Graphics processing units leverage on a large array of parallel processing cores to boost the performance of the streaming computation patterns frequently found in graphics applications. Unfortunately, while many other general purpose applications also exhibit streaming behavior, they possess unfavorable data layout and poor computation-to-communication ratios that may penalize any straight-forward GPU implementation. In this paper we describe a performance-driven code generation framework that maps general purpose streaming applications onto GPU systems. This automated framework takes into account the idiosyncrasies of the GPU pipeline and the unique memory hierarchy. The framework has been implemented as a back-end to the StreamIt programming language compiler. Several key features in this framework ensure maximized performance and scalability. First, the generated code increases the effectiveness of the on-chip memory hierarchy by employing a heterogeneous mix of compute and memory access threads. Our scheme goes against the conventional wisdom of GPU programming which is to use a large number of homogeneous threads. Second, we utilise an efficient stream graph partitioning algorithm to handle larger applications and achieve the best performance under the given on-chip memory constraints. Lastly, the framework maps complex applications onto multiple GPUs using a highly effective parallel execution scheme. Our comprehensive experiments show its scalability and significant speedup compared to a previous state-of-the-art solution.

Spin-transfer torque random access memory (STT-RAM) is the most promising candidate to be universal memory due to its good scalability, zero standby power, and radiation hardness. Having a cell area only 1/9 to 1/3 that of SRAM, allows for a much larger cache with the same die footprint. Such reduction of cell size can significantly shrink the cache array size, leading to significant improvement of overall system performance and power consumption, especially in this multicore era where locality is crucial. However, deploying STT-RAM technology in L1 caches is challenging because write operations on STT-RAM are slow and power-consuming. In this paper, we propose a range of cache hierarchy designs implemented entirely using STT-RAM that deliver optimal power saving and performance. In particular, our designs use STT-RAM cells with various data retention times and write performances, made possible by novel magnetic tunneling junction designs. For L1 caches where speed is of utmost importance, we propose a scheme that uses fast STT-RAM cells with reduced data retention time coupled with a dynamic refresh scheme. In the dynamic refresh scheme, another emerging technology, memristor, is used as the counter to monitor the data retention of the low-retention STT-RAM, achieving a higher array area efficiency than an SRAM-based counter. For lower level caches with relatively larger cache capacities, we propose a design that has partitions of different retention characteristics, and a data migration scheme that moves data between these partitions. The experiments show that on the average, our proposed multiretention level STT-RAM cache reduces total energy by as much as 30%-74.2% compared to previous single retention level STT-RAM caches, while improving instruction per cycle performance for both two-level and three-level cache hierarchies.

The write endurance of NAND flash memory adversely impacts the lifetime of flash devices. A flash cell is likely to wear out after undergoing excessive program/erase (P/E) flips. Wear leveling is hence employed to spread erase operations as evenly as possible. It is traditionally conducted by the flash translation layer (FTL), a management firmware residing in flash devices. In this paper, we shall propose a novel wear leveling algorithm involving the operating system (OS). We will show that our operating System-Assisted Wear leveling (SAW) algorithm can significantly improve the wear evenness. SAW takes advantage of OS's knowledge about files at a higher level of abstraction, and provides useful hints to the lower-level FTL to accommodate data. A prototype based on a file system and an FTL has been developed to verify the effectiveness of SAW. Experiments show that wear evenness can be improved by as much as 85.0% compared to the state-of-the-art FTL wear leveling schemes.

NAND flash memory is widely used for secondary storage today. The flash translation layer (FTL) is the embedded software that is responsible for managing and operating in flash storage system. One important module of the FTL performs RAM management. It is well-known to have a significant impact on flash storage system's performance. This paper proposes an efficient RAM management scheme called TreeFTL. As the name suggests, TreeFTL organizes address translation pages and data pages in RAM in a tree structure, through which it dynamically adapts to workloads by adjusting the partitions for address mapping and data buffering. TreeFTL also employs a lightweight mechanism to implement the least recently used (LRU) algorithm for RAM cache evictions. Experiments show that compared to the two latest schemes for RAM management in flash storage system, TreeFTL can reduce service time by 46.6% and 49.0% on average, respectively, with a 64MB RAM cache.

Stencils represent an important class of computations that are used in many scientific disciplines. Increasingly, many of the stencil computations in scientific applications are being offloaded to GPUs to improve running times. Since a large part of the simulation time is spent inside the stencil kernels, optimizing the kernel is therefore important in the context of achieving greater computation efficiencies and reducing simulation time. In this work, we proposed a novel in-plane method for stencil computations on GPUs and compared its performance with the conventional method implemented in the Nvidia SDK. We also implemented an auto-tuning framework for our method to select the optimal parameters for different GPU architectures. A performance model was developed for our proposed method, and is used to speed up the auto-tuning process. Our results show that a speedup of nearly 2× can be achieved compared to Nvidia's implementation.

Recently, the discovery of memristor brought the promise of high density, low energy, and combined memory/arithmetic capability into computing. This paper demonstrates a practical neural branch predictor based on memristor. By using analog computation techniques, as well as exploiting the accuracy tolerance of branch prediction, our design is able to efficiently realize a neural prediction algorithm. Compared to the digital counterpart, our method achieves significant energy reduction while maintaining a better prediction accuracy and a higher IPC. Our approach also reduces the resource and energy required by an alternative design.

The sparse matrix-vector (SpMV) multiplication routine is an important building block used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of bit-representation-optimized (BRO) compression schemes for representing sparse matrices on GPUs. The proposed schemes, BRO-ELL, BRO-COO, and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through reduction of memory traffic. Furthermore, we formulate a BRO-aware matrix reordering scheme as a data clustering problem and use it to increase compression ratios. With the proposed schemes, experiments show that average speedups of 1.5x compared to ELLPACK and HYB can be achieved for SpMV on GPUs.

It has been predicted that a processor's caches could occupy as much as 90% of chip area a few technology nodes from the current ones. In this article, we investigate the use of multilevel spin-transfer torque RAM (STT-RAM) cells in the design of processor caches. We start with examining the access (read and write) scheme for multilevel cell (MLC) STT-RAM from a circuit design perspective, detailing the read and write circuits. Compared to traditional SRAM caches, a multilevel cell (MLC) STT-RAM cache design is denser, fast, and requires less energy. However, a number of critical architecture-level issues remain to be solved before MLC STT-RAM technology can be deployed in processor caches. We shall offer solutions to the issue of bit encoding as well as tackle the write endurance problem. In particular, the latter has been neglected in previous works on STT-RAM caches. We propose a set remapping scheme that can potentially prolong the lifetime of a MLC STT-RAM cache by 80× on average. Furthermore, a method for recovering the performance that may be lost in some applications due to set remapping is proposed. The impacts of process variations of the MLC STT-RAM cell on the robustness of the memory hierarchy is also discussed, together with various enhancement techniques, namely, ECC and design redundancy.

We present a novel code generation scheme for GPUs. Its key feature is the platform-aware generation of a heterogeneous pool of threads. This exposes more data-sharing opportunities among the concurrent threads and reduces the memory requirements that would otherwise exceed the capacity of the on-chip memory. Instead of the conventional strategy of focusing on exposing as much parallelism as possible, our scheme leverages on the phased nature of memory access patterns found in many applications that exhibit massive parallelism. We demonstrate the effectiveness of our code generation strategy on a computational systems biology application. This application consists of computing a Dynamic Bayesian Network (DBN) approximation of the dynamics of signalling pathways described as a system of Ordinary Differential Equations (ODEs). The approximation algorithm involves (i) sampling many (of the order of a few million) times from the set of initial states, (ii) generating trajectories through numerical integration, and (iii) storing the statistical properties of this set of trajectories in Conditional Probability Tables (CPTs) of a DBN via a prespecified discretization of the time and value domains. The trajectories can be computed in parallel. However, the intermediate data needed for computing them, as well as the entries for the CPTs, are too large to be stored locally. Our experiments show that the proposed code generation scheme scales well, achieving significant performance improvements on three realistic signalling pathways models. These results suggest how our scheme could be extended to deal with other applications involving systems of ODEs.

In NAND flash memory, wear leveling is employed to evenly distribute program/erase bit flips so as to prevent overall chip failure caused by excessive writes to certain hot spots of the chip. In this paper, we analyze latest wear leveling algorithms, and propose Observational Wear Leveling (OWL). OWL considers the temporal locality of write activities at runtime when blocks are allocated. It also transfers data between blocks of different ages. From our experiments, with minimal additional space and time overhead, OWL can improve wear evenness by as much as 29.9% and 43.2% compared to two state-of-the-art wear leveling algorithms, respectively.

Flash memory is widely utilized for secondary storage today. However, its further use is hindered by the lifetime issue, which is mainly impacted by wear leveling and bad block management (BBM). Besides initial bad blocks resulting from the manufacturing process, good blocks may eventually wear out due to the limited write endurance of flash cells, even with the best wear leveling strategy. Current BBM tracks both types of bad blocks, and keeps them away from regular use. However, when the amount of bad blocks exceeds a threshold, the entire chip is rendered non-functional. In this paper, we reconsider existing BBM, and propose a novel one that reuses worn-out blocks, utilizing them in wear leveling. Experimental results show that compared to a state-of-the-art wear leveling algorithm, our design can reduce worn-out blocks by 46.5% on average with at most 1.2% performance penalties.

The popularity of GPU programming languages that explicitly express thread-level parallelism leads to the question of whether they can also be used for programming reconfigurable accelerators. This paper describes Guppy, a GPU-like softcore processor based on the in-order LEON3 core. Our long-term vision is to have a unified programming paradigm for accelerators - regardless of whether they are FPGA or GPU based. While others have explored this from a high level hardware synthesis perspective, we chose to adopt the approach of a parametrically reconfigurable softcore. We will discuss the main architecture features of Guppy, compare its performance to the original core. Our design has been synthesized on a Xilinx Virtex 5 FPGA.

There are many legacy Fortran programs still in use today, especially scientific codes which were written decades ago. Many of these codes use explicit DO-loops in programs that tend to clutter the code and make it harder to understand and maintain. Modern features of the Fortran language, such as the array slicing notation and introduction of commonly used intrinsic functions, go a long way in helping programmers write code that is easier to read and maintain. We introduce a refactoring tool that can help to transform code to make use of the array slicing notation and related intrinsic functions.

Solid-state drives (SSDs) made of flash memory are widely utilized in enterprise servers nowadays. Internally, the management of flash memory resources is done by an embedded software known as the flash translation layer (FTL). One important function of the FTL is to map logical addresses issued by the operating system into physical flash addresses. The efficiency of this address mapping in the FTL directly impacts the performance of SSDs. In this paper, we propose a hybrid mapping FTL scheme, called Aggregated Data movement Augmenting Predictive Transfers (ADAPT). ADAPT observes access behaviors online to handle both sequential and random write requests efficiently. It also takes advantage of locality revealed in the history of recent accesses to avoid unnecessary data movements in the required merge process. More importantly, by these mechanisms, ADAPT can adapt to various workloads to achieve good performance. Experimental results show that ADAPT is as much as 35.4%, 44.2% and 23.5% faster than a state-of-the-art hybrid mapping scheme, a prevalent page-based mapping scheme, and a latest workload-adaptive mapping scheme, respectively, with a small increase in space requirement.

Graphics processing units leverage on a large array of parallel processing cores to boost the performance of a specific streaming computation pattern frequently found in graphics applications. Unfortunately, while many other general purpose applications do exhibit the required streaming behavior, they also possess unfavorable data layout and poor computation-to-communication ratios that penalize any straight-forward execution on the GPU. In this paper we describe an efficient and scalable code generation framework that can map general purpose streaming applications onto a multi-GPU system. This framework spans the entire core and memory hierarchy exposed by the multi-GPU system. Several key features in our framework ensure the scalability required by complex streaming applications. First, we propose an efficient stream graph partitioning algorithm that partitions the complex application to achieve the best performance under a given shared memory constraint. Next, the resulting partitions are mapped to multiple GPUs using an efficient architecture-driven strategy. The mapping balances the workload while considering the communication overhead. Finally, a highly effective pipeline execution is employed for the execution of the partitions on the multi-GPU system. The framework has been implemented as a back-end of the StreamIt programming language compiler. Our comprehensive experiments show its scalability and significant performance speedup compared with a previous state-of-the-art solution.

MOTIVATION: Biopathways are often modeled as systems of ordinary differential equations (ODEs). Such systems will usually have many unknown parameters and hence will be difficult to calibrate. Since the data available for calibration will have limited precision, an approximate representation of the ODEs dynamics should suffice. One must, however, be able to efficiently construct such approximations for large models and perform model calibration and subsequent analysis. RESULTS: We present a graphical processing unit (GPU) based scheme by which a system of ODEs is approximated as a dynamic Bayesian network (DBN). We then construct a model checking procedure for DBNs based on a simple probabilistic linear time temporal logic. The GPU implementation considerably extends the reach of our previous PC-cluster-based implementation (Liu et al., 2011b). Further, the key components of our algorithm can serve as the GPU kernel for other Monte Carlo simulations-based analysis of biopathway dynamics. Similarly, our model checking framework is a generic one and can be applied in other systems biology settings. We have tested our methods on three ODE models of bio-pathways: the epidermal growth factor-nerve growth factor pathway, the segmentation clock network and the MLC-phosphorylation pathway models. The GPU implementation shows significant gains in performance and scalability whereas the model checking framework turns out to be convenient and efficient for specifying and verifying interesting pathways properties. AVAILABILITY: The source code is freely available at http://www.comp.nus.edu.sg/~rpsysbio/pada-gpu/

This paper proposes a unified framework for the hardware/software codesign of body sensor network applications that aims to enhance both modularity and reusability. The proposed framework consists of a Unified Modeling Language (UML) 2 profile for TinyOS applications and a corresponding simulator. The UML profile allows for the description of the low-level details of the hardware simulator, thereby providing a higher level of abstraction for application developers to visually design, document and maintain their systems that consist of both hardware and software components. With the aid of a predefined component repository, minimum TinyOS knowledge is needed to construct a body sensor network system. A novel feature of our framework is that we have modeled not only software applications but the simulator platform in UML. A new instance of the simulator can be automatically generated whenever hardware changes are made. Key design issues, such as timing and energy consumption can be tested by simulating the generated software implementation on the automatically customized simulator. The framework ensures a separation of software and hardware development while maintaining a close connection between them. This paper describes the concepts and implementation of the proposed framework, and presents how the framework is used in the development of nesC-TinyOS based body sensor network applications. Two actual case studies are used to show how the proposed framework can quickly and automatically adapt the software implementation to efficiently accommodate hardware changes.

The constant push for feature richness in mobile and embedded devices has significantly increased computational demand. However, stringent energy constraints typically remain in place. Embedding processor cores in FPGAs offers a path to having customized instruction processors that can meet the performance and energy demands. Ideally, the customization process should be automated to reduce the design effort, and indirectly the time to market. However, the automatic generation of custom extensions for floating point computation remains a challenge in FPGA co-design. We propose an approach for accelerating such computation via application-specific SIMD extensions. We describe an automated co-design toolchain that generates code and application-specific platform extensions that implement SIMD instructions with a parameterizable number of vector elements. The parallelism exposed by encapsulating computation in vector instructions is matched to an adjustable pool of execution units. Experiments on actual hardware show significant performance improvements. Our framework provides an important extension to the capabilities of embedded processor FPGAs which traditionally dealt with bit, integer, and low intensity floating point code, to now being able to handle vectorizable floating point computation.

Graphic Processing Units (GPUs) are made up of many streaming multiprocessors, each consisting of processing cores that interleave the execution of a large number of threads. Groups of threads - called warps and wave fronts, respectively, in nVidia and AMD literature - are selected by the hardware scheduler and executed in lockstep on the available cores. If threads in such a group access the slow off-chip global memory, the entire group has to be stalled, and another group is scheduled instead. The utilization of a given multiprocessor will remain high if there is a sufficient number of alternative thread groups to select from. Many parallel general purpose applications have been efficiently mapped to GPUs. Unfortunately, many stream processing applications exhibit unfavorable data movement patterns and low computation-to-communication ratio that may lead to poor performance. In this paper, we describe an automated compilation flow that maps most stream processing applications onto GPUs by taking into consideration two important architectural features of nVidia GPUs, namely interleaved execution as well as the small amount of shared memory available in each streaming multiprocessors. In particular, we show that using a small number of compute threads such that the memory footprint is reduced, we can achieve high utilization of the GPU cores. Our scheme goes against the conventional wisdom of GPU programming which is to use a large number of homogeneous threads. Instead, it uses a mix of compute and memory access threads, together with a carefully crafted schedule that exploits parallelism in the streaming application, while maximizing the effectiveness of the unique memory hierarchy. We have implemented our scheme in the compiler of the Stream It programming language, and our results show a significant speedup compared to the state-of-the-art solutions.

Spin-transfer torque random access memory (STT-RAM) has received increasing attention because of its attractive features: good scalability, zero standby power, non-volatility and radiation hardness. The use of STT-RAM technology in the last level on-chip caches has been proposed as it minimizes cache leakage power with technology scaling down. Furthermore, the cell area of STT-RAM is only 1/9 ~ 1/3 that of SRAM. This allows for a much larger cache with the same die footprint, improving overall system performance through reducing cache misses. However, deploying STT-RAM technology in L1 caches is challenging because of the long and power-consuming write operations. In this paper, we propose both L1 and lower level cache designs that use STT-RAM. In particular, our designs use STT-RAM cells with various data retention time and write performances, made possible by different magnetic tunneling junction (MTJ) designs. For the fast STT-RAM bits with reduced data retention time, a counter controlled dynamic refresh scheme is proposed to maintain the data validity. Our dynamic scheme saves more than 80% refresh energy compared to the simple refresh scheme proposed in previous works. A L1 cache built with ultra low retention STT-RAM coupled with our proposed dynamic refresh scheme can achieve 9.2% in performance improvement, and saves up to 30% of the total energy when compared to one that uses traditional SRAM. For lower level caches with relative large cache capacity, we propose a data migration scheme that moves data between portions of the cache with different retention characteristics so as to maximize the performance and power benefits. Our experiments show that on the average, our proposed multi retention level STT-RAM cache reduces 30 ~ 70% of the total energy compared to previous works, while improving IPC performance for both 2-level and 3-level cache hierarchy.

In today's multi-core systems, cache contention due to true and false sharing can cause unexpected and significant performance degradation. A detailed understanding of a given multi-threaded application's behavior is required to precisely identify such performance bottlenecks. Traditionally, however, such diagnostic information can only be obtained after lengthy simulation of the memory hierarchy.

One of the major impediments to deploying partially run-time reconfigurable FPGAs as hardware accelerators is the time overhead involved in loading the hardware modules. While configuration prefetching is an effective method that can be employed to reduce this overhead, mispredicted prefetches may worsen the situation by increasing the number of reconfigurations needed. In this paper, we present a static algorithm for configuration prefetching in partially reconfigurable FPGAs that minimizes the reconfiguration overhead. By making use of profiling, the interprocedural control flow graph, and the placement information of hardware modules, our algorithm predicts hardware execution and tries to prefetch hardware modules as early as possible while minimizing the risk of mis-predictions. Our experiments show that our algorithm performs significantly better than current state-of-the-art prefetching algorthms for control-bound applications.

Profiling and online analysis are important tasks in program understanding and feedback-directed optimization. However, fine-grained profiling and online analysis tend to seriously slow down the application. To cope with the slowdown, one may have to terminate the process early or resort to sampling. The former tends to distort the result because of warm-up effects. The latter runs the risk of missing important effects because sampling was turned off during the time that these effects appeared. A promising approach is to make use of the parallel processing capabilities of the now ubiquitous multicore processors to speed up the profiling and analysis process. In this article, we present Pipelined Profiling and Analysis (PiPA), which is a novel technique for parallelizing dynamic program profiling and analysis by taking advantage of multicore systems. In essence, the application under examination is profiled using a dynamic instrumentation tool. Optimized instrumentation code outputs the profile information in a succinct format, that we call the REP format, to buffers. This lightweight trace compression minimizes the processing overhead impinged on the application whenever a buffer is full. Another thread recovers the required information from the REP buffer. The recovered full profile is then divided up and passed to multiple threads for further analysis. To achieve the best performance, the entire system has to be well-balanced. We have implemented prototypes of PiPA using two dynamic instrumentation systems, namely DynamoRIO and Pin, thereby demonstrating its portability. Our experiments show that PiPA is able to speed up the overall profiling and analysis tasks significantly. Compared to the more than 100× slowdown of Cachegrind and the 32× slowdown of Pin dcache, we achieved a mere 10.2× slowdown on an 8-core system. In this paper, we will also describe the insights we gained in obtaining the balance needed for PiPA to perform optimally.

With increasing availability of predefined IP (Intellectual Properties) blocks and inexpensive microprocessors, embedded system designers are faced with more design choices than ever. On the other hand, there is a constant pressure on reducing the time to market. However, as the IP blocks are provided by different vendors, they differ in their interfaces. In order to improve design reuse, methods for combining heterogeneous IP blocks with incompatible protocols and I/Os are needed. In this paper, we propose an interface synthesis method that uses the UML notation to model the interfaces of predefined components and glue logic within the standard OCP-compliant environment. We built a code generator to produce the interface adapters from the UML models. We experimented with our approach using simple-bus and a MPEG-2 decoder as case studies.

Energy consumption is of significant concern in battery operated embedded systems. In the processors of such systems, the instruction cache consumes a significant fraction of the total energy. One of the most popular methods to reduce the energy consumption is to shut down idle cache banks. However, we observe that operating idle cache banks at a reduced voltage/frequency level along with the active banks in a pipelined manner can potentially achieve even better energy savings. In this paper, we propose a novel DVS-based pipelined reconfigurable instruction memory hierarchy called PRIM. A canonical example of our proposed PRIM consists of four cache banks. Two of these cache banks can be configured at runtime to operate at lower voltage and frequency levels than that of the normal cache. Instruction fetch throughput is maintained by pipelining the accesses to the low voltage banks. We developed a profile-driven compilation framework that analyzes applications and inserts the appropriate cache reconfiguration points. Our experimental results show that PRIM can significant reduce the energy consumption for popular embedded benchmarks with minimal performance overhead. We obtained 56.6% and 45.1% energy savings for aggressive and conservative VDD settings, respectively, at the expense of a 1.66% performance overhead.

Stream processing represents an important class of applications that spans telecommunications, multimedia and the Internet. The implementation of streaming programs in FPGAs has attracted significant attention because of their inherent parallelism and high performance requirements. Languages, tools, and even custom hardware for streaming have been proposed, some of which are commercially available.

Modern use of FPGAs as hardware accelerators involves the partial reconfiguration of hardware resources as the application executes. In this paper, we present a polynomial time algorithm for scheduling reconfiguration tasks given a trace of actors (invocations of hardware kernels) that is both provably optimal and placement-aware. In addition, we will propose a dependence analysis to determine whether for each actor instance, a reconfiguration task is needed prior to its execution in hardware. A case study using the H.264 encoder is presented to compare our algorithm against the state-of-the-art heuristics.

There has been much work on the next generation of memory technologies such as MRAM, RRAM and PRAM. Most of these are non-volatile in nature, and compared to SRAM, they are often denser, just as fast, and have much lower energy consumption. Using 3-D stacking technology, it has been proposed that they can be used instead of SRAM in large level 2 caches prevalent in today's microprocessors. However, one of the key challenges in the use of these technologies, such as MRAM, is their higher fault probabilities arising from the larger process variation, defects in its fabrication, and the fact that the cache is much larger. This seriously affect yield. In this paper, we propose a fault resilient set associative cache architecture which we called the salvage cache. In the salvage cache, a faulty cache block is sacrificed and used to repair faults found in other blocks. We will describe in detail the architecture of the salvage cache as well as provide results of yield simulations that show that a much higher yield can be achieved viz-a-viz other fault tolerant techniques. We will also show the performance savings that arise from the use of a large next-generation L2 cache.

We present ClearView, a system for automatically patching errors in deployed software. ClearView works on stripped Windows x86 binaries without any need for source code, debugging information, or other external information, and without human intervention.

One important trend in today's microprocessor architectures is the increase in size of the processor caches. These caches also tend to be set associative. As technology scales, process variations are expected to increase the fault rates of the SRAM cells that compose such caches. As an important component of the processor, the parametric yield of SRAM cells is crucial to the overall performance and yield of the microchip. In this article, we propose a microarchitectural solution, called the buddy cache that permits large, set-associative caches to tolerate faults in SRAM cells due to process variations. In essence, instead of disabling a faulty cache block in a set (as is the current practice), it is paired with another faulty cache block in the same set—the buddy. Although both cache blocks are faulty, if the faults of the two blocks do not overlap, then instead of losing two blocks, buddying will yield a functional block from the nonfaulty portions of the two blocks. We found that with buddying, caches can better mitigate the negative impacts of process variations on performance and yield, gracefully downgrading performance as opposed to catastrophic failure. We will describe the details of the buddy cache and give insights as to why it is both more performance and yield resilient to faults.

Dynamic instrumentation systems are gaining popularity as means of constructing customized program profiling and analysis tools. However, dynamic instrumentation based analysis tools still suffer from performance problems. The overhead of such systems can be broken down into two components - the overhead of dynamic instrumentation and the time consumed in the user-defined analysis tools. While important progress has been made in reducing the performance penalty of the dynamic instrumentation itself, less attention has been paid to the user-defined component. In this paper, we present PiPA - Pipelined Profiling and Analysis, which is a novel technique for parallelizing dynamic program profiling and analysis by taking advantage of multi-core systems. We implemented a prototype of PiPA using the dynamic instrumentation system DynamoRIO. Our experiments show that PiPA is able to speed up the overall profiling and analysis tasks significantly. Compared to the more than 100x slowdown of Cachegrind and the 32x slowdown of Pin dcache, we achieved a mere 10.5x slowdown on an 8-core system.

Considering both spatial and temporal partitioning, though potentially profitable, increases the complexity of the design space of applications for run-time reconfigurable architectures. In particular, the number of ways to partition is exponential and dynamic reconfiguration cost is difficult to estimate. These difficulties are particularly challenging for the implementation of neighborhood searches over the design space, such as the sheer amount of design space to be searched and time taken to evaluate each design point accurately. In order to address these challenges, this paper presents a framework that enables fast navigation of the design space using any neighborhood search schemes. The key is a neighborhood relation which spans the entire spatial and temporal partitioning design space. Computed over a SEQUITUR compressed loop trace structure, this relation enables the fast estimation of neighboring design points. We implemented two neighborhood searches, Hill-Climb and Tabu search, to evaluate our technique. On four non-trivial benchmarks, these searches are accelerated by up to two orders of magnitude when using our proposed technique while finding optimal results most of the time.

Abstract Instruction scheduling and register allocation are two of the most important optimization phases in modern compilers as they have a significant impact on the quality of the generated code. Unfortunately, the objectives of these two optimizations are in conflict with one another. The instruction scheduler attempts to exploit instruction‐level parallelism and requires many operands to be available in registers. On the other hand, the register allocator wants register pressure to be kept low so that the amount of spill code can be minimized. Currently these two phases are done separately, typically in three passes: prepass scheduling, register allocation and postpass scheduling. But this separation can lead to poor results. Previous works attempted to solve the phase‐ordering problem by combining the instruction scheduler with graph‐coloring‐based register allocators. The latter tend to be computationally expensive. Linear‐scan register allocators, on the other hand, are simple, fast and efficient. In this paper, we describe our effort to integrate instruction scheduling with a linear‐scan allocator. Furthermore, our integrated optimizer is able to take advantage of execution frequencies obtained through profiling. Our integrated register allocator and instruction scheduler achieved good code quality with significantly reduced compilation times. On the SPEC2000 benchmarks running on a 900 MHz ItaniumII, compared with OpenIMPACT, we halved the time spent in instruction scheduling and register allocation with negligible impact on execution times. Copyright © 2007 John Wiley & Sons, Ltd.

Modern memory systems play a critical role in the performance of applications, but a detailed understanding of the application behavior in the memory system is not trivial to attain. It requires time consuming simulations and detailed modeling of the memory hierarchy, often using long address traces. It is increasingly possible to access hardware performance counters to count relevant events in the memory system, but the measurements are coarse-grained and better suited for performance summaries than providing instruction level feedback. The availability of a low cost, online, and accurate methodology for deriving finegrained memory behavior profiles can prove extremely useful for runtime analysis and optimization of programs. This paper presents a new methodology for Ubiquitous Memory Introspection (UMI). It is an online and lightweight methodology that uses fast mini-simulations to analyze short memory access traces recorded from frequently executed code regions. The simulations provide profiling results at varying granularities, down to that of a single instruction or address. UMI naturally complements runtime optimizations and enables new opportunities for online memory specific optimizations. We present a prototype runtime system implementing UMI. The prototype has an average runtime overhead of 14%. This overhead is only 1% more than a state of the art binary instrumentation tool. We used 32 benchmarks, including the full suite of SPEC CPU2000 benchmarks, for evaluation. We show that the mini-simulations accurately reflect the cache performance of two existing memory systems, an Intel Pentium 4 and an AMD Athlon MP (K7). We also demonstrate that UMI predicts delinquent load instructions with an 88% rate of accuracy for applications with a relatively high number of cache misses, and 61% overall. The online profiling results are used at runtime to implement a simple software prefetching strategy that achieves an overall speedup of 64% in the best case.

The cache hierarchy of state-of-the-art - especially multicore - microprocessors consumes a significant amount of area and energy. A significant amount of research has been devoted especially to reducing the latter. One of the most important microarchitectural techniques proposed for the energy management is dynamic voltage scaling (DVS). In DVS solutions, each cache operates at a number of different voltages. Most of the research in DVS techniques have been around how the voltages can be adjusted and tuned. In this paper, we depart from the use of DVS for energy conservation by examining static voltage assignments for caches. We propose the use of voltage scaled cache hierarchies (VOSCH) as a means to conserve both static and dynamic energy. In VOSCH, the caches are powered at progressively lower supply voltages as the cache level increases. Compared to DVS solutions, VOSCH is simple, potentially more robust and can conserve more energy. We also experimented with more aggressive designs that included the addition of small cache structures to VOSCH. Even greater energy savings were achieved without having to sacrifice performance.

Time-triggered architectures (TTAs) are strong candidate platforms for safety-critical real-time applications. A typical time-triggered architecture is constituted by one or more clusters. Each cluster consists of nodes communicating with one another via a time-triggered communication protocol. Designing applications to run on such a platform is a challenging task. We address this problem by constructing a UML-based design framework which exposes the essential features of the time-triggered platforms at the UML-level and allows applications to be developed at a more abstract level before full implementation. To support preliminary functional validation, we have constructed a translator by which SystemC code can be automatically generated from UML designs. Our framework enables fast prototyping of time-triggered applications and early design validation. It also supports key design principles of TTAs, such as temporal firewalls and composability.

10.1145/1152154.1152180

Various high level hardware description languages have been invented for the purpose of improving the productivity in the generation of customized hardware. Most of these languages are variants, usually parallel versions, of popular software programming languages. In this paper, we describe our effort to generate hardware from OpenMP, a software parallel programming paradigm that is widely used and tested. We are able to generate FPGA hardware from OpenMP C programs via synthesizable VHDL and Handel-C. We believe that the addition of this medium-grain parallel programming paradigm will bring additional value to the repertoire of hardware description languages

Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

On current superscalar processors, performance and power issues cannot be decoupled for designers. Extensive simulations are usually required to meet both power and performance constraints. This paper describes an integrated performance and power analytical model. The model's performance and power results are in good agreement with detailed simulations, previous models and physically measured results. For designers, the model enables quick and flexible explorations into a subset of even entire huge parameter space of more than 15 workload and architectural parameters plus leakage power, feature sizes, clock and voltage.

The performance of the instruction memory hierarchy is of crucial importance in embedded systems. In this paper, we propose a reconfigurable instruction memory hierarchy for embedded systems whose architectural parameters can be customized for specific applications. The proposed instruction memory hierarchy consists of an instruction cache and a scratchpad memory (SPM). We propose an algorithm to manage this instruction memory hierarchy and optimize its performance. Given a fixed amount of reconfigurable on-chip storage resources and an application, our algorithm determines the sizes of the SPM and the instruction cache to best suit the application. It analyzes the application, partitions the available storage resources into SPM and cache, and assigns instructions to them. Our algorithm aims to reduce the instruction fetch miss rate, improve the system performance, and reduce the energy consumption. We have implemented this reconfigurable instruction memory hierarchy on the Altera Nios II FPGA platform. Our experimental results using five benchmarks from the MediaBench and the MiBench suites show that our proposed architecture provides significant performance improvements and energy reduction.

Wireless sensor networks have emerged as an exciting technology for a wide range of important applications that acquire and process information from the physical world. Grid computing has evolved as a standards-based approach for coordinated resource sharing. Sensor grids combine these two promising technologies by extending the grid computing paradigm to the sharing of sensor resources in wireless sensor networks. There are several issues and challenges in the design of sensor grids. In this paper, we propose a sensor grid architecture, called the scalable proxy-based architecture for sensor grid (SPRING), to address these design issues. We also developed a sensor grid testbed to study the design issues of sensor grids and to improve our sensor grid architecture design

While enabling fast implementation and reconfiguration of stream applications, programmable stream processors expose issues of incompatibility and lack of adoption in existing stream modeling languages. To address them we describe a design approach in which specifications are captured in UML 2.0, and automatically translated into SystemC models consisting of simulators and synthesizable code under proper style constraints. As an application case, we explain real time stream processor specifications using new UML 2.0 notations. Then we expound how our translator generates SystemC models and includes additional hardware details. Verifications are made during UML execution as well as assertions in SystemC. The case study demonstrates the feasibility of fast specifications, modifications and generation of real time stream processor designs.

This paper introduces a compiler orchestrated prefetching system as a unified framework geared toward ameliorating the gap between processing speeds and memory access latencies. We focus the scope of the optimization on specific subsets of the program dependence graph that succinctly characterize the memory access pattern of both regular array-based applications and irregular pointer-intensive programs. We illustrate how program embedded precomputation via speculative execution can accurately predict and effectively prefetch future memory references with negligible overhead. The proposed techniques reduce the total running time of seven SPEC benchmarks and two OLDEN benchmarks by 27% on an Itanium 2 processor. The improvements are in addition to several state-of-the-art optimizations including software pipelining and data prefetching. In addition, we use cycle-accurate simulations to identify important and lightweight architectural innovations that further mitigate the memory system bottleneck. In particular, we focus on the notoriously challenging class of pointer-chasing applications, and demonstrate how they may benefit from a novel scheme of it sentineled prefetching. Our results for twelve SPEC benchmarks demonstrate that 45% of the processor stalls that are caused by the memory system are avoidable. The techniques in this paper can effectively mask long memory latencies with little instruction overhead, and can readily contribute to the performance of processors today.

The effective use of processor caches is crucial to the performance of applications. It has been shown that cache misses are not evenly distributed throughout a program. In applications running on RISC-style processors, a small number of delinquent load instructions are responsible for most of the cache misses. Identification of delinquent loads is the key to the success of many cache optimization and prefetching techniques. We propose a method for identifying delinquent loads that can be implemented at compile time. Our experiments over eighteen benchmarks from the SPEC suite shows that our proposed scheme is stable across benchmarks, inputs, and cache structures, identifying an average of 10% of the total number of loads in the benchmarks we tested that account for over 90% of all data cache misses. As far as we know, this is the first time a technique for static delinquent load identification with such a level of precision and coverage has been reported. While comparable techniques can also identify load instructions that cover 90% of all data cache misses, they do so by selecting over 50% of all load instructions in the code, resulting in a high number of false positives. If basic block profiling is used in conjunction with our heuristic, then our results show that it is possible to pin down just 1.3% of the load instructions that account for 82% of all data cache misses.

Reconfigurable system-on-a-chip (RSoC) processors promise a low cost and rapid means of prototyping complex systems of integrated software and hardware, especially for embedded applications. Due to need to manage a wide diversity of resources on-chip, an embedded operating system is needed. We report on our experience in porting an industrial-strength embedded operating system, namely Microsoft Windows CE .NET/spl reg/, on a state-of-the-art RSoC processor platform, namely the Altera Excalibur/spl reg/. We report performance evaluation using a set of kernel micro-benchmarks. We also illustrate how the reconfigurable hardware resource, the programmable logic device (PLD), can be used in an application running under Windows CE.

Field programmable gate arrays (FPGAs) holds the possibility of dynamic reconfiguration. The key advantages of dynamic reconfiguration are the ability to rapidly adapt to dynamic changes and better utilization of the programmable hardware resources for multiple applications. However, with the advent of multi-million gate equivalent FPGAs, configuration time is increasingly becoming a concern. High reconfiguration cost can potentially wipe out any gains from dynamic reconfiguration. One solution to alleviate this problem is to exploit the high levels of redundancy in the configuration bitstream by compression. In this paper, we propose a novel configuration compression technique that exploits redundancies both within a configuration's bitstream as well as between bitstreams of multiple configurations. By maximizing reuse, our results show that the proposed technique performs 26.5-75.8% better than the previously proposed techniques. To the best of our knowledge, ours is the first work that performs inter-configuration compression.

We present a system level description mechanism based on UML-notations from which one can automatically extract SystemC code. Our modelling framework is based on a restricted set of UML diagram types and some standard extensions influenced by the communication infrastructure of SystemC. The system specifications are developed using the UML-compatible tool, Rhapsody (2004). We then translate the internal representation of the design generated by Rhapsody into SystemC code. The extensions we have implemented using the stereotype feature of the Rhapsody tool pull up the communication infrastructure and timing features of SystemC to the UML-level. Consequently, we can describe executable platforms at the UML-level as well as translate UML-based application descriptions to SystemC level.

Distributed Shared Memory (DSM) is a highly desirable programming model for cluster based computing. Even though a number of software DSMs have been developed with their performance evaluated, few of them have a theoretical performance model. In this paper, we propose and analyze the performance model of the software DSM of SilkRoad,, a multithreaded runtime system for cluster computing. SilkRoad is built on the Cilk system with an extended memory consistency model which we call RC/sub dag/ consistency: Extending Cilk's theoretical performance model, we show that with the RC/sub dag/ consistent DSM, the expected execution.time T/sub P/ of a partially strict multithreaded computation on P processors is O((T/sub 1/(Z, L) + N)/P + /spl mu/HT/sub /spl infin//), where T/sub 1/(Z, L) is the total work of computation, T/sub /spl infin// is the critical path, N is the number of lock acquisitions, /spl mu/ is the service time of a cache miss, and H is the height of memory: Finally, we present experimental evidence that verify the performance model.

The increasing density and speed of modern field programmable gate arrays offer the reconfigurable systems using them greater capability and flexibility, in particular for more complex computation. However, there remains a very important problem of how to design on a more abstract level to manage the vast hardware resource and shorten the design time. This paper presents an approach to compile a system level description to hardware through a conventional software intermediate representation (IR) of a state-of-the-art optimizing compiler for Explicitly Parallel Instruction Computing (EPIC) processors. The front end compiles C programs into an intermediate representation for an infinite resource EPIC processor. The intermediate representation contains all the information of control flow graph of basic blocks. It is from this intermediate representation that we have devised means to generate synthesizable Register Transfer level (RTL-level) Verilog description that can be mapped into the reconfigurable HW device. We will describe the details of the translation process and the performance on actual FPGA hardware.

A parallel programming paradigm dictates the way in which an application is to be expressed. It also restricts the algorithms that may be used in the application. Unfortunately, runtime systems for parallel computing often impose a particular programming paradigm. For a wider choice of algorithms, it is desirable to support more than one paradigm. In this paper we consider SilkRoad II, a variant of the Cilk runtime system for cluster computing. What is unique about SilkRoad II is its memory model which supports multiple paradigms with the underlying software distributed shared memory. The RC-dag memory consistency model of SilkRoad II is introduced. Our experimental results show that the stronger RC-dag can achieve performance comparable to LC of Cilk while supporting a bigger set of paradigms with rather good performance.

With dramatic improvements in cost-performance, the use of clusters of personal computers is becoming widespread. For ease of use and management, a single system image (SSI) is highly desirable. There are several approaches that one can take to achieve SSI. In this paper, we discuss the achievement of SSI via the use of the user login shell. To this end, we describe shoc (shell over a cluster)-an implementation of the standard Linux-GNU bash shell that permits the user to utilize a cluster as a single resource. In addition, shoc provides for transparent pre-emptive load balancing without requiring the user to rewrite, recompile or even relink of existing applications. Running at user-level, shoc does not require any kernel modification and currently runs on any Linux cluster fulfilling a minimal set of requirements. We also present results on the performance of shoc and show that the load balancing feature gives rise to better overall cluster utilization as well as improvement in response time for individual processes.

Reconfigurable computing offers the embedded systems designers the flexibility of application specific optimizations on a generic platform. In this paper, we are concerned with a fine-grain, tightly coupled, dynamically reconfigurable architecture we call Adaptive EPIC. A generic EPIC architecture is augmented with a dynamically reconfigurable structure. In this paper, we describe an experimental setup to evaluate the performance of such a processor. Our results show that such architecture can offer significant performance improvements for low frequency, and hence low power, core processors.

This paper introduces PD-XML, a meta-language for describing instruction processors in general and with an emphasis on embedded processors, with the specific aim of enabling their rapid prototyping, evaluation and eventual design and implementation. PD-XML is not specific to any one architecture, compiler or simulation environment and hence provides greater flexibility than related machine description methodologies. We demonstrate how PD-XML can be interfaced to existing description methodologies and tool-flows. In particular we show how PD-XML specifications can be translated into appropriate machine descriptions for the parametric HPL-PD VLIW processor, and for the Flexible Instruction Processor (FIP) approach targeting reconfigurable implementations.

An important technique for alleviating the memory bottleneck is data prefetching. Data prefetching solutions ranging from pure software approach by inserting prefetch instructions through program analysis to purely hardware mechanisms have been proposed. The degrees of success of those techniques are dependent on the nature of the applications. The need for innovative approach is rapidly growing with the introduction of applications such as object-oriented applications that show dynamically changing memory access behavior In this paper, we propose a novel framework for the use of data prefetchers that are trained off-line using smart learning algorithms to produce prediction models which captures hidden memory access patterns. Once built, those prediction models are loaded into a data prefetching unit in the CPU at the appropriate point during the runtime to drive the prefetching. On average by using table size of about 8KB size, we were able to achieve prediction accuracy of about 68% through our own proposed learning method and performance was boosted about 37% on average on the benchmarks we tested. Furthermore, we believe our proposed framework is amenable to other predictors and can be done as a phase of the profiling-optimizing-compiler.

It is widely acknowledged that even as VLSI technology advances, there is a looming crisis that is an important obstacle to the widespread deployment of mobile embedded devices, namely that of power. This problem can be tackled at many levels like devices, logic, operating systems, micro-architecture and compiler. While there have been various proposals for specific compiler optimizations for power, there has not been any attempt to systematically map out the space for possible improvements. In this paper, we quantitatively characterize the limits of what a compiler can do in optimizing for power using precise modeling of a state-of-the-art embedded processor in conjunction with a robust compiler. We provide insights to how compiler optimizations interact with the internal workings of a processor from the perspective of power consumption. The goal is to point out the promising and not so promising directions of work in this area, to guide the future compiler designer.

Constructing multithreaded parallel systems with software distributed shared memory (DSM) is an attractive trend in cluster computing. Distributed Cilk (Cilk 5.1) is a multithreaded runtime system for SMP clusters with support for the divide-and-conquer programming paradigm. However, it lacks support for user-level shared memory. We describe SilkRoad, an extension of Distributed Cilk which implements the lazy release consistency (LRC) memory model. In the SilkRoad runtime system, system control information is kept consistent by means of a backing store, just as it is in the original Distributed Cilk, while the user's cluster wide shared data is kept consistent by LRC. LRC enables SilkRoad programmers to define and use shared variables between the threads running on different nodes in a cluster This greatly enlarges the scope of supported programming paradigms in Cilk. Besides testing its performance, we also compared SilkRoad with TreadMarks, an LRC software DSM system for clusters with no support of multithreading. The results show that with the hybrid memory model of dag-consistency and LRC, multithreaded SilkRoad programs written in a divide-and-conquer fashion with good data locality can achieve comparable performance with the corresponding multiple-process TreadMarks programs.

The authors describe a multithreaded software distributed shared memory, (DSM) system named Orion. It has been developed to provide a POSIX-thread (pthread) like interface. We believe this will avoid creating another unique set of application programming interfaces and ease the porting of pthread programs to a distributed environment. Orion implements a home based consistency model. We also present 2 adaptive schemes for home based DSM systems: home migration and dynamic adaptation between write-invalidation and require-update protocols. The two fully automatic schemes aim to involve minimal user intervention and yet deliver good performances with some speedups ranging from 2% to 79% observed in some 8 benchmarks tested.

The ability to predict the directions of branches, especially conditional branches, is an important problem in modern computer architecture and advanced compilers. Many static and dynamic techniques have been proposed. Today, all state-of-the-art microprocessors have some form of hardware support for dynamic branch prediction. Static techniques, on the other hand, have not been widely studied because of the belief that they give poorer results. However, good static branch predictions are invaluable information for (static) compiler optimization or performance estimation. In this paper, we propose performing static branch prediction at the source code level. The assumption is that the source code contains information unavailable at the assembly or machine code level that may be used for branch prediction. Empirical studies on 14 integer Spec benchmarks indicate that the simple heuristics proposed can be effective in practice.

In this paper we introduce a new method for the fast evaluation of the elementary functions in single precision based on the evaluation of truncated Taylor series using a difference method. We assume the availability of large and fast (at least for read purposes) memory. We call this method the ATA (Add-Table lookup-Add) method. As the name implies, the hardware required for the method are adders (both two/ and multi/operand adders) and fast tables. For IEEE single precision numbers our initial estimates indicate that we can calculate the basic elementary functions, namely reciprocal, square root, logarithm, exponential, trigonometric and inverse trigonometric functions, within the latency of two to four floating point multiplies.>

As the name suggests, elementary functions play a vital role in scientific computations. Yet due to their inherent nature, they are a considerable computing task by themselves. Not surprisingly, since the dawn of computing, the goal of speeding up elementary function computation has been pursued. This paper describes new hardware based algorithms for the computation of the common elementary functions, namely division, logarithm, reciprocal square root, arc tangent, sine and cosine. These algorithms exploit microscopic parallelism using specialized hardware with heavy use of truncation based on detailed accuracy analysis. The contribution of this work lies in the fact that these algorithms are very fast and yet are accurate. If we let the time to perform an IEEE Standard 754 double precision floating point multiplication be /spl tau//sub /spl times//, our algorithms to achieve roughly 3.68/spl tau//sub /spl times//,4.56/spl tau//sub /spl times//, 5.25/spl tau//sub /spl times//, 3.69/spl tau//sub /spl times//, 7.06/spl tau//sub /spl times//, and 6.5/spl tau//sub /spl times//, for division, logarithm, square root, exponential, are tangent and complex exponential (sine and cosine) respectively. The trade-off is the need for tables and some specialized hardware. The total amount of tables required, however, is less than 128 Kbytes. We discuss the hardware, algorithmic and accuracy aspects of these algorithms.>