APP下载

网络断路感知的同步机制*

2019-02-13项哲慧秦小麟

计算机与生活 2019年2期
关键词:效率结构

项哲慧,秦小麟+,犹 锋,刘 亮

1.南京航空航天大学 计算机科学与技术学院,南京 210016

2.南瑞集团有限公司,南京 210003

1 引言

近年来随着数据规模的增大,优化各种大数据处理平台的性能已成为研究的热点。图计算平台Pregel[1]和Giraph[2]等基于并行计算加快图数据的处理,它们采用BSP[3]编程模型作为并行算法的基础框架。Barrier(栅栏)同步是并行计算常采用的一种同步方法,用于BSP的两个超步(super-step)之间的同步。一个线程调用Barrier意味着该线程需要在该点等待所有线程到达,控制线程的执行进度确保并行计算的正确性。在并行最小生成树算法中[4],对多个连通分量进行合并需要先统计所有连通分量选择的边,再确定该边是否同时被两个连通分量选中,进而合并连通分量。因此线程在计算完连通分量选择的边之后需要同步,否则会出现先计算完的线程无法判断边是否同时被两个分量选中,因为选择该边的另一个连通分量可能由其他线程处理。可见Barrier同步是保证并行计算正确性不可或缺的部分,它的效率直接影响并行计算的性能。

并行计算有两种计算结构:共享内存结构和消息传递结构。后者在大数据处理平台中更常见,如Pregel,Giraph的Barrier同步机制是通过消息传递实现线程之间的同步的。然而在网络中,消息过量、消息重发以及消息的输入速率超过输出速率[5-6]等原因都能造成网络拥堵或者网络断路。而现有的Barrier算法在遇到网络拥堵或者网络断路时只能等待或者选择一条更远的路由传递消息,降低了同步算法的效率。……

登录APP查看全文

猜你喜欢

效率结构
《形而上学》△卷的结构和位置
提升朗读教学效率的几点思考
注意实验拓展,提高复习效率
论结构
新型平衡块结构的应用
效率的价值
论《日出》的结构
跟踪导练(一)2
创新治理结构促进中小企业持续成长
“钱”、“事”脱节效率低