در [۳۹] نگاهی به ارزیابی و طراحی الگوریتم‌های مهم ولی ساده در علوم محاسبات انجام داده است و شیوه‌های مختلفی به قالب تفسیر اصلی این الگوریتم‌ها افزوده است. الگوریتم‌های معرفی شده را برای اجرا در سیستم‌های چند هسته‌ای و توزیع‌شده آماده نموده و نیاز به درجه بالای همزمانی برای رسیدن به قدرت محاسباتی بیشتر در معماری‌های جدید را نشان داده است. استاندارد MPI را معرفی و استفاده از آن را در مدیریت پردازش‌ها روی هسته‌های یک پردازنده مناسب دانست. البته برای کار نمودن روی تعداد هسته بیشتر که در آینده خواهد آمد ترکیبی از MPI و OpenMP را پیشنهاد نموده است. البته شیوه‌های مختلف افزوده شده به الگوریتم‌های موجود با توجه به تغییرات سخت‌افزار در آینده نیاز به تغییر دارد.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در [۴۰] مسایل هماهنگ‌سازی تصویری یک زوج مدل وابسته در شبکه‌های عصبی را مورد بررسی قرار داده است. برای نزدیک شدن به اجرای دنیای واقعی با مسایل تاخیرزمانی، توزیع و اختلال در مدل، روبرو خواهیم بود. و برای هماهنگ‌سازی تصویری برای شبکه‌های عصبی مدلی بر اساس نظریه ثبات Lyapunov و روش کنترل تطبیقی ارائه داده است. شبیه‌سازی عددی انجام شده برای مدل پیشنهادی نشان دهنده امکان‌سنجی و اثربخشی نتایج بدست آمده است. در این مقاله فرض شده است که احتمالات انتقال توسط زنجیره مارکوف انجام پذیرد. در صورتی که با انتقال وقت‌گیری مواجه شویم احتمال انتقال ناقص نیز وجود دارد.
در [۴۱] یک الگوریتم جدید هماهنگ سازی ساعت بنام SAPD ارائه شده است که ترکیبی از دو الگوریتم PDC و DSA بوده و ایده‌های پارامتریک تفاوت در RBS و میزان همکاری عملیات در CTS را در خود گنجانده است. الگوریتم و مدل زمانبندی جدید ارائه و پیاده‌سازی شده علاوه به بهبود عملکرد و زمان الگوریتم هماهنگ‌سازی، پایداری و دقت مطلوبی که ازویژگی‌های کلیدی می‌باشد برخوردار است. الگوریتم هماهنگ‌سازی جدید برای اولین بار در محیط‌های شبیه سازی مربوط به برنامه‌های توزیع‌شده فرموله و به اجرا در آمده است.
در [۴۲] یک شمارنده برچسب زمانی براساس پروتکل همزمان‌سازی ساعت نسبی با دقت بالا، برای سیستم‌های کنترل شرایط زمانی توزیع‌شده روی شبکه‌های محلی به‌نام TSC-RCSP ارائه شد. روش ارائه شده یک راه‌حل کم هزینه برای هماهنگ‌سازی بوده و نیاز به دستگاه‌های گران‌قیمت و سفارشی مانند یک گیرنده رادیویی ماهواره‌ای نیاز نبوده و از دقت بالایی برخوردار است. همزمان‌سازی ارائه شده قابل استفاده به‌طور وسیع در پروتکل‌های شبکه است. ثبات شمارنده برچسب زمانی پردازنده‌ها معمولاً از ساعت TOD استفاده می‌کنند که در این روش نیز از همان استفاده نمودند. که یک روش بدون هزینه و بدون اعمال سخت افزار اضافی می‌باشد. در این پایان نامه نیز سعی در ارائه روشی برای همزمان‌سازی منطقی برنامه‌ها بدون اعمال سخت‌افزار اضافه و هزینه است. این مقاله سعی در افزایش سرعت اجرا با همزمان‌سازی ارائه شده بوده همچنین در این پایان نامه نیز سعی در ارائه روشی برای برقراری انحصار متقابل و کنترل ناحیه بحرانی همانند روش ارائه شده در [۳۳] براساس شبکه‌های عصبی رقابتی است و سعی در بهبود کار داریم.
در [۴۳] مطالعه‌ای روی مقالاتی که درباره طراحی و یکپارچه‌سازی سیستم، روش یا مدل محاسبات و بهینه‌سازی‌ها انجام داده البته بیشتر روی تحقیقاتی که سبب بهبود استفاده از زمان واقعی در سیستم‌های تعبیه‌شده است تمرکز نمود. مقالات مورد بررسی در زمینه‌های سیستم‌های محاسباتی زمان واقعی، فن‌آوری GPU، معماری چند هسته‌ای، فن‌آوری‌های شبکه‌های حسگر بی‌سیم و همچنین سیستم‌های فیزیکی اینترنتی و برنامه‌های کاربردی می‌باشد. ظهور سخت‌افزارهای چند‌هسته‌ای سطح بیشتری از پیچیدگی را وارد محاسبات نموده است. اجبار تکنولوژی و اقتصادی برای مهاجرت به سیستم عامل‌های چند هسته‌ای سبب تشدید مسایل مربوط به همزمانی برای نرم‌افزارهای و تعبیه شده و زمان واقعی شده است.
در [۴۴] برنامه‌های مختلفی را مورد بحث قرار داده، مفاهیم مختلف هماهنگ‌سازی را معرفی و روش‌های مختلف تجزیه‌وتحلیل نتایج برای فاز هماهنگ‌سازی و فاز متعادل نمودن بار را مورد بحث قرار می‌دهد همچنین نحوه شکل‌گیری الگوی هماهنگ‌سازی فرکانس و هماهنگ سازی جزیی را ارائه می‌دهد. در این مقاله انواع توپولوژی‌های کامل و جزیی شبکه، همگن و ناهمگن، نوسانات محدود و بی‌نهایت تحت پوشش قرار گرفته است. با وجود این پیشینه زیاد معرفی شده و استفاده‌های بی‌شمار و ارائه نتایج نظری متعدد روی خواص هماهنگ‌سازی اما همچنان مسایل مهمی باز است.
یکی از کاربردهای اصلی نسل آینده موازی سازی و سیستم‌های توزیع شده تجزیه‌وتحلیل ترافیک داده عظیم است.در [۴۵] مطالعه‌ای برروی مخازن داده‌ای توزیع شده و چالش‌های پیش روی برای روش‌ها و توسعه نرم‌افزارها این چنینی را معرفی می کند. یکی از چالش‌های معرفی شده حفظ حریم خصوصی در تکنیک‌های توزیع شدگی است. نحوه توزیع بر روی سیستم‌عامل‌های مختلف با قابلیت‌های محاسباتی گوناگون و شبکه، تحمل خطا، امنیت، مقیاس‌پذیری، کنترل دسترسی و اینکه وظایف تجزیه‌وتحلیل معمولاً با محدودیت زمانی روبرو هستند از مسایل مهم دیگر است.
در [۴۶] نمای کلی از پروژه SimGrid را ارائه می‌دهد و پیشرفت‌های علمی و مهندسی اخیر در این زمینه را بیان می‌دارد. راهکارهایی برای بهبود در دقت و مقیاس پذیری ارائه داده است. استفاده از این تکنیک، با ارائه یک طراحی شبیه‌سازی و تجزیه‌وتحلیل قالب به عنوان بخشی از SimGrid یک قدم بزرگ به سوی روش علمی بهتر در این زمینه باشد. هدف از طراحی SimGrid قابلیت اجرا در تمامی زمینه‌های مربوطه با دقت و مقیاس‌پذیری لازم است تلاش‌های اخیر برای تطبیق‌پذیری شبیه‌ساز می‌باشد.
در [۴۷] یک روش هماهنگ سازی بر مبنا تئوری گراف کارآمد برای شبکه‌های زوجی تصادفی با بهره گرفتن از زنجیره مارکوف و استفاده از یک کنترل کننده بازخورد حالت ارائه شده است. بدلیل اینکه دید کلی در مورد شبکه‌ها را در نظر گرفته است هر دو نوع نویز سفید و رنگی را در مدل ارائه شده دخیل نموده است. روش ارائه شده در این مقاله ترکیب دو روش هماهنگ سازی نمایی لحظه‌ای و دائمی است که روی شبکه‌های اجرا-پاسخ با بهره گرفتن از زنجیره‌های مارکوف ارائه و معرفی شده است. معیارهای هماهنگ‌سازی نمایی ارتباط نزدیک با خواص توپولوژیکی شبکه‌های اجرا- پاسخ دارد. در انتها با بهره گرفتن از یک مثال عددی و شبیه‌سازی روش بهبود کارایی هماهنگ‌سازی را نمایش داده شده است.
مساله انحصار متقابل اظهار می‌دارد که فقط یک پروسه واحد می‌تواند اجازه دسترسی به یک منبع محافظت شده، یا بخش بحرانی را در یک زمان داشته باشد. انحصار متقابل نوعی همسان‌سازی و یکی از بنیادی‌ترین اصول در سیستم‌های کامپیوتری است. انحصار متقابل به صورتی گسترده در سیستم‌های توزیع شده مورد مطالعه قرار گرفته است، که در آنها پروسه‌ها توسط انتقال پیغام ناهماهنگ با یکدیگر ارتباط برقرار می‌کنند. برای سیستمی دارای N پروسه، الگوریتم‌های رقیب بسته به خصوصیاتشان دارای یک پیچیدگی پیغام بین logN و (N-1)3 پیغام در هر دسترسی به منبع بحرانی (CS) هستند. الگوریتم‌های انحصار متقابل توزیع شده یا نشانه محورند یا غیر نشانه محور. در الگوریتم‌های انحصار متقابل نشانه محور، یک نشانه منحصر به فرد در سیستم وجود داشته و فقط صاحب نشان می‌تواند به منابع محافظت شده دسترسی پیدا کند. الگوریتم‌های انحصار متقابل غیر نشانه محور برای تعیین اینکه کدام پروسه می‌تواند بعد از این به بخش حیاتی دست پیدا کند به تبادل پیغام می‌پردازند]۶۵[.
در ]۳۷[ یک نظریه راجع به ساختارهای داده برای طراحی الگوریتم‌های انحصاری متقابل ارائه شده است. بر اساس این نظریه، یک ساختار داده به توصیف این می‌پردازد که کدام پروسه به نگهداری از اطلاعات در مورد کدام پروسه دیگر می‌پردازد، و یک پروسه باید از کدام پروسه دیگر قبل از ورود به بخش حیاتی اطلاعات کسب کند.
جدول ۳‑۱- مقایسه سه الگوریتم MDX بنیادی ]۳۷[
الگوریتم پیغام به ازای هر ورودی/خروجی تاخیر قبل از ورودی مسایل
مرکزی سازی شده
۳
۲
نقص در هماهنگ کننده
توزیع شده
۲(n-1)
۲(n-1)
نقص همه پروسه ها
حلقه نشانه
۱ تا ∞
۰ تا n-1
نشانه گم شده، شکست پروسه
به منظور مقایسه با جزئیات الگوریتم‌ها، ما می‌توانیم به مشاهده سایر خصوصیات الگوریتم‌های ذکر شده در جدول ۳-۱ بپردازیم. این موارد در جدول ۳-۱ به منظور مقایسه الگوریتم‌ها ذکر شده‌اند: تعداد پیغام‌های مورد نیاز به ازای ورود/خروج از منطقه بحرانی، تاخیر قبل از ورود و همچنین مسایل عمده مربوط به هر الگوریتم ]۳۷[.
ما می‌دانیم که نشانه‌های زمانی برپایه ساعت لامپورت به هر پیغام اختصاص می‌یابند. در زمینه انحصار متقابل، ساعت‌های لامپورت بدین ترتیب عمل می‌کنند: هر پروسه یک ساعت عددی مدرج با مقدار اولیه ۰ را حفظ می‌کند. هر وقت پروسه‌ای بخواهد به منطقه بحرانی دسترسی یابد، به آن درخواست یک برچسب زمانی اختصاص داده می‌شود که یکی بیشتر از مقدار ساعت است. پروسه درخواست دارای برچسب زمانی را برای تعیین اینکه آیا می‌تواند به منطقه بحرانی دسترسی یابد یا خیر به سایر پروسه‌ها ارسال کند. هروقت پروسه‌ای یک درخواست دارای برچسب زمانی از پروسه‌ای دیگر که به دنبال اجازه دستیابی به منطقه بحرانی است دریافت می‌کند، پروسه ساعت خود را به حداکثر مقدار فعلی‌اش و برچسب زمانی درخواست به روز رسانی می‌کند]۴۲[.
قابلیت اطمینان یک معیار خیلی مهم برای راه حل‌های اکثر مسایل محافظت از منابع در شرایط واقعی می‌باشد. تعریف پذیرفته شده قابلیت اطمیان در حیطه انحصار متقابل زمانی است که در آن یک سیستم هیچ نقص و شکستی نداشته و یا قادر است کار خود را در هر شرایطی ادامه دهد]۶۵[.
در ادامه، به توصیف مدل سیستمی کلی پرداخته و مروری خواهیم داشت بر روی الگوریتم ریکارت-آگراوالا (RA[152]) که بهترین الگوریتم انحصار متقابل توزیع شده شناخته شده می‌باشد ]۶۵[.
الگوریتم RA و الگوریتم ارائه شده توسط لامپورت مدل پیش‌رو را در نظر می‌گیرند. تعداد N پروسه در سیستم وجود دارند. پروسه‌ها فقط از طریق ارسال پیام‌های همزمان در کل یک شبکه ارتباطی با یکدیگر ارتباط برقرار می‌کنند، که بدون خطا بوده، و زمان‌های ارسال پیغامی که ممکن است متفاوت باشند. فرض بر این است که پروسه‌ها به درستی کار می‌کنند. بر خلاف الگوریتم RA اما مشابه الگوریتم لامپورت، ما کانال‌های FIFO را در شبکه ارتباطی خود مفروض می‌داریم. بدون از دست دادن اصل کلی، ما فرض می‌کنیم که یک پروسه واحد در یک سایت یا گره در نمودار سیستمی شبکه اجرا می‌شود. بدین ترتیب، واژه‌های پروسه، سایت و گره را می‌توان به جای یکدیگر به کار برد.
یک پروسه با ارسال دستور “REQUEST” درخواست خود مبنی بر دسترسی به منطقه بحرانی را ارسال کرده و قبل از وارد شدن به آن منطقه بحرانی منتظر پاسخ‌های مناسب می‌ماند. در حالیکه یک پروسه در حال انتظار برای وارد شدن به CS خود است، نمی‌تواند درخواست دیگری ارسال کرده یا وارد CS دیگری شود. به هر “REQUEST” برای دسترسی به CS یک اولویت اختصاص داده می‌شود. و “REQUEST” های دسترسی به CS باید به منظور کاهش اولویت برای انحصار متقابل عادلانه همگی تایید شوند. اولویت یا شناسایی کننده، یا ReqID یک درخواست به صورت ReqID برابر است با (ترتیب شماره,PID) تعریف می‌گردد، که در آن شماره ترتیب یک عدد ترتیب اختصاصی محلی برای درخواست، و PID همان شناسایی کننده پروسه است. شماره ترتیب بدین صورت تعیین می‌گردد: هر پروسه بالاترین عدد ترتیب دیده شده (HSNS) تا به حال را، در یک HSNS متغیر محلی ذخیره می‌کند. وقتی یک پروسه یک درخواست ارسال می‌کند، از یک عدد ترتیب استفاده می‌کند که یکی بیشتر از مقدار HSNS است.
این الگوریتم از دو نوع پیغام استفاده می‌کند: “REQUEST” و REPLY. به عنوان ساختار داده، هر پروسه Pi از متغیرهای عدد صحیح محلی زیر استفاده می‌کند:
My_Sequence_Numberi, ReplyCounti, and HSNSi
الگوریتم RA در شکل ۳-۱ نمایش داده شد. همه رویه‌ها در این الگوریتم به صورت ذره‌ای انجام می‌شوند. فقط پروسه‌های با اولویت بالاتری که درخواست دسترسی به منطقه بحرانی را داده‌اند پیام‌های REPLY ارسالی توسط پروسه را مسدود می‌کنند. بدین ترتیب، وقتی یک پروسه پیغام‌های REPLY به همه درخواست‌های معوقه ارسال می‌کند، پروسه دارای بالاترین اولویت بعدی آخرین پیغام REPLY مورد نیاز را دریافت کرده و وارد CS می‌شود. اجرای درخواست‌های CS در این الگوریتم همیشه به ترتیب اولویت کاهشی است.
برای هر دسترسی به CS، دقیقا (N-1)2 پیغام وجود دارند: (N-1 REQUEST) و (N-1 REPLY). این الگوریتم عادلانه و ایمن است. هرچند، این الگوریتم دارای معایبی است، مانند داشتن قابلیت بالایی برای بروز اشتباه، داشتن یک نقطه شکست در هر پروسه و تنگنا داشتن سیستم. همچنین دارای قدرت موازی سازی کمی است. از میان این معایب، دو مورد اهمیت بیشتری به نسبت سایرین دارند، چرا که در صورتی که اتفاق بیافتند، منجر به شکست کل سیستم می‌شوند. اگر هر کدام از پروسه‌ها از کار بیافتد، همه اطلاعات شامل درخواست‌های پروسه‌ای که در صف قرار دارند و پرچم‌های مربوط به منابع از دست می‌روند. اما دو مساله دیگر فقط بر روی کارایی و سرعت سیستم تاثیر می‌گذارند.
شکل ۳‑۱ – : الگوریتم توزیع شده ریکارت و آگراوالا
یک “REQUEST” ارسال شده توسط پروسه Pi با عدد ترتیب x با بهره گرفتن از شناسه درخواستش مبنادهی می‌شود، بدین صورت: Ri,x. اولویت Ri;x به صورت (x, i) نشان می‌دهیم، که به صورت Pr(Ri,x) هم نشان داده می‌شود. عدد ترتیب x هر وقت هیچ ابهامی وجود نداشته باشد حذف می‌شود، و می‌گوییم که یک درخواست Ri دارای اولویت Pr(Ri) می‌باشد. از این عبارت در کل این روش استفاده شده است. وقتی گفته می‌شود دو “REQUEST” همزمان هستند که برای هر کدام از پروسه‌های درخواست کننده، “REQUEST” صادر شده توسط پروسه دیگر پس از درخواستی که توسط این پروسه ارسال شده بود دریافت گردد.
Ri و Rj در صورتی همزمان محسوب می‌شوند که “REQUEST” مربوط به Ri پس از اینکه Rj درخواست خود را ارسال کرد دریافت گردد. هر درخواست Ri که توسط Pi ارسال شده باشد دارای یک مجموعه همزمانی به نام CSeti است، که مجموعه آن “REQUEST” های Rj است که با Ri همزمان هستند. همچنین CSeti شامل Ri هم می‌شود.
همچنین، می‌دانیم که Ri، Ri، Rj}U{Ri} همگام است با CSeti = {Rj | Ri. مشاهده می کنید که رابطه “همگام است با” به صورت متقارن تعریف می‌گردد.
الگوریتم ارائه شده در ]۶۵[ همان مدل مورد استفاده در RA را در نظر می‌گیرد. همچنین فرض بر این است که کانال‌های شبکه از نوع FIFO می‌باشند. پروسه‌ای یک صف حاوی “REQUEST” ها را به ترتیب اولویت‌های دریافت شده توسط پروسه پس از ارسال آخرین “REQUEST” ایجاد می‌کند. این صف، که به آن صف درخواست‌های محلی ([۱۵۳]LRQ) گفته می‌شود، فقط حاوی “REQUEST” های همزمان است. الگوریتم جدید از پنج نوع پیغام استفاده می کند: “REQUEST”، REPLY، IN-REGION، AYA (Are You Alive)، NEWEPOACH، FLUSH، و بااختصاص هوشمندانه اهداف چندگانه به هر کدام به صرفه‌جویی دست می‌یابد. بالاخص، این صرفه‌جویی‌ها با مشاهدات کلیدی زیر به دست می‌آیند.
همه درخواست‌ها در کل مشابه الگوریتم RA بر اساس اولویت ترتیب‌دهی می‌شوند. یک پروسه دریافت کننده پیغام “REQUEST” می‌تواند به صورت آنی تعیین کند که آیا پروسه درخواست دهنده یا خودش باید اجازه ورود اول به منطقه بحرانی را داشته باشند یا خیر.
