Distributed spatial simulations commonly employ Bulk Synchronous Parallel model (BSP) implementation. However, implementations using BSP are usually fraught with the straggler problem, where the delay of any worker sl...
详细信息
ISBN:
(纸本)9781450354905
Distributed spatial simulations commonly employ Bulk Synchronous Parallel model (BSP) implementation. However, implementations using BSP are usually fraught with the straggler problem, where the delay of any worker slows down the entire system. Random stragglers commonly occur due to many reasons: imbalanced workload, operating system scheduling, or communication delays. The straggler problem is further exasperated with increasing parallelism. To reduce the straggler problem and preserve simplicity and scalability advantages of the BSP model, we propose a new parallel model, which we call Priority Asynchronous Parallel (PAP) model. PAP exploits data dependencies of parallel processes to be computed and synchronized based on data priority to the other workers. For further computational improvement, we develop a load balancing and partitioning method, called GridGraph that utilizes the spatial and connectivity properties of the simulation space to reduce the size of exchanged data in addition to balancing the workload among workers. The proposed schemes are implemented and evaluated in a microscopic traffic simulator. Running traffic simulation for Melbourne, Beijing, and New York cities on 80 workers, the simulation achieves a performance speedup of around 47.4% for Melbourne, 52.18% for Beijing, and 65.84% for New York, using PAP model combined with GridGraph partitioning compared to BSP model.
This paper introduces a parallel computing framework based on the Spectral partitioning (SP) method designed to enhance the computational efficiency of large-scale microscopic traffic simulation (LSMTS). The framework...
详细信息
This paper introduces a parallel computing framework based on the Spectral partitioning (SP) method designed to enhance the computational efficiency of large-scale microscopic traffic simulation (LSMTS). The framework employs the SP method to partition roadnetworks, taking into account vehicle information and road information as constitutive components for node weight determination. Micro-simulation relies on vehicle information from both preceding and following vehicles to accurately infer the operational states of a vehicle. However, networkpartitioning can disrupt the flow of vehicle information, resulting in its loss. To address this, the proposed framework incorporates a boundary transmission method to ensure simulation accuracy and precision. This study presents an improved SP (iSP) method tailored for LSMTS, further enhancing the partitioning results achieved through the SP method. Lastly, the framework's validity is confirmed through roadnetwork experiments of varying scales and densities, with comparisons made to existing parallel simulation methods. The results demonstrate that the framework significantly reduces the execution time of simulation tasks while maintaining a high level of load balance and minimizing communication overhead.
Driven by our work on a large-scale distributed microscopic road traffic simulator, we present ENHANCE, a novel re-partitioning approach that allows incorporating fine-grained simulator-specific cost models into the p...
详细信息
Driven by our work on a large-scale distributed microscopic road traffic simulator, we present ENHANCE, a novel re-partitioning approach that allows incorporating fine-grained simulator-specific cost models into the partitioning process to account for the actual performance characteristics of the *** use of explicit cost models enables partitioning for heterogeneous resources, which are a common occurrence in cloud deployments. Importantly, ENHANCE can be used in conjunction with other partitioning approaches by further enhancing partitions according to provided cost models. We demonstrate the benefits of our approach in an experimental evaluation showing performance improvements of up to 29% against METIS under heterogeneous conditions. Taking a different perspective, the partitioning produced by ENHANCE can provide similar performance as METIS, but using up to 20% fewer resources.
暂无评论