Sparse-Dense Matrix Multiplication (SpMM) on GPUs has gained significant attention because of its importance in modern applications and the increasing computing power of GPUs in the last decade. Previous SpMM studies have focused on the importance of storage format and load balance for the overall performance of SpMM on GPUs. However, very little attention has been paid to the efficacy of coalesced memory access in improving the efficiency of data loading, which incurs a notable overhead that amounts to an average of more than 32% of the overall performance, according to our experimental observation. Existing state-of-the-art (SOTA) solutions fail to adequately support coalesced memory access of both sparse and dense matrices between the global memory and threads on GPUs. In this paper, we propose an efficient algorithm called Swift.11Swift is available at https://github.com/MinttHu/Swift.git that speeds up the loading of both sparse and dense matrices of SpMM on modern GPUs. Leveraging coalesced memory access, Swift achieves high loading efficiency by sorting both the columns of the sparse matrix and elements of the dense matrix based on the number of non-zero elements and balancing the load by handling the regular and irregular parts differently and judiciously. Swift takes the Compressed Sparse Column format as an implementation case study to prove the concept and gain insights. We conduct a comprehensive comparison of Swift with four SOTA solutions: ASpT, cuSPARSE, RoDe, and Sputnik, using the full SuiteSparse Matrix Collection as the workload. The experimental results on RTX 4080s, RTX 3090Ti, A100, and V100 demonstrate that our method outperforms the baselines significantly.

Abstract High-performance computing (HPC) systems must remain stable and reliable to consistently deliver robust computational power and ensure the proper execution of user jobs. Anomaly detection is a key means to ensure the stability and reliability of these systems. With the expansion of HPC systems and changes in their architecture, accurately identifying anomalies in dynamic environments has become increasingly challenging. Traditional detection methods rely on experience and rules, which could be inefficient and inaccurate. To address these issues, researchers have proposed machine learning-based methods to automatically process large amounts of complex data, improving the efficiency of anomaly identification and diagnosis. In this survey, we conduct a comprehensive and in-depth investigation of machine learning-based anomaly detection methods in HPC systems. Firstly, we summarize and introduce the background and challenges of anomaly detection in HPC systems. Secondly, we compare a series of machine learning-based anomaly detection works in detail and summarize their frameworks. We conclude their advantages and disadvantages and application scenarios. Finally, we discuss several promising development trends of machine learning-based HPC system anomaly detection.

Autopilot vehicles integrate additional views to capture comprehensive feature information, enhancing target detection accuracy. However, this integration imposes a higher computational burden on CNN accelerators in autopilot systems, potentially increasing the response latency of autopilot systems. It is a challenge for safety-critical autopilot systems. Traditionally, researchers have addressed this challenge by employing complex designs and processes to enhance the arithmetic capabilities of chips. In contrast, the paper proposes a simple technology that is an extension architecture of CNN accelerators for multiview acceleration (CAMVA). The extension architecture utilizes the characteristic of multi-view approximation to enhance the sparsity of input features and dynamically reuse the approximated feature extraction results, accelerating CNN accelerators. This paper uses multi-view autonomous driving datasets (KITTI and nuScenes) to create two tasks, and evaluates the impact of CAMVA on 2D and 3D object detection networks by simulating their data flows. Results of 2D experiments show that for 2D object detection, the accuracy of the KITTI task decreases by 2.29%~4.26%, while that of the nuScenes task decreases by 0.37%~1.11%. For 3D object detection, the accuracy of the KITTI task decreases by 1.97%~-0.22%. Then, the paper utilizes the pruning operation of CAMVA to create two subtasks, which are subsets of the KITTI with sparsity of 9.6% and 19.8%, respectively. It evaluates the performance, energy consumption, and RTL of CAMVA at the hardware architecture level based on the two subtasks. The results show that CAMVA enhances the performance of CNN accelerator by 1.04~1.08× and reduces energy consumption by 4.23%~8.01% in the sparsity 9.6% subtask; additionally, it improves performance by 1.13~1.34× and decreases energy consumption by 14.13%~25.97% in the sparsity 19.8% subtask. CAMVA increases CNN accelerator’;s area by a mere 0.75%.

The Conjugate Gradient method is a prevalent iterative approach for solving sparse linear systems$Ax = b$, whereAis a symmetric positive definite matrix. In this scenario, the Factorized Sparse Approximate Inverse (FSAI) preconditioner is commonly used. The FSAI approximates$A^{-1}$by the matrix productGTG, whereGis a lower triangular matrix. The numerical properties of FSAI mainly depend on the sparsity pattern ofG. This work presents an approach to generate FSAI sparsity patterns tailored to SIMD architectures, which play a pivotal role in current high-performance computing systems. First, we implement FSAI-S, an FSAI preconditioner based on the SELL-C-σ format for SIMD architectures. To further improve iterative performance, we propose a padding-aware preconditioner, FSAI-P, which leverages the zero padding inherent in the SELL-C-σ to extend the sparsity pattern with minimal computational and storage overhead. We evaluate our approach on three SIMD architectures: a Skylake processor implementing the AVX-512 ISA, a RISC-V processor supporting the RISC-V “V” Vector ISA, and an Nvidia A100 GPU. Experimental results show that FSAI-P provides performance gains across all evaluated platforms. Specifically, average speedups are 12.51% (vs. FSAI) and 11.66% (vs. FSAI-cache) on Skylake, 57.79% (vs. FSAI) on RISC-V, and 18.33% (vs. FSAI) on the A100 GPU.

Spin Transfer Torque-Magnetic Random Access Memory (STT-MRAM), as a new non-volatile memory technology with lower leakage power and higher density, is widely considered to be a new generation of memory technology that may replace SRAM in the cache. STT-MRAM is divided into Single-Level Cell (SLC) STT-MRAM and Multi-Level Cell (MLC) STT-MRAM. Compared with SLC STT-MRAM, MLC STT-MRAM has further improved its storage density. However, MLC STT-MRAM has a high energy consumption and write latency due to its unique two-step state transitions (TTs) issue. State-of-the-art approaches mitigate this issue by eliminating TTs with expansion coding methods. Unfortunately, they focus more on eliminating TTs and have limited improvement in reducing energy consumption. To this end, we propose a new scheme, AEIS, which further reduces energy consumption while eliminating TTs. Our work begins with exploring the general rules of (M,N)-based expansion coding methods that eliminate TTs. Based on the discovered rules, the minimum energy coding method is found. To further improve energy efficiency, we segment the cache lines according to the data pattern. We only apply the expansion coding to those flipping segments to reduce the expansion coding overhead. The evaluation results show that AEIS can eliminate TTs in MLC STT-MRAM, reduce energy consumption by 28.5%, and increase the lifetime by 24.8%, while the total number of bits used for the cache only increases by 5.7%.

