本发明涉及并行程序数据处理技术领域特别是 涉及一种多处理器系统及 其同步引擎装置。 背景技术

在并行程序中， 多个进程 /线程 （以下统称进程） 并行协同工作， 完成处 理任务。 多个进程在其运行周期中， 需要使用同步原语来实现多个进程之间的 同步。 同步原语是保证并行程序正确性的关键原语。 并行程序中常用的具有同 步含义的原语有 Lock和 Barrio图 1是并行程序中使用 Barrier同步原语实现 读写次序的例子示意图， 如图 1所示， 同步原语 Barrier可以保证进程 P2在读 取变量 A的值时， 读到的值一定是进程 P1写入的值。 Lock原语在科学计算中 一般是用来保证多个进程之间对某种资源的互 斥访问。它的实现一般依赖于处 理器提供的特殊指令来实现， 比如典型的 LL/SC指令。

除了 Barrier和 Lock这种只包含同步含义的原语以外， 在并行程序中还有 其他一些常用的， 隐含同步的原语， 如 Reduce或者 All-Reduce原语。 Reduce 原语可以简单地表示为 Reduce (Root,Ai,Op,Com), 其中 Root表示这次 Reduce 运算的根进程； Ai表示进程 i参与 Reduce的源数据； Op表示 Reduce的运算 模式， 常见的有"加"、 "减"、 "最大"、 "最小 "等； Com表示参与这个 Reduce 的进程的集合。 Reduce (Root,Ai，Op，Com)的含义如下： 在集合 Com内的每个 进程 i的数据 Ai， 均使用 Op模式进行运算， 并把运算结果返回至 Root。 在这 个 Reduce运算中， 隐含了 Com集合中所有进程和 Root进程的同步关系， 即 Root进程必须在所有 Com集合内的进程到达某个时间点之后， 才能获得最终 的运算结果， 并且在实现同步的同时， 也实现了数据在进程间的移动。

All-Reduce与 Reduce的区别仅仅在于最后的计算结果是广播到 Com内所有进 程， 而不仅仅是 Root。 在下文中除了特别说明， All-Reduce和 Reduce都统称 Reduce o

现有技术中使用软件实现上述同步原语具有较 好的灵活 但是执行效率 较低， 主要体现在启动开销大， 执行速度慢， 进程间通信次数多。 比如软件实 现的 Barrier可以用类似于计数器的方法， 使用一个共享内存的计数器 A， A 被 Root进程初始化为 Q然后每个参与 Barrier的进程都执行 A=A+1 的操作 然后不断在循环中读取 A的值 当 A的值等于参与 Barrier的进程总数的时 il吳 即表明所有进程都达到了同步。 这种软件实现的方法有两个问题， 一个是在执 行八=八+1的时候， 由于 Α是共享的， 可能被多个进程同时操作， 因此每个进 程都要保证自己的操作是原子操作， 因此需要用或者是锁技术， 或者是锁内存 总线的方法来保证原子操作， 而这些操作都是很费时， 并且影响处理器性能的 操作； 另外一个问题在于各个进程在循环中读取 A的值， 由于 A是分配在某 个处理器的内存上的， 在多处理器的环境下， 如果多处理器间有 Cache—致性 保证， 会导致大量的 Cache—致性控制信息在处理器间交换； 如果没有 Cache 一致性保证， 循环读取 A值的时候会引起大量的远程 Load操作， 无论哪种情 况都会导致多处理器的通信带宽被大量占用， 从而影响系统性能。

一种软件实现的 Reduce算法与上述 Barrier类似， 除了计算是否所有进程 都达到同步点以外， 还要对各个进程的数据进行计算， 计算的结果存放在共享 内存的变量 Value中。 假设进程 0的数据为 ValueO, 进程 1的数据为 Valuel ... 进程 N的数据为 ValueN。 Root进程根据 Reduce的操作类型初始化 Value, 比 如 Reduce的操作类型是 "最大"， 则把 Value初始化为计算机能够表示的最小 值， 然后每个进程 n进行如下操作：

if (Value n大于 Value)

Value = Value n;

同样的， 每个进程需要保证上述操作的原子性， 这样当所有进程都通过 Barrier所述的计数器 A判断完成计算后， Value的最终值就是所有进程的数据 中最大的的那个值， 每个进程就可以读取 Value的值了， 也就是完成了操作类 型为"最大"的 Reduce o

与 Barrier类似的， 软件实现多个处理器间的 Reduce, Lock操作也有类型 问题。 虽然软件使用一些改进算法可以减少上述的缺 点， 但是仍然不能从根本 上解决问题， 仍然存在执行次数慢， 消耗处理器执行资源等问题。 发明公开 本发明的目的在于提供一种多处理器系统及其 同步引擎装置。其能够很好 地在多处理器环境下支持各种常用同步操作， 具有执行速度快， 占用处理器通 信带宽小，无论处理器间是否有 Cache—致性都能适用等优点； 同时由于所述 的同步引擎装置是硬件实现的设备， 计算需要的原子性很容易得到保证。

为实现本发明的目的而提供的一种多处理器的 同步引擎装置， 包括： 多个存储队列，用于接收多个处理器发送的同 步原语，一个队列存储来自 一个处理器的所有同步原语；

多个调度模块， 用于在所述多个存储队列中选定用于执行的同 步原语之 后， 根据同步原语的类型， 发送到相对应的处理模块进行处理， 所述调度模块 与所述存储队列一一对应；

多个处理模块， 用于接收所述调度模块发来的同步原语， 执行不同功能； 虚拟同步存储结构模块，使用少量的存储空间 ，通过控制逻辑把所有处理 器的直属存储空间都映射为同步存储结构来实 现各种同步原语的功能；

主存端口，用于与所述虚拟同步存储结构模块 进行通讯，对各处理器的直 属存储进行读和写， 以及向所述处理器发起中断；

配置寄存器， 用于存储所述处理模块需要用到的各种配置信 息。

在同步原语存储到对应的存储队列里时，将同 时保存进程号信息， 以区别 同一处理器上不同进程发送过来的同步原语。

所述处理模块， 包括： Reduce 处理模块、 Barrier 处理模块、 Load/Store 处理模块， 以及 Put/Get处理模块。

所述同步引擎装置中的处理模块，能够根据同 步引擎装置支持的同步原语 的类型进行扩展。

