CN114356580B - 基于共享资源访问的异构多核系统任务分配方法和装置 - Google Patents

Abstract

本发明公开了一种基于共享资源访问的异构多核系统任务分配方法，包括，计算各任务在各处理器核上的最坏情况执行时间和实际执行时间；计算各任务的在各处理器上的能量密度和各任务的能量密度差值；依次选择能量密度差最大的未分配任务，将该任务分配给可选处理器核中与该任务资源相似度最大的处理器核。本发明还公开了基于共享资源访问的异构多核系统任务分配装置，本发明的技术方案中，按照各任务的能量密度差值从大到小选择任务分配的顺序，能有效降低异构多核系统处理器核的能耗。

Description

基于共享资源访问的异构多核系统任务分配方法和装置

技术领域

本发明属于计算机体系结构领域，具体涉及到一种基于共享资源访问的异构多核系统任务分配方法和装置。

背景技术

随着计算机技术的飞速发展，嵌入式设备的使用越来越广泛，尤其是消费类电子产品飞速增长。为了满足嵌入式设备对不同任务的处理需求，异构多核处理器逐渐受到市场青睐。算力增长的同时，设备的功耗也在增长，这不仅会降低嵌入式设备的工作时长，而且会产生过多的热量，导致用户的体验下降，如何降低异构多核嵌入式设备功耗成为异构多核片上系统技术中迫切需要解决的问题。

现有技术基于共享资源访问的异构多核系统任务分配方案中，普遍采用启发式算法对任务进行分配。主要有最坏匹配降序(简称,WFD)、同步感知最坏匹配降序(简称，SA-WFD)等方法。

SA-WFD启发式任务分配算法最早应用于扩展的多核堆栈资源协议(简称，MSRP)，为了保证在最坏情况下仍然能满足任务的实时可调度性，SA-WFD算法使用任务的最差估计利用率(简称，)，先计算每个任务τ_i的最差估计利用率/>根据最差估计利用率对任务进行降序排列，然后根据排列顺序分配任务。

1.选择最差估计利用率最大的任务；

2.在剩余处理器核中选择与该任务资源相似度(资源相似度指，该待分配任务和处理器核上已有任务访问相同共享资源的个数)最大的处理器核，若存在多个资源相似度一样的处理器核，则在所述资源相似度一样的处理器核中选择总最差估计利用率最小的一个；

其中，j表示处理器核编号，EU^j表示处理器核π^j当前的总最差估计利用率，Ψ^j表示分配到处理器核π^j上的任务集，表示任务τ_i在处理器核π^j上的最差估计利用率；

3.计算将该任务分配给选择的处理器核后，该处理器核的总最差估计利用率是否大于1，如果是，执行步骤2，否则执行步骤4；

4.将该任务分配给所选择的处理器核；

5.计算并更新该处理器核π^j当前的EU^j；

重复执行上述步骤直至任务分配完成。

该技术方案存在分配完成后还存在大量的空闲时间，而且分配过程中没有考虑能耗对系统的影响，不利于降低设备功耗。

发明内容

为了解决现有技术中存在的上述问题，本发明提供了一种基于共享资源访问的异构多核系统任务分配方法和装置，以降低处理器的动态能耗。

本发明的基于共享资源访问的异构多核系统任务分配方法包括：

计算各任务在各处理器核上的最坏情况执行时间和实际执行时间T_i ^j；

其中，表示任务τ_i的临界区个数，χ为临界区编号，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间，/>为处理器核π^j当前的执行频率，i为任务编号，j为处理器核编号；

计算各任务的在各处理器上的能量密度和各任务的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；/>为任务τ_i在处理器核π^j上的能耗，β^j为处理器核π^j的架构系数，p_i为任务τ_i的执行周期；

依次选择能量密度差最大的未分配任务τ_i，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，将所述τ_i分配给一个与该任务资源相似度最大且/>不大于1的处理器核；否则将τ_i分配给EU^j最小的处理器核；