As integrated circuit design continues to scale, three-dimensional integrated circuit (3D-IC) technology has emerged as a promising solution to extend Moore’s Law. Among various physical design stages, placement plays a pivotal role, directly influencing key power, performance, and area (PPA) metrics. In research that does not consider specific 3DIC process technologies, the state-of-the-art ePlace-3D introduces 3D electrostatic field density modeling, enabling nonlinear placement algorithms to truly address 3D placement problems. However, its complex flow results in low runtime efficiency. In this work, we propose LightPlace, a lightweight and effective 3D placement framework. This framework incorporates Virtual Macro Insertion approach and Macro Connection Reconstruction method, which streamline the macro placement phase and allocate space for subsequent standard cell placement. These innovations enhance runtime efficiency and optimize wirelength. Experimental results on the large-scale Modern Mixed-Size (MMS) benchmarks demonstrate that, LightPlace reduces total wirelength by an average of 10% and achieves up to 4× faster runtime compared to the runtime reported for ePlace-3D.

Matrix operations (MOPs) are essential for various computational tasks, particularly in deep learning models, which have grown increasingly complex. As these models expand, their demand for computational resources increases significantly, making deployment on resource-limited hardware platforms, such as field-programmable gate arrays, more challenging, especially in balancing resource allocation and computation latency. Reuse-control techniques have been employed to optimize resource allocation by enabling multiple operations to share the same computational units, such as digital signal processors. Yet, this approach presents a tradeoff between resource utilization and latency. In this study, we tackle this challenge by thoroughly analyzing existing reuse-control mechanisms and introducing a novel integer linear programming (ILP)-based strategy. Our experimental results demonstrate that the proposed approach not only improves resource utilization for large-scale MOPs but also significantly reduces latency compared to existing methods. In the best case, on the ResNet model, our ILP-based method achieves up to$2.21\times$lower latency and$2.14\times$lower energy consumption per inference, demonstrating significantly improved performance and energy efficiency. In addition, our work provides a new optimization perspective for hardware design based on high-level synthesis.

Graph-structured data appears in domains such as molecular analysis, social networks, and program optimization, where graphs often exhibit implicit heterogeneity, as nodes may look homogeneous in type yet differ significantly in semantics or functionality. Graph Neural Networks (GNNs), while powerful on homophilic graphs, tend to degrade in such settings due to polarity confusion, over-smoothing, and inefficiency caused by dense propagation. We propose a polarity-aware framework for graph classification that addresses these challenges through adaptive directional sparse aggregation. The framework introduces a polarity-aware propagation mechanism that adaptively reinforces or inverts neighbor signals, mitigating contamination under heterophily. A polarity-guided sparse aggregation operator further alleviates over-smoothing, improves scalability by constraining redundant connections, and condenses information flow into more effective representations, while maintaining unbiased estimation with controlled variance. We provide theoretical analyses that characterize the computational complexity, stability properties, and expressive behavior of signed directional aggregation, offering theoretical insights into its computational, stability, and expressive properties. Extensive experiments on molecular and social graph benchmarks with implicit heterophily demonstrate consistent improvements in graph classification accuracy and efficiency. Our method achieves a 2.36% improvement when compared with the strongest baseline on each dataset. In addition, it improves accuracy by 4.53% on average on program optimization strategy recognition tasks, reaching 80.12% overall.

Deep neural networks (DNNs) dominate workloads on cloud and edge platforms. Meanwhile, the hardware platform towards the heterogeneous system with various accelerators. By mapping layers to their different preferred accelerators, the computation cost of each layer can be reduced. While mapping these layers on the same accelerator can reduce the inter-accelerator communication cost. These two costs are often competing and difficult to optimize simultaneously. Therefore, the core challenge in achieving efficient execution of DNN workloads on heterogeneous systems is: how to map layers to achieve the best trade-off between computation and communication costs. Existing works group layers into blocks and perform blockwise mapping to reduce inter-layer communication within blocks. However, when grouping layers, they typically rely on modelagnostic rules, which fail to hide critical inter-layer communication within blocks for diverse DNNs. Moreover, after block mapping, the lack of intra-block resource allocation further increases computation cost of block. In this paper, we proposeGHCoM, a novel block-wise mapping framework for exploring the effective cost trade-offs.GHCoMemploys an adaptive grouping strategy to guide layer grouping based on the topology of DNNs and dynamically adjust the grouping according to the trade-off target. Furthermore,GHCoMconsiders the fine-grained allocation of computation (i.e., processing elements) and communication (i.e., on-chip bandwidth) resources within each block to mitigate interlayer resource contention. To jointly optimize layer grouping, block-wise mapping and intra-block resource allocation,GHCoMleverages a two-level genetic algorithm (GA) with tailored encodings and operators that capture the interdependence across the entire design space. Experiments across various workloads and system configurations show thatGHCoMconsistently outperforms state-of-the-art baselines, achieving 1.08× to 4.79× speedup in execution latency and reducing energy consumption by 1.83% to 87.71%.

Federated Learning (FL) has emerged as a key framework to deliver AI services, recognized for its capability to construct global models while ensuring individual data. Nevertheless, FL heavily relies on a central server, which introduces significant challenges for participants to collaborate effectively and substantially limits the scalability of FL. Blockchain-based FL (BFL) offers a promising solution by replacing the central server with a decentralized blockchain system, thereby establishing a secure and trustworthy environment for FL. However, current BFL approaches face challenges in balancing high computational overhead, consistency, and security. In view of this, this paper introduces EBFL, an efficient blockchain framework for FL services. EBFL incorporates both asynchronous and synchronous advantages. A DAG-based (Directed Acyclic Graph) asynchronous computation enhances computational efficiency by mitigating delays caused by slow devices and reducing unnecessary waiting due to frequent synchronized consensus. Simultaneously, a periodic synchronized consensus mechanism is introduced during asynchronous training to ensure consistency, thereby improving security and model accuracy. Additionally, taking into account the unique characteristics of FL, we have designed a series of operations tailored for EBFL to further enhance the performance. Experimental results demonstrate that, compared to traditional synchronous BFL (TBFL) approaches, EBFL achieved a maximum speedup of up to 2.38× while retaining 92% of their accuracy. Subsequently, in-depth analytical experiments show that EBFL excels in both convergence speed and security, thereby confirming its potential to balance computational efficiency, consistency, and security.

