制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法

摘要

本发明提出了一种制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，包括以下步骤：根据任务调度策略，为任务集生成任务分配与调度实例；在考虑制程变异的前提下，对任务、PE和功耗进行建模，形成任务模型、PE模型和功耗模型，并进行后台配置，将任务分配与调度实例用调度列表和分支裁剪法进行模型转换；通过随机性模拟实现约束查询，并通过UPPAAL-SMC生成统计数据，得出任务分配与调度实例的性能产出；对比同一MPSoC架构或不同MPSoC架构下不同的任务调度策略生成的不同任务分配与调度实例的性能产出，评估任务调度策略，确定表现更优的MPSoC架构。MPSoC的设计者们可以借助本发明进行决策，在TAS策略与MPSoC的架构之间进行选择，以获得最佳的组合。

说明书

技术领域

本发明涉及一种制程变异下多核片上系统任务调度建模与评估方法，尤其涉及一种基于 UPPAAL-SMC(静态模型检验UPPAAL)的带有制程变异MPSoC的任务调度建模与评估方法。

背景技术

随着科技的高速发展，嵌入式系统正发挥着越来越重要的作用，近年来逐渐兴起的片上 系统(System-on-a-chip，SoC)便在嵌入式系统的领域内得到了广泛应用。人们要求嵌入式 设备有更多的功能、更高的性能，多核片上系统(Multiprocessor System-on-a-chip，MPSoC) 由此产生。

制程变异(Process Variation)是在集成电路制造过程中晶体管属性(长，宽，栅氧化 层厚度等)自然发生的变化，在工艺节点小于65nm时，影响越发明显。这也成为了集成电路 芯片性能提升的瓶颈之一。即使是同一流水线生产出的产品，在参数上还会存在微小的偏差， 而这些偏差将对MPSoC的性能与功耗产生显著的影响，使得MPSoC的表现与预期不完全相符， 从而进一步导致行为的不可预测性。

任务分配与调度(Task Allocation and Scheduling，TAS)是一个NP难问题。因为制程 变异的存在为MPSoC的性能与功耗带来较大的变化，在考虑到制程变异的因素时，传统的用来 产生可行解的最坏时间分析法已不再适用。对于MPSoC的设计者来说，很难决定在特定的约束 条件下，哪种任务调度策略更好。为了保障调度算法的性能产出(Performance Yield)，对 任务调度算法的评估就成了一个重要的问题。

因此，构建一套制程变异下MPSoC任务调度算法的评估方法，有利于MPSoC设计者们将众 多调度策略进行对比，从而进行评估以选择适合的策略。

发明内容

本发明的目的是为了弥补当前考虑制程变异的多核片上系统中任务调度策略评估方面的 空白，提供了一种制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，实现了自 动将任务调度策略转换为模型的过程，并可以给出具有比较性的结果，从而实现对不同任务 调度策略的评估与对比。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，包括以下 步骤：

步骤一：根据任务调度策略，为任务集生成任务分配与调度实例；

步骤二：在考虑制程变异的前提下，对任务、PE和功耗进行建模，形成任务模型、PE模 型和功耗模型，并进行模型的后台配置，将所述任务分配与调度实例用已有的List  Scheduling(列表调度)和BULB(分支裁剪)算法进行模型转换；

步骤三：通过随机性模拟来实现约束查询，并通过UPPAAL-SMC(静态模型检验UPPAAL) 生成统计数据，得出所述任务分配与调度实例的性能产出；

步骤四：对比同一MPSoC架构或不同MPSoC架构下不同的所述任务调度策略生成的不同 所述任务分配与调度实例的所述性能产出，评估所述任务调度策略，确定表现更优的所述 MPSoC架构。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述任 务建模包括以下步骤：

步骤A1：运行初始化函数，对时间和功耗的制程变异进行初始化；

步骤A2：若任务不存在前驱节点，则执行下一步；否则，等待接收到所述前驱节点的完 成消息后，再执行下一步；