更新所述处理器核的EU^j；

其中，所述EU^j为处理器核π^j当前的总最差估计利用率，所述为任务τ_i在该处理器核上的最差估计利用率，所述/>为任务τ_i分配前已分配在该处理器核上的任务的最差估计利用率。

进一步的，所述将所述τ_i分配给一个与该任务资源相似度最大且不大于1的处理器核包括：

在与该任务资源相似度最大且不大于1的处理器核中，选择/>最小的处理器核，将任务τ_i分配到该处理器核上。

进一步的，所述更新所述处理器核的EU^j包括：

更新τ_i在该处理核上的最差估计利用率

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；BW_i ^j为任务τ_i访问其共享资源子集的实际全局等待时间之和；

计算该处理器核的总最差估计利用率EU^j，

进一步的，所述方法还包括设置各处理器核的最终执行频率

计算处理器核π^j的利用率U^j；

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。

如果处理器核π^j的利用率不大于1，将处理器核的执行频率降低一级，重新计算所述利用率；

如果处理器核π^j的利用率大于1，将处理器核的执行频率升高一级，作为该处理器核的最终执行频率/>

本发明的基于共享资源访问的异构多核系统任务分配装置包括：

任务执行时间计算模块，用于计算各任务在各处理器核上的实际执行时间；

其中，T_i ^j为任务τ_i在处理器核π^j上的实际执行时间；表示任务τ_i访问其共享资源子集的最坏情况执行时间之和，/>表示任务τ_i的临界区个数，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间；

能量密度差值计算模块，用于计算各任务在各处理器上的能量密度和各任务的能量密度差值DD_i；

任务选择模块，用于在未分配任务中选择能量密度差值最大的任务τ_i，发送给任务分配模块；

任务分配模块，用于将所述任务τ_i分配给可选处理器核中与该任务资源相似度最大的处理器核。

进一步的，所述能量密度差值计算模块包括：

能耗计算单元，用于计算各任务τ_i在各处理器核π^j上的能耗

能量密度计算单元，用于计算τ_i的在各处理器核上的能量密度

能量密度差计算单元，用于计算任务τ_i的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；

进一步的，所述任务分配模块包括：

任务最差估计利用率计算单元，用于计算任务τ_i在各处理器核上的最差估计利用率

其中BW_i ^max为任务τ_i访问该任务访问的共享资源子集γ_i的最坏情况最长等待时间之和；

任务分配单元，用于根据各处理器核中与任务τ_i的资源相似度和各处理器核总最差估计利用率EU^j为所述任务τ_i分配处理器核；

具体分配方法为，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，将所述τ_i分配给一个与该任务资源相似度最大且不大于1的处理器核；否则将τ_i分配给EU^j最小的处理器核；

总最差估计利用率计算单元，用于更新各处理器核的总最差估计利用率；

进一步的，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，所述任务分配单元将所述任务τ_i分配给与该任务资源相似度最大且不大于1的处理器核中/>最小的处理器核。

进一步的，所述任务分配模块还包括：

任务最差利用率更新单元，用于在将任务分配到处理器核后更新该任务在其所分配的处理核上的最差估计利用率发送所述更新后的最差估计利用率到所述总最差估计利用率计算单元计算所述处理器核的总最差估计利用率；

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；临界区表示任务访问共享资源的程序段；BW_i ^j表示任务τ_i访问其共享资源子集的实际全局等待时间之和。

进一步的，所述装置还包括：

最终执行频率设置模块，用于设置各处理器核的最终执行频率包括：

利用率计算单元，用于计算各处理器核的利用率U^j；

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。

处理器核频率设置单元，用于根据各处理器核的利用率设置各处理器核的最终执行频率；

如果处理器核的利用率不大于1，将该处理器核的执行频率降低一级；将更新后的执行频率发送给利用率计算单元计算处理器的利用率；

如果处理器核的利用率大于1，将处理器核的执行频率升高一级，作为该处理器核的最终执行频率