The median (MED) is a crucial statistic for measuring the central tendency. However, exact MED computation remains costly, with even state-of-the-art (SOTA) algorithms failing to meet (near) real-time processing demands. While approximate MED algorithm has arisen as a promising candidate, existing approaches ignore the potential opportunity of spatiotemporal similarity within the application and fail to provide applicationspecific trade-offs between execution time and accuracy. Our goal is to design an enhanced approximate MED algorithm STREAM, which is capable of exploiting the spatiotemporal similarity to achieve bucket reuse and establish a tunable-grained bucket mechanism to meet the accuracy of application-specific requirements. Experimental results show that while maintaining nearly identical accuracy, STREAM outperforms the SOTA approximate methods DDSketch (up to $10 \times 4.7 \times$ on average) and KLL (up to $71.2 \times 10.1 \times$ on average).

Sparse Matrix-Vector Multiplication (SpMV) is an essential sparse operation in scientific computing and artificial intelligence. Efficiently adapting SpMV algorithms to diverse matrices and architectures requires a framework capable of accurately recognizing sparse patterns and selecting the optimal implementation. In this work, we introduce Sparsity-aware SpMV (SSpMV), a framework that integrates expert-designed features with multimodal representations to adaptively predict the best-performing algorithm and parameters. For this purpose, we design a multimodal neural network called MM-Adapter, to capture diverse modalities to represent the computational features of SpMV. Experimental results demonstrate that MMAdapter achieves the highest accuracy of $81.05 \%$, outperforming existing SpMV prediction models. Furthermore, SSpMV consistently delivers substantial performance improvements over state-of-the-art sparse libraries across various multi-core platforms.

High-Level Synthesis (HLS) offers various optimization directives that enable designers to flexibly adjust hardware microarchitecture. However, existing HLS performance prediction methods typically rely on control data flow graphs generated (CDFG) from original HLS C/C++, which struggle to capture the complex interactions between directives and the resulting hardware resource reuse issues. To address these issues, this paper proposes a post-implementation performance prediction method tailored for directive-optimized circuits design, which utilizes a Graph Builder to integrate directive optimization and resource reuse information into the graph representation. In addition, the performance prediction model, which integrates a TransformerConv-based graph neural network (GNN) and an aggregation pool module, effectively captures key features related to post-implementation performance. Experimental results show that our method can reduce the prediction error of critical path delay (CP), power, and resource utilization to 3.87% $\sim$ 8.08%, significantly outperforming existing state-of-the-art methods. It also demonstrates excellent generalization on unseen kernels, providing a more effective and accurate performance prediction tool for HLS.

Sparse general matrix-matrix multiplication (SpGEMM) is a core primitive for numerous scientific applications. Traditional hash-based approaches fail to strike a balance between reducing hash collisions and efficiently utilizing fast shared memory, which significantly undermines the performance of executing SpGEMM on GPUs. To address this issue, this paper introduces a novel accumulator design that achieves high shared memory utilization on modern GPUs. For the proposed high shared memory utilization algorithm, i.e., HSMU-SpGEMM1, we further optimize different symbolic stages. Our evaluations with four state-of-the-art hash-based SpGEMM libraries (Nsparse, spECK, OpSparse, and NVIDIA’s cuSPARSE) on three NVIDIA GPUs (Ampere, Ada Lovelace, Turing) demonstrate significant performance benefits from HSMU-SpGEMM.1HSMU-SpGEMM is available at https://github.com/wuminqaq/HSMUSpGEMM

Graph Neural Networks (GNNs) excel in processing graph-structured data, making them attractive and promising for tasks such as recommender systems and traffic forecasting. However, GNNs’ irregular computational patterns limit their ability to achieve low latency and high energy efficiency, particularly in edge computing environments. Current GNN accelerators predominantly focus on value sparsity, underutilizing the potential performance gains from bit-level sparsity. However, applying existing bit-serial accelerators to GNNs presents several challenges. These challenges arise from GNNs’ more complex data flow compared to conventional neural networks, as well as difficulties in data localization and load balancing with irregular graph data.To address these challenges, we propose BEAST-GNN, a bit-serial GNN accelerator that fully exploits bit-level sparsity. BEAST-GNN introduces streamlined sparse-dense bit matrix multiplication for optimized data flow, a column-overlapped graph partitioning method to enhance data locality by reducing memory access inefficiencies, and a sparse bit-counting strategy to ensure balanced workload distribution across processing elements (PEs). Compared to state-of-the-art accelerators, including HyGCN, GCNAX, Laconic, GROW, I-GCN, SGCN, and MEGA, BEAST-GNN achieves speedups of 21.7 ×, 6.4×, 10.5×, 3.7×, 4.0×, 3.3×, and 1.4× respectively, while also reducing DRAM access by 36.3×, 7.9×, 6.6×, 3.9×, 5.38×, 3.37×, and 1.44×. Additionally, BEAST-GNN consumes only 4.8%, 12.4%, 19.6%, 27.7%, 17.0%, 26.5%, and 82.8% of the energy required by these architectures.

Sparsification technology is crucial for deploying convolutional neural networks in resource-constrained environments. However, the efficiency of sparse models is hampered by irregular memory access patterns in sparse matrix multiplication kernels. Hardware-level support for 2:4 granularity in sparse tensor cores presents an opportunity for designing efficient sparse matrix multiplication kernels. Existing approaches often involve adjusting sparse structures or secondary sparsification, introducing additional computational errors. To tackle this challenge, we introduce a flexible 2:4 structured adaptive sparse matrix multiplication (FS-AMM) method, a hardware-friendly sparse matrix multiplication kernel that leverages model context to accelerate convolutional neural networks. First, we propose a model context-aware matrix pre-processing method that employs heuristic algorithms to estimate a loss of accuracy due to weight sparsity at each layer. Second, we design a hardware-friendly sparse storage format that combines 2:4 sparse and dense storage formats, enabling more versatile sparsity ratio selection. Third, we implement efficient matrix multiplication kernels to optimize GPU utilization. Finally, experimental results on A100 GPUs show that our method effectively utilizes the sparse tensor kernel and obtains an average 3.09 times speedup ratio compared to other sparse methods while maintaining a high accuracy.

