面向通讯同步的多处理器阵列重构

发布时间：2018-04-26 10:48

本文选题：VLSI阵列 + 拓扑重构　；参考：《计算机科学》2017年07期

【摘要】：从多处理器阵列中获取所需大小并且同步通讯性能优良的子阵列,是高性能拓扑重构的核心问题之一。基于不同的逻辑列剔除策略提出了3种面向通讯同步的拓扑重构算法:基于分治思想剔除逻辑列的重构算法(SCA_01),该算法能够使被优化的逻辑列相对均匀地分布在物理阵列中;优先剔除长逻辑列的贪心重构算法(SCA_02),该算法能够使被优化的逻辑列的长链接总数最少;基于分治与长链接数的混成重构算法(SCA_03),该算法将某一区域内的最长逻辑列剔除,且尽可能将剩余逻辑列均匀分布在物理阵列中。同时,对逻辑阵列的最大通讯延时给出了下界的求解算法。实验结果表明,3种算法在故障率小于1%、逻辑列的剔除率超过20%时,算法重构出的逻辑阵列的通讯延时特别接近计算出的性能下界。在多数情况下SCA_01优于SCA_02和SCA_03,而后两者的性能相近。在小阵列上且故障率与剔除率较小时,SCA_02具有性能优势,但在大阵列上SCA_03具有优势。在32×32的阵列上,SCA_01构造的阵列产生的通讯延时较SCA_02和SCA_03产生的延时平均减少25%,并且运行速度也提升了19.4%。
[Abstract]:It is one of the core problems of high performance topology reconstruction to obtain the required size from the multiprocessor array and to synchronize the sub-arrays with good communication performance. Three topology reconstruction algorithms oriented to communication synchronization are proposed based on different logic column elimination strategies: the algorithm of reconstructing logic columns based on partition and conquer is called SCAstack 01, which can make the optimized logic columns distribute in the physical array relatively evenly; The greedy reconstruction algorithm (SCA02C), which gives priority to the elimination of long logical columns, can minimize the total number of long links in the optimized logical columns, and the hybrid reconstruction algorithm based on partition, conquer and long link number (SCA03), which removes the longest logical columns in a certain region, As far as possible, the remaining logical columns are uniformly distributed in the physical array. At the same time, the lower bound algorithm is given for the maximum communication delay of logic array. The experimental results show that when the failure rate is less than 1 and the elimination rate of logic sequence is more than 20, the communication delay of the reconstructed logic array is especially close to the calculated lower bound of performance. In most cases, SCA_01 is superior to SCA_02 and SCA03, and the performance of the latter two is similar. On the small array, the failure rate and elimination rate are smaller than that on the small array, but the SCA_03 has the advantage on the large array. The communication delay generated by the array constructed by SCA01 on the 32 脳 32 array is 25% less than that produced by SCA_02 and SCA_03 on average, and the running speed is also increased by 19.4%.
【作者单位】：广东工业大学计算机学院;
【基金】：国家自然科学基金项目(61572144) 广东省科技计划应用专项基金(2015B010129014) 广东省自然科学基金项目(2016A030313703)资助
【分类号】：TP332

【参考文献】