所述同步存储结构是使用少量的片内存储虚拟 出来的，并不直接占用处理 器直属存储的空间。

所述同步存储结构是 {Count, P， L， Value} , {Count, P， L,}称为同步存储的

Tag, Count和 Value的位宽可以根据系统需求进行不同的设定� �� Value: 存储 单元，用于存储数据， L: Lock标志位，用于支持 Lock/Unlock原语； P: Produce 标志位，用于实现 Put/Get原语， Count:计数器，用于实现 Barrier原语、 Reduce 原语， 以及多种模式的 Put/Get原语。 计数器的位宽和同步引擎装置支持的最 大并行进程有关， n位 Count可以支持最大 2 ⁿ 个进程。 所述同步存储结构的虚拟方法是： 使用一块片内存储作为哈希表， 哈希表 中每一项的结构为 {关键值， Tag, Value} , 当处理模块写入一项同步存储结构 时， 所述处理模块执行指令， 把指令的地址作为关键值， 使用哈希算法在哈希 表内选择一行作为存储单元， 把同步结构存储下来； 当处理模块读取一项同步 存储结构时， 同样使用哈希算法找到对应于这个地址的项， 哈希表输出找到的 那一行的内容 { Tag, Value}； 如果读取过程中使用哈希算法没有找到对应的 项， 则说明当前指令应该暂缓执行， 则指令被重新回归相应的存储队列中， 等 候下次调度执行； 在同步原语被执行后， 如果同步存储结构的 Tag的执行结果 等于全 0， 则说明这一项同步存储结构已经被完全执行完 毕， 则在哈希表中释 放对应的存储空间； 当所述哈希表溢出的时候， 则使用所述主存端口向对应的 处理器发送中断， 在所述处理器直属内存中构造哈希表， 来存储所述同步存储 结构； 其中 {Count, P，L，}称为同步存储的 Tag; Value为存储单元。

为实现本发明的目的还提供一种采用所述的多 处理器的同步引擎装置的 多处理器系统， 其特征在于， 所述系统， 包括： 多个处理器和一个处理芯片， 其中- 所述处理芯片， 包括：

多个设备端口， 用于和所述多个处理器高速互联， 每个处理器和一个设备 端口连接；

所述同步引擎装置， 其中， 所述存储队列与所述多个设备端口互联； 在设备发现过程中，每个处理器通过标准设备 搜索流程搜索到与之互联的 设备端口， 并分配设备端口申请的各种资源； 所述同步引擎装置把自身的资源 通过设备端口映射到对应的处理器的操作系统 中，在多个处理器上的软件通过 映射关系操作所述同步引擎装置， 所述同步引擎装置被多个处理器共享。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Barrier原语的处理方法， 所述方法， 包括下列步骤：

110.同步引擎装置系统初始化： 指定多个连续地址的同步存储结构作为多 个 Barrier 变量， 同时维护一个表示多个 Barrier 变量完成状态的寄存器 Barrier_HW_State, 每个处理器在其直属的内存中申请一段空间 Barrier_State 作为 Barrier的完成状态表示；

120.N个进程调用 Barrier原语， 使用所述 Barrier变量执行一次 Barrier操 作 同时分别保存相应处理器的 Barrier—State的第 n位的状态到所述 N个进程 的本地变量 Local_Barrier_State;

130.所述同步引擎装置在接收到对所述 Barrier变量的 Store指令后， 根据 Store的物理地址向所述 Barrier变量写入值， 值的大小等于 N-1；

140.Barrier处理模块读取对应地址的同步存储结� ��， 如果不存在这项同步 存储结构， 或者读取到同步存储结构中的 Count等于 0， 则建立一项同步存储 结构， 其中的 Count等于 Store的值， 如果读取到同步存储结构 Count不等于 0， 则执行下一步骤 150;

150.所述 Barrier处理模块读取对应地址的同步存储结构� �把读取到的同 步存储结构的 Count减 1 ;

160.判断 Count值是否等于 0， 若是， 则所有进程都已经到达了同步点， 一次 Barrier 已经完成， 把 Barrier— HW— State 对应的位取反， 然后把 Barrier— HW_State广播到多个处理器的 Barrier— State的位置； 否则， 返回步骤 150；

170.每个所述进程在发送 Store 指令之后， 定时査询本处理器所属的

Barrier_State的第 n位的值， 如果査询到的值等于 Local_Barrier— Staten的值， 则表示本进程的 Barrier尚未完成， 则稍后再次査询； 如果查询到的状态不等 于 Local— Barrier— Staten, 则表示 Barrier已经完成， 所述进程退出査询状态， 同时退出 Barrier原语调用； 其中 Count为计数器。 同步引擎装置系统初始化 的步骤 110， 包括下列步骤：

111.指定多个连续地址的同步存储结构作为多� � Barrier变量并把指定信 息写入到所述配置寄存器中；

112.在所述同步引擎装置内部维护一个表示多� � Barrier变量完成状态的 寄存器 Barrier_HW— State, 每一位对应一个 Barrier变量的完成状态；

113.每个处理器在其直属的内存中申请一段空� � Barrier— State作为 Barrier 的完成状态表示， 每个处理器的 Barrier_State都被初始化为全 0， Barrier— State 在对应的处理器内部的各个进程是共享的， 各个进程都可以读取；

114.每个处理器把申请 Barrier— State 的物理地址发送到所述配置寄存器 中。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Reduce原语的处理方法， 所述方法， 包括下列步骤：

210.同步引擎装置系统初始化： 指定多个连续地址的同步存储结构作为多 个 Reduce 变量， 同时维护一个表示多个 Reduce 变量完成状态的寄存器 Reduce_HW_State _; 每个处理器在其直属的内存中申请一段空间 Reduce— State 作为 Reduce的完成状态表示；

220.N个进程调用 Reduce原语，使用所述 Reduce变量 Rn执行一次 Reduce 操作， 每个进程保存本处理器的 Reduce一 State 的第 n位的状态到本地变量 Local— Reduce—State；

230.每个参与 Reduce的进程把上述 Reduce原语的数据结构发送到同步引 擎装置； 所述同步引擎装置在接收到 Reduce数据结构之后， 根据 Reduce的物 理地址向所述 Reduce变量 Rn量写入值， 值的大小等于 N-1；