Zero-Knowledge Proofs (ZKP) and Homomorphic Encryption (HE) are crucial for data privacy in applications like cloud, blockchain, and analytics. However, the real-world adoption often faces performance challenges, particularly in the execution of the Number Theoretic Transform (NTT) required for polynomial multiplication involving sizes beyond \(2^{20}\) and large integer widths (e.g., 256 bits). FPGAs offer a promising platform for acceleration, but efficiently implementing large-size NTTs remains difficult due to the limited on-chip resources. The widely adopted four-step NTT method, used to relieve the need for large on-chip memory, introduces performance bottlenecks. Initially, the traditional dataflow NTT architecture may not fully exploit available compute capability, which hinders achieving peak performance. Furthermore, during the matrix transpose phase, the non-sequential access to external High-Bandwidth Memory (HBM) causes inefficiency. To address these challenges, we introduce HiFA, an FPGA-based automatic accelerator framework designed for high-performance and flexible large-size NTT computations. HiFA utilizes a stacked NTT architecture for high parallelism, maximizing HBM throughput. It supports various decomposed polynomial sizes via a novel reordering module. Additionally, a specialized cyclic shuffle module is integrated to optimize data movement during the matrix transpose step, alleviating random memory access delay. HiFA also provides an automatic Design Space Exploration (DSE) framework that identifies optimal four-step decomposition parameters and generates corresponding hardware configurations. Our experiments show that the FPGA implementation of HiFA achieves an average speedup of 2.97× and up to 7.25× improvement in latency over prior state-of-the-art FPGA solutions. Compared to prior GPU-based methods, HiFA achieves an average energy efficiency gain of 2.24×.

Multimodal transformer excels in various applications, but faces great challenges such as high memory consumption and limited data reuse that hinder real-time performance. To address these issues, we propose a processing-in-memory (PIM)-GPU collaboration oriented compiler to accelerate the multimodal transformers. The PIM-GPU collaboration adapts well to multimodal transformers and significantly accelerates model inference. In addition, we introduce a tailored PIM allocation algorithm for variable-length inputs to further improve computation efficiency. Experimental results show that our scheme can achieve an average 15x end-to-end speedup.

Cache miss analysis has become one of the most important things to improve the execution performance of a program. Generally, the approaches for analyzing cache misses can be categorized into dynamic analysis and static analysis. The former collects sampling statistics during program execution but is limited to specialized hardware support and incurs expensive execution overhead. The latter avoids the limitations but faces two challenges: inaccurate execution path prediction and inefficient analysis resulted by the explosion of the program state graph. To overcome these challenges, we propose CBANA, an LLVM- and process address space-based lightweight, efficient, and flexible cache behavior analysis framework. CBANA significantly improves the prediction accuracy of the execution path with awareness of inputs. To improve analysis efficiency and utilize the program preprocessing, CBANA refactors loop structures to reduce search space and dynamically splices intermediate results to reduce unnecessary or redundant computations. CBANA also supports configurable hardware parameter settings, and decouples the module of cache replacement policy from other modules. Thus, its flexibility is established. We evaluate CBANA by using the popular open benchmark PolyBench, graph workloads, and our synthetic workloads with good and poor data locality. Compared with the popular dynamic cache analysis tools Perf and Valgrind, the cache miss gap is less than 3.79% and 2.74% respectively with over ten thousand data accesses for the synthetic workloads, and the time reduction is up to 92.38% and 97.51% for the multiple-path workloads. Compared with the popular static cache analysis tool Heptane, CBANA achieves a time reduction of 97.71% while ensuring accuracy at the same time.

Through the attention mechanism, Transformer-based large-scale deep neural networks (LSDNNs) have demonstrated remarkable achievements in artificial intelligence applications such as natural language processing and computer vision. The matrix-matrix multiplication operation (MMMO) in Transformer makes data movement dominate the inference overhead over computation. A solution for efficient data movement during Transformer inference is to embed arithmetic logic units (ALUs) into the memory array, hence an accelerator-in-memory architecture (AIMA). Existing work along this direction has not considered the heterogeneity of parallelism and resource requirements among Transformer layers. This increases the inference latency and lowers the resource utilization, which is critical for the embedded systems domain. To this end, we propose HAIMA, a hybrid AIMA and the parallel dataflow for Transformer, which exploit the cooperation between SRAM and DRAM to accelerate different MMMOs. Compared to the state-of-the-art Newton and TransPIM, our proposed hardware-software co-design achieves 1.4x-1.5x speedup, and solves the problem of resource under-utilization when DRAM-based AIMA performs the light-weight MMMOs.

Modern blockchains supporting smart contracts implement a new form of state machine replication with a trusted and decentralized paradigm. However, inefficient smart contract transaction execution severely limits system throughput and hinders the further application of blockchain.

The blockchain establishes trust by maintaining a distributed appending-only ledger, which is widely applied to the nodes lacking trust in the edge environment. However, the full-replication storage mode of blockchain is a big challenge for resource-constrained edge devices. What is worse, system performance is also affected by the large storage overhead. Existing solutions to reduce blockchain storage overhead often require additional security assumptions, lack incentives, or fail to account for resource heterogeneity. To overcome these limitations, we design an auction-based storage resource allocation scheme. Winners are selected to store blocks, taking into account the block preferences of nodes, and the fairness of the system. Nodes are incentivized by implementing fairness and equity in distributed auctions and data transactions through smart contracts. Finally, extensive experiments show 65%–81% savings in storage overhead compared to fully replicated storage.

The service resource allocation strategy optimization problem has always been a hot issue in mobile edge computing (MEC). In this paper, the problem is formulated as a long-term quality of service (QoS) improvement problem while satisfying the budget of MEC service provider (MSP). Since it is very unrealistic to accurately obtain the request information of user equipments (UEs) over a long time, we first transform the original problem into a series of real-time linear programing sub-problems by using Lyapunov optimization method, and propose a centralized algorithm to determine the resource allocation strategies. However, since the sub-problems are still NP-hard problems, it is a huge challenge to determine the strategies for all UEs with the centralized algorithm in a large scale MEC environment. Thus, we then formulate the sub-problems as an N players non-cooperative game, prove that there exists a Nash equilibrium, and develop two iterative algorithms to find the Nash equilibrium while determining the strategies. Experimental results show that the algorithms can take into account QoS and budget of MSP at the same time, and perform better compared to five other common schemes.

