Parallel algorithm for finding modules of large-scale coherent fault trees

عنوان انگلیسی :

Parallel algorithm for finding modules of large-scale coherent fault trees

سال چاپ : 2015

تعداد صفحه : 4

چکیده :

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

عنوان فارسی :

قابلیت اطمینان میکروالکترونیکی-الگوریتم های موازی برای پیدا کردن نمونه های بزرگ درختان خطای منسجم

تعداد صفحه : 10 صفحه

چکیده :

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

جهت دریافت فایل مقاله به زبان انگلیسی و یا دریافت ترجمه مقاله با شماره زیر تماس حاصل فرمایید

09358978227 - زمانی

هزینه ترجمه مقاله 6 هزار تومان