一种基于模型和动态分析的多核系统实时性评估方法

摘要

本发明公开了一种基于模型和动态分析的多核系统实时性评估方法，属于嵌入式多核系统实时性评估技术领域；该方法首先获得嵌入式多核系统的资源参数，明确任务的产生方式，对共享资源SoC片上的BUS的使用状态，及任务对共享资源使用状态相互之间的关系。然后建立petri‑net模型，计算模拟cache命中率。总线空闲时接收任务访问，总线忙碌时说明有任务在占用资源并且和资源同步处于该状态；任务读入的时间服从参数为λ的指数分布；任务隐式通信的时间长度是固定的，隐式通信的次数服从参数a,b的均匀分布。最后在设定的时间内运行模型，在运行过后进行实时性分析。本发明实时性评估结果更符合真实运行中的情况，客观化、直观化的给出多核IMA任务的执行模型。

说明书

技术领域

本发明属于嵌入式多核系统实时性评估技术领域，涉及一种基于模型和动态分析的多核系统实时性评估方法。

背景技术

综合化模块化航空电子系统IMA(Integrated Modular Avionics)综合的层次可以分为三层结构，即资源综合、功能综合以及管理综合。

资源综合包括物理综合以及数据综合，物理综合是指针对整个航空电子系统结构中的设备资源，如计算资源、网络通信资源以及IO资源进行综合，确立完整的航空电子分布式环境下设备资源分配方式，并在此基础上进行资源分配的分析以及评估，从而提升IMA系统的设计能力；而整个IMA系统底层存在大量数据资源，这些数据来源不同、意义不同、存储组织方式不同，甚至同类型数据的组织方式也不尽相同，因此需要制定统一的数据语义表示以及能力描述，并基于能力操作进行数据资源融合，为上层功能综合以及管理综合提供技术支撑。

功能即信息处理，是对一个或者多个资源状态进行改变的过程。功能综合的目的是在现有资源的基础之上提升系统效能，主要手段包括执行过程复用和结果共享。通过对上层应用进行功能分解，建立分类明确、过程规范、接口标准和结果通用的基本功能组件构建任务共享平台，并由统一的任务调度引擎执行任务调度，实现以最少的活动，为系统提供最强劲的效能服务，从而实现功能综合。

航空电子各系统功能，如导航、探测、大气数据、敌我识别、飞行管理、火力控制、显示控制等功能都是在现有资源和功能的基础之上通过协作完成。管理综合的目的就是通过综合管理，降低系统的缺陷、错误，有效地进行故障管理，从而提升系统有效性和稳定性。通过任务构建、功能组织、资源配置等操作，集成当前系统剩余有效能力，实现基于状态监控的任务、功能、资源的有机组织、从而提升系统整体效能。上述需求需要对系统范围内的所有资源、任务、功能进行统一管理、监控和配置，为满足飞行需求和作战任务定制有效的执行方案。

航空电子系统越来越复杂，综合程度越来越高。综合已从显示器推进到数据处理，又推进到传感器系统，在这样的系统中，对于系统计算能力的渴求也就变的越来越强烈。在消费电子领域的经验表明在处理器频率、制程处于瓶颈期的情况下，多核是提升处理器性能的重要方式。从另一个角度上讲，多核也体现了IMA综合层次中资源综合的重要发展前景。

多核系统在商用电子产品领域已经发展了多年。在处理器的处理频率和尺寸已经达到一个瓶颈的情况下，多核已经被实践证明是一个能够有效提高系统处理能力的发展方向。从IMA系统的角度上来说，多核的出现也是IMA系统资源融合一个重要的发展方向。在ARINC 653中描述的基本的分区和进程的概念是与被称为单核模块有关的硬件单元。多核处理器的认证还处在一个较为初步的情况，历史上经过认证的处理系统都是单核的系统。

目前，嵌入式多核系统由于cache命中率导致的任务执行时间不确定的情况，业界还没有给出良好的解决方案，该问题也是业界近年来研究的热点。

发明内容

本发明为了解决嵌入式多核系统在cache的命中率有限，导致任务的实时性不确定的问题，利用赋时petri网建模的方式对多核实时性评估，提出了一种基于模型的、针对芯片上共享IO资源的、动态分析的实时性评估方法。

本发明提供的基于模型和动态分析的多核系统实时性评估方法，包括以下步骤：

