Fast fuzzy forcedirected simulated evolution metaheuristic for multiobjective VLSI cell placement

Abstract

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

VLSI standard cell placement is the process of arranging circuit components (modules) on a silicon layout The cell placement problem is a proven NP hard combinatorial optimization problem The complexity of this problem increases when multiple optimization objectives are considered simultaneously In this paper a novel technique is presented to address this hard problem while optimizing multiple objectives A major difficulty with such multiobjective combinatorial optimization problems is the existence of a very large solution search space within which is the desired optimal solution Simulated Evolution (SE) a general iterative heuristic is used to traverse the large search space while fuzzy logic is resorted to assist in multicriteria decision making and overcome the imprecise nature of design information at placement stage New fuzzy aggregation functions are proposed SE is hybridized with force directed algorithm to speedup the search The proposed schemes are compared with previously presented SE based heuristics The implementations exhibit considerable improvement in terms of both solution quality and runtime