مقاله درباره تحلیل الگوریتم شاخه و قید موازی آسنکرون

اختصاصی از یاری فایل مقاله درباره تحلیل الگوریتم شاخه و قید موازی آسنکرون دانلود با لینک مستقیم و پر سرعت .

لینک پرداخت و دانلود در "پایین مطلب"

 فرمت فایل: word (قابل ویرایش و آماده پرینت)

 تعداد صفحات:51

 خلاصه:

در این مقاله توضیحی درباره کامپیوترهای موازی می‌دهیم و بعد الگوریتمهای موازی را بررسی می‌کنیم. ویژگیهای الگوریتم branch & bound را بیان می‌کنیم و الگوریتمهای b&b موازی را ارائه می‌دهیم و دسته‌ای از الگوریتمهای b&b آسنکرون برای اجرا روی سیستم MIMD را توسعه می‌دهیم. سپس این الگوریتم را که توسط عناصر پردازشی ناهمگن اجرا شده است بررسی می‌کنیم.

نمادهای perfect parallel و achieved effiency را که بطور تجربی معیار مناسبی برای موازی‌سازی است معرفی می‌کنیم زیرا نمادهای قبلی speed up (تسریع) و efficiency (کارایی) توانایی کامل را برای اجرای واقعی الگوریتم موازی آسنکرون نداشتند. و نیز شرایی را فراهم کردیم که از آنومالیهایی که به جهت موازی‌سازی و آسنکرون بودن و یا عدم قطعیت باعث کاهش کارایی الگوریتم شده بود، جلوگیری کند.

2- معرفی:

همیشه نیاز به کامپیوترهای قدرتمند وجود داشته است. در مدل سنتی محاسبات، یک عنصر پردازشی منحصر تمام taskها را بصورت خطی (Seqventia) انجام میدهد. به جهت اجرای یک دستورالعمل داده بایستی از محل یک کامپیوتر به محل دیگری منتقل می‌شد، لذا نیاز هب کامپیوترهای قدرتمند اهمیت روز افزون پیدا کرد. یک مدل جدید از محاسبات توسعه داده شد، که در این مدل جدید چندین عنصر پردازشی در اجرای یک task واحد با هم همکاری می‌کنند. ایده اصل این مدل بر اساس تقسیم یک task به subtask‌های مستقل از یکدیگر است که می‌توانند هر کدام بصورت parallel (موازی) اجرا شوند. این نوع از کامپیوتر را کامپیوتر موازی گویند.

تا زمانیکه این امکان وجود داشته باشد که یک task را به زیر taskهایی تقسیم کنیم که اندازه بزرگترین زیر task همچنان به گونه‌ای باشد که باز هم بتوان آنرا کاهش داد و البته تا زمانیکه عناصر پردازشی کافی برای اجرای این sub task ها بطور موازی وجود داشته باشد، قدرت محاسبه یک کامپیوتر موازی نامحدود است. اما در عمل این دو شرط بطور کامل برقرار نمی‌شوند:

اولاً: این امکان وجود ندارد که هر taskی را بطور دلخواه به تعدادی زیر task‌های مستقل تقسیم کنیم. چون همواره تعدادی زیر task های وابسته وجود دارد که بایستی بطور خطی اجرا شوند. از اینرو زمان مورد نیاز برای اجرای یک task بطور موازی یک حد پایین دارد.

دوماً: هر کامپیوتر موازی که عملاً ساخته می‌شود شامل تعداد معینی عناصر پردازشی (Processing element) است. به محض آنکه تعداد taskها فراتر از تعداد عناصر پردازشی برود، بعضی از sub task ها بایستی بصورت خطی اجرا شوند و بعنوان یک فاکتور ثابت در تسریع کامپیوتر موازی تصور می‌شود.

الگوریتمهای B&B مسائل بهینه سازی گسسته را به روش تقسیم فضای حالت حل می‌کنند. در تمام این مقاله فرض بر این است که تمام مسائل بهینه سازی مسائل می‌نیمم کردن هستند و منظور از حل یک مسئله پیدا کردن یک حل ممکن با مقدار می‌نیمم است. اگر چندین حل وجود داشته باشد، مهم نیست کدامیک از آنها پیدا شده.