步骤1，获得嵌入式多核系统的资源参数，包括核心的数量、缓存命中率以及核心所共享的计算资源的类型；明确任务的产生方式；根据产生的任务，给定多核处理器的调度方式；给定IO的使用策略；明确任务对共享资源SoC片上的BUS的使用状态，以及任务对共享资源使用状态相互之间的关系。

步骤2，为嵌入式多核系统的任务执行过程建立petri-net模型，该模型包括四个部分：任务产生模块、任务的等待队列、任务的处理和服务模块、完成任务列表。

步骤3，通过下面公式来模拟cache命中率c_h；

其中，设总线读入阶段所占用的时间t_r服从参数为λ的指数分布，由于cache导致的总线隐式通信阶段所占用的时间t_ic服从参数为a,b的均匀分布。

步骤4，当总线处于空闲时能接收任务的访问，当总线处于忙碌时说明有任务在占用资源并且和资源同步处于该状态；当任务处于读入阶段时，读入的时间服从参数为λ的指数分布；当任务处于隐式通信阶段时，隐式通信的时间长度是固定的，隐式通信的次数服从参数a,b的均匀分布；

步骤5，在设定的时间内运行模型，在运行过后进行实时性分析。

步骤5进行实时性分析，包括：分析单个核的任务队列有没有产生阻塞情况；分析总的任务完成列表中的任务产生时间、任务完成时间、以及计算任务完成时间与任务产生时间的差值，分析该差值是否在增大，如果该差值没有增大，则统计该差值的数学期望和方差。

相对现有技术，本发明的优点和积极效果在于：

(1)一种基于赋时层次petri-net的模型构建方法，利用数学建模的方法，构建多核IMA任务处理模型，客观化，直观化的给出多核IMA任务的执行模型。

(2)一种基于cache命中率的，将cache命中率转化为核读取任务时长，cacherefill次数的cache命中率转化的方法，利用相关产生函数的数学期望分析情况以及相关的数学推演，将cache命中率对系统的影响结构化，模型化地体现在上述模型中，使得实时性评估结果更符合真实运行中的情况。

(3)一种基于模型的多核IMA任务实时性分析评估方法，通过给定一个较长的时间，动态运行上述模型，在任务执行过程中，动态地分析任务执行过程中的任务的阻塞情况。在任务执行后能够显示化，直观化的分析已完成任务的实时性分析。

附图说明

图1为一个多核共享内存处理器的硬件结构物理模型示意图；

图2为一个多核共享内存处理器的基于任务执行的时间分解示意图；

图3为本发明一种基于排队理论的任务产生和服务模型建模方法原理图；

图4为本发明一种基于排队理论的任务产生模型建模方法原理图；

图5为本发明运用统计理论和Bus调度策略为FIFO的任务处理模型建模方法原理图；

图6为本发明Bus调度策略为基于优先级调度的任务融合队列替换原理图；

具体实施方式

下面将结合附图对本发明的技术方案作进一步的详细说明。

本发明在为嵌入式多核系统的缓存建立模型时，需要确定和获取如下信息：

需要明确资源参数，包括计算核心的数量、缓存cache的命中率以及核心所共享的计算资源的类型等等。

需要明确任务的产生方式，任务的产生方式有两种，一种是给定任务集合，对于给定的任务集合分析该任务集合实时性的满足情况。第二种情况是任务的产生是随机的。在任务产生是随机的情况下，需要给定单位时间内任务到来的分布。如果不指定任务到来的分布，则默认采用泊松分布。

根据产生的任务，给定多核处理器的调度方式，例如共享时间(timesharing)的调度方式，共享空间的调度方式(space sharing)，集体调度(gang sharing)的方式。将上一步产生的任务，使用选定的调度方式进行调度，也就是选定任务要执行的核。

给定IO的使用策略，通常有三种：固定优先级别(Fixed Priority)，分时复用(Round Robin)，划分时间片(TDMA)。想要使用IO的任务来自于锁定要在核上运行的任务。

明确任务对共享资源片SoC上的BUS的使用状态，以及任务对共享资源使用状态相互之间的关系。任务对BUS的使用状态分为未使用(空闲)，读入，隐式通信和写出。未使用的状态会转移到写入的状态。写入的状态完毕之后会转移到隐式通信状态。隐式通信状态可以转移到写出阶段，隐式通信也有可能转移到隐式通信状态本身，写出状态会转移到空闲状态。

本发明实施例结合一个共享内存处理器来说明。在不同版本的多核处理器上，共享缓存级别可能不同。为了简单起见，本发明将描述一个具有一些关键要素的抽象模型的真实多核共享内存处理器。