步骤A3：根据所述后台配置，将任务分配到相应的PE；

步骤A4：所述PE完成任务后，若没有后续结点，则结束运行；否则，继续运行所述后 续节点。

优选地，本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中， 所述任务建模没有对整个任务序列进行建模，而是对所有的任务节点进行了抽象与统一，对 单一任务节点进行建模，并根据前驱、后继节点的配置情况，通过同步信号将不同的任务连 接起来，按序执行，每个任务负责与前驱、后继节点的通信，以及对处理单元的分配，而任 务完成的时间由所述PE模型进行管理，初始节点根据读取所述后台配置中时间和功耗制程变 异信息作为参数，生成服从正态分布的随机数，对时间和功耗的制程变异进行初始化。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述 PE建模包括以下步骤：

步骤B1：记录要执行的任务的信息，根据制程变异确定所述任务实际需要的执行时间， 并更新所述功耗模型的功耗信息；

步骤B2：等待所述执行时间结束后，释放所述功耗模型中所占用的功耗，并更新所述功 耗信息。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述PE 模型中包括多个监听新任务消息的回路，有效地避免了所述PE模型接收不到新任务消息的情 况，实现了功能上的完整和语义上的完善。

优选地，本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中， 所述PE模型是对所有PE的抽象模型，通过所述后台配置来控制PE的表现，包括功耗、制程 变异等。所述PE模型通过与所述任务模型和所述功耗模型间的通信，控制任务的执行过程和 功耗信息的更新。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述功 耗模型对功耗进行监控与维护；所述功耗模型包括处理状态和等待状态，并在所述处理状态 和所述等待状态之间进行切换，在切换的过程中监听功耗信号。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述后 台配置包括：MPSoC的相关参数、设计约束、所述任务分配与调度实例的应用背景和至少一 个任务DAG。

优选地，本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中， 所述后台配置加入了时间和处理器功耗的制程变异的信息，作为框架的配置设定输入。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，所述约 束查询的形式如下：

Pr[<＝x](<>Task(0).Finish&&max_power<＝y)；

式中，Task(0).Finish表示：整个任务有向无环图的完成；max_power<＝y表示：最大 功耗不会超过y。

优选地，本发明的基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，只要调度算法 生成的结果包含任务id、开始时间、PE的id这三部分信息，框架即可将其转换为可被模型 识别的所述后台配置，转换工具使用转换算法确定任务的先后关系后，将其写入所述 UPPAAL-SMC的后台配置中。

优选地，在约束查询完成后，所述UPPAAL-SMC以图表或数据的方式给出运行的结果，通 过改变查询的内容，多次运行所述UPPAAL-SMC得出在不同的需求下，各所述任务分配与调度 实例的表现情况，从而在任务分配与调度策略与MPSoC的架构之间进行选择，以获得最佳的 组合。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法的有益效果 如下：本发明可以准确地反映任务分配与调度实例在工艺变动下的性能产出，帮助MPSoC设 计时可以选择适合的调度策略，或者根据调度策略对MPSoC的设计进行调整。

附图说明

图1为本发明任务分配与调度策略评估框架图。

图2为本发明基于UPPAAL-SMC的MPSoC任务调度建模与评估方法的流程图。

图3为本发明中对任务建模的示意图。

图4为本发明中对PE建模的示意图。

图5为本发明中对功耗建模的示意图。

具体实施方式

结合以下具体实施例和附图，对本发明作进一步的详细说明。实施本发明的过程、条件、 试验方法等，除以下专门提及的内容之外，均为本领域的普遍知识和公知常识，本发明没有 特别限制内容。

本发明提出了一种制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，参见图 1，本发明中任务分配与调度策略评估的框架图。

本发明框架接收配置设定作为输入，以及一个确定的任务分配与调度实例，将这些参数 应用到模型中，并多次运行查询语句，最终生成该任务分配与调度实例在输入参数的环境下 的稳定性表现(即性能产出)。其中，框架接收配置设定包括：