附图说明

图1是本发明具体实施例1基于共享资源访问的异构多核系统任务分配方法流程图；

图2是本发明具体实施例2基于共享资源访问的异构多核系统任务分配装置结构示意图；

图3是本发明具体实施例2能量密度差值计算模块结构示意图；

图4是本发明具体实施例2任务分配模块结构示意图；

图5是本发明具体实施例2最终执行频率设置模块结构示意图；

图6是本发明技术方案与现有技术方案在各任务临界区比率下可调度率对比图；

图7是本发明技术方案与现有技术方案相比的能耗优化图；

具体实施方式

为了更好的说明本发明的技术方案，下面结合附图对本发明的具体实施方式进行详细描述。

本发明下述具体实施例中，系统有J个处理器核π＝{π¹，π²，...，π^J}，J为处理器核总数量；需要分配的任务集合τ＝{τ₁,τ₂,…,τ_I}，i为任务编号，i∈[1,I]，其中I表示任务总数量；任务各自执行的截止期限为D_i，执行周期p_i，任务之间相互独立，所有任务在同一时间点0时刻开始释放。各处理器核的可运行频率集合为j∈[1,J]，其中，j为处理器核编号，执行频率升序排列，其中f₁ ^j是处理器π^j的最低可选执行频率，/>是处理器π^j的最高可选执行频率。

为任务τ_i在处理器核π^j上的最坏情况执行时间；/>为任务τ_i在处理器核π^j上的执行效率；所述β_j为处理器核π^j的架构系数，其取值为与处理器设计和工艺相关的常量值；处理器核的总执行时间为分配给该处理器核的各任务在该处理器核上的执行时间之和。

本发明的下述具体实施例中，所述任务访问共享资源采用基于挂起的资源访问协议规则，具体规则可参见吴小东2012年发表的华中科技大学博士学位论文《基于电压岛的多核实时系统中同步任务节能调度策略研究》(万方数据2013年05月16日在线出版)。

系统的共享资源集合为γ＝{R₁,R₂,…,R_r},其中包含r个共享资源，所有任务均可访问，任务集合τ＝{τ₁,τ₂,…,τ_I}，处理器核集合π＝{π¹，π²，…，π^J}，Z_i,χ表示任务τ_i的第χ个临界区(临界区表示任务访问共享资源的程序段)，R(z_i,χ)表示临界区Z_i,χ对应的共享资源，基于分区最早截止时间优先(简称，EDF)任务调度。根据所述协议规则，任务τ_i在处理器核π^j上被阻塞有两种情况：

第一种，任务τ_i执行临界区Z_i,χ欲访问资源R(z_i,χ)时，资源R(z_i,χ)正在被其他核上任务访问，此时任务τ_i被加入到R(z_i,χ)的FIFO队列中，这个时间被称为访问资源R(z_i,χ)的全局等待时间(简称，BW_i,χ)；

第二种，处理器核π^j上任务τ_i欲访问某个资源时，同一个核上一个优先级低于任务T_i的任务正在访问其他资源，或者该低优先级任务提出访问资源的请求，但是其所申请的资源正在被其他核的任务访问而将该低优先级任务放置到其资源FIFO队列中，此时任务τ_i会被该低优先级任务阻塞，这种等待时间称为本地等待时间(简称，B_i)。

任意时刻一个处理器核上最多只有一个任务处于正在访问资源或者正在资源FIFO队列中等待资源释放的状态；任何一个任务至多只会被同一个处理器核上的更低优先级任务阻塞一次；任务本地等待时间的上限为同一个处理器核上更低优先级任务访问一次资源的最长时间(此时间包含了低优先级任务访问资源的全局等待时间)。

具体实施例1

本实施例为本发明基于共享资源访问的异构多核系统任务分配方法的一种优选实施方式。

参见图1，如图1所示，本实施例的方法包括：

S101、系统上电启动，一个周期任务集合τ＝{τ₁,τ₂,…,τ_I}分配到系统；