如图1所示，核心(core)与1级缓存(Level1_cache)绑定，图1的示例中包含两个核心core1和core2。在整个模型中，核心和缓存总是被考虑在内。实际上，缓存的核心部分是下面描述的底层模型。一致性结构也被简化为共享总线(Shared Bus)，这是关键要素。外围设备和存储器通过共享总线与内存连接。值得注意的是，内存分为几个部分，包括core1的内存(Memory for core1)，core2的内存(Memory for core2)和共享内存(SharedMemory)。以不同的核心-缓存部分拥有不同的内存的方式，可以完成空间分离。共享内存用于信息交换。一个内核缓存部分写入共享内存，然后另一个内核缓存部分读取共享内存。对于设备，可以分为2类，一类是抢占设备(Preemptive devices)，另一类是非抢占设备(Non-preemptive devices)。抢占设备是在使用过程中无法接管的设备。如果违反原则，则会出现一些不可恢复的结果。

从顶层看，整个总线访问阶段可分为两个阶段，如图2所示。一个是调度阶段(schedule phase)，另一个是中断阶段(Interruption Phase)。在调度阶段，它包含几个块(block)，不同的块代表不同的任务。真正重要的是这些块的相对位置导致数据依赖，这对所真正关心的WCET(Worst-Case Execuion Time，最坏情况执行时间)有很大的影响。如果总线Bus时间表是在设计时确定的，现在已经有一些方法可以解决。中断阶段是应用于IMA系统时不能忽略的阶段。只有在中断阶段，IMA系统才能处理事件触发的任务。中断优先级与IMA系统的调度方案有关，受特定飞机的安全要求的影响。在每个调度块时间段内，访问阶段可以分为3个阶段：读取阶段(R)，执行阶段(TE)，写作阶段(W)。

在读取阶段，核心缓存部分通过显式通信(EC)从内存中检索信息。之后，核心缓存部分与内存进行隐式通信(IC)来执行本地任务。这里有一个问题。如果隐式通信仍然需要使用总线，则WCET无法特别适用于中断阶段。因为Bus的抢占必须导致以下任务的延迟。如果通过使用另一条总线进行这种特定的隐式通信，那么在一定程度上可能会违反商用货架产品(COTS,Commercial Off-The-Shelf)规则。为了规避这个问题，本发明假设核心缓存部分仅使用一条总线与内存进行通信。在读取阶段，核心缓存部分通过显式通信将信息设置到存储器。

在多核IMA的实时性分析评估阶段，通过对片上总线的调度模式的分析，并且对核的关键特征，cache的命中率等属性进行数学的形式化转化，在得到多核IMA任务处理构件的转化后模型后，利用基于模型的任务实时性统计分析评估的方法，对转化后的评估模型进行基于模型的任务实时性统计分析关键特征评估的实时性评估方法，形成了基于多核IMA体系结构的赋时层次petri-net模型的任务实时性评估方法。

本发明一种基于多核IMA体系结构的赋时层次petri-net模型实时性评估方法，如图3所示。本发明首先根据排队论的相关信息，任务产生和服务计算的相关关系，将系统划分为四个部分，分别为：任务产生模块Arrivals，任务等待队列Queue，任务的处理和服务模块CPU_Model，完成任务列表Completed。

任务有以下几种属性：

●JobType，表示任务(job)的类型，取决于job的优先级，数据类型为Int，取值为1或2；

●At，表示job的当前时间，数据类型为Int；

●Core，表示工作/任务将执行的核心，数据类型为Int；

●StartAt，表示job的开始时间，数据类型为Int；

●cacheMiss，表示cache的失效率，数据类型为Int；

●phase，表示工作/任务将遇到的下一个阶段，包括完成F，读取R，计算C，和写入W。

任务(Job)所有的过程，通过比较StartAt属性和At属性，很容易知道工作经历的时间跨度。

图3，图4，图5，图6都是用CPN tools软件制作的。

图3中，Arrivals代表任务产生模块，其功能是按一定的时间间隔，不断的产生任务。通过分层变迁Arrivals来产生任务。产生后的任务按照产生的先后顺序依次添加到任务队列Queue的尾部。任务处理和服务模块CPU_Model对Queue中的任务按特定的规则进行处理。处理过后的任务，最后进入到完成任务列表Completed中，以便分析。图3中1’[]标识该变迁的初始状态为一个空队列。

