多核堆栈处理器研究与设计

刘自昂，周永录，2+，代红兵，2，刘宏杰，2

(1.云南大学 信息学院，云南 昆明 650500；2.云南大学 云南省高校数字媒体技术重点实验室，云南 昆明 650223)

0 引 言

Forth语言是一种可交互性开发和易于移植的结构化高级程序设计语言，具有程序小、运行快的特点[1]。Forth语言是以堆栈为核心，所有的操作都基于参数堆栈和返回堆栈，这使得Forth语言在寄存器式处理器上运行会增加的处理器资源消耗，降低Forth程序的运行速度。所以，Forth工程师们开发出了基于堆栈的处理器。堆栈处理器因任务切换快、切换开销低、资源占用少，可以高效执行Forth程序，并且Forth语言可以为不同硬件平台快速构建出Forth系统，这些特点使堆栈处理器嵌入式领域取得了成功[2-5]。

在Forth发展的几十年来出现了多种经典的堆栈处理器，例如，MSL16、EP32、b16[6]、Kalachev实现的Forth软核[7]等，在嵌入式应用领域里都有良好的表现。随着嵌入式环境的复杂性日益增高，多任务Forth系统内的实时任务增多，这些实时任务按同优先级时间片轮转的方式交叉执行[8-10]，在单核堆栈处理器硬件平台上容易出现低优先级实时任务“饿死”的现象，而多核堆栈处理器可以很大程度上缓解任务“饿死”的问题，因此多核堆栈处理器成为了Forth领域研究的热点之一。

在国外，GreenArrays公司在2009年后先后推出了GA4、GA32以及GA144片上多计算机芯片，其中，GA144由144个F18A堆栈计算机的二维阵列构成，其指令执行速度高达960亿条指令/s，震惊业界[11-13]。在国内，南京航空航天大学何凯成等实现了一个双核堆栈处理器，该处理器的主核和从核都是其自研的内核，主核负责与其它模块通信，从核只与主核连接且所有任务都由主核分配，该双核堆栈处理器的总工作频率达到了209.8 MHz。

总体上看，国内和国外在多核堆栈处理器的研究上都相对匮乏，目前有据可查的多核堆栈处理器与堆栈片上多处理机仅有上述几种，它们无论是在原理上还是在体系架构上都存在明显的不同，其实现及应用也还尚局限于特定的方面。

1 J1堆栈处理器模型

J1是James Bowman等设计的一款基于冯·诺依曼架构的16位单核堆栈处理器模型[14]，其结构如图1所示。

图1 J1处理器结构

J1拥有一个参数堆栈D和一个返回堆栈R，这两种堆栈深度均为32，为方便对堆栈进行操作，James为参数堆栈设置了一个参数堆栈栈顶寄存器T，用来存放参数堆栈栈顶的数据。另外，J1采用双端口RAM用来存储Forth系统，每个周期都可以同时读出一条指令和数据，这种设计方式可以允许J1的访存操作只需要一个周期即可完成。

J1指令为单周期指令，它具有5种基本指令格式，分别是Literal指令、Jump指令、Conditional Jump指令、Call指令和ALU指令，这几种指令的结构如图2所示。其中，ALU指令中有一位剩余空闲保留位，这一位使ALU指令拥有一定的指令扩展能力，但扩展能力十分有限，不能满足多核环境下对指令的需求。

图2 J1指令集结构

虽然J1堆栈处理器不支持中断和异常，不能对突发状况做出响应，也不支持多任务Forth系统，但是J1的结构简单，功耗较低且具有较高的性能，适合在它的基础上设计多核堆栈处理器的内核。

2 L32-MC多核堆栈处理器设计

2.1 L32堆栈处理器模型设计

在J1模型的基础上，将字长从16位扩展成32位，同时增加了有限状态机、时间计数器、中断、指令总线通信模块、数据总线通信模块、IO总线通信模块和临界资源申请模块，形成了一种新的32位单核堆栈处理器模型——L32堆栈处理器模型，如图3所示。

图3 L32堆栈处理器模型

