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

Abstract

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

Description

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

技术领域

本发明属于片上网络技术领域，特别是涉及一种基于连接特征的多任务集合划分方法。

背景技术

根据摩尔定律，微处理器的速度以及单片集成度每18个月就会翻一番。半导体工业在近几十年的发展中一直在追随着摩尔定律的节奏，微处理器的频率也不断攀升。随着通用处理器的主频突破4GHz，人们发现单一提升主频的做法已经不能再有效地提高性能，反而却带来了功耗的急剧上涨，高频率的道路逐渐走到了尽头。

于是对于计算机处理器的研究开始转向多处理核心的方向。早期的对称多处理器（SMP，Symmetric Multi-Processor）多是采用在同一计算机上汇集一组CPU的方式，它们之间共享内存子系统以及总线结构。之后由于纳米级制造工艺的引入，SMP开始转变为单芯片多处理器（CMP，Chip Multiprocessor），即在同一芯片上集成多个处理核心，形成了现在我们所说的多核处理器。多核心之间直接共享缓存以及总线结构，大大地降低了线延迟，显著提高了通讯效率。

按处理核的对等与否，多核处理器可分为同构多核和异构多核。处理核相同、地位对等的称为同构多核。现在市面上流行的Intel和AMD的多核处理器就是同构的多核处理器。处理核不同、地位不对等的称为异构多核。异构多核一般采用“主处理器＋协处理器”的设计。IBM、索尼和东芝等联手推出的Cell处理器正是这种异构架构的典范。处理器本身的结构关系到整个芯片的面积、功耗和性能。如何继承和发展传统处理器的成果直接影响到多核处理器的性能和实现周期。

多核处理器的各处理核执行的程序之间有时需要进行数据共享与同步，因此其硬件结构必须支持核间通信。高效的通信机制是多核处理器高性能的重要保障。目前片上高效通信机制通常有两种：基于共享总线的cache结构，基于片上网络的互连结构。基于共享总线的cache结构是指每个处理核拥有共享的二级或三级cache，用于保存比较常用的数据，并通过总线进行通信。这种系统的优点是结构简单，通信速度快；缺点是可扩展性差。

共享总线显然无法满足大规模系统的需要。把互连网络用于片上系统设计，解决片上组件之间的通讯问题，这就是片上网络。片上网络(-Network On Chip，NoC)技术以其支持同时访问、可靠性高、可重用性高等特点被认为是更加理想的大规模CMP互连技术。片上网络克服了总线结构可扩展性差的缺点，为10亿晶体管时代提供了一种可行的片上系统通讯机制。片上网络除了可以连接更多的IP组件，与总线结构相比，还有高可重用性等特点。

在片上系统设计中，可重用性是一个重要的设计原则。可重用性设计可以节省设计成本，提高设计的可靠性，缩短产品的上市周期。在基于总线的片上系统设计中，各个IP组件是重用的，但通讯结构却无法重用。每个设计都需要重新设计通讯结构。在片上网络中，除了各个组件是可重用的，片上通讯结构以及片上的通讯服务也是可重用的。设计新的系统时，在原有的系统上添加路由器和新的功能部件就可以了，以前的设计得到了重用，大大加快了设计的进度。同时，片上网络还具有低功耗的特点，它采用全局异步、局部同步设计，端到端的通讯方式，只有参与通讯的组件是激活的，避免了总线结构中采用广播方式进行通讯所造成的系统的功耗浪费，因此大大降低了系统的功耗。

在片上网络中，提供了丰富的计算资源，实现多任务的并行，这就需要完成多任务的调度、管理，尤其是映射。如何将任务映射到片上网络的处理器核上是非常重要的问题，而这首先取决于如何对多任务集合进行划分。传统上以划分任务图的方式来进行，非常耗时，且由于是NP完全问题，只能以复杂的算法寻求最优解。

发明内容

本发明旨在克服现有技术缺陷，目的在于提供一种基于连接特征的多任务集合划分方法，该方法能够提高多任务集合的划分效率。

为实现上述目的，本发明采用的技术方案的步骤是：

步骤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、按任务关联集合Si对多任务集合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所在的集合合并，划分完成。

由于采用上述技术方案，本发明利用了多任务之间的通信关系和通信量，计算出连接特征因子，并以连接特征因子来对多任务进行划分，从新的角度来实现多任务的快速划分，提高了划分的效率。本发明与现有技术相比，具有如下积极效果：

(1)高效性。片上网络中往往可以支持大量的任务，由于任务数量众多，如何来进行任务集合的划分，从而支持高效的映射、达到对片上网络的有效利用是需要解决的问题。在本发明中，以连接特征因子来进行多任务的划分，减少了划分方法的复杂程度，提高了划分的速度，因此具有较高的效率。

(2)实用性。在现有的任务划分中，多数都采用复杂的方法来实现，尽管可以达到一定的优化效果，但是由于方法复杂，在实现时往往面临着各种实际的问题。本发明中，减少了对条件的依赖，从而降低了方法在实现时的复杂度，从而具有很强的实用性。

因此，本发明适用于对多个任务进行任务集合的划分，充分利用了多个任务之间的连接和通信关系，能够快速有效的将多个任务划分成不同的集合。为多任务管理、多任务调度和多任务映射等提供基本的多任务划分集合，提高管理、调度和映射的效率。

附图说明

图1是本发明的一种方法示意图；