1)若干个任务DAG(Directed Acyclic Graph，有向无环图)：如果DAG超过1个，则多 个DAG在调度时必须映射到一个任务分配与调度实例上，即所有的任务DAG都在同一个调度中 执行；

2)MPSoC的相关参数：包括处理单元(PE)的个数、类型、额定功耗以及制程变异区间， 这些参数是与MPSoC相关的。其中，制程变异区间是一个正态分布的函数，框架会在运行时自 动从中选择值，该值作为MPSoC相对于额定功率的百分比，用户应该指定其方差；

3)设计约束：包括所有任务的完成时间、MPSoC的最大功耗，以及需要实现的性能产出 等。

统计模型检查(Statistical Model Checking，SMC)技术通过模型的随机运行来产生大 量的试验结果，并针对特定的查询约束建立统计结论。

本发明提出的制程变异下基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，对于给定的 一个调度策略，首先用该策略生成一个任务调度的实例，再将该实例转换成框架的输入参数； 框架接受这些输入参数，会将其转换为UPPAAL-SMC模型中的配置文件，并在模型中运行；再 通过给定的约束查询，就可以得出该调度策略在给定设计约束下的性能产出。

如图2所示，本发明的基于UPPAAL-SMC的MPSoC任务调度建模与评估方法包括：步骤一： 任务分配与调度实例生成步骤；步骤二：模型转换步骤；步骤三：查询生成步骤；步骤四： 任务分配与调度实例的分析与评估步骤。

其中，任务分配与调度实例生成步骤是对调度策略进行评估的首要操作，本步骤根据采 用的调度策略，在特定的MPSoC上，为给定的任务集生成任务分配与调度实例。

任务分配与调度实例生成后，即为给定的任务集生成任务分配与调度实例之后，执行模 型转换步骤，本步骤在考虑制程变异的前提下进行任务建模、PE建模和功耗建模，形成任务 模型、PE模型和功耗模型，并进行模型的后台配置，将任务分配与调度实例进行模型转换。

本发明的框架由两部分构成：前台模型和后台配置。前台模型包括了对任务、PE和功耗 的建模；后台配置包括了框架接收的配置设定参数，以及对任务分配与调度应用背景的描述。 后台配置控制所有结构性、逻辑性的信息，当UPPAAL-SMC对框架进行初始化时，会首先读取 配置部分，并将配置应用到任务分配与调度实例中，再执行约束查询，后台配置中的信息和 任务集、PE息息相关，决定着框架的运行过程。

如图3所示，本发明框架没有对整个任务序列进行建模，而是对所有的任务节点进行了抽 象与统一，对单一任务节点进行建模，并根据前驱、后继节点的配置情况。

任务从“初始”节点开始运行，并运行初始化函数(initialize()函数)，跳转到“准 备”节点。在initialize函数中，节点会首先读取后台配置，并判断自己的前驱、后继节点 的个数和序号；接着，节点判断自己是不是整个任务序列的初始节点，如果是，则根据后台 配置生成服从正态分布的随机数，对时间和功耗的制程变异进行初始化。本发明框架根据 Box-Muller算法，利用UPPAAL-SMC中提供的random函数，将其生成的平均分布随机数转换为 正态分布随机数。

到达“准备”节点后，任务对自身的前驱节点进行判断。如果不存在前驱节点(pre_num ＝＝0)，则跳转到“开始”节点；否则，跳转到“接收”节点，等待它的前驱节点完成并发 送消息；当start_task消息来到时，模型首先对消息进行选择，判断是否为任务通信类型 message_task_t；如果是，再调用is_this函数判断是否是自己的前驱节点发出的消息；如果 是，则将自己等待的前驱节点数减一，跳转到“开始”状态；然后，对其剩余前驱节点进行 判断，已决定继续等待接受消息或准备开始运行。

到达“开始”节点后，任务如果没有前驱节点，则从后台配置assigned中读取并判断本 任务应该被分配到哪个PE上，接着向目标PE发送分配消息(assign_proc)，通知目标PE本任 务将要执行，并跳转到“运行”状态。

