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

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

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

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

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

از سوی دیگر به دلیل پیشرفتهای زیاد در زمینه شبکه های کامپیوتری و ابزار آن، روش جدیدی برای انجام محاسبات ارائه گردید که 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 دارای کمترین زمان تاخیر ارتباطی است که البته پیچیدگی مسیریابی در آن مقداری بیشتر می گردد.

2-3-3- Generilized Binary Hypercube: ساختارهای Boolean به خاطر داشتن قطر کم و میانگین فاصله کوتاه مورد توجه قرار دارند.

اما شکل کلی افزایش درجه گراف با می باشد.

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

Cube – Connected – Cycles CCC(n): شکل (5-3) نشان دهنده ساختار بازگشتی این شبکه ها است.

هر نود با دو آدرس نود و رینگ شناخته می شود.

شبکه های CCC یک شبکه منظم با درجه 3 و گره‌های متقارن می باشند.

مسیریابی با مقایسه آدرس مبدا و مقصد انجام می گیرد.

در این شبکه‌ها می توان N گره اضافه نمود بدون اینکه قطر سیستم افزایش یابد.

Generalized Boolean n – Cube GQ(R,n): در این شبکه ها دیگر یک trade off بین قطر و درجه وجود ندارد.

این ساختار یک ساختار کاملاً متقارن گره ای می باشد و بیشترین Connectivity را ارائه می کند.

3-3-3- Variation of W : این سیستم ها نیز قابلیت افزایش تعداد گره ها بدون بالا رفتن درجه را داراست.

این نوع شبکه ها بسته به قاعده اتصال نودها به دو دسته تقسیم می شوند.

Mesh M(w,n): این ساختار یک ساختار نامنظم است زیرا گره های کناری درجه کمتری نسبت به گره‌های داخلی دارند.

این سیستم دارای الگوریتم مسیریابی شبیه به Boolean‌ها است.

W-ary n – Cube HC(w,n): این ساختار شبیه Boolean است با این تفاوت که بجای آدرس باینری نودها سیر منشا W استفاده می شود.

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

توپولوژی منظم و متقارن گره ای است.

Generalized Hypercube این ساختار منظم و متقارن است.

این شبکه دارای تلرانس خطای پائین است.

الگوریتم مسیریابی نقطه به نقطه و الگوریتم پخشی تک مبدا Single–Source Broodcast استفاده می شود.

4-3- Cayley Graphs: این گرافها دارای قابلیت بسیار بالا در تغییر ساختار شبکه بندی داخلی می باشند.

این گرافها، ساختارهای با اتصال بالا هستند.

تقارن گره ای وجود دارد و هر گره به خودش وصل نمی شود.

ساختار مسیریابی در این نوع گرافها شامل مرتب کردن یک تغییر مفروض (آدرس مبدا) نسبت به دیگری (آدرس مقصد) می باشد.

ساختار Boolean نیز از این گروه می تواند باشد.

انواع این گرافها بسته به عمل تغییر آنها می‌تواند به صورت زیر باشد.

Swaps: یکی از تغییرات Swap یا جانشین سازی است که دو سمبل را با یکدیگر جابجا می‌کند.

که گرافهای Star Graph SG(n) و Bubble Sort Graph BSG(n) از این دسته اند.

Flips: گرافهای Pancake Graph PG(n) از این دسته اند که ساختار مسیریابی ساده‌ای دارند.

Cyclic Shifts: این گرافها با یک شیفت دایره ای بدست می آید که البته با ترکیب Swap و Shift می توان ساختارهای جالبی بدست آورد.

گرافهای Cayley دارای مزیت تقارن می باشد که این به معنای مسیریابی راحت می‌باشد.

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

خصوصیات دیگر آنها بهینه بودن تلرانس خطا است.

گرافهای SOS دارای هزینه کمتری هستند و در عواض گرافهای SG و Pancake قطر کوچکتر دارند.

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

