التوجيه (أتمتة التصميم الإلكتروني)

في تصميم الإلكترونيات ، يُعدّ توجيه الأسلاك ، أو ما يُعرف اختصارًا بالتوجيه ، خطوةً أساسيةً في تصميم لوحات الدوائر المطبوعة (PCBs) والدوائر المتكاملة (ICs). ويعتمد هذا التوجيه على خطوة سابقة تُسمى التموضع ، والتي تُحدد موقع كل عنصر فعّال في الدائرة المتكاملة أو المكوّن على لوحة الدوائر المطبوعة. بعد التموضع، تُضيف خطوة التوجيه الأسلاك اللازمة لتوصيل المكوّنات الموضوعة بشكل صحيح، مع مراعاة جميع قواعد تصميم الدائرة المتكاملة. وتُعرف خطوتا التموضع والتوجيه معًا في تصميم الدوائر المتكاملة باسم " التموضع والتوجيه" .

مهمة جميع أجهزة التوجيه واحدة. تُزوَّد هذه الأجهزة بمضلعات موجودة مسبقًا تتكون من دبابيس (تُسمى أيضًا أطرافًا) على خلايا، وبعض العوائق التي لا يمكن توجيه الأسلاك من خلالها، وربما بعض الأسلاك الموجودة مسبقًا والتي تُسمى مسارات مسبقة. يرتبط كل دبوس بشبكة ، عادةً بالاسم أو الرقم. تتمثل المهمة الأساسية لجهاز التوجيه في إنشاء أشكال هندسية بحيث تكون جميع الأطراف المخصصة لنفس الشبكة متصلة، ولا تكون أي أطراف مخصصة لشبكات مختلفة متصلة، ويتم الالتزام بجميع قواعد التصميم. قد يفشل جهاز التوجيه في توصيل الأطراف التي يجب توصيلها (دائرة مفتوحة)، أو عن طريق توصيل طرفين عن طريق الخطأ لا يجب توصيلهما (دائرة قصيرة)، أو عن طريق إحداث انتهاك لقاعدة من قواعد التصميم. بالإضافة إلى توصيل الشبكات بشكل صحيح، يُتوقع من أجهزة التوجيه أيضًا التأكد من أن التصميم يفي بمتطلبات التوقيت، ولا يعاني من مشاكل التداخل ، ويلبي أي متطلبات لكثافة المعدن، ولا يعاني من تأثيرات الهوائي ، وما إلى ذلك. هذه القائمة الطويلة من الأهداف المتضاربة في كثير من الأحيان هي ما يجعل التوجيه صعبًا للغاية.

من المعروف أن معظم مشاكل التوجيه غير قابلة للحل . أبسط مشكلة توجيه، وهي مشكلة شجرة شتاينر ، التي تتمثل في إيجاد أقصر مسار لشبكة واحدة في طبقة واحدة دون عوائق أو قواعد تصميم، تُصنف ضمن فئة NP-complete ، سواءً في حالة السماح بجميع الزوايا أو في حالة اقتصار التوجيه على الأسلاك الأفقية والرأسية فقط. ^{[ 1 ]} كما ثبت أن أنواعًا مختلفة من توجيه القنوات تُصنف أيضًا ضمن فئة NP-complete، ^{[ 2 ]} بالإضافة إلى التوجيه الذي يقلل من التشويش المتبادل ، وعدد الوصلات الرأسية ، وما إلى ذلك. حتى قبل إثبات أن مشاكل التوجيه تُصنف ضمن فئة NP-complete، كانت صعوبة إيجاد الحلول المثلى واضحة. لذلك، تعتمد جميع الخوارزميات تقريبًا على طرق استدلالية ، لا تسعى إلى الحل الأمثل، بل إلى حل "جيد بما فيه الكفاية". ^{[ 3 ]}

تختلف قواعد التصميم أحيانًا اختلافًا كبيرًا من طبقة إلى أخرى. ففي الدوائر المتكاملة ذات الطبقات المعدنية المتعددة، على سبيل المثال، قد يكون العرض والمسافة المسموح بهما في الطبقات السفلية أصغر بأربع مرات أو أكثر من العرض والمسافة المسموح بهما في الطبقات العلوية. وهذا يُضيف العديد من التعقيدات الإضافية التي لا تواجهها أجهزة التوجيه في تطبيقات أخرى، مثل تصميم لوحات الدوائر المطبوعة أو الوحدات متعددة الرقائق . وتبرز صعوبات خاصة إذا لم تكن القواعد مضاعفات بسيطة لبعضها البعض، وعندما يتعين على الوصلات المرورية أن تعبر بين طبقات ذات قواعد مختلفة.

