The number of threads in the thread pool is a critical factor that significantly influences the efficiency of parallel execution in Parallel Discrete Event Simulation (PDES). However, current methodologies, including such as static configuration, iterative search, solution based on system state information, and machine learning primarily cater to the domain of parallel computing. These approaches fail to consider PDES-specific characteristics like logical clock synchronization and the interaction among various simulation parameters, thereby posing challenges in accurately predicting the optimal number of threads required for achieving peak performance in PDES. In response to this, this paper proposes an adaptive multivariate power coefficient probability prediction method that considers the interrelated parameters in PDES which collectively influence runtime behavior. The method models various factors affecting PDES efficiency as multivariate power coefficients, incorporating a probability model and bias term to capture the variability of the simulation system. It constructs a nonlinear correlation model between the number of threads and simulation speedup, and derives the number of threads by calculating the optimal speedup of PDES. Experimental results demonstrate that this method achieves an average relative error of 6.4% in predicting the optimal number of threads, with performance improvement achieved by utilizing these predicted threads reaching 93.28% compared to ideal performance improvement relative to serial execution.

The large-scale Multi-Agent Path Finding (MAPF) problem presents a significant challenge in combinatorial optimization. Currently, one of the advanced, near-optimal algorithms is Large Neighborhood Search (LNS), which can handle instances with thousands of agents. Although a basic portfolio parallel search based on multiple independent LNS solvers enhances speed and robustness, it encounters scalability issues with increasing CPU cores. To address this limitation, we propose the Cooperative Parallel LNS (CPLNS) algorithm, aimed at boosting parallel efficiency. The main challenge in cooperative parallel search lies in designing suitable portfolio and cooperative strategies that balance search diversification and intensification. To address this, we first analyze the characteristics of LNS. We then introduce a flexible group-based cooperative parallel strategy, where the current best solution is shared within each group to aid intensification, while maintaining diversification through independent group computations. Furthermore, we augment search diversification by integrating a simulated annealing-based LNS and bounded suboptimal single-agent pathfinding. We also introduce a rule-based methodology for portfolio construction to simplify parameter settings and improve search efficiency. Finally, we enhance communication and memory efficiency through a shared data filtering technique and optimized data structures. In benchmarks on 33 maps with 825 instances, CPLNS achieved a median speedup of 21.95 on a 32-core machine, solving 96.97% of cases within five minutes and reducing the average suboptimality score from 1.728 to 1.456. Additionally, tests with up to 10,000 agents verify CPLNS's scalability for large-scale MAPF problems.

Interest management is a filtering technique to reduce communication in simulation. It involves a process called "interest matching" to identify intersections between two sets of d-dimensional axis-parallel rectangles. Because of frequent demands in simulation execution, interest matching becomes a bottleneck as the problem size grows. However, classical interest matching algorithms, mainly designed for serial processing, do not take advantage of modern multicore processors' computing power. Recent parallel interest matching algorithms can fill the gap, but there is scope for improvement. In this paper, we propose a parallel hierarchical sort-based interest matching algorithm. It embeds subscription regions into an interest management tree and allows update regions compare with nodes of the tree to find results in parallel. The association between adjacent nodes and the hierarchical relation between parent-child nodes can serve to eliminate unnecessary operations. Moreover, we also provide proof to confirm the correctness and a detailed analysis of time-complexity. The experimental results demonstrate that the proposed algorithm can achieve better performance than state-of-art algorithms.

In distributed simulation, communication based on publish/subscribe will generate large amount of irrelevant data transmissions, and thereby degrading the performance. To solve the problem, HLA standard defines data distribution management to filter unnecessary communication. Among several famous interest matching algorithms, the sort-based algorithm has been proven to be the most efficient method in most scenarios. However, the potential of existing sort-based algorithm has not been fully exploited, due to the overhead of sorting the bounds can be further reduced and a portion of unnecessary bit operations can be eliminated. In this paper, we propose a binary search enhanced sort-based interest matching algorithm (BSSIM). Based on a different sufficient and necessary condition to judge interval overlapping, the size of list to be sorted can be remarkably reduced. Moreover, unnecessary bit operations can be eliminated by binary searches. Experimental results show that BSSIM algorithm outperforms the sort-based algorithm, and approximately 64%-159% performance improvement can be achieved at different scenarios.