L32的有限状态机包括停止态、中断执行态、普通执行态、访存态4种状态，如图4所示。有限状态机在停止状态下，收到时间计数器模块或内核控制器发来的启动内核的信号后进入中断执行态，L32运行中断服务程序。在中断执行态下，当中断服务程序发出内核停止指令时，L32的有限状态机将进入停止态，此时L32将停止运行。中断执行态和普通执行态是非常相似的两个状态，它们的区别在于中断执行态是关中断的普通执行态。当L32处于普通执行态时发生中断，有限状态机进入中断执行态，L32转入对应的中断服务程序，中断服务完毕后，有限状态机从中断执行态返回到普通执行态。无论是中断执行态或者是普通执行态，当L32需要访问RAM时，有限状态机进入访存态，并根据访问需求向数据、指令或IO总线申请总线使用权，访问RAM完成后，有限状态机返回发起总线申请之前的执行态。

图4 L32堆栈处理器状态

在L32中，时间计数器模块用于计时或计数操作，该模块可以由指令进行控制。在计时完成时，时间计数器会向中断控制模块发出中断信号，中断控制模块收到该中断信号后，立刻使有限状态机进入中断执行态。

指令总线通信模块、数据总线通信模块和IO总线通信模块是L32通过指令总线、数据总线和IO总线与其它设备通信的接口。以数据总线通信模块为例，L32需要访问RAM中的数据时，数据总线通信模块使有限状态机进入访存态，同时向数据总线发出申请使用信号。数据总线通信模块获得数据总线使用权后，将访存地址通过数据总线送入多端口存储器中，取得所需数据后，使有限状态机回到申请数据总线之前的状态，同时释放数据总线使用权。指令总线通信模块和IO总线通信模块与数据总线通信模块的通信过程相似。

中断控制模块和临界资源申请模块在本文2.2部分进行描述。

2.2 L32-MC多核堆栈处理器模型设计

基于L32单核堆栈处理器模型，可以构建出多核堆栈处理器模型L32-MC，其结构如图5所示。L32-MC多核堆栈处理器模型由多个L32内核、内核控制器、中断控制器、临界资源仲裁器、多端口存储器、数据总线、指令总线、IO总线和外设组等部分构成。

图5 L32-MC多核堆栈处理器模型

L32-MC多核堆栈处理器模型采用同构内核架构，每个内核都是一个L32单核堆栈处理器，这些L32内核具有完全相同的地位和功能，Forth任务可以在任意一个内核上运行。

L32内核的中断控制模块除了响应来自时间计数器模块的中断请求，还响应来自中断控制器的中断请求。当一个中断信号到来后，首先保存程序计数器的值(若是核内中断还会从中断控制器内获取中断服务程序地址)，再将与中断信号一同到来的中断服务程序地址送入程序计数器中，使内核转去执行中断服务程序，这整个中断响应过程仅需两个时钟周期即可完成。在堆栈深度32时，几乎所有的Forth任务都不会出现堆栈溢出情况，L32内核的堆栈深度为64，因此L32内核被设计为只能发生一层中断，即L32内核不支持中断嵌套。中断控制器支持16个具有优先级的中断源，它内有一块存储器用来存储中断向量表，并提供其它模块访问中断向量表的接口。所有中断源的中断服务程序地址都保存在中断控制器的中断向量表中，通过Mix指令的中断功能可以快速修改这些中断服务程序的地址，使Forth系统在运行时可以对中断服务程序快速定位和热更新。当一个中断源的请求需要被响应时，中断控制器会通过轮询的方式选择一个合适的内核去响应中断，同时将中断服务程序的地址送入该内核。

内核控制器是用来控制和存储处理器中所有L32内核的运行状态。在内核控制器看来，L32内核的运行状态只有两种：运行态和停止态，这两种状态都由多任务Forth系统进行控制，当系统中需要更多的内核执行任务时便通过“内核编号”+“内核启动指令”将停止态的L32内核唤醒，而当系统中只需要较少的内核执行任务时便通过“内核停止指令”将某些运行态的内核停止。

