一种多处理器系统及其同步引擎

本发明公开了一种多处理器系统及其同步引擎。所述同步引擎包括：多个存储队列，一个队列存储来自一个处理器的所有同步原语；多个调度模块，在多个存储队列中选定用于执行的同步原语之后，根据同步原语的类型，发送到相对应的处理模块进行处理，调度模块与存储队列一一对应；多个处理模块，接收调度模块发来的同步原语，执行不同功能；虚拟同步存储结构模块，使用少量的存储空间，通过控制逻辑把所有处理器的直属存储空间都映射为同步存储结构来实现各种同步原语的功能；主存端口，与虚拟同步存储结构模块进行通讯，对各处理器的直属存储进行读和写，以及向处理器发起中断；配置寄存器，存储处理模块需要用到的各种配置信息。

1.一种多处理器的同步引擎，其特征在于，所述同步引擎，包括：多个存储队列，用于接收多个处理器发送的同步原语，一个队列存储来自一个处理器的所有同步原语；多个调度模块，用于在所述多个存储队列中选定用于执行的同步原语之后，根据同步原语的类型，发送到相对应的处理模块进行处理，所述调度模块与所述存储队列一一对应；多个处理模块，用于接收所述调度模块发来的同步原语，执行不同功能；虚拟同步存储结构模块，使用少量的存储空间，通过控制逻辑把所有处理器的直属存储空间都映射为同步存储结构来实现各种同步原语的功能；主存端口，用于与所述虚拟同步存储结构模块进行通讯，对各处理器的直属存储进行读和写，以及向所述处理器发起中断；配置寄存器，用于存储所述处理模块需要用到的各种配置信息。
2.根据权利要求1所述的多处理器的同步引擎，其特征在于，在同步原语存储到对应的存储队列里时，将同时保存进程号信息，以区别同一处理器上不同进程发送过来的同步原语。
3.根据权利要求1所述的多处理器的同步引擎，其特征在于，所述处理模块，包括：Reduce处理模块、Barrier处理模块、Load/Store处理模块，以及Put/Get处理模块。
4.根据权利要求1所述的多处理器的同步引擎，其特征在于，所述同步引擎中的处理模块，能够根据同步引擎支持的同步原语的类型进行扩展。
5.根据权利要求1所述的多处理器的同步引擎，其特征在于，所述同步存储结构是使用少量的片内存储虚拟出来的，并不直接占用处理器直属存储的空间。
6.根据权利要求1所述的多处理器的同步引擎，其特征在于，所述同步存储结构是{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ⁿ个进程。
7.根据权利要求1所述的多处理器的同步引擎，其特征在于，所述同步存储结构的虚拟方法是：使用一块片内存储作为哈希表，哈希表中每一项的结构为{关键值，Tag，Value}，当处理模块写入一项同步存储结构时，所述处理模块执行指令，把指令的地址作为关键值，使用哈希算法在哈希表内选择一行作为存储单元，把同步结构存储下来；当处理模块读取一项同步存储结构时，同样使用哈希算法找到对应于这个地址的项，哈希表输出找到的那一行的内容{Tag，Value}；如果读取过程中使用哈希算法没有找到对应的项，则说明当前指令应该暂缓执行，则指令被重新回归相应的存储队列中，等候下次调度执行；在同步原语被执行后，如果同步存储结构的Tag的执行结果等于全0，则说明这一项同步存储结构已经被完全执行完毕，则在哈希表中释放对应的存储空间；当所述哈希表溢出的时候，则使用所述主存端口向对应的处理器发送中断，在所述处理器直属内存中构造哈希表，来存储所述同步存储结构。
8.一种采用权利要求1-7中的一项所述的多处理器的同步引擎的多处理器系统，其特征在于，所述系统，包括：多个处理器和一个处理芯片，其中：所述处理芯片，包括：多个设备端口，用于和所述多个处理器高速互联，每个处理器和一个设备端口连接；所述同步引擎，其中，所述存储队列与所述多个设备端口互联。在设备发现过程中，每个处理器通过标准设备搜索流程搜索到与之互联的设备端口，并分配设备端口申请的各种资源；所述同步引擎把自身的资源通过设备端口映射到对应的处理器的操作系统中，在多个处理器上的软件通过映射关系操作所述同步引擎，所述同步引擎被多个处理器共享。
9.根据权利要求1所述的多处理器的同步引擎对于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原语调用。
10.根据权利要求9所述的多处理器的同步引擎对于Barrier原语的处理方法，其特征在于，同步引擎系统初始化的步骤110，包括下列步骤：
111.指定多个连续地址的同步存储结构作为多个Barrier变量，并把指定信息写入到所述配置寄存器中；
112.在所述同步引擎内部维护一个表示多个Barrier变量完成状态的寄存器Barrier_HW_State，每一位对应一个Barrier变量的完成状态；
113.每个处理器在其直属的内存中申请一段空间Barrier_State作为Barrier的完成状态表示，每个处理器的Barrier_State都被初始化为全0，Barrier_State在对应的处理器内部的各个进程是共享的，各个进程都可以读取；
114.每个处理器把申请Barrier_State的物理地址发送到所述配置寄存器中。
11.根据权利要求1所述的多处理器的同步引擎对于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-1，并把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已经完成，退出查询状态。
12.根据权利要求11所述的多处理器的同步引擎对于Reduce原语的处理方法，其特征在于，同步引擎系统初始化的步骤，包括下列步骤：
211.指定多个连续地址的同步存储结构{Count，P，L，Value}作为多个Reduce变量，并把指定信息写入到同步引擎的配置寄存器中；
212.在同步引擎内部维护一个表示多个Reduce变量完成状态的寄存器Reduce_HW_State，每一位对应一个Reduce变量的完成状态；
213.每个处理器在其直属的内存中申请一段空间Reduce_State作为Reduce的完成状态表示，每个处理器的Reduce_State都被初始化为全0；
214.每个处理器把申请Reduce_State的物理地址发送到同步引擎的配置寄存器中。
13.根据权利要求11所述的多处理器的同步引擎对于Reduce原语的处理方法，其特征在于，所述Reduce原语的数据结构为{Reduce变量地址，操作符，数据类型，进程数目-1，源数据}。
14.根据权利要求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调用。
15.根据权利要求14所述的多处理器的同步引擎对于Lock原语的处理方法，其特征在于，所述Lock原语数据结构为{返回物理地址，目标物理地址}，返回物理地址表示当加锁成功的时候，同步引擎会把成功消息存放在主存中的返回物理地址中；目标物理地址表示软件希望对哪个物理地址进行加锁。
16.根据权利要求1所述的多处理器的同步引擎对于Unlock原语的处理方法，其特征在于，所述方法，包括下列步骤：进程把所述数据结构发送到所述同步引擎，并退出Unlock调用；所述同步引擎在接收到Unlock数据结构后，根据目标地址从哈希表中读取同步数据结构，把其中的L位清零，如果同步数据结构在L位清零后等于全0，则释放这一项同步数据结构，否则仅仅把L位清零后的数据结构写回。
17.根据权利要求16所述的多处理器的同步引擎对于Unlock原语的处理方法，其特征在于，所述Unlock原语的数据结构为{目标地址}，数据结构中仅有的一个元素表示需要解锁的变量地址。
18.根据权利要求1所述的多处理器的同步引擎对于Put原语的处理方法，其特征在于，所述方法，包括下列步骤：
410.进程将Put原语的数据结构发送到所述同步引擎，并退出Put调用；
420.所述同步引擎的Put处理模块根据Put原语的数据结构中的目标地址读取相应的同步存储结构，如果不存在，则新建一项同步存储结构，如果存在则读取已存在的同步存储结构；
430.把根据Put原语的数据结构中的目标地址读取的相应的同步存储结构的P位置1，并把接收到的Put原语中的源数据存储到所述同步存储结构的Value位。
19.根据权利要求18所述的多处理器的同步引擎对于Put原语的处理方法，其特征在于，所述Put原语数据结构为{目标地址，源数据}，其中，目标地址表示Put原语中源数据被存放的物理地址；源数据表示Put原语中移动的数据内容。
20.根据权利要求18所述的多处理器的同步引擎对于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调用。
21.根据权利要求20所述的多处理器的同步引擎对于Get原语的处理方法，其特征在于，所述Get原语数据结构为{返回物理地址，目标物理地址}。数据结构中各个元素的含义如下：返回物理地址是当Get成功执行后，返回Get的数据以及完成标识的存放地址，Get返回值的数据结构如{返回数据，完成标识}，此返回值被连续存放在返回物理地址中；目标物理地址表示Get试图去获得的数据的物理地址。