تحليل أداء خوارزميات التوجيه الخالية من الجمود في شبكات الشرائح ثنائية الأبعاد

الملخص

في هذا المقال يتم مناقشة تفاصيل بعض الخوارزميات التي تمتلك خاصية deadlock-free أي خوارزميات خالية من الجمود. إن الخوارزميات الخالية من الجمود هي خوارزمية XY (ذات التوجيه الحتمي)، التوجيه الفردي الزوجي Odd Even Routing (ذات التوجيه التكيفي القائم على نموذج الدوران)، خوارزميات الغرب أولاً West first، الشمال أخيراً North Last والسلبي أولاً Negative First (وهي تكيفية جزئياً ذات توجيه قائم على نموذج الدوران) و DyXY (ذات توجيه تكيفي ذو مسار أصغري). وبعد مقارنة أدائهم في أنماط حركة المرور المختلفة من خلال تطبيق أحمال مختلفة للشبكة، تبين أن DyXY تؤدي أفضل أداء لكنها ذات استهلاك طاقة اعلى. كما ان خوارزمية الشمال أخيراً تؤدي أفضل أداء بين خوارزميات التوجيه التكيفية جزئياً. كما أن خوارزمية XY الأكثر كفاءة في استخدام الطاقة.