如图4所示，为任务产生模块Arrivals的建模方法。其中，Init库所和Init变迁是任务产生模块的使能模块，也就是控制整个任务产生模块工作的开始。Next_Job是一个任务产生间隔控制库所，能够通过入弧上的表达式来控制任务产生的时间间隔。Job_Arrival变迁是一个任务产生变迁，其有两个功能：一个是通过newjob()函数来产生新任务；另外一个是output()函数，其功能是输出任务。Job_Arrival与队列变迁相连，实现任务的输入。

图4中的()@+expTime(100)，是指任务产生的时间间隔是expTime(100)，而expTime(100)是一个函数，定义如下：

Real.fromInt mean表示将int类型的输入值mean转变为实数类型的值。

图4中的为jobs^^[job]代表将jobs这个队列与[job]这个队列进行合并，将元素job放在jobs队列的末尾

如图5是CPU_Model变迁的内部具体展示；具体步骤如下：

图5是关于如何处理一个任务，考虑到共享资源-BUS，两个核心与自己的缓存。要了解这个模式，不可避免的要一次来看整个模型。整个模型一个接一个地从队列Queue中接收任务。distributedTran变迁是一个分发者，可以通过任务的核心属性Core分配任务。如果作业的核心属性为1，则转发到核心1的分发库所core1distribute。变迁core1Q和库所core1QTran协同起来构成了核心1缓存core_cache_1的任务队列，确保任务是先来先服务(FIFO，First In First Out)。设置两个库所，忙碌busy库所和空闲idle库所，以及设置两个库所之间的变迁，空闲到忙碌变迁idleTobusy，以及忙碌到空闲变迁busyToidle。例如对于核心1，变迁core1idleTobusy、core1busyToidle和库所busy1、idle1。变迁core1idleTobusy，core1busyToidle和库所busy1，idle1组合完成只有一个功能，这个功能就是当一个job被core_cache_1处理时，拒绝任何其他任务被core_cache_1处理。为了实现这个功能，这四个东西的组合就像一个开关。当开关空闲时，允许接受令牌。接受令牌后，交换机进入忙碌状态。只有通过变迁jobcompT1完成job后，开关才能恢复到空闲状态。任务通过该变迁jobcompT1，代表任务被执行完了。jobcompT1表示核心1当前的任务执行完毕。值得注意的是，jobcompT1之间的弧与其他弧不同。这是一个继承约束弧，该弧的被指向端必须立即在该弧起始端之后执行。当job令牌位于core_cache_1的位置时，并不意味着job已经加载到core-cache中。这意味着这项job被core是抢占了。只有那些被抢占的job才有权排队Queue2，以便抢先访问总线资源。在本发明图1所示的简化模型中，只有2个核心，因此Queue2的最大长度为2。在这个模型中，总线的调度策略是“先到先服务”。

正如模型所示，该总线有四种状态是闲置(Idle)，读取(reading)，隐式通信(IC)和写入(writing)。与空闲相反，读入、IC和写出阶段被认为是忙碌。只有当总线空闲时，它才能被内核访问。Start变迁可以决定总线可以使用多长时间。当job令牌通过Start变迁时，它可以根据它所具有的phase属性来决定哪种方式。读入后，总线回到空闲状态。同时，job的阶段变为“C”，“C”表示计算。当job处于计算compute阶段时，使用总线的唯一情况就是隐式通信。在隐式通信之后，after_compute函数将改变该job的阶段。

整个模型的关键组件是Start变迁中的generateTime函数。缓存的命中率可能会影响任务执行的持续时间。缺少的部分必须通过总线获取。当发生这种情况时，总线处于隐式通信阶段。因此，命中率可以转换为在隐式通信阶段中job使用总线的次数。当job完成计算时，结果必须通过总线写入。当job通过总线写出时，总线在写入阶段。在撰写阶段之后，根据其核心属性重新分配该作业，以使得能够进行新的job进入。

如图6所示，任务在抢占Bus时，Bus的调度策略为基于优先级的调度策略时，队列2插入形式的替换建模。图6中，任务从wanna_use_bus库所出来，通过send变迁，利用优先级抢占的方式插入到Queue2当中。图6所描述的图可以用来替换图5当中wanna_use_bus到Queue2的部分，用以替换任务对核资源的使用方式。

关于描述的隐式通信状态的时间长短是和cache的命中率有一个函数关系，隐式通信状态的转移概率也和cache的命中率有一定的函数关系。而这两个关系都在generateTime函数中体现。

下面内容为generateTime函数的参数和形式推导：