S102、设置各处理器核的执行频率

S103、计算各任务在各处理器核上的实际执行时间和最坏情况执行时间；

其中，T_i ^j为任务τ_i在处理器核π^j上的实际执行时间；表示任务τ_i访问其共享资源子集的最坏情况执行时间之和，/>表示任务τ_i的临界区个数，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间；

重复执行本步骤，计算得到任务在各个处理器核上的实际执行时间；

S104、计算各任务的能量密度差值；

本步骤进一步包括：

S1041、计算任务τ_i在处理器核π^j上的能耗

S1042、重复步骤S1041获得任务τ_i在所有处理器核上的能耗；

S1043、计算τ_i的在各处理器核上的能量密度

S1044、计算任务τ_i的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；

对各任务分别执行步骤S1041～S1044，获得各任务的能量密度差值；

S105、根据各任务的能量密度差值大小对任务进行降序排列；获得第一任务列表；

S106、选择第一任务列表中能量密度差值最大的未分配任务τ_i；

S107、将τ_i分配给可选处理器核中与该任务资源相似度最大的处理器核；

本步骤可进一步包括：

S1071、计算该任务与各处理器核的资源相似度

其中，其中，q为处理器核π^j上已分配任务的编号，τ_q为已分配到处理器核π^j上的任务；Ψ^j表示处理器核π^j上已分配的任务集；Θ_i,q为任务τ_i与任务τ_q访问相同类型的共享资源的个数；

S1072、计算任务τ_i在各处理器核上的最差估计利用率

其中BW_i ^max为任务τ_i访问该任务访问的共享资源子集γ_i的最坏情况最长等待时间之和；

S1073、判断最大的处理器核中，是否有/>不大于1的处理器核，如果是，执行步骤S1074，否则执行步骤S1075；

其中，EU^j为处理器核π^j当前的总最差估计利用率，为已分配到处理器核π^j上的任务τ_q的最差估计利用率；

S1074、将任务τ_i分配到一个最大且/>不大于1的处理器核上；执行步骤108；

作为本实施例的一种优选实现方案，本步骤可以进一步包括：

在最大的处理器核且EU^j不大于1的处理器核中，选择/>最小的处理器核，将任务τ_i分配到该处理器核上；

S1075、将任务τ_i分配到EU^j最小的处理器核上；

S108、更新该处理器核的总最差估计利用率

重复步骤S107～S108直到完成所有任务分配。

作为本实施例的一种优选实现方案，所述步骤S108可以包括；

S1081、更新各任务在该任务所分配的处理核π^j上的最差估计利用率

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；临界区表示任务访问共享资源的程序段；BW_i ^j表示任务τ_i访问其共享资源子集的实际全局等待时间之和；

S1082、计算该处理器核的总最差估计利用率；

作为本实施例的一种优选实现方案，本实施例还可以包括步骤S109。

S109、设置各处理器核的最终执行频率

S1091、计算任务τ_i在其所分配的处理器核π^j上的本地等待时间B_i；

其中，表示任务τ_m,m≠i在临界区Z_m,χ的最坏情况执行时间；Z_m,χ表示任务τ_m的第χ个临界区；/>表示任务τ_m在π^j中的执行效率，/>表示任务τ_m访问资源R(z_m,χ)时的最坏情况全局等待时间；max{}表示取最大值。

S1092、计算处理器核π^j的利用率U^j；

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。

S1093、判断处理器核π^j的U^j是否不大于1，如果是，执行步骤1094，否则执行步骤1095；

S1094、将处理器核的执行频率降低一级；执行步骤S1091；

S1095、将处理器核的执行频率升高一级，作为该处理器核的最终执行频率

重复执行步骤S109直到完成所有处理器核的频率设置。

具体实施例2

本实施例为本发明基于共享资源访问的异构多核系统任务分配装置的一种优选实施方式。

参见图2，如图2所示，本实施例的装置包括：