Abstract Nowadays, a new paradigm named mobile edge computing (MEC) is capable of supplying some cloud‐like functions at the edges of wireless networks, which enables vehicles to offload the computation intensive tasks on MEC servers with low latency. However, new challenges posed by the complex network environment and the mobility of vehicles are usually not covered by traditional offloading schemes. To solve such problems, we propose a heuristic task migration computation offloading (TMCO) scheme. Compared with traditional ones, TMCO can dynamically choose suitable places to offload the tasks for moving vehicles within deadline. For this purpose, the mobility of vehicle and strict delay deadline are considered comprehensively. We use hash table to store the number of tasks on the corresponding server and use random function to simulate the probability of task offloading. In terms of latency, experimental results suggest that the performance of TMCO is on average 10% higher than that of traditional full offloading schemes.

In this article, we design a service mechanism for profits optimization between multiple cloud providers and multiple cloud customers (many-to-many). We explore this problem from the perspective of game theory but take a different approach compared with existing cloud resource pricing game methods. First, we regard the relationships among multiple cloud customers as an evolutionary game, and formulate the competitions among the multiple cloud providers as a noncooperative game. Eventually, we form a hybrid game model in which the strategy of each customer and each cloud provider is affected not only by the other side but also by customers or cloud providers other than themselves. Second, based on the hybrid game model, we simulate the bargaining process between cloud providers and customers by controlling supply and demand allocation, and try to ultimately achieve a balanced supply and demand state, i.e., a win-win situation. For each cloud customer and provider, we design a utility function. A customer’s utility involves net profits and the cloud providers’ bidding strategies, and a cloud provider’s utility involves net profits and the cloud customers’ demand strategies. Both sides attempt to maximize their own profits under the influences of each other. We prove that our proposed strategies enable each of the two games to converge to their own equilibrium. Finally, the strategies of cloud customers and providers can be implemented through an iterative proximal algorithm ($\mathcal {IPA}$) and a distributed iterative algorithm ($\mathcal {DIA}$). The experimental results validate our methods and show that the proposed method can benefit both multiple cloud providers and customers.

Integrating user ends (UEs), edge servers (ESs), and the cloud into end-edge-cloud computing (EECC) can enhance the utilization of resources and improve quality of experience (QoE). However, the performance of EECC is significantly affected by its architecture. In this article, we classify EECC into two computing architectures types according to the visibility and accessibility of the cloud to UEs, i.e., hierarchical end-edge-cloud computing (Hi-EECC) and horizontal end-edge-cloud computing (Ho-EECC). In Hi-EECC, UEs can offload their tasks only to ESs. When the resources of ESs are exhausted, the ESs request the cloud to provide resources to UEs. In Ho-EECC, UEs can offload their tasks directly to ESs and the cloud. In this article, we construct a potential game for the EECC environment, in which each UE selfishly minimizes its payoff, study the computation offloading strategy optimization problems, and develop two potential game-based algorithms in Hi-EECC and Ho-EECC. Extensive experiments with real-world data are conducted to demonstrate the performance of the proposed algorithms. Moreover, the scalability and applicability of the two computing architectures are comprehensively analyzed. The conclusions of our work can provide useful suggestions for choosing specific computing architectures under different application environments to improve the performance of EECC and QoE.

Transformer-based deep neural networks have recently swept the field of natural language processing due to their outstanding performance, and are gradually spreading to more applications such as image/video processing. However, compared with general DNNs, training a sizeable transformer-based model is further time-consuming and memory-hungry. The existing distributed training strategies for general DNNs are not appropriate or can not efficiently handle transformer-based networks. In view of this, we propose an intra-layer model parallelization optimization strategy, AccTFM, which introduces a novel fine-grained pipeline execution and hybrid communication compression strategy to overcome the synchronization bottleneck. Specifically, on one hand, it first decouples the inter-layer computation and communication dependencies, and then searches for the optimal partitioning strategy to maximize the overlap of computation and communication. On the other hand, the hybrid communication compression module consists of token-level top-$k$sparsification and piecewise quantization methods aiming at minimizing communication traffic. Experimental results show that AccTFM accelerates transformer-based DNNs training by up to 2.08x compared to state-of-the-art distributed training techniques.

Deep Neural Networks (DNNs) are widely investigated due to their striking performance in various applications of artificial intelligence. However, with DNNs becoming larger and deeper, the computing resource of a single hardware accelerator is insufficient to meet the training requirements of popular DNNs. Hence, it is required to train them using multiple accelerators in a distributed setting. For a better utilization of the accelerators and a faster training, it is necessary to partition the whole process into segments that can run in parallel. However, in this context, intra-layer parallelization techniques (i.e., data and model parallelization) often face communication and memory bottlenecks, while the performance and resource utilization of inter-layer parallelization techniques (i.e., using pipelining) depend on the partitioning possibilities of the model. We present EffTra, a synchronous hybrid parallelization strategy, that uses a combination of intra-layer and inter-layer parallelism to realize a distributed training of DNNs. EffTra employs the idea of dynamic programming to try to search for the optimal partitioning of a DNN model and assigns devices to the obtained partitions. Our evaluation shows that EffTra accelerates training by up to 2.0x and 1.78x compared to state-of-the-art inter-layer (i.e., GPipe) and intra-layer (i.e., data parallelism) parallelization techniques respectively.

Task scheduling in cloud environments is the problem of assigning and executing computational tasks on the available cloud resources. Effective task scheduling can improve processor utilization, reduce processor energy consumption, and improve user experience. Large-scale task scheduling under multiple constraints is an NP-complete problem. The traditional task scheduling algorithm cannot be applied to large-scale scheduling, either because of high time complexity or because its heuristic algorithm cannot be applied to complexly large-scale scenarios. The problem of large-scale task scheduling is gradually becoming a challenge in cloud computing. The article proposes a topology-based multilevel algorithm for large-scale task scheduling in clouds. Based on the topological order of the graph, multi-level coarsening is performed on the large-scale graphs, and then uses the traditional scheduling algorithm for the initial scheduling of the coarse graph, and then refine the initial scheduling result during its uncoarsen phrase. It can perform fast and efficient scheduling of large-scale task graphs. At the same time, it has good compatibility, which can be combined with excellent traditional scheduling algorithms.