240.Reduce处理模块读取对应地址的同步存储结� �， 如果不存在这项同步 存储结构， 或者读取到同步存储结构中的 Count等于 0, 则建立一项同步存储 结构， 其中的 Count等于 N-l， 并把 Reduce数据结构中的源数据存储在同步 存储结构中的 Value中； 如果读取到同步存储结构 Count不等于 0， 则执行下 一步骤 250;

250.Reduce 处理模块读取对应地址的同步存储结构， 并把对应的 Count 减 1, 并把读取到的同步存储结构中的 Value和 Reduce数据结构中的源数据进 行运算， 把结果存放到同步存储结构中的 Value中；

260.判断 Count值是否等于 0， 若是， 则说明一次 Reduce 完成， 则把

Reduce_HW_State对应的位取反然后把 Reduce_HW— State广播到 n个处理器 的 Reduce— State的位置； 否则， 返回步骤 250;

270.每个进程在发送 Reduce 数据结构之后， 定时査询本处理器所属的 Reduce_State的第 n位的值， 如果査询到的状态等于 Local_Reduce—Staten， 则 表示本次进程的 Reduce尚未完成， 则稍后再次査询； 如果查询到的状态不等 于 Local_Reduce— Staten, 则表示 Reduce己经完成， 退出査询状态； 其中 Value 为存储单元； Count为计数器。

同步引擎装置系统初始化的步骤， 包括下列步骤：

211.指定多个连续地址的同步存储结构 {Count, P， L, Value}作为多个 Reduce变量， 并把指定信息写入到同步引擎装置的配置寄存 器中； 212.在同步引擎装置内部维护一个表示多个 Reduce变量完成状态的寄存 器 Reduce— HW_State， 每一位对应一个 Reduce变量的完成状态；

213.每个处理器在其直属的内存中申请一段空� � Reduce— State作为 Reduce 的完成状态表示， 每个处理器的 Red _UCe _St _a t _e 都被初始化为全 0;

214.每个处理器把申请 Reduce—State的物理地址发送到同步引擎装置的� �� 置寄存器中。

所述 Reduce原语的数据结构为 {Reduce变量地址， 操作符， 数据类型， 进程数目 -1， 源数据 }。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Lock 原语的处理方法， 所述方法， 包括下列步骤：

310.每个处理器在其直属的内存中申请变量 Lock—Result把这个变量的内 容清零， 并把这个变量的物理地址作为 Lock原语数据结构的返回物理地址；

320.所述同步引擎装置在接收到进程发送的 Lock原语的数据结构后， 根 据其中的目标物理地址读取同步存储结构， 如果读取不到同步存储结构， 或者 读取到的同步存储结构中的 L位等于 0， 则说明此物理地址尚未被加锁， 则 Lock原语执行成功， 转至下一步骤 330; 如果读取到的同步存储结构的 L位 等于 1， 则说明此物理地址已经被加锁， 则放弃本次 Lock的执行， 把 Lock原 语放入相应的存储队列中， 等候在此调度执行；

330.把同步存储结构中的 L位置 1并且保存， 根据所述返回物理地址， 向 直属的内存的 Lock— Result写入 1 ;

340.所述进程定时查询 Lock— Result, 如果读取到的 Lock— Result等于 0， 则表示尚未加锁成功， 则延时后再查询； 如果读取到的 Lock—Result等于 1， 则表示加锁成功， 退出 Lock调用； 其中 L为 Lock标志位。

所述 Lock原语数据结构为{返回物理地址， 目标物理地址 }， 返回物理地 址表示当加锁成功的时候，同步引擎装置会把 成功消息存放在主存中的返回物 理地址中； 目标物理地址表示软件希望对哪个物理地址进 行加锁。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Unlock原语的处理方法， 所述方法， 包括下列步骤：

进程把数据结构发送到所述同步引擎装置， 并退出 Unlock调用； 所述同步引擎装置在接收到 Unlock数据结构后， 根据目标地址从哈希表 中读取同步数据结构， 把其中的 L位清零， 如果同步数据结构在 L位清零后 等于全 0， 则释放这一项同步数据结构， 否则仅仅把 L位清零后的数据结构写 回； 其中 L为 Lock标志位。

所述 Unlock原语的数据结构为 {目标地址}， 数据结构中仅有的一个元素 表示需要解锁的变量地址。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Put原 语的处理方法， 所述方法， 包括下列步骤：

410.进程将 Put原语的数据结构发送到所述同步引擎装置， 并退出 Put调 用；

420.所述同步引擎装置的 Put处理模块根据 Put原语的数据结构中的目标 地址读取相应的同步存储结构， 如果不存在， 则新建一项同步存储结构， 如果 存在则读取已存在的同步存储结构；

430.把根据 Put原语的数据结构中的目标地址读取的相应的 同步存储结构 的 P位置 1， 并把接收到的 Put原语中的源数据存储到所述同步存储结构的 Value位； 其中 P为 Produce标志位； Value为存储单元。

所述 Put原语数据结构为{目标地址， 源数据 }， 其中， 目标地址表示 Put 原语中源数据被存放的物理地址； 源数据表示 Put原语中移动的数据内容。

为实现本发明的目的还提供一种所述多处理器 的同步引擎装置对于 Get 原语的处理方法， 所述方法， 包括下列步骤- 510.处理器在其直属的内存空间中申请一段空� � Get— Result用于存储 Get 返回值的数据结构， 并把申请到的空间清零；

520.所述 Get处理模块根据接收到的进程发送的 Get原语数据结构中的目 标地址， 读取对应的同步存储结构， 如果不存在对应的同步存储结构， 则放弃 Get的执行， 把 Get原语放回所述存储队列中， 等待再次被调度执行； 如果存 在对应的同步存储结构， 但是其中的 P位为 0， 则放弃 Get的执行， 把 Get原 语放回到所述存储队列中，等待再次被调度执 行；如果哈希表中存在对应的同 步存储结构， 而且其中的 P位为 1， 则执行下一步骤 530;

530.把读取到的同步存储结构中的 P清零， 把读取到的同步存储结构中的 Value内容， 根据 Get原语数据结构中的返回物理地址， 把返回值 { 1， Value}写 入处理器的直属存储中； 540.如果清零后同步存储结构的 Tag等于全零， 则释放对应的同步存储结 构项， 否则把 P位清零的同步存储结构写回；