الگوریتم B&B یک مسئله را به زیر مسئله‌های کوچکتر بوسیله تقسیم فضای حالت به زیر فضاهای (Subspace) کوچکتر، تجزیه می‌کند. هر زیر مسئله تولید شده یا حل است و یا ثابت می‌شود که به حل بهینه برای مسئله اصلی (Original) نمی‌انجامد و حذف می‌شود. اگر برای یک زیر مسئله هیچ کدام از این دو امکان بلافاصله استنباط نشود، آن زیر مسئله به زیرمسئله‌های کوچکتر دوباره تجزیه می‌شود. این پروسه آنقدر ادامه پیدا می‌کند تا تمام زیر مسئله‌های تولید شده یا حل شوند یا حذف شوند.

پاورپوینت درباره موازی سازی

اختصاصی از یاری فایل پاورپوینت درباره موازی سازی دانلود با لینک مستقیم و پر سرعت .

فرمت فایل :powerpoint (لینک دانلود پایین صفحه) تعداد صفحات 24 صفحه

•سرعت بالاتر(حل سریع مسائل)

•پیش بینی هوا

•خط مرگ نرم و سخت

•گذردهی بالاتر(حل مسائل بیشتر)

•پردازش تراکنش ها

•قدرت محاسباتی بالاتر(حل مسائل طولانی)

•پیش بینی هوا برای یک هفته در کمتر از 24 ساعت

 

 

GFLOPS on desktop: Apple Macintosh, with G4 processor

TFLOPS in supercomputer center: 

   1152-processor IBM RS/6000 SP (switch-based network)

   Cray T3E, torus-connected

PFLOPS on drawing board: 

   1M-processor IBM Blue Gene (2005?)

   32 proc’s/chip, 64 chips/board, 8 boards/tower, 64 towers

   Processor: 8 threads, on-chip memory, no data cache

   Chip: defect-tolerant, row/column rings in a 6 ´ 6 array

   Board: 8 ´ 8 chip grid organized as 4 ´ 4 ´ 4 cube

   Tower: Boards linked to 4 neighbors in adjacent towers

   System: 32´32´32 cube of chips, 1.5 MW (water-cooled)

تحقیق درباره پورت سریال و موازی

اختصاصی از یاری فایل تحقیق درباره پورت سریال و موازی دانلود با لینک مستقیم و پر سرعت .

فرمت فایل : WORD (لینک دانلود پایین صفحه) تعداد صفحات 11 صفحه

مقدمه

 پورت سریال یکی از متداولترین روش های موجود جهت اتصال یک دستگاه به کامپیوتر است . با اینکه سیستمهای جدیدتر سعی در استفاده محدود از پورت سریال را داشته و پورت USB را مورد توجه بیشتر قرار می دهند ولی همچنان دستگاه های متعددی نظیر مودم  از پورت سریال استفاده می نمایند. پورت های سریال یک کانکتور استاندارد و یک پروتکل را به منظور اتصال دستگاههائی نظیر مودم به کامپیوتر ، ارائه می نمایند. اغلب کامپیوترها دارای دو پورت سریال می باشند.

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

پاورپوینت با عنوان پردازش موازی و خط لوله در رایانه (Pipeline) در 65 اسلاید

اختصاصی از یاری فایل پاورپوینت با عنوان پردازش موازی و خط لوله در رایانه (Pipeline) در 65 اسلاید دانلود با لینک مستقیم و پر سرعت .

