计算系统的并行化和映射问题研究

《计算系统的并行化和映射问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ParallelProgrammingandMappingProblemsonComputingSystemAdissertationsubmittedtothefacultyoftheDepartmentofPhysicsandthegraduateschoolofNanjingUniversityinpartialfulfillmentoftherequirementforthedegreeofMasterofEngineeringByⅥ伦iYi(MicroelectronicsandSolid-stateElectronics)S

2、upervisor：AssociateProfessorHongbingPanMay2011摘要毕业论文题目：盐笠丕丝丝羞堑垡垄迭盟闭墨逝窒丝垫主堂鱼固堡垫主堂专业2QQ墨级硕士生姓名：墨堡指导教师(姓名、职称)：渣红基副塾撞摘要由于传统单核芯片的功耗和性能已经不能满足人们对电子产品日益增长的需求，这就使得大家开始寻求更好的替代方案。MPSoCIll是实现高性能，低功耗的有效解决方案之一。然而由于多核硬件的研究远远领先于软件研究，所以现在的软件并不能很好的利用硬件资源，发挥其所有的性能。本文专注于多核系统中的软件研究，寻求最大化硬件性能

3、的软件调度方法。调度问题是组合优化中的一类基本问题，其核心内容是如何高效的使用稀缺资源，即将一些任务有效的安排在若干台机器上进行处理，而使某个目标达到最优。根据任务特性、机器特性和优化目标的不同，调度问题包含了成百上千个不同的调度模型。本文主要是基于实际需要，在具体应用中根据不同的情况使用不同的任务划分和调度方案，从而尽可能的最大化系统性能。H3MP是项目组独立开发的高性能，高吞吐量，高速度的16核芯片。为了最大化利用系统的资源，本文利用流媒体高速度，高吞吐量的特点，将该多核芯片集成在Xilinx的ML525(XC5VLX330T)开发

4、板上，实现了四通道淡入淡出的实时流媒体系统。本文为该系统提出了两种并行化方案。方案一在于数据级的细粒度划分，得到7．6的加速比。方案二在于任务级的粗粒度划分，得到9．2的加速比。为了寻找更通用的编程模型，本文分别在OpenMP模型，Pthread模型和CUDA模型上对AC多模匹配算法进行编程测试，并将其结果进行了比较。实验证明Pthread模型比OpenMP模型更适合于复杂控制流的系统模型。CUDA[2J模型结果很大程度上优于另外两个模型，在于GPU上有更多的计算核心，然而如果可并行化部分不多的话，也不能得到很大的性能提升。随着VLSI

5、技术的飞速发展，将大量的运算，逻辑，存储单元放到一个芯片上已经不再是问题，这样就可以更大化任务的并行程度。然而随着片上资源的不断增加，那么必然导致片上的通信就显得越来越严重，NOCTM的提出正式为了解决这一问题。但是将不同的IP核放置在不同的节点也会很大程度上影响系统的性能和功耗。所以本文还针对NOC，对网络映射问题做了一定的探讨。南京大学硕士学位论文如何在兼顾功耗和负载平衡的情况下对任务进行映射是首要需要解决的问题。蚁群算法可以有效得解决该问题，但是传统蚁群算法的收敛性对初始化参数的设置比较敏感，本文使用遗传算法对蚁群算法的初始化参数

6、进行选择，同时在算法陷入局部最优解的时候引入混沌模型加大遗传算法的突变概率来修改蚁群参数，避免算法停滞。修改后的算法在能耗方面相较于传统算法改善了11％，而在负载平衡方面则改善了1％，两者联合优化的效果则比传统算法改善了4％。本文主要贡献和创新如下：(1)提出了一种粗粒度的划分方案，通过使用计算时间来覆盖通信时间从而大幅度的提高了加速比。(2)分别使用OpenMP，Pthread和CUDA模型对AC多模匹配算法进行并行化实现，对几个模型进行了比较。(3)为了避免蚁群算法的缺点在映射问题中发散，本文使用遗传算法避免蚁群算法对初始化参数发散

7、的问题，同时使用混沌模型解决其陷入局部最优的问题。关键词：片上多核；片上网络；ARM处理器；FPGA；流媒体；调度；CUDA；映射；蚁群算法，遗传算法；混沌模型ABSTRACTDISSERTATl0N：SPECIALIZATION：APPLICANT：ADVISORS：ParallelProgrammingandMappingProblemsonComputingSystem】ⅥicroelectronicsandSolid—stateElectronicsW-eiYiAssociateProfessorHongbingPanABSTR

8、ACTWiththeincreasingdemandforelectronicproducts，thesingle—coreonthechipwithlowperformanceandhighpowerco