CN-122019943-A - Parallelized cut-integrated reduction method based on prime number compression coding

CN122019943ACN 122019943 ACN122019943 ACN 122019943ACN-122019943-A

Abstract

A parallelization cut-integrated simplification method based on prime number compression coding relates to the field of fault tree analysis. Aiming at the problems that the simplified calculation process of the cut sets is serialized, the parallel efficiency is low, the data structure is not matched with the GPU parallel architecture and the minimum cut sets of a large-scale complex system are difficult to solve efficiently in the prior art, the method is provided for representing the cut sets in a fault tree model in a matrix mode in a binary vector mode, grouping the cut sets according to the number of events under the GPU parallel architecture, converting the cut sets into compressed integers by distributing unique prime numbers for basic events, realizing the integer division judgment of the inclusion relation of the cut sets, realizing the large-scale parallelization subset identification by matrix broadcasting and Boolean judgment matrix, dynamically updating the effective cut set by combining an instant rejection mechanism, remarkably improving the calculation efficiency and reducing the memory occupation. The method is suitable for the system reliability evaluation and safety analysis work.

Inventors

DING MING
WANG YANKAI
YANG YONGYONG
CAO XIAXIN
MENG ZHAOMING
GUO ZEHUA
HAO XIAOTIAN

Assignees

哈尔滨工程大学

Dates

Publication Date: 20260512
Application Date: 20251223

Claims (10)

1. A parallelized cut-and-gather reduction method based on prime number compression coding, comprising: Converting a plurality of cut sets to be simplified into binary vectors with equal length, splicing the binary vectors according to rows to form a two-dimensional cut set matrix, counting the number of 1's in each row under a parallel computing architecture, and grouping the cut sets according to the number of events to form a cut set subgroup which is arranged in ascending order according to the number of events; Distributing unique prime number codes for each basic event, generating a mapping table of the event and prime numbers, carrying out continuous multiplication on prime number codes corresponding to each 1' of each row of a previous output cut set matrix to obtain compressed integer codes of the cut set, and finally forming prime number compressed code vectors arranged according to subgroups; Selecting each subgroup of the previous output in pairs according to the number of the events, taking the subgroup with fewer events as a compared group and the subgroup with more events as a reference group, constructing a compared matrix and a reference matrix by utilizing a broadcasting mechanism, enabling each pair of elements of the two matrices to represent a comparison relation of a group of cutsets, and outputting matrix pairs with consistent matching dimension; Executing element-by-element integer division judgment on a matrix pair output before under a parallel computing architecture, marking 1 in a Boolean matrix when elements in a reference matrix can be integer divided by corresponding elements in a comparison matrix, and otherwise marking 0 to generate a Boolean judgment matrix representing a cut set inclusion relation; Removing the record identified as the non-minimum cut set according to the previous output Boolean judgment matrix result, dynamically updating the effective cut set index list to reduce the subsequent calculation scale, and outputting an updated cut set of the removed non-minimum cut set; And repeatedly executing the matrix construction, integer division judgment and non-minimum cut set elimination process until all the subgroups finish comparison, and outputting the cut set which is not finally contained as a minimum cut set result.
2. The parallelization cut-set simplification method based on prime number compression coding according to claim 1, wherein when the input fault tree model is structurally analyzed, the number statistics of 1' is carried out on each row of the cut-set matrix by adopting a parallel computing mode of intra-thread block reduction, and the step accumulation is realized through the inter-thread shared memory.
3. A parallelized prime number compression coding based cut-and-gather reduction method according to claim 1, characterized in that when assigning unique prime number codes to each basic event, the prime numbers are assigned according to the occurrence frequency of the basic event, and the high frequency event is assigned smaller prime numbers.
4. The parallelized prime number compression coding-based cut-and-gather reduction method according to claim 1, wherein when the compared matrix and the reference matrix are constructed, synchronous expansion of data according to row-column dimension is realized through a GPU broadcasting mechanism, and cyclic copy operation is avoided.
5. The parallelized prime number compression coding-based cut-and-gather reduction method of claim 1, wherein when performing element-by-element integer divide determination on the matrix pairs, a block parallel processing strategy is adopted to divide the integer divide determination matrix into a plurality of sub-blocks, the integer divide determination is performed by independent thread blocks, and the input data is cached through the shared memory.
6. The parallelized prime number compression coding-based cut-set reduction method according to claim 1, wherein when non-minimum cut sets are eliminated according to boolean judgment matrix results, the effective cut set index list is updated in real time so that the eliminated cut sets no longer participate in subsequent matrix construction operations.
7. A parallelized prime number compression coding-based cut-and-gather reduction device, comprising: Converting a plurality of cut sets to be simplified into binary vectors with equal length, splicing the binary vectors according to rows to form a two-dimensional cut set matrix, counting the number of 1's in each row under a parallel computing architecture, and grouping the cut sets according to the number of events to form a module of a cut set subgroup arranged according to the ascending order of the number of the events; Distributing unique prime number codes for each basic event, generating a mapping table of the event and prime numbers, carrying out continuous multiplication on prime number codes corresponding to each 1' of each row of a previous output cut set matrix to obtain compressed integer codes of the cut set, and finally forming a module of prime number compressed code vectors arranged according to subgroups; The method comprises the steps of selecting each subgroup of the previous output in pairs according to the number of events, taking the subgroup with fewer events as a compared group and the subgroup with more events as a reference group, constructing a compared matrix and a reference matrix by utilizing a broadcasting mechanism, enabling each pair of elements of the two matrices to represent a comparison relation of a group of cutsets, and outputting matrix pairs with consistent matching dimensions; Executing element-by-element integer division judgment on a matrix pair of a previous output under a parallel computing architecture, marking 1 in a Boolean matrix when elements in a reference matrix can be integer divided by corresponding elements in a comparison matrix, and otherwise marking 0 to generate a Boolean judgment matrix representing a cut set inclusion relation; A module for eliminating records identified as non-minimum cutsets according to the previous output Boolean judgment matrix result, dynamically updating the effective cutset index list to reduce the subsequent calculation scale, and outputting an updated cutset set with non-minimum cutsets eliminated; And repeatedly executing the matrix construction, integer division judgment and non-minimum cut set elimination process until all the subgroups finish comparison, and outputting the cut set which is not finally contained as a module of a minimum cut set result.
8. Computer storage medium for storing a computer program, characterized in that the computer performs the method of claim 1 when the computer program is read by the computer.
9. A computer comprising a processor and a storage medium, characterized in that the computer performs the method of claim 1 when the processor reads a computer program stored in the storage medium.
10. Computer program product, as a computer program, characterized in that the method of claim 1 is implemented when the computer program is executed.

