面向编码MapReduce的通信有效计算负载调度研究

发布时间：2020-12-09 04:28

　　近年来,边缘计算已经成为了下一代网络研究中最为瞩目的技术亮点,边缘计算为许多诸如虚拟现实,自动驾驶,深度学习等新兴的计算密集型应用提供了强有力的计算力保证。这些新型的计算应用的发展也对计算性能提出更高的要求。MapReduce是一种专门为大规模并行数据处理设计的分布式计算框架。在边缘计算中通常可以采用MapReduce框架在多个边缘服务器上分布式处理各种类型的计算任务。更进一步,编码MapReduce框架利用编码技术与冗余计算资源通过调整计算负载可以对服务器之间的通信负载进行优化。随着近些年计算应用对于低时延的需求日益强烈。边缘服务器之间的大量通信负载成为提高计算性能的瓶颈,并且边缘计算资源具有时变特征。如何通过计算负载调度充分利用动态变化的冗余计算资源来提高计算性能,如何对边缘服务器之间通信负载进行优化。以此为动机,本文开展了对面向编码MapReduce的通信有效计算负载调度的研究。首先,本文研究了单任务场景下通信有效计算负载调度算法。对于可以预先获知整个时间范围内可用计算资源状态的离线情况,将通信负载的调度算法转化为优化问题,利用最优性条件对计算重复因子和计算任务量进行解耦,将联合... 

【文章来源】：浙江大学浙江省 211工程院校 985工程院校 教育部直属院校

【文章页数】：86 页

【学位级别】：硕士

【部分图文】：

图１．１?ＭａｐＲｅｄｕｃｅ框架基本执行流程［ｓ］??

?丨?＿ｉｉ?ｗｍ??图１．１?ＭａｐＲｅｄｕｃｅ框架基本执行流程［ｓ］??码ＭａｐＲｅｄｕｃｅ框架中，将编码技术的应用扩展到边缘计算中来，通过编码减少Ｓｈｕｆｆｌｅ阶段??的通信负载，提高边缘计算的整体性能。??编码ＭａｐＲｅｄｕｃｅ通过建立计算负载与通信负载之间的关系，证明可以通过增加计算负??载以减少Ｓｈｕｆｆｌｅ阶段的通信负载。编码ＭａｐＲｅｄｕｃｅ利用不同计算节点上相同数据块的重复??计算，以实现编码。更具体地说，对于具有Ｋ个计算节点的服务器群集，通过多播ＬＡＮ网??络互连，计算任务共有＜５个输入文件，Ｂ个Ｒｅｄｕｃｅ函数。编码ＭａｐＲｅｄｕｃｅ提出了一种特定??的策略来分配Ｍａｐ任务，可以对计算节点上每个数据块进行ｉ？次重复计算，并在Ｓｈｕｆｆｌｅ阶??段进行编码可以大幅减少Ｓｈｕｆｆｌｅ阶段的通信负载，具体实例可以参考如图１．２所示。??在图１．２中

□??引理２?（定理２注解）．我们发现在定理２中的计算负载调度算法与注水算法有异曲同工之??妙。如图２Ｊ所示，Ａ是与＾相交的解平面，是它直接决定了调度方案，因为所有注??入的水Ｓ⑷的总量满足⑴Ｃ，＋?｝?＝?Ｍ，所以我们可以通过调整Ａ来??调整水平面以满足最终水量的和为Ｍ达到最优性。此时与最优解平面Ａ＊与＾相交的结果??便是最优调度算法。??２．４在线计算负载调度算法??在本节中，我们基于上一节的离线最优计算负载调度算法希望可以可在在线场景中得??到相应的解决方案。利用竞争分析方法，我们得到任意在线调度算法的竞争比下界，并且??１６??


本文编号：2906271