L32内核通过临界资源申请模块与临界资源仲裁器进行通信，这两个模块与访问临界资源相关的指令配合可以实现各个Forth任务正确访问临界资源的功能。本文所述的临界资源特指Forth系统中一组代表独享资源数量的系统变量，Forth任务通过临界资源仲裁器获得临界资源的访问权限才可以改变这些系统变量。当某一个独享资源的系统变量值为0时，其它任务则不可以访问该独享资源。某个Forth任务发出了申请临界资源访问权指令时，临界资源申请模块向临界资源仲裁器发出申请信号，临界资源仲裁器会查询其内部的状态存储器，若状态存储器值为0时，表示多任务Forth系统中没有任务访问临界资源，则向申请方发送申请成功信号并修改状态存储器值为1，该Forth任务获得临界资源访问权；若状态存储器值为1时，表示有其它任务正在访问临界资源，则向申请方发送申请失败信号。释放临界资源访问权时，临界资源申请模块向临界资源仲裁器发出释放信号，临界资源仲裁器直接将状态存储器值置为0。

2.3 L32-MC指令集设计

L32-MC的指令集沿用参考J1指令集的设计风格，有5种类型的指令，分别是Literal指令、Jump指令、CJump指令、Call指令和Mix指令，每个指令字长均为32位，指令结构如图6所示。这些指令的操作较为简单，均可在一个时钟周期内完成。

图6 L32-MC指令集结构

指令的第31位为1时表示这条指令为Literal指令，这类指令的0～30位存储无符号整数，范围为0～2147483647。Literal指令的功能是将Value送入参数堆栈，并将参数堆栈指针加1。

Jump指令、CJump指令和Call指令的0～28位存储跳转目的地址Target，该跳转地址以字为单位，跳转范围为0～1FFFFFFF，寻址方式为直接寻址。

指令的29～31位为011时表示这条指令为Mix指令，这类指令中具有多个位域，每个区域都具有不同的功能，见表1和表2。Mix指令Set位区的功能描述中，tcb寄存器用于存储Forth任务tcb的首地址，_pc_寄存器用于L32内核进入中断执行态时存储当前程序计数器的值，terminal寄存器用于存储当前Forth任务的任务编号。

表1 Mix指令功能

表2 ALU操作码及操作

2.4 总线设计

在L32-MC中，数据总线、指令总线和IO总线都采用了Wishbone总线协议。Wishbone总线是一款免费开源的片上总线协议，具有功能强大，复杂度低的特点，它基于主从式架构，拥有高效且规范的信号接口[15，16]。Wishbone总线有多种互联类型，L32-MC中的Wishbone总线采用共享总线互联和十字开关互联。

数据总线用于L32内核与多端口存储器进行数据上的通信，采用共享总线方式互联，内部有一个轮询总线仲裁器。当L32内核需要从多端口存储器内的RAM读写数据时，L32内核中数据总线通信模块向数据总线申请使用权。数据总线以轮询的方式对主设备分配数据总线使用权，L32内核的数据总线通信模块获得数据总线使用权后，将访问地址和读写标识通过数据总线送入多端口存储器完成读写操作。数据总线的整个操作过程最少需要3个周期。数据总线互联方式如图7所示，箭头虚线表示数据总线仲裁器把数据总线的使用权分配给了L32_0内核。数据总线上所有L32内核为主设备，一个多端口存储器为从设备。

图7 数据总线互联方式

指令总线用于L32内核与多端口存储器进行指令上的通信，采用共享总线方式互联，内部有一个轮询总线仲裁器。指令总线上所有L32内核为主设备，一个多端口存储器为从设备。L32内核从多端口存储器内的RAM中获取指令的操作与通过数据总线从RAM中获取数据的操作相同。在指令总线中不仅有一套标准的Wishbone信号线用于访问RAM外，而且为每个L32内核设置了一套用于访问ROM的专用信号线，每套专用信号线包括一个ROM地址线和ROM数据线。当L32内核不访问RAM内的指令时，L32内核的指令总线接口会被指令总线内的2路选择器连接到访问ROM的信号线。指令总线互联方式如图8所示，箭头虚线表示指令总线的仲裁器把指令总线的使用权分配给了L32_0内核，实线表示内核没有得到指令总线的使用权时总是与ROM连接。

图8 指令总线互联方式

