导　　师： 王洋; 叶可江

授予学位： 硕士

作　　者： (）;

机构地区： 中国科学院深圳先进技术研究院

摘　　要： 在计算任务的执行过程中,为了提高执行效率,并且最小化执行开销,计算任务往往会被卸载到具有更多计算资源,I/O资源以及存储资源的设备上。在进行卸载之前,一个应用或者服务被抽象成为一个带权重的有向无环图,其中,一个图节点代表应用或者服务中的一个计算任务,节点之间的边代表了计算任务之间存在通信。目前的研究都旨在给定卸载策略算法,将该应用或者服务,也即图切分成两个部分,一部分保留在本地执行,一部分卸载到其他设备上执行,以达到优化执行效率,减小执行开销的目的。为了简化问题,当前的研究在进行抽象建模的时候,往往会忽略当两个计算任务位于同端时的通信代价,而只考虑当两个计算任务位于不同端时的跨端通信代价。此外,当前研究都忽略了跨端通信代价是非对称的。但是在边缘计算框架中,尤其是当前,在大多数应用服务都以微服务架构部署的时候,这些被忽略的条件都必须重新纳入模型。因为在边缘计算框架中,一个应用服务被拆分为多个松耦合的简单微服务,部署在由多台机器组成的多个集群中。不同于在同一个机器内通过共享内存进行高效通信,这些微服务之间的通讯需要跨越机器,更加复杂昂贵,导致通信代价不可忽略。而且,由于上下行带宽不一致,网络拥塞等原因,跨端通信代价并非对称。为此,本文提出了一个新的卸载模型:该模型不但考虑了计算任务位于同端时的通信代价,还考虑了当计算任务位于不同端时,跨端的通信代价非对称这一因素。我们证明在该卸载模型下求解最优卸载策略是一个NP难问题,并设计了一个简单有效的贪婪算法来求解次优卸载策略。此外,我们提出了一个简化的同构模型。基于同构模型,我们考虑了当跨端网络带宽对称时,如何求解任务卸载策略。通过将同构模型转化为一个最大流最小割问题,我们证明当跨端网络带宽对称时,存在最优任务卸载策略,并提出了一个最优算法。我们的实验数据显示,相比于当前研究采用的简化模型而得到的卸载策略,我们的算法给出的卸载策略能够减少更多计算任务的执行代价、通信代价,提高计算任务的执行效率。更多还原

关 键 词： [1282135]云计算 边缘计算 计算卸载 [100291612]NP-HARD MAX2-SAT

分 类 号： [TP3]

领　　域： []