No abstract available.

Stream processing is integral to edge computing due to its low-latency attributes. Nevertheless, variability in user group sizes and disparate computing capabilities of edge devices necessitate frequent operator migrations within the stream. Moreover, intricate dependencies among stream operators often obscure the detection of potential bottleneck operators until an identified bottleneck is migrated in the stream. To address this, we propose a Cost-Aware Operator Migration (CAOM) scheme. The CAOM scheme incorporates a bottleneck operator detection mechanism that directly identifies all bottleneck operators based on task running metrics. This approach avoids multiple consecutive operator migrations in complex tasks, reducing the number of task interruptions caused by operator migration. Moreover, CAOM takes into account the temporal variance in operator migration costs. By factoring in the fluctuating data generation rate from data sources at different time intervals, CAOM selects the optimal start time for operator migration to minimize the amount of accumulated data during task interruptions. Finally, we implemented CAOM on Apache Flink and evaluated its performance using the WordCount and Nexmark applications. Our experiments show that CAOM effectively reduces the number of necessary operator migrations in tasks with complex topologies and decreases the latency overhead associated with operator migration compared to state-of-the-art schemes.

Multi-Agent Pathfinding (MAPF) is the problem of finding plans for multiple agents such that every agent moves from its start location to its goal location without collisions. If unexpected events delay some agents during plan execution, it may not be possible for the agents to continue following their plans without causing any collision. We define and solve a T-robust MAPF problem that seeks plans that can be followed even if some delays occur, under the generalized MAPFR setting with continuous time notions. The proposed approach is complete and provides provably optimal solutions. We also develop an exact method for collision detection among agents that can be delayed. We experimentally evaluate our proposed approach in terms of efficiency and plan cost.

This paper proposes a novel approach to enhance supply chain (SC) visibility, cooperation, and performance during inventory management while effectively mitigating the risk of information leakage by leveraging machine learning techniques. The SC inventory policies are optimized using multi-agent reinforcement learning (MaRL) and SC network topological information. Furthermore, we conduct a simulation-based evaluation that demonstrates the superior performance of our method compared to alternative optimization approaches. This research effectively addresses the dual objectives of ensuring information security and achieving cost reduction in SC inventory management.

The examined paper presents a surrogate model for HPC networks. The authors have uploaded their artifact to Zenodo, which ensures a long-term retention of the artifact. This paper can thus receive the Artifacts Available badge. The artifact allows for easy re-running of experiments for two figures and textual output for one table. All of the dependencies are documented. The software in the artifact runs correctly with minimal intervention, and is relevant to the paper, earning the Artifacts Evaluated–Functional badge. The experimental results are reproduced in two figures and one table, which gains the Results Reproduced badge. Furthermore, since the artifact is also available on GitHub, the paper is assigned the Artifacts Evaluated–Reusable badge.

The recent development of new technologies within the Industry 4.0 revolution drives the increased digitization of manufacturing plants. To effectively utilize the digital twins, it is essential to guarantee a correct alignment between the physical system and the associated simulation model along the whole system life cycle. Data assimilation is frequently used to incorporate observation data into a running model to produce improved estimates of state variables of interest. However, it assumes a closed system and cannot handle structural changes in the system, e.g., machine breakdown. Instead of combining the observation data into an existing model, we aim to automatically generate the model concurrently with the data assimilation procedure. This can reduce the time and cost of building the model. In addition, it can generate a more accurate model when sudden operational changes are not reflected at the higher planning levels. Component-based model generation approach is used with the application of data and process mining techniques to generate a complete process model from the data. A new data assimilation method is proposed to iteratively generate new models based on the arrival of further data. Each model is simulated to obtain the system performance, which will be compared to the real system performance to select the best-estimated model. Identical twin experiments of a wafer-fab simulation are conducted under different scenarios to evaluate the feasibility of the proposed approach.

Smart factories manage digital twins (DTs) to evaluate the performance of various what-if production scenarios. This article presents a DT consistency-checking approach to maintain DT in high fidelity by checking whether each sensed timed event from the physical manufacturing plant is under its corresponding DT-based estimations in runtime. The approach targets DTs developed using time colored Petri net (TCPN). To build the candidates of the next observable event with observable time margins, we considered the stochastic property of the plant, frequent external actuation caused by a new order, machine maintenance, etc., as well as intermediate unobservable state transitions reaching the sensible events. Based on the considerations, we propose an iterative method to build the virtual estimates for streaming physical events using efficiently evolved state-class graphs (SCGs). We also propose a TCPN partitioning method to accelerate the SCG-evolution and make DT maintenance easier by supporting the isolation of inconsistent subnets being diagnosed. We applied the approach to a USB flash-drive factory to prove the concept and evaluated the performance under various situations to show speedups of the SCG evolution, that is the crucial overhead of the estimation.

Smart manufacturing utilizes digital twins (DTs) that are virtual forms of their production plants for optimizing decisions. Discrete-event models (DEMs) are frequently used to model the production dynamics of the plants. To accelerate the performance of the discrete-event simulations (DES), adaptive abstraction-level conversion (AAC) approaches were proposed to change specific subcomponents of the DEM with corresponding abstracted queuing models during the runtime based on the steady-state of the DEMs. However, the speedup and accuracy loss of the AAC-based simulations (ABS) are highly influenced by user-specified significance level α (degree of tolerance of statistical invariance between two samples) and the stability of the DEMs. In this paper, we proposed a simulation-based optimization (SBO) that optimizes the problem based on genetic algorithm (GA) while tuning the hyperparameter (α) during runtime to maximize the speedup of ABS under a specified accuracy constraint. For each population, the proposed method distributes the computing budget between the α exploration and fitness evaluation. A discrete-gradient-based method is proposed to estimate each individual’s initial α (close to the final optimum) using previous exploration results of neighboring individuals so that the closeness can reduce the iterative α exploration as GA converges. We also proposed a clean-up method that removes inferior results to improve the α estimation. The proposed method was applied to optimize raw-material releases of a large-scale manufacturing system to prove the concept and evaluate the performance under various situations.