IO总线用于L32内核与外设进行数据上的通信，采用十字开关的方式互联。IO总线上所有L32内核为主设备，所有外设为从设备。外设分为共享设备和独占设备，IO总线为每个共享设备都设置了一个轮询仲裁器，用于对来自L32内核使用申请进行仲裁，而独占设备则没有仲裁器，这类设备的使用权通过Forth系统进行分配。L32内核访问一个共享设备的操作与L32内核通过数据总线访问RAM的操作相似，在访问共享设备的过程中需要附带共享设备的编号，方便IO总线寻找共享设备。Forth任务访问一个独占设备前需要在多任务Forth系统中获取独占设备的访问权，然后多任务Forth系统将获得访问权的Forth任务编号写入IO总线内用于存储独占设备访问权的权限存储器中，每个独占设备在权限存储器中都有一块对应的存储空间，当一块存储空间存储了一个Forth任务编号时，表示该存储空间对应的独占设备被分配给了该Forth任务。在Forth任务访问独占设备时，需要将当前Forth任务编号和权限存储器中对应独占设备的Forth任务编号进行对比，编号一致时允许该内核访问申请的独享设备，编号不一致时不允许访问。IO总线互联方式如图9所示，箭头虚线表示IO总线内的各个共享外设的仲裁器把设备的使用权分配给了内核，虚线表示运行在该内核上的Forth人物获得了该独占外设的使用权。

图9 IO总线互联方式

2.5 多端口存储器设计

一个功能相对完整的32位多任务Forth系统大小约为20 KB左右，完全可以将整个Forth系统放入存储器之中，因此在本存储器设计中，未采用从外部存储器加载Forth系统的形式，而是使用Verilog的系统函数将Forth系统写入多端口存储器之中，使整个存储器模块复杂性大大降低。作为示意，图10中给出了双核模型的存储器结构。

图10 双核L32-MC的多端口存储器结构

在图10所示的存储器结构中有两个ROM和一个RAM，均采用FPGA双端口BRAM资源实现。所有ROM大小均为24 KB，地址范围均是0～17FF；RAM大小为56 KB，地址范围是1800～4FFF。ROM和RAM存储器位宽都为32 bit。ROM中存放多任务Forth系统基础词的指令和其它必要的数据，RAM则是多任务Forth系统的运行内存。ROM0和RAM的一个端口用作所有L32内核在Forth系统运行中对数据的存取(仅RAM存取，ROM0只读)，这两个端口为共享端口，在使用时需要通过数据总线访问。RAM另一个端口用于所有L32内核读取RAM中的指令，这个端口为共享端口，在使用时需要通过指令总线访问。ROM0另一个端口和其它ROM的所有端口用于所有L32内核读取ROM中的指令，这些端口都为独享端口，在使用时需要L32内核通过指令总线的专用信号线访问。每个L32内核都需要占用一个ROM端口，当内核增多后，空闲ROM端口不够时则需要新增一个ROM。这种ROM设计相当于每个L32内核都有一个独享的Forth基本系统指令ROM存储器，L32内核运行Forth基本系统内的程序时都从自己的Forth基本系统指令ROM存储器中获取。

3 实验验证

L32和L32-MC均采用Verilog HDL进行描述，在Xi-linx XC7A100T FPGA芯片上进行L32单核堆栈处理器和4核、8核的L32-MC多核堆栈处理器的实现，时钟频率均为100 MHz，资源使用情况见表3。表中L32-4和L32-8分别代表L32-MC的4核和8核堆栈处理器实现。

表3 FPGA资源使用情况

目前，能够查询到的多核堆栈处理器较少，且都未公开具体的实验数据，也没有公开处理器源码及其搭配的Forth系统源码，故本文所设计的处理器难以与之进行对比与评价。因此，本研究使用自研多任务Forth系统以及测试验证程序来对L32堆栈处理器和4核、8核的L32-MC堆栈处理器的性能进行验证测试，并以J1堆栈处理器的性能为基准进行评价。

L32、L32-4和L32-8堆栈处理器运行多任务Forth系统，系统中的多任务调度算法采用多级反馈队列算法对Forth任务进行调度，J1堆栈处理器则运行单任务Forth系统。在实验中，J1、L32、L32-4和L32-8的工作频率均为100 MHz。

