Deep Neural Networks (DNNs) have grown rapidly in size and complexity, requiring various optimizations to make training and deployment practically feasible. For example, BLOOM 176B and Megatron-Turing 530B require terabytes of memory and zettaflops of compute, which are far beyond the capabilities of any single device. Generally, training at such scales requires the use of large multi-machine, multi GPU/CPU systems, where parallelization techniques such as data, model, pipeline, and tensor parallelism must be explored and employed at different levels. Following the main body of research in this direction, we represent DNNs as DAG-structured workflows and formulate DNN training as a workflow mapping problem for throughput maximization. We design a class of approximation algorithms for DNN workflow partitioning and mapping with a performance bound, specifically targeting heterogeneous systems. Extensive experimental results show the efficacy of our proposed method and also confirm our theoretical analysis.

Microservice architecture has demonstrated immense advantages in solving the scalability and maintainability problems confronted by traditional monolithic systems. However, existing microservice architectures still encounter the problem of blurred boundaries, which significantly impact the system performance. The primary reason being the lack of unified evaluation indicators and efficient microservice splitting strategies. Specifically, some approaches divide entities like classes subjectively, resulting in inconsistent microservice boundaries, while others utilize objective criteria, but their complexity makes practical implementation challenging. To this end, we formalize the optimal microservice granulation problem, show its NPcompleteness and propose the granulation solution based on granular-ball computing. Our designs encompass a microservicebased information decision system to quantify the structural similarity between entities, a microservice granulation representation method based on granular-ball computing, and an optimal microservice granulation method given fixed budget constraint. Extensive experiments are conducted on open-source microservice projects to showcase the granulation result and the experimental results also show the efficacy and effectiveness.

Abstract Many computing workloads in big data and machine learning applications are structured as directed acyclic graphs (DAG) and deployed on PC clusters for parallel execution using multiple physical or virtual machines. The scheduling of such workloads is critical to the application performance such as execution time and a plethora of techniques have been developed, taking into account various aspects such as data locality, network bandwidth, and server capability. We formulate DAG-structured workload scheduling as a nonlinear integer programming (NIP) problem and prove it to be NP-complete. Our empirical study reveals a positive correlation between scheduling plan distance (SPD) and finish time gap (FTG), and based on this finding, we propose a running time gap strategy (RTGS) to tackle this scheduling problem in multiprocessor environments. RTGS follows the main optimization strategy in the family of whale optimization algorithm (WOA). We derive a new function and use a greedy algorithm to generate an effective scheduling plan in RTGS. Extensive experiments with real production traces from Alibaba on simulation environments and realistic Hadoop environments show that our approach significantly improves the stability of WOA when applied to the scheduling problem of DAG-structured workloads, and also reduces the workload completion time by up to $$93\%$$ 93 % in comparison with seven state-of-the-art baseline algorithms.

The rapidly increasing demand for big data processing has necessitated the development of advanced scheduling policies that can effectively accommodate urgent job requirements. This paper presents the Urgent Job Priority Scheduler (UJPS) for Hadoop YARN, aimed at handling urgent jobs efficiently in big data processing. UJPS uses an Aging model to cut waiting times and prevent job starvation, a Dynamic Priority model for urgency-based prioritization, and a Container Load model to boost data locality and efficiency. Tested on Hadoop with benchmark tasks, UJPS outperforms five advanced schedulers, lowering waiting times by up to 81.42% and reducing job runtime by 32.90%. It prioritizes urgent tasks while ensuring overall efficiency, offering benefits to organizations using Hadoop YARN for timely job execution.

Hadoop stands out as one of the most widely employed systems for processing big data. Embedded within Hadoop as a foundational technological layer is the Hadoop Distributed File System (HDFS), providing fault tolerance and high throughput in data storage. This is achieved through mechanisms such as data partitioning, block replication, and cluster-wide distribution, which in turn facilitate parallel computing in the upper layers. Consequently, the strategy governing block placement emerges as a pivotal factor influencing the performance of Hadoop clusters. However, the default block distribution approach of HDFS overlooks the varying capacities of data nodes and their diverse data access patterns, rendering it unsuitable for heterogeneous Hadoop clusters. To address this challenge, we formulate a Block Distribution problem for heterogeneous clusters, prove it to be NP-complete, and design an approximation algorithm, Linear Programming-based Iterative Rounding (LPIR-BD), with a rigorous performance guarantee. Extensive experiments illustrate the notable performance superiority of LPIR-BD over several state-of-the-art algorithms, thus confirming the efficacy of our theoretical analysis.