到达“运行”节点后，任务进入了等待状态。此时，该任务将等待执行者PE完成任务， 并发送finish_task(任务完成)信号；任务执行时间的流动由PE负责。当finish_task消息 到来时，模型判断是否是message_task_t，接着判断自己是否为消息的接收者，如果是，则 跳转到“完成”节点。

到达“完成”节点后，任务会判断自己是否存在后继节点，如果没有则会跳转到“终止” 节点，结束自身的运行；如果该任务存在后继节点，则会跳转到“发送”节点，并进入一个 循环；当任务的剩余后继节点大于0时，任务会在每次循环中发送start_task(任务开始)消 息，通知其后继节点可以开始运行，并更新自己的后继节点计数器。

如图4所示，本发明中，PE模型是对所有PE的抽象模型，通过后台配置来控制PE的表现， 包括功耗、制程变异等。PE模型的初始节点为“开始”，处于“开始”节点时，Processor (处理器)首先调用queue_empty函数对队列进行判断，如果队列为空，即当前该Processor 并没有接到任何任务请求，则进入下方的“等待”节点；如果队列不为空，则跳转到“运行” 节点，并读取队列中的头部任务，对sid(安全标识符)、tid(线程控制符)、real_time_cost (实际执行时间)等进行更新，使sid和tid记录当前将要执行的任务的信息，real_time_cost 保存依据制程变异计算出的实际完成时间，为“运行”节点执行任务做准备。同时，PE模型 发出一个request_power信号，告知功耗模型更新功耗情况；此外，如图所示，“开始”节点 包含了一个自循环的有向边，该边的状态迁移在收到assign_proc信号时触发，首先对消息进 行选择，判断是否为message_proc_t类型的信号，再判断自己是否为该消息的接收者，如果 是，则将其加入自己的任务队列。类似的自循环边在“等待”、“运行”、“完成”节点均 有体现。在“开始”节点，Processor判断队列是否为空，并进行相应动作，同时监听assign_proc 信号。

当Processor到达“运行”节点时，会在该节点停留固定的时间，这一点通过不变式和跳 转条件的组合来实现。而在状态迁移的同时，Processor发送一个finish_task信号，携带目 标任务的sid和tid，告知相关任务模型运行已结束，使目标任务从“运行”节点迁移到“完 成”节点，与此同时，“运行”节点在迁移时还对任务队列执行出队操作，更新了任务队列。 从语义上来讲，“运行”节点负责队列头部任务的运行，根据额定时间和制程变异确定实际 执行时间，并在时间结束后发送消息，通知任务。此外，“运行”节点也存在一个环路来监 听任务模型发来的assign_proc消息。

“完成”节点作为一个中间节点存在，由于UPPAAL-SMC禁止在同一个状态迁移边上设定 两个不同的同步值，因此让Processor首先到达“完成”节点，再从“完成”节点迁移到“开 始”节点，完成其一次完整的任务执行过程。在从“完成”节点迁移到“开始”节点的过程 中，Processor发出一个free_power信号，通知功耗模型释放Processor占用的功耗，更新功 耗的信息。

PE模型通过与任务模型和功耗模型间的通信，控制任务的执行过程，与功耗信息的更新， 是整个框架中动态性较强的模型。在模型中包括了多个监听新任务消息的回路，增加了一些 语法上的冗余，但是有效地避免了PE模型接收不到新任务消息的情况，实现了功能上的完整 和语义上的完善。

如图5所示，功耗模型负责对功耗的情况进行监控与维护，包含“处理”和“等待”两个 节点。功耗模型初始处于“处理”状态，而在“处理”和“等待”状态时，都接收两种信号， 分别是：request_power(供电需求)和free_power。当功耗模型接到request_power的信号 时，它会根据发送者的pid，调用power_alloc函数，增加当前功耗current_power，并且， 如果当前的功耗大于历史最大功耗(current_power≥max_power)，则更新max_power；当 功耗模型接到free_power的信号时，根据发送者的pid，调用power_free函数，减少当前功 耗。