为测试验证L32-MC处理器的任务执行性能，本实验采用斐波那契数求解、冒泡排序和矩阵乘法3种任务在J1、L32和L32-MC堆栈处理器上运行。斐波那契数任务是使用递归的方法求第20个斐波那契数；冒泡排序任务是按从小到大的顺序对200个随机数进行排序；矩阵乘法任务是计算两个32阶矩阵的乘法。为使L32-4和L32-8的各个L32内核都忙碌，在清空多任务Forth系统的所有任务后，分别运行以下测试任务一、二和三。

测试任务一：在J1处理器上，循环执行24次斐波那契数求解任务，得到24次求解任务总执行时间；分别在L32、L32-4和L32-8上，各运行24个斐波那契数求解任务且各任务相互独立，分别得到24个斐波那契数求解任务总执行时间。

测试任务二：在J1处理器上，循环执行24次冒泡排序任务，取得任务总执行时间；分别在L32、L32-4和L32-8上，各运行24个冒泡排序任务且各任务相互独立，分别得到任务总执行时间。

测试任务三：在J1处理器上，执行一次两个32阶矩阵乘法任务，得到矩阵乘法的计算时间；分别在L32、L32-4和L32-8上，各运行一个矩阵乘法任务，得到两个32阶矩阵相乘的计算时间，该时间包括各个子任务通信时间。

测试任务一、二和三的总执行时间见表4。

表4 各测试任务执行时间/ms

为测试验证L32-MC多核处理器的指令执行速度，在Vivado软件仿真环境下，使L32内核和L32-MC的每个内核上执行一个循环累加任务，不断获取每个L32内核运行时的执行时间和执行指令数，再对所获取的执行指令数求取平均值，可得出L32和L32-MC平均的每秒执行指令数，见表5。

表5 L32-MC平均每秒执行指令数/MIPS

通过表4和表5的实验数据可知，L32相对于J1的任务执行性能下降了大约20%，指令性能下降0.26%。L32的任务执行性能与多任务Forth的性能有直接关系，由于多任务Forth系统中存在切换任务和时间片大小等原因造成了额外时钟周期消耗和频繁的任务切换，直接导致了L32任务执行性能的下降，若多任务Forth系统进一步优化，则L32的任务执行性能会进一步提升；L32处理器在从普通执行态转换到中断执行态是需要消耗额外的一个时钟周期，用于保存当前任务的执行地址，并不执行从多端口存储器中读取的指令，造成了指令性能的下降。在功耗方面，L32比J1降低了4%，这是因为FPGA中BRAM资源消耗能源相对较高，而J1处理器无论什么情况下均激活RAM的两个访问端口，增加了总体的功耗，而L32针对该问题进行优化，使RAM的两个端口仅在被需要时进行激活，降低了功耗，另外L32内核使用HDL语言实现时提高了电路的复用性，实现更多功能的同时使用更少的逻辑单元数量，进一步降低了功耗。L32-4在任务执行性能上，相对于J1平均有290%的提升，执行指令性能有395%的提升，功耗仅增加了38%。L32-8在任务执行性能上，相对于J1平均有548%的提升，执行指令性能有791%的提升，功耗仅增加了118%。L32-4和L32-8处理器在执行任务的性能上，均未接近J1的4倍和8倍，原因仍在于多任务Forth系统存在任务切换等必要消耗。在功耗方面，L32-4和L32-8处理器仅增加了L32内核数和存储器内ROM个数，总线和各类控制器等结构并未改变，所以功耗增加量较少。

上述实验数据表明了本文在J1堆栈处理器模型的基础上所设计的L32单核和L32-MC多核堆栈处理器具有更好的综合性能和功耗表现，满足高性能低功耗的多核处理器设计目标。

4 结束语

本文以J1堆栈处理器模型为基础，加入了有限状态机、中断、时间计数器等模块，形成了L32单核堆栈处理器模型。在L32模型的基础上，对多核结构、指令集、总线、多端口存储器等方面进行了研究与设计，提出了一种多核堆栈处理器模型L32-MC，在Xilinx XC7A100T FPGA板上实现了该模型4核和8核的堆栈处理器原型，并以100 MHz的时钟频率稳定运行。实验结果表明，L32-MC堆栈处理器的原型机具有良好的综合性能和功耗表现，为高实时性多核堆栈处理器的研究、设计与应用奠定了良好基础。