550.定时査询 Get_Result中数据结构的完成标识， 如果查询结果为 0， 表 示 Get原语尚未执行完毕， 则延时一段时间后继续査询； 如果査询结果为 1， 则表示 Get原语执行完毕， 执行下一步骤 560;

560.读取 Get_Result中数据结构的返回数据， 退出 Get调用； 其中 P为 Produce标志位； Value为存储单元； {Count, P， L,}称为同步存储的 Tag。

所述 Get原语数据结构为{返回物理地址， 目标物理地址 }。数据结构中各 个元素的含义如下： 返回物理地址是当 Get成功执行后， 返回 Get的数据以及 完成标识的存放地址， Get返回值的数据结构如 {返回数据， 完成标识}， 此返 回值被连续存放在返回物理地址中；目标物理 地址表示 Get试图去获得的数据 的物理地址。

本发明的有益效果是： 本发明的同步引擎装置使用统一的共享存储结 构， 对 Barrier、 Lock/Unlock, Reduce > Put/Get等基本同步原语进行支持和加速， 大幅度提高同步原语的执行速度，减少进程间 的通信量，并简化同步原语的接 口， 不依赖于多处理器的 Cache—致性， 不依赖于处理器的特殊指令集， 使得 并行程序在使用同步原语时更加方便， 具有使用简单， 应用范围广， 执行速度 快的特点。 附图简要说明

图 1是并行程序中使用 Barrier同步原语实现读写次序的例子示意图； 图 2是本发明的多处理器的同步引擎装置的结构� �意图；

图 3是本发明另一实施例中多处理器的同步引擎� �置的结构示意图； 图 4是本发明中同步存储结构的示意图；

图 5是本发明中处理模块与同步存储结构进行通� �的结构示意图； 图 6是本发明的同步引擎中同步存储结构对于 Barrier原语的支持的步骤 流程图；

图 7是本发明中对于 Barrier原语的支持中同步引擎系统初始化的步� �流 程图； 图 8是本发明的同步引擎中同步存储结构对于 Reduce原语的支持的步骤 流程图；

图 9是本发明中对于 Reduce原语的支持中同步引擎系统初始化的步骤 流 程图；

图 10是本发明的同步引擎中同步存储结构对于 Lock原语的支持的步骤流 程图；

图 11是本发明的同步引擎中同步存储结构对于 Put原语的支持的步骤流 程图；

图 12是本发明的同步引擎中同步存储结构对于 Get原语的支持的步骤流 程图；

图 13是本发明的多处理器系统的结构示意图。 实现本发明的最佳方式

为了使本发明的目的、技术方案及优点更加清 楚明白， 以下结合附图及实 施例，对本发明的一种多处理器系统及其同步 引擎进行进一步详细说明。应当 理解， 此处所描述的具体实施例仅仅用以解释本发明 ， 并不用于限定本发明。

本发明的一种多处理器系统及其同步引擎，改 变使用软件实现同步原语的 方式， 使用统一的共享存储结构， 通过硬件装置实现对 Barrier、 Lock/Unlock、 Reduce, Put/Get等基本同步原语进行支持和加速，不依� �于多处理器的 Cache —致性， 不依赖于处理器的特殊指令集， 具有使用简单， 应用范围广， 执行速 度快的特点。

下面结合上述目标详细介绍本发明的一种多处 理器的同步引擎，所述同步 引擎， 图 2是本发明的多处理器的同步引擎的结构示意� �， 如图 2所示， 所述 同步引擎， 包括：

多个存储队列 1， 用于接收多个处理器发送的同步原语， 一个队列存储来 自一个处理器的所有同步原语；

处理器 1到 n发送的同步原语在发送到同步引擎时， 分别被存储在队列 1 到 n。

由于一个队列存储来在一个处理器的所有同步 原语， 而一个处理器上可能 运行多个进程， 因此在同步原语存储到对应的队列里时， 应该同时保存进程号 信息， 以区别同一处理器上不同进程发送过来的同步 原语。 在队列的出口处使 用调度模块对同一个队列里的来自不同进程的 同步原语进行调度 以保证来自 不同进程的同步原语不会相互阻塞。

多个调度模块 2， 用于在在所述多个存储队列中选定用于执行的 同步原语 之后， 根据同步原语的类型， 发送到相对应的处理模块进行处理， 所述调度模 块与所述存储队列一一对应；

多个处理模块 3，用于接收所述调度模块发来的同步原语，� �行不同功能; 所述处理模块如图 2中 Reduce处理模块、 Barrier处理模块、 Load/Store 处理模块， 以及 Put/Get处理模块。如果有同步引擎支持更多类� �的同步原语， 可以在这里扩展更多的处理模块。

在另一实施例中，所述处理模块还可存在如如 图 3所示的构成形式，所述 处理模块包括分散（Scatter)处理模块、运算（C alculate)处理模块、 Load/Store 处理模块， 以及聚集 （Gather) 处理模块。 其中聚集 （Gather) 处理模块用于 实现多对一的集合通信模式，将多个源端口的 消息聚集后，发送给特定的目的 端口， 该模块用于 Barrier和 Reduce操作的收集源数据过程。 分散 （Scatter) 处理模块用于实现一对多的集合通信模式，将 一个源端口的消息分发至多个目 的端口， 该模块用于 Barrier和 Reduce操作的分发结果过程。运算（Calculate) 处理模块用于实现计算功能，该模块用于聚集 处理模块提交的运算，实现 Lock 以及 Put/Get所需的运算功能。 Load/Store处理模块用于实现以 Load/Store方 式对同步存储结构的访问。 Barrier操作可以通过聚集（Gather)处理模块和分 散（Scatter)处理模块的配合完成， Reduce操作通过聚集（Gather)处理模块、 分散（Scatter) 处理模块和运算（Calculate)处理模块完成， Put/Get操作需要 运算 （Calculate) 处理模块和 Load/Store处理模块完成。

虚拟同步存储结构模块 4， 使用 RAM作为存储， 以及控制逻辑实现。 目 的在于使用少量的存储空间，通过控制逻辑把 所有处理器的直属存储空间都映 射为同步存储结构 { Count, P, L, Value }。从而达到使用这种同步存储结构来实 现各种同步原语的功能。 控制逻辑实现的映射方法在下面的文字中有描 述。