رای اجرای دستورالعمل‌ها در پردازنده ابتدا فرض را بر این می‌گیریم که هر دستور در یک سیکل انجام می‌شود. یعنی در یک سیکل، فقط یک دستورالعمل در مسیر داده حرکت می‌کند. سپس ایده ی pipeline(خط لوله) را برای کارایی بیشتر پردازنده ارائه میدهیم. ابتدا کارمان را با طرح یک مثال آغاز میکنیم.فرض کنید میخواهید تعدادزیادی لباس را شسته، خشک کرده و در محلشان قرار دهید.پس ابتدا لباسها را در لباسشویی قرار داده تا شسته شوند، سپس آنها را از لباسشویی خارج کرده و در خشک کن قرار میدهید و پس از خشک شدن، از خشک کن خارج کرده و در مرحله ی بعد، در محلشان قرار میدهید.و باز به سراغ سری بعدی لباسها رفته و برای آنها نیز این مراحل را تکرار میکنید. روش دیگر برای شستن تعداد زیاد لباس این است که در ابتدا تعدادی لباس را در لباسشویی قرار داده و پس از شسته شدن، آنها را از لباسشویی خارج کرده ودر خشک کن قرار میدهیم، منتهی از سوی دیگر، تعدادی لباس دیگر را وارد لباسشویی(که فعلاً بیکار است)می کنیم.اینطور در زمانمان صرفه جویی میکنیم(از وقتهای مرده ی هر مرحله استفاده میکنیم). حال به پردازنده باز میگردیم تا ربط مثال فوق، مشخص شود.روش اول، معادل آن است که هر دستور، تنها در یک سیکل انجام شود واز آنجا که در یک سیکل، داده ها از عناصر موجود در مسیر داده تنها یک بار میگذرند پس در قسمتی از سیکل، بعضی عناصر داده بی مصرف میمانند. استفاده از روش دوم معادل آن است که در هر سیکل، علاوه بر آنکه یک دستور، اجرا شده ودر طول سیکل، از مسیر داده عبور می‌کند، به دنبال آن بقیه دستورها وارد مسیر داده شوند که در اینصورت، در یک سیکل، تعداد بیشتری از عناصر داده شده استفاده میشوند و در نتیجه، سرعت و کارآیی بهبود می یابند. پس pipeline، مجموعه ای از عناصر(مراحل) پردازش داده است که بصورت سری به یکدیگر متصلند و ورودی هر عنصر، خروجی عنصر قبلی است. در تکنیک pipelinee، چند دستور میتوانند در یک زمان اجرا شوند.یعنی دستورات از لحاظ زمان اجرا دارای همپوشانی هستند.

در مثال فوق، مراحل ما سه گانه بودند(شستن، خشک کردن، تا کردن و در محل قرار دادن) اما در پردازنده های مختلف، تعداد مراحل، متفاوت است.

مثلاً در پردازنده های ARM و MIPS تعدادمراحل، ۵ است که شامل موارد زیر است:

1. fetch:بیرون کشیدن دستورالعمل از حافظه.
2. decode:خواندن دستور العمل(برای فهمیدن نوع دستورالعمل) و تشخیص registerهای مورد نیاز.
3. execute:انجام محاسبات مانند محاسبه ی آدرس پرش، جمع، تفریق و...(بسته به نوع دستور).
4. memory:دستیابی به حافظه(مثلاً برای نوشتن یا خواندن داده).
5. write back:بازنویسی نتیجه(نتیجه ی محاسبات یا خواندن از حافظه)در register.

گاهی در پردازش به صورت خط لوله اتفاقاتی رخ می دهد که باعث می شود دستور بعدی برای پردازش آماده نباشد.به این اتفاقات، مخاطره گفته می شود.

مخاطرات خط لوله

با توجه به اتفاقاتی که برای دستوربعدی (که میخواهد وارد خط لوله شود)می افتد، مخاطرات به سه دسته تقسیم می شوند:

1. مخاطرات ساختاری
2. مخاطرات داده ای
3. مخاطرات کنترلی

مخاطرات ساختاری

فرض کنید دو مرحله از خط لوله ی ما فقط قابل استفاده در یک مرحله بود.مثلاً در مثال لباسشویی خشک کن و شستن لباس در یک مرحله انجام میشد.در اینصورت در این مرحله فقط یک دستور می تواند به یکی از این دو دسترسی داشته باشد و این باعث به وجود آمدن تاخیر در خط لوله می شود، چرا که بجای آنکه دو دستور در یک پالس ساعت یک گام جلو روند باید صبر کنیم تا یکی جلو رود و در پالس ساعت بعدی دیگری وارد این مرحله شود.