任务执行时间计算模块，用于计算各任务在各处理器核上的实际执行时间；

其中，T_i ^j为任务τ_i在处理器核π^j上的实际执行时间；表示任务τ_i访问其共享资源子集的最坏情况执行时间之和，/>表示任务τ_i的临界区个数，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间；

能量密度差值计算模块，用于计算各任务的能量密度差值DD_i；

参见图3.如图3所示，本模块进一步包括：

能耗计算单元，用于计算各任务τ_i在各处理器核π^j上的能耗

能量密度计算单元，用于计算τ_i的在各处理器核上的能量密度

能量密度差计算单元，用于计算任务τ_i的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；

任务选择模块，用于在未分配任务中选择能量密度差值最大的任务τ_i，发送给任务分配模块；

任务分配模块，用于将所述任务τ_i分配给可选处理器核中与该任务资源相似度最大的处理器核；

参见图4，如图4所示，本模块进一步包括：

资源相似度计算单元，用于计算所述任务τ_i与各处理器核的资源相似度

其中，其中，q为处理器核π^j上已分配任务的编号，τ_q为已分配到处理器核π^j上的任务；Ψ^j表示处理器核π^j上已分配的任务集；Θ_i,q为任务τ_i与任务τ_q访问相同类型的共享资源的个数；

任务最差估计利用率计算单元，用于计算任务τ_i在各处理器核上的最差估计利用率

其中BW_i ^max为任务τ_i访问该任务访问的共享资源子集γ_i的最坏情况最长等待时间之和；

任务分配单元，用于根据所述和处理器的各处理器核总最差估计利用率EU^j为所述任务τ_i分配处理器核，具体分配方法为：

判断最大的处理器核中，是否有/>不大于1的处理器核，如果是，将所述任务τ_i分配到一个/>最大且EU^j不大于1的处理器核上；否则，将所述任务τ_i分配到EU^j最小的处理器核上；

其中，所述为已分配到处理器核j上的任务τ_q的最差估计利用率；

作为本实施例的一种优选实现方案，如果在最大的处理器核中，有不大于1的处理器核，所述任务分配单元将所述任务τ_i分配到/>最大且EU^j不大于1的处理器核中/>最小的处理器核上；

总最差估计利用率计算单元，用于更新各处理器核的总最差估计利用率；

作为本实施例的一种优选实现方案，所述任务分配模块还可以包括：

任务最差利用率更新单元，用于在将任务分配到处理器核后更新该任务在其所分配的处理核上的最差估计利用率发送所述更新后的最差估计利用率到所述总最差估计利用率计算单元计算所述处理器核的总最差估计利用率；

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；临界区表示任务访问共享资源的程序段；BW_i ^j表示任务τ_i访问其共享资源子集的实际全局等待时间之和；

作为本实施例的一种优选实现方案，所述装置还可以包括：

最终执行频率设置模块，用于设置各处理器核的最终执行频率参见图5，如图5所示，所述最终执行频率设置模块包括：

任务本地等待时间计算单元，用于计算各任务在其所分配的处理器核上的本地等待时间B_i；

其中，表示任务τ_m,q≠i在临界区Z_m,χ的最坏情况执行时间；Z_m,χ表示任务τ_m的第χ个临界区；/>表示任务τ_m在π^j中的执行效率，/>表示任务τ_m访问资源R(z_m,χ)时的最坏情况全局等待时间；max{}表示取最大值。

利用率计算单元，用于计算各处理器核的利用率U^j；

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。

处理器核频率设置单元，用于根据各处理器核的利用率设置各处理器核的最终执行频率；

如果处理器核的利用率不大于1，将该处理器核的执行频率降低一级；将更新后的执行频率发送给利用率计算单元计算处理器的利用率；

如果处理器核的利用率大于1，将处理器核的执行频率升高一级，作为该处理器核的最终执行频率

