片上网络(Network-on-Chip,No C)借鉴计算机互联网络采用包交换方法替代传统总线方法,实现了处理单元和通信结构的分离,有效解决了片上系统(System-on-Chip,SoC)多核之间的复杂通信问题,片上网络以其优良特性成为研究热点。片上网络的布局结构极大地影响着系统性能,布局结构关联到IPCore(Intellectual Property Core)处理单元之间的平均距离、通信路径长度和通信流量分布等特性,这些特征又影响到系统的功耗、时延、面积、吞吐量和负载平衡等众多的性能。片上网络布局中的重要步骤IPCore分配、IPCore映射以及最优路由算法等都是NP问题,这一类问题采用传统的优化算法,难以求得满足条件的解,通常是采用智能算法进行求解。智能算法广泛应用于各类优化问题,当前智能算法的一个重要研究方向是基于多种智能算法思想的融合,提出优势互补的智能算法,并运用于解决具体的优化问题。本文以基于智能算法的片上网络布局优化为研究课题,重点研究了NoC布局优化建模、IPCore分配、IPCore映射、容错机制、路由算法和拓扑结构等问题,主要研究内容如下:(1)根据片上网络布局中的需求和约束条件,建立多目标优化模型。对于其中两个重要阶段IPCore分配和IPCore映射分别建立以下评价模型:IPCore分配包括计算时间、计算功耗和面积等;IPCore映射包括通信时间、通信功耗、负载平衡和可靠性等。所建立的模型能较好地反映出阶段设计要求。(2)以提高NoC可靠性和系统性能为目标,根据NoC通信及故障特点,设计了基于空间冗余的容错结构,以及自适应的容错路由算法。该容错机制可以恢复由交换节点故障引起的通信中断,提高系统可靠性,采用的容错路由算法确保容错路径的性能优化,可以避免死锁、获得最短通信路径并且兼顾通信负载平衡。(3)根据IPCore分配的需求,以优化计算时间、计算功耗和面积等性能为目标求解分配方案,本文设计了两个适用于IPCore分配的智能算法:带多样化策略的多目标优化智能算法MPDS算法和强化局部跳变的多目标优化智能算法MPEL算法。这两个算法通过关键路径算法处理任务的并行性,结合多目标优化策略及智能优化思想,在传统智能算法基础上,引入多样化处理和局部跳变搜索等优化策略,融合了粒子群算法、遗传算法和模拟退火算法等多种智能算法的优点,克服传统单一智能算法易陷入局部最优等缺点,实验结果显示本文提出的算法相比其他常见的智能算法获得了更多,更高质量的IPCore分配方案。(4)IPCore映射是将IPCore安排到NoC结构中的合适位置的处理单元上,结合路由算法,构建NoC的拓扑结构。根据IPCore映射布局的需求和约束条件,以提高布局方案的通信时间、通信功耗、负载平衡和可靠性等性能为目标,设计了带不确定性策略的多目标分散搜索算法MSSU算法。该算法在传统智能算法的完全随机搜索过程中引入可控机制,结合局部的不确定性搜索策略,实现基于小种群的求解过程,在此基础上引入非支配排序方法,实现了多目标优化的求解。该算法兼具有分散搜索算法和遗传算法的优势,其解的搜索能力优于一般的智能算法,实验显示该算法求得的映射布局方案在数量和质量上均优于其他常见智能算法。(5)提出了基于彼得森图的可重构NoC布局结构。可重构布局策略不需要改变IPCore处理单元的映射位置,只需要通过重构节点调整拓扑关系,即可构建适用于多个NoC应用的布局结构,从而增强了布局结构的复用性。彼得森图具有网络直径短的优势,因此以彼得森图作为重构的基础结构,可以减少通信距离。由此得到的可重构布局一方面可以有效缩短节点之间的通信距离,减少中转交换节点的个数,从而达到减少通信代价的目的;另一方面可重构的方法提高了系统的重用性和灵活性。(6)根据NoC映射和路由的特点及需求,提出了多值量子进化算法MQG,并应用于求解NoC的布局优化方案。量子进化算法结合了量子优化和进化算法的思想,多值量子进化编码方法相比传统编码可以携带更多的编码信息,增强进化个体的多样性。在编码及解码过程中,摒弃传统的全路径编码,而是根据路径及节点之间的连续性构建路径,不仅缩短了编码长度,更避免了无效路径的产生。以此为基础构建的布局方案,在避免死锁的基础上搜索最优通信路径,以达到减少通信代价的目的。实验结果显示基于可重构的彼得森图的多值量子进化算法取得的布局方案相比其他常见算法和结构,获得了更低的通信代价。MQG算法思想也可以推广应用于其他NP问题的求解。