The computation of the probability of the top event or minimal cut sets of fault trees is known as intractable NP-hard problems.Modularization can be used to reduce the computational cost of basic operations on fault trees efficiently. The idea of the linear time algorithm, as a very efficient and compact modules detecting algorithm, is visiting the nodes one by one with top-down depth-first left-most traversal of the tree. So the efficiency of the linear time algorithm is limited by nodes visiting time successively and serially, especially when confronting large-scale fault trees. Aiming at improving the efficiency of modularizing largescale fault trees, this paper proposes a new parallel method to find all possible modules. Firstly, we transform the fault tree into a directed acyclic graph (DAG) and treat the terminal basic nodes as entries of the algorithm. And then, according to the proposed rules in this paper, we traverse the graph bottom-up from the terminal nodes and mark the internal nodes in a parallel way. Therefore, we can compare all internal nodes and decidewhich nodes aremodules. Eventually, an experiment is carried out to compare the linear and parallel algorithm, and the result shows that the proposed parallel algorithm is efficient on handling large-scale fault trees.

 

 

محاسبه احتمال اتفاقات مهم یا حداقل مجموعه برشهای درختان خطا (گسل) به عنوان NP مقاوم و رام نشدنی- مشکلات سخت، شناخته می شود. پیمانه بندی (ماژول سازی) میتواند برای کم شدن هزینه های محاسبات عملیات اولیه درختان خطای کار آمد، استفاده شود. ایده الگوریتم خطی زمانی، به عنوان یک الگوریتم خیلی کارآمد و شناساگر ماژول های فشرده، گره هارا یک به یک از بالا به پایین، اول عمق، بیشترین پیمایش به سمت چپ درخت را، بررسی می کند، بنابراین کارآمدی الگوریتم زمانی خطی به وسیله دیدن گره ها به صورت پی در پی و ردیفی محدود می باشد، مخصوصا زمانی که با یک درخت خطای بزرگ روبه رو هستیم. با هدف بهبود کارآیی پیمانه بندی درختان خطای منسجم بزرگ، این مقاله یک روش موازی را برا پیدا کردن تمامی نمونه های احتمالی (ماژول) ارائه می دهد. در گام نخست، ما درختان خطای منسجم بزرگ را به یک گراف جهت دار غیر مدور تغییر میدهیم (DAG) و با گره های اصلی ترمینال مانند ورودی الگوریتم برخورد می کنیم. و سپس، با توجه به قوانین ارائه شده در این مقاله، ما از گره ترمینال در گراف از پایین به بالا حرکت می کنیم و گره های داخلی در راه های موازی را، علامت می زنیم. بنابراین، ما می توانیم تمام گره های داخلی را با هم مقایسه کنیم و تصمیم بگیریم که کدام یک از گره ها ماژول هستند. در نهایت، پژوهشی برای مقایسه الگوریتم های موازی و خطی انجام شد و نتایج نشان می دهد که الگریتم موازی برای بررسی و رسیدگی به درختان خطای بزرگ، کارآمد است.