在本发明上述具体实施例的技术方案中，在进行任务分配时，综合考虑了各任务在异构处理器不同核上的能耗不同，根据各任务的能量密度差设置任务分配的先后顺序，优先分配能量密度差大的任务，在任务分配的准备阶段就综合考虑了系统能耗问题，与现有技术方案相比，能有效降低任务分配后系统的能耗。在本具体实施的一种优选实现方案中，在完成任务分配后，根据任务访问共享资源的实际全局等待时间对各任务的最差估计利用率进行更新，使得任务分配过程中所使用的最差估计利用率和处理器核的利用率的计算更加准确，与现有技术相比，增加了任务集的调度成功率，参见图6，如图6所示，本发明的技术方案与现有技术相比，在各个临界区比率下可调度率平均高约8％。在本具体实施的另一种优选实现方案中，在任务分配完成后，根据各处理器核的利用率，在保证任务执行的实时性的考虑下，采用动态电压频率调整技术，不断的尝试降低处理器核的执行频率，使得系统利用率尽可能逼近1，减少处理器核的执行空闲时间，进一步减少了系统处理器核的功率消耗，参见图7，如图7所示，于现有技术相比，本发明技术方案在周期范围[50,100]低周期下，能耗优化约为6.8％；在周期范围[100,200]中周期下，能耗优化约为7.8％；在周期范围[200,400]高周期下，能耗优化约为8.4％。

Claims (10)

1.一种基于共享资源访问的异构多核系统任务分配方法，其特征在于，包括：

计算各任务在各处理器核上的最坏情况执行时间和实际执行时间T_i ^j；

其中，表示任务τ_i的临界区个数，χ为临界区编号，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间，为处理器核π^j当前的执行频率，i为任务编号，j为处理器核编号；

计算各任务的在各处理器上的能量密度和各任务的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；/>为任务τ_i在处理器核π^j上的能耗，β^j为处理器核π^j的架构系数，p_i为任务τ_i的执行周期；

依次选择能量密度差最大的未分配任务τ_i，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，将所述τ_i分配给一个与该任务资源相似度最大且/>不大于1的处理器核；否则将τ_i分配给EU^j最小的处理器核；

更新所述处理器核的EU^j；

其中，所述EU^j为处理器核π^j当前的总最差估计利用率，所述为任务τ_i在该处理器核上的最差估计利用率，所述/>为任务τ_i分配前已分配在该处理器核上的任务的最差估计利用率。

2.根据权利要求1所述的方法，其特征在于，所述将所述τ_i分配给一个与该任务资源相似度最大且不大于1的处理器核包括：

在与该任务资源相似度最大且不大于1的处理器核中，选择/>最小的处理器核，将任务τ_i分配到该处理器核上。

3.根据权利要求1所述的方法，其特征在于，所述更新所述处理器核的EU^j包括：

更新τ_i在该处理核上的最差估计利用率

计算该处理器核的总最差估计利用率EU^j，

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；为任务τ_i访问其共享资源子集的实际全局等待时间之和。

4.根据权利要求1～3中任一项所述的方法，其特征在于，所述方法还包括设置各处理器核的最终执行频率

计算处理器核π^j的利用率U^j；

如果处理器核π^j的利用率不大于1，将处理器核的执行频率降低一级，重新计算所述利用率；

如果处理器核π^j的利用率大于1，将处理器核的执行频率升高一级，作为该处理器核的最终执行频率/>

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。

5.一种基于共享资源访问的异构多核系统任务分配装置，其特征在于，包括：

任务执行时间计算模块，用于计算各任务在各处理器核上的最坏情况执行时间和实际执行时间T_i ^j；

其中，表示任务τ_i的临界区个数，χ为临界区编号，/>表示任务τ_i的第χ个临界区的访问其共享资源最坏情况执行时间，/>表示任务τ_i非访问共享资源最坏情况执行时间，为处理器核π^j当前的执行频率，i为任务编号，j为处理器核编号；