In an agent-based simulation (ABS), a state update scheme carries out the transitions of agents from one state to the next. To produce correct simulation results, the update scheme must respect the cause-and-effect relationships defined by the agent-based model and ensure that the resulting overall simulation state is internally consistent. At the same time, the update scheme should be efficient enough to meet a simulationist's demand for timely results. Considering the common class of synchronous time-driven ABS, a number of update schemes have been employed in the literature and simulation frameworks. In this paper, various implementations of update schemes are analyzed and contrasted with respect to their ability to maintain the simulation correctness as well as their performance characteristics. A semantic model is formulated to define the reference behavior of synchronous time-driven ABS updates and model the dependencies among agent updates using a state access graph. Relying on the formalization, conditions under which different update schemes achieve causality are shown. Further, resolution methods are categorized according to their coordination mechanisms to achieve consistency by resolving conflicts among agent state updates. Through two case studies, the empirical performance of different update schemes and resolution methods are evaluated. For sequential execution, an update scheme based on the agent's dependencies achieves the highest performance, whereas in the parallel case, the choice of update scheme involves a tradeoff between execution time and memory usage. If deterministic simulation output is required, decentralized coordination generally outperforms centralized coordination. The results can assist implementers and researchers in their selection of appropriate methods in the design and implementation of agent-based simulators.

Closeness centrality is one of the key indicators for vertex importance in social network analytics. Since social networks are constantly growing, it is essential to monitor a vertex's closeness centrality through time in order to study its trend in influential power. In this paper, we model dynamic social networks as a time-evolving graph (a sequence of graph snapshots through time) and work on the problem of computing a vertex's closeness centrality for all graph snapshots.

We propose Distributed Neighbor Expansion (Distributed NE), a parallel and distributed graph partitioning method that can scale to trillion-edge graphs while providing high partitioning quality. Distributed NE is based on a new heuristic, called parallel expansion, where each partition is constructed in parallel by greedily expanding its edge set from a single vertex in such a way that the increase of the vertex cuts becomes local minimal. We theoretically prove that the proposed method has the upper bound in the partitioning quality. The empirical evaluation with various graphs shows that the proposed method produces higher-quality partitions than the state-of-the-art distributed graph partitioning algorithms. The performance evaluation shows that the space efficiency of the proposed method is an order-of-magnitude better than the existing algorithms, keeping its time efficiency comparable. As a result, Distributed NE can partition a trillion-edge graph using only 256 machines within 70 minutes.

Many real-world networks, including online social networks and communication networks, are commonly modeled as temporal graphs. Answering earliest-arrival queries in temporal graphs is one of the most fundamental studies with numerous applications, such as information diffusion and measuring temporal closeness centrality. As graph sizes are growing rapidly, speedup of query execution time becomes even more important.In this paper, we propose a novel edge-centric parallel algorithm for solving single-source earliest-arrival problem in temporal graphs based on a new data structure named Edge-Scan-Dependency Graph (ESD-Graph). We evaluate the proposed parallel algorithm by theoretical analysis as well as by empirical experiments on real-world temporal graphs and synthetic graphs. Empirical results show that the new parallel algorithm outperforms the existing serial algorithm by up to 8.2 and 9.5 times on multi-core processors for real-world data and synthetic data respectively.

Social contact network (SCN) models the contacts between people by their daily activities. It can be formalized by an agent-to-location bipartite graph. The simulations over SCN are employed to study the complex social dynamics such as information propagation and disease spread among large-scale population. A challenge to the simulation is the skewed degree distribution of SCN, which contains a few hub locations with large numbers of visitors. The skewed degree distribution can cause load imbalance for parallel simulation and greatly degrade the execution performance. This paper proposes an approach which decomposes hub locations into small splits. Thus, SCN can be partitioned with better balanced workloads and multiple splits are able to run in parallel. Based on the pattern of information transmission between agents, we duplicate necessary data among splits to ensure the correctness of simulation. Furthermore, we enhance the parallel algorithm of SCN simulation to reduce the additional overhead from communication between splits. Finally, we build an experiment with epidemic simulation on an open dataset. The experimental results demonstrate that our approach achieves 14~35% performance improvement compared with the partitioning method without decomposition of hub locations.

Due to globalization of economy, the supply chains are vulnerable to disruptive events. In addition, lean initiatives often lead to single supplier, which is vulnerable to supply disruption. In this paper, two strategies are proposed for generating supply chain networks to improve the resilience of supply chain networks: hierarchical preferential attachment and hierarchical random attachment. The supply chain resilience is evaluated using supply availability and the demand to supply ratio. Disruptions in the supply chain are modeled using random and targeted disruptions. The paper also designed an algorithm to recover the supply chain network from disruptions, based on the network attachment rules (preferential attachment and random attachment). Through a simulation study, the recovered supply chain is shown to have better resilience compared to a single supplier supply chain network.

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.

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.

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.

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.