寻找片上网络任务与节点间映射方案及网络编码位置方法

摘要

本发明公开了一种寻找片上网络任务与节点间映射方案及网络编码位置方法，其针对多播应用在无线NoC上的映射，搜索最佳节点分配和路由选择方案时，不仅考虑单播任务总功耗与响应时间作为考核方案的优先指标，同时保证其中多播任务的吞吐率最大和多播任务的网络传输功耗最低。从而使采用此优选出来的方案设计出来的网络的性能达到最好，并且与其它对多个目标函数下寻找任务与节点间映射的优先方案的方法比较，具有复杂度，实现简单的特点。

主权项

一种寻找片上网络任务与节点间映射方案及网络编码位置方法，其特征在于，包括如下步骤：1).随机生成一个包含K个分配方案的方案组并为每个分配方案X＝(x₁,x₂,...,x_N)设定一个交叉的概率p_task和变异的概率q_task，以及任务映射迭代次数T_task，并令记录任务映射迭代的次数的变量t_task＝0以及初始化已得到的方案个数Z＝1，设置最大解个数Z_max；2).求出方案组J_t中每种方案下无线片上网络单播任务功耗与响应时间，并且记录最大功耗与最大响应时间为最差功耗值和最差响应时间值；3).计算出方案组J_t中各方案的适应度值，该适应度值大小反映方案的优先级，值越大优先级越高，所谓优先级别是按单播任务总功耗与响应时间小为优；4).将方案组J_t中的K个方案随机分成个方案小组，其中L是每方案小组中的方案个数，按照第3步中确定的优先关系选出每方案小组中最优先的方案组成一个优先方案组5).将优先方案组中的方案按随机配对，所述的配对是指按照两个方案一组进行分组，并以步骤1中设定的交叉的概率p_i将每对方案中的两个方案上任意一个相同位置上的节点的编号进行互换，然后再将所有被互换后的每对方案合并起来得到方案组6).以步骤1中设定的变异概率q_i改变方案组中各个方案中在任意一个位置上的节点的编号，得到方案组7).按第3步计算出来的适应度值从小到大的顺序，从方案组J_t中 选择个方案，与方案组的方案合并在一起，构成包含K个方案的新的方案组8).将方案组和合并成方案组9).计算方案组中每种方案下无线片上网络单播总功耗与响应时间，计算时，首先判断方案组中的每个方案的多播任务源和目的节点都是否映射到不同的无线片上网络节点上，如果是，则直接将最差功耗值和最差相应时间值赋值给本方案的功耗与响应时间值，如果不是，则计算方案组中每种方案下无线片上网络单播总功耗与响应时间；10).将方案组R_t中所有2K个方案分成多个小组，每个小组代表一个边界集，对小组编号，编号较小的小组里的方案比编号较大的小组的方案的优先级高；所谓优先级别是按功耗与响应时间小为优；11).初始化一个新的没有方案的方案组然后从第10步骤分好的小组中，按小组的编号从大到小的顺序，依次将小组内的方案加入到中，直到方案组里的方案个数超过K个，然后将最后加入的小组的方案全部取出；12).第10)步中，确定每个小组中各方案的优先次序的具体方法步骤如下：12‑1令小组中每个方案的距离值为0，所述的距离值表示该方案与其它方案的联系是否紧密；12‑2根据第9)步计算出的各个方案的功耗的大小对方案进行倒序排列，功耗较小的方案排在功耗较大的方案的前面；12‑3计算各方案的功耗距离，每个方案的功耗距离为排在它后面的那个方案的功耗减去排在它前面的那个方案的功耗所得到的值；12‑4根据第9)步计算出的各个方案的响应时间大小对方案进行倒序排列，响应时间较小的方案排在响应时间较大的方案的前面；12‑5计算各方案的响应时间距离，每个方案的响应时间距离为排在它后面的那个方案的响应时间减去排在它前面的那个方案的响应时间所得到的值；12‑6将各个方案的响应时间距离和功耗距离相加得到方案的距离值；12‑7把功耗最小的方案和响应时间最小的方案排在最前面，然后根据距离大小对剩余的方案进行排序，并排在功耗最小的方案和响应时间最小的方案的后面，距离值较大的方案排在距离值较小的方案的前面，这样排在前面的方案的优先级比排在后面的方案的优先级高；13).从第12)步骤里取出的小组里按优先级高低选择方案加入方案组直到方案组里的方案个数为K个；14).将方案组中的K个方案随机分成个方案小组，其中L是每方案小组中的方案个数，按照第10)步和第12)步确定的优先关系选出每方案小组中最优先的方案组成一个优先方案组15).将优先方案组中的方案再随机配对，以步骤1)中设定的交叉的概率p_task将每对方案中的两个方案上任意一个相同位置上的节点的编号进行互换，然后再将所有被互换后的每对方案合并起来得 到方案组16).以步骤1)中设定的变异的概率q_task改变方案组中各个方案中在任意一个位置上的节点的编号，得到方案组17).根据第10)步确定的方案组中方案的优先次序，按照优先级从高到低的顺序，从方案组中选择个方案，与方案组的方案合并在一起，构成包含K个方案的新的方案组18.如果t_task＜T_task，则t_task＝t_task+1，然后返回到步骤2)，继续迭代；否则进入步骤19)；19).计算出方案组中各方案的适应度值，将适应度值最大的方案，即功耗和响应时间同时最小的方案J_min作为无线片上网络的任务到节点间的任务映射方案；其中，K，L，均为正整数。