Control Logic Routing for Continuous-Flow Microfluidic Biochips Using Deep Reinforcement Learning
-
摘要:
随着电子设计自动化技术的迅速发展，连续微流控生物芯片成为了目前最具前景的生化实验平台之一. 该芯片通过采用内部的微阀门以及微通道来操纵体积仅为毫升或纳升的流体样品，从而自动执行混合和检测等基本的生化实验操作. 为了实现正确的生化测定功能，部署于芯片内部的微阀门通常需要由基于多路复用器的控制逻辑进行管控，其通过控制通道获得来自核心输入的控制信号以实现精确切换. 由于生化反应通常需要非常高的灵敏度，因此为了保证信号的即时传输，需要尽可能地减少连接每个阀门的控制路径长度，以降低信号传输的时延. 此外，为了降低芯片的制造成本，如何有效减少控制逻辑中通道的总长度也是逻辑架构设计需要解决的关键问题之一. 针对上述问题，提出了一种基于深度强化学习的控制逻辑布线算法以最小化信号传输时延以及控制通道总长度，从而自动构建高效的控制通道网络. 该算法采用竞争深度Q网络架构作为深度强化学习框架的智能体，从而对信号传输时延和通道总长度进行权衡评估. 此外，针对控制逻辑首次实现了对角型的通道布线，从根本上提高了阀门切换操作的效率并降低了芯片的制造成本. 实验结果表明，所提出的算法能够有效构建高性能、低成本的控制逻辑架构.
Abstract:With the advancement of electronic design automation, continuous-flow microfluidic biochips have become one of the most promising platforms for biochemical experiments. This chip manipulates fluid samples in milliliters or nanoliters by utilizing internal microvalves and microchannels, and thus automatically performs basic biochemical experiments, such as mixing and detection. To achieve the correct bioassay function, the microvalves deployed inside the chip are usually managed by a multiplexer-based control logic, and valves receive control signals from a core input through the control channel for accurate switching. Since biochemical reactions typically require high sensitivity, the length of control paths connecting each valve needs to be reduced to ensure immediate signal propagation, and thus to reduce the signal propagation delay. In addition, to reduce the fabrication cost of chips, a vital issue to be addressed in the logic architecture design is how to effectively reduce the total channel length within the control logic. To address the above issues, we propose a deep reinforcement learning-based control logic routing algorithm to minimize the signal propagation delay and total control channel length, thereby automatically constructing an efficient control channel network. The algorithm employs the dueling deep Q-network architecture as the agent of the deep reinforcement learning framework to evaluate the tradeoff between signal propagation delay and total channel length. Besides, the diagonal channel routing is implemented for the first time for control logic, thus fundamentally improving the efficiency of valve switching operations and reducing the fabrication cost of the chip. The experimental results demonstrate that the proposed algorithm can effectively construct a high-performance and low-cost control logic architecture.
-
实时嵌入式系统几乎存在于任何环境中，诸如汽车、航空电子设备和电信等领域都可以找到大量的实时嵌入式系统. 在实时系统中，系统的正确性不仅取决于其逻辑行为，还取决于执行计算的时间.
任务对时间的敏感程度不同，可区分为软实时（soft real-time，SRT）任务和硬实时（hard real-time，HRT）任务. 在软实时系统和硬实时系统中，应用通常实现为与时间约束相关的实时任务的集合，并根据选定的调度算法调度. 但是，在硬实时应用（如紧急救援行动）中，违背时间限制或错失最后期限可能会造成不可估量的灾难性损失；而在软实时应用中，错失最后期限只会导致系统提供的服务质量（quality of service，QoS）下降. 因此，为了提供正确的行为和良好的QoS，实时嵌入式应用程序的设计必须始终满足其最后期限.
对实时系统的研究与对通用计算机系统的研究几乎同时开始[1]，但与通用系统基于图灵完备性迅速发展相反的是，实时系统研究发展缓慢. 主流通用计算到目前为止还没有充分认识到与时间可预测性相关的挑战[2]. 在通用计算快速发展的影响下，实时系统的研究者往往直接采用通用计算机系统各个层次（体系结构、编译器、编程语言等）的技术来完成设计. 在通用系统中设计可预测的分析是具有挑战性的，因为时间需求在系统层次结构中向下传递，意味着必须预见系统所有部分的时间属性：处理器和指令集架构、语言和编译器支持、软件设计、运行时系统和调度、通信基础设施等. 随着现代处理器性能提高的趋势，为了提高通用计算系统的性能、生产力和提高程序吞吐量或执行效率，引入的体系结构元素，如流水线、无序执行、片上内存系统等，导致了系统执行中很大程度的不确定性，这些因素都让提供时间保证变得更加困难. 现代通用处理器引入了大量的体系结构优化和多个软件抽象层，以时序的巨大可变性为代价来提供高性能的系统. 如果保证最后期限是一个关键目标，时间的不可预测性就使部署这些系统变得非常麻烦. 以此方法设计的系统的时序软硬件紧密相关，无法进行层次化设计，部署前需要进行大量的验证和测试工作，且一点微小的改动或升级都将影响系统的安全性.
学界对实时系统的许多基础概念、定义都没有共识. 例如在对实时系统的理解上，Roop[3]认为实时系统即为反应式系统，实时性体现为系统确定的响应能力，希望通过在指令集中增加同步语义来直接支持执行同步语言程序，并提出基于C语言扩展的PRET-C同步语言，及支持PRET-C同步语义的微体系结构ARPRET[4]；Lee等人[5]认为实时性体现在操作的定时执行上，提出了精确计时（precision timed，PRET）机并在ISA层面扩展了时间操作指令，以DU（delay until）原语控制过早问题，并采用EE（exception on expired）原语通过异常处理而响应过晚错误.
典型的嵌入式系统结构如图1所示. 最上层为实现嵌入式系统功能的应用程序，由实时操作系统（RTOS）等软件层应用提供实时性支持；中间层位于软硬件之间，为软件层提供硬件抽象；硬件层包括嵌入式微处理器、I/O、通用接口、人机交互接口等.
实时应用程序提出对时间属性、时间语义的要求. 我们可以在软件层、中间层或硬件层支持这些需求. 表1列出了在不同层次实现时间语义的对比.
表 1 嵌入式系统各层支持时间语义对比Table 1. Comparison of Time Semantics Supported by Each Layer of Embedded System特性 软件层 中间层 硬件层 应用程序移植难度 较低 一般 较高 支持的时间精度 较低，一般比硬件高2，3个数量级 较高，与硬件相关 最高，与硬件晶振时钟同数量级 设计灵活度 受中间层提供的接口限制 受硬件结构限制 自由 兼顾性能 有挑战性 较易 最易 图2展示了实时系统各个方面的研究工作. 传统实时系统设计方法存在脆弱性、冗余和平台依赖3个问题（将在第2节讨论）. 实时领域的研究工作大多针对单一软硬件平台，研究成果难以整合，导致对实时系统的研究在工业界与学术界脱钩，不同研究者也难以复现彼此工作，因此难以深刻认识各自工作的价值. 实时系统的研究相较于其他领域需要更深的积累、更长的周期，需要自行搭建自编程语言到硬件的研究平台.
更有甚者，由于实时系统面临安全关键的问题，而软硬件平台又没有很好的抽象，导致系统即使需要微小的升级，也需要重新开始整个设计周期，导致大量的人力物力浪费.
本文介绍了实时系统在系统结构方面发展遇到的主要问题，着重比较了PRET机[5]和我们之前提出的实时处理单元（real-time processing unit，RPU）[6]及在其基础上扩展的实时计算系统（real-time system，RTS）. 本文的主要内容包括3方面：
1） 简要介绍了实时系统的相关概念、需求、发展现状以及挑战.
2） 实时系统在应用层、指令集架构（instruction set architecture，ISA） 层、硬件层的需求，遇到的问题以及现有的解决方法，并着重比较了PRET和RPU这2套解决方案.
3） 实时系统的未来发展方向与主要挑战.
1. 研究背景与问题描述
本节阐述实时计算的相关概念、发展中遇到的问题并简述现有的解决思路.
1.1 实时计算与时间属性
实时计算系统的设计是为了满足实时的最后期限要求.实时系统对时间敏感，一般应用在特定的应用领域，如航空设备、汽车部件和宇航领域等.
对实时系统的研究几乎与对通用计算系统的研究同时开始. 早在1947年，MIT 在 Whirlwind[1] 中引入了当时先进的实时系统概念，用于控制飞行模拟器. 与基于图灵完备性理论和冯•诺依曼体系结构定义而迅速发展的通用计算系统相比，对实时系统的研究却进展缓慢. 目前学术界和工业界对于实时系统最基础的概念、定义都还未有规范统一的定论. 例如“什么是实时？”都还未有一致的共识. 一方面，实时系统属于多学科交叉领域，来自不同领域的研究者很自然地对同样的系统有不同的观察视角. 另一方面，实时系统囊括内容广泛，常有人用其表示某一类具体的实时系统. 因此，在不同的上下文中，实时系统常有不同的含义. 1988 年，Stankovic[7]指出，很多人认为实时计算仅仅是指对速度要求快一点的计算. 而直到 2018 年，Lee[8]仍然强调，在实践中，当工程师谈到“实时”时，他们可能会想表达：1）高速计算；2）优先级调度；3）流数据上的实时计算；4）有界执行时间；5）程序的时间语义；6）网络的时间语义.
一般情况下，研究者从系统的逻辑正确性和时间正确性这2个方面定义实时系统[5,9-10]，实时系统定义为系统的正确性不仅取决于系统产生的结果（逻辑正确性），而且取决于这些结果产生的时间（时间正确性）.
本文认为，实时性体现在计算系统的多个方面，从软件应用层到ISA，再到底层硬件，实时性无处不在. 为了清楚地说明什么是实时性，必须对这一概念进行详细地描述与定义. 因此，本文从软件和硬件2个方面描述当前学术界对于实时性的研究背景.
在软件方面，实时性体现在实时计算程序的时间属性上，Lee[8]总结了多种对实时性的定义：快速计算、优先调度、对流数据的计算、有界执行时间、程序的时间语义等. 本文认为，根据实时计算的应用场景，实时性是一种来自软件应用层的对时间属性的需求，这种需求即为应用程序的时间语义.
硬件上对实时性的概念也来自于应用软件对时间语义的需求. 因为超标量等技术在处理器平均性能上的过度开发，单独一条指令的执行时间变得难以预测，从而硬件难以表达来自程序的时间语义. 鉴于此，硬件上对实时性的描述聚焦于对硬件执行程序时间的可预测性.
值得注意的是，“可预测性”是一个很容易混淆的概念：一方面，它可以代表对一个硬件的时间属性分析（如最坏情况执行时间（worst case execution time，WCET）分析）结果的准确程度（即理论分析得到的执行时间界限与实际执行时间界限的差距）. 另一方面，“可预测性”也可以代表着程序实际执行时间的变化程度，相对应地，越小的变化程度对应着越好的可预测性. 这2种概念在学术界均被广泛地采用，如Thiele等人[11]和Kirner等人[12]分别使用了形式化的方法来描述这2种时间可预测性.
1.2 实时计算系统发展面临的问题
随着实时嵌入式应用程序对处理能力的要求更高，多核架构，如对称多处理（SMP），也被用于实时嵌入式系统领域. 因为多核平台的低成本以及其特性的发展和集成便于满足实时计算系统的需求. 例如，在汽车环境中，“自动紧急断开”和“夜视辅助”等新的安全功能必须读取和融合来自传感器的数据，处理视频流，并在实时约束条件下检测到道路上的障碍物时发出警告. 这是一个典型的场景，对高级特性的需求不断增加，导致对额外计算能力的需求成比例地增加. 此外，系统功能的增加决定了电力消耗、散热和空间占用（如布线）方面的额外成本[13]. 因此，多核处理器是降低上述成本的一种经济有效的解决方案，因为额外的计算需求可以分配到单个处理单元，而不是分散在车辆上的多个处理单元.
然而，在不断引入新技术提高性能的同时，处理器等硬件设备的执行时间逐渐地缺少时间可预测性，抑或是变得难以分析. 这导致现代实时计算系统开发往往需要耗费大量的人力物力在硬件的“验证—纠错—重新设计”流程上. 因为硬件设计上一个微小的变化经常会导致时序的巨大改变，为了保证设计出的硬件系统能够满足实时系统的时间与要求，需要通过对硬件的时序进行严格的建模与分析，但这一过程的代价是巨大的. 为了解决这一困境，提高生产效率，业界也提出了许多解决方案，如：采用有大量冗余性能的硬件、使用传统的简单而易于验证的设计、执行时间分析、实时操作系统等. 本文接下来会简要介绍其中几种解决方案并将它们进行对比，着重介绍现代工业界常用的WCET分析方法，进一步指出导致实时系统设计困难的关键问题.
1.3 现有的解决思路及其优劣
一种最简单的平衡实时计算系统对实时性和性能需求的方式就是采用高性能的硬件，但是这样做的效果并不好，原因很简单：这样做大大增加了生产所需的成本，即使采用高性能硬件，也无法验证程序运行时所需的时间语义是否可以满足，因为传统高性能硬件从未考虑过程序的时间语义.
另一个极端就是使用传统且简单的硬件设计，因为它们的硬件结构足够简单，在其基础上的验证与分析变得非常容易. 然而，这样做只能满足一些小型工业设备的生产设计要求，对于同时需要高性能与时间语义的复杂实时计算系统，过于简单的硬件无法胜任.
执行时间分析是一种相较而言成熟的解决方案，一般来说，实时系统满足其最后期限的能力是通过可调度性分析来验证的[14]. 所有此类可调度性分析技术都有一个基本的假设，即每个任务的WCET的上限是已知的. 然而，在任务WCET上导出安全而严格的边界正变得越来越困难. 在多核架构上尤其如此，因为处理器或核心共享硬件资源，例如缓存内存层次结构、总线、DRAM和I/O外设. 因此，由一个处理单元执行的操作可能导致在任何共享资源级别上不受管制的争用，从而不可预测地延迟在不同核心上运行任务的执行.
实时系统缓存管理方案的主要目标是简化任务的WCET估计. WCET估计通常遵循2种主要方法之一：静态分析或经验测量. 在静态分析方法中，分析工具试图通过分析应用程序二进制代码来提供WCET，而不直接在硬件上执行它. 一般来说，WCET估计工具只适用于简单的处理器，这是由于复杂的硬件特性，如缓存、分支预测器和流水线等，使得静态分析极其困难或过于悲观[15]. 在后一种方法中，应用程序二进制代码在硬件平台上执行多次，并从这些执行中提取具有可调置信值的WCET估计. 此外，在基于度量的方法中，为了考虑可能由于延迟执行的未观察到的条件，WCET的结果值通常会进一步增加一个误差范围（观测值的20%～30%）. 因此，基于度量的方法也可能导致高估WCET. 缓存的使用使得静态和基于测量的WCET估计更加复杂，因为指令的执行时间可能会根据：
1） 数据/指令在内存层次结构中的位置；
2） 存储器的存取导致任何缓存层的缺失或命中；
3） 正在使用的缓存一致性协议；
4） 缓存控制器上实现的缓存替换策略而变化[16].
虽然已经有人为单核系统提出了多种实时缓存分析框架[15]，但目前的静态分析方法对共享缓存的失效提供了悲观的上界. 此外，据我们所知，没有现有的静态分析技术能够解释一致性协议的影响. 总而言之，硬件设计上的复杂性会导致WCET分析结果不紧致，从而根据WCET分析得出的硬件性能需求往往会比实际高得多.
在软件层面，RTOS提供计时功能，但RTOS提供的计时行为不精确，且在复杂系统中不可控. 软件抽象时间属性将在计时精度上损失若干个数量级. 硬件的中断行为一般需要纳秒级的计时精度，而软件实现在用户级可能只能达到毫秒级，对于部分实时程序，这一量级远远超出了可接受的范围.
目前实时系统的挑战在于兼顾性能和实时性. 如果愿意放弃性能，那么精确的计时可以很容易实现. 相反地，如果注重性能，那么很难在现有的高性能设计基础上继续保证硬件有良好的时间可预测性. 现代处理器架构使WCET分析变得相当困难，即使是分析简单的程序也需要付出巨大的努力. 从根本上说，通用处理器的中间层ISA和硬件层未能提供足够的抽象，即计算机体系结构的ISA层缺乏对时间语义的描述，硬件层缺少对时间语义的支持.
1.4 基于ISA层引入时间语义的解决方案
相较于在软件层面实现实时性产生的巨大开销和挑战，以及使用时间可预测、可重复的硬件带来的设计、应用成本花费，在中间层ISA引入时间属性、设计时间语义是有潜力的研究方向.
针对ISA层缺乏时间语义的问题，目前已经有若干解决方案. 通常，这类工作依赖于系统中子组件之间的强制时间隔离：1个子组件的执行时间不应该依赖于其他子组件的行为.这种隔离可以：
1）在单个任务级别实现，其中子组件是任务代码中的功能或基本块；
2）在核心一级，其子组成部分是任务；
3）在多核系统级别，子组件是单独的核心或运行在每个核心上的软件分区.
具体工作将在本文第3节阐述.目前现有的解决方案主要有2007年始由Lee等人[5]提出精确计时机PRET，和我们实验室提出的实时处理单元RPU及在其基础上扩展的实时计算系统RTS.本文着重介绍与比较PRET和RPU这2种解决方案，它们均在ISA层引入时间语义来尝试解决性能和实时性之间产生的冲突.
1.4.1 精确计时机PRET
来自UC Berkley的Lee等人提出的精确时序机器PRET共包含3个版本. 其中，第1个版本仅仅是一个基于SPARC的处理器模型[17]，该模型用来在前期论证硬件多线程、scratchpad memory以及对主存的调度访问在PRET中实现的可行性. 第2个版本，又称之为PTARM[18]，是一个在FPGA上实现的基于ARM指令集扩展的硬件多线程处理器，对该处理器的测试表明，其在应用程序中具有足够的并发性，实现可重复的时序行为并不需要以过多的性能为代价. 在该版处理器的实现中，Reineke等人[19]同时证明了DRAM存储的访问延迟的不确定性可以通过按照DRAM设备的内部结构划分物理地址空间，并交错访问分区中的块来解决. 第3代PRET机器，又名FlexPRET[20]，是一个基于开源RISC-V指令集的硬件多线程处理器. 相较于第2版，FlexPRET的特别之处在于它的硬件线程数是可变的. FlexPRET既可以只配置一个硬件线程，像一个普通的RISC-V处理器一样执行，也可以配置数个硬实时线程来保证任务执行时有确定的时序. 除此之外，FlexPRET还支持混合优先级任务调度，通过调度硬实时线程以及软实时线程，FlexPRET可以最大化利用处理器的资源.
所有PRET机器都是细粒度多线程处理器，其中PTARM和FlexPRET均使用多线程在流水线中交错执行的方式来实现线程之间的硬件隔离，从而每个线程的执行时序都独立于其他线程而不会受影响. 为了精确表达与控制任务的时间属性，PRET机器都在各自的指令集上进行了指令扩展，在指令集架构层引入时间语义，实现从软件到硬件的时间语义表达的一致性这样一种自上而下的解决方案.
1.4.2 实时处理单元RPU
RPU[6]是中国科学技术大学高能效智能计算实验室所提出的一个实时硬件多线程处理器项目. 其中第1版RPU（RPU1.0）是一个基于RISC-V整形指令集的粗粒度硬件多线程处理器，并额外支持时间语义指令集（time triggered instruction，TTI）扩展. RPU1.0通过粗粒度多线程切换的方式隐藏处理器运行时的长时延问题（如DRAM访存等），从而提高处理器资源利用率，间接地提高性能. 除此之外，RPU1.0针对LET应用模型的要求，通过TTI中的线程控制指令来严格控制线程的执行时间，并通过定时I/O指令来实现精确的输入输出控制.
RPU2.0是在RPU1.0基础之上实现的一个细粒度硬件多线程处理器，与RPU1.0不同的是，RPU2.0为每个硬件线程都配置了一套寄存器、PC、流水段间寄存器等部件，从而实现每个硬件线程之间的隔离以及线程之间的无缝切换. 通过这种方式，RPU2.0可以独立地对每个线程进行时序分析，减少线程之间的干扰. 线程调度采用可动态配置的循环调度方式，每个线程可以自由配置执行时长等参数，处理器严格按照调度执行各个线程，从而保证线程执行的时序，在每个线程内，线程还可以使用TTI来实现精确定时的I/O操作.
2. 应用、软件层级的实时性
本节介绍实时应用在通用的传统体系结构上实现的方法技术.
2.1 应用的时间需求
实时计算系统所面向的应用场景相当广泛，从航空航天到汽车控制系统、医用设备，以及高精度工业控制设备方面都有广泛的应用. 这些应用都需要实时地与外界物理环境进行交互，这不仅需要实时计算系统的操作逻辑正确，还需要其操作能够满足一定的时间约束，即应用的时间语义. 显然，为了尽可能地满足应用的时间需求，需要明确在这些应用场景下有哪些时间语义需要表达.
在响应式系统（reactive systems）[21]中，系统需要在有限的时间内根据外界的输入进行快速计算并输出结果. 这类系统在实际生产中的常见应用往往是一些安全攸关（safety critical）的应用，如汽车刹车系统、医疗电子控制系统、核电站控制系统等. 这些系统需要保证程序能够在给定的时间内完成执行，否则会带来灾难性的后果. 从这点来说，它们的时间需求聚焦于程序的WCET是可分析的，且往往要求WCET的变化范围小于某一特定的值.
在交互式系统（interactive system）[22]中，系统以一定的频率和外界环境进行交互（通常按照环境的步调持续地与其进行交互），这一交互往往需要和其他组件同步（synchronize）. 比如在时分复用的实时通信系统中，计算结果的输入和输出需要和通信时对应的时间片同步. 在这种情况下，系统的时间需求注重系统输入/输出的时刻需要和外界精确同步，更进一步地来说，这一过程可能还具有周期性.
此外，在现代的工业生产设计中，一种系统可能具有多种不同优先级的任务，即混合关键系统（mixed criticality systems，MCS）[22]，在这种系统中，有着不同优先级的任务在同一个硬件平台上共享执行资源. 在实时系统中，高优先级任务往往有较强的时间语义，低优先级任务可能有较弱甚至不具备时间语义. 在这种情况下，实时系统往往需要进行合理的调度来保证高优先级任务的时间语义被优先保证.
2.2 实时操作系统
实时应用程序在软件层面通用的解决方法是在传统结构上运行实时操作系统（real time operating system，RTOS）. 传统计算机系统的层次结构中，体系结构层次以“指令”作为最基础的单元，而操作系统通过外部中断的协助对“指令”流进行管理和封装，为上层提供丰富的服务. 在实时领域的研究过程中，出现一批实时操作系统，如μCOS[23]，FreeRTOS[24]，RTEMS[25]等. 它们基于传统的操作系统和实时调度算法，提供具有一定时间语义的任务模型接口. 然而，在这种方式下，操作系统更像是编程语言配套的实时库，既要保证实时应用的时间属性，仍然需要用户结合实时应用和体系结构进行设计和调整. 这些“实时操作系统”仍未突破传统计算机系统的层次结构，其实际效果也具有一定的局限性.
在时间精度方面，实时操作系统基于内核服务提供时间延迟和超时. 如FreeRTOS用32位寄存器保存定时器中断的计数值，在常见的嵌入式设备（例如STM32F429开发板）上时钟精度约为50
μs ，比硬件运行的纳秒级别的时钟周期高约3个数量级. 另一方面，RTOS按预定的调度策略调度任务执行. RTOS通常支持优先级抢占或时间片轮转（round-robin，RR）这2种基本任务调度机制，由于在软件层面切换任务带来的大量开销，RTOS提供的快速任务抢占耗时一般达到毫秒级（相较于通用系统的非抢占内核，最坏情况为秒级）[26].在提供的服务方面，典型的RTOS采用微内核（micro kernel）体系结构[27]，其内核只提供最基本的系统服务（如任务调度和管理），其他服务位于内核外，需要根据应用需求单独裁剪配置；且由于状态切换带来的大量开销，对时间敏感的嵌入式系统可能不区分用户态和内核态，应用程序之间的隔离性较弱.
2.3 最坏情况执行时间（WCET）分析
WCET分析始终是一项富有挑战性的工作[15].因为程序流分析是一个不可判定问题，需要描述清楚，对一个在某个系统上运行的程序进行WCET分析，需要对这个系统的每个细节，包括流水线、存储系统以及执行结构进行建模.现有的先进WCET工具有AbsInt的aiT工具，该工具曾被用在空客A380的安全攸关的软件系统的分析中[17]. 除此之外，还有Otawa以及Chronos等工具.
此外，说明WCET工具的有效性也是件困难的工作，Wägemann等人[28]提出GenE工具来评估WCET分析器的有效性，GenE可以生成一系列已知流图的程序测试用例，从而通过对比WCET分析工具在其上的分析结果与已知流图的分析结果可以判断WCET分析结果的有效性. 令人遗憾的是，GenE发现了aiT工具在ARM Cortex-M4处理器的建模下分析出的WCET并不正确[17]：aiT分析出的WCET结果小于程序的实际执行时间. 这说明针对复杂的系统设计，建模必须格外小心，否则WCET结果难以和实际的系统设计保持一致. 更进一步地，正如Wägemann等人[28]提到的：“最精确的执行时间模型就是处理器设计本身”，因为建模的过程不可避免地会发生错误.
WCET分析的经验表明单单依靠分析工具来保证实时性并不可靠. 针对这种困境，目前有一种观点认为应当通过在程序执行的更低层次引入时间语义来提供程序执行时间的抽象表述，从而简化WCET分析，保证应用的实时性.
2.4 编译器保证的代码段执行时间上界
传统编译器只聚焦于提高代码的平均性能，且无需知晓程序执行的硬件架构是怎么样的. 在实时程序的设计中，这2点都发生了很大的改变. 编译器层面变为着重于对程序WCET的优化[29]，且这一过程是架构相关的，即编译器至少需要底层硬件执行指令时的时序相关的信息才能进行有效的WCET分析.
Broman等人[30]在PRET的设计过程中为这些问题提出了一种解决方案. 针对编译器过于依赖底层硬件实现的问题，Broman等人[30]认为，编译器对于底层硬件的信息需求是必不可少的，但是可以通过参数化描述底层硬件架构的方式来增强编译出的目标代码的可移植性. 因此，可以使用体系结构描述语言（architecture description language，ADL），比如EXPRESSION[31]，来参数化描述硬件架构，从而为编译器增加对硬件的时间行为的描述，减少对硬件架构的依赖，增强目标代码的可移植性.
编译器为了保证代码执行时间的上界，除了需要硬件架构的时序信息之外，还需要对程序本身进行WCET分析，PRET小组使用MTFD指令来对程序块的执行时间进行约束[18]，并将这一约束信息传递给PRET编译器. 编译器通过对程序中被MTFD约束的代码块进行WCET分析，来判断约束是否被满足.
PRET小组在设计的过程中还提到了编译器的一个额外任务，即程序内存空间分配的工作. 在PRET机器中，实时程序的代码和数据被放在一块名为便签存储器（scratchpad memory，SPM）[32]的部件中执行，SPM可以快速地响应数据请求且其响应时间是可预测的，因为实时程序不能忍受访问如DDR主存时的抖动巨大的响应时间. 但SPM必须显式管理、手动分配，这就需要编译器知晓SPM在内存中的位置，并主动将实时程序的代码与数据分配到SPM中.
总而言之，实时程序的编译器相较于传统的编译器（如C编译器），承担了许多额外的工作来保证代码段执行时的时间属性，包括WCET分析、硬件时序分析、内存空间管理等，对支持实时程序的编译器的开发仍将会是一项富有挑战性的工作.
2.5 本节小结
传统的实时系统设计方法基于通用计算系统，关注计算过程的时序可预测性，通过设计阶段进行时序分析来满足系统的时间约束.
很久以来，程序的“正确”执行从未考虑时间. 计算的所有抽象层次都未曾提供时间属性. 指令集体系结构不能保证时间属性；没有通用的语言有时间语义的表示；实时操作系统由于并发等因素不能保证时间语义属性；现有的网络架构也没有时间语义属性[5]. 这导致实时系统设计方法始终无法摆脱3个问题：
1）脆弱性. 表现为在实时系统中即使是一个微小的改变或“改进”也可能会导致严重的时序紊乱，需要重新验证实时性是否得到保证，甚至重新设计.
2）冗余. 体现在实时系统的设计往往需要预留多余的时间或计算资源以保证系统的正确性.
3）平台依赖. 体现在实时系统设计依赖其使用的软硬件平台、系统时序与平台绑定.
传统的实时系统设计方法往往通过投入大量的人力物力来解决这些问题. 然而，当今社会的实时需求日益复杂，对敏捷设计的要求也在逐步凸显，实时系统急需新的高可用、高易用的设计方法.
3. ISA级的系统实时性
计算机科学领域的时间概念相当原始. 图灵机和冯·诺依曼机模型基于顺序控制抽象，指令一条接一条地执行，时间先后关系（temporal succession）是当前机器语言级唯一可用的时序关系. 虽然定义冯·诺依曼机的程序逻辑行为无需显式地引用量化时间概念，但无法满足实时系统的时间约束.
由于传统的计算机体系结构模型缺乏时间语义，早期的实时系统设计者不得不把具有时间语义的程序运行在不具有时间语义的体系结构上. 莱斯定理[33]指出，程序所有非平凡的语义属性都是不确定的. 这意味着在基于缺乏时间语义的体系结构模型设计的处理器上，难以确定性地运行时间语义程序. 只有在体系结构模型中加入时间语义，结合具有时间语义的指令集设计实时处理器，才能保证时间关键应用的运行时确定性（PRET研究组将这个特性称为时间可重复性）.
3.1 将时间作为关键因素编程
虽然一些实时系统建模语言（Timed C等）中包含了时间概念，但实现语言，如C语言、通用RiscV汇编语言等缺乏时态语义.因此，程序的执行时间受其自身特性和软硬件执行环境的影响，分析复杂、脆弱易变.时序仅仅是特定硬件平台上软件实现的一种附带效果.硬实时程序测试、验证和认证时需要仔细考虑软硬件交互的细微之处，但任何微小的软硬件设计变化都可能导致不可预测的时序变化，成本高昂.实时系统的建模和实现既没有可移植性，也无法保证在实际系统中执行的正确性.在系统的设计阶段，设计者对所设计系统的时序行为进行了仔细定义和分析，但现有的实现技术基本上忽略了这些工作，迫使设计者通过测试对所实现系统的时序行为进行重新确认.
时序指令仅仅建立一种指定时序约束的方法，并不强制执行时间行为，它们仅仅用于对软件中的时序变量进行监测、检查和交互. PRET和RPU的目标都是在ISA中引入时序语义，但不过度约束ISA的时态属性. 时序指令只需要满足其时序属性完全实现，不限制其他指令的性能优化. 基于这些时序指令，程序员可以分析和控制程序的时态属性，独立于体系结构. 同时，时序指令自身并不保证程序的执行时间. 静态分析为了可以得到紧致的WCET界，需要下层体系结构提供可预测的执行时间.
目前，实时ISA的研究工作主要有2个方向：
1） 基于传统的ISA，以辅助WCET分析为目标设计时间可预测的体系结构.
2） 定义带有时间语义的ISA，为上层提供精确的时间语义，并为目标设计时间可预测的体系结构.
3.2 基于传统ISA的工作
传统ISA缺乏时间语义，Kopetz最早提出采用时间触发（time-triggered，TT）范式代替事件触发（event-triggered，ET）范式进行体系结构的设计，并采用时间触发体系结构（time-triggered architecture，TTA）以解决分布式实时系统中多节点间缺乏时间语义的问题[34-36]. 随后，越来越多的学者认识到处理器缺乏时间语义的问题，并在传统ISA上改进设计时间可预测的体系结构.
表 2 ET系统和TT系统的比较Table 2. Comparison of ET System and TT System性质 ET系统 TT系统 可预测性 很难满足时间约束 可满足时间约束 可测试性 尽量进行覆盖测试 可进行构造测试 资源利用率 负载低时较优 极端情况较优 可扩展性 易改造，无法保证时序 重新设计，保证时序 Pont[37]认为了解硬件的每一个细节，就可以基于现代处理器构建满足所有实时要求的软件，这对硬件、系统设计者提出了较高的要求. Pont研究团队提出了时间可预测的PH Core[38]，它使用硬件多线程来处理由中断引起的延迟，并且有一个硬件调度器以更好地支持TT模式.
Schoeberl[39]希望使用Java进行实时系统的开发，并为Java环境设计了一套硬件体系结构——JOP（Java optimized processor），从架构的角度增加系统的可预测性. JOP架构中更简单、更准确的 WCET分析比平均情况性能更重要. JOP是Java虚拟机在硬件上的实现，它采用了3级流水线，没有使用分支预测. JOP主要应用于需要Java环境的嵌入式实时系统，其微指令长度一定且执行时间相同.
我们认为基于传统的ISA设计可预测的体系结构没有明确在ISA层抽象出时间触发、时间控制的概念，复杂度高、泛用性较低.
3.3 重定义ISA的相关工作及时间语义
ISA层在实时系统中对上层提供时间接口、抽象时间属性和时间语义（对时间相关操作的表达能力），对下层硬件提出需要满足的抽象要求.
Roop[3]对支持同步语义的反应式处理器进行研究，希望通过在指令集中增加同步语义来直接支持执行同步语言程序；以Esterel[40]为代表的同步编程语言基于同步假设，通过信号管理，如轮询（polling）、发射（emission）和抢占（preemption）等同步程序，保证并发行为的确定性，易于程序验证；HiDRA[41]是一个实时系统的软硬件协同设计方案，使用多个反应式核REMIC[42]构造全局异步局部同步（globally asynchronous locally synchronous，GALS）的体系结构，提供类Esterel语言的同步语义. STARPro[43]与HiDRA思想一致，但HiDRA支持类Esterel的同步语义，而STARPro旨在直接支持 Esterel程序执行. 另外，Roop等人[4]提出基于C语言扩展的PRET-C同步语言，并提出支持PRET-C同步语义的微体系结构ARPRET. ARPRET分为2部分，GPP实现通用计算，PFU负责调度和保证功能的时间属性正确.
据本文调查所知，目前仅PRET项目和RPU完整地抽象了时间语义，向上层提供了ISA级的时间接口，扩展了时间语义指令集.
3.3.1 PRET基于delay的延时语义
PRET扩展的时间语义主要约束了程序段执行时间长度. DU（delay until）指令保证了程序段的执行时间下界，mtfd结构在编译阶段静态检查代码段是否满足设定的执行时间上界，并采用EE（exception on expired）指令通过异常处理响应过晚错误. PRET基于代码块进行时序控制，我们认为PRET在功能上，逻辑与时序控制分离；在时序上，“过早”与“过晚”分离.
此方案添加时序语义，可以约束指令序列执行时间的上下界，然而其缺少对定时语义的支持，无法直接表达操作发生在某个时刻的语义. 正如Zimmer等人[20]阐述的那样，如果系统中存在中断，PRET基于delay+load/store的结构实现定时I/O就存在实现与语义不一致的问题，操作缺少原子性.
Wan等人[44]提出构建时间语义指令集的思想，拟添加时间语义和操作语义绑定的指令，但该想法处于较早期阶段.
3.3.2 时间触发指令集TTI的语义
TTI指令集所描述的时间语义主要包括2个方面：1）对程序执行时间长度的约束；2）对程序执行操作时刻的约束. 在对程序执行时间长度的约束方面，TTI并没有特别定义针对某个程序设置执行时长的指令，对程序执行时长的控制体现在TTI的多线程指令方面. TTI中有一个线程调度表，该表负责为每个线程分配执行的时间片大小. 通过对多线程的调度，可以控制每个线程在处理器中运行的时间长度.
值得注意的是，相较于PRET，TTI对程序执行时间的控制方式是不一样的. 在执行超时的情况下，PRET机器通过超时触发定时中断的方式实现对程序执行时间长度的控制. 在执行时间短于规定时间的情况下，PRET机器通过DU指令来延长程序的执行时间. 而TTI在这2种情况下都使用线程切换的方式来实现，在程序超时后，时间语义指令将异常状态代码写入特定的控制与状态寄存器（control and status register，CSR）中，并切换至其他线程，原有线程的程序被中止执行. 而在一个线程被分配到的执行时间片内，即使程序已经完成了执行，处理器仍只会运行该线程而不会跳转至其他线程，直到该线程被分配的时间片用完.
针对同步式实时控制系统的需求，TTI还支持针对I/O的定时语义，TTI可以将程序的I/O与执行时刻绑定，在处理器运行的离散时间中指定某一时刻执行操作.
3.3.3 时间指令集扩展及对比
为实现ISA定义的时间语义抽象，需要向通用指令集中扩展时间操作指令. PRET系列机和TTI的时间扩展指令集对比如表3所示.
表 3 PRET与TTI在扩展的时间指令集的对比Table 3. Comparison of PRET and TTI on the Extended Time Instruction Set类型 PRET 解释 TTI 解释 时间管理指令 set time %r, offset %r = 当前时间+offset getti r1 r1 = 当前时间 setti r1 当前时间 = r1 settg r1 标准时钟粒度 = r1 getts rd rd = 上次时间触发操作的时间戳 （TTI 2.0） settsg r1 时间片长度 = r1指定的CPU cycle数 （TTI 2.0） gettsg rd rd = 当前时间片长度 时间触发操作指令 delay until %r 延迟后续指令，直至%r时刻开始执行 delay r1 延迟后续指令直至 r1指定时刻开始执行 ttiat rd，r2，r1 if（ti==r1） then rd←[r2]；else wait. ttoat r3，r2，r1 if（ti==r1） then [r2]←r3；else wait. 异常管理指令 expection on expire %r，id 当前时间等于[%r] + 1，则异常 deactivate exception id 禁止id异常 静态检查执行时间上界约束指令 mtfd %r 保证该指令执行时，当前时间≤%r mtfd r1 保证该指令执行时，当前时间≤r1 任务并发管理指令 tkend 当前线程的任务执行完毕 addtk r1,r2 添加一个调度表项，使得处理器在ti＝r1时，切换到r2指定的线程执行 PRET和TTI时间扩展指令集对于过早的操作都采取等待的方式，对超时错误抛出异常. 不同的扩展时间指令集对实时性的影响差异体现在指令集可描述的时间语义上，如3.3.1节和3.3.2节所述. 在时钟精度方面，PRET的时钟精度由微处理器运行的周期长度决定，而TTI基于时间触发范式TT[34]和时间触发自动机TTA[34-36]设计，完整地抽象了时间触发、时间控制的概念，时钟可以由外部接入（例如网络时间），支持的时间精度与微处理器运行的时钟周期同数量级[6]. TTI针对RISC结构的微处理器使用的load/store结构，定义了定时I/O指令ttiao/ttoat，原子性地保证了I/O操作的时间点（time point）[26]，符合LET编程模型[45]的规范.
RPU实现TTI指令集，基于LET编程模型.目前在Xilnx FPGA开发板（xc7a100t-csg324-1）上实现了智能小车跟车系统[26]和ABS防抱死应用系统[46]的验证，结果符合预期.
3.4 本节小结
实时系统在中间层ISA实现实时性，相较于软件层实现实时性，利用了微处理器一般达到纳秒级的运行时钟，为上层直接提供时间语义指令.
目前指令集架构层面引入时间语义指令的工作主要有PRET研究组的系列工作[20,47-48]和TTI指令集. PRET研究组提出了指令集架构在时序控制方面需要具备的能力[47]，基于这一想法，文献[20,48]分别基于ARM指令集和RISC-V指令集扩展，加入了控制代码段执行时间的指令，并依据扩展后的指令集构建了可以执行时间语义指令的处理器PTARM和FlexPRET；文献[6]在PRET研究组工作的基础上提出了时间和操作相结合的定时指令，定义了TTI指令集，并实现了RPU. 文献 [6, 20, 48]所述的工作，重点在于时间语义指令集的定义，以及处理器硬件架构的实现. 文献[47]虽然给出了指令集架构在时序控制方面需要具有的语义，但是没有说明从上层模型到底层指令的映射关系，没有给出相应的设计范式.
现有的时间语义指令集工作对指令集可以表达的时间语义没有给出明确说明，同时缺乏相应的时间语义程序设计范式，导致上层控制模型或编程模型映射至底层时间语义程序时依旧缺乏相关理论指导.
4. 硬件层级的实时性支持
4.1 实时系统对硬件性能的需求
现今实时计算系统面临的挑战在于同时兼顾系统的性能以及实时性，因此，对性能的需求也是必不可少的. 一个单周期处理器显然有很优秀的实时性，但是它的性能远远满足不了现代应用的需求.
一个常见的误区在于高性能等于更好的实时性，导致许多工业系统设计错误地估计了实时系统的性能需求，Stankovic[7]也曾在1988年提出过，高性能的硬件有助于对系统实时性的提升，但是却不能保证系统的实时性，这和实时计算系统的设计初衷是相违背的. 若使用软件来取代通常由硬件提供的功能或与其他硬件设备交互的应用程序需要精确计时的输入/输出（I/O），其所需的计时精度在纳秒级，这是处理器时钟周期的粒度. 目前，尽管对于许多应用程序来说毫秒级的计时精度已经足够了，但对于某些特定的应用程序来说还不够精确.
4.2 实现时间属性的硬件支持与计时精度
PRET[5]和RPU[6]都基于经典5段流水线，在EX段执行扩展的时间指令，采用寄存器寄存当前计时时间. 在PRET系列最新的FlexPRET实现中，系统上电时刻计时时钟寄存器归0，随后每个CPU运行时钟上升沿到来时，计时时钟值加1. 由于最终运行频率为100 MHz，FlexPRET认为其计时精度为10 ns. 我们认为，在PRET中计时时钟和运行时钟只是同一个晶振源的不同视角，且冯•诺依曼结构并未指明硬件实现必须要使用时钟同步的各个部件，因此PRET未对计时时钟和时间语义有足够的抽象.
实现TTI[6,22]的RPU提出了实时机（real-time machine，RTM）的概念，在冯•诺依曼机5大组成部件的基础上显式引入计时时钟，直接提供给上层针对程序的时间行为予以控制约束的接口，为RTM赋以时间语义. RPU基于RTM模型，引入计时时钟（称为标准时钟），明确了时间触发、时间控制的概念.
标准时钟和CPU运行时钟之间显然有2种关系：同步与异步. 在实际应用中，如果需要从外部接入标准时钟（例如网络时间），则运行时钟和标准时钟之间是异步关系. 在之前的研究中，我们说明了在异步情况下TTI的时间触发指令抖动小于一个CPU cycle[6].
4.3 硬件多线程流水线结构
实时系统标准的传统方法是在单线程处理器上进行软件调度，而不需要为每个任务使用整个处理器或核心，并承受相关的效率损失. 调度算法选择在不同时间段执行某个任务，因为只能有一个任务在执行. 使用传统方法已经越来越不能满足实时系统对性能日渐增长的需求，在单核系统上引入硬件多线程可以在保证实时性的基础上以较小的开销提升处理器的吞吐量，减少stall或是等待线程代码段执行时间下界的空闲周期.
我们的调查得出的一个主要结论是，一定程度的硬件支持对于在实时系统中为并发执行任务提供可靠的隔离保证是必要的. 即使可以只用软件实现，但与硬件解决方案相比，软件的解决方案通常更麻烦、更难以认证且增加更多的开销.
粗粒度多线程（coarse-grain multi-threading，CGMT）描述了一种硬件多线程结构，CGMT在同一时间只能执行1个线程，但又可以使用硬件切换为执行另一个线程，无需软件干预. 为此，它必须在处理器中使用硬件存储多个线程的状态，该状态称为硬件上下文（context）. 切换2个存储在硬件上下文中的线程，包括清空正在运行的线程状态并将另一个线程状态加载到流水线中. 与操作系统使用的软件上下文切换相比，这通常需要少量的周期. 相应地，软件上下文切换只能用于隐藏长延迟（例如磁盘和其他 I/O延迟），但粗粒度多线程处理器可以隐藏更短时间的延迟，例如高速缓存未命中带来的延迟.
细粒度多线程（fine-grain multi-threading，FGMT）相较于粗粒度多线程，将若干个CPU时钟组织成时间片，在每个时间片按线程调度表切换线程. 线程之间交错执行，实现了“时间触发”而不是“事件触发”切换线程[6,17,20]. PRET实现细粒度多线程，采用线程交错的流水线来避免同一线程中的数据依赖，在PTARM[18]和FlexPRET[20]实现中，每个CPU时钟上升沿选择一个线程取指. PTARM中，多线程以严格轮询的方式调度，流水线的每一段交错地执行若干个线程. 而2015年提出的FlexPRET改进型结构，使用细粒度多线程和灵活的调度与定时指令来实现每个任务在基于硬件的隔离和有效的处理器利用率之间进行权衡，多个线程不必严格轮转，每个周期可以由设定好的线程调度表选择线程取指进入流水线. 每个线程中程序相邻的2条指令取指之间的时间间隔（以CPU cycle计量）称之为一个thread cycle. FlexPRET 同时调度HRT任务和SRT任务时，对HRT线程采用时分复用（time division multiplexing，TDM）的调度，消除线程间干扰.
RPU1.0实现粗粒度多线程，RPU2.0版本实现了细粒度多线程. RPU1.0采用和预设最大线程数相等套数的段间寄存器、PC寄存器、Regfile，增加了一定的硬件消耗，确保了切换线程的时序. 多线程由专用的时间触发（TT）线程控制器管理，TT线程控制器根据TT表控制切换线程，TT表的抽象结构为队列. 在RPU1.0版本中，TT表记录了若干线程编号-标准时间数据对，每当队头指定的时刻（在EX段判断）到来时，花费4个CPU cycle切换至指定线程[6]. TT表由0号线程维护，通过addtk指令不断向TT表中添加表项，0号线程需要经过特定设计以满足调度需要. 在RPU2.0版本中，多线程按时间片轮转调度，TT表记录了各个线程编号及其分配到的时间片个数. 相较于RPU1.0版本，RPU2.0损失了一定的灵活性，但在保证可预测性的同时降低了0号线程的设计难度.
4.4 存储系统的实时性
存储层次结构设计影响功能、可预测性和性能，根据应用程序领域的不同，需要做出不同的权衡.
目前对实时存储系统的研究主要有2个方向：
1）在通用的传统Cache-Bus-Memory结构上改进以令存储系统具有时间可预测性和时间可重复性.
2）使用新的存储组织结构.
在通用结构上改进的主要挑战来自于Cache访问时的不确定性、总线/存储器访问调度策略等，以及扩展至多核系统时保证时间可预测的缓存一致性；使用新的存储组织结构能保证较好的实时性，但现有的实时应用和硬件都需要重新设计.
4.4.1 传统Cache-Bus-Memory结构
CPU Cache对程序员来说是透明的，并且其依赖于内存访问的时间和空间局部性来减少应用程序的平均执行时间. 因此，CPU Cache使用一组启发式方法来保存在不久的将来更有可能被访问的数据，并替换旧的、未引用的条目. 在较高的层次上，Cache的启发式行为意味着在整个任务执行过程中对同一位置的内存访问可能会导致Cache命中，也可能不会命中，这取决于系统的历史记录. 事实上，任务本身的执行模式、同一核上的不同任务的执行模式，甚至是不同核上的一组任务的执行模式都会影响给定内存访问模式的Cache命中率. 这意味着复杂功能的系统历史可以直接影响任务从内存层次检索数据所需的时间，这也解释了为什么Cache是不可预测性的主要来源之一. 此外，实时应用程序的内存访问行为是由其功能驱动的. 例如，简单的HRT控制循环不需要高的内存带宽，而视频处理应用程序需要内存带宽和延迟. Cache Line分配中的冲突称为空间争用；由多个核同时访问同一个级别的Cache，称为时间域的争用.
解决基于Cache的传统存储结构可预测性的2种最常用的方法都是在Cache上强制执行更确定的行为.
第1种实现时间隔离的方法是Cache分区，它将 Cache 划分为若干分区，并将特定的分区分配给任务或核心.基于组相联Cache的结构，这些方法可以进一步分类为：
1） 基于index的缓存分区，每个index指示的Cache Line被划分一个分区（水平切片）；
2） 基于way的缓存分区，每一个可用的Cache Way都被专门划分为一个分区（垂直切片）.
第2种常用技术是Cache锁定. Cache锁定依赖于许多嵌入式平台中存在的硬件特性. 具体来说，可以将给定的Cache Line或方式标记为锁定，从而防止其内容在连续执行解锁操作之前被替换[36,49]. 应用程序可以通过操作系统（OS）内存分配器使用Cache分区和锁定.
单核情况下只有一对指令和数据Cache，时序较为确定，可分析性强. 在多核情况下，保持各个核心的Cache一致是保证逻辑正确性的必然要求. 在通用计算机系统中，应用较为广泛的Cache一致性协议是MSI协议，它定义了Cache的3个状态：Modified（已修改）、Shared（共享）、Invalid（无效）[50]，可以保持多核情况下各个Cache数据的一致性. 但分析表明，仲裁延迟随核数的增加呈线性增长，而一致性延迟随核数的增加呈二次增长，这强调了考虑缓存一致性对延迟范围影响的重要性[51].
University of Waterloo 的研究人员在 2017 年基于MSI协议设计了可预测的PMSI Cache一致性协议，通过引入一组暂态来实现MSI上提出的不变量，同时仅对缓存控制器进行最小的架构更改. 在维持可预测性的同时，PMSI协议在4核系统上比竞争总线的调度方法实现4倍的性能提升[51]. 随后不久，又提出了新的缓存通信机制CARP[52]，CARP在SPLASH2 基准测试中比PMSI协议性能提高4%. University of Waterloo的研究人员在可预测一致性协议的基础上实现了实例MapleBoard[53]，并支持 MSI，MESI，PMSI[51]，PMESI[54]，CARP[52]一致性协议.
在总线层次，Bus一端承接了多个Cache，接收多个核心的访存请求；另一端连通多个存储器或外设（也可以看作特定地址的存储器）. 需要解决的问题是设计可预测的总线架构和仲裁算法. 目前通用的总线结构解决方案是使用2级调度器，将每个核心的访存请求按可调度算法排成队列，在外界看来仅有一个被核内时间可预测调度器选择的访存请求，而多核间的请求由高一级的调度器选择一个核心的请求并给予总线控制权. 目前通用的可预测的调度方法为TDMA的轮询型调度，它保证了每个请求的最长响应时间和最长结束时间. 作为实例，Barcelona Supercomputing的研究人员提出的可预测性架构[55]就使用了2级调度结构，以ICBA（intra-core bus arbiters）调度核内请求，以XCBA（inter-core bus arbiters）调度核间请求，并给出了可预测的调度算法和仲裁方法.
存储器方面，实时嵌入式系统一般采用动态RAM（DRAM），以应对现代设计中不断增加的数据量和代码大小. 然而，到目前为止，内存控制器的设计主要集中在提高平均性能上[19]. 因此，内存访问的延迟是不可预测的，这使得硬实时嵌入式系统所需的WCET分析变得复杂. Hassan等人[56]提出了一种可预测的内存请求调度方法，该方法能在大量的请求中保持局部性，最小化最坏情况的延迟，同时保证了平均延时没有明显增长. 这种方法引入了一种新颖的紧凑的时分多路复用调度器和一种新的框架，用于构造多核混合关键系统的最优片外DRAM存储器控制器调度. 这些调度计划在引导阶段加载到内存控制器.
RPU扩展而成的实时系统RTS采用传统经典的Cache-Bus-Memory结构，利用TDMA的轮询调度保证总线和Cache访问的可预测性[57]，相较于PRET，能更简单地移植基于Cache存储系统编写的程序.
4.4.2 便签存储器
便签存储器（scratchpad memory，SPM）被认为是一种比Cache更可预测的选择. SPM是一种特殊的静态RAM存储器，放置在靠近处理器的地方，类似于L1-Cache. SPM的地址空间被映射到处理器预定义的内存地址上. 与Cache不同，SPM必须显式管理. 即某个数据在使用之前，其所在内存块必须在软件中从主存中移动并复制到SPM中. 因此，SPM是高度可预测的，因为它们只有一个CPU运行时钟周期的访问延迟，而Cache有2个不同的Cache命中延迟和未命中延迟. 然而，SPM显式程序管理的需求意味着基于Cache的系统编写的程序不能轻松地移植到基于SPM的系统上执行，而且在可用的商业系统中，对便签存储器的支持是有限的[58].
PRET机采用SPM较为简单地处理存储系统的可预测性问题. 以FlexPRET为例，FlexPRET有单独的指令和数据存储器，使用软件管理的SPM而不是Cache，并且程序只允许访问SPM允许的区域. 因此，所有有效的内存访问总是成功的，并且单周期返回结果. FlexPRET每个周期只能发生一次存储器操作；在加载或存储操作期间，不会获取新指令，从而使用SPM降低了处理器的总吞吐量. 在常见的通用设计中，通常使用指令和数据Cache而不是SPM来构建存储系统，但对于具有类似或更高复杂性的处理器来说，PRET认为这是合理的设计决策. 其理由是，如果代码和数据之间只共享一个SPM，那么硬件线程的内存操作只能发生在一个预定的周期内，这个周期可能与内存阶段不一致，它需要更多的控制逻辑和数据存储. 例如，每个硬件线程将需要为一个内存操作存储地址和数据，直到下一个预定周期，然后阻止读取. FlexPRET可选地允许对指令内存而不是数据内存进行内存操作.
4.5 本节小结
在硬件层实现实时性的支持，设计自由度最大，但必须考虑从成熟的通用系统迁移实时应用的成本. 实时领域的研究工作大多针对单一软硬件平台，为特定应用环境开发专用的成套软硬件是可行的做法，但研究成果难以整合，导致在实时系统研究方面工业界与学术界脱钩，不同研究者也难以复现彼此工作，因此难以深刻认识各自工作的价值. 实时系统的研究相较于其他领域需要更深的积累、更长的周期，需要自行搭建自编程语言到硬件的研究平台. 更有甚者，由于实时系统面临安全关键问题，而软硬件平台又没有很好的抽象，导致系统即使需要微小的升级，也需要重新开始整个设计周期，导致大量的人力物力浪费.
5. 总 结
本文针对实时计算系统的发展情况，从计算机 系统结构的各个层次分别对实时计算系统的需求、问题以及解决方案进行了论述. 在对现有的实时系统设计研究的过程中，本文注意到实时系统设计问题的关键在于上层应用的时间语义难以与底层实现保持一致，为此，需要在ISA层以及硬件设计时引入时间语义. 针对在ISA层引入时间语义的方法，本文着重描述了现有的2种解决方案，分别是来自UC伯克利大学设计的PRET项目以及本文实验室所设计的RPU项目，并从ISA层的时间语义方面分别介绍了2种解决方案的异同. 在硬件层面上，本文针对现有硬件设计总结了在实现时间可预测性方面的问题与挑战，从多线程和存储系统的实时性方面入手，分别对比了传统设计和实时系统的设计，论述了如何在硬件层面取得更好的时间可预测性.
并行性和实时性是目前安全关键实时系统的核心要求和特征，传统计算平台对此支持不足，导致系统设计、实现和验证成本高昂，必须从3个基础设施入手加以解决.
1）多核与多线程实时系统
向多核架构的迁移对硬实时系统的发展提出了 极大的挑战. 这是因为共享硬件资源（如内存、互 连、I/O等）的存在会在核心之间造成不必要的干扰. 反过来，这种干扰使得我们很难得出安全且准确的任务执行时间的最差情况界限，而这是保证时间限制所必需的.
一个重要的问题是如何处理多核情况下的CPU 运行时钟和时间语义需要的计时时钟的同步性. 一方面，研究表明分析多核系统上并行程序的存储器一致性需要显式的全局时钟[59]. 对于没有显式全局时钟的片上多核处理器系统， Lamport[60]证明了在分布式系统中，如果各个进程使用不同的分布时钟，则使用一定的算法可以把不同的时钟换算成一个近似的全局时钟，并且保证这个全局时钟的误差足够小. 另一方面，为了保证时间语义并利于验证，每个核心上的计时时钟也需要同步，一种简单的实现是为每个核心接入同一个外部晶振作为计时时钟.
2）时间可预测ISA
实时系统的ISA应该提供给上层应用足够的时间抽象. 对于未来的时间增强ISA，我们认为其应该：
①提供时间管理接口，从用户需求出发抽象出秒、毫秒、纳秒等计时单位，并设置时间粒度.
②满足用户对于定时执行的需求. 时间需求可 以抽象为绝对点时间、相对点时间、绝对段时间、相 对段时间，ISA应该具有能满足这些需求的语义.
③提供程序隔离能力，为新一代的混合关键系统提供执行环境.
④能够提高处理器的利用率，改善长期以来实时系统因预留资源导致计算能力大量浪费的现状.
3）时间可预测存储系统
向多核方向发展需要重新设计可预测的存储系 统. 基于传统Cache的存储系统和基于SPM的存储系统存在较大的差异性，SPM可预测性更好，但需要显式管理，目前流行的基于Cache的存储系统编写的程序都不能很方便地在使用SPM的系统中运行. 在基于经典的Cache-Bus-Memory结构的实时系统方面，很多研究者都提出了不同的解决方案. 在Cache层次，多核之间需要时间可预测的一致性通信算法，目前这方面的工作主要有University of Waterloo的研究人员提出的可预测MSI方法PMSI，以及PMESI，CARP等方法；而多核Cache内部同一处理器的访问需要具备时间可预测性，目前流行的解决方法是采用TDMA的调度方式消除时间不确定性. 未来这方面的工作主要集中在提高一致性方法的性能并减少消耗上. 总线结构和调度方法上，需要着重考虑实时性和性能之间的权衡. 严格轮询的调度具有很好的可预测性，但会严重损失性能. TDMA的调度方法是目前性能和实时性之间综合考虑的选择. 未来的实时系统使用怎样的总线结构和调度方法仍然有一定的挑战. 存储器控制器和总线面临的情况类似. 与总线系统相比，存储器控制器仅需要调度一侧的请求. 未来对实时系统中存储系统的创新更有可能是整体结构的重新设计，在保证实时性的基础上能以较小的开销实现、迁移基于经典存储系统编写的程序.
作者贡献声明：龚小航、蒋滨泽共同调研并撰写论文；陈香兰、高银康、李曦提供论文指导和修改意见.
-
![]()
图 4 基于DRL的控制逻辑布线算法流程图
Figure 4. Flow chart of DRL-based control logic routing algorithm
![]()
图 5 流阀门f1至f5的模式序列以及初始化的布线网格
Figure 5. Pattern sequences of flow valves f1 to f5 and initialized routing grid
![]()
图 8 本文算法与DRA针对RC02生成的布线结果
Figure 8. Routing results generated by our proposed algorithm and DRA for RC02
表 1 DuelingDQN架构配置
Table 1 Configuration of DuelingDQN Architecture
网络层数 网络类型 神经元数量 激活函数 1 输入层 7 2 隐层（全连接） 64 ReLu 3 隐层（全连接） 128 ReLu 4 隐层（全连接） 128 ReLu 5 输出层 5 
下载: 导出CSV
表 2 本文所用测试用例的详细信息
Table 2 Details of Test Cases Used in Our Paper
测试用例 网格大小 流阀门数量 控制阀门数量 RC01 18×34 20 75 RC02 18×43 26 92 RC03 18×53 31 123 RC04 18×59 28 139 RC05 18×82 50 229 RC06 19×98 52 327
下载: 导出CSV
表 3 本文使用的参数设置
Table 3 Setting of Parameters Used in Our Paper
参数 取值 参数 取值 c1p 20 c4n −10 c2p 15 BS 128 c3p 8 EP 45000 c1n −40 ε 0.9 c2n −2 Uc 200 c3n −5 ∂ 10-3
下载: 导出CSV
表 4 控制通道总长度的比较
Table 4 Comparison of the Total Control Channel Length
测试用例 通道总长度/mm 优化率/% DRA 本文算法 DRA RC01 268.2 231.6 13.6 RC02 332.8 296.6 10.9 RC03 455.8 405.2 12.5 RC04 483.0 415.8 13.9 RC05 699.6 618.4 11.6 RC06 903.4 804.0 11.0 平均 12.3
下载: 导出CSV
表 5 信号传输时延的比较
Table 5 Comparison of the Signal Transmission Delay
测试用例 时延/s 优化率/% DRA 本文算法 DRA RC01 2.0 1.6 20.0 RC02 1.6 1.4 12.5 RC03 1.8 1.4 22.2 RC04 1.8 1.6 11.1 RC05 2.2 1.8 18.2 RC06 2.0 1.6 20.0 平均 17.3
下载: 导出CSV
表 6 本文算法的泛化性验证
Table 6 Generalization Verification of Our Proposed Algorithm
测试用例 通道总长度/mm 优化率/% 时延/s 优化率/% DRA 本文算法 DRA DRA 本文算法 DRA RC05 699.6 625.8 10.5 2.2 1.8 18.2 RC06 903.4 821.0 9.1 2.0 1.6 20.0
下载: 导出CSV
表 7 DuelingDQN在控制通道总长度方面的有效性验证
Table 7 Effectiveness Validation of DuelingDQN with Respect to the Total Control Channel Length
测试用例 通道总长度/mm 优化率/% DQN DoubleDQN DuelingDQN DQN DoubleDQN RC01 249.8 241.4 231.6 7.3 4.1 RC02 328.7 315.4 296.6 9.8 6.0 RC03 456.8 426.2 405.2 11.3 4.9 RC04 480.2 448.0 415.8 13.4 7.2 RC05 687.2 642.2 618.4 10.0 3.7 RC06 890.4 844.6 804.0 9.7 4.8 平均 10.3 5.1
下载: 导出CSV
表 8 DuelingDQN在信号传输时延方面的有效性验证
Table 8 Effectiveness Validation of DuelingDQN with Respect to the Signal Transmission Delay
测试用例 时延/s 优化率/% DQN DoubleDQN DuelingDQN DQN DoubleDQN RC01 1.8 1.8 1.6 11.1 11.1 RC02 1.6 1.4 1.4 12.5 0.0 RC03 1.8 1.6 1.4 22.2 12.5 RC04 1.8 1.6 1.6 11.1 0.0 RC05 2.2 1.8 1.8 18.2 0.0 RC06 2.0 1.8 1.6 20.0 11.1 平均 15.6 5.8
下载: 导出CSV
表 9 对角型布线在控制通道总长度方面的有效性验证
Table 9 Effectiveness Validation of Diagonal Routing with Respect to the Total Control Channel Length
测试用例 通道总长度/mm 优化率/% MHR 本文算法 MHR RC01 292.0 231.6 20.7 RC02 383.0 296.6 22.6 RC03 509.0 405.2 20.4 RC04 534.0 415.8 22.2 RC05 768.0 618.4 19.5 RC06 996.0 804.0 19.3 平均 20.8
下载: 导出CSV
表 10 对角型布线在信号传输时延方面的有效性验证
Table 10 Effectiveness Validation of Diagonal Routing with Respect to the Signal Transmission Delay
测试用例 时延/s 优化率/% MHR 本文算法 MHR RC01 2.1 1.6 23.8 RC02 1.8 1.4 22.2 RC03 2.1 1.4 33.3 RC04 2.2 1.6 27.3 RC05 2.6 1.8 30.8 RC06 2.5 1.6 36.0 平均 28.9
下载: 导出CSV
表 11 本文算法的训练和推理时间以及DRA和MHR的运行时间
Table 11 Training Time and Inference Time of Our Proposed Algorithms and Running Time of DRA and MHR
测试用例 训练时间/min 推理时间/s 运行时间/s 本文算法 本文算法 DRA MHR RC01 90.3 0.1 0.1 0.1 RC02 112.5 0.1 0.2 0.1 RC03 150.2 0.1 0.3 0.1 RC04 172.5 0.1 0.3 0.2 RC05 225.2 0.2 0.3 0.2 RC06 337.5 0.2 0.4 0.2
下载: 导出CSV
-
[1] Huang Xing, Ho T, Guo Wenzhong, et al. Computer-aided design techniques for flow-based microfluidic lab-on-a-chip systems[J]. ACM Computing Surveys, 2021, 54(5): 1−29
[2] Liu Genggeng, Huang Hongbin, Chen Zhisheng, et al. Design automation for continuous-flow microfluidic biochips: A comprehensive review[J]. Integration, 2022, 82: 48−66
[3] Hu Xu, Chen Zhen, Chen Zhisheng, et al. Architectural synthesis of continuous-flow microfluidic biochips with connection pair optimization[J]. Electronics, 2024, 13(2): 247 doi: 10.3390/electronics13020247
[4] Einav S, Gerber D, Bryson P D, et al. Discovery of a hepatitis C target and its pharmacological inhibitors by microfluidic affinity analysis[J]. Nature Biotechnology, 2008, 26(9): 1019−1027 doi: 10.1038/nbt.1490
[5] Hong J W, Chen Yan, Anderson W F, et al. Molecular biology on a microfluidic chip[J]. Journal of Physics: Condensed Matter, 2006, 18(18): 691−701 doi: 10.1088/0953-8984/18/18/S14
[6] Unger M A, Chou H P, Thorsen T, et al. Monolithic microfabricated valves and pumps by multilayer soft lithography[J]. Science, 2000, 288(5463): 113−116 doi: 10.1126/science.288.5463.113
[7] Thorsen T, Maerkl S J, Quake S R. Microfluidic large-scale integration[J]. Science, 2002, 298(5593): 580−584 doi: 10.1126/science.1076996
[8] Huang Xing, Ho T, Chakrabarty K, et al. Timing-driven flow-channel network construction for continuous-flow microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(6): 1314−1327
[9] Araci I E, Quake S R. Microfluidic very large scale integration (mVLSI) with integrated micromechanical valves[J]. Lab on a Chip, 2012, 12(16): 2803−2806 doi: 10.1039/c2lc40258k
[10] Fidalgo L M, Maerkl S J. A software-programmable microfluidic device for automated biology[J]. Lab on a Chip, 2011, 11(9): 1612−1619 doi: 10.1039/c0lc00537a
[11] Lim Y C, Kouzani A Z, Duan W. Lab-on-a-chip: A component view[J]. Microsystem Technologies, 2010, 16: 1995−2015 doi: 10.1007/s00542-010-1141-6
[12] Tseng T M, Li Mengchu, Freitas D N, et al. Columba 2.0: A co-layout synthesis tool for continuous-flow microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(8): 1588−1601
[13] Yang Kailin, Yao Hailong, Ho T, et al. AARF: Any-angle routing for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(12): 3042−3055 doi: 10.1109/TCAD.2018.2789356
[14] Wang Qin, Zuo Shiliang, Yao Hailong, et al. Hamming-distance-based valve switching optimization for control-layer multiplexing in flow-based microfluidic biochips[C]//Proc of the 22nd Asia and South Pacific Design Automation Conf. Piscataway, NJ: IEEE, 2017: 524−529
[15] Wang Qin, Xu Yue, Zuo Shiliang, et al. Pressure-aware control layer optimization for flow-based microfluidic biochips[J]. IEEE Transactions on Biomedical Circuits and Systems, 2017, 11(6): 1488−1499 doi: 10.1109/TBCAS.2017.2766210
[16] Zhu Ying, Huang Xing, Li Bing, et al. Multicontrol: Advanced control-logic synthesis for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(10): 2489−2502
[17] Huang Xing, Cai Huayang, Guo Wenzhong, et al. Control-logic synthesis of fully programmable valve array using reinforcement learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(1): 277−290 doi: 10.1109/TCAD.2023.3309740
[18] Liang Siyuan, Li Mengchu, Tseng T M, et al. CoMUX: Combinatorial-coding-based high-performance microfluidic control multiplexer design[C/OL]//Proc of the 41st ACM Int Conf on Computer-Aided Design. New York: ACM, 2022 [2024-06-19]. https://dl.acm.org/doi/abs/10.1145/3508352.3549353
[19] Chen Zhisheng, Huang Xing, Guo Wenzhong, et al. Physical synthesis of flow-based microfluidic biochips considering distributed channel storage[C]//Proc of Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2019: 1525−1530
[20] Hu Kai, Dinh T A, Ho T, et al. Control-layer routing and control-pin minimization for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 36(1): 55−68
[21] 曾俊杰,秦龙,徐浩添,等,基于内在动机的深度强化学习探索方法综述[J]. 计算机研究与发展,2023,60(10):2359−2382 Zeng Junjie, Qin Long, Xu Haotian, et al. Exploration approaches in deep reinforcement learning based on intrinsic motivation: A review[J]. Journal of Computer Research and Development, 2023, 60(10): 2359−2382 (in Chinese)
[22] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]//Adaptive Computation and Machine Learning. Cambridge, MA: MIT, 2018
[23] 唐楚哲,王肇国,陈海波. 机器学习方法赋能系统软件:挑战、实践与展望[J]. 计算机研究与发展,2023,60(5):964−973 Tang Chuzhe, Wang Zhaoguo, Chen Haibo. Empowering system software with machine learning methods: Challenges, practice, and prospects[J]. Journal of Computer Research and Development, 2023, 60(5): 964−973 (in Chinese)
[24] Kober J, Bagnell J A, Peters J. Reinforcement learning in robotics: A survey[J]. The International Journal of Robotics Research, 2013, 32(11): 1238−1274 doi: 10.1177/0278364913495721
[25] Mnih V, Kavukcuoglu K, Silver D, et al. Human-level control through deep reinforcement learning[J]. Nature, 2015, 518(7540): 529−533 doi: 10.1038/nature14236
[26] Wang Ziyu, Schaul T, Hessel M, et al. Dueling network architectures for deep reinforcement learning[C]//Proc of the 33rd Int Conf on Machine Learning. Cambridge, MA: MIT, 2016: 1995−2003
[27] Liu Chunfeng, Huang Xing, Li Bing, et al. DCSA: Distributed channel-storage architecture for flow-based microfluidic biochips[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(1): 115−128
[28] Marcus J S, Anderson W F, Quake S R. Microfluidic single-cell mRNA isolation and analysis[J]. Analytical Chemistry, 2006, 78(9): 3084−3089 doi: 10.1021/ac0519460
[29] Van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double q-learning[C]//Proc of the 30th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2016: 2094−2100
[30] Mnih V, Kavukcuoglu K, Silver D, et al. Playing Atari with deep reinforcement learning[J]. arXiv preprint, arXiv:1312.560, 2013
计量
- 文章访问数: 46
- HTML全文浏览量: 2
- PDF下载量: 7