能量密度差值计算模块，用于计算各任务在各处理器上的能量密度和各任务的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度；/>为任务τ_i在处理器核π^j上的能耗，β^j为处理器核π^j的架构系数，p_i为任务τ_i的执行周期；

任务选择模块，用于在未分配任务中选择能量密度差值最大的任务τ_i，发送给任务分配模块；

任务分配模块，用于将所述任务τ_i分配给可选处理器核中与该任务资源相似度最大的处理器核；

依次选择能量密度差最大的未分配任务τ_i，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，将所述τ_i分配给一个与该任务资源相似度最大且/>不大于1的处理器核；否则将τ_i分配给EU^j最小的处理器核；

更新所述处理器核的EU^j；

其中，所述EU^j为处理器核π^j当前的总最差估计利用率，所述为任务τ_i在该处理器核上的最差估计利用率，所述/>为任务τ_i分配前已分配在该处理器核上的任务的最差估计利用率。

6.根据权利要求5所述的装置，其特征在于，所述能量密度差值计算模块包括：

能耗计算单元，用于计算各任务τ_i在各处理器核π^j上的能耗

能量密度计算单元，用于计算τ_i的在各处理器核上的能量密度

能量密度差计算单元，用于计算任务τ_i的能量密度差值DD_i；

其中，为/>中的最高能量密度，/>为/>中的最低能量密度。

7.根据权利要求5所述的装置，其特征在于，所述任务分配模块包括：

任务最差估计利用率计算单元，用于计算任务τ_i在各处理器核上的最差估计利用率

其中为任务τ_i访问该任务访问的共享资源子集γ_i的最坏情况最长等待时间之和；

任务分配单元，用于根据各处理器核中与任务τ_i的资源相似度和各处理器核总最差估计利用率EU^j为所述任务τ_i分配处理器核；

具体分配方法为，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，将所述τ_i分配给一个与该任务资源相似度最大且/>不大于1的处理器核；否则将τ_i分配给EU^j最小的处理器核；

总最差估计利用率计算单元，用于更新各处理器核的总最差估计利用率；

。

8.根据权利要求7所述的装置，其特征在于：

所述任务分配单元为所述任务τ_i分配处理器核时，如果在与所述任务τ_i资源相似度最大的处理器核中，有不大于1的处理器核，所述任务分配单元将所述任务τ_i分配给与该任务资源相似度最大且/>不大于1的处理器核中/>最小的处理器核。

9.根据权利要求7所述的装置，其特征在于，所述任务分配模块还包括：

任务最差利用率更新单元，用于在将任务分配到处理器核后更新该任务在其所分配的处理核上的最差估计利用率发送所述更新后的最差估计利用率到所述总最差估计利用率计算单元计算所述处理器核的总最差估计利用率；

其中，SW_i,χ为在任务τ_i之后进入共享资源R(z_i,χ)等待队列的任务所在处理器核中的所有任务访问该共享资源的最长时间之和；为τ_i的临界区数量，χ为τ_i的临界区编号；临界区表示任务访问共享资源的程序段；BW_i ^j表示任务τ_i访问其共享资源子集的实际全局等待时间之和。

10.根据权利要求5～9中任一项所述的装置，所述装置还包括：

最终执行频率设置模块，用于设置各处理器核的最终执行频率包括；

利用率计算单元，用于计算各处理器核的利用率U^j；

处理器核频率设置单元，用于根据各处理器核的利用率设置各处理器核的最终执行频率；

如果处理器核的利用率不大于1，将该处理器核的执行频率降低一级；将更新后的执行频率发送给利用率计算单元计算处理器的利用率；

如果处理器核的利用率大于1，将处理器核的执行频率升高一级，作为该处理器核的最终执行频率

其中，τ_n为分配在处理器核π^j上的任务；τ_n在π^j上实际执行时间B_i为任务τ_i在其所分配的处理器核π^j上的本地等待时间，/>为τ_n访问其共享资源子集的实际全局等待时间之和；/>表示表示该处理器核执行各任务时的利用率中的最大值。