图2是本发明的一种多任务关系示意图。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步的描述，并非对其保护范围的限制。

一种基于连接特征的多任务集合划分方法。该方法的步骤如图1所示：

步骤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所有通信量之和。

对于具有11个任务的任务集合，其多任务模型G(T,P,Q)如下：

T={t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇,t₈,t₉,t₁₀}。

P、Q、W如图2所示，p_ij=1表示两个任务t_i和t_j之间有连线存在，p_ij=0表示两个任务t_i和t_j之间没有连线存在；两个任务t_i和t_j之间的连线上数字表示w_ij；如果任何两个任务之间存在连线可以将这两个任务连接在一起，则这两个任务是连通的。

L_i值如表1所示：

表1任务的L_i值

	t0	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10
												Li	4	3	2	2	2	3	2	2	3	4	3

Hi值如表2所示：

表2任务的H_i值

	t0	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10
												Hi	900	630	500	430	430	780	560	420	650	670	410

步骤2、计算每个任务的连接特征因子θ_i

任务t_i的连接特征因子θ_i：

θ_i=L_i×lg(H_i)     (1)

然后对所有任务按照连接特征因子θ_i的大小进行降序排序，形成多任务集合T’；在排序过程中，如果两个任务具有相同大小的连接特征因子，则按照多个任务的序号大小进行降序排序。

对于前述具有11个任务的多任务集合T={t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇,t₈,t₉,t₁₀}，

根据表1和表2计算11个任务的连接特征因子如表3所示：

表3任务的连接特征因子θ_i

	t0	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10
												θi	11.817	8.398	5.398	5.267	5.267	8.676	5.496	5.246	8.439	11.304	7.838

按照连接特征因子θ_i的大小进行排序后形成的新集合T’为：

T’={t₀,t₉,t₅,t₈,t₁,t₁₀,t₆,t₂,t₃,t₄,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)。

对于具有11个任务的任务集合，其多任务模型G(T,P)如下：

T={t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇,t₈,t₉,t₁₀}；

则按照图2所示，其关联任务集合如表4所示：

表4任务的关联任务集合

步骤4、按任务关联集合对多任务集合进行划分

按照任务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。

对于具有11个任务的任务集合，其多任务模型G(T,P)如下：

T={t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇,t₈,t₉,t₁₀}。

则划分出的集合如下所示：

步骤4.1、V₁={t₀,t₁,t₅,t₈,t₉,t₁₀,t₃,t₄}。

步骤4.2、V₂={t₂,t₆,t₇}。

步骤5、按照连接特征因子进行多任务集合划分

对于步骤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所在的集合合并，划分完成。

对于具有11个任务的任务集合，其多任务模型G(T,P)如下：

T={t₀,t₁,t₂,t₃,t₄,t₅,t₆,t₇,t₈,t₉,t₁₀}。

按步骤4，划分出的集合V为：

V₁={t₀,t₁,t₅,t₈,t₉,t₁₀,t₃,t₄}。

V₂={t₂,t₆,t₇}。

设置收敛因子为8，则对于V₁，由于t₁₀,t₃,t₄这三个任务中，S₀(t₁₀)、S₀(t₄)和S₀(t₃)均大于收敛因子8，则t₁₀,t₃,t₄被加入新的集合V₃。

再次设置新的收敛因子5，则t₁₀,t₃,t₄所构成的集合V₃不再调整；

对于V₂，设置新的收敛因子为5，则V₂不再调整；

划分后的集合为：

V₁={t₀,t₉,t₅,t₈,t₁}

V₂={t₂,t₆,t₇}

V₃={t₁₀,t₃,t₄}

本具体实施方式利用了多任务之间的通信关系和通信量，计算出连接特征因子θ_i，并以连接特征因子θ_i来对多任务进行划分，从新的角度来实现多任务的快速划分，提高了划分的效率。本发明与现有技术相比，具有如下积极效果：

(1)高效性。片上网络中往往可以支持大量的任务，由于任务数量众多，如何来进行任务集合的划分，从而支持高效的映射、达到对片上网络的有效利用是需要解决的问题。在本发明中，以连接特征因子θ_i来进行多任务的划分，减少了划分方法的复杂程度，提高了划分的速度，因此具有较高的效率；

(2)实用性。在现有的任务划分中，多数都采用复杂的方法来实现，尽管可以达到一定的优化效果，但是由于方法复杂，在实现时往往面临着各种实际的问题。本发明中，减少了对条件的依赖，从而降低了方法在实现时的复杂度，从而具有很强的实用性。

因此，本发明适用于对多个任务进行任务集合的划分，充分利用了多个任务之间的连接和通信关系，能够快速有效的将多个任务划分成不同的集合。为多任务管理、多任务调度和多任务映射等提供基本的多任务划分集合，提高管理、调度和映射的效率。

Claims (1)

1.一种基于连接特征的多任务集合划分方法，其特征在于该实现方法的步骤如下：

步骤1、建立多任务模型

对于多任务，建立多任务模型G(T,P,Q)，其中：

T为任务的集合，T={t₀,t₁,…,t_m}；

P为pi_j的集合，pi_j=1表示任务t_i与任务t_j之间存在着通信关系，pi_j=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)；

其中，Si(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、按任务关联集合Si对多任务集合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、对于只有一个任务ti的集合，通过p_ij找到对应的任务编号最小的任务t_j所在的集合，将任务t_i所在的集合与任务t_j所在的集合合并，划分完成。

Images