主存端口 5， 用于对各处理器的直属存储进行读和写操作， 以及向处理器 发起中断。 配置寄存器 6, 用于存储各种软件发送过来的配置信息。 配置信息包括如 发送中断时中断号是多少， 同步引擎在向直属存储写入必要信息时， 写入的物 理地址是多少等。配置寄存器用寄存器实现存 储，各个功能模块需要用到的配 置信息都从这里读取。

在图 2所示的处理模块中，使用到的数据都是由所� �虚拟同步存储结构模 块提供的同步存储结构 {Count, P， L, Value} , 这个存储结构是由所述同步引擎 使用少量的片内存储虚拟出来的， 并不直接占用处理器直属存储的空间。

一个存储队列 1存储来自一个处理器的所有同步原 i 在同步原语存储到 对应的存储队列 1里时， 同时保存进程号信息， 以区别同一处理器上不同进程 发送过来的同步原语； 在存储队列 1的出口处使用调度模块 2， 根据同步原语 的类型， 对同一个存储队列里的来自不同进程的同步原 语进行调度， 以保证来 自不同进程的同步原语不会相互阻塞； 多个处理模块 3 分别根据调度模块 2 的调度 并使用由所述虚拟同步存储结构模块 4提供的数据执行相应的同步原 语， 实现采用硬件装置对并行程序中的同步原语的 支持和加速。

对于普通的地址空间， 存储结构仅仅是存储数据的结构， 如对于 32位地 址 32，h0000_8600的地址 A来说， Store (A, 3556)的含义仅仅表示向地址 A写 入立即数 3556， 则 3556这个值被存储在地址 A的空间里。 当这个 Store指令 被执行完毕后， 使用 Load (A)指令读取地址 A 的内容， 则返回的值应该是 3556。 典型的处理器的直属存储， 也就通常意义上的内存。 但是对于这种存储 结构， 并不能保证 Store和 Load的执行次序， 需要额外的方法来保证 Load指 令在 Store指令后面执行， 才能保证读出来的数据是 3556。 在图 1中己经给出 保证读写次序的一种可行方法。

在本发明中， 所述同步引擎把地址空间的存储结构映射成为 一种新的存储 结构（同步存储结构)， 图 4是本发明中同步存储结构的示意图， 如图 4所示， 使用同步存储结构不仅可以对 Barrier、 Lock/Unlock、 Reduce等基本同步原语 进行支持和加速 还能够支持一种自动维护如图 1所示的读写次序而无需使用 Barrier的新同步原语。 这种能够自动维护读写次序的同步原语称之为 Put/Get 原语。 Put原语代表一种写操作， Get代表一种读操作。 使用本专利所述的同 步引擎能够维护 Put和 Get的执行次序保证 Get操作读取到的内容一定是 Put 操作写入的内容。 所述同步存储结构是在普通的单一存储空间 Value前面附加一个头部，使 之构成 {Count, P，L, Value}这样的同步存储结构。 在同步存储结构中， {Count, P， L，}称之为同步存储的 Tag。同步存储结构里面的 Count和 Value的位宽可以 根据系统需求有不同的设定， 图 4标注的位宽仅仅作为一个例子。 在图 4中， 每 32位的存储空间前面有 1位 L， 1位 P， 8位 Coimt。 同步存储结构里各个 元素的含义如下-

Value: 存储单元， 用于存储数据， 通用处理器可以使用常见的 Store指令 向里面写入内容， 也可以使用常见的 Load指令读取里面存储的内容。

L: Lock标志位， 当 Lock指令成功执行后， 由同步引擎自动把这一标志 位赋值为 1。 L内容为 1表示此存储单元被加锁， 则另外的对这个存储单元的 加锁原语均不能被成功执行。 当 Unlock指令被成功执行后， 由同步引擎自动 把这一标志位赋值为 0。 L内容为 0表示此单元未被加锁， 之后的第一条加锁 原语可以被成功执行。 使用这个标志位可以支持 Lock/Unlock原语。

P: Produce标志位， 当 Put指令成功执行后， 在条件满足时由同步引擎把 这一标志位赋值为 1。 P内容为 1表示此存储单元的数据允许被 Get指令获得， 当 Get指令成功执行后， 在条件满足时， 由同步引擎自动把这一标志位赋值为 0。 使用这个标志位可以实现 Put/Get, 保证读写次序。

Count: 计数器， 可以用于实现 Barriers Reduce, 以及多种模式的 Put/Get 原语。 计数器的位宽和同步引擎支持的最大并行进程 有关， n位 Count可以支 持最大 2"个进程。

所述同步存储结构中的 Value元素是当前计算机的标准存储单元， 占据真 实的存储空间。而同步存储结构中的 Tag是由同步引擎映射而产生的， 仅仅在 同步引擎内部存在， 并不占用处理器的存储空间。 同步存储结构的 Tag不能由 处理器的 Load/Store指令访问，必须通过所述同步引擎支� �的各种同步原语进 行间接的访问。 同步存储结构的地址等于映射 Tag之前的 Value的地址。

图 4是本发明中处理模块与同步存储结构进行通� �的结构示意图， 如图 4 所示， 所述同步引擎使用少量的片内存储虚拟所述同 步存储结构的虚拟方法 是： 使用一块片内存储作为哈希表， 哈希表中每一项的结构如 {关键值， Tag, Value} 当处理模块写入一项同步存储结构时， 比如 Put/Get模块执行 Put指 令， 则把 Put指令的地址作为关键值， 使用哈希算法在哈希表内选择一行作为 存储单元， 把同步结构存储下来。 当处理模块读取一项同步存储结构时， 同样 使用哈希算法找到对应于这个地址的项， 哈希表输出找到的那一行的内容

{ Tag, Value} 如果读取过程中使用哈希算法没有找到对应的 项， 如 Get指令 先于对应的 Put指令被发送到同步引擎， 则说明当前指令应该暂缓执行， 则指 令被重新回归图 2所示的存储队列中， 等候下次调度执行。在同步原语被执行 后， 同步存储结构的 Tag会根据指令的不同有所改变， 如果同步存储结构的 Tag的执行结果等于全 0， 则说明这一项同步存储结构已经被完全执行完 毕， 则在哈希表中释放对应的存储空间。 由此， 能够使用较小的片内存储空间虚拟 出我们所需要的同步存储结构， 而不需要改变各处理器的直属存储结构。