In this paper, we focus on request migration strategies among multi-servers for load balancing. Different from the general load balancing problem, we consider it under a distributed, non-cooperative, and competitive environment. Due to the mentioned characteristics, we view our problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple servers, in which each server is informed with incomplete information of other servers. For each server, we define its expected response time as a disutility function and try to minimize its value. We also take into account server availability, which impacts the processing capacity of a server and thus its disutility. We solve the problem by employing variational inequality (VI) theory and prove that there exists a Nash equilibrium solution set for the formulated game. Then, we propose an iterative proximal algorithm (IPA) to compute a Nash equilibrium solution. The convergence of the IPA algorithm is also analyzed and we find that it converges to a Nash equilibrium. Finally, we conduct some numerical calculations to verify our theoretical analyses. The experimental results show that our proposed IPA algorithm converges to a Nash equilibrium very quickly and significantly decreases the disutilities of all servers by configuring a proper request migration strategy.

In this paper, we try to design a service mechanism for profit optimizations of both a cloud provider and its multiple users. We consider the problem from a game theoretic perspective and characterize the relationship between the cloud provider and its multiple users as a Stackelberg game, in which the strategies of all users are subject to that of the cloud provider. The cloud provider tries to select and provision appropriate servers and configure a proper request allocation strategy to reduce energy cost while satisfying its cloud users at the same time. We approximate its servers selection space by adding a controlling parameter and configure an optimal request allocation strategy. For each user, we design a utility function which combines the net profit with time efficiency and try to maximize its value under the strategy of the cloud provider. We formulate the competitions among all users as a generalized Nash equilibrium problem (GNEP). We solve the problem by employing variational inequality (VI) theory and prove that there exists a generalized Nash equilibrium solution set for the formulated GNEP. Finally, we propose an iterative algorithm (IA), which characterizes the whole process of our proposed service mechanism. We conduct some numerical calculations to verify our theoretical analyses. The experimental results show that our IA algorithm can benefit both of a cloud provider and its multiple users by configuring proper strategies.

A variety of realistic industrial problems can be constructed into quadratic programming (QP) problems, especially their time-varying versions. A zeroing neural network (ZNN) as a good approach for dynamic problems can solve QP problems subject to equality constraints in the past. In this article, we propose a unified predefined-time convergent and robust ZNN (PTCR-ZNN) model for solving time-varying QP problems subject to equality or inequality constraints. Compared with the normal ZNN model, the PTCR-ZNN model mainly has advantages in the following three aspects: 1) solving QP problems with or without inequality constraints in a unified model; 2) converging to the optimal solution of QP problems within a predefined time that can be determined in advance; and 3) resisting many external noises with tiny and predictable residual error. These improvements have been rigorously proved in theory. By conducting both qualitative and quantitative simulations with comparisons, the superior properties of the PTCR-ZNN model are further validated. Finally, the application of the PTCR-ZNN model to image fusion task illustrates the efficiency together with its applicability.

Closer to mobile users geographically, mobile edge computing (MEC) can provide some cloud-like capabilities to users more efficiently. This enables it possible for resource-limited mobile users to offload their computation-intensive and latency-sensitive tasks to MEC nodes. For its great benefits, MEC has drawn wide attention and extensive works have been done. However, few of them address task migration problem caused by distributed user mobility, which can't be ignored with quality of service (QoS) consideration. In this article, we study task migration problem and try to minimize the average completion time of tasks under migration energy budget. There are multiple independent users and the movement of each mobile user is memoryless with a sequential decision-making process, thus reinforcement learning algorithm based on Markov chain model is applied with low computation complexity. To further facilitate cooperation among users, we devise a distributed task migration algorithm based on counterfactual multi-agent (COMA) reinforcement learning approach to solve this problem. Extensive experiments are carried out to assess the performance of this distributed task migration algorithm. Compared with no migrating (NM) and single-agent actor-critic (AC) algorithms, the proposed distributed task migration algorithm can achieve up 30-50 percent reduction about average completion time.

The pricing mechanism of cloud-computing resources is an essential issue for both cloud customers and service providers, especially from the point of multi-provider competition. Although various mechanisms for resource provision are proposed, few studies have focused on multi-attribute resource provision with the objective of improving benefits of both cloud customers and service providers. To address the issue, we propose a price bidding mechanism for multi-attribute cloud-computing resource provision from the perspective of a non-cooperative game, in which the information of each player (customers and providers) is incomplete to others and each player wishes to maximize his/her own benefit. More specifically, considering the fairness pricing competition, we propose a novel and incentive resource provision model referring to the Quality-of-Service (QoS) and the bidding price. Then, combining with the resource provision model, the problem of price bidding is formulated as a game to find a proper price for each cloud provider. We demonstrate the existence of Nash equilibrium solution set for the formulated game model by assuming that the quantity function of provided resources from every provider is continuous. To find a Nash equilibrium solution, we propose an Equilibrium Solution Iterative (ESI) algorithm, which is proved to converge to a Nash equilibrium. Finally, a Near-equalization Price Bidding (NPB) algorithm is proposed to modify the obtained Nash equilibrium solution. Extensive simulated experiments results and the comparison experiments with the state-of-the-art and benchmark solutions validate and show the feasibility of the proposed method.

End-to-end latency is sensitive for user-interactive neural network (NN) services on clouds. For periods of high request load, co-locating multiple NN requests has the potential to reduce end-to-end latency. However, current batch-based accelerators lack request-level parallelism support, leaving the queuing time non-optimized. Meanwhile, naively partitioning resources for simultaneous requests suffers from longer execution time as well as lower resource efficiency because different applications utilize separate resources without sharing. To effectively reduce the end-to-end latency for real-time NN requests, we propose CoExe architecture, equipped with a pipeline implementation of a sparsity-driven real-time co-execution model. By leveraging the non-trivial amount of sparse operations during concurrent NNs execution, the end-to-end latency is decreased by up to 12.3× and 2.4× over Eyeriss-like and SCNN at peak workload mode. Besides, we propose row cross (RC) dataflow to reduce data movement cost, and avoid memory duplication.

