پایگاه علمی سعید سان دانلود رایگان مقالات علمی کنفرانس و ژورنال
دانلود ترجمه و آنالیز آنالیز مقاله اول یافتن مسیر بهینه بدون خطا در شبکه با خرابی گره زیاد
آنالیز مقاله اول
یافتن مسیر بهینه بدون خطا در شبکه با خرابی گره زیاد
– طرح اصلی مقاله
تعبیه مسیر ویژه در پردازش‌های موازی از اصول بسیارمهم است. قبلا، تعدادی از الگوریتم‌های موازی که توانایی اجرا شدن روی آرایه‌های خطی را دارند توسعه داده شده اند. بنابراین به خوبی قابل اجرا روی معماری موازی و مسیر تعبیه شده هستند. پیدا کردن طولانی ترین مسیر عاری از خطا بین دو گره دلخواه، می‌تواند در الگوریتم‌های مسیریابی دوگانه و چندگانه برای کاهش تراکم و اجتناب از بن بست موجود در الگوریتم‌های درختی رایج در محاسبات موازی مورد استفاده قرار گیرد.
با توجه به اینکه خرابی لینک و پردازنده ممکن است زمانی که شبکه در حال استفاده است، رخ دهد، لذا رسیدگی به شبکه معیوب و یافتن مسیر عاری از خطا بسیار مهم است. با فرض اینکهمجموعه خرابی‌های گره در گراف ستاره ای بعدی Sn مفروض باشد. میتوان نشان داد جائیکه و کمینه باشد حلقه بدون خرابی با طول (به طوری که همه خرابی‌های گره وابسته به گراف ستاره ای m بعدی است) توانائی تعبیه شدن روی را دارد.
آنالیز مقاله دوم
تعبیه سیکل تحمل پذیری خطا در فرامکعب با زوج‌هایی از گره‌ها و لبه‌های خراب
– طرح اصلی مقاله
فرض کنید fv (به همان ترتیب، fe) تعدادی ازگره‌های معیوب (به همان ترتیب، لبه‌ها) دریک فرامکعبی چندبعدی را مشخص می‌کنند. در این طرح نشان داده شده است که یک سیکل عاری از خطا با حداقل طول می‌تواند در یک فرامکعبی چند بعدی با و تعبیه شود. با فرض یا و نتایج نه تنها بهترین نتایج به دست آمده قبلی را بهبود می بخشد بلکه نتایجی را که فقط در آن گره‌های معیوب مطرح شده اند را نیز بهبود می‌بخشد. فرامکعبی یکی از پرکاربردترین معماری‌های چند منظوره‌ای است که تاکنون برای ساختارهای موازی حجیم یا سیستم‌های توزیع شده به اکتشاف رسیده است. یک ساختار حلقه ای که یک توپولوژی اساسی برای پردازش توزیع شده و موازی می‌باشد، که برای شبکه‌های محلی و توسعه الگوریتم‌های موازی مشابه با هزینه‌های ارتباطی کم مناسب است.
Embedding longest fault-free paths onto star graphs
with more vertex faults
Sun-Yuan Hsieh
Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1,
Ta-Hsueh Road, Tainan 701, Taiwan
Received 16 March 2004; accepted 14 January 2005
Communicated by O. Watanabe
Abstract
The n-dimensional star graph Sn belongs to a class of bipartite graphs, and it is recognized as
an attractive alternative to the hypercube. Since S1, S2, and S3 have trivial structures, we focus our
attention on Sn with n4 in this paper. Let F (Sn) be the set of vertex faults. Previously, it was
shown that when |F (Sn)|n – 5, Sn with n6 can embed a longest fault-free path of length at least
n! – 2|F (Sn)| – 1 (respectively, n! – 2|F (Sn)| – 2) between two arbitrary vertices in different partite
sets (respectively, the same partite set) [Longest fault-free paths in star graphs with vertex faults,
Theoretical Computer Science 262 (2001) 215–227]. In this paper, we improve the above result by
tolerating more faults (|F (Sn)|n – 3) to embed a longest fault-free path between two arbitrary
vertices in Sn, n4.
© 2005 Elsevier B.V. All rights reserved.
Keywords: Interconnection networks; Fault-tolerant embedding; Longest fault-free paths; Star graphs
Fault-tolerant cycle embedding in the hypercube
with more both faulty vertices and faulty edges
Sun-Yuan Hsieh
Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road,
Tainan 70101, Taiwan, ROC
Received 22 March 2004; received in revised form 1 September 2005; accepted 26 September 2005
Available online 28 November 2005
Abstract
Let fv (respectively, fe) denote the number of faulty vertices (respectively, edges) in an n-dimensional hypercube. In this
paper, we show that a fault-free cycle of length of at least 2n 2fv can be embedded in an n-dimensional hypercube with
fe 6 n 2 and fv + fe 6 2n 4. Our result not only improves the previously best known result of [A. Sen, A. Sengupta,
S. Bandyopadhyay, On some topological properties of hypercube, incomplete hypercube and supercube, in: Proceedings
of the International Parallel Processing Symposium, Newport Beach, April, 1993, pp. 636–642] where fv > 0 or fe 6
n 2 and fv + fe 6 n 1 were assumed, but also extends the result of [J.-S. Fu, Fault-tolerant cycle embedding in the
hypercube, Parallel Computing 29 (2003) 821–832] where only the faulty vertices are considered.
2005 Elsevier B.V. All rights reserved.
Keywords: Hypercubes; Interconnection networks; Fault-tolerant embedding; Cycle embedding
مقاله اصلی لاتین در قالب فایل پی دی اف و ترجمه ها در قالب فایل ورد + فایل پاورپوینت 14 اسلایدی