CN-122019129-A - Matrixing parallel computing method for solving minimum cut set of fault tree

CN122019129ACN 122019129 ACN122019129 ACN 122019129ACN-122019129-A

Abstract

A matrixing parallel computing method for solving a minimum cut set of a fault tree relates to the field of fault tree analysis. Aiming at the problems that in the prior art, the calculation process is serialized, the parallel efficiency is low, the data structure is not suitable for a GPU architecture and the minimal cut set of a large-scale fault tree cannot be solved efficiently, the matrixing parallel calculation method for solving the minimal cut set of the fault tree is provided. The method comprises the steps of carrying out structural coding on a fault tree, constructing a gate event and an input relation into a structural description matrix, vectorizing a basic event and representing a candidate cut set of an intermediate event in a binary matrix form, carrying out row combination on a gate under a GPU parallel architecture, carrying out broadcast combination on the gate and carrying out parallel cut integration simplification, and simultaneously introducing a blocking and buffer multiplexing strategy to improve the calculation throughput rate and reduce the memory occupation. And (5) outputting a minimum cut set by circulating iteration until the top event matrix is stable. The method is suitable for safety and reliability analysis of large complex engineering systems.

Inventors

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

Assignees

哈尔滨工程大学

Dates

Publication Date: 20260512
Application Date: 20251223

Claims (10)

1. A matrixing parallel computing method for solving a minimal cut set of a fault tree, comprising: Carrying out structural coding on an input fault tree model, establishing a structural description matrix for representing the relation between a gate event and an input event and the gate type attribute, and uniformly representing a fault tree logic structure in a matrix form to form a computable input; Vectorizing the basic event to represent and generate a corresponding independent heat vector, and forming a candidate matrix by the intermediate event and a candidate cut set thereof according to a binary form to form a data input set for logic operation; determining intermediate events with candidate matrixes in all inputs in the current calculation round according to the structure description matrix, and generating a target event list to ensure the accuracy of a calculation sequence; When the intermediate event is an OR gate, performing row dimension merging and parallel deduplication on the candidate matrix of the input event to generate a union candidate matrix, and outputting a result as an upper event input; When the intermediate event is an AND gate, performing row dimension expansion on the input candidate matrix, performing component-by-component combination and normalization on the parallel processing unit to generate a Cartesian combination matrix, and outputting a combination result for subsequent simplification; A step of executing parallelization cut set comparison on the generated candidate matrix to delete redundant cut sets containing relations and keep the minimum cut set, and taking the reduced matrix as a next round input; Dynamically implementing a blocking and cache multiplexing strategy according to the scale and calculation bandwidth of the candidate matrix to reduce memory occupation and improve operation throughput rate, and using an optimization result for continuous iterative calculation; and circularly executing the operations of determining the intermediate event, logic combination and parallel reduction until the top event candidate matrix is stable and outputting the minimum cut set as a final solving result.
2. The matrixing parallel computing method for solving fault tree minimal cut sets according to claim 1, wherein a partition structure description matrix is adopted in the structured coding process, input relations between gate events and basic events are represented in partitions, and gate type identifiers are set in additional columns to distinguish and gates from or gates.
3. A matrixing parallel computing method for solving fault tree minimal cut sets according to claim 1, wherein the number of basic events in the system is used as vector dimension in the vectorization representation process, each event or event combination is represented as binary vector, and a plurality of cut set vectors are stacked in rows to form a candidate matrix.
4. A matrixing parallel computing method for solving fault tree minimal cut sets according to claim 1, characterized in that candidate matrices of a plurality of input events of and gates are expanded along a row dimension and component-by-component addition operation is performed on parallel processing units, and binary characteristics are maintained by performing normalization processing on elements greater than one in the addition result.
5. The matrixing parallel computing method for solving fault tree minimal cut set according to claim 1, wherein all row vectors of the candidate matrix are aligned in parallel by adopting a containment relationship judging mechanism, and when a certain row vector is detected to completely contain another row vector, the containment is deleted.
6. A matrixing parallel computing method for solving fault tree minimal cut sets according to claim 1, characterized in that the computing blocks are dynamically divided according to the size of candidate matrices and computing hardware bandwidth, and the buffer space is multiplexed in the cyclic computation.
7. A matrixing parallel computing device for solving a minimal cut set of a fault tree, comprising: Carrying out structural coding on an input fault tree model, establishing a structural description matrix for representing the relation between a gate event and an input event and the gate type attribute, and uniformly representing a fault tree logic structure in a matrix form to form a module capable of calculating input; the module is used for vectorizing the basic event to represent and generate a corresponding independent heat vector, and forming a candidate matrix by the intermediate event and a candidate cut set thereof according to a binary form so as to form a data input set for logic operation; the module is used for determining intermediate events of candidate matrixes in all inputs in the current calculation round according to the structure description matrix and generating a target event list so as to ensure the accuracy of a calculation sequence; when the intermediate event is an OR gate, performing row dimension merging and parallel deduplication on the candidate matrix of the input event to generate a union candidate matrix, and outputting a result as an upper event input module; When the intermediate event is an AND gate, performing row dimension expansion on the input candidate matrix, performing component-by-component combination and normalization on the parallel processing unit to generate a Cartesian combination matrix, and outputting a combination result to a module for subsequent simplification; a module for executing parallelization cut set comparison on the generated candidate matrix to delete redundant cut sets containing relations and keep the minimum cut set, and taking the reduced matrix as the next round of input; A module for dynamically implementing blocking and buffer multiplexing strategies according to the scale of the candidate matrix and the calculation bandwidth to reduce memory occupation and improve operation throughput rate, and using an optimization result for continuous iterative calculation; And circularly executing the operations of determining the intermediate event, logic combination and parallel reduction until the top event candidate matrix is stable and outputting the minimum cut set as a final solving 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

