多核处理器的任务映射与通信路由算法研究

发布时间：2018-01-02 17:28

本文关键词：多核处理器的任务映射与通信路由算法研究　出处：《复旦大学》2012年硕士论文　论文类型：学位论文

【摘要】：随着半导体技术的发展,越来越多的IP核被集成到一个单芯片上,然而各个IP核之间的互连成为了制约芯片性能提高的主要瓶颈。近几年提出的片上网络能够很好地实现各个IP核之间的并行通信,具有高性能和低功耗两大优势,并且由于其具有很好的可扩展性和可重用性,已经成为近几年业界和学术界研究的重点。然而,在硬件发展的同时,如何将应用程序映射到片上网络的硬件并使其能够高效地运行又具有低功耗的特点,成为了制约片上网络性能发挥的难点。本文致力于片上网络软件编译器的设计,提出了本项目组编译器的设计思路,实现应用程序在片上网络的高效运行。重点介绍了编译器设计中的任务映射和路由算法两部分。任务映射中,在深入研究分支限界算法的基础上进行优化,提出了任务绑定的思想。任务映射的目标在于减少整个NoC网络节点之间的通信功耗。为了降低搜索空间,本文将通信量大的任务通信对绑定,一起映射到相邻的NoC网络节点上,显著地提高了任务映射的效率。实验表明,优化的算法可以在更短的时间为多核系统找到性能相当的映射方案。例如,当映射25个任务到5×5的NoC系统时,只用传统算法的26.3%的时间就可以找到性能相同的映射方案。路由算法中,在分析传统路由算法的基础上,提出了通信通道时分复用的思想,减小了对NoC系统的带宽的需求。在对通信请求进行硬件资源分配和回收时,引入了被广泛用于操作系统的银行家的算法。在对通信请求寻找最短路径时,引入了迷宫算法。同时,当存在多条通信路径时,用了尽量靠近NoC网络边缘、中心和随机三种规则进行选择。实验结果表明,考虑了通信通道时分复用后的路由算法相对于传统的路由算法对NoC系统的带宽需求大大降低。同时,当存在多条通信路径时,尽量选择靠近NoC系统边缘的做法更有利于减少通信网络的阻塞。
[Abstract]:With the development of semiconductor technology, more and more IP cores are integrated into a single chip, however, the connection of each IP core has become the bottleneck of improving the system performance. The network proposed in recent years on chip can realize parallel communication between each IP core, with high performance and low power consumption two major advantages, and because it has good scalability and reusability, has in recent years become the focus of the industry and academia. However, in the hardware development at the same time, how the application is mapped to the network on chip hardware and its characteristics can run efficiently and with low power consumption that has become the key to play on the network performance constraints.
This paper is devoted to the design of the software compiler on the network on chip. The design idea of the project group compiler is put forward to achieve the efficient operation of the application on the chip network. The two parts of the task mapping and routing algorithm in the compiler design are mainly introduced.
Task mapping, optimization based on in-depth study of the branch and bound algorithm, put forward the task of binding thoughts. The goal is to reduce the task of mapping between the NoC power communication network nodes. In order to reduce the search space, the task of large communication to bind together, mapped to the network node on the adjacent NoC, significantly improve the efficiency of task mapping. Experiments show that the algorithm can find the optimal mapping scheme of equivalent performance in a shorter time for multi-core system. For example, when mapping 25 tasks to the NoC system of 5 * 5, only 26.3% of the time of the traditional algorithm can find the mapping scheme for the same performance.
The routing algorithm, based on the analysis of the traditional routing algorithm, proposes a communication channel time division multiplexing thought, reduces the bandwidth requirements of NoC system. The hardware resource allocation and recovery in the communication request, is widely used in the operating system of the banker 's algorithm is introduced. In the search for the shortest path to the communication request when the maze algorithm is used. At the same time, when multiple communication paths exist when used as close to the edge of the NoC network, select the center and three kinds of random rules. The experimental results show that the routing algorithm of communication channel time division multiplexing of NoC system is greatly reduced compared to the bandwidth requirements of traditional routing algorithms. At the same time. When multiple communication paths exist, as close to the edge of the practice NoC system can reduce the block of communication.

【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP332;TN47

【参考文献】