随着集成电路技术的发展,芯片上的集成晶体管数目呈指数增加。当集成电路工艺进入到65 nm以下,线延时不再随着工艺特征尺寸缩小而减少。芯片的性能无法随着器件数目和时钟频率的增加而成比例的提升。随着系统应用复杂度的增加,可以将多个处理器核、存储器以及其他的知识产权核(intellectual propertycore,简称IP核),通过片上网络互连的方式,集成到单一芯片中。片上网络设计需要考虑低能耗、高带宽、低传输延迟、可扩展、可靠性等设计要求和挑战。从系统的角度综合考虑这些设计挑战和要求,基于层次交互构件方法,重点研究片上网络设计亟待解决的三个关键问题：应用映射、多播路由,以及消息依赖造成的死锁。首先,针对二维片上网络,本论文提出一种感知应用通信特性和拓扑结构的应用映射算法：基于应用模板的高效应用映射算法(template-aware efficient mapping,简称TEM)。TEM按照应用的通信轨迹图的特性,将应用分为两大类,1)存在通信热点的应用和2)通信比较均匀的应用。对于第一类应用,TEM将热点及其相连的节点映射到靠近的资源节点；对于第二类应用,TEM采用图划分的方式进行映射。TEM可以被用在二维网格、环绕网格、蝶形胖树等拓扑结构。将TEM映射算法的结果作为遗传算法(genetic algorithm,简称GA)的初始群体,得到更为优化的映射算法GA+TEM。采用SPLASH-2基准测试的通信轨迹作为Noxim片上网络仿真器的输入,实验结果表明,GA+TEM比单纯使用GA算法明显降低了通信能耗(5%-20%)。本论文进一步提出了一种针对三维集成片上网络的增量式应用映射算法：高能效的运行时增量式应用映射算法框架(energy efficient run-time incremental mapping framework,简称ERIM)。ERIM根据新到达应用的任务图的特性,将应用分为两种类型,1)通信密集型和2)计算密集型。对于这两种类型的应用,ERIM首先找到一个长方体形状的资源节点区域,以减少对未到达应用的影响。对于通信密集型的应用,ERIM通过有效地利用垂直方向所增加的连接度,来降低通信能耗。而对于计算密集型的应用,ERIM尽量平衡在每一个垂直堆叠(vertical stack)上运行任务的处理器核之间的温度来避免温度超过门限值。实验结果表明,ERIM产生的映射结果比两个贪婪式映射算法的映射结果的能耗低达15%。其次,我们考虑多个应用被分配到同一个片上网络系统中而每一个应用的子区域可能不规则时,如何进行多播路由。本论文提出了一种面向不规则子区域的多播路由策略,其原理如下：基于一个现有的多播路由算法,比如多播XY路由,当发现一个输出端口所连接的网络节点不在同一个子区域内,就选择另外一个方向(称为替换方向,alternative).基于这个策略,提出了一个面向二维子区域的替换多播XY路由算法(alternative multicasting XY routing,简称AL+XY)和一个面向三维子区域的替换多播XYZ路由算法(alternative multicasting XY routing,简称AL+XYZ)。实验结果表明AL+XY比多次单播和区域内广播两种方法,能耗和延迟都低。当多播对单播比例为0.3、注入率为0.4(flit/cycle)的时候,多次单播和子区域内广播的能耗分别为AL+XY的2.2倍和2倍。在同样的多播对单播比例和注入率下,多次单播和子区域内广播的延迟分别为AL+XY的11和1.2倍。AL+XY可以被扩展为适用于三维集成片上网络子区域多播的AL+XYZ多播路由。AL+XY和AL+XYZ路由器在TSMC 65nm工艺下综合,工作频率为800MHz。AL+XY比二维网格片上网络的单播路由器面积增加了3%, AL+XYZ的面积比三维集成片上网络单播路由器面积增加了7%。最后,本论文中提出了一种可以避免在点对点流式传输系统中可能出现的请求-请求类型消息依赖造成的死锁的方法。消息依赖造成的死锁产生的原因是网络中的消息不能被目的节点消耗而驻留在网络中,这些消息相互依赖,从而造成死锁。本论文从理论上证明了一个避免请求一请求类型消息依赖造成的死锁的充分条件,并提出可以通过增加非均匀虚通道(即路由器的每个端口所配置的虚通道数目可以不一样)来避免这种死锁。基于该理论,本论文进一步证明了寻找最小数目的非均匀虚通道的问题是一个NP完全问题,并提出一个基于线性规划的近似算法：路径选择和最少虚通道分配方法(path selection and minimum virtual channel allocation,简称PSMV)。PSMV算法可以和现有的应用映射算法集成在一起,产生没有死锁的映射结果。PSMV产生的结果延迟低,使用额外缓冲开销较少。
