| 主权项 |
1.一种片上网络中任务与节点间映射方案与拓扑结构的设计方法，其特征在于，用向量X=(x<sub>1</sub>,x<sub>2</sub>,...x<sub>n</sub>...,x<sub>N</sub>)表示片上网络的N个任务向M个节点映射的一种方案，向量X的第n个位置上的x<sub>n</sub>(0≤x<sub>n</sub>≤M-1)代表了第n个任务映射到某个节点的节点编号，即x<sub>n</sub>表示了将编号为n的任务分配给了第x<sub>n</sub>的节点，包括如下步骤：1、生成无线片上网络任务与节点间映射方案的待选拓扑结构T<sub>1</sub>,T<sub>2</sub>,...,T<sub>G</sub>，在不同的待选拓扑结构上选择最优的映射方案;具体步骤为步骤2到步骤20，初始化g=1；2、对第g个待选拓扑Tg，随机生成一个包含K个分配方案的方案组J<sub>t</sub>，并为每个分配方案X=(x<sub>1</sub>,x<sub>2</sub>,...,x<sub>N</sub>)设定一个交叉的概率p<sub>i</sub>和变异的概率q<sub>i</sub>，以及总的迭代次数T，并令记录迭代的次数的变量t=0；3、求出方案组J<sub>t</sub>中每种方案下片上网络功耗与响应时间:利用计算式P=P<sub>N</sub>+P<sub>PE</sub>求出无线NoC的功耗P,其中，P<sub>N</sub>是仅与电磁波导传输线上载波数有关的无线NoC上RF-I链路消耗的功耗固定值,P<sub>PE</sub>是无线NoC上所有处理核的功耗之和;响应时间是从任务流图的输入到输出的时间间隔，其计算式为D=T<sub>p</sub>+T<sub>D</sub>+T<sub>W</sub>，其中，T<sub>p</sub>为输入到输出路径上所有任务的处理时间，T<sub>D</sub>为输入到输出路径上的数据传递时间之和，T<sub>W</sub>为传输过程中由于拥塞导致的数据包排队与等待的时间;对方案组J<sub>t</sub>中每种方案，判断其是否满足下列四个条件：一个任务只能映射到一个处理核上；数据的处理速率大于数据达到率；映射方案所需求的带宽小于或等于所提供的最大带宽；反馈环路的迭代边界小于或等于迭代时间;若不满足，则将其功耗设为方案组J<sub>t</sub>中功耗最大值，响应时间设为方案组J<sub>t</sub>响应时间最长值;4、计算出方案组J<sub>t</sub>中各方案的适应度值，该适应度值大小反映方案的优先级，值越小优先级越高，所谓优先级别是按功耗与响应时间小为优;5、将方案组J<sub>t</sub>中的K个方案随机分成<img file="FDA0000459606140000021.GIF" wi="70" he="142" />个方案小组，其中L是每方案小组中的方案个数，按照第3步中确定的优先关系选出每方案小组中最优先的方案组成一个优先方案组Q<sub>t</sub>；6、将优先方案组Q<sub>t</sub>中的方案按随机配对，所述的配对是指按照两个方案一组进行分组，并以步骤2中设定的交叉的概率p<sub>i</sub>将每对方案中的两个方案上任意一个相同位置上的节点的编号进行互换，然后再将所有被互换后的每对方案合并起来得到方案组Q<sub>t</sub>′；7、以步骤2中设定的变异概率q<sub>i</sub>改变方案组Q<sub>t</sub>′中各个方案中在任意一个位置上的节点的编号，得到方案组G<sub>t</sub>;8、按第4步计算出来的适应度值从小到大的顺序，从方案组J<sub>t</sub>中选择<img file="FDA0000459606140000022.GIF" wi="170" he="142" />个方案，与方案组G<sub>t</sub>的方案合并在一起，构成包含K个方案的新的方案组G<sub>t</sub>′；9、将方案组J<sub>t</sub>和G<sub>t</sub>合并成方案组R<sub>t</sub>;10、计算方案组R<sub>t</sub>中每种方案下片上网络功耗与响应时间；11、将方案组R<sub>t</sub>中的2K个方案分成多个小组，每个小组代表一个边界集，对小组编号，编号较小的小组里的方案比编号较大的小组的方案的优先级高；所谓优先级别是按功耗与响应时间小为优;12、初始化一个新的没有方案的方案组F<sub>t</sub>，然后从第11步骤分好的小组中，按小组的编号从大到小的顺序，依次将小组内的方案加入到F<sub>t</sub>中，直到方案组F<sub>t</sub>里的方案个数超过K个，然后将最后加入的小组的方案全部取出;13、确定第11步中每个小组中各方案的优先次序，具体方法如下：13-1令小组中每个方案的距离值为0，所述的距离值表示该方案与其它方案的联系是否紧密;13-2根据第10步计算出的各个方案的功耗的大小对方案进行倒序排列，功耗较小的方案排在功耗较大的方案的前面；13-3根据第10步计算出的各个方案的响应时间大小对方案进行倒序排列，响应时间较小的方案排在响应时间较大的方案的前面；13-4对于步骤13-2中已排序的方案，计算各方案的功耗距离，每个方案的功耗距离为排在它后面的第1个，第2个，…，第i个方案的功耗分别对应地减去排在它前面的第1个，第2个，…，第i个方案的功耗所得到的差相加，然后除以i所得的值,其中i的取值满足关系式：i≤log<sub>2</sub>2K；13-5对于步骤13-3中已排序的方案，计算各方案的响应时间距离，每个方案的响应时间距离为排在它后面的第1个，第2个，…，第i个方案的功耗分别对应地减去排在它前面的第1个，第2个，…，第i个方案的功耗所得到的差相加，然后除以i所得的值；13-6将各个方案的响应时间距离和功耗距离相加得到方案的距离值；13-7把功耗最小的方案和响应时间最小的方案排在最前面，然后根据距离大小对剩余的方案进行排序，并排在功耗最小的方案和响应时间最小的方案的后面，距离值较大的方案排在距离值较小的方案的前面，这样排在前面的方案的优先级比排在后面的方案的优先级高；14、从经过了第13步骤排序后的第12步骤里取出的小组里按优先级高低选择方案加入方案组F<sub>t</sub>，直到方案组F<sub>t</sub>里的方案个数为K个；15、将方案组F<sub>t</sub>中的K个方案随机分成<img file="FDA0000459606140000041.GIF" wi="68" he="144" />个方案小组，其中L是每方案小组中的方案个数，按照第10步和第12步联合确定的优先关系选出每方案小组中最优先的方案组成一个优先方案组F<sub>t</sub>′；16、将优先方案组F<sub>t</sub>′中的方案再随机配对，以步骤2中设定的交叉的概率p<sub>i</sub>将每对方案中的两个方案上任意一个相同位置上的节点的编号进行互换，然后再将所有被互换后的每对方案合并起来得到方案组H<sub>t</sub>；17、以步骤2中设定的变异的概率q<sub>i</sub>改变方案组H<sub>t</sub>中各个方案中在任意一个位置上的节点的编号，得到方案组H<sub>t</sub>′；18、根据第11步和第13步联合确定的方案组F<sub>t</sub>中方案的优先次序，按照优先级从高到低的顺序，从方案组F<sub>t</sub>中选择<img file="FDA0000459606140000051.GIF" wi="172" he="144" />个方案，与方案组H<sub>t</sub>′的方案合并在一起，构成包含K个方案的新的方案组J<sub>t+1</sub>；19、如果t<T，则t=t+1，然后返回到步骤3重复上述所有步骤，否则进入步骤20;20、检查方案组J<sub>T</sub>中各方案是否满足下列四个条件：一个任务只能映射到一个处理核上；数据的处理速率大于数据达到率；映射方案所需求的带宽小于或等于所提供的最大带宽；反馈环路的迭代边界小于或等于迭代时间;若不满足，则将该方案的适应度值设为最差值；否则，按照步骤4所述的方法计算出方案组J<sub>T</sub>中各方案的适应度值，选出适应度值最小的方案，即功耗和响应时间同时最小的方案，将其作为第g个待选拓扑结构最优的任务到节点间的映射方案J<sub>Tg</sub>，进入步骤21；21、如果g<G,则g=g+1，进入步骤2，重复上述所有步骤；否则，进入步骤22;22、得到待选拓扑结构T<sub>1</sub>,T<sub>2</sub>,...,T<sub>G</sub>所对应的G种最优方案分别为<img file="FDA0000459606140000061.GIF" wi="337" he="79" />计算出<img file="FDA0000459606140000062.GIF" wi="311" he="90" />中各方案的适应度值，选择适应度最小的方案，将其作为无线片上网络的任务到节点间的映射方案，将该方案对应的拓扑g作为无线NoC的拓扑结构。 |
