基于Pi演算的分布式多Agent异构调度算法的研究与实现

发布时间：2023-07-01 11:16

　　任务调度问题是分布式计算领域的核心问题之一,它不仅可以有效地提高计算能力,同时可以保证应用程序合理有效地运行,直接影响整个分布式计算环境的整体性能。由于调度问题是NP难问题,如何提高调度算法的效率一直是众多学者的研究方向之一。分布式计算系统又可分为同构型和异构型两种。随着计算机网络和计算机系统的发展,同构性是相对的,而异构性是绝对的,不可避免的。考虑到异构型分布式计算系统的绝对性和更具普遍性,以及静态调度算法是目前学者们研究最多的一类,本文选择静态异构调度算法进行研究。在静态异构调度算法中,HEFT算法是调度长度和鲁棒性较好的一个经典算法。目前实现任务调度算法的底层模型本质上大多还是串行模型,而Pi演算作为一个成熟的并行模型,支持通道名的传输,可以方便地实现复杂的通信系统结构的变化,非常适合与分布式任务调度相结合。面向Agent技术的合作性、代理性、智能性、持续性、学习性使其非常适合分布式任务调度的实现。本文将Pi演算的思想和多Agent技术结合应用到HEFT算法,不仅利用pi演算并行计算的特性,可利用通道传递信息,并结合多Agent技术进一步提高并行性,提出了基于Pi演算的分布式多A...

【文章页数】：63 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 引言
    1.1 研究背景
    1.2 国内外研究现状
    1.3 研究意义
    1.4 主要工作
    1.5 论文组织结构
第2章 相关理论概述
    2.1 Pi演算简介
        2.1.1 Pi演算的语法
        2.1.2 Pi演算的等价规则和迁移规则
    2.2 多Agent技术概述
    2.3 HEFT算法相关理论
        2.3.1 DAG图
        2.3.2 HEFT算法过程
    2.4 本章小结
第3章 对HEFT算法建模
    3.1 Pi演算中的表编程
        3.1.1 表结构
        3.1.2 表编程
    3.2 对HEFT算法建模
        3.2.1 任务节点分层
        3.2.2 建模所需数据结构
        3.2.3 建模过程
    3.3 形式化验证
    3.4 本章小结
第4章 使用Nomadic Pict对模型编程实现
    4.1 Nomadic Pict介绍
        4.1.1 Nomadic Pict的框架与结构
        4.1.2 Nomadic Pict和 Pi演算的对应关系
    4.2 扩展Nomadic Pict
    4.3 对模型编程实现
        4.3.1 算法流程
        4.3.2 具体实现
    4.4 本章小结
第5章 实验结果分析与对比
    5.1 实验环境及相关准备
    5.2 HEFT算法实验结果对比分析(一)
        5.2.1 宽度优先对比
        5.2.2 深度优先对比
        5.2.3 计算Agent数量不同时的执行时间对比
    5.3 HEFT算法实验结果对比分析(二)
    5.4 本章小结
第6章 总结与展望
    6.1 本文工作总结
    6.2 未来工作展望
参考文献
作者简介及在学期间所获得的科研成果
致谢



本文编号：3836152