论文部分内容阅读
由于单核处理器的时钟频率进一步增加会导致很大的功耗和严重的散热问题,芯片厂商和研究人员开始转向开发低频低压的多核平台。同时,由于核间通信、同步和存储访问的需求,片上多核处理器的通信骨架必须能够随着核的个数增加可扩展。否则,多核处理器的计算能力不能被充分使用而导致浪费。由于片上网络体系结构具备很好的可扩展性和很高的通信效率,而成为通信骨架的一个普遍方案。片上网络可以允许核间并行传输,并且硬件成本中等。由于实时并行应用(比如机器人、无人机和自动驾驶)的高性能需求,基于片上网络的多核处理器具备很高的并行处理能力而被广泛使用。对于映射到该多核平台的实时应用来说,实时保证是其最核心的需求,比如除了功能需求以外,还要求设定的截止时间需求被满足。尽管基于片上网络的多核处理器平台有强大的能力去执行实时应用,其上的软件并不能相当完全地被支持。对于片上网络上的实时系统,其中一个主要的挑战是在设计阶段可调度性测试时去评估实时任务的响应时间上界。而上界主要由采用的片上网络体系结构和相应的调度策略所决定。在当前的最新工作中,主要存在以下四个问题。首先,在广泛使用的优先级抢占的虫洞流控制的片上网络上,由于传统单跳片上网络的体系结构局限性,既有的实时分析已经达到瓶颈并很难进一步优化。具体来说,即使在无冲突的场景下截止时间仍有可能不被满足,特别是对于分配长路径的并且截止时间紧急的数据包流。同时,最新工作没有考虑优先级和虚拟信道的共享,以及更通用的任意截止时间的数据包流模型,这限制了实时分析模型的应用范围。第二,多核系统上广泛使用的动态调度器会在运行阶段发生时间异常现象。如果不解决时间异常现象,评估的响应时间上界将是不安全的,进而导致实时任务在运行阶段的不可调度性。第三,广泛使用的片上网络比如虫洞片上网络通常是为尽最大努力传输的通信任务和平均性能设计的,表现出很差的响应时间上界评估质量,得到的上界要么不安全要么悲观。第四,所有的最新工作几乎只是单方面地考虑了片上网络上计算任务或者通信任务,这种假设在大多数情况下是不符合实际场景的,这限制了提出的调度方法和相应实时分析模型的应用范围。为了解决以上提到的问题和挑战,本文通过以下三个步骤提出新的调度策略和相匹配的实时分析模型来获得安全和紧致的响应时间上界:在新兴的片上网络体系结构上建立实时分析模型,在多核处理器上设计安全的动态任务调度方法,以及更细粒度地同时考虑计算和通信任务的实时分析。和既有的最新工作相比,本文的工作通过引入新的片上网络体系结构、新的调度策略和新的实时分析模型来极大地提升了片上网络上实时系统的性能和安全性。具体来说,本文主要贡献如下:(1)本文引入了一种新兴的具有单周期多跳传输特性的片上网络,叫做SMART,来降低最坏传输延迟。为了使得SMART延迟可预测,结合单周期旁路转发技术,本文提出了一个基于优先级抢占的调度策略,允许冲突的数据包根据预先定义的优先级进行仲裁。基于该优先级抢占调度方案和给定数据包流的映射和优先级,本文通过考虑虚拟信道(和优先级)的共享和通用的任意截止时间的数据包流模型,然后提出了相应的实时通信分析模型来评估最坏传输延迟和验证可调度性。(2)对于多核平台上的实时DAG(directed acyclic graph)任务,本文提出了一个无时间异常的动态调度器来获得安全并紧致的时间上界。核心思路是在运行阶段调度DAG任务时,通过在DAG节点对于的作业之间插入某种调度限制来消除时间异常现象的发生。而安全的时间上界通过在设计阶段模拟DAG任务的运行时执行获得。应用该无时间异常的调度策略到含条件分支的DAG任务的主要挑战是,在运行阶段它会生成指数级个执行实例,需要指数级计算开销。为了解决这个问题,本文提出了有效的抽象方法可以在多项式时间内获得安全的上界。最后,本文提出了一个算法来探索DAG节点之间的调度顺序来进一步收紧响应时间上界。(3)通过更细粒度地同时考虑计算和通信负载,本文提出了一个基于顺序限制的调度范式(叫做DAG-Order)来保证片上网络上的实时服务。DAG-Order基于一种既有的先进的低延迟的单周期长路径片上网络(叫做SLT No C)来避免源到目的地的长路径上的难以预测的并行传输。为了使得SLT No C时间可预测,通过在DAG内的节点和有向边之间施加某种调度限制来消除时间异常现象,DAG-Order可以实现可证明的响应时间上界安全性。随后,该限制条件被进一步放松以获取更大的运行时调度灵活性,从而实现更高的平均运行时性能但不会违背上界的安全性。最后,为了进一步收紧上进,本文提出了一个有效的启发式算法来探索一个DAG任务内合适的调度顺序。本文通过在随机和真实程序测试集上进行多维度的综合实验来验证提出调度策略和实时分析模型的有效性。实验结果显示,提出的一系列调度方法和相应的实时分析模型的实时性能(比如上界紧致性和运行时平均性能)得到了很大的提升。