5-3- Additional Links: اگر یک ساختار مفروض در نظر گرفته شود با اضافه کردن چند اتصال می توان تاخیر ارتباطی را کاهش داد و نیز تلرانس خطا را بهبود بخشید و البته فقط هزینه بالاتر می رود.

از این شبکه ها می توان Hypertree HT(n) را نام برد که تغییر یافته درخت ساده می‌باشد و مبنای ایجاد آن در کاهش قطر سیستم است البته هزینه بالاتر می رود و البته تاخیر ارتباطی آن کاهش و تلرانس خطا نیز بهبود می یابد و الگوریتم مسیریابی آن ترکیبی از مسیریابی درخت باینری و هایپرکیوبهاست که قابلیت یافتن کوتاهترین مسیر بین هر دو نقطه را داراست.

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

از ساختارهای دیگر Sneptree ST(h) است که بهبود نسبی را نسبت به درخت باینری داراست.

Chardal Ring CR(w) نیز از این دسته است که با تغییر شبکه حلقه ای ساده بدست می آید.

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

با کمی تغییر در ساختار این شبکه ها، شبکه Extended Choral Ring ECR(w) بدست می آید که ساختاری منظم و متقارن از درجه P دارند.

توپولوژیهایی دیگری مانند Double-Chordal Ring DCR(w1,w2)، Banyan Hypercube BQ(h,n,s)، Minimum Distance Mesh With Wrap aroud Links MDMW(N)، Folded Hypercube FQ(n) از این دسته اند.

6-3- Generalized Chordal Rings: این ساختارها دارای بازه تغییرات وسیعی در قطر شبکه و میانگین فاصله و دیگر پارامترها هستند مسیریابی این شبکه ها بیشتر به روش نقطه به نقطه انجام می شود که Arden آن را ارائه کرده است گروهی از این گرافها، گرافهای چرخشی هستند که دارای ساختار منظم می باشند.

7-3- Combinational of Basic Modules: این گرافها با ترکیب گرافهای نامنظم با هم بدست می آیند که گره های یا درجه کوچک را به هم متصل می سازد و یک ساختار منظم بدست آورد و اغلب درختها به عنوان ساختار اولیه بکار می روند.

متدهای مختلفی برای ترکیب وجود دارد که Merging Methods و Linking Methods از آن جمله اند.

تمام ساختارهای این دسته منظم می باشند.

