一种基于连接特征的多任务集合划分方法

摘要

本发明涉及一种基于连接特征的多任务集合划分方法。其技术方案的步骤是：步骤1是为多任务建立多任务模型；步骤2是计算每个任务的连接特征因子θ_i；步骤3是建立每个任务的关联任务集合；步骤4是按任务关联集合对多任务集合T进行划分；步骤5是按照连接特征因子θ_i进行多任务集合划分。本发明适用于对多个任务进行任务集合的划分，充分利用了多个任务之间的连接和通信关系，能够快速有效地将多个任务划分成不同的集合。本发明能为多任务管理、多任务调度和多任务映射等提供基本的多任务划分集合，提高管理、调度和映射的效率。

主权项

一种基于连接特征的多任务集合划分方法，其特征在于实现该方法的步骤如下：步骤1、建立多任务模型对于多任务，建立多任务模型G(T, P, Q)，其中：T为任务的集合，T={t₀, t₁, … , t_m}；P为p_ij的集合，p_ij=1表示任务t_i与任务t_j之间存在着通信关系，p_ij=0表示任务t_i与任务t_j之间不存在通信关系；Q为q_ij的集合，q_ij=1表示任务t_i与任务t_j之间不存在通信关系，但通过任务t_i与其他任务之间的通信关系和通过任务t_j与其他任务之间的通信关系，任务t_i与任务t_j能被连通；多任务模型G(T, P, Q)所具有的属性为：D(q_ij)为连通关系q_ij的属性，表示任务t_i与任务t_j之间的连通所需要经过的任务数量；w_ij是任务t_i的属性，w_ij表示任务t_i与任务t_j之间的通信量，W为w_ij的集合；L_i是任务t_i的属性，表示与任务t_i存在通信关系的任务的数量；H_i是任务t_i的属性，表示任务t_i所有通信量之和；步骤2、计算每个任务的连接特征因子θ_i任务t_i的连接特征因子θ_i为：θ_i=L_i×lg(H_i)                            (1)然后对所有任务按照连接特征因子θ_i的大小进行降序排序，形成多任务集合T’；在排序过程中，如果多个任务具有相同大小的连接特征因子，则按照多个任务的序号大小进行降序排序；步骤3、建立任务t_i的关联任务集合对于多任务集合T中的任务t_i，任务t_i的关联任务集合S_i为与任务t_i具有通信关系或连通关系的所有任务的集合；对于关联任务集合S_i中与任务t_i具有通信关系的任务t_j，S_i(t_j)=0；对于关联任务集合S_i中与任务t_i具有连通关系的任务t_j，S_i(t_j)= D(q_ij)；其中，S_i(t_j)是任务t_i与任务t_j之间的关联所需要经过的任务数量；若S_i(t_j)=0，表示任务t_i与任务t_j之间的关联所需要经过的任务数量为0；若S_i(t_j)= D(q_ij)，表示任务t_i与任务t_j之间的关联所需要经过的任务数量为D(q_ij)；步骤4、按关联任务集合S_i对多任务集合T进行划分按照任务t_i的关联性，对多任务集合T根据任务t_i之间的关联进行划分，划分为g个相互之间没有任何关联的集合V₁, V₂, …, V_g，具体步骤是：步骤4.1、对于任务t₀，将任务t₀和集合S₀中的所有任务加入到集合V₁当中；步骤4.2、对于不在集合V₁中的任务t_i，将任务t_i和集合S_i中的所有任务加入到集合V₂当中；步骤4.3、对于不在集合V₁和集合V₂中的任务t_j，将任务t_j和集合S_j中的所有任务加入到集合V₃当中；步骤4.4、按照步骤4.1、步骤4.2和步骤4.3进行到第k步时，对于不在集合V₁, V₂, … V_k‑1中的任务t_c，将任务t_c和集合S_c中的所有任务加入到集合V_k当中；直到完成第g个步骤，多任务集合T划分为集合V₁, V₂, …, V_g；步骤5、按照连接特征因子θ_i进行多任务集合划分对于步骤4中生成的集合V₁, V₂, …, V_g进行进一步的划分，具体步骤是：步骤5.1、设置收敛因子I，I为0或自然数；步骤5.2、对于集合V₁, V₂, …, V_g中的一个集合V_i，对于在集合V_i中且多任务集合T’排序第一的任务t_x，按照多任务集合T’中的排序，检查任务t_x与多任务集合T’中任务t_y之间的连通关系；如果S_x(t_y)<I，则将任务t_y从集合V_i中去除，建立集合V_g+1，并将任务t_y加入集合V_i’；步骤5.3、对所有集合V_i’，均按照步骤5.1和步骤5.2进行操作，直到不再有新的集合生成；其中每次按照步骤5.1操作时，需重新设置收敛因子I；步骤5.4、对于只有一个任务t_i的集合，通过p_ij找到对应的任务编号最小的任务t_j所在的集合，将任务t_i所在的集合与任务t_j所在的集合合并，划分完成。