CMP中一种动态线程划分算法及Cache共享数据的提取方法

摘要

片上多核处理器系统已经成为处理器发展的主流趋势，针对此类系统的并行程序的运行时优化成为当前研究中的热点。并行线程调度优化已经成为提高系统资源利用率的关键之一，而传统调度算法不能够很好地适应新型片上并行结构的特性。本文中介绍了片上多核系统中线程的共享数据问题以及现阶段解决策略，并针对此问题提出了一种动态线程划分算法和一种支持此划分算法的统计信息提取方法。
　　 本文首先设计一种信息提取方法，利用硬件性能监测单元获取算法所需的数据，以保证动态划分算法的可行性。针对数据量过大的问题，采用了时间抽样方法减缓样本数据增加速度。为了降低整体算法运行规模，根据远程访问地址采用空间抽样方法进行抽样分析，避免检测所有cache的访问情况，以此减少算法运行规模和存储空间。
　　 在算法设计过程中，首先从抽样统计信息中获取线程之间的关系，建立一个无向带权图。然后采用子图识别算法对整个图进行连通子图地识别。不同于现有的聚集算法，本文在连通子图识别以后对所得子图进行规模大小地判断，当一个连通子图中包含的线程节点数大于N/K时（Ⅳ是系统中线程总数，K代表处理器核的数目），对此子图进行进一步分割使得每一个划分结果都满足负载平衡的要求。然后采用贪婪算法把所有连通子图重新划分为K组，每一组对应一个处理器核。算法运行以后向系统提交分配结果，然后算法睡眠直到系统状态再次触发线程划分算法。
　　 在算法实验中，从两个角度对比动态划分算法的有效性，一个对比角度是通过在仿真系统上定制处理器系统，并且运行商业的基准程序来获取数据源。在此数据源上从两个方面分析所设计的算法效果，其一就是对比不同程序中算法的效果，这里表现最好的是SPECJBB2000，在初始配置中优化幅度接近70％。其二是对同样的应用采用不同的任务负载强度。当服务程序个数和每个程序的线程个数分别增加的时候，算法的效果都有所提高，并且在最佳实例中达到1OO%的优化效果。而在程序个数和线程数量同时增加时，结果显示最好的优化效果减弱到60%左右，即随着任务整体负载的增加，在分配时算法丢弃的关联边更多，算法优化效果减弱。
　　 另一个对比角度是基于随机数据源的实验，从实验结果可以得出任务负载量的变化并不会对算法效果产生大的影响。但当片上核心数量增加时，算法的效果略有提升。就总体而言，动态划分算法取得了很可观的优化效果。
　　 为了观察抽样方法对数据特征的影响，本文对抽样参数变化的影响进行了分析。分别从时间跨度、空间抽样向量长度、映射比例三个方面分析抽样的影响。通过实验对比得出时间抽样跨度在N=100时统计数据特征变化趋于稳定，而空间向量长度为512时，子图分布变化比较缓和，然后子图变化加快。另外，映射比例的对比结果显示当哈希比例不超过16:1时，冲突不会对算法效果产生大的影响。