مخطط القيود (التخطيط)

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

في تخطيط الأرضيات ، يكون نموذج مخطط الأرضية للدائرة المتكاملة عبارة عن مجموعة من المستطيلات المتساوية تسمى "الكتل" داخل مستطيل أكبر يسمى "الحدود" (على سبيل المثال، " حدود الشريحة "، "حدود الخلية ").

يمكن تعريف مخططات القيود على النحو التالي: مخطط القيود لمخطط طابق معين هو مخطط موجه ، ومجموعة رؤوسه هي مجموعة كتل مخطط الطابق، ويوجد ضلع من الكتلة b1 إلى b2 (يسمى قيدًا أفقيًا) إذا كانت b1 تقع بالكامل على يسار b2، ويوجد ضلع من الكتلة b1 إلى b2 (يسمى قيدًا رأسيًا) إذا كانت b1 تقع بالكامل أسفل b2.

إذا اقتصرنا على القيود الأفقية فقط، نحصل على مخطط القيود الأفقية . وإذا اقتصرنا على القيود الرأسية فقط، نحصل على مخطط القيود الرأسية .

وفقًا لهذا التعريف، يمكن أن يحتوي الرسم البياني للقيود على عدد يصل إلى${\displaystyle O(n^{2})}$الحواف، حيث n هو عدد الكتل. لذلك، تُؤخذ في الاعتبار رسوم بيانية أخرى للقيود أقل كثافة. رسم بياني الرؤية الأفقية هو رسم بياني للقيود الأفقية، حيث يوجد قيد أفقي بين كتلتين فقط إذا كان هناك خط مستقيم أفقي يربط بينهما ولا يتقاطع مع أي كتل أخرى. بعبارة أخرى، تُعتبر إحدى الكتل "عائقًا مباشرًا" محتملاً لتحريك كتلة أخرى أفقيًا. يُعرَّف رسم بياني الرؤية الرأسية بطريقة مماثلة.

تُعرف عملية توجيه القنوات بأنها مسألة توجيه مجموعة من الشبكات N ذات أطراف ثابتة على جانبين متقابلين من مستطيل ("قناة"). في هذا السياق، يُمثل الرسم البياني للقيود الأفقية الرسم البياني غير الموجه ذو مجموعة الرؤوس N ، وترتبط شبكتان بحافة إذا وفقط إذا تداخلت الأجزاء الأفقية من مسار التوجيه. في المثال المذكور، الشبكتان 5 و6 فقط لا تخضعان لقيد أفقي. أما الرسم البياني للقيود الرأسية فهو الرسم البياني الموجه ذو مجموعة الرؤوس N، وترتبط شبكتان بحافة إذا وفقط إذا كان هناك طرفان من شبكتين مختلفتين على نفس الخط الرأسي، وكانت الحافة موجهة من الشبكة التي يقع طرفها على الحافة العلوية للقناة. يعني هذا الاتجاه أنه يجب توجيه هذه الشبكة على مسار أفقي أعلى المسارات الأفقية للشبكة الثانية. في المثال المذكور، الشبكتان 1 و3 فقط تخضعان لقيد رأسي. ^{[ 1 ]}