片上网络实时应用调度与映射算法研究

摘要

随着半导体技术的不断发展，越来越多的核将被集成到同一块芯片中，以使处理器获得更高的计算能力同时降低整体功耗。传统的点对点和基于总线的通信机制并不能满足多核芯片内部的数据通信的迅速增长。片上网络通过网络将芯片内部的各个核连接起来并提供数据包交换服务，为核与核之间的数据通信提供更大的带宽。目前在大规模多核处理器中，片上网络已经成为一种得到广泛认可的通信解决方案。
　　片上网络实时通信集调度与多资源调度不同，由于片上网络的特殊结构，一个通信任务可能同时占用多个物理链路，导致物理链路的竞争。对于实时应用来说，目前的研究只能解决某些特定情况下的实时通信调度，缺乏通用性。针对片上网络的通信和自身的体系结构特点，本文提出全新的EPOGen调度算法，该算法在前序相关研究的基础上，为复杂的有环通信集提供了实时调度方案，因此能够解决各种类型通信集的实时调度问题。
　　由于片上网络体系结构的特点，应用的映射成为片上网络系统设计中一个关键步骤。如果任务被分配到不同的地点，通信的源点和目的点将随之改变。因此，任务与处理单元间不同的映射策略将影响通信的实时性。本文提出一个多项式映射算法RTMAP,该算法分为三步映射:初步映射、进一步映射和优化映射。该映射算法通过优化各通信间的关系，能够在最小化通信消耗的前提下，进一步增强了EPOGen算法对通信集调度的实时性。
　　实验结果表明，映射算法RTMAP不仅提高应用程序的实时性能，并且最小化通信成本。与经典算法FPA和NMAP相比，本文的算法EPOGen和RTMAP可以在很小的通信成本开销下显著提高应用的实时性。

目录

声明

摘要

第1章 绪论

1．1 课题背景

1．2 研究现状

1．3 本文工作

1．4 论文结构

第2章 相关技术介绍

2．1 片上网络

2．1．1 片上网络体系结构

2．1．2 片上网络关键技术

2．2 实时系统

2．2．1 实时任务概述

2．2．2 实时系统的特点

2．2．3 实时系统调度

2．4 本章小结

第3章 问题模型与无环通信调度背景

3．1 系统模型

3．2 问题描述

3．3 无环通信背景

3．3．1 有环通信环境

3．3．2 虚通道技术应用

3．4 本章小结

第4章 调度算法的设计与实现

4．1 调度问题描述

4．2 无环通信调度算法

4．2．1 实时通信和调度模型

4．2．2 POGen调度算法

4．3 有环调度算法描述

4．3．1 针对一个环的调度算法

4．3．2 针对多个环的调度算法

4．4 本章小结

第5章 映射算法的设计与实现

5．1 映射问题描述

5．2 映射算法描述

5．2．1 映射算法总体设计

5．2．2 HeuristicValue()函数设计与实现

5．2．3 Dijkstra()函数设计与实现

5．3 本章小结

第6章 实验设计与结果分析

6．1 实验基础

6．2 调度算法实验设计与结果分析

6．2．1 测试数据的生成

6．2．2 算法接收率对比与结果分析

6．3 映射算法实验设计与结果分析

6．3．1 测试数据的生成

6．3．2 影响因素maxu实验对比与结果分析

6．3．3 影响因素片上网络规模实验对比与结果分析

6．4 本章小结

第7章 结论与展望

7．1 结论

7．2 未来工作与展望

参考文献

致谢

科研项目和论文发表情况