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

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

از طرفی رشد تکنولوژی پردازنده ها نسبت به حجم محاسبات بسیار پایین است و نیز بخاطر محدودیت در تولید ابزار نیمه هادی سرعت پردازنده ها نیز دارای محدودیت می‌باشد.

از این رو استفاده از یک کامپیوتر به تنهایی پاسخگوی نیازهای محاسباتی نیست.

بنابراین استفاده از چند کامپیوتر برای انجام پردازش های موازی ضروری است.

از سوی دیگر به دلیل پیشرفتهای زیاد در زمینه شبکه های کامپیوتری و ابزار آن، روش جدیدی برای انجام محاسبات ارائه گردید که Network-based coputation نام دارد.

در حالت کلی کامپیوتر های موازی شامل واحدهای پردازش و حافظه مختلفی هستند.

و بحث مهم در طراحی و آنالیز سیستمهای موازی، روش اتصال اجزاء مختلف به یکدیگر می باشد بنابراین نحوه ارتباط شبکه است که کارائی کل سیستم را معین می‌کند.

امروزه طیف وسیعی از سیستمهای موازی موجود می باشد.

که بعضی از آنها به منظور کاربرد خاص و گروهی نیز به صورت استفاده همه منظوره هستند.

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

زیرا معماری های مختلف نیازهای مختلف را برآورده می‌سازند.

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

به این سیستم ها fault telorant گفته می شود.

تا کنون دسته بندی کامل و جامعی برای سیستمهای موازی ارائه نشده است: Flynn روشی برای این دسته بندی ارائه کرده که البته به طور کامل تمام سیستمها را تحت پوشش نمی گیرد.

سیستم دسته بندی Flynn براساس تعداد دنباله دستورالعملها و اطلاعات موجود در یک کامپیوتر می باشد که در اینجا منظور از دنباله یا Stream، رشته از دستورات یا اطلاعات است که توسط یک پردازنده پردازش می شود.

Flynn هر سیستم را بسته به تعداد دستورات و تعداد اطلاعات به یکی از چهار مجموعه زیر نسبت می دهد که در زیر توضیح مختصری از هر یک از آنها آمده است.

SISD: Sungle Instruction – Single Data SISD یک سری از کامپیوترهای سنتی از گروه Apple می باشد که در آن یک دستورالعمل از حافظه خوانده و اجرا می شود و از اطلاعات حافظه استفاده می کند و بعد دستورالعمل بعدی فراخوانی و اجرا می شود و به همین ترتیب ادامه می یابد این کلاس از کامپیوترها حدود چهار دهه مورد استفاده بوده و برنامه و نرم افزارهای فراوانی بر این اساس پایه گذاری شده است.

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

SIMD: Single Instruction – Multiple Data در این دسته از کامپویترها، یک واحد دستورالعمل، دستورات را به تعدادی از المانهای پردازش (PE) می فرستد و از آنجا که هر PE بر روی اطلاعات محلی خویش کار می کند در واقع تعداد زیادی از رشته اطلاعات وجود خواهد داشت مثلاً در روش ILLIAC IV یک واحد دستورات را به 64 واحد PE می رساند و هر کامپیوتر 2k بایت حافظه محلی دارد.

کامپیوترها در 8 ردیف 8 تایی قرار دارند (شکل P.1.7) که کامپیوترهای بالایی از سمت بالا به سمت پایین پائینیها متصلند همین طور کامپیوترهای سمت راست به سمت چپی ها متصلند.

در واقع هر PE از 4 جهت به بقیه متصل است: شمال، جنوب، شرق و غرب که به این روش گاهی شبکه NEWS هم گفته می شود.

از این روشها اغلب در حل معادلات دیفرانسیل جزئی و یا در پیش‌بینی وضع هوا استفاده می شود.

تعدادی از سیستمهای SIMD معروف از قرار زیر هستند: ICL DAP و ILLIAC IV MISD: Multiple Instruction – Multiple Data در کامپیوترهای این دسته، چندین واحد دستورالعمل، دستورات را به چندین واحد پردازش پخش می کنند.

این دسته خود شامل دو زیر شاخه مطرح Shared memory و Message passing می باشد در معماری Shared memory پردازنده ها توسط حافظه مشترک با یکدیگر ارتباط دارند.

در چنین سیستمهای چند پردازنده ای، شبکه اتصال داخلی باید به گونه ای باشد تا دسترسی هر پردازنده به تمام حافظه تضمین شود.

همچنین این شبکه باید به گونه ای باشد که در ارتباط پردازنده ها با حافظه برخوردی پیش نیاید و در واقع شبکه باید nonblocking باشد.

در معماری Distributed memory هر واحد پردازش دارای حافظه محلی متعلق به خویش است.

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

