一种基于离散状态合并的不确定性传播方法及装置与流程
本发明涉及计算机数据处理与形式化验证,具体涉及一种基于离散状态合并的不确定性传播方法及装置。
背景技术:
1、在四状态三进制计算机系统中,数值计算和逻辑运算常常伴随着各种不确定性。典型的不确定性包括:因算术运算产生进位或借位而引发的算术不确定性,以及因访问未初始化内存、读取无效数据或执行未定义操作而产生的语义不确定性。这些不确定性如果不能在运算过程中得到有效管理和传播,将导致计算结果依赖于计算顺序或数据到达的时序,从而破坏计算的确定性,给并行处理、乱序执行及形式化验证带来严峻挑战。
2、现有技术中,处理不确定性的主要方式包括基于概率论的贝叶斯网络传播、模糊逻辑的隶属度传播、区间算术的区间扩张以及传统三值逻辑的真值表方法。其中,概率传播和区间算术通常涉及连续的数值计算,计算复杂度高,难以直接映射到硬件电路;模糊逻辑传播规则多基于经验或启发式方法,缺乏严格的数学结构,往往不满足结合律,即多个不确定性状态合并时,不同的合并顺序可能得到不同的最终状态,导致计算结果依赖于计算路径。传统三值逻辑虽然提供了“真”、“假”、“未知”三种状态,但其无法区分不确定性的来源和类型,例如无法区分进位带来的不确定性和数据未定义带来的不确定性,限制了其在精细化系统管理中的应用。
3、更重要的是,在硬件电路设计、编译器优化及分布式协议等工程实践中,不确定性状态必须在极短的时钟周期内被确定性地传播和处理,而现有的软件化或基于复杂数值模型的方案难以满足低延迟、低硬件开销的要求。
技术实现思路
1、为了解决现有技术中不确定性传播过程延迟高、无法高效映射到硬件以及难以形式化验证的技术问题,提供一种基于离散状态合并的不确定性传播方法及装置,能够在任何计算顺序下均得到唯一确定的传播结果,同时支持高效的硬件实现与形式化验证。
2、本申请所提供的基于离散状态合并的不确定性传播方法,包括:
3、获取第一操作数和第二操作数,所述第一操作数和所述第二操作数分别携带有状态标记,所述状态标记选自一个预设的有限状态集合,所述有限状态集合至少包括用于表示确定性的第一状态、用于表示第一类不确定性的第二状态、以及用于表示第二类不确定性的第三状态;
4、基于所述第一操作数的状态标记和所述第二操作数的状态标记,依据预设的状态合并规则,确定针对所述第一操作数和所述第二操作数执行指定操作所得结果的状态标记;
5、其中,所述预设的状态合并规则被构造为,对于所述有限状态集合中的任意三个状态标记,所述合并规则满足结合律,使得无论以何种顺序对多个操作数的状态标记进行合并,所得到的最终结果状态标记是唯一确定的,且仍在所述有限状态集合中。
6、本申请还提供一种基于离散状态合并的不确定性传播装置,包括:状态获取模块,用于获取第一操作数和第二操作数,所述第一操作数和所述第二操作数分别携带有状态标记,所述状态标记选自一个预设的有限状态集合,所述有限状态集合至少包括用于表示确定性的第一状态、用于表示第一类不确定性的第二状态、以及用于表示第二类不确定性的第三状态;状态合并模块,用于基于所述第一操作数的状态标记和所述第二操作数的状态标记,依据预设的状态合并规则,确定针对所述第一操作数和所述第二操作数执行指定操作所得结果的状态标记;其中,所述预设的状态合并规则被构造为,对于所述有限状态集合中的任意三个状态标记,所述合并规则满足结合律,使得无论以何种顺序对多个操作数的状态标记进行合并,所得到的最终结果状态标记是唯一确定的。
7、本发明还提供一种基于离散状态合并的不确定性传播电路,包括:
8、输入接口,用于接收第一操作数和第二操作数;
9、状态提取单元,用于从所述第一操作数和所述第二操作数中提取对应的状态标记,所述状态标记选自一个预设的有限状态集合,所述有限状态集合至少包括用于表示确定性的第一状态、用于表示第一类不确定性的第二状态、以及用于表示第二类不确定性的第三状态;
10、状态合并逻辑单元,其硬连线地实现了预设的状态合并规则,用于接收所述第一操作数和所述第二操作数的状态标记,并输出合并后的结果状态标记;
11、输出接口,用于输出所述合并后的结果状态标记以及所述指定操作的结果;
12、其中,所述状态合并逻辑单元实现的合并规则满足结合律,使得对于所述有限状态集合中的任意三个状态标记,无论所述状态合并逻辑单元以何种顺序接收和处理它们,其最终输出的状态标记是唯一确定的。
13、发明的技术效果和优点:通过定义有限离散状态并设计具有半环代数结构的合并规则,保证了不确定性传播过程符合结合律,彻底消除了因计算顺序或数据到达时序导致的结果不确定性。该方法及装置具有数学严谨性,可进行穷举等形式化验证;同时由于状态空间极小,状态合并逻辑可硬连线为查找表或极简组合逻辑,硬件实现面积小、功耗低、延迟短,可直接集成到处理器流水线中而不影响关键路径时序。由此,本申请为高性能计算、可信编译器及高可靠嵌入式系统提供了坚实的基础。
1.一种基于离散状态合并的不确定性传播方法,其特征在于,包括以下步骤:
2.根据权利要求1所述的方法,其特征在于,所述有限状态集合还包括:
3.根据权利要求2所述的方法,其特征在于,所述指定操作为加法操作,所述预设的状态合并规则具体包括:
4.根据权利要求3所述的方法,其特征在于,所述第四状态为乘法操作中的零元,使得第四状态与任一状态进行与乘法操作对应的状态合并时,结果均为第四状态。
5.根据权利要求3所述的方法,其特征在于,所述预设的状态合并规则及其作用的所述有限状态集合,共同构成一个数学半环结构。
6.根据权利要求5所述的方法,其特征在于,所述数学半环结构中,所述加法操作对应的合并规则满足交换律和幂等性。
7.根据权利要求1所述的方法,其特征在于,所述第一类不确定性为源于算术运算的进位不确定性,所述第二类不确定性为源于数据语义的未定义或未知状态的不确定性。
8.一种基于离散状态合并的不确定性传播装置,其特征在于,包括:
9.一种基于离散状态合并的不确定性传播电路,其特征在于,包括:
10.根据权利要求9所述的电路,其特征在于,所述状态合并逻辑单元包括一个查找表电路,所述查找表电路中预先存储了所有可能的状态标记组合与其对应结果状态的映射关系,且所述映射关系构成一个数学半环。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com