一般说来， 存储在哈希表内的数据在很短暂的时间内就会 被使用， 从而同 步引擎会释放其占用哈希表中的空间， 因此哈希表溢出的概率是比较小的， 构 造哈希表所需要的片内存储空间也不会很大一 个比较相近的例子可以参考处 理器的 Cache, Cache的大小是远远小于内存的大小的。

当哈希表溢出的时候，则使用图 2所示的主存端口向对应的处理器发送中 断， 由软件中断程序模拟同步引擎的过程， 在处理器直属内存中构造哈希表， 来处理这个过程。通过这个构造同步存储的过 程，就可以在不直接占用处理器 直属存储的前提下， 为每个 Value前面增加一个实现同步功能的 Tag。 从而支 持 Barrier、 Lock/Unlock、 Reduce以及 Put/Get原语。

以下详细说明本发明中的同步存储结构对于 Barrier、 Lock/Unlock、 Reduce. Put/Get等基本同步原语进行支持和加速的执行� �骤。

一. 以 m个进程 （m大于等于 1 )执行 Barrier操作为例， 图 5是本发明 的同步引擎中同步存储结构对于 Barrier原语的支持的步骤流程图， 图 6是本 发明中对于 Barrier原语的支持中同步引擎系统初始化的步� �流程图， 如图 5 和图 6所示， 包括下列步骤- 110.同步引擎系统初始化 （这个步骤只需要在系统上电的时候执行一次 ）

111.软件指定多个连续地址的同步存储结构 {Count, P, L, Value}作为多个 Barrier变量， 每个变量占用 4Byte空间， 并把指定信息写入到同步引擎的配置 寄存器中；

112.在同步引擎内部维护一个表示多个 Barrier变量完成状态的寄存器 Barrier— HW_State， 每一位对应一个 Barrier变量的完成状态； 113.每个处理器在其直属的内存中申请一段空� � Barrier— State作为 Barrier 的完成状态表示， Barrier— State 的大小等于 Barrier变量个数除以 8， 单位为 Byte, 每个 Barrier变量的完成状态对应于 Barrier_State的 l bito每个处理器的 Barrier— State都被初始化为全 0。 Barrier— State在对应的处理器内部的各个进程 是共享的， 各个进程都可以读取。

假设有 32个 Barrier变量， 则每个处理器在其直属的内存中申请 4 Byte 的 Barrier— States Barrier变量 B0的完成状态对应于 Barrier— State的 bitQ Barrier 变量 B1的完成状态对应于 Barrier_State的 bitl。

114.每个处理器把申请 Barrier—State的物理地址发送到同步引擎的配置 寄 存器中， 处理器 1 申请到的 Barrier_State地址为 Barrier—Maskl， 处理器 2申 请到的 Barrier— State地址为 Barrier— Mask2 处理器 n申请到的 Barrier_State 地址为 Barrier一 Maskno

120.多个进程调用 Barrier原语，使用某个 Barrier变量 Bn执行一次 Barrier 操作， 每个进程保存本处理器的 Barrier— State的第 n位的状态到这个进程的本 地变量 Local— Barrier— State;

130.每个参与 Barrier的进程使用普通的 Store指令向所述 Barrier变量写 入某个值， 此值的大小等于整个多处理器系统参与 Barrier的进程个数减 1。此 值将被同步引擎用于计算是否所有进程都达到 了同步点。

比如有 m个进程 （m大于等于 1 )使用这个 Barrier变量执行一次 Barrier 操作。 则 Store的地址等于这个 Barrier变量所代表的同步存储结构的地址， 而

Store 的值等于 m-l。 不管多个进程的执行次序如何， Store 的值都固定等于 m-1 , 对于各个进程来说 Store的值都是相同的。

140.同步引擎在接收到对 Barrier变量的 Store指令后， 由于步骤 111中软 件己经把指定信息写入到配置寄存器中， 根据 Store的物理地址， 这些 Store 指令都被同步引擎解释为 Barrier原语。 Barrier处理模块读取对应地址的同步 存储结构， 如果在图 4所示的哈希表中不存在这项同步存储结构， 或者读取到 同步存储结构中的 Count等于 0， 说明这是第一次到达同步引擎的 Barrier原 语， 则在哈希表中建立一项同步存储结构， 其中的 Count等于 Store的值， 也 就是 m-l。 如果读取到同步存储结构 Count不等于 0， 则执行步骤 150;

150.所述 Barrier处理模块读取对应地址的同步存储结构� � 并把读取到的 同步存储结构的 Count减 1 ;

160.如果在执行步骤 140中的 Barrier原语之后， Count值等于 0， 则说明 所有进程都己经到达了同步点， 一次 Barrier已经完成， 则把 Barrier— HW— State 对应的位取反， 然后把 Barrier— HW— State广播到多个处理器的 Barrier— State的 位置， 同步存储结构在哈希表中不释放； 否则， 返回步骤 150;

170.每个进程在发送 Store 指令之后， 定时査询本处理器所属的 Barrier— State 的第 n 位的值， 如果查询到的值等于步骤 120 的 Local— Barrier— Staten, 则表示本进程的 Barrier尚未完成， 则稍后再次查询。 如 果査询到的状态不等于 Local_Barrier_Staten， 则表示 Barrier已经完成， 所述 进程退出査询状态， 同时退出 Barrier原语调用。 比如査询到本处理器所属的 Barrier— State的第 n位的值等于 0， 而本进程保存的 Local— Barrier— Staten等于 0， 则表示 Barrier尚未完成； 而如果查询到 Local— Barrier_Staten等于 1， 则表 示 Barrier己经完成。 由于只使用 lbit来表示完成状态， 因此它们的取值只有 0和 1两种。 上述步骤中， 除了步骤 110只需要系统初始化一次， 其他时候在 各进程调用 Barrier原语的时候， 都是从步骤 120开始执行， 结束于步骤 160。 Barrier的同步原语等效于 Store(Barrier变量地址， m-l)。