Matrixing parallel computing method for solving minimum cut set of fault tree Technical Field The method relates to the field of fault tree analysis, in particular to matrixing parallel calculation for solving a minimum cut set of a fault tree. Background Fault tree analysis (Fault TREE ANALYSIS, FTA) is a top-down system security analysis method, which is used to identify system weak links and evaluate failure risk by modeling and reasoning about the logical relationship between unexpected events (top events) and potential causes (basic events) in the system. Since the 60 s of the 20 th century, the method was proposed by the bell laboratories in the united states, and has been widely used in the high reliability industries of aerospace, nuclear energy, electric power, rail transit, automotive electronics, and chemical safety. In fault tree analysis, minimum Cut Set (MCS) solution is the most core link. The minimal cut set represents a minimal set of basic events that occur when they occur simultaneously. The minimum cut set is accurately and efficiently solved, the accuracy of the identification and quantitative reliability assessment result of the system failure mode is related, and the scientificity of the system safety design and maintenance strategy is directly influenced. Aiming at the minimum cut set solution, various algorithms and improvement methods are provided for scholars and engineering software at home and abroad. For example: (1) MOCUS algorithm (Method Of Obtaining Cut Sets) the method generates cutsets step by top-down logic expansion, which is one of the earliest and most classical algorithms. The method has the advantages of simple realization, but frequent logic simplification is needed in a large-scale fault tree, so that the calculation complexity is exponentially increased. (2) Fussell-Vesely algorithm, namely solving the cutset of the intermediate event step by step through the logic simplest idea, partially improving the calculation efficiency, but still expanding in a recursion form, and hardly fully utilizing the parallelism capability of the modern calculation platform. (3) Based on the algorithm of Boolean algebra and ZBDD (Zero-suppressed Binary Decision Diagram), the method utilizes a decision diagram data structure to carry out logic compression, can effectively reduce repeated calculation, and typically represents a BDD solving module in an SCRAM tool. However, BDD-like methods occupy huge memory resources due to node explosion in large-scale engineering systems, and have difficulty in parallelization implementation. (4) Heuristic and intelligent algorithms in recent years, partial research attempts to introduce cut set search methods, branch deductions or Monte Carlo simulation to improve minimum cut set search, but these methods generally rely on random search mechanisms, so that the integrity and certainty of results are difficult to ensure, and the calculation efficiency is rapidly reduced along with the problem scale. As modern engineering systems increase dramatically in size and complexity, traditional least squares solution algorithms face significant challenges: On one hand, the system has deep hierarchy, more logic gates and complex combination, so that the number of cutsets increases exponentially, and the traditional recursive or serial algorithm has long calculation time consumption and large memory occupation; On the other hand, the data structure (such as a linked list and a tree structure) of the existing algorithm is not suitable for the modern parallel architecture such as the GPU, and the high throughput and multi-thread concurrency characteristics of the graphics processor cannot be fully utilized. In addition, the current mainstream method focuses on the improvement of the algorithm level, but lacks systematic reconstruction from the point of view of a data structure and a computational mapping mechanism, and fails to realize the transition from the symbolic logic solution to the numerical matrixing solution. In summary, the prior art has the defects of serialization of the calculation process, low parallel efficiency, data structure inadaptation to the GPU architecture, and incapability of efficiently solving the minimum cut set of the large-scale fault tree. Disclosure of Invention In order to solve the defects that in the prior art, the calculation process is serialized, the parallelism efficiency is low, the data structure is not adaptive to the GPU architecture, and the minimum cut set of a large-scale fault tree cannot be solved efficiently, the invention provides the following technical scheme: A matrixing parallel computing method for solving a fault tree minimal cut set, comprising: Carrying out structural coding on an input fault tree model, establishing a structural description matrix for representing the relation between a gate event and an input event and the gate type attribute, and uniformly representing a fault tree logic structure in a