Nowadays, cloud-supported Internet of Things (Cloud-IoT) has been broadly deployed in smart medical systems, where the limitations of Internet of Things (IoT)-associated medical devices in terms of data access, storage, scalability, and computing are solved through the use of cloud computing architectures. However, with the rapid development of medical equipment and the increasing number of medical devices, it will be extremely difficult to program or manage such an expanding and massive medical IoT system in traditional single-cloud platforms. In this article, we design and implement a multicloud framework for building OpenStack-based platform for medical IoT, referred to as the tri-storage failure recovery system (Tri-SFRS). To implement Tri-SFRS, we combine several techniques to achieve this reduction in effort, including a multicloud cascading architecture, a low-overhead native testing framework, a medical data storage-backup mechanism, and snapshot-volume cascaded operations for b-ultrasonic data. Tri-SFRS is also able to simultaneously enable resource management specialization. Tri-SFRS has been designed as a native component in the OpenStack platform, and it demonstrates the degree of native OpenStack multicloud platform management by our proposed cascading framework. Comparing with the traditional single-cloud OpenStack platform, Tri-SFRS can reduce the resource-request processing latency from B ultrasonic machines by up to 20%. Our experiments also demonstrate the broad applicability of Tri-SFRS.

The prevalence of the Internet of Things (IoT) and the explosion of available information on the Web have led to an enormous amount of widely available IoT data sets with sparsity. Sparse matrix-vector multiplication (SpMV) is one of the most essential algorithms in various kinds of IoT applications. This article designs an autotuning hybrid computing scheme for SpMV, named ahSpMV, on the powerful and unique architecture of Sunway TaihuLight supercomputer, to combine the advantages of the heterogeneous parallel Sunway architecture and the Hybrid (HYB) sparse matrix format and optimize the SpMV's performance. First, we propose a heterogeneous parallelization design for ahSpMV based on the heterogeneous manycore architecture of the SW26010 of Sunway TaihuLight and the hybrid feature of the HYB format. Second, we propose several optimization techniques for computation and communication of ahSpMV, to fully utilize the computing power of Sunway. Third, we analyze the execution time of ahSpMV on Sunway. Fourth, based on the performance analysis, we propose an autotuning scheme for ahSpMV to set the proper parameter for the HYB format. We evaluate ahSpMV's performance on the Sunway architecture. The result analysis indicates that ahSpMV has obvious performance improvement over parallel SpMV based on other related sparse matrix formats. The optimization techniques and the autotuning scheme for ahSpMV also yield expected optimization effects. Moreover, the experimental results illustrate that ahSpMV has good scalability on the Sunway architecture.

Mobile edge computing (MEC) is becoming a promising paradigm of providing computing servers, like cloud computing, to Edge node. Compared to cloud servers, MECs are deployed closer to mobile devices (MDs) and can provide high quality-of-service (QoS; including high bandwidth, low latency, etc) for MDs with computation-intensive and delay-sensitive tasks. Faced with many MDs with high QoS requirements, MEC with limited computation capacity should consider how to allocate the computing resources to MDs to maximize the number of served MDs. Besides, for each MD, he/she wants to minimize the energy consumption within an acceptance delay range. To solve these issues, we propose a Game-based Computation Offloading (GCO) algorithm including a task offloading profile of MEC and the transmission power controlling of each MD. Specifically, we propose a Greedy-Pruning algorithm to determine the MDs that can offload the tasks to MEC. Meanwhile, each MD competes the computing resources by using his/her transmission power-controlling strategy. We illustrate the problem of task offloading for multi-MD as a non-cooperative game model, in which the information of each player (MDs) is incomplete for others and each player wishes to maximize his/her own benefit. We prove the existence of the Nash equilibrium solution of our proposed game model. Then, it is proved that the transmission power solution sequence obtained from GCO algorithm converges to the Nash equilibrium solution. Extensive simulated experiments are shown and the comparison experiments with the state-of-the-art and benchmark solutions validate and show the feasibility of the proposed method.

In this article, we investigate code-oriented partitioning computation offloading strategy for multiple user equipments (UEs) and multiple mobile edge computing servers with limited resources (i.e., limited computing power and waiting task queues with finite capacity). This article aims to develop an offloading strategy to decide the execution location, CPU frequency, and transmission power for UE while minimizing the execution overhead (i.e., a weighted sum of energy consumption and computational time) of UE's applications, which is an NP-hard problem. To achieve the objective, first, we transform the problem into a convex optimization problem and find the optimal solution. Second, we propose a decentralized computation offloading strategy (DCOS) algorithm for UE, and define a dictionary data structure for recording the strategy of the UE to reduce the algorithm complexity. Finally, the effectiveness of DCOS, and the impact of various key parameters on the strategy and overhead are demonstrated by simulation experiments.

In this article, two improved finite-time convergent complex-valued zeroing neural network (IFTCVZNN) models are presented and investigated for real-time solution of time-varying reciprocal of complex matrices on account of two equivalent processing ways of complex calculations for nonlinear activation functions. Furthermore, a novel nonlinear activation function is explored to modify the comprehensive performance of such two IFTCVZNN models. Compared with existing complex-valued neural networks converging within the limited time, the proposed IFTCVZNN models with the new activation function have better finite-time convergence and less conservative upper bound. Numerical simulations verify that the maximum of convergence time estimated via Lyapunov stability is theoretically much closer to the actual convergence time.

Multi-dimensional, large-scale, and sparse data, which can be neatly represented by sparse tensors, are increasingly used in various applications such as data analysis and machine learning. A high-performance sparse tensor-vector product (SpTV), one of the most fundamental operations of processing sparse tensors, is necessary for improving efficiency of related applications. In this article, we propose aeSpTV, an adaptive and efficient SpTV framework on Sunway TaihuLight supercomputer, to solve several challenges of optimizing SpTVon high-performance computing platforms. First, to map SpTV to Sunway architecture and tame expensive memory access latency and parallel writing conflict due to the intrinsic irregularity of SpTV, we introduce an adaptive SpTV parallelization. Second, to co-execute with the parallelization design while still ensuring high efficiency, we design a sparse tensor data structure named CSSoCR. Third, based on the adaptive SpTV parallelization with the novel tensor data structure, we present an autotuner that chooses the most befitting tensor partitioning method for aeSpTV using the variance analysis theory of mathematical statistics to achieve load balance. Fourth, to further leverage the computing power of Sunway, we propose customized optimizations for aeSpTV. Experimental results show that aeSpTV yields good sacalability on both thread-level and process-level parallelism of Sunway. It achieves a maximum GFLOPS of 195.69 on 128 processes. Additionally, it is proved that optimization effects of the partitioning autotuner and optimization techniques are remarkable.

In the distributed computing framework of Spark, cross-node/rack data transfer produced by map tasks and reduce tasks are common problems resulting in performance degradation, such as prolonging of entire execution time and network congestion. To address these problems, this article utilizes the bipartite graph modelling to propose an optimal locality-aware task scheduling algorithm. By considering global optimality, the algorithm can generate the optimal scheduling solution for both the map tasks and the reduce tasks for data locality. Because of the different communication modes, this article uses a unified graph to model the map task scheduling and the reduce task scheduling respectively. Then, by calculating the communication cost matrix of tasks, we formulate an optimal task scheduling scheme to minimize overall communication cost and transform the problem as the well-known graph problem: minimum weighted bipartite matching (MWBM), which can be resolved by Kuhn-Munkres algorithm. In addition, this article proposes a locality-aware executor allocation strategy to improve the data locality further. We implement our algorithm and strategy in Spark-2.4.1 and evaluate its performance using several representative micro-benchmarks, macro-benchmarks, and HiBench benchmark suite. The experimental results verify that by reducing the network traffic and access latency, the proposed algorithm can improve the job performance substantially compared to some other task scheduling algorithms.

Considering the fact that a server is more likely to fail if it is highly loaded, in this paper, we involve load impacts on service reliability in a heterogeneous cluster, where servers have load-dependent reliabilities and jobs have resource and execution interval demands. Specifically, each server is specified by a resource capacity and a workload limitation, i.e., the server is expected to perform reliably if its workload is less than the workload limitation. There is also a set of jobs needing to be executed on these servers. Each job is associated with a resource demand and an execution interval, i.e., the time interval that the job is planned to be executed. Our goal is to find a reliable schedule ofjobs to servers such that all servers' workload limitations are satisfied. The problem is proved to be strongly NP-complete, which implies that there is not even a pseudo-polynomial time algorithm. Hence, we try our best to find a reliable schedule. To solve the problem, we define a stereogram (specifically defined as a bipartite stereogram) and develop a bipartite stereogram matching-based scheduling method (BSMSM), which combines the matching of our constructed bipartite stereogram with reliable scheduling. Some theoretical results are also derived in this paper. We perform extensive random experiments and the results show that BSMSM can find reliable schedules, i.e., the workloads on all servers can be maintained to be less than or equal to the servers' workload limitations, to a large extent.

We consider the minimal cost server configuration for meeting resource demands over multiple time slots. Specifically, there are some heterogeneous servers. Each server is specified by a cost, certain amounts of several resources, and an active interval, i.e., the time interval that the server is planed to work. There are different overall demands for each type of resource over different time slots. A feasible solution is a set of servers such that at any time slot, the resources provided by the selected servers are at least their corresponding demands. Notice that, a selected server can not provide resources for the time slots out of its active interval. The total cost of the solution is the summation of the costs of all selected servers. The goal is to find a feasible solution with minimal total cost. This problem is proved to be NP-hard due to a reduction from the multidimensional knapsack problem (MKP), which is a well-known NP-hard combinational optimization problem. To solve our problem, we present a randomized approximation algorithm called partial rounding algorithm ($\mathcal {PRA}$), which guarantees$O\left(\log \left(KT \right) \right)$-approximation, i.e.,$\eta \;\log \left(KT \right)$-approximation, where$K$is the number of kinds of resources,$T$is the number of time slots, and$\eta$is a positive constant. Furthermore, to minimize$\eta$as much as possible, we propose a varied Chernoff bound and apply it in$\mathcal {PRA}$. We perform extensive experiments with random inputs and a specific application input. The results show that$\mathcal {PRA}$with our varied Chernoff conclusion can find solutions closing to the optimal one.

Summary In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.

In this paper, we focus on price bidding strategies of multiple users competition for resource usage in cloud computing. We consider the problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple cloud users, in which each cloud user is informed with incomplete information of other users. For each user, we design a utility function which combines the net profit with time efficiency and try to maximize its value. We design a mechanism for the multiple users to evaluate their utilities and decide whether to use the cloud service. Furthermore, we propose a framework for each cloud user to compute an appropriate bidding price. At the beginning, by relaxing the condition that the allocated number of servers can be fractional, we prove the existence of Nash equilibrium solution set for the formulated game. Then, we propose an iterative algorithm ($\mathcal {IA}$), which is designed to compute a Nash equilibrium solution. The convergency of the proposed algorithm is also analyzed and we find that it converges to a Nash equilibrium if several conditions are satisfied. Finally, we revise the obtained solution and propose a near-equilibrium price bidding algorithm ($\mathcal {NPBA}$) to characterize the whole process of our proposed framework. The experimental results show that the obtained near-equilibrium solution is close to the equilibrium one.

In this paper, we focus on strategy configurations of multiple users to make cloud service reservation. We consider the problem from a game theoretic perspective and formulate it into a non-cooperative game among the multiple cloud users, in which each user is informed with incomplete information of other users. For each user, we design a utility function which combines the net profit with time efficiency and try to maximize its value. We solve the problem by employing variational inequality (VI) theory and prove that there exists a Nash equilibrium solution set for the formulated game. Then, we propose an iterative proximal algorithm (IPA), which is designed to compute a Nash equilibrium solution. The convergence of the IPA algorithm is also analyzed and we find that it converges to a Nash equilibrium if several conditions are satisfied. Finally, we conduct some numerical calculations to verify our theoretical analysis. The experimental results show that our proposed IPA algorithm converges to a stable state very quickly and improves the utilities of all users to certain extent by configuring a proper request strategy.

The energy aware scheduling problem has been a critical issue in high-performance clusters owing to their high operation cost, environmental impact, and low reliability. An existing technique to reduce energy consumption of applications is dynamic voltage/frequency scaling (DVFS). In this paper, we develop an energy aware scheduling algorithm called EASLA for precedence-constrained applications in the context of Service Level Agreement (SLA) on DVFS-enabled cluster systems. Due to the dependencies among tasks and makespan extension, there may be some slacks under used. The main idea of the EASLA algorithm is to distribute each slack to a set of tasks and scale frequencies down to try to minimize energy consumption. Specifically, it first finds the maximum set of independent tasks for each task, and then iteratively allocates each slack to the maximum independent set whose total energy reduction is the maximal. Randomly generated graphs and two real-world applications are tested in our experiments. The experimental results show that our scheduling algorithm can save up to 22.68% and 12.01% energy consumption compared with GreedyDVS and EvenlyDVS algorithms, respectively.