公开/公告号CN104142977A
专利类型发明专利
公开/公告日2014-11-12
原文格式PDF
申请/专利权人 上海航天电子通讯设备研究所;
申请/专利号CN201410324012.X
发明设计人 陈晓强;
申请日2014-07-09
分类号G06F17/30;
代理机构上海汉声知识产权代理有限公司;
代理人胡晶
地址 200082 上海市杨浦区齐齐哈尔路76号
入库时间 2023-12-17 01:54:18
法律状态公告日
法律状态信息
法律状态
2018-03-06
授权
授权
2015-08-05
实质审查的生效 IPC(主分类):G06F17/30 申请日:20140709
实质审查的生效
2014-11-12
公开
公开
技术领域
本发明涉及数据处理技术,具体地,涉及一种从多数据源获取数据并按 优先级存储的方法。
背景技术
在业务应用系统的数据采集设备和数据存储设备中,常常需要对多个数 据源的信息进行缓存或存储。例如多通道的数据采集设备,多业务的信息处 理机。对数据处理业务中存在对关键数据识别和优先处理要求的数据源,需 按优先级进行数据的存储。对于一些单处理模型多通讯接口的控制设备,由 于对通讯接口的复节和实时处理的要求,也需建立一定的操作顺序。
为达到数据通讯和存储的优先级排序,在工程实现上,常以多条件分支 判断的方法或以不同的存储介质区分。采用多条件分支判断的方法,在数据 源数量较多时存在标识复杂,逻辑深度较深的问题,造成运算性能不高,资 源消耗较大的问题。采用独立存储控制,在数据源数量较多时无法实现。
发明内容
针对现有技术中的缺陷,本发明的目的是提供一种采用检索表确定数据源 优先级的存储方法,包括如下步骤:
步骤1:将数据源通道分组形成多个数据源通道序列,每个数据源通道序列 包含相同数量的数据源通道;
步骤2:采用数据位标识数据源通道形成数据源标识序列,其中,采用“1” 标识数据源通道有数据存储请求,采用“0”标识数据源通道没有数据存储请求;
步骤3:将每个数据源标识序列中的数据位进行按位或运算得到集合数据位, 从而采用一个集合数据位表示一个数据源标识序列,多个集合数据位形成数据源 组标识序列;
步骤4:设定数据源组标识序列的集合数据位和数据源标识序列中的数据位 的优先级按从左到右的位次依次降低,根据数据源组标识序列的数值穷举以独热 的方式建立第一优先级查询检索表;根据数据源标识序列中的数值穷举以独热的 方式建立第二优先级查询检索表;
步骤5:当数据通道存在数据存储请求时,首先根据数据源组标识序列中的 数值查询第一优先级查询检索表获取优先级最高的数据源组;再次以该数据源组 相对应的数据源标识序列中的数值查询第二优先级查询检索表获取最高优先级 的数据源通道。
进一步地,所述步骤4还包括如下步骤:
根据数据源组标识序列的数值穷举以存储地址的方式建立与第一优先级查 询检索表相对应的第一存储位置查询检索表;
根据数据源标识序列中的数值穷举以存储地址的方式建立与第二优先级查 询检索表相对应的第二存储位置查询检索表。
进一步地,所述步骤5还包括如下步骤:
根据数据源组标识序列中的数值查询第一存储位置查询检索表获取基地址; 再次以该数据源组相对应的数据源标识序列中的数值查询第二存储位置查询检 索表获取偏移存储地址,进而根据基地址和偏移存储地址确定存储地址。
进一步地,数据源通道序列中数据源通道的数量小于等于存储器的字长;数 据源通道序列的数量小于等于存储器的位宽。
进一步地,将第一优先级查询检索表中以数据源组标识序列中集合数据位第 一位为1穷举的数值映射到同一地址,从而生成新的第一优先级查询检索表;
将第二优先级查询检索表中以数据源通道标识序列中数据位第一位为1穷 举的数值映射到同一地址,从而生成新的第二优先级查询检索表;
将第一存储位置查询检索表中以数据源组标识序列中集合数据位第一位为 1穷举的数值映射到同一地址,从而生成新的第一存储位置查询检索表;
将第二存储位置查询检索表中以数据源通道标识序列中的数据位第一位为 1穷举的数值映射到同一地址,从而生成新的第二存储位置查询检索表。
进一步地,当数据源通道序列的数量与数据源通道序列包含的数据源通道的 数量相同时,则第一优先级查询检索表和第二优先级查询检索表相同,第一存储 位置查询检索表和第二存储位置查询检索表相同。
与现有技术相比,本发明具有如下的有益效果:
1、本发明以空间换时间的思想简化运算逻辑,以时间换空间的思想优 化了硬件逻辑的时序特性;
2、本发明利用外部扩展的存储器存储资源构建优先级表,以查表检索 方式替代传统的多条件分支判断的方法,以多级分组检索方式简化原查找方 式的逻辑深度;
3、本发明通过表格化的优先级查询方式,可以通过表索引值的改变实 现动态优先级的管理,给多数据源通讯的数据采集和通讯设计提供了一种有 效的设计方法。
附图说明
通过阅读参照以下附图对非限制性实施例所作的详细描述,本发明的其 它特征、目的和优点将会变得更明显:
图1为本发明中混合存储优先级表的硬件逻辑原理框图;
图2为本发明中独立优先级表的硬件逻辑原理框图;
图3为本发明的原理框图;
图4为本发明优化后的原理框图;
图5为本发明中二级分组条件下的单字节操作示意图;
图6为本发明中二级分组下的批量数据操作示意图;
图7为本发明中二级分组条件下的单字节流水操作示意图;
图8为本发明中二级分组条件下的双字节流水操作示意图;
图9为本发明中二级分组条件下的批量数据流水操作示意图;
图10为本发明的流程图;
图11为本发明中查询存储地址的流程图。
图中:
1-数据源组标识序列;2-优先级查询检索表;3-数据源通道标识序列; 4-最优数据源通道。
具体实施方式
下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的 技术人员进一步理解本发明,但不以任何形式限制本发明。应当指出的是,对本 领域的普通技术人员来说,在不脱离本发明构思的前提下,还可以做出若干变形 和改进。这些都属于本发明的保护范围。
在本实施例中,本发明提供的采用检索表确定数据源优先级的存储方法,通 过FPGA模块和存储器实现,FPGA模块用于实现整个方法逻辑,存储器作为通讯 数据和检索表的数据宿主。
本发明提供的采用检索表确定数据源优先级的存储方法,包括如下步骤:
步骤1:将数据源通道分组形成多个数据源通道序列,每个数据源通道序列 包含相同的数据源通道;
步骤2:采用数据位标识数据源通道形成数据源标识序列,其中,采用“1” 标识数据源通道有数据存储请求,采用“0”标识数据源通道没有数据存储请求;
数据通道是指设备针对数据源建立通讯的数据缓存队列,从而数据源通道的优先 级与数据源的优先级一一对应。
各数据通道采用数据位Cnm标识,n为行号,m为列号,Cnm的取值为0或1, 形成数据通道标识序列如下:
{C00,C01,C02,C03,C04,C05,C06,C07}
…
{Ci0,Ci1,Ci2,Ci3,Ci4,Ci5,Ci6,Ci7}
…
{Cn0,Cn1,Cn2,Cn3,Cn4,Cn5,Cn6,Cn7}
步骤3:将每个数据源标识序列中的数据位进行按位或运算得到集合数据位, 从而采用一个集合数据位表示一个数据源标识序列,多个集合数据位形成数据源 组标识序列,具体为将数据源通道序列采用Gn标识,形成如下所示的数据源组 标志序列,
{G0,G1,G2,G3,G4,G5,G6,G7}
数据源组标识序列有效时表示该组中存在有效的数据源通道,数据源组标识 序列中集合数据位的公式如下。
Gn=Cn0|Cn1|Cn2|Cn3|Cn4|Cn5|Cn6|Cn7 (1)
步骤4:设定数据源组标识序列的集合数据位和数据源标识序列中的数据位 的优先级按从左到右的位次依次降低,即将数据源通道按优先级分组,采用数据 源组标识各数据源的数据存储请求,数据源组序列中的集合数据位对应每个数据 源通道序列,数据源组序列中高位表示高优先级组,低位表示低优先级组;对于 每个数据源组中的数据源通道,采用数据位标识相应的数据源通道,序列中高位 标识高优先级数据源通道,低位标识低优先级数据源通道;
从而分别根据数据源组标识序列和数据源标识序列中的数值穷举以独热的 方式建立第一优先级查询检索表和第二优先级查询检索表;根据数据源组标识序 列和据数据源标识序列中的数值穷举以存储地址的方式建立与第一优先级查询 检索表和第二优先级查询检索表相对应的第一存储位置查询检索表和第二存储 位置查询检索表,具体为:
设定数据源通道标识Cn0表示分组后数据源通道序列{Cn0,Cn1,Cn2,Cn3, Cn4,Cn5,Cn6,Cn7}中的最高优先级数据源通道,数据源组标识G0表示最高 优先级数据源组。通过按优先级排序完成整个数据通道的组织。
建立优先级查询检索表,优先级查询检索表以穷举方式列出各数值条件的对 应最高优先级,对应了8位数值的256种情况。优先级查询检索表标识了各种数 据源请求条件下序列中的最高优先级索引。所建优先级查询检索表如表1和表2 所示。由于数据源通道序列的数量与数据源通道序列包含的数据源通道的数量相 同时,则第一优先级查询检索表和第二优先级查询检索表相同,即表1;第一存 储位置查询检索表和第二存储位置查询检索表相同,即表2。在表1中采用16 进制表示独热方式穷举的数值。
表1
表2
表1和表2分别列出了数据源组序列和数据源序列为8位时的256个数值条 件下对应的优先级。表1中以独热方式标识对应数据源通道标识或数据源组标识, 表2以存储地址方式标识对应数据源通道中数据的存储位置。其中独热方式为只 有一个比特为1,其他全为0的一种码制。
当数据源无序存储时,可采用表1的方式检索优先级;当数据源有固定存储 位置可独立采用表2或表1、表2结合的方法检索优先级。
步骤5:当数据通道存在数据存储请求时,首先根据数据源组标识序列中的 数值查询第一优先级查询检索表获取优先级最高的数据源组;再次以该数据源组 相对应的数据源标识序列中的数值查询第二优先级查询检索表获取最高优先级 的数据源通道;采用数据源组标识序列的数值作为表地址进行优先级查询检索表 的检索,优先级查询检索表中的数值标识数据源的优先级。具体为:
将数据源组序列作为存储器地址访问存储于外部存储器的优先级表,获取表 中对应信息,所得信息标识了最高优先级组,即如图3中的组序列00010101, 按表1查询后,得到00010000,表示自高至低第四组为有效的最高优先级数据 源组,通过译码器,选择第四组数据源通道序列01001101。
通过译码器选择对应数据源组中的数据源通道序列,并将该数据源通道序列 作为存储器地址二次查表,并按上述方法找到目标数据源通道,即最高优先级数 据源通道。根据所得的第四组数据源通道序列01001101经二次查表,得到数据 01000000,即第四组中第2个数据源通道为当前最高优先级数据源通道。按256 满序列条件下,可得3*8+2=26,即第二十六通道为最高优先级数据源。
根据数据源组标识序列中的数值查询第一存储位置查询检索表获取基地址; 再次以该数据源组相对应的数据源标识序列中的数值查询第二存储位置查询检 索获取偏移存储地址,进而根据基地址和偏移存储地址确定存储地址,具体为:
将表2进行一级扩展,形成2个表项,第一个表项用于数据源组序列的检索, 确定数据源组序列的基地址,第二个表项用于组内的数据源通道序列检索,确定 对应的最高优先级数据源通道和偏移存储地址,通过基地址和偏移地址计算最终 的存储地址。将数据源组序列(00010101)作为地址访问表2,得到结果addr4, 通过译码选则第四组数据源通道序列(01001101),并将addr4作为存储的基地址。 采用数据源通道序列(01001101)为存储器地址进行二次查表,得到结果addr6, 即偏移地址,通过译码选择最终的数据源通道,并通过addr4和addr6计算最终 的存储地址。具体地,如在64K的存储器中,可由addr4作为存储器的高8位地 址,由addr6作为存储器的低8位地址,从而得到目标数据源的存储地址为 {addr4,addr6}。在更大的数据存储器中,可采用分段式的存储地址计算方法或 线性地址计算方法求得存储地址,在分段式中目标地址为((addr4<<4)+ addr6),在线性地址计算方法下有((addr4<<8)+addr6),此外,实际使用中 还可以使用addr4和add6共计16bit的数据任意拆分进行如上述形式的地址计 算。完成最高优先级数据源的选择和存储地址的计算后,取出缓存中的数据并按 计算所得的存储地址写入数据源数据。
对数据源存储有地址要求的采用如表2或表4方式,否则可采用表1或表3 方式。表3和表4方式的优先级查询检索表是表1和表2的变形,需消耗较多的 运算逻辑资源,可获得优先级表占用空间小的特点。实际应用中可根据具体应用 情况选择最适合的方式建立检索表。
将第一优先级查询检索表中以数据源组标识序列中集合数据位第一位为1 穷举的数值映射到同一地址,从而生成新的第一优先级查询检索表;
将第二优先级查询检索表中以数据源通道标识序列中数据位第一位为1穷 举的数值映射到同一地址,从而生成与第二优先级查询检索表相对应的第四优先 级查询检索表;
将第一存储位置查询检索表中以数据源组标识序列中集合数据位第一位为 1穷举的数值映射到同一地址,从而生成新的第一存储位置查询检索表;
将第二存储位置查询检索表中以数据源通道标识序列中的数据位第一位为 1穷举的数值映射到同一地址,从而生成与第二存储位置查询检索表相对应的第 四存储位置查询检索表,具体为:
数据源通道的优先级检索是在数据源组标识不为0时,即序列中存在有效标 识的条件下进行对应数据源通道的优先级检索,因此表1和表2中的0x0地址均 为无效数据,在表中采用FF标识。如表1和表2中在序列数值大于0x7F时所填 数据均指向同一数据源通道,使表1和表2的一半以上数据冗余,其中0x7F为 16十六进制的数值
当序列数值小于等于0x7F时,表示第1位数据源通道没有有效数据,0x8X 为第0位数据源通道存在有效数据,上述描述表示当第1位数据源通道存在有效 数据时,按照本发明中设定的优先级关系,此时可以忽略2至8位的状态。由于 不存在所有通道均无效的查找过程,因此序列值0没有任何意义,为此,在条件 大于等于0x80时,将0x80~0xFF中的所有值映射到0x0地址中。简化了查找表 1板的空间开销。
为优化空间资源利用率,将优先级查找表进行了如表3和表4的优化。表3 和表4中采用地址0x0标识了序列值为0x8X条件下所有优先级。并所生成序列 进行如下公式的计算
^{Ci1|Ci0,Ci2|Ci0,Ci3|Ci0,Ci4|Ci0,Ci5|Ci0,Ci6|Ci0,Ci7|Ci0} (2)
^{G1|G0,G2|G0,G3|G0,G4|G0,G5|G0,G6|G0,G7|G0} (3)
上述公式(2)和公式(3)采用序列的最高位进行位扩展,位扩展后与低位 序列进行按位或反运算,仅当序列最高位为1时,序列值为0,充分利用了优先 级查询检索表表,并减小了原查找表一半的空间开销,即用第1位与序列中的每 一位先进行按位或运算,并将计算结果取位反,即当Ci0为0时,序列仍为原序 列,当Ci0为1时,序列为0。
表3
表4
完成数据源通道序列的分组,并形成优先级查询检索表。当检测到数据源通 道中存在有效数据时即数据源标识为“1”时进行优先级的查表检索。按分组的 级数逐级查找优先级查询检索表,先后确定最高优先级数据源组和最高优先级数 据源通道。
如图1所示,本发明采用数据存储器共享方式完成优先级查询检索表和有效 数据的存储。使用该方式要求存储接口带宽满足检索和数据通讯带宽之和。如图 2所示,本发明也可以采用了独立形式的数据存储器进行优先级查询检索表的存 储。其中,共享存储方式可获得最优的资源配置,独立的优先级查询检索表和数 据存储器可通过并行处理方式提高数据存储器带宽的利用率。
以数据源组序列的数据源序列作为地址进行二次扩展存储访问,获取最高优 先级数据源;图10和图11给出了流程图。
如图10所示,数据源通道在分组后分别形成数据源组序列和组内的数据源 通道序列,以数据源组序列作为存储器地址进行扩展存储访问,检索并获取对应 的最高优先级数据源组。通过译码逻辑和多路选择器选择对应最高优先级组的数 据源通道序列,并以数据通道序列为地址进行扩展存储访问,检索并获取最高优 先级数据源。完成优先级检索后,对译码选择最高优先级数据源的数据源通道, 并进行数据扩展存储操作。
本发明通过优先级表标识数据源组序列和数据源序列的优先级。为减小算法 逻辑的逻辑深度,简化逻辑资源的消耗,本发明采用了两种形式的优先级表,方 法一中的“独热”编码用于简化译码器或多路选择器的逻辑深度,方法二种采用 地址编码方式可免除算法逻辑对通道地址的计算。图11是针对图10从实现角度 的进行优化。图11中的一级查表和二级查表均采用“独热”方式选中数据源通 道,并以扩展查表方式获取目标数据源通道的存储地址,采用查表方式实现了优 先级的判断、选中,并完成了目标存储地址的计算。
图5和图6给出了单字节存储和批量数据存储操作的示意图,如图所示,在 实施数据存储操作过程中需要进行二次优先级表检索,单字节操作条件下的存储 带宽利用率为33%。猝发批量数据存储其带宽利用率为n÷(n+r)×100%,其中 n为批量操作的数据量,r为分组级数。
上述实施例利用了数据存储空间作为优先级查找表,并以最小资源开销完成 数据源优先级的识别。由于整个操作过程中增加了存储器的访问开销,因此本方 案适用于大数据量的猝发存储或速率不高的单字存储。
为提高数据存储带宽的利用率,本发明另一实施例中采用了如图2所示的硬 件原理框图,采用了独立的优先级表存储器。优先级表和数据存储器在操作上具 有独立的端口,在实施过程中可采用独立的小容量存储器芯片、FPGA的片内存 储资源也可采用双端口SRAM实现算法和数据的独立访问端口。图7给出了二级 分组条件下的单字节流水操作示意图,图8给出了二级分组条件下的双字节流水 操作示意图,图9给出了二级分组条件下的批量数据流水操作示意图。图7中采 用流水方式后,由于算法逻辑实施周期大于数据存储操作周期,因此数据存储过 程仍需等待算法逻辑完成最高优先级的选择。仅当此数据操作数大于算法逻辑的 工作周期时,可实现100%的存储带宽利用率。
以上对本发明的具体实施例进行了描述。需要理解的是,本发明并不局 限于上述特定实施方式,本领域技术人员可以在权利要求的范围内做出各种 变形或修改,这并不影响本发明的实质内容。
机译: 确定集装箱装载和卸载优先级的方法以及采用该方法的集装箱起重机
机译: 如何确定IIC总线采用系统的优先级
机译: 如何确定IIC总线采用系统的优先级