总线在读入阶段读入的数据量为d_r，在隐式通信阶段读入的数据量为d_i，它们与cache命中率c_h的关系为

由于BUS的带宽是一定的，上面的公式可以化简为

其中，t_r为读入阶段所占用的时间，t_ic为隐式通信阶段所占用的时间。

在任务不确定的情况下，可以假设t_r服从参数为λ的指数分布，即：

由(3)得到t_r的数学期望为λ。

由于cache导致的隐式通信的时间长t_ic假设服从参数为a,b的均匀分布，即：

t_ic～U(a,b)(4)

由公式(2)可以得到：

再由得到t_r的数学期望为λ，t_ic的数学期望为(a+b)/2可以得到：

在模型当中，本发明通过控制参数a,b和指数分布的参数λ的满足公式(6)来实现模型对于cache命中率的模拟。

参数a,b在任务产生阶段产生，也就是有newJob函数来产生，newJob产生的任务的cache miss的次数均匀的取a,b之间的所有整数，包括a,b。而generateTime函数中对每一次cache miss时，对BUS的使用时间为一个时间单位；而对于generateTime读入阶段的时间，读入时长服从期望为λ的指数分布。如此就能够满足公式(6)。

下面给出一个示例：

任务产生的时间间隔是服从参数为200的指数分布。经过3154个时间单位，实验结果如下：

{jobType＝1,AT＝287,core＝1,startAT＝23}

{jobType＝1,AT＝961,core＝2,startAT＝839}

{jobType＝1,AT＝1847,core＝2,startAT＝1747}

{jobType＝1,AT＝2388,core＝2,startAT＝2272}

{jobType＝1,AT＝2618,core＝2,startAT＝2288}

{jobType＝1,AT＝2811,core＝2,startAT＝2378}

{jobType＝1,AT＝3132,core＝2,startAT＝2676}

{jobType＝2,AT＝1207,core＝1,startAT＝1058}

{jobType＝2,AT＝1537,core＝2,startAT＝1397}

{jobType＝2,AT＝2977,core＝1,startAT＝2605}

其中，At和startAT的单位是时间单位，取决于系统的设定。

在任务完成后，cacheMiss＝0，phase＝F是两个共有的信息，并且不是本发明关心的分析项，所以这些东西被省略。

任务之间的时间间隔是服从参数为100的指数分布。在3150个时间单位之后，在第765步，实验结果如下所示：

{jobType＝1，AT＝451，core＝1，startAT＝170}

{jobType＝1，AT＝634，core＝1，startAT＝314}

{jobType＝1，AT＝1222，core＝2，startAT＝689}

{jobType＝1，AT＝1274，core＝1，startAT＝822}

{jobType＝1，AT＝1818，core＝2，startAT＝1395}

{jobType＝1，AT＝2126，core＝2，startAT＝1582}

{jobType＝1，AT＝2618，core＝2，startAT＝1785}

{jobType＝2，AT＝613，core＝2，startAT＝368}

{jobType＝2，AT＝891，core＝2，startAT＝679}

{jobType＝2，AT＝1646，core＝1，startAT＝932}

{jobType＝2，AT＝1937，core＝1，startAT＝1104}

{jobType＝2，AT＝2361，core＝1，startAT＝1124}

{jobType＝2，AT＝2875，core＝1，startAT＝1554}

{jobType＝2，AT＝3150，core＝2，startAT＝2482}

比较上面两个的情况，不难推断，当任务之间的时间间隔是服从参数为100的指数分布时，AT-startAT正在增加，这表明任务被阻止。但是，当任务之间的时间间隔是服从参数为200的指数分布时，AT-startAT是稳定的。AT-startAT的平均值为248.2。

如上所述，当共享资源即总线的状态为空闲时，可以接受任务的访问，当处于忙碌时，说明有任务在占有共享资源并且和资源同步处于该状态。当任务处于读入阶段时，读入的时间服从参数为λ的指数分布；当任务处于隐式通信阶段时，隐式通信的时间长度是固定的。但是，隐式通信的次数服从参数a,b的均匀分布。其中参数a,b和λ应满足公式(6)。

在设定的运行时间内，运行本发明的petri-net模型，设置的运行时间应相对较长。在运行过后，分析单个核的任务队列有没有产生阻塞情况；分析总的任务完成列表中的任务产生时间、任务完成时间、以及计算任务完成时间与任务产生时间的差值。分析该差值是否在增大。如果该差值没有增大，则求出该差值的数学期望、方差等统计性数据。