Individual authentication in air warfare is used to check whether a single participant is a legal member of the predefined group but not determine all participants at one time. An asynchronous (m, t, n) group authentication protocol is proposed based on multidimensional sphere reconstruction theorem of space analytic geometry without making any computational assumption, where m is the number of participants, t is threshold value, and n is the number of members. The proposed protocol can determine whether all participants belong to the predefined group at one time, which is applicable to batch verification prior to individual authentication. The center’s coordinate of (t-1) -dimensional sphere is treated as the shared secret and the coordinate of the point on the surface of the sphere, multiplied by a random blind factor, is issued to all members as their tokens. If m participants can reconstruct the shared secret by utilizing their tokens, indicate that there is not any invalid participant, otherwise perform individual authentication. Analyses show the proposed scheme can not only rule out the illegal outsider but also resist up to t-1 group member conspiring to forge a valid token for an outsider. In addition, compared with other schemes the proposed scheme is more applicable for air warfare network, with light-weight computation, flexible distribution, and high information rate.

The widespread utilization of many-core processors offers a good opportunity for Parallel Discrete Events Simulation (PDES) to obtain a better execution performance. As one of the newly introduced many-core processors, the Intel Xeon Phi coprocessor based on Many Integrated Core (MIC) architecture integrates about 60 optimized x86 cores within a PCB board, reaching a peak performance of 1.0 TFLOPS. Furthermore, benefiting from using x86 architecture cores, the MIC coprocessor is fully compatible with almost all programs designed for general purpose CPUs, which makes it easy to run simulation progress on MIC. There have been many works on performance evaluation and optimization of PDES simulator using Graphic Processing Unit (GPU) or Tilera or other many-core processors, yet almost no related works on Phi are published until now. In this article, an early performance evaluation of the well-known PDES simulator ROSS and its POSIX thread version ROSS-MT was conducted based on a computing node composed of two Intel Xeon multi-core CPUs and one Phi coprocessor, using the classical PDES benchmark PHOLD and its extended version by adding different event granularities. Experiment results show that the pure MPI based ROSS performs poorly on MIC coprocessor, indicating that it would not be feasible for common PDES applications. Though ROSS-MT has a much better performance on MIC, the computation potential of MIC is still hardly fully explored. Furthermore, with the event granularity becomes larger, performance of this benchmark exhibits a "fall of cliff", which turns it into a computation dominant application. However, the entire performance on MIC coprocessor is still worse than that on host. After reasoning the problems, we vectorized the code of event handler to better use the Vector Processing Unit (VPU) of MIC coprocessor, which brings us a peak speedup of 9.7X, showing that MIC coprocessor is able to find its place in the PDES field. At last, according to our evaluation work, we provide some advices to further exploit the power of MIC coprocessor for PDES applications.

The graphic processing unit (GPU) brings an opportunity to implement large scale simulations in an economical way. GPU's performance relies on high parallelism, but using synchronous conservative time management algorithm for discrete event simulation will meet the scenarios with limited parallelism. This conflict leads to bad performance even though the application itself has high parallelism. To solve this problem, we propose an expansion-aided synchronous conservative time management algorithm. It uses runtime information to enlarge the time bound of "safe" events, and uses an expansion method to import "safe" events. By interleaving a series of expansions with event computation, more events can be assembled to be processed in parallel. Moreover, a simulated annealing algorithm is adopted to control the number of expansions. It helps achieve stable performance under different conditions by finding a balance between low parallelism and unnecessary expansions. Experiments demonstrate that the proposed algorithm can achieve up to a 30% performance improvement.