Peer-to-peer (P2P) content delivery networks (CDNs) have demonstrated immense potential to mitigate escalating network traffic. Meanwhile, blockchain emerges as a promising technology that can overcome the shortcomings confronted by P2P CDNs via acting as a trusted third party (TTP) to ensure critical security properties such as fairness and offering monetary incentivization. However, existing protocols for blockchain-based P2P CDNs still encounter the delivery efficiency issue, one of the primary reasons being the absence or failure to identify the most suitable deliverers. Specifically, some overlook the process of selecting deliverers, entrusting them haphazardly, and some merely consider a single evaluation dimension for a deliverer, resulting in a lack of comprehensiveness. Even when multiple dimensions are considered, the outcome of each dimension is not verifiable, leading to unreliability. To this end, we propose an optimized deliverer selection method in blockchain-based P2P CDNs. Our designs encompass a proof of delivery quality (PoQD) protocol to quantify the accumulative verifiable contributions of a deliverer, a comprehensive credibility evaluation mechanism based on neighborhood entropy, and a provider budget constraint optimized deliverer selection algorithm. Extensive experiments are conducted on Ethereum test network to justify our adaptive selection of k optimized deliverers, desired delivery efficiency and feasible on-chain costs. The experiment results indicate the efficacy and effectiveness of our proposed method.

In the evolving landscape of business analytical practice, big data stands as a pivotal force, steering organizational strategies, particularly in portfolio management across end-to-end businesses. With the surge in data's volume, variety, veracity and velocity, there is a pressing need for sophisticated computational methods to demystify intricate business portfolios, thereby facilitating astute decision-making. Traditional portfolio analysis techniques, although foundational, grapple with the challenges posed by expansive, multifaceted data and volatile market dynamics. To counter these challenges, our research pioneers an innovative approach, harnessing the power of clustering algorithms to refine and consolidate business portfolios. We employ big data techniques to analyze and categorize extensive portfolio datasets, unearthing inherent groupings and patterns. Leveraging clustering algorithms, we categorize business entities by similarity, yielding a streamlined and lucid portfolio blueprint. Our approach not only enhances the clarity of vast business portfolios but also strengthens strategic decision-making capabilities, propelling organizational nimbleness and market competitiveness. Through comparative analyses, our solution showcases significant advantages in portfolio simplification and decision-making efficacy over conventional techniques.

In Hadoop’s big data processing systems, YARN is responsible for resource management and job scheduling. The built-in job scheduling algorithms in YARN are simple to execute, but have some limitations such as job starvation, excessive server load, and load imbalance. In this paper, we propose a new Hybrid Dynamic Priority job Scheduling algorithm (HDPS) to address these limitations. HDPS dynamically adjusts the priority of a job as its waiting time increases to prevent job starvation. It also features a task assignment strategy designed specifically to address data locality by considering the available resources of servers and the distribution of data blocks stored on servers to reduce data transfer time and improve job execution efficiency. We implement and integrate HDPS into YARN and conduct experiments in a real Hadoop system using built-in benchmark test cases of Hadoop. Experimental results show that HDPS exhibits comprehensive superior performance over existing algorithms in terms of execution efficiency and load balance.