كانت أقدم أنواع موجهات EDA تُعرف باسم "الموجهات اليدوية"، حيث كان المصمم ينقر بالماوس على نهاية كل جزء من كل شبكة. أما برامج تصميم لوحات الدوائر المطبوعة الحديثة، فتُوفر عادةً "موجهات تفاعلية"، حيث يختار المصمم موضعًا وينقر على عدة نقاط لتحديد المسار المطلوب، ثم تحاول الأداة وضع الأسلاك بالقرب من هذا المسار قدر الإمكان دون مخالفة قواعد التحقق من التصميم (DRC). تتضمن بعض الموجهات التفاعلية الأكثر تطورًا ميزات "الدفع والإزاحة" (المعروفة أيضًا باسم "الإزاحة الجانبية" أو "التحريك التلقائي")، حيث تقوم الأداة بإزاحة الشبكات الأخرى، إن أمكن، لوضع سلك جديد في المكان الذي يريده المصمم مع تجنب مخالفة قواعد التحقق من التصميم. كما تُوفر برامج تصميم لوحات الدوائر المطبوعة الحديثة عادةً "موجهات تلقائية" تقوم بتوجيه جميع الوصلات المتبقية غير الموجهة دون تدخل بشري.

تستخدم الدوائر المتكاملة الحديثة عادةً التوجيه التلقائي بالكامل، نظرًا لكثرة المسارات التي يصعب توجيهها يدويًا. إذا لم يُسفر التوجيه التلقائي عن حلٍّ كامل، فإن الحل الشائع هو تغيير موضع المسارات لإتاحة مساحة أكبر لها، بدلًا من محاولة إكمال المسارات المفقودة يدويًا.

• جهاز توجيه المتاهة ^{[ 4 ] [ 5 ]}
  • ^{[ 6 ] [ 4 ] [ 7 ]} خوارزمية البحث A * شائعة الاستخدام في المتاهة وموجهات Lee.
  • جهاز توجيه هادلوك ^{[ 8 ]}
  • موجه الفيضان ^{[ 4 ]}
• جهاز توجيه مسبار الخط
  • موجه ميكامي-تاهوتشي ^{[ 9 ]}
  • جهاز توجيه هاي تاور ^{[ 10 ] [ 7 ] [ 11 ] [ 4 ]}
• موجه النمط ^{[ 7 ] [ 11 ]}
• موجه القناة ^{[ 12 ] [ 11 ] [ 7 ] [ 13 ]}
  • جهاز توجيه Switchbox ^{[ 13 ]}
  • موجه النهر ^{[ 13 ]}
  • جهاز توجيه العمود الفقري والخياطة ^{[ 14 ]}
• جهاز توجيه بدون شبكة ^{[ 15 ] [ 11 ] [ 7 ] [ 16 ]}
  • موجه المنطقة
  • جهاز توجيه قائم على نظرية الرسم البياني ^{[ 17 ]}
    • موجه Bloodhound ^{[ 18 ] [ 19 ] [ 20 ]} ( CADSTAR بواسطة Racal-Redac / Zuken )
    • Specctra ^{[ 20 ]} (المعروف أيضًا باسم Allegro PCB Router ) (بدون شبكة منذ الإصدار 10)
  • موجه طوبولوجي
    • برنامج التوجيه FreeStyle (المعروف أيضًا باسم SpeedWay ، وهو برنامج توجيه تلقائي قائم على نظام التشغيل MS-DOS لبرنامج P-CAD )
    • TopoR ( برنامج توجيه تلقائي يعمل بنظام ويندوز ، ويستخدم أيضًا في تصميم دلتا من شركة Eremex )
    • توبوروتر (جهاز التوجيه مفتوح المصدر من تطوير أنتوني بليك والموجود في لوحة الدوائر المطبوعة لمجموعة gEDA )
    • TopRouter (الموجه الطوبولوجي المسبق في برنامج EAGLE 7.0 من CadSoft / Autodesk والإصدارات الأحدث)
    • SimplifyPCB (موجّه طوبولوجي مع التركيز على توجيه الحزم مع نتائج التوجيه اليدوي) ^{[ 21 ]}

تقوم العديد من أجهزة التوجيه بتنفيذ الخوارزمية العامة التالية:

• أولًا، حدد مسارًا تقريبيًا لكل شبكة، غالبًا عن طريق التوجيه على شبكة واسعة. تُسمى هذه الخطوة بالتوجيه العام ، ^{[ 22 ]} وقد تتضمن اختياريًا تعيين الطبقات. يحد التوجيه العام من حجم وتعقيد خطوات التوجيه التفصيلية اللاحقة، والتي يمكن تنفيذها مربعًا تلو الآخر على مستوى الشبكة.

أما بالنسبة للتوجيه التفصيلي، فإن التقنية الأكثر شيوعًا هي قطع وإعادة التوجيه، والمعروفة أيضًا باسم قطع وإعادة المحاولة : ^{[ 4 ]}

• حدد التسلسل الذي سيتم فيه توجيه الشبكات.
• قم بتوجيه كل شبكة بالتسلسل
• إذا لم يكن من الممكن توجيه جميع الشبكات بنجاح، فقم بتطبيق أي من طرق "التنظيف" المتنوعة، والتي يتم فيها إزالة التوجيهات المحددة، وتغيير ترتيب الشبكات المتبقية المراد توجيهها، ومحاولة التوجيهات المتبقية مرة أخرى.

تتكرر هذه العملية حتى يتم توجيه جميع الشبكات أو حتى يتوقف البرنامج (أو المستخدم).

ثمة نهج بديل يتمثل في التعامل مع حالات قصر الدائرة، ومخالفات قواعد التصميم، والعوائق، وما إلى ذلك، على قدم المساواة مع طول السلك الزائد، أي كتكاليف محدودة يجب تقليلها (مبدئيًا) بدلًا من كونها أمورًا مطلقة يجب تجنبها. تُوصَف طريقة التوجيه "التحسينية التكرارية" متعددة المراحل هذه ^{[ 23 ]} بالخوارزمية التالية:

• لكل من عدة تمريرات تكرارية:
• حدد أو عدّل معايير الوزن لدالة الهدف (بحيث يكون لكل وحدة من طول السلك الزائد، ولكل نوع من أنواع المخالفات، قيمة وزن محددة). على سبيل المثال، في المرحلة الأولى، يُعطى طول السلك الزائد عادةً تكلفة عالية، بينما تُعطى مخالفات التصميم مثل التماس الكهربائي، والتجاور، وما إلى ذلك، تكلفة منخفضة. في المراحل اللاحقة، يتغير الترتيب النسبي للتكاليف بحيث تكون المخالفات ذات تكلفة عالية، أو قد تُحظر تمامًا.
• حدد (أو اختر عشوائياً) تسلسلاً يتم فيه توجيه الشبكات خلال هذه العملية.
• قم بإلغاء التوجيه (إن وُجد) وأعد توجيه كل شبكة بدورها، وذلك لتقليل قيمة دالة الهدف لتلك الشبكة. (بعض التوجيهات قد تحتوي عمومًا على دوائر قصر أو مخالفات تصميمية أخرى).
• انتقل إلى المرور التكراري التالي حتى يكتمل التوجيه ويكون صحيحًا، أو لا يتم تحسينه أكثر من ذلك، أو يتم استيفاء معيار إنهاء آخر.

تُخصّص معظم أجهزة التوجيه طبقات الأسلاك لنقل الأسلاك ذات الاتجاه "س" أو "ص" بشكل أساسي، مع وجود بعض أجهزة التوجيه التي تتجنب أو تقلل الحاجة إلى هذا التخصيص. ^{[ 24 ]} ولكل نهج مزايا وعيوب. فالاتجاهات المقيدة تُسهّل تصميم مصدر الطاقة والتحكم في التداخل بين الطبقات، بينما يسمح السماح بمسارات عشوائية بتقليل الحاجة إلى الوصلات الرأسية وخفض عدد طبقات الأسلاك المطلوبة.

• أتمتة التصميم الإلكتروني
• مخطط التصميم (EDA)
• تصميم الدوائر المتكاملة
• المكان والمسار
• الاستقطاب الذاتي (الأزواج التفاضلية)
• التوصيل التلقائي (إيثرنت)

• شيفر، لويس ك.؛ لافانيو، لوتشيانو؛ مارتن، غرانت (2006). "الفصل 8: التوجيه ". دليل أتمتة التصميم الإلكتروني للدوائر المتكاملة . المجلد  الثاني. بوكا راتون، فلوريدا، الولايات المتحدة الأمريكية: مطبعة سي آر سي / تايلور وفرانسيس . ISBN 978-0-8493-3096-4.

• http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf
• http://www.facweb.iitkgp.ernet.in/~isg/CAD/SLIDES/10-grid-routing.pdf