مثالی از این نوع مخاطره وجود یک حافظه برای دستورالعمل و داده بجای دو حافظه برای این دو است.وقتی یک حافظه داشته باشیم نمیتوان در یک پالس ساعت هم از حافظه واکشی دستور داشته باشیم وهم داده از آن بگیریم در نتیجه مرحله یک و چهار بصورت همزمان نمی‌توانند اجرا شوند.در صورت بروز این نوع مخاطره، برای رفع مشکل از روش تعلیق(حباب انداختن)استفاده می کنیم که در مباحث آتی به آن خواهیم پرداخت.

مخاطرات داده‌ای

این مخاطره در صورتی رخ می دهد که داده ی مورد نیاز، که در دستور یا دستورات قبلی تهیه می شده، آماده نباشد.در صورت بروز این نوع مخاطره، بسته به نوع ایجاد آن به چند روش می توان مشکل را رفع کرد:

• تعلیق
• پیش فرستادن
• تغییر ترتیب کد اسمبلی برنامه

فهرست:

پردازش موازی

خط لوله

تصویر کلی

مسیر داده

کنترل

هازاردهای داده

توقف خط لوله

ارسال به جلو

هازاردهای کنترلی

استثناها

کد پیاده سازی مقایسه کارایی اجرای سریال و موازی الگوریتم بهینه سازی کلونی مورچگان برای حل مسئله فروشنده دوره‌گرد با متلب

اختصاصی از یاری فایل کد پیاده سازی مقایسه کارایی اجرای سریال و موازی الگوریتم بهینه سازی کلونی مورچگان برای حل مسئله فروشنده دوره‌گرد با متلب دانلود با لینک مستقیم و پر سرعت .

این برنامه با استفاده از مقاله Performance Comparison of Sequential and Parallel
Execution of the Ant Colony Optimization Algorithm
for Solving the Traveling Salesman Problem پیاده سازی شده است ./

کد برنامه پیاده سازی مقاله امقایسه کارایی اجرای سریال و موازی الگوریتم بهینه سازی کلونی مورچگان برای حل مسئله فروشنده دوره‌گرد با استفاده از متلب نوشته شده در اختیار شما قرار داده می شود . به همراه کد توضیحات کامل کد و آموزش کامل اجرای برنامه  در اختیار شما قرار داده خواهد شد ./

توجه : ترجمه مقاله ای که پیاده سازی بر اساس ان انجام شده در سایت و اینجا موجود است / 

مقاله اصلی را به زبان انگلیسی می توانید رایگان از اینجا دریافت کنید . /

چکیده

پیش زمینه: گسترش انفجاری داده های زیست شناسی در سال های اخیر چالشی بزرگ برای الگوریتم های خوشه بندی سنتی بوجود آورده است. با افزایش مقیاس مجموعه داده ها، به حافظه های بزرگتر و زمان اجراهای طولانی تری برای مسایل شناسایی خوشه نیاز است. الگوریتم انتشار همریشگی (affinity propagation) عملکردی بهتر از بسیاری دیگر از الگوریتم های کلاسیک خوشه بندی دارد و بصورت گسترده در پژوهش های زیست شناسب بکار گرفته می شود. با این حال به هنگام پرداختن به مجموعه داده های دارای مقیاس بزرگ پیچیدگی زمانی و فضایی به تنگنا و محدودیت عمده ای تبدیل می شود. با این حال ماتریس شباهت که رویه های ساختن آن زمان اجرای زیادی می طلبد، پیش از اجرای الگوریتم انتشار همریشگی مورد نیاز است، چرا که این الگوریتم مجموعه داده ها را بر پایه ی مجموعه شباهت میان جفت داده ها خوشه بندی می کند./1005/

پس از خرید از درگاه امن بانکی لینک دانلود در اختیار شما قرار میگیرد و همچنین به آدرس ایمیل شما فرستاده میشود.

تماس با ما برای راهنمایی آدرس ایمیل:

[e-mail]

شماره جهت ارتباط پیامکی :

09337843121

توجه: اگر کارت بانکی شما رمز دوم ندارد، در خرید الکترونیکی به مشکل برخورد کردید و یا به هر دلیلی تمایل به پرداخت الکترونیکی ندارید با ما تماس بگیرید تا راههای دیگری برای پرداخت به شما پیشنهاد کنیم.