توپولوژی های Hypernets اغلب برای شبکه های بزرگ بکار می روند و این بخاطر ساختار سلسله مراتبی آنهاست و شبکه Torus برای شبکه های کوچک (N شبکه های Torus و D-tress دارای زمان تاخیر ارتباطی پایین قابل ملاحظه ای هستند.

8-3- Boolean Operations on Graphs: این توپولوژیها حاصل اعمال بولین بر روی دو گراف هستند که این اعمال عبارتنداز: Conjunction، Disjunction، Symmetric Difference، Rejection، Cartesian Product، Generalized Product و Composition.

در میان اعمال بالا Composition و Conjunction دارای بیشترین هزینه می‌باشند و Rejection دارای کمترین هزینه است به نظر می رسد حاصلضرب عمومی به عنوان بهترین انتخاب باشد زیرا می تواند با انتخاب تابع مناسب قطر شبکه را کاهش داد.

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

9-3- Random Graphs: این گرافها حاصل تجربیات احتمالی می باشد.

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

نتایج نشان می دهد که ساختارهای احتمالی شبکه های کلاسیک چون درختها و Hypercubs و مانند آنهارا اجرا نمی کند.

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

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

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

این دو فاکتور عبارتند از هزینه سیستم (Connection Costs) که با تعداد کل اتصالات رابطه دارد و تاخیر ارتباطی (Communication Delay) که با قطر سیستم رابطه دارد.

در جدول زیر این توپولویژها با هم مقایسه شده اند.

در این مقایسه موارد زیر در نظر گرفته شده اند.

1- نظم (Regularity): این معیار با علائم زیر مشخص شده است: + سیستم منظم می باشد.

- سیستم نامنظم می باشد.

2- تقارن (Symmetry): با علائم زیر نشان داده شده است.

++ نشان دهنده یک ساختار کاملاً متقارن است.

+ نشان دهنده ساختاری است که تقارن آن بسیار عالی است.

0 نشان دهنده ساختار نسبتاً متقارن است.

- نشان دهنده ساختار نامتقارن یا دارای تقارن بسیار کم است.

3- قابلیت گسترش (Extensibility): با علائم زیر مشخص شده است.

++ برای سیستمهایی است که دارای قابلیت گسترش نوع اول type1 هستند به عبارت دیگر توپولوژی هر سه ویژگی مطلوب را برای گسترش دارا می باشد.

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

(types 2,3,5) 0 نشان دهنده توپولوژیهایی است که تنها یکی از آنها را برآورده می سازد.

(types 4,6,7) - برای توپولوژیهایی است که هیچیک از سه خصوصیت را دارا نباشد.

(type 8) 4- الگوریتم مسیریابی (Routing Algorithm): ++ برای توپولوژیهایی است الگوریتم مسیریابی type1 دارند به عبارت دیگر توپولوژی هر سه ویژگی مطلوب را برای مسیریابی دارا می باشد.

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

(types 2,3,5) 0 نشان دهنده توپولوژیهایی است که تنها یکی از ویژگیها را برآورده سازد.

(types 4,6,7) - برای توپولوژیهایی است که هیچیک از سه ویژگی را دارا نباشند.

(type 8) فصل 5: Routing in Network در هنگام اجرای پردازش موازی با سیستم چند کامپیوتره، واحدهای پردازش باید اطلاعات خویش را مبادله کنند که برای این کار نیاز عملی به نام مسیریابی (Routing) می باشد.

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

Point-to-point routing: یک نود قصد ارسال پیام به نود دیگر را دارد.

Broadcasting: یک نود (که موسس نامیده می شود) پیامی را برای بقیه پخش می کند.

Gossiping: هر کدام پیغامی را برای بقیه می فرستد در حالی که همزمان از بقیه پیغام دریافت می کند.

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

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

ابتدا ساختار عمومی مسیریابی (topology independent) و استراتژیهای مختلف آن را بررسی می کنیم و بعد این ساختار را برای توپولوژیهای مختلف (topology dependent) تعمیم می دهیم.

در تمام مسائل ارتباطی موضوع اولیه مورد بحث زمان ارتباط بین هر نود با همسایه‌اش است.

که این زمان به چند چیز بستگی دارد: زمان مورد نیاز برای برقراری ارتباط بین نودها (startup time)، پهنای باند این ارتباط و اندازه پیام.

اگر فرض کنیم تمام خطوط پهنای باند یکسان و زمان برقراری ارتباط یکسان داشته باشند ارسال یک پیام با اندازه M بین دو نود همسایه به زمان نیاز خواهد داشت حال اگر اندازه پیامها نیز یکسان در نظر گرفته شود.

این زمان به عنوان یک واحد ثابت می تواند بکار رود.

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

پس برای اینکه این ارتباط کمترین زمان را بگیرد نیاز به آن است که الگوریتمهای مسیریابی بر پایه یافتن کوتاه‌ترین مسیر طرح ریزی شوند.

در توپولوژیهایی که کاملاً متقارن است و شبکه دارای یک پیکربندی واضح و روشن است می توان مسیریابی را به راحتی با برقراری یک درخت ارتباطی انجام داد.

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

در شبکه هایی که ارتباط به صورت دینامیک می باشد، لینک های ارتباطی بین نودها ثابت نیستند و در حال تغییر می باشند.

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

بلکه در هر لحظه در راه انتقال بسته از هر واحد پردازنده (نود) که عبور می کند باید مسیر بعدی توسط آن واحد تعیین گردد و این کار نیاز به یک مسیریابی دینامیک پله به پله و کاملاً متغیر دارد و بررسی برخوردها و ارزیابی ترافیک از دیگر مسائلی است که به میان می آید و بررسی این سیستم ها مشکل تر می کند.