توپولوژی استاتیک: در جایی است که اتصالات اختصاصی بین پردازنده ها وجود دارد.

در قسمتهای بعد به مقایسه توپولوژیهای مختف خواهیم پرداخت.

ابتدا معیارهای توپولوژی را مانند تاخیر ارتباطی، هزینه اتصال، قابلیت اعتماد و عبور اطلاعات معرفی می شود.

ویژگیهای شبکه: مدل مناسب برای بررسی توپولوژی شبکه مالتی کامپیوترها گراف G=(V,E) می‌باشد که در آن V مجموعه گره ها است که نشان دهنده واحدهای پردازنده (PE) است و E مجموعه یال هاست که نشان دهنده ارتباطات بین واحدهای پردازنده می‌باشد.

با این روش ویژگیهای شبکه را می توان با تفسیر خصوصیات گراف ها تحلیل کرد که این روش یک روش ارزیابی استاتیک است زیرا بحثهایی از جنبه مسیریابی (routing) و غیره در نظر گرفته نمی شود این روش باری مقایسه شبکه ها بکار می رود و هزینه شبکه با تعداد یالها و تاخیر ارتباطی با تعداد یالها بین گره ها متناظر خواهد بود.

یکی از موضوعات مورد علاقه در شبکه کمترین زمان ارتباطی است که برای اندازه‌گیری آن باید به روش ارزیابی دینامیک عمل نمود زیرا در اینجا انتخاب مسیر و بحث روتینگ در زمان تاثیر دارد.

یکی دیگر از پارامترهای مهم در پردازشهای موازی قابلیت اعتماد و موجودیت اجزاء سیستم می باشد.

که این مورد را می توان با تعریف کارایی یک شبکه بیان کرد.

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

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

قابلیت توسعه یا امکان افزایش اجزاء شبکه، نکته قابل بررسی برای شبکه ها می‌باشد.

زیرا گاهی نیاز است بسته به بار پردازشی شبکه، اجزاء آن را تغییر داد و این تغییر باید به گونه ای باشد که نیازی به چیدمان مجدد برای قسمتهای باقیمانده نباشد.

3- بررسی اجمالی توپولوژیها بعضی از دسته بندیها (Fecng) توپولوژی های شبکه را بر طبق ابعاد مورد نیاز برای طرح ریزی مجزا می کنند.

Kotsis این دسته بندی را بر اساس ساختار بکار رفته در شبکه بنا نهاده است.

اولین دسته که استفاده از آن نیز ساده است شبکه های با ساختار ساده مانند ring، Line و Tree می باشد این متد این خانواده را Simple Connection Structures می نامد.

دسته دیگری از توپولوژیها، توپولوژیهای graphs on alphabets هستند که در آن آدرس گره ها کلمه هایی با طول خاص از حروف الفبا می باشند که یک زیر گروه از این خانواده Hypercube Structures ها هستند (شکل gk.1.3).

همچنین می تواند تئوری گروهها در آنها استفاده شود که به آنها Cayley Graphs گویند.

در بعضی از گرافهای ناکامل می توان تاخیر ارتباطی با اضافه کردن چند اتصال کاهش داد.

ابتدا با گرافهای rings و tree شروع می کنیم با گسترش اتصالات اضافی که براساس قاعده های متناسب با گره های منفصل اولیه انجام می شود مفهوم Generalized Chordal Rings شکل می گیرد با ادغام ساختارهای ساده می توان ساختارهای Combinational ساخت.

عملیات دیگری که می توان ساختار پیچیده‌تری ارائه دهد عملیات Boolean بر روی گرافهاست.

ویژگیهای توپولوژیها را می توان به صورت زیر بیان نمود: هزینه اتصالات، که با تعداد کل لینک ها بیان می شود.

تاخیر ارتباطات، که با قطر شبکه و فاصله میانگین بیان می شود.

تقارن و انظباط سادگی مسیریابی قابلیت گسترش 1-3- ساختارهای ارتباطی ساده Simple Connection Structures: Line L(N): سادهترین روش ارتباطی است.

این شبکه کمترین هزینه اتصالات و بیشترین تاخیر ارتباطات را دارا می باشد.

تلرانس خطا بسیار ضعیف است زیرا به راحتی ارتباط قطع می شود.

مسیریابی و قابلیت گسترش ساده ای دارد.

در کاربردهای خاص از آن استفاده می شود.

Ring C(N): در این شبکه ها قطر شبکه نصف و فاصله میانگین به 75% کاهش می‌یابد بنابراین تاخیر ارتباطی کاهش می یابد.

روتینگ و گسترش بسیار ساده هستند و تلرانس خطا نیز بهتر شده است.

البته اگر بین گره های یک رینگ ارتباط جدید بوجود آید بهبود زیادی حاصل می شود که شبکه های با توپولوژی Chardal Rings شکل می گیرد.