二.以 m个进程（m大于等于 1 )执行 Reduce操作为例， 本发明的同步引 擎中同步存储结构对于 Reduce的支持和实现与 Barrier的过程类似。 同步存储 结构支持的 Reduce原语的数据结构为 {Reduce变量地址， 操作符， 数据类型， 进程数目 -1， 源数据 }。 数据结构中各个元素的含义如下： Reduce变量地址表 示选择的被用来做 Reduce运算的物理地址； 操作符表示这次的 Reduce的运算 类型是什么， 比如是"加"、 "减 "等； 数据类型表示参与运算的源数据的类型是 什么， 比如是 "双精度浮点"、 "64位定点 "等； 进程数目表示有多少个进程参与 这次的 Reduce运算； 源数据表示参与 Reduce的数据。 图 7是本发明的同步引 擎中同步存储结构对于 Reduce原语的支持的步骤流程图， 图 8是本发明中对 于 Reduce原语的支持中同步引擎系统初始化的步骤 流程图， 如图 7和图 8所 示， 具体方法， 包括下列步骤：

210.同步引擎系统初始化 （这个步骤只需要在系统上电的时候执行一次 ）

211.软件指定多个连续地址的同步存储结构 {Count, P， L, Value}作为多个 Reduce变量， 每个变量占用 8Byte空间， 并把指定信息写入到同步引擎的配 置寄存器中。

212.在同步引擎内部维护一个表示多个 Reduce变量完成状态的寄存器 Reduce— HW— State, 每一位对应一个 Reduce变量的完成状态；

213.每个处理器在其直属的内存中申请一段空� � Reduce— State作为 Reduce 的完成状态表示， Reduce—State的大小等于 Reduce变量个数除以 8， 单位为

Byte, 每个 Reduce变量的完成状态对应于 Reduce— State的 1 bit。 每个处理器 的 Reduce_State都被初始化为全 0。

假设有 32个 Reduce变量， 则每个处理器在其直属的内存中申请 4 Byte 的 Reduce— Stata Reduce变量 R0的完成状态对应于 Reduce— State的 bitQ Reduce 变量 R1的完成状态对应于 Reduce_State的 bitl。

214.每个处理器把申请 Reduce_State的物理地址发送到同步引擎的配置寄 存器中， 处理器 1申请到的 Reduce— State地址为 Reduce_Maskl， 处理器 2申 请到的 Reduce— State地址为 Reduce— Mask2 处理器 n申请到的 Reduce— State 地址为 Reduce— Maskn ₀

220.某个进程调用 Reduce原语，使用某个 Reduce变量 Rn执行一次 Reduce 操作， 每个进程保存本处理器的 Reduce—State 的第 n位的状态到本地变量 Local— Reduce—State；

230.每个参与 Reduce的进程把上述 Reduce原语的数据结构发送到同步引 擎， 所述同步引擎在接收到 Reduce数据结构之后， 根据 Reduce的物理地址向 所述 Reduce变量 Rn量写入值， 值的大小等于 N-1 ;

240.同步引擎在接收到 Reduce数据结构之后， Reduce处理模块读取对应 地址的同步存储结构， 如果在图 4所示的哈希表中不存在这项同步存储结构， 或者读取到同步存储结构中的 Count等于 0， 说明这是第一次到达同步引擎的 Reduce原语， 则在哈希表中建立一项同步存储结构， 其中的 Count等于 m-1， 并把 Reduce数据结构中的源数据存储在同步存储结构 中的 Value中。 如果读 取到同步存储结构 Count不等于 0， 执行下一步骤 250;

250.把对应的 Count减 L并把读取到的同步存储结构中的 Value和 Reduce 数据结构中的源数据进行运算， 把结果存放到同步存储结构中的 Value中； 260.如果在执行 Reduce原语之后， Count值等于 0。 则说明一次 Reduce 完成， 则把 Reduce— HW_State对应的位取反， 然后把 Reduce— HW— State广播 到 n个处理器的 Red _UCe _Stat _e 的位 ¾同步存储结构在哈希表中不释方夂否拠 返回上一步骤 250

270.每个进程在发送 Reduce数据结构之后， 定时查询本处理器所属的 Reduce— State 的第 n 位的值， 如果査询到的状态等于步骤 220 的 Local—Reduce— Staten， 则表示本次进程的 Reduce尚未完成， 则稍后再次查询； 如果査询到的状态不等于 Local— Reduce— Staten, 则表示 Reduce已经完成， 软 件退出査询状态， 比如査询到本处理器所属的 Reduce— Staten的第 n位的值等 于 0， 而本进程保存的 Local_Reduce— Staten等于 0， 则表示 Reduce尚未完成； 而如果査询到 Local— Reduce— Staten等于 1 , 则表示 Reduce已经完成。 由于只 使用 lbit来表示完成状态， 因此它们的取值只有 0和 1两种。当査询到 Reduce 己经完成后， 使用普通 Load指令来读取相应的 Reduce变量的值。

上述步骤中， 除了步骤 210只需要系统初始化一次， 其他时候在软件调用 Reduce原语的时候， 都是从步骤 220开始执行， 结束于步骤 260。

三.以 m个进程（m大于等于 1 )执行 Lock操作为例， 本发明的同步引擎 中同步存储结构支持的 Lock原语数据结构为{返回物理地址， 目标物理地 址}， 其中各个元素的含义如下： 返回物理地址表示当加锁成功的时候， 同步 引擎会把成功消息存放在主存中的返回物理地 址中； 目标物理地址表示软件希 望对哪个物理地址进行加锁。 图 9是本发明的同步引擎中同步存储结构对于 Lock原语的支持的步骤流程图， 如图 9所示， 具体方法， 包括下列步骤：

310.每个处理器在其直属的内存中申请变量 Lock_Result把这个变量的内 容清零， 并把这个变量的物理地址作为 Lock原语数据结构的返回物理地址； 进程把 Lock原语的数据结构发送到同步引擎；

320. 同步引擎在接收到 Lock原语的数据结构后， 根据其中的目标物理地 址读取同步存储结构， 如果从图 5所示的哈希表中读取不到同步存储结构， 或 者读取到的同步存储结构中的 L位等于 0， 则说明此物理地址尚未被加锁， 则 Lock原语执行成功转至步骤 33Q如果读取到的同步存储结构的 L位等于 1， 则说明此物理地址已经被加锁， 则放弃本次 Lock的执行， 把 Lock原语放入相 应的存储队列中， 等候在此调度执行；

330.把同步存储结构中的 L位置 1， 并且保存至哈希表中。 根据 Lock数 据结构中的返回物理地址， 向直属的内存的 Lock—Result写入 1 ; 340.所述进程定时查询 Lock— Result, 如果读取到的 Lock— Result等于 0， 则表示尚未加锁成功， 则延时后再查询； 如果读取到的 Lock— Result等于 1， 则表示加锁成功， 退出 Lock调用。

