Fuzzy simulated evolution algorithm for VLSI cell placement.

Abstract

النشوء المحاكي (Simulated Evolution) عبارة عن مستكشف تسلسلي يستخدم لإيجاد حلول قريبة من الحل الأمثل للمشاكل التي لا يمكن حلها بكثيرات الحدود (NP-Hard Problems) . وضع الخلايا في الدوائر المتكاملة عالية الكثافة جداً مشكلة لا يمكن تمثيلها بكثيرة حدود ولها أهداف متعارضة ألا وهي طول التوصيلات ، زمن التنفيذ والمساحة الكلية . أفضل الحلول لمشكلة كهذه هو الذي يحقق أقل القيم في جميع الأهداف إلا أن حلاً كهذا لا يوجد غالباً . لتعريف الحل الأمثل الذي يقدمه خوارزم النشوء المحاكي ، نقدم طريقة جديدة لحساب تكلفة الحل بطريقة غامضة معتمدة على الهدف . تتغلب هذه الطريقة على المشاكل المتعلقة بطريقة المجموع الموزون . إضافة إلى ذلك فإن هذه الطريقة تسمح باعتبار أفضليات المستخدم لمختلف الأهداف . كما نقدم طريقة لتغميض مرحلة التوزيع ومرحل التقييم في الخوارزم المذكور ، طريقة التوزيع تحاول تظليل قيم الأهداف المتعارضة وإضافة عشوائية محكومة خلافاً للطريقة الأصلية ذات التوزيع المحدد . التجارب على دوائر الاختبار تثبت تطوراً ملحوظاً في نوعية الحل . طريقة التقييم الغامض تجمع طور التوصيلات وزمنها لحساب جودة الخلايا متفرقة . ينتج عن ذلك تحسن في زمن التنفيذ وزيادة بسيطة في طور لاتوصيلات . إضافة إلى ذلك ، قدمنا طريقة تحفيز متغير بدلاً من التحفيز الثابت في الخوازم الأصلي ، التحفيز الثابت يتطلب تجارب عديدة لتحديد لاقيمة الأنسب . في المقابل ، التحفيز المتغير دالة تعتمد على متوسط جودة الخلية ، تضبط قيمتها تلقائياً لتوفر التجارب . نتائج التحفيز المتغير قريبة من أفض نتائج التحفيز الثابت .