Description

Parallelized cut-integrated reduction method based on prime number compression coding Technical Field Relates to the field of fault tree analysis, in particular to a high-efficiency parallelization fault tree cut set solving method. Background In the field of system security and reliability analysis, fault tree analysis (Fault TREE ANALYSIS, FTA) is a classical and widely used quantitative deduction analysis method. By hierarchically modeling the structure, functionality, and failure logic of the system, the fault tree can help engineers identify all basic event combinations that lead to the occurrence of system top events (system failure states), which are called cutsets (Cut sets). The minimum event combination which cannot be simplified is called a Minimum Cut Set (MCS), and the solving result directly reflects the weak link and the potential risk path of the system, so that the method is an important foundation for reliability assessment, risk prevention and control and system redundancy design. The prior art mainly adopts logical or bit operation of element-by-element comparison to carry out subset judgment. When faced with millions of cutsets, this approach, which requires near-O (n 2) comparisons, is computationally very complex and very long processing time, and becomes a major performance bottleneck in the overall reliability analysis flow. In addition, for the prime number-based simplification method, algorithms are mostly designed in series, so that the powerful capability of parallel computing hardware such as modern multi-core CPU (Central processing Unit), GPU (graphics processing Unit) and the like is difficult to effectively utilize, and the increasing requirement of a large-scale complex system on analysis efficiency cannot be met. In summary, the prior art has the defects of serialization of the cut-and-gather simplified calculation process, low parallel efficiency, mismatching of a data structure with a GPU parallel architecture, and incapability of efficiently solving the minimum cut-and-gather of a large-scale complex system. Disclosure of Invention In order to solve the defects of serialization, low parallel efficiency, unmatched GPU parallel architecture of data structure and incapability of efficiently solving the minimum cut set of a large-scale complex system in the cut-set simplified calculation process in the prior art, the invention provides the technical scheme as follows: A parallelized cut-gather reduction method based on prime number compression coding, comprising: Converting a plurality of cut sets to be simplified into binary vectors with equal length, splicing the binary vectors according to rows to form a two-dimensional cut set matrix, counting the number of 1's in each row under a parallel computing architecture, and grouping the cut sets according to the number of events to form a cut set subgroup which is arranged in ascending order according to the number of events; Distributing unique prime number codes for each basic event, generating a mapping table of the event and prime numbers, carrying out continuous multiplication on prime number codes corresponding to each 1' of each row of a previous output cut set matrix to obtain compressed integer codes of the cut set, and finally forming prime number compressed code vectors arranged according to subgroups; Selecting each subgroup of the previous output in pairs according to the number of the events, taking the subgroup with fewer events as a compared group and the subgroup with more events as a reference group, constructing a compared matrix and a reference matrix by utilizing a broadcasting mechanism, enabling each pair of elements of the two matrices to represent a comparison relation of a group of cutsets, and outputting matrix pairs with consistent matching dimension; Executing element-by-element integer division judgment on a matrix pair output before under a parallel computing architecture, marking 1 in a Boolean matrix when elements in a reference matrix can be integer divided by corresponding elements in a comparison matrix, and otherwise marking 0 to generate a Boolean judgment matrix representing a cut set inclusion relation; Removing the record identified as the non-minimum cut set according to the previous output Boolean judgment matrix result, dynamically updating the effective cut set index list to reduce the subsequent calculation scale, and outputting an updated cut set of the removed non-minimum cut set; And repeatedly executing the matrix construction, integer division judgment and non-minimum cut set elimination process until all the subgroups finish comparison, and outputting the cut set which is not finally contained as a minimum cut set result. Further, in a preferred embodiment, when the input fault tree model is structurally analyzed, the number of 1's is counted for each row of the cut set matrix by adopting a parallel computing mode of in-thread block reduction, and step accumulation is realiz