All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into ...All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into two kinds: direct communication algorithm and indirect communication algorithm. The optimal direct all-to-all communication algorithm on rings and 2-D tori does exist. But, for indirect all-to-all communication algorithms, there is a gap between the time complexity of the already existing algorithm and the lower bound. In this paper an efficient indirect algorithm for all-to-all communication on rings and 2-D square tori with bidirection channels is presented. The algorithms is faster than any previous indirect algorithms. The main items of the time complexity of the algorithm is P2/8 and p3/2/8 on rings and 2-D tori respectively, both reaching the theoretical lower bound, where p is the number of processors.展开更多
Fast data synchronization in wireless ad hoc networks is a challenging and critical problem.It is fundamental for efficient information fusion,control and decision in distributed systems.Previously,distributed data sy...Fast data synchronization in wireless ad hoc networks is a challenging and critical problem.It is fundamental for efficient information fusion,control and decision in distributed systems.Previously,distributed data synchronization was mainly studied in the latency-tolerant distributed databases,or assuming the general model of wireless ad hoc networks.In this paper,we propose a pair of linear network coding(NC)and all-to-all broadcast based fast data synchronization algorithms for wireless ad hoc networks whose topology is under operator’s control.We consider both data block selection and transmitting node selection for exploiting the benefits of NC.Instead of using the store-and-forward protocol as in the conventional uncoded approach,a compute-and-forward protocol is used in our scheme,which improves the transmission efficiency.The performance of the proposed algorithms is studied under different values of network size,network connection degree,and per-hop packet error rate.Simulation results demonstrate that our algorithms significantly reduce the times slots used for data synchronization compared with the baseline that does not use NC.展开更多
全比较计算数据分发策略是提高分布式集群系统整体计算性能的关键。针对现有数据分发策略存在的计算负载不均衡、数据不能完全本地化、存储空间浪费和计算速度慢等弊端,在满足数据完全本地化的前提下以负载均衡、最优化存储作为优化目标...全比较计算数据分发策略是提高分布式集群系统整体计算性能的关键。针对现有数据分发策略存在的计算负载不均衡、数据不能完全本地化、存储空间浪费和计算速度慢等弊端,在满足数据完全本地化的前提下以负载均衡、最优化存储作为优化目标,结合优化的粒子群算法提出了数据分发模型(Data Distribution Based on Particle Swarm Optimization,DDBPSO)。DDBPSO模型分别以任务扰动、交换任务的方式对粒子进化规则进行了优化,有效避免了算法陷入局部最优。通过计算负载、存储占用和数据本地化等实验,结果表明,与开源框架Hadoop的数据分发策略相比,提出的DDBPSO模型与算法具有计算负载均衡、完全的数据本地化、存储空间占用小、计算速度快等优势。展开更多
基金the Ph.D. Research Foundation The Ministry of Education, China (No.9703825).
文摘All-to-All personalized communication is a basic communication operation in a parallel computing environment. There are a lot of results appearing in literature. All these communication algorithms can be divided into two kinds: direct communication algorithm and indirect communication algorithm. The optimal direct all-to-all communication algorithm on rings and 2-D tori does exist. But, for indirect all-to-all communication algorithms, there is a gap between the time complexity of the already existing algorithm and the lower bound. In this paper an efficient indirect algorithm for all-to-all communication on rings and 2-D square tori with bidirection channels is presented. The algorithms is faster than any previous indirect algorithms. The main items of the time complexity of the algorithm is P2/8 and p3/2/8 on rings and 2-D tori respectively, both reaching the theoretical lower bound, where p is the number of processors.
基金This work is financially supported by Beijing Municipal Natural Science Foundation(No.L202012)the Open Research Project of the State Key Laboratory of Media Convergence and Communication,Communication University of China(No.SKLMCC2020KF008)the Fundamental Research Funds for the Central Universities(No.2020RC05).
文摘Fast data synchronization in wireless ad hoc networks is a challenging and critical problem.It is fundamental for efficient information fusion,control and decision in distributed systems.Previously,distributed data synchronization was mainly studied in the latency-tolerant distributed databases,or assuming the general model of wireless ad hoc networks.In this paper,we propose a pair of linear network coding(NC)and all-to-all broadcast based fast data synchronization algorithms for wireless ad hoc networks whose topology is under operator’s control.We consider both data block selection and transmitting node selection for exploiting the benefits of NC.Instead of using the store-and-forward protocol as in the conventional uncoded approach,a compute-and-forward protocol is used in our scheme,which improves the transmission efficiency.The performance of the proposed algorithms is studied under different values of network size,network connection degree,and per-hop packet error rate.Simulation results demonstrate that our algorithms significantly reduce the times slots used for data synchronization compared with the baseline that does not use NC.
文摘全比较计算数据分发策略是提高分布式集群系统整体计算性能的关键。针对现有数据分发策略存在的计算负载不均衡、数据不能完全本地化、存储空间浪费和计算速度慢等弊端,在满足数据完全本地化的前提下以负载均衡、最优化存储作为优化目标,结合优化的粒子群算法提出了数据分发模型(Data Distribution Based on Particle Swarm Optimization,DDBPSO)。DDBPSO模型分别以任务扰动、交换任务的方式对粒子进化规则进行了优化,有效避免了算法陷入局部最优。通过计算负载、存储占用和数据本地化等实验,结果表明,与开源框架Hadoop的数据分发策略相比,提出的DDBPSO模型与算法具有计算负载均衡、完全的数据本地化、存储空间占用小、计算速度快等优势。
