基于多核处理平台上的任务调度与共享缓存分配策略研究

摘要

传统提高单核处理器性能的方法主要是通过提高时钟频率的方式来实现的。随着大规模计算应用以及复杂应用对处理器的计算能力、存储系统设计等方面需求的大幅度提升，单核处理器能耗与热处理等问题更加难以解决，单纯依靠提高时钟频率来提升处理器性能的方法已不能满足这样的需求。多核处理器的结构是在同一个芯片上整合两个或者更多个处理器内核。多核处理器在低功耗、可靠性以及安全性设计方面都有着很大的优势，因此，多核处理器的应用范围越来越广泛。但是，多核处理器结构的特殊性也为复杂应用的调度以及共享缓存的设计带来了巨大的挑战。
　　多核处理器的调度比单核处理器的调度复杂得多，多核处理器的调度将任务分配到不同的处理器内核上执行，并在满足整个应用系统的性能、功耗等方面约束的前提下，最优化执行时间。当前的主流多核处理器大多采用共享缓存结构，但并行应用间的冲突访问会降低系统的性能。为了解决这些问题，本文对多核平台上的任务调度与共享缓存分配算法进行了研究。
　　针对多核处理平台上分时任务的调度问题，提出了一种基于任务图模型的分时任务调度策略。对于任务图的空间并行调度模型，采用并行节点合并、分配的算法进行优化;对于时间并行调度模型，进行了流水线并行的优化设计方法。之后，我们将优化的空间与时间并行调度模型结合到同一框架内对任务进行调度。实验结果表明，本文提出的基于任务图模型的分时任务调度算法可以有效地降低处理器内核间的通信与同步开销，提高了系统的计算效率与吞吐率。
　　针对多核处理平台上实时任务的调度问题，提出了基于时限驱动系统的全局预留调度算法。本文重点分析了常量利用率服务器算法，并对该算法进行了改进设计。新的服务器预留算法能够更高效地对实时任务进行截止期划分、处理器预算分配，以及迁移时机的选择。在此基础上，设计了基于时限驱动的全局预留调度算法，该算法为实时任务保护处理器的绝对带宽，从而确保了实时任务能够在截止期之前完成。实验结果表明，提出的多核实时调度算法能够很好地保障任务的实时性与系统的稳定性。此外，本文讨论了在新的调度算法环境下处理器内核的分配问题，并提出了处理器内核的分配策略，使得每个处理器内核的利用率与响应时间接近整个多核处理器的利用率与响应时间的平均值，从而很好地解决了负载平衡问题，优化了系统性能。
　　针对并行应用竞争共享缓存所导致的系统性能下降的问题，提出了基于多核处理平台上的共享缓存分配算法。将应用访存失效的情况分为局部错失访问与全局错失访问，建立一个能够鉴别并统计不同类型失效访问的监测机制。重点分析了并行应用获取或损失缓存资源时系统性能的增减情况，建立了性能评价模型。基于监测机制收集的访存失效信息与性能评价模型的收益函数，我们可以高效地选择出共享缓存的最优分配方式。实验结果表明，本文提出的基于多核处理平台的共享缓存分配算法，能够为并行应用合理地分配共享缓存资源，有效地降低冲突访问的频率，提高系统的计算效率。

目录

声明

摘要

第1章 绪论

1．1 多核处理技术背景

1．1．1 多核处理器的发展

1．1．2 多核处理器架构

1．1．3 多核处理器的典型结构

1．2 多核处理平台上的任务调度

1．2．1 多核处理平台上的分时任务调度

1．2．2 多核处理平台上的实时任务调度

1．3 多核处理平台上缓存的划分

1．4 本文的主要工作

1．5 论文的组织结构

第2章 多核平台上任务调度与共享缓存划分问题分析

2．1 多核处理平台上的调度问题分析

2．1．1 静态调度

2．1．2 动态调度

2．1．3 实时任务调度

2．2 多核处理平台的共享缓存划分问题分析

2．2．1 共享缓存划分的必要性

2．2．2 共享缓存划分方法

2．2．3 共享缓存的性能分析模型

2．3 本章小结

第3章 多核处理平台上基于任务图的分时任务调度方法研究

3．1 研究现状

3．2 多核分时任务调度算法设计

3．2．1 任务图调度模型的建立

3．2．2 多核平台上空间与时间并行结合的思想

3．2．3 时间并行的优化方法

3．2．4 并行调度算法框架设计

3．3 多核平台基于任务图的空间并行优化算法

3．3．1 多核平台空间并行调度模型

3．3．2 多核平台空间并行优化调度算法描述

3．4 多核平台时间并行优化调度算法

3．5 空间与时间并行结合的调度算法设计

3．6．实验结果与分析

3．6．1 流水线并行的性能测试

3．6．2 数据并行优化的性能比较

3．6．3 流水线并行优化的性能比较

3．6．4 不同算法的性能测试

3．7 本章小结

第4章 多核处理平台的实时任务调度方法研究

4．1 研究现状

4．2 多核平台的处理器预留算法

4．2．1 处理器预留算法模型

4．2．2 常量利用率服务器算法

4．2．3 处理器预留算法改进设计

4．3 多核平台上实时任务调度

4．3．1 基于时限驱动的全局预留调度算法设计

4．3．2 处理器内核分配问题

4．4 实验结果与分析

4．4．1 多核平台上实时任务集的可调度率

4．4．2 多核平台软实时系统测试

4．5 本章小结

第5章 多核处理平台上共享缓存的分配方法研究

5．1 研究现状

5．2 共享缓存的错失监测方法研究

5．3 共享缓存分配性能评价模型设计

5．4 共享缓存分配算法描述

5．5 实验结果与分析

5．5．1 检索数组长度选取

5．5．2 硬件开销分析

5．5．3 不同缓存容量的性能测试

5．5．4 几种共享缓存分配算法的性能比较

5．6 本章小结

第6章 总结与展望

6．1 论文的总结

6．2 论文的主要贡献

6．3 进一步的工作

参考文献

致谢

攻读博士学位期间的主要成果