片上网络有环通信集的实时调度研究

发布时间：2018-01-15 10:02

本文关键词：片上网络有环通信集的实时调度研究　出处：《东北大学》2012年硕士论文　论文类型：学位论文

【摘要】：传统的依靠提升处理器频率来获得高计算性能的方法已接近极限,已不能满足人们对高计算性能的要求,所以多核成为新的发展方向。而随着处理核心的增多,传统的总线通信架构成为影响系统性能提升的瓶颈,所以片上网络(Network-on-Chip)应运而生。片上网络让不同任务可以进行并行通信,极大提升了系统的通信效率。然而当任务间通信十分频繁时,仍会发生对通信资源的争用,特别在实时系统中对任务的完成时间有严格限定,通信资源的争用会导致实时任务完成时间的不确定性增加,所以需要对运行在在片上网络的实时系统的通信进行研究来解决这一问题。由于存在计算和通信的双重并行性,所以将实时系统应用于NoC(Network-on-Chip)需要一个新的理论框架。与传统的实时系统不同,片上网络结构的多核SoC(System-on-Chip)对实时通信任务集进行调度并使片上网络的利用率最大化是一个新的挑战。尽管和多资源调度有类似的形式,片上网络实时通信集调度有其不同之处。因为一个通信任务可能同时多个物理链路,面临物理链路的竞争。以往对片上网络实时通信的研究大都集中在对无环通信任务集可调度性分析,而很少有对有环通信任务集的研究,然而实际应用中有环通信任务集是普遍存在的。通信任务集的环是指片上网络中的通信任务的路由路径相互叠加而形成的环路。本论文中针对有环的通信任务集提出了两种调度算法：基于虚通道的实时调度算法(CS-VC)和基于时间隔离的实时调度算法(CS-TI),并给出了通信任务集用这两种算法可调度的通信任务集利用率界限(也是通信任务集可调度的充分条件)。实验部分将CS-VC和CS-TI与目前最好的有环通信任务集实时调度算法FPA (Fixed Priority Algorithm)进行了比较,实验结果表明CS-VC和CS-TI有更高的接收率,并且当通信任务集和片上网络规模越小时,CS-VC和CS-TI的接收率越高。CS-TI与CS-VC相比虽然接收率较低,但CS-TI无需额外的片上网络结构作为支持更便于实现。
[Abstract]:The traditional method of improving processor frequency to achieve high computing performance is approaching the limit, which can not meet the requirements of high computing performance, so multi-core has become a new direction of development, and with the increase of processing cores. Traditional bus communication architecture has become the bottleneck to improve the performance of the system, so Network-on-Chip emerges as the times require. The on-chip network allows different tasks to communicate in parallel. The communication efficiency of the system is greatly improved. However, when the communication between tasks is very frequent, there will still be contention for communication resources, especially in real-time systems, the completion time of tasks is strictly limited. The contention of communication resources will lead to the uncertainty of the completion time of real-time task, so it is necessary to study the communication of real-time system running in on-chip network to solve this problem. Due to the dual parallelism of computing and communication, the application of real-time systems to NoCU Network-on-Chip requires a new theoretical framework, which is different from the traditional real-time systems. Multi-core SoCn System-on-Chip with on-Chip Network structure. Scheduling real-time communication task sets and maximizing the utilization of on-chip networks is a new challenge, although it has a similar form to multi-resource scheduling. The scheduling of real-time communication set in on-chip network has its differences, because a communication task may have multiple physical links at the same time, so it faces the competition of physical links. In the past, the research of real-time communication in on-chip network mostly focused on the schedulability analysis of the task set of acyclic communication, but there was little research on the task set of ring communication. However, in practical applications, ring communication task sets are ubiquitous, and the ring of communication task set refers to the loop formed by the superposition of the routing paths of communication tasks in the on-chip network. In this paper, we propose two scheduling algorithms for the cyclic communication task set: virtual channel based real-time scheduling algorithm (CS-VC) and time isolation based real-time scheduling algorithm (CS-TI). The limit of the utilization ratio of the communication task set is given, which is also a sufficient condition for the schedulability of the communication task set. In the experiment part, CS-VC and CS-TI are compared with FPA fixed Priority algorithm, which is the best real-time scheduling algorithm for ring communication task set. A comparison was made. The experimental results show that CS-VC and CS-TI have higher reception rate, and when the communication task set and on-chip network scale is smaller. The higher the receiving rate of CS-VC and CS-TI is, the lower the receiving rate of CS-TI is compared with that of CS-VC, but it is easier to implement CS-TI without additional on-chip network structure.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP332;TN47

【参考文献】