进程每次调用 Lock时， 都会执行上面 4个步骤。

本发明的同步引擎中同步存储结构支持的 Unlock原语的数据结构为 {目 标地址 }, 数据结构中仅有的一个元素表示需要解锁的变 量地址。 进程只需要 把所述数据结构发送到同步引擎即可退出 Unlock调用。 而同步引擎硬件在接 收到 Unlock数据结构后， 根据目标地址从哈希表中读取同步数据结构， 把其 中的 L位清零， 如果同步数据结构在 L位清零后等于全 0， 则在哈希表中释放 这一项同步数据结构， 否则仅仅把 L位清零后的数据结构写回即可。

四. 本发明的同步引擎中同步存储结构支持的 Put原语数据结构为{目标 地址， 源数据 }， 其中数据结构中的各个元素的含义如下： 目标地址表示 Put 原语中源数据被存放的物理地址； 源数据表示 Put原语中移动的数据内容。 图 10是本发明的同步引擎中同步存储结构对于 Put原语的支持的步骤流程¾如 图 10所示， 具体方法， 包括下列步骤：

410.进程将 Put原语的数据结构发送到同步引擎即可退出 Put调用； 420.同步引擎的 Put处理模块根据 Put原语的数据结构中的目标地址在图 4所示的哈希表中读取相应的同步存储结构， 如果不存在， 则新建一项同步存 储结构， 如果存在则读取已存在的同步存储结构。

430.把步骤 420所得的同步存储结构的 P位置 1， 以及把接收到的 Put原 语中的源数据存储到同步存储结构的 Value位置。

五.本发明的同步引擎中同步存储结构支持的 Get原语数据结构为{返回 物理地址， 目标物理地址 }。 数据结构中各个元素的含义如下： 返回物理地址 是当 Get成功执行后， 返回 Get的数据以及完成标识的存放地址， Get返回值 的数据结构如 {返回数据， 完成标识}， 此返回值被连续存放在返回物理地址 中； 目标物理地址表示 Get试图去获得的数据的物理地址。 图 11是本发明的 同步引擎中同步存储结构对于 Get原语的支持的步骤流程图， 如图 11所示， 具体方法， 包括下列步骤：

510.处理器在其直属的内存空间中申请一段空� � Get— Result用于存储 Get 返回值的数据结构， 并把申请到的空间清零； 进程发送 Get原语数据结构到同步引擎；

520.Get处理模块根据接收到的 Get原语数据结构中的目标地址， 读取图 6所示的哈希表中对应的同步存储结构。 如果哈希表中不存在对应的同步存储 结构， 则放弃 Get的执行， 把 Get原语放回存储队列中， 等待再次被调度执行。 如果哈希表中存在对应的同步存储结构， 但是其中的 P位为 0， 则放弃 Get的 执行， 把 Get原语放回到存储队列中， 等待再次被调度执行； 如果哈希表中存 在对应的同步存储结构， 而且其中的 P位为 1， 转步骤 540;

530.把读取到的同步存储结构中的 P清零， 把读取到的同步存储结构中的 Value内容， 根据 Get原语数据结构中的返回物理地址， 把返回值 { 1， Value}写 入处理器的直属存储中；

540.如果清零后同步存储结构的 Tag等于全零， 则释放哈希表中对应的同 步存储结构项， 否则把 P位清零的同步存储结构写回。

虽然 Get把 P位清零了。但是对应的这一行同步存储结构� �可能被用来做 其他用途， 比如其中的 L位是置 1的， 表示这一行同步存储结构还被加锁了。 那么就不能释放这行同步存储。只有 Tag等于全零了，才表示这行数据无用了。

550.定时査询 Get— Result中数据结构的完成标识， 如果査询结果为 0， 表 示 Get原语尚未执行完毕， 则延时一段时间后继续査询； 如果査询结果为 1， 则表示 Get原语执行完毕， 执行步骤 560。

560.读取 Get_Result中数据结构的返回数据， 退出 Get调用。

相应于本发明的一种多处理器的同步引擎， 还提供一种多处理器系统， 图

12是本发明的多处理器系统的结构示意图， 如图 12所示， 所述系统 7， 包括： 多个处理器 71和一个处理芯片 72， 其中：

所述处理芯片 72， 包括：

多个设备端口 721， 用于和所述多个处理器的高速互联， 每个处理器和一 个设备端口连接；

所述同步引擎， 用于与芯片内部的多个设备端口互联。

图 12显示了同步引擎在 n个处理器环境下的拓扑结构。 在一个芯片内实 现 n个设备端口用于和处理器的高速互联， 每个处理器和一个设备端口连接。 在设备发现过程中，每个处理器通过标准设备 搜索流程都可以搜索到与之互联 的设备端口， 并分配设备端口申请的各种资源， 主要是地址空间资源。 芯片内 部的多个设备端口都和同步引擎互 同步引擎所需要的资源都由设备端口代 为向处理器之上的操作系统申请。 操作系统分配资源给对应的设备端口， 实际 上是把资源分配给同步引擎。 同时， 同步引擎也把自身的资源通过设备端口映 射到对应的操作系统上面。 由于同步引擎通过 n个设备 端口把自身映射到 n 个处理器之上的操作系统中， 因此在 n个处理器上的软件都可以通过映射关 系， 像操作独占资源那样去操作同步引擎， 因此同步引擎实际上被 n个处理器 共享。

本发明的有益效果是： 本发明的同步引擎使用统一的共享存储结构， 对 Barrier> Lock/Unlock、 Reduce Put/Get等基本同步原语进行支持和加速， 大 幅度提高同步原语的执行速度，减少进程间的 通信量，并简化同步原语的接口， 不依赖于多处理器的 Cache—致性， 不依赖于处理器的特殊指令集，使得并行 程序在使用同步原语时更加方便， 具有使用简单， 应用范围广， 执行速度快的 特点。

通过结合附图对本发明具体实施例的描述，本 发明的其它方面及特征对本 领域的技术人员而言是显而易见的。

以上对本发明的具体实施例进行了描述和说明 ， 这些实施例应被认为其只 是示例性的， 并不用于对本发明进行限制， 本发明应根据所附的权利要求进行 解释。