当功耗模型处于“处理”状态，并没有收到信号时，跳转到“等待”状态；当功耗模型 处于“等待”状态收到信号时，跳转到“处理”状态。功耗模型在两个状态之间进行切换， 并在切换的过程中完成对功耗信号的监听。验证时，只需要比较max_power与设计约束，就可 以实现对功耗约束的判断。

本发明提出的基于UPPAAL-SMC的MPSoC任务调度建模与评估方法中，当针对特定的MPSoC 设计约束和资源情况，按照特定的调度算法产生了任务调度后，需按照所选的List  Scheduling(列表调度)和BULB(分支裁剪)算法将其转换为模型的后台配置，从而控制前 台模型产生不同的行为。

本发明框架包含了一个模型后台配置转换器，只要调度算法生成的结果包含任务id、开 始时间、PE的id这三部分信息，框架即可将其转换为可以被模型识别的后台配置。

在模型中，所有的任务先后顺序都通过依赖关系来表示，根据具体的任务调度，为原有 的任务依赖关系添加新的依赖。通过转换工具，可以将任务之间的先后关系确定下来，并使 用框架中的工具写入UPPAAL-SMC的后台配置中；任务的额定执行时间与PE的功耗属性，可以 直接写入全局数组中；其他的转换过程与上述过程类似，不再赘述。

模型转换步骤完成后，执行查询生成步骤，通过随机性模拟来实现约束查询，并由 UPPAAL-SMC生成统计数据。当使用不同的任务分配与调度实例来生成价格时间自动机网络 (Network of Priced Timed Automata，NPTA)模型时，需要比较不同任务分配与调度实例 的性能产出，根据设计约束生成许多不同的查询供UPPAAL-SMC进行验证。在UPPAAL-SMC中， 采用了如下形式的查询：

Pr[<＝x](<>Task(0).Finish&&max_power<＝y)；

其中，Task(0).Finish表示整个任务有向无环图(Directed Acyclic Graph,DAG)的完 成；max_power<＝y表示最大功耗不会超过y。

在UPPAAL-SMC中，约束查询是通过多次随机模拟来完成的；在每一次模拟完成后， UPPAAL-SMC都会验证当前约束是否得到满足，并给出统计数据。当所有随机性模拟完成后， UPPAAL-SMC会自动生成统计数据，可以根据这些统计数据，判断调度策略的优劣。

在约束查询完成后，UPPAAL-SMC生成本次运行的统计信息，并以图表或数据的方式给出 运行的结果。通过改变查询的内容，可以多次运行UPPAAL-SMC以了解在不同的需求下，各任 务分配与调度实例的表现情况。

本发明方法可以对同一MPSoC环境下，不同的任务分配与调度策略生成的不同实例进行横 向对比，便于在确定了芯片设计的情况下选择适合的任务分配与调度策略；同样地，也可以 采用不同的MPSoC架构，分别在不同的架构上运行于不同的任务分配与调度策略，并通过对任 务分配与调度实例的对比，确定表现更优的MPSoC架构。通过将这两方面的评估与比较结合起 来，MPSoC的设计者们可以进行决策，在任务分配与调度策略与MPSoC的架构之间进行选择， 以获得最佳的组合。

本发明提出的基于UPPAAL-SMC的MPSoC任务调度建模与评估方法，根据给定MPSoC的相关 信息以及调度策略，本发明可以有效地根据调度策略生成的不同TAS对调度策略进行对比，也 可以用来对不同的TAS实例进行比较。直觉评估在不考虑制程变异情况下可以产生最优解的调 度策略，在考虑制程变异情况下未必就是最优的选择；而对于MPSoC的设计者来说，本发明可 以在考虑制程变异情况下选择调度策略时，针对不同的MPSoC采用特定的策略，根据实验数据 与实际情况选择最优的组合，使性能产出最大化。

本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下，本领域技术 人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保护范围。