Completely Connected Network K(N): این شکبه ها دارای حداقل زمان ارتباطی و بهینه ترین تلرانس خطا می باشند البته پرهزینه‌ترین اتصال نیز از آن این روش می باشد.

Tree T(B,h): درختها دارای امکان گسترش خوبی هستند.

زمان تاخیر ارتباطی نسبتاً مناسبی دارند.

هزینه اتصالات نیز بسیار مناسب می باشد اما این شبکه ها، شبکه‌های نامنظم هستند و با افزایش دو درجه گراف غیرخطی افزایش می یابد.

نقطه ضعف اصلی درختها در تلرانس خطای ضعفیف می باشد.

البته ترافیک ارتباطی بالا در نودهای نزدیک به نود اصلی بسیار زیاد خواهد بود.

مسیریابی بسیار ساده می باشد.

Star S(N): این شبکه شبیه درختها می باشد.

تنها محدودیت آن در بالا بودن درجه نود میانی و ترافیک عبوری بسیار سنگین در این نود می باشد.

2-3- گرافهای الفبایی Graphs on Alphabets: در این متد ساختاری نودها با حروف الفبا به طول خاص شماره گذاری می شوند.

برای تمام این توپولوژیها می توان یک ساختار مسیریابی یکسان براساس مقایسه آدرسها بکار برد.

Odd Graphs OG(d): این نوع گرافها برای ساختارهایی است که تعداد زیادی نود با قطر و درجه پائین دارند.

امکان گسترش آنها رتبه هشتم را دارد.

هزینه اتصالات با افزایش درجه گراف بیشتر از خطی تغییر می کند.

De Bruijn Graph BG (n,b): این گرافها دارای روتینگ متوسط می باشند و افزایش نودها می تواند باعث افزایش درجه و یا افزایش قطر گردد.

این گراف در شکل (gk.3.3) آمده است.

Kautz Graph KG(n,b): این گراف همان گراف قبل است با این تفاوت که نودها هم حروف همسایه اند این گرافها امکان گسترش بیشتری نسبت به BG دارند.

Moebious Graph MG(n): این گرافها دارای درجه ثابت 3 هستند شکل 3.3 و نودها به صورت باینری و ساختار منظم حلقه نامگذاری می شوند.

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

در این گروه از شبکه ها گرافهای MG دارای کمترین هزینه و گرافهای OG دارای بیشترین هزینه می باشند اما مزیت گرافهای BG و KG در تقارن و منظم بودن آنهاست.

3-3- ساختارهای فوق مکعبی Hypercube Structures: این گروه در واقع از خانواده گرافها هستند اما به دلیل اهمیت بالایی که دارند به صورت جدا معرفی می شوند.

1-3-3- Binary Hypercube: تمام توپولوژی های این دسته دارای N=2n نود هستند و همگی روی یک Hypercube، n بعدی قرار دارند اما قاعده ارتباطی مختلف دارند که همین باعث تفاوت آنها در قطر شبکه و فاصله میانگین می شود.

تمام شبکه های با این توپولوژی ساختار منظم از درجه n دارند و همه آنها دارای تلرانس خطای بهینه هستند.

Boolean n-cube Q(n): پرکاربردترین و رایج ترین ساختار برای شبکه های داخلی مالتی کامپیوترها است و این به دلیل منظم و متقارن بودن و قدرت بالای آن در بکار انداختن موازی سازی است.

گروهی از شبکه های پردازشی امروزه با این سیستم کار می کنند.

این ساختار به خاطر داشتن زمان تاخیر ارتباطی مورد توجه قرار می گیرد و البته اگر از جنبه هزینه به آن نگاه کنیم خیلی مورد علاقه نیست.

مسیریابی در این شبکه ها فقط به آدرس ابتدا و انتها نیاز دارد برای کاهش قطر می توانیم سیستم را از تقارن در آوریم.

Twisted Cube TQ(n): با انجام یک عملیات تابانیدن بین دو نود غیر ارتباطی دارای کوتاهترین مسیر در سیستمهای Boulean بدست می آید که باعث کاهش در قطر شبکه می گردد که البته این کار باعث از بین رفتن تقارن شبکه و مشکل تر شدن مسیریابی می گردد (شکل 3.4).

Multiply – Twisted Cube MQ(n): این سیستم از سیستم Twisted قطر کمتری دارد و البته الگوریتم مسیریابی آن مشکل تر می شود و می بایست کوتاهترین مسیر شناسایی گردد.

بزرگترین اشکال تمامی ساختارهای Binary Hypercube این است که با افزایش سایز شبکه درجه گراف کاهش می یابد که این باعث ضعف قابلیت گسترش می‌گردد.

MQ دارای