منذ تسعينيات القرن الماضي ، أدهشني أن تصميم عالم الإلكترونيات الدقيقة الرقمية بالكامل يتحكم فيه مكتبان في كاليفورنيا ، على بعد 10 دقائق بالسيارة من بعضهما البعض - سينوبسيس وكادينس. في ذلك الوقت ، تم تصميم ربع التصميم العالمي في اليابان (كان البر الرئيسي للصين في ذلك الوقت في حالة بدائية) ، وكل هؤلاء من سوني وهيتاشي وفوجيتسو وغيرها من الشركات العملاقة انحنوا لأمريكا ودفعوا ملايين الدولارات التي لا تحصى مقابل البرامج التي استخدمها المصممون اليابانيون. الآن تستمر مع Samsung و Huawei وحتى مع المكاتب الروسية التي تصمم الرقائق الدقيقة للمساحة.
تمكنت الأرض الروسية من تنمية ياندكس مقابل جوجل ، فلماذا لا نحاول إنشاء بعض البرامج لتصميم الرقائق؟ يمكنك أن تبدأ صغيرًا: لتعميم المسابقات والاختراقات لتطوير خوارزميات أتمتة التصميم (Electronic Design Automation - EDA). هذه الخوارزميات مريحة من حيث أن لديها العديد من مستويات الصعوبة: يمكن للطالب أن يكتب أبسط برنامج Place & Route خلال عطلة نهاية الأسبوع ، لكن البرنامج المتقدم سيتطلب عقودًا من العمل لمئات الأشخاص ومليارات الدولارات في البحث والتطوير.
الآن في Innopolis بالقرب من Kazan يقومون بتنظيم
حدث للطلاب في شكل "أسبوعين من التدريب + hackathon" . أحد الموضوعات كانت مهمة EDA التقليدية - وضع وتعقب رسم بياني لدائرة إلكترونية في صفوف من الخلايا القياسية. سيكون من المثير للاهتمام معرفة ما يمكن لفريق صغير من المبرمجين لديهم فهم أساسي لـ C ++ / Java / Python وطرق تحليل النص وخوارزميات الرسم البياني والمهارات اللازمة لتصور هياكل البيانات باستخدام واجهة المستخدم الرسومية التي يمكن تنفيذها في وقت قصير.
لذلك - بيان المشكلة:
تتكون المهمة من ثلاث مهام فرعية يمكن للطلاب المختلفين التعامل معها:
- تحليل تمثيل نص الرسم البياني الدوائر الرقمية.
- وضع رسم بياني على صفوف الخلايا القياسية من الدائرة الدقيقة وربط هذه الخلايا مع المسارات (تتبع).
- تصور النتائج - عرض على شاشة مسارات الدوائر والاتصالات.
الإدخال إلى البرنامج هو ملف نصي في مجموعة فرعية محدودة للغاية من لغة وصف أجهزة Verilog. يصف هذا الملف المدخلات والمخرجات للدائرة (المدخلات ، المخرجات) ، الاتصالات الداخلية (السلك) ويوفر قائمة بالعناصر المنطقية بالتنسيق "type مثيل - اسم (قائمة الاتصالات)". يمكن تحليل الملف في C / C ++ باستخدام Lex + Yacc أو برامج مماثلة.
يجب أن تكون نتيجة تحليل النص عبارة عن تمثيل رسومي للعناصر الموجودة في الذاكرة. سيتم استخدام طريقة العرض هذه بواسطة خوارزمية الموضع والتتبع ، والتي سيتم إنشاؤها بعد ذلك بواسطة بنية أخرى. إذا كان هناك عدد كافٍ من المشاركين في فريق hackathon ، يمكن تصور نتيجة التحليل الأولي خلال hackathon كمهمة إضافية. تقريبا بهذه الروح ، حتى لو لم تكن جميلة:
إذا لم يكن هناك عدد كافٍ من المشاركين خلال hackathon ، فيجب ترك تصوُّر الرسم البياني المتوسط وغير المستبد لوقت لاحق ، وخلال hackathon ، يجب عرض الموضع النهائي فقط على الشاشة.
بشكل عام ، يمكن طرح مهمة التحليل بعدة مستويات من التعقيد:
- في أبسط الحالات ، تكون جميع العقد في الرسم البياني عنصرين منطقيين للإدخال AND و OR ، وكذلك عناصر NOT للإدخال الفردي. في الموضع النهائي ، يتم تحقيقها بواسطة خلايا قياسية بنفس العرض.
- إذا كان هناك ما يكفي من الوقت للاختراق ، يمكن أن تكون المهمة معقدة:
- إدخال ثلاث أو أربع خلايا الإدخال AND3 ، OR4 ، وما إلى ذلك ؛
- توسيع مجموعة أنواع العقدة عن طريق إضافة NAND ، XOR ، D-flip-flops (D-Flip-Flop) بخيارات مختلفة (إعادة التعيين ، التمكين) ، إلخ.
- إنشاء ملف نصي إضافي لتعيين عرض ومعلمات الخلايا الأخرى.
- بعد hackathon ، يمكن ربط المهمة بالعالم الحقيقي ، وليس محلل AND و OR الذي يتم تحليله ، ولكن الملف بنفس التنسيق ، ولكن مع خلايا من مكتبات حقيقية من خلايا ASIC القياسية من 28 أو 14 أو 7 نانومتر ، والتي يتم توفيرها لمطوري برامج EDA ومصممي المصانع نوع TSMC (شركة تصنيع أشباه الموصلات تايوان).
ما هي الخلية القياسية؟ هذه هي خلية الارتفاع القياسية لمكتبة أسيك معينة ، أي مكتبة بدائية لتصنيع دائرة كهربائية صغيرة في مصنع باستخدام بعض التكنولوجيا. أسيك - تطبيق الدوائر المتكاملة. الآن معظم الرقائق ، على سبيل المثال في الهواتف الذكية ، هي أسيك. تحتوي الخلايا الموجودة في مكتبة ASIC على ارتفاع قياسي بحيث يمكن ترتيبها بشكل مريح في صفوف لتوفير الطاقة لها وتسهيل خوارزميات التتبع. لا يمكن لخلايا مختلفة في المكتبة أن تقوم بتنفيذ الأوليات فقط مثل AND و OR ، ولكن أيضًا الإنشاءات الأكثر تعقيدًا - المضاعفات ، المزالج ، مجموعات مكونة من عنصرين أو ثلاثة عناصر منطقية (AND-OR) ، إلخ.
تصطف الخلايا على الدائرة
المصغرة في صفوف (شريحة من
محاضرات تشارلز دانشيك ):
بين الصفوف توجد قنوات (قنوات التوجيه) تمر بها الاتصالات. يمكن تغيير عرض القنوات إذا تم تشكيل الازدحام في الاتصالات. في الصفوف ، يمكنك إنشاء فجوات بين الخلايا:
بالنسبة للاختراق ، يمكن تبسيط المهمة إلى مستوى حصان كروي في فراغ:
- الحد من أنواع الخلايا. بالنسبة للمبتدئين ، يمكنك عمومًا وضع رسم بياني فقط لـ NAND ذي الإدخالين.
- النظر في جميع الخلايا ليكون لها نفس العرض.
- تجاهل جميع جوانب الطبيعة المادية للخلايا ، بما في ذلك تأخير الإشارة واستهلاك الطاقة.
هنا ، يعني "التجاهل" أنه في التمرين التدريبي لا يمكنك مراعاة فيزياء الخلية عند تقييم جودة التنسيب والتتبع. بادئ ذي بدء ، يكفي التفكير في الشكل الهندسي فقط ، على سبيل المثال ، لتقليل الطول الكلي للمفاصل وعدد الطبقات التي تم تكوين الوصلات عليها. تنشأ الحاجة إلى طبقة جديدة عندما يكون من المستحيل وضع موصلين دون عبورهما.
في hackathon ، يكفي اعتبار الخلايا القياسية "صناديق سوداء" وعرضها على الشاشة كما في الأشكال أعلاه. أو مع صور لعناصر منطقية ، كما هو الحال في شريحة من
محاضرات إيجور ماركوف :
على الرغم من أنك إذا عرضت بداخل الخلايا ، فإن الصور تكون أكثر زخرفية. شريحة من
محاضرات تشارلز دانشيك :
صورة أخرى من الإنترنت مع وضع وتتبع + صورة من الدواخل من الخلايا:
ولكن كيف يمكن وضع الخلايا في صفوف وتوسيع القنوات وتضييقها بين الصفوف وبناء الاتصالات وإدخال طبقات جديدة وتقييم أفضل النتائج وترتيب الخيارات؟ حسنًا ، هذه مهام خوارزمية وبرمجية بحتة ، في Innopolis ربما يقومون بتدريس هذا ، لذلك لن نشر أفكاري أو أفكاري على الشجرة. كإلهام أولي للتتبع ، يمكنك استخدام الطريقة القديمة لتتبع الموجات ، الموصوفة
في الجزء الثالث من الدورة لتلاميذ المدارس من RUSNANO . على الرغم من أن هذه الطريقة ليست للخلايا القياسية مرتبة في الصفوف ، ولكن بالنسبة للحالة الأقل ترتيبًا مع عدد صغير من المكونات:
2.10. كيفية القيام بذلك: خوارزمية تتبع الموجة.
واحدة من الخوارزميات الكلاسيكية التي تستخدمها برامج التتبع المبكرة كانت تتبع الموجة ، والتي تم وصفها في مقال نشر عام 1961 من قِبل تشيستر لي ، الباحث في Bell Labs. في الإنجليزية ، تسمى خوارزمية Lee "maze routing" ، والتي تُعرف حرفيًا باسم "تتبع المتاهة". يرجع هذا الاسم إلى حقيقة أنه بالإضافة إلى برامج تصميم الإلكترونيات ، تم استخدام خوارزمية Lee في برامج الألعاب للعثور على أقصر الطرق في المتاهة.
تمثل خوارزمية Lee الكتل التي يجب أن تكون متصلاً ، في شكل أشكال على متن طائرة محدودة ، تحمل علامة "في المربع". للعثور على أقصر مسار من إخراج كتلة واحدة إلى إخراج كتلة أخرى ، تستخدم خوارزمية Lee تمريرين:
- أول ممر يسمى انتشار الموجة. نحتفل بجميع "الخلايا" أو الخلية في الإخراج الأول مع وحدة. بعد ذلك ، بالنسبة لكل خلية مصنفة بالرقم N ، نضع علامة على جميع الخلايا المجانية غير المُعلَّمة المجاورة بالرقم N + 1. كرر الترميز حتى نصل إلى نهاية الكتلة الثانية أو لا توجد فرصة أخرى لنشر "الموجة".
- يسمى الممر الثاني "استعادة المسار". إذا تم وضع علامة على الخلية الموجودة في المربع الثاني ، فسنختار من بين جيرانها خلية تحمل علامة 1 أقل من الرقم الموجود في الخلية الحالية. أضف خلية مجاورة إلى المسار ، واذهب إليها وابدأ في النظر إلى جيرانها ، والتي تحمل علامة واحدة أخرى أقل. نكرر هذا حتى نصل إلى خاتمة الكتلة الأولى.
في البداية ، تم استخدام خوارزمية Lee في برامج تصميم لوحات الدوائر المطبوعة ، ثم بدأوا في استخدامها لتصميم الدوائر الصغيرة. ومع ذلك ، عندما نما حجم الدوائر الدقيقة ، كان من المستحيل تطبيق خوارزمية Lee في شكلها الأصلي ، لأنه يتطلب مقدارًا كبيرًا من الذاكرة لتخزين صفيف البيانات ، بالإضافة إلى قدر كبير من الوقت لتمرير العديد من هذه المجموعة. على الرغم من حقيقة أن برامج التتبع التلقائي الحديثة تستخدم خوارزميات أخرى ، تظل خوارزمية Lee تمرينًا ممتازًا لأولئك الذين أتقنوا البرمجة مؤخرًا ويريدون كتابة برنامج تتبع صغير بأنفسهم.
للحصول على خوارزميات أكثر جدية ، يمكنك البحث عن أفكار
في مواد Igor Markov . ولكن أفضل شيء هو أن تكون مبدعًا - ماذا لو أتيت بشيء لم يجد الآلاف من مبرمجي الخوارزميات الذين يتمتعون ببراعة في الرياضيات اختناقات مرورية على الطرق السريعة 101 و 880 و 237 في مكاتب سينوبسيس وكادينس كل صباح في مدن سان خوسيه ، سانيفيل وماونتن فيو ، كاليفورنيا.
المراجع (من البسيط إلى المعقد):
- محاضرات تعريفية حول أساسيات التصميم الرقمي في Innopolis: 1 ، 2 .
- دورة تمهيدية في مجال الإلكترونيات الرقمية و EDA لأطفال المدارس المتقدمين من النوع الأوليمبي. من روسنانو: 1 ، 2 ، 3 .
- كتاب هاريس وهاريس .
- شرائح من المحاضرات التي كتبها تشارلز دانشيك .
- دورة لإيجور ماركوف من جامعة ميشيغان . قرأ هذه الدورة في جامعة موسكو الحكومية.
أعرب عن أملي
في أن تتوسع
مبادرة Innopolis في المسابقات الخوارزمية . منطقة جمعية الإمارات للغوص مثيرة للاهتمام رياضياً وتدفع أجورها. افتتح سينوبسيس فرعًا في أرمينيا وأصبح أحد أرباب العمل الرائدين هناك:
"اليوم ، تعد سينوبسيس واحدة من أكبر أرباب العمل في مجال تكنولوجيا المعلومات في أرمينيا مع أكثر من 650 موظفًا (بما في ذلك أكثر من 600 مهندس)". ألاحظ أن روسيا أكبر من أرمينيا ، وربما يمكنها إنشاء سينوبسيس خاص بها. في النهاية ، هناك العديد من المبرمجين في روسيا ، وعلماء الرياضيات أيضًا ، والرسملة السوقية الحالية لـ Synopsys + Cadence تساوي تقريبًا تكاليف أولمبياد سوتشي.