一种二维网格片上网络的任务映射方法

本发明公开了一种二维网格片上网络的任务映射方法，，包括下列步骤：1)预分配所有线程至二维网格上的预期位置，所述线程包括可以映射至任何位置的普通线程；2)计算每个普通线程与该普通线程的预期位置附近的普通线程或空闲位置交换后的总通信功耗系数的变化量Com_diff，将所述普通线程与使Com_diff取最小的普通线程或空闲位置执行交换，直至所述所有普通线程与其预期位置附近的普通线程或空闲位置交换均使Com_diff大于或等于0；3)根据所述所有线程的位置输出映射文件。本发明优化程度高；用户可自行调整参数来控制时间复杂度，且解决了部分映射问题。

1.一种二维网格片上网络的任务映射方法，包括下列步骤：1)预分配所有线程至二维网格上的预期位置，所述线程包括可以映射至任何位置的普通线程；2)计算每个普通线程与该普通线程的预期位置附近的普通线程或空闲位置交换后的总通信功耗系数的变化量Com_diff，将所述普通线程与使Com_diff取最小的普通线程或空闲位置执行交换，直至所述所有普通线程与其预期位置附近的普通线程或空闲位置交换均使Com_diff大于或等于0；其中，所述预期位置附近的普通线程或空闲位置与预期位置的距离小于预定阈值；3)根据所述所有线程的位置输出映射文件。
2.根据权利要求1所述的方法，其特征在于，所述步骤1)包括：11)按照每个普通线程的通信量的大小顺序将所述普通线程列入一个队列；12)将所述队列中的第一个普通线程分配至所述二维网格的中心位置；13)根据已经分配的线程的预期位置计算待分配的普通线程预期位置。
3.根据权利要求1所述的方法，其特征在于，所述所有线程还包括需要映射至特定位置的特殊线程。
4.根据权利要求3所述的方法，其特征在于，所述步骤1)包括：11’)将所述特殊线程列入一个队列；12’)按照每个普通线程的通信量的大小顺序将所述普通线程加入所述队列；13)根据已经分配的线程预期位置计算待分配的普通线程预期位置。
5.根据权利要求2或4所述的方法，其特征在于，所述步骤13)依据如下公式根据已经分配的线程预期位置计算待分配的普通线程预期位置：其中Com_i，k表示线程i、k之间的数据通信总量，x_k和y_k分别表示线程k的x轴和y轴坐标，x_i和y_i分别表示线程i的x轴和y轴坐标。
6.根据权利要求2或4所述的方法，其特征在于，所述步骤2)包括：21)将所述队列中的所有普通线程构成循环队列，任取其中一个普通线程； 22)假设所述普通线程属于未映射线程，计算所述普通线程与其预期位置附近的普通线程或空闲位置交换后的总通信功耗系数的变化量Com_diff，将所述普通线程与使Com_diff取最小的普通线程或空闲位置执行交换；23)重复步骤22)直至所述所有普通线程与其预期位置附近的普通线程或空闲位置交换均使Com_diff大于或等于0。
7.根据权利要求6所述的方法，其特征在于，所述与预期位置的距离根据曼哈顿距离计算。