Machine learning techniques have gained significant traction in supply chain forecasting, driven by the increasing availability of data assets. These techniques offer opportunities to optimize management processes, reduce operational costs, and enhance decision-making for enterprise success. However, conventional statistical approaches dominating time series forecasting, such as the Autoregressive-moving-average model (ARMA), dynamic regression, and unobserved component models (UCMs), suffer from limitations in model accuracy and performance. They struggle to handle batch processing, large-scale big data, uncertainty-induced disruptions, and the synchronization of demand and supply scenarios. To address these challenges, we propose a class of ensemble techniques that combine neural networks with baseline models. Firstly, we conduct classification and segmentation by leveraging feature engineering on signal components, such as spikes and anomalies as outlier skews, to capture the complexity of combined scenarios in categorical data hierarchies and identify patterns for ensemble forecasting. Subsequently, we employ an ensemble model equipped with time series pattern sensors to automatically discern signal components, encompassing seasonality, promotions, trends, and intermittent or discontinued activities. We evaluate the performance of eight commonly-used model categories, and our proposed ensemble modeling approaches exhibit substantial improvements in accuracy compared to individual baseline models and other univariate time series algorithms.

Abstract Extracting frequent itemsets from datasets is an important problem in data mining, for which several mining methods including FP‐Growth have been proposed. FP‐Growth is a classical frequent itemset mining method, which generates pattern databases without candidates. Many improvements have been made in the literature due to the high time complexity and memory usage of FP‐Growth. However, most of them still suffer from performance issues on large datasets. In this paper, we design an auxiliary structure, Array Prefix‐Tree (AP‐Tree), and propose a new algorithm, Array Prefix‐Tree Growth (APT‐Growth), which is further parallelized as a Spark workflow, referred to as PAPT‐Growth. Based on a density threshold, we incorporate an adaptive algorithm selection process into PAPT‐Growth to ensure its running time performance. We conduct extensive experiments on different thresholds and multiple datasets, and experimental results show the performance superiority of PAPT‐Growth in comparison with several state‐of‐the‐art methods such as PFP, YAFIM, and DFPS. The analysis on density reveals a changing point, which justifies the necessity and validity of adaptive algorithm selection.

The rapid advance in science and technology is made possible by research conduct and breakthroughs in a wide range of fields, which have resulted in a large number of academic papers. Searching through the enormous literature to find relevant information of one's research interest has become an increasingly important yet challenging problem for many researchers. Most existing methods for academic paper recommendation are based on the analysis of paper contents and only meet with limited success. We propose a novel method based on heterogeneous information networks for academic paper recommendation, referred to as HNPR. This method considers the citation relationship between papers, the collaboration relationship between authors, and the research area information of papers to construct two types of heterogeneous information networks. In such networks, a random walk-based strategy is used to simulate natural sentences for the discovery of relevance between two papers according to a mature natural language processing model. Extensive experimental results using real data in public digital libraries show that HNPR significantly improves the accuracy of academic paper recommendation in comparison with traditional content-based recommendation methods.

Big data generated by large-scale scientific and industrial applications need to be transferred between different geographical locations for remote storage, processing, and analysis. High-speed dedicated connections provisioned in High-performance Networks (HPNs) are increasingly utilized to carry out such big data transfer. HPN management highly relies on an important capability of performance (mainly throughput) prediction to reserve sufficient bandwidth and meanwhile avoid over-provisioning that may result in unnecessary resource waste. This capability is critical to improving the resource (mainly bandwidth) utilization of dedicated connections and meeting various user requests for data transfer. Conventional methods conduct performance prediction by fitting prior observed transfer history with predefined loss functions, without considering unobservable latent factors such as competing loads on end hosts. Such latent factors also have a significant impact on the application-level data transfer performance, which may result in an inaccurate prediction model. In this paper, we first investigate the impact of latent factors and propose a clustering-based method to eliminate their negative impact on performance prediction. We then develop a robust machine learning-based performance predictor by: i) incorporating the proposed latent factor elimination method into data preprocessing, and ii) adopting a customized domain guided loss function. Extensive experimental results show that our predictor achieves significantly higher prediction accuracy than several other state-of-the-art methods.

Many next-generation scientific and business applications feature large-scale data-intensive workflows, which require massive computing resources for execution on high-performance clusters in cloud environments. Such computing resources (e.g., VCores and virtual memory) requested through parameter setting in big data systems, if not fully utilized by workloads, are simply wasted due to the nature of exclusive access made possible by containerization. This necessitates accurate modeling and prediction of workflow performance to make an effective recommendation of appropriate parameter settings to end users. However, it is challenging to determine optimal workflow and system configurations due to the large parameter space and the interaction between various technology layers of big data systems. Towards this goal, we propose a machine learning-based feature selection method to identify influential parameters based on historical performance measurements of Spark-based computing workloads executed in big data systems with YARN. We first identify a comprehensive set of parameters across multiple layers in the big data technology stack including workflow input structure, Spark computing engine, and YARN resource management. We then conduct an in-depth exploratory analysis of their individual and coupled impact on workflow performance, and develop a performance-influence model using random forest for prediction. Experimental results show that the proposed approach identifies important features for performance modeling and achieves high accuracy in performance prediction.

Modern data-intensive applications require the transfer of big data over high-performance networks (HPNs) through bandwidth reservation for various purposes such as data storage and analysis. The key performance metrics for bandwidth scheduling include the utilization of network resources and the satisfaction of user requests. In this paper, for a given batch of Deadline-Constrained Bandwidth Reservation Requests (DCBRRs), we attempt to maximize the number of satisfied requests with flexible scheduling options over link-disjoint paths in an HPN while achieving the best average Earliest Completion Time (ECT) or Shortest Duration (SD) of scheduled requests. We further consider this problem from two bandwidth-oriented principles: (i) Minimum Bandwidth Principle (MINBP), and (ii) Maximum Bandwidth Principle (MAXBP). We show that both of these problem variants are NP-complete, and propose two heuristic algorithms with polynomial-time complexity for each. We conduct bandwidth scheduling experiments on both small-and large-scale DCBRRs in a real-life HPN topology for performance comparison. Extensive results show the superiority of the proposed algorithms over existing ones in comparison.

Many scientific applications are generating extremely large amounts of data at a high speed, which must be transferred to remote collaborating sites for storage and analysis. Such high- demanding data transfer has been increasingly supported by bandwidth reservation services in high-performance networks (HPNs). For each bandwidth reservation request (BRR), most existing scheduling algorithms return either the best-case reservation option or a reject message if the BRR cannot be satisfied. To perform intelligent scheduling, we provide two alternative reservation options in the latter case: schedule the BRR within the closest time intervals before and after the user-specified time interval. We consider two different types of BRRs and for each, we design a flexible bandwidth scheduling algorithm with a rigorous optimality proof to compute both the best and alternative reservation options. For comparison, we also design two heuristics adapted from existing bandwidth scheduling algorithms. Extensive simulations show that the proposed algorithms have superior performance to those in comparison.

Bandwidth reservation has been increasingly used to provide QoS for various network applications. To accommodate a high-priority bandwidth reservation request (BRR), the bandwidth scheduler sometimes needs to preempt existing bandwidth reservations that have been made for BRRs with a lower priority, which is traditionally known as connection preemption. When such preemption is unavoidable, one primary goal of bandwidth scheduling is to minimize the disruption to existing reservations. In this paper, we study the problem of bandwidth reservation preemption for two types of BRRs, bandwidth- and data transfer- oriented, respectively, on one given link of the scheduling network with two different objectives: (i) minimize the number and then the total bandwidth of existing bandwidth reservations to be preempted, and (ii) minimize the total bandwidth and then the number of existing bandwidth reservations to be preempted. We prove these four problems to be NP-complete and propose a heuristic algorithm for each. We also design baseline heuristic algorithms for performance comparison. Extensive simulation results show that the proposed heuristic algorithms outperform those in comparison.

Hadoop is one of the most popular distributed systems for big data computing in both industry and science communities. The default data placement strategy of Hadoop Distributed File System (HDFS), which was initially designed for homogenous environments, may suffer from performance degradation when deployed in heterogeneous clusters comprised of data nodes with disparate computing power and disk capacity, hence undermining the performance of MapReduce applications. In this paper, we use a Grey Forecast model to predict data hotness dynamically and determine an appropriate number of data block replicas on the fly. Based on such information, we further propose a dynamic data placement strategy (DDPS) to decide the best location for new replicas according to their hotness. The proposed method is able to dynamically adjust data replicas stored on each node in a heterogeneous Hadoop cluster and reduce the response time of big data applications. Experimental results on a heterogeneous Hadoop cluster show that DDPS together with the prediction model significantly increases application execution efficiency and improve MapReduce performance over the default HDFS configuration.

Multi-path routing has been increasingly used to improve aggregate bandwidth for big data transfer in various network environments. Typical solutions to this problem include a path set with the largest total bandwidth and the widest path pair. In this paper, we formulate a multi-path routing problem to maximize the total bandwidth of k edge-disjoint paths, where k > 1. We show this problem to be NP-complete and propose a heuristic algorithm with focus on global optimization. We implement the proposed algorithm and evaluate its performance in comparison with existing solutions in the literature. Extensive simulation results illustrate the superiority of the proposed algorithm in terms of aggregate bandwidth and satisfaction of edge count constraint.

With the maturity and proliferation of Software-Defined Networking (SDN), there has been an increasing number of network deployments that provide dedicated connections through on-demand and in- advance scheduling in support of data-intensive applications for global scientific collaboration. In such dedicated network environments, bandwidth scheduling serves as a key technique to improve the utilization of network resources and meet diverse user requests. In this paper, we formulate a periodic bandwidth scheduling problem to maximize the number of satisfied user requests for variable slot-bandwidth reservation under deadline constraint on a network path, referred to as VSBR- DC. We show that VSBR-DC is NP-complete, and propose a bandwidth scheduling algorithm based on optimal scheduling order and allocation strategy, referred to as OSOAS-BS. Extensive simulation results show that OSOAS-BS has a superior performance in terms of scheduling success ratio over three heuristic algorithms designed for performance comparison, and may be used to facilitate scientific collaboration that requires VSBR- based reservation services for coordinated data transfer over high- speed network links.

Many large-scale applications in science and business domains require the transfer of big data over high-performance networks for remote operations. Such big data transfer is increasingly supported by bandwidth reservation services that discover feasible and efficient routing options in dynamic network environments with time-varying resources. By exploring the flexility and capacity of variable paths, we formulate a generic problem of Bandwidth Scheduling with Two Variable Node-Disjoint Paths (BS-2VNDP), in which, we further consider two variable paths of fixed or variable bandwidth with negligible or non-negligible switching delay, referred to as 2VPFB/VB-0/1. We show the NP-completeness and propose a heuristic approach for each of them. We implement and test these proposed scheduling algorithms in both simulated and real-life networks. Extensive results show that they significantly outperform greedy scheduling methods in large-scale networks.

The efficiency of bandwidth scheduling in high-performance networks is critical to the utilization of network resources and the satisfaction of user requests. In this paper, we formulate a periodic bandwidth scheduling problem to maximize the number of satisfied user requests for bandwidth reservation with deadline constraint on a fixed network path, referred to as multiple deadline-constrained bandwidth scheduling (M-DCBS). We show the NP-completeness of this problem and propose a Maximum User Number Resource Reservation Algorithm (MUNRRA). Extensive simulation results show that MUNRRA exhibits a superior performance over existing algorithms in terms of scheduling success ratio and execution time. Considering the popularity of the DCBS-based service model and the rapid expansion of high-performance networks in both speed and scope, the proposed scheduling algorithm has great potential to improve the network performance of big data applications that require the DCBS service for data transfer.

The efficiency of bandwidth scheduling in high-performance networks (HPNs) is critical to the utilization of network resources and the satisfaction of user requests. We consider a periodic bandwidth scheduling problem to maximize the number of satisfied fixed-slot bandwidth reservation requests, referred to as multiple fixed-slot bandwidth scheduling (MFSBS), which is shown to be NP-complete. We first design a minimum resource occupation algorithm for a special type of M-FSBS with identical slots, referred to as MinRO-IS, and further propose a generalized version of MinRO for M-FSBS with arbitrary slots. We also design four greedy algorithms for performance comparison. Extensive simulation results illustrate that both MinRO-IS and MinRO have a superior performance over the existing algorithms in the literature and the other four greedy algorithms in comparison. Considering the popularity of the FSBS-based service model and the rapid expansion of HPNs in both speed and scope, the proposed scheduling algorithms have great potential to improve the network performance of big-data applications that require the FSBS service in HPNs.