SA-based Approach to Implement Digital Systems on 3D Integrated Circuits

Document Type : Research Article

Authors

1 M.Sc., Department of Electrical Engineering,University of Kurdistan, Sanandaj, Iran

2 Assistant Professor, Department of Electrical Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

The 3D integrated circuit is emerged as a promising solution to integrate very large-scale circuits on electronics chips. In such chips, several layers of silicon substrates are stacked which are separated by insulator interfaces. Interconnection between two layers is realized using Through Silicon Via (TSV). Fabrication of TSVs is challenging due to their large size and complex process. Consequently, the number of TSVs should be minimized in the circuit’s implementation. The 3D implementation consists of three main steps: Partitioning, Placement, and Routing. In this paper, the first two steps are accomplished using the Simulated Annealing-based optimization approach wherein minimization of the number of TSVs and total wire length are considered the main objectives. In this paper, an improved version of the pathfinder method has been developed which would efficiently generate the necessary interconnections among circuit modules. The results of simulations on MCNC benchmark circuits show that the proposed method outperforms the previous state-of-the-art methods in all aspects. In comparison with FSA, the number of TSVs is reduced by 6.15%, and the algorithm’s runtime is decreased by 27.79%. Moreover, in comparison with the hMETIS method, the number of TSVs is reduced by 9.78%, and the algorithm’s runtime is decreased by 31.73% .

Keywords


  • مقدمه[1]

در گذار از یک نسل تراشه‌های مجتمع دیجیتال به نسل بعد، همواره سعی بر آن است که براساس قانون مور [1]، تعداد ترانزیستورهای مجتمع‌شده دو برابر شود. این امر معمولاً با کوچک‌کردن اندازة ترانزیستورها انجام می‌شود؛ برای مثال، پردازندۀ ساخته‌شده در شرکت NVIDIA موسوم به GA100 Ampere در سال 2020 با فناوری 7 نانومتر ساخته شده که شامل 54 میلیارد ترانزیستور است [22]. با کاهش مقیاس ترانزیستورها به زیر 10 نانومتر، ادامة روند ترسیم‌شده با قانون مور ازطریق کاهش اندازة ترانزیستورها، تقریباً غیرممکن شده است. بر‌طبق آخرین گزارش ITRS در سال 2015، با کوچک‌شدن اندازة ترانزیستورها، پس از سال 2021، کاهش مقیاس تقریباً امکان‌پذیر نخواهد بود [2].

با کاهش اندازة‌ ترانزیستورها در حوزة نانومتری، اثرات نامطلوبی مانند افزایش توان نشتی و وابستگی بسیار زیاد عملکرد ترانزیستور به تغییرات ناشی از مشخصات فناوری ساخت، نمود بیشتری پیدا می‌کنند [3 ,4]. همچنین، اتصالات[1] در تراشه‌های نانومتری سهم بزرگی از تأخیر را به خود اختصاص می‌دهند؛ برای مثال، در فناوری 90 نانومتری، تقریباً 75 درصد تأخیر کلی تراشه، ناشی از اتصالات داخلی و سیم‌بندی‌ها است [5].

مدارهای مجتمع سه‌بعدی[2] به‌عنوان یک راه‌حل بسیار کارا برای حل مشکلات ذکرشده مطرح شده‌اند. در این تراشه‌ها، طول سیم لازم برای اتصال ماجول‌های مختلف کاهش می‌یابد که نتیجة مستقیم آن، افزایش سرعت تراشه، بهبود مجتمع‌سازی و کاهش توان مصرفی است [6]. در معماری تراشه‌های مذکور، تعداد N لایة‌ فعال روی یکدیگر قرار گرفته‌اند که هرکدام ساختاری شبیه به تراشه‌های دوبعدی دارند (یعنی ترانزیستورها روی سطح بالایی آنها ساخته می‌شوند و اتصالات لازم بین این ترانزیستورها، با چند لایة سیم‌بندی در بالای لایة فعال انجام می‌شود). همچنین، برای ایجاد ارتباط بین ترانزیستورها در لایه‌های مختلف، از اتصالات عمودی ویژه‌ای به نام [3]TSV استفاده می‌شود. برای ایجاد TSV بین لایه‌های فعال 1 و 2، باید کانالی (با سطح مقطع دایره‌ای، مربعی و ...) از رویة زیرین لایة فعال دوم به رویة بالایی آن ایجاد شود. برای ایجاد ارتباط عمودی بین دو لایة‌ فعال غیرمجاور (مثلاً لایه‌ها‌ی 1 و 4) باید کانال مدنظر از لایه‌های میانی (2، 3 و 4) عبور کند. ساختن کانال‌های این چنینی با محدودیت‌های مکانیکی و پیچیدگی‌های ساخت فراوانی همراه است؛ بنابراین، مدار مدنظر باید به‌گونه‌ای بین لایه‌های فعال تقسیم‌بندی شود که به کمترین تعداد TSV نیاز داشته باشد.

مسئلة مهم دیگر، حرارت تولیدشده در لایه‌های میانی است که باید به‌صورت مناسبی به یک Heatsink منتقل شود که پایین‌تر از لایة اول قرار دارد. این انتقال با استفاده از کانال‌های حرارتی ساخته‌شده با استفاده از TSVها انجام می‌شود.

پیاده‌سازی مدارهای منطقی روی تراشه‌های سه‌بعدی با تعداد NL لایة فعال، در سه مرحله انجام می‌شود. ابتدا مدار مدنظر به NL بخش‌ مساوی تقسیم می‌شود. سپس هرکدام از بخش‌ها روی یک لایه پیاده‌سازی می‌شوند. پیاده‌سازی روی لایه‌ها در دو مرحلة جانشانی (انتساب گیت‌ها به مکان‌هایی روی سطح لایه) و مسیردهی (ایجاد سیم‌بندی‌های لازم بین گیت‌ها) انجام می‌شود. از منظر پیچیدگی محاسباتی هر سه مرحلة‌ بخش‌بندی، جانشانی و مسیردهی از نوع مسائل NP-Hard هستند؛ بنابراین، حل تحلیلی آنها امکان‌پذیر نیست و برای یافتن راه‌حل‌های پذیرفتنی، مجبور به استفاده از روش‌های فراابتکاری هستیم.

در مطالعات پیشین، روش‌های فراابتکاری متنوعی برای پیاده‌سازی مدارهای دیجیتال روی تراشه‌های سه‌بعدی ارائه شده است. مراجع [7]، [8] و [9] از الگوریتم ژنتیک در حل مسئله استفاده کرده‌اند. در مرجع [7] دو هدف اصلی کاهش طول سیم مصرفی (کاهش تأخیر مدار) و توزیع مناسب بلوک‌ها برای انتقال بهینة حرارت تولیدشده در لایه‌های میانی تعریف شده است. نتایج نشان‌دهندة‌ کاهش میزان میانگین و بیشینة حرارت تولیدشده در نقاط داغ تراشه است که با افزایش اندکی در طول سیم مصرفی همراه است. یک روش فراابتکاری چند هدفه بر مبنای الگوریتم ژنتیک در مرجع [8] ارائه شده است که در آن شبکه‌های سه‌بعدی موجود در مدار (یعنی یک منبع و ماجول‌هایی که به خروجی این منبع وصل‌اند) روی لایه‌های تراشة سه‌بعدی به‌صورت همزمان پیاده‌سازی می‌شوند. در این پیاده‌سازی سعی بر آن است که محل TSVها به‌گونه‌ای انتخاب شوند که نخست، در مکانی با چگالی توان بالا و تراکم سیم‌بندی کم باشند؛ دوم، طول سیم‌بندی شبکه‌های سه‌بعدی حداقل شود. در مرجع [9] روش پیاده‌سازی دیگری بر مبنای الگوریتم ژنتیک ارائه شده است که در آن ابتدا با شروع از پایین‌ترین لایه، بلوک‌ها به لایه‌ها نسبت داده می‌شوند. با انتخاب توالی‌های مختلف، بخش‌بندی‌های مختلفی ایجاد می‌شوند که هرکدام یک کروموزم خواهند بود. در مرحلة بهینه‌سازی، الگوریتم ژنتیک با اعمال عملگرهای ژنتیکی روی کروموزم‌ها جواب‌های مطلوب را جستجو می‌کند. تابع هزینه در این الگوریتم ترکیبی از چگالی توان و تعداد TSVها است.

در مرجع [10]، رویکرد متفاوتی برای حل مسئلة‌ پیاده‌سازی روی تراشه‌های سه‌بعدی بر مبنای الگوریتم تبرید شبیه‌سازی‌شده[4] یا به اختصار SA ارائه شده است. در این روش، با شروع از یک پیاده‌سازی تصادفی، یک بلوک در بین لایه‌ها جابه‌جا می‌شود و این جابه‌جایی در صورتی پذیرفته می‌شود که به کاهش تابع هزینه منجر شود. در صورتی که حرکت مدنظر باعث افزایش تابع هزینه شود، با احتمال کوچکی پذیرفته خواهد شد. تابع هزینه در این رویکرد بر مبنای کاهش تعداد TSVها و متعادل‌کردن سطح مصرفی لایه‌ها تعریف شده است. در روش FSA مطرح‌شده در مرجع [11]، با استفاده از رهیافت نیروی کشسانی فنر، مدلی احتمالاتی برای افزایش نرخ همگرایی SA ارائه شده است. در این روش اهداف اصلی، کاهش تعداد TSVها و متعادل‌کردن سطح مصرفی لایه‌ها هستند.

تمام روش‌های ذکرشده در بالا دو نقص اساسی دارند؛ سرعت رسیدن به جواب بهینه و حافظة مورد نیاز در اجرای فرایند بهینه‌سازی. الگوریتم ژنتیک برای حل مسائلی با اندازة بزرگ کارا نیست. در این الگوریتم، برای رسیدن به جواب بهینه (یا شبه‌بهینه با کیفیت بالا) باید تعداد کروموزم‌ها نسبتاً زیاد باشد؛ اما این مسئله به مصرف مقدار زیادی حافظه منجر خواهد شد و اعمال عملگرهای ژنتیکی نیز به زمان‌ زیادی نیازمند است. به همین دلیل، روش‌های ارائه‌شده بر مبنای الگوریتم ژنتیک مقیاس‌پذیر نیستند و برای مدارهای با اندازة بزرگ کاربردی نیستند. روش‌‌های ارائه‌شده بر مبنای SA، به‌دلیل استفاده از فقط یک حل اولیه و ایجاد تغییرات کوچک در ساختار آن مشکل حافظة مصرفی بالا را حل کرده‌اند. مشکل مقیاس‌پذیری در روش‌های مبتنی بر SA همچنان وجود دارد. دلیل این امر، نیاز به فرایند سردسازی بسیار طولانی و طی‌کردن تعداد زیادی تغییرات کوچک در هر گام دمایی به‌منظور رسیدن به جواب بهینه برای مدارهای بسیار بزرگ است.

در روند پیاده‌سازی ارائه‌شدة پیشنهادی، مراحل بخش‌بندی و جانشانی از هم جدا شده‌اند که به کاهش اندازة مسئلة بهینه‌سازی منجر می‌شود. روش فراابتکاری SA [12] برای یافتن حالت بهینه در مراحل بخش‌بندی و جانشانی استفاده ‌شده است. هدف در مرحلة بخش‌بندی، کاهش تعداد TSVها و در مرحلة جانشانی، کاهش طول مصرفی برای اتصال ماجول‌ها روی هرکدام از لایه‌ها است. مرحلة مسیردهی براساس الگوریتم ابتکاری مسیریاب[5] انجام می‌شود که در ابزارهای طراحی مدارهای مجتمع به‌صورت وسیع استفاده شده است [13].

در ادامة مقاله، در بخش دوم پیش‌نیازهای لازم و در بخش سوم، روش پیشنهادی بیان شده است. در بخش چهارم، نتایج حاصل از روش پیاده‌سازی بررسی شده و در بخش پنجم، نتیجه‌گیری مربوط به این تحقیق بیان شده است.

 

2- پیش‌نیازها

در این بخش ساختار مدارهای مجتمع سه‌بعدی و ساختار TSVها به‌صورت اجمالی معرفی می‌شوند. توضیحاتی دربارة‌ بخش‌بندی، جانشانی و مسیردهی ارئه خواهند شد و درنهایت الگوریتم SA معرفی می‌شود.

 

1-2- ساختار مدارهای مجتمع سه‌بعدی

ساختار کلی یک مدار مجتمع سه‌بعدی در شکل (1) نشان داده شده است. همان‌طور که دیده می‌شود، لایه‌های فعال به‌صورت انباشته[6] روی یکدیگر قرار می‌گیرند و ایجاد اتصالات عمودی بین لایه‌ای با استفاده از TSVها انجام می‌شود.

یکی از مهم‌ترین مزیت‌های مدارهای مجتمع سه‌بعدی، کاهش طول و عرض تراشه (و به ‌تبع آن مساحت تراشه) در مقایسه با معادل دوبعدی است. میزان این کاهش، به شدت به تعداد TSVها وابسته است.

برای درک بهتر این موضوع، شکل (2) را در نظر بگیرید. همان‌طور که در شکل (2) قسمت (الف) دیده می‌شود، تراشة دوبعدی، دارای طول و عرض X است. حال اگر بخواهیم منابع موجود در این تراشة‌ دوبعدی را در یک تراشة سه‌بعدی با چهار لایه توزیع کنیم (شکل 2، قسمت ب)، سطح تراشة دوبعدی به چهار قسمت مساوی تقسیم می‌شود که طول و عرض هرکدام به نصف حالت قبلی (یعنی X/2) کاهش می‌یابد.

 

 

شکل (1): نمایی کلی از یک مدار مجتمع سه‌بعدی یا چهار لایه

 

شکل (2): الف) تراشة دوبعدی، ب) تراشة سه‌بعدی معادل با چهار لایه

 

قرارگرفتن TSVها در ساختار تراشه‌های سه‌بعدی، نیازمند در نظر گرفتن فضای کافی در محل قرارگیری آنها است. به همین دلیل، همان‌گونه که در شکل (2) قسمت (ب) مشاهده می‌شود، اندازة طول و عرض تراشة سه‌بعدی نسبت به مقدار مورد انتظار X/2 بیشتر است. این مقدار افزایش با مشخصة Delta نشان داده شده‌ است. با افزایش تعداد TSVها در سطح تراشه، مقدار Delta بیشتر می‌شود. بیشینة فاصلة منهتن[7] (از نقطه A به نقطه B) در تراشة‌ دوبعدی (شکل 2، قسمت الف) مطابق معادلة (1) محاسبه می‌شود:

(1)

MDmax, 2D = X + X

 

همچنین، بیشینة فاصلة منهتن در تراشة سه‌بعدی (شکل 2، قسمت ب) مطابق معادله (2) محاسبه می‌شود:

(2)

MDmax, 3D = (n-1) × hTSV + 2× (X/2 + delta)

 

در این معادله، hTSV برابر با ارتفاع TSV و n برابر با تعداد لایه‌های تراشة سه‌بعدی است. هرچند ارتفاع TSV حدود 20 میکرومتر است [14]، با توجه به مشخصه‌های ذاتی TSV (در بخش‌های بعدی به آن اشاره خواهد شد)، در مقایسه با سیم‌های استاندارد، تأخیر بسیار کمتری دارد [8]؛ بنابراین، سهم عبارت اول در معادله (2) در مقدار تأخیر مسیر، قابل صرف‌نظر کردن است. به‌صورت تقریبی، نسبت تأخیر مسیرها با بیشترین طول در تراشة‌ سه‌بعدی و دوبعدی با استفاده از معادله (3) محاسبه می‌شود:

(3)

MDmax(3D)/MDmax(2D) = 2/(1+2×Delta/X)

 

با توجه به رابطه‌ (3)، افزایش تعداد TSVها که به افزایش مقدار Delta منجر می‌شود، سبب کاهش مزیت تراشة‌ سه‌بعدی نسبت به تراشة دوبعدی می‌شود. نتیجة کلی این است که باید کنترل جدی بر تعداد TSVها صورت بگیرد.

همان‌طور که گفته شد، TSVها به‌عنوان اتصالات عمودی در تراشه‌ها استفاده ‌می‌شوند و توان تلفاتی کمتر و تأخیر کمتر در مقایسه با سیم‌های ارتباطی بین تراشه‌ها دارند.

مطالعات اخیر در حوزة TSVها بیشتر روی طراحی بر مبنای قابلیت اطمینان[8] و مقرون‌به‌صرفه[9] بودنِ ساخت آنها تمرکز دارند. فاکتورهای اساسی تأثیرگذار بر نحوة عملکرد یک TSV عبارت‌اند از ماده پرکننده[10] (ماده‌ای که برای پرکردن حفرة TSV استفاده می‌شود)، طول، شکل و قطر TSVها. از رایج‌ترین مواد پرکنندة TSV می‌توان مس، تنگستن و پلی کریستال سیلیکون[11] را نام برد که در زمان حاضر مس از همه رایج‌تر است. به‌تازگی نانو اتصال‌گرهای بر مبنای گرافن[12]، رقیبی برای مس مطرح شده‌اند. دلیل واردشدن این فناوری به عرصة رقابت با مس، خواص و رفتار یکتایی است که ازنظر الکتریکی، مکانیکی، شیمیایی و گرمایی دارد [15]. TSVها در شکل‌های گوناگونی مانند دایره‌ای، حلقوی، مربعی، مستطیلی و مخروطی ساخته شده‌اند؛ اما ساختار فیزیکی یک TSV همچنان یک چالش به حساب می‌آید و پژوهشگران حوزة نیمه‌هادی‌ و نانوالکترونیک، توجه بیشتری به این زمینه دارند.

بر طبق نقشه‌‌راه اعلام‌شده توسط ITRS 2015 برای مقطع زمانی 2019 تا 2022، قطر یک TSV برابر با 2-5/0 میکرومتر، گام‌های[13] آن برابر با 4-1 میکرومتر و ارتفاع آن برابر با 20-5 میکرومتر است.

 

2-2- بخش‌بندی، جانشانی و مسیردهی

فرض کنید گراف مدار G(V, E) را در اختیار داریم که در آن، سلول‌های منطقی (معادل همان گیت‌های منطقی) و ارتباطات داخلی (یا همان سیم‌بندی بین المان‌ها) به‌ترتیب با رأس‌ها و یال‌ها معادل ‌شوند.

در گراف مدار، V = {v1, v2, v3, … , vn} مجموعه رأس‌ها و E = {e1, e2 , e3, … , en} مجموعه یال‌ها هستند. در مسئلة بخش‌بندی، هدف تقسیم‌کردن مجموعه رأس‌های V از گراف G(V, E) به k زیرگراف V1, V2, V3, … Vk است؛ به طوری که داشته باشیم:

|V1| = |V2| = … = |Vk|,

Vi ∩ Vj = Φ,   i ≠ j

 

تابع هزینه‌ در مسئلة بخش‌بندی، براساس تعداد یال‌های متصل‌کنندة بخش‌های مختلف تعریف می‌شود که اندازة برش[14] نامیده می‌شود. مسئلة بخش‌بندی گراف‌ها از دیدگاه ریاضی به‌عنوان یک مسئلة NP-hard شناخته شده است.

مراحل بعد از بخش‌بندی، جانشانی و مسیردهی[15] هستند. جانشانی عبارت است از پیداکردن بهترین مکان برای هر رأس (بلوک)، به طوری که در هر مختصات مکانی، بیش از یک رأس قرار نگیرد. یک جانشانی ضعیف، باعث اشغال مساحتی بیشتر در سطح تراشه و همچنین افت کیفیت در مرحلة مسیردهی می‌شود. در فرایند جانشانی زیرگراف‌ها روی لایه‌های تراشة سه‌بعدی، بلوک‌های مربوطه به‌گونه‌ای جانشانی می‌شوند که کمترین طول سیم مصرفی مصرف شود.

مسئلة مسیردهی در تراشه‌های دیجیتال، عبارت است از اختصاص‌دادن شبکه[16] (منظور از شبکه، مجموعه اتصالات خروجی یک ماجول منبع به تمام ماجول‌های مقصد مربوط به آن است) به منابع بخش اتصالات، به گونه‌ای که هیچ‌یک از منابع با بیش از یک شبکه به اشتراک گذاشته نشود. این مرحله به کیفیت مرحلة قبل از خود، یعنی جانشانی وابسته است [16].

 

3-2- الگوریتم SA

الگوریتم SA یکی از الگوریتم‌های فراابتکاری است که کاربرد زیادی در طراحی‌‌های فیزیکی دارد. الگوریتم SA یک روش بهینه‌سازی است که از فرایند خنک‌سازی آهستة فلزات الهام گرفته شده است. در این فرایند با کاهش تدریجی حرکت اتم‌ها، قرارگیری نهایی آنها به‌گونه‌ای است که وضعیت کمترین انرژی پایدار در شبکه حاصل ‌شود [12]. شبه‌کد مربوط به SA، در الگوریتم (1) مشاهده می‌شود.

 

الگوریتم (2-1): شبه‌کد الگوریتم SA

Input: G (V, E)

Output: Optimized solution

 

1: Initialization

2: S       S­init

3: CostCurrent = Cost(S)

4: while T > Tmin

5:      while stopping criterion is not met yet

6:            neighbor(S’)

7:            Costnew = CostCurrent

8:            ∆Cost = Costnew - CostCurrent

9:            if (∆Cost < 0)

10:              S       S’

11               Costnew = CostCurrent

12:          else

13:              r        Rand (0,1)

14:              if (r < exp(-∆Cost/T))

15:                  S       S’

16:                  Costnew = CostCurrent

17:              end if

18:          end if

19:      end while

20:      T = G (T, K)

21: end while

 

عملکرد این الگوریتم (به‌صورت خلاصه) بدین صورت است: در ابتدا مشخصه‌های اساسی (دمای اولیه، ضریب خنک کنندگی و ...) مقداردهی اولیه می‌شوند و یک راه‌حل مسئله به‌صورت تصادفی تولید می‌شود. هزینة این راه‌حل اولیه، محاسبه (CostCurrent) و الگوریتم وارد یک حلقه می‌شود. در هر تکرار از حلقه، تغییر کوچکی به‌صورت تصادفی در حل مرحلة قبل ایجاد می‌شود (neighbor(S’)). اگر این تغییر، در راستای کاهش هزینه باشد (یعنی اختلاف تابع هزینة جدید و قبلی، منفی باشد)، پذیرفته و تابع هزینه با توجه به این تغییر و تأثیرات آن به‌روز می‌شود؛ اما اگر این تغییر به کاهش مقدار تابع هزینه منجر نشود، به احتمال کمی مطابق خطوط 13 تا 16 از الگوریتم پذیرفته می‌شود. این راه‌کار، سبب جلوگیری از گیر‌افتادن الگوریتم در یک کمینه محلی خواهد شد. در پایان بدنة حلقه، مشخصة دما بر طبق یک تابع خاص (خط 20 از الگوریتم) به‌روز می‌شود. این تابع و فرایند خنک‌سازی، نباید آنقدر زود اتفاق بیافتد که مانعی برای کاهش تابع هزینه به اندازة کافی شود و نیز نباید آنقدر با سرعت کمی پیش برود که زمان اجرا به‌صورت غیرقابل قبولی افزایش یابد. این فرایند به‌صورت مستقیم از مشخصه‌های الگویتم، ازجمله دمای اولیه، دمای نهایی و ضریب خنک‌سازی تبعیت می‌کند.

 

3-فرایند پیاده‌سازی پیشنهادی

در روش پیاده‌سازی توسعه داده شده‌ در این مقاله، ابتدا توصیف سخت‌افزاری وریلاگ مدار به سطح گیت تبدیل می‌شود. سپس گراف جهت‌دار مدار با استفاده از توصیف سطح گیت استخراج می‌شود. گراف مدار با استفاده از رهیافت فراابتکاری، به NL بخش (زیرگراف) با اندازة مساوی تقسیم می‌شود؛ به گونه‌ای که تعداد برش‌های بین آن‌ها کمینه باشد. سپس هر زیرگراف روی لایة مربوطه با استفاده از الگوریتم فرا‌ابتکاری SA جانشانی می‌شود. ایجاد اتصالات (سیم‌بندی‌های لازم در شبکه‌های موجود در لایه‌ها) در مرحلة مسیردهی انجام می‌شود.

شمای کلی روش پیشنهادی در شکل (3) نشان داده شده است. در ابتدا توصیف وریلاگ مدار مدنظر وارد فرایند می‌شود. در مرحلة دوم با استفاده از سنتزگر odin_II [23]، کد وریلاگ به یک توصیف سطح گیت تبدیل می‌شود. این سنتزگز، مستقل از فناوری و خروجی آن یک فایل BLIF[17] است. فایل BLIF از ورودی - خروجی‌های مدار و لیست گیت‌های تشکیل‌دهندة مدار ساخته شده است. برای هرکدام از گیت‌ها، اسامی پایه‌های ورودی و خروجی مشخص شده است که با استفاده از اسامی گره‌ها می‌توان گراف مدار را استخراج کرد. در گراف مدار، هرکدام از گیت‌ها نقش یک رأس را دارند و یال‌های خروجی هر رأس، به رأس‌هایی (گیت‌هایی) وصل می‌شوند که ورودی‌های هم‌نام با گیت مدنظر را دارند. همچنین، در فایل BLIF برای هرکدام از گیت‌ها با استفاده از جدول صحت (LUT)، نوع گیت‌ها (NAND, XOR, …) مشخص شده است.

در این پژوهش، از روش طراحی شبه - سفارشی[18] استفاده شده است که در آن سطح دوبعدی هر لایة تراشه به تعدادی سطر با ارتفاع یکسان تقسیم‌بندی می‌شود. گیت‌های منطقی استفاده‌شده در فایل BLIF مدار، در محدودة این سطرها پیاده‌سازی می‌شوند. بین دو سطر متوالی از سطح لایه، فضایی برای انجام مسیردهی در نظر گرفته می‌شود که کانال‌های مسیردهی نامیده می‌شوند.

خروجی مرحلة اول، گراف جهت‌دار مدار است که در مرحلة‌ بخش‌بندی استفاده می‌شود. زیرگراف‌های ایجادشده در مرحلة جانشانی و سپس مرحلة مسیردهی روی لایه‌ها پیاده‌سازی می‌شوند. نتیجة‌ نهایی فرایند، تولید دو فایل .place و .route برای هر لایه است که دربرگیرندة اطلاعات مربوط به چینش ماجول‌ها روی لایه‌ها و همچنین نحوة ایجاد اتصالات بین آنها است. در ادامه هرکدام از این مراحل تشریح می‌شوند.

 

شکل (3): نمایی از فلوی کلی روش پیشنهادی

 

 

 

1-3- بخش‌بندی

در حالت کلی هدف از بخش‌بندی، تقسیم یک گراف به دو یا چند زیرگراف است که این تقسیم‌بندی با اهدافی متفاوت و همچنین با الگوریتم‌های مختلفی می‌تواند صورت گیرد. در این مقاله، هدف از بخش‌بندی تولید NL زیرگراف به‌صورتی است که تا حد امکان کمترین ارتباط بین لایه‌ها (تعداد TSV) ایجاد شود و توازن در تعداد رأس‌های مربوط به زیرگراف‌ها به وجود آید.

در شکل (4)، دو بخش‌بندی متعادل (هرکدام از بخش‌ها شامل 4 رأس‌اند) نشان داده شده است. این بخش‌بندی‌ها براساس تعداد اتصالات ایجادشده بین دو بخش، بخش‌بندی بد (قسمت الف) و بخش‌بندی عالی (قسمت ب) نام‌گذاری شده‌اند. تعداد TSVهای لازم برای بخش‌بندی بد و بخش‌بندی عالی به‌ترتیب 8 و 2 است که نشان‌دهندة اهمیت بالای مرحلة بخش‌بندی در کاهش تعداد TSVها است.

همان‌طور که در بخش مقدمه اشاره شد، در فرایند پیاده‌سازی پیشنهادی، بخش‌بندی براساس الگوریتم فرا‌ابتکاری SA انجام می‌شود. شبه‌کد مربوطه، در الگوریتم (2) ارائه شده است. در این الگوریتم، ورودی یک گراف جهت‌دار با 2n رأس است (در صورتی که تعداد رئوس گراف مدار فرد باشد، یک رأس مجازی به آن اضافه می‌شود) و خروجی آن شامل فایل‌هایی است که بلوک‌های مربوط به هر لایه را دربردارد.

 

 

شکل (4): گراف G با دو رویکرد متفاوت در بخش‌بندی. در قسمت الف) سایز برش 8 است و در قسمت ب) سایز برش 2 است.

در خط 1، گراف ورودی به‌صورت تصادفی به NL بخش (لایه) تقسیم می‌شود. سپس تابع Setup() اجرا می‌شود. در خط سوم، مشخصه‌های الگوریتم مقداردهی می‌شوند. این مشخصه‌ها روی عملکرد الگوریتم بسیار تأثیرگذارند. در خط چهارم و پنجم، تابع هزینة اولیه برآورد می‌شود. در ادامه، اجرای حلقة اصلی (خط 6 تا 27) ادامه می‌یابد تا زمانی که شرط حلقه (خط 6) برقرار باشد و به محض نقض شرط حلقه یا عدم پیشرفت[19]، الگوریتم خاتمه می‌یابد. همان‌گونه که در شکل (5) دیده می‌شود، عدم پیشرفت زمانی رخ می‌دهد که تابع هزینه برای چند گام پیاپی بدون تغییر باقی بماند یا میزان تغییرات آن کم باشد. در این شرایط، به‌دلیل صرف زمان زیاد تا رسیدن به یک جواب مطلوب، بهتر است الگوریتم با جواب فعلی خاتمه یابد.

در هر گام دمایی، یک حلقة محلی با N  گام اجرا می‌شود (خط 8 تا 23). مقدار N، در خط 7 از الگوریتم تعیین می‌شود (Setting Local Parameters(alpha, N)).

در این حلقة محلی، در ابتدا تابع Selection() اجرا می‌شود. با اجرای این تابع، دو رأس برای جابه‌جایی بین دو یا چند لایه به‌صورت تصادفی انتخاب می‌شوند. در خط 10 و 11 تابع هزینة جدید ناشی از این جابه‌جایی و اختلاف آن با تابع هزینة فعلی محاسبه می‌شود. اگر این مقدار منفی باشد، یعنی جابه‌جایی انجام‌شده در راستای کاهش هزینه بوده است و این جابه‌جایی پذیرفته می‌شود (خط 12 تا 14)؛ اما اگر اختلاف بین تابع هزینة فعلی و تابع هزینة جدید منفی نباشد، با احتمال کمی جابه‌جایی پذیرفته می‌شود (خط 15 تا 19). هدف از این کار جلوگیری از گیرافتادن الگوریتم در مینیمم محلی (شکل 5) است. در ادامه توابع موجود در الگوریتم شرح داده می‌شوند.

شبه‌کد مربوط به تابع Setup() در الگوریتم (3) نشان داده شده است. گراف مدار توسط تابع دریافت می‌شود و اطلاعات لازم توسط سه زیرتابع Vertice_Gain()، Adjacency_matrix()، و Connectivity() استخراج می‌شوند.

در خط 1 با استفاده از تابع Vertice_Gain()، بهرة همه رأس‌های گراف محاسبه می‌شود. بهرة رأس i با استفاده از معادله (4) به دست می‌آید:

(4)

Di = Ei - Ii

 

الگوریتم (2): الگوریتم بخش‌بندی بر مبنای الگوریتم SA

Input: G (V, E)

Ensure: Optimized partitioned Graph to l tiers

 

1:   Randomly_partitioning( )

2:   Setup( )

3:   Setting parameters (T, Tmin)

4:   S       S­init

5:   CostCurrent       Cost(S)

6:   while T > Tmin

7:        Setting local parameters (alpha, N)

8:        for i = 0: N

9:            Selection(S’)

10:          Costnew       CostCurrent

11:          ∆Cost = Costnew - CostCurrent

12:          if (∆Cost < 0)

13:               S       S’          // updating

14                CostCurrent       Costnew

15:          else

16:                r        Rand (0, 1)

17:                if (r < exp(-∆Cost/T))

18:                     S       S’     // updating

19:                     CostCurrent       Costnew

20:                 end if

21:            end if

22:        end for

23:        if (stall)

24:            break;

25         else

26:            T = α × T

27:       endif

28:   end while

 

شکل (5): نمایی از مقادیر یک تابع هزینه در گذر زمان

 

الگوریتم (3-2): فاز Setup

Input: G (V, E)

Ensure: Extract the required data

1: Vertice_Gain( )

2: Adjacency_matrix( )

3: Connectivity( )

در این معادله، Ei ارزش خارجی[20] و Ii ارزش داخلی[21] برای رأس iام است. ارزش داخلی برای رأس i، برابر تعداد یال‌هایی است که این رأس با رأس‌های داخلی بخش مربوط به i دارد و ارزش خارجی رأس i برابر با تعداد یال‌هایی است که این رأس را به بخش‌های دیگر متصل می‌کنند.

با استفاده از تابع Adjacency_matrix()، ماتریس مجاورت برای گراف اصلی ساخته می‌شود. ماتریس مجاورت برای گراف G(V, E) با n رأس، ماتریسی متقارن با ابعاد n در n به شکل زیر است:

 

 

این ماتریس نقش مهمی در سرعت‌بخشیدن به الگوریتم دارد. با ایجاد این ماتریس، هنگام نیاز به محاسبة وزن یال‌های متصل بین دو رأس، بدون محاسبة‌ مجدد در هر تکرار و بدون درگیرکردن پردازنده در یک جستجوی طولانی، به وزن مدنظر می‌توان دست یافت.

بعد از این مرحله (در خط سوم)، تابع Connectivity() اجرا می‌شود. با اجرای این تابع، برای هر رأس یک لیست ایجاد می‌شود که نشان‌دهندة شماره رأس‌هایی است که به آن متصل‌اند. این تابع، باعث کاهش چشمگیر زمان اجرای الگوریتم (2)، در خطوط 13 و 18 می‌شود.

زمانی که دو رأس‌ از دو لایة مختلف (Vj و Vi) توسط تابع Selection() برای جابه‌جایی انتخاب می‌شوند، تابع هزینة مربوطه و اختلاف آن با تابع هزینة فعلی باید محاسبه شود تا مجاز بودن یا نبودن جابه‌جایی تعیین شود. برای محاسبة تابع هزینه، فرض کنید ارزش داخلی رأس‌های مربوطه، برابر با Ii و j و ارزش خارجی آنها برابر با Ei و Ej باشند، در این صورت تابع هزینه از معادله (4) به دست می‌آید که در آن Cij برابر با تعداد یال‌های مشترک بین دو رأس Vj و Vi است.

(4)

Cost = (Ii + Ij) – (Ei + Ej) + (2. Cij)

 

2-3- جانشانی و مسیردهی

مجموعه رأس‌های V1, V2, V3, … Vn و مجموعه مکان‌های P1, P2, P3, … Pk  (n ≤ k) را روی سطح تراشه در نظر بگیرید. مسئلة جانشانی یعنی اختصاص‌دادن بهترین مکان به هر رأس، به طوری که دو رأس در یک مکان یکسان قرار نگیرند [16]. کیفیت انجام جانشانی در تعیین مقدار سطح مصرفی و سرعت مدار پیاده‌سازی‌شده نقشی اساسی دارد.

مسئلة جانشانی ازنظر ریاضی، یک مسئلة NP-hard است. به همین دلیل، حل این مسئله با استفاده از الگوریتم‌های فرا‌ابتکاری، بهترین رهیافت ممکن است. در این مقاله، الگوریتم SA برای حل مسئلة جانشانی استفاده می‌شود.

با توجه به مشخص‌شدن گیت‌های هر لایه در مرحلة بخش‌بندی، فرایند جانشانی از لایة اول شروع می‌شود. ابتدا یک جانشانی به‌صورت کاملاً تصادفی تولید می‌شود. با توجه به طراحی نیمه‌سفارشی، گیت‌هایی که در هر ردیف جانمایی می‌شوند، ممکن است عرض‌های مختلفی داشته باشند؛ درحالی‌که ارتفاع همه آنها برابر است. سپس برای هر دما (T)، تعداد مشخصی جابه‌جایی تصادفی بین مکان گیت‌ها صورت می‌گیرد. اولین معیار برای پذیرفته‌‌شدن یک جابه‌جایی این است که پس از انجام جابه‌جایی، همپوشانی بین ناحیة اشغال‌شده توسط گیت‌ها ایجاد نشود. این همپوشانی معمولاً هنگامی به وجود می‌آید که یک گیت با عرض بزرگ‌تر با گیتی با عرض کوچک‌تر جابه‌جا می‌شوند.

در صورت نبود همپوشانی، پذیرفته‌شدن هر جابه‌جایی مشروط به مقدار تابع هزینة جانشانی در روابط (5) تا (7) است:

Cost_W3D =

(5)

Cost_T3D=  × t_p

(6)

Cost3D = V × Cost_T3D +

               (1 - V) × Cost_W3D

(7)

 

در رابطه (5)، xspan(n) و yspan(n) برابر با طول گذر در جهت X  و Y در Bounding Box کمینة مربوط به شبکه n است؛ برای مثال، در شکل (6) شبکة تشکیل‌شده از بلوک n و بلوک‌های متصل به آن نشان داده شده است.  XW, YW وزن‌هایی برای تعیین اولویت شبکه‌ها در بهینه‌سازی‌اند؛ برای مثال، شبکه‌های بحرانی دارای بالاترین اولویت‌اند و حداکثر مقدار XW و YW برای آنها لحاظ می‌شود. همچنین، K(n) مشخصه‌ای قابل تنظیم در الگوریتم است.

در رابطه (6)، متغیر  t_pضریب قابل تنظیم الگوریتم و delay (∆xij, ∆yij) مقدار تأخیر زمانی بین دو نقطه (x1 , y1) و (x2 , y2) را بیان می‌کند. میزان دقیق تأخیر زمانی، تنها بعد از انجام کامل مسیردهی محاسبه می‌شود؛ بنابراین، در مرحلة جانشانی، یک درخت استینر[22] [24] تقریبی بین منبع شبکه و مقاصد در نظر گرفته می‌شود. سپس براساس مدل تأخیر المور[23] [25] مقدار تأخیر تقریبی شبکه استخراج می‌شود. تابع هزینة کلی در رابطه (7) بیان شده است. ضریب V سهم هزینة زمان (Cost_T3D) و هزینة طول سیم (Cost_W3D) در تابع هزینة نهایی را تعیین می‌کند. اگر این ضریب، مقدار بزرگ (یعنی نزدیک به یک) داشته باشد، به تابع هزینة‌ زمان اهمیت بیشتری داده می‌شود. هچنین اگر این مقدار نزدیک به صفر باشد، هزینة طول سیم غالب خواهد شد. در الگوریتم پیشنهادی ما با آزمودن مقادیر متفاوت، این ضریب برابر با 7/0 در نظر گرفته شده است.

جانشانی لایه‌های بعدی، به‌ترتیب و با رویکردی مشابه انجام می‌گیرد. شایان ذکر است به زیرگراف لایة iام تعدادی رأس مجازی اضافه می‌شود که هرکدام بیان‌کنندة TSVهایی‌اند که بعد از جانشانی لایه‌های پایین‌تر وارد لایة i‌ام می‌شوند.

 

 

شکل (6): کمینه bounding box

در مرحلة آخر، اتصالات لازم بین بلوک‌های موجود، با استفاده از منابع و شبکة مسیردهی انجام می‌شود. در این مرحله، الگوریتم پیشنهادی بر مبنای الگوریتم‌ مسیریاب [13] گسترش داده شده است. این دسته از الگوریتم‌ها، از رهیافت پیداکردن کوتاه‌ترین مسیر[24] در تئوری گراف بهره می‌برند. هدف در این رهیافت، یافتن مسیری بین دو رأس از گراف است؛ به گونه‌ای که مجموع وزن یال‌های مربوطه به کمترین مقدار ممکن برسد. هستة اصلی الگوریتم پیشنهادی در حل مسئله کوتاه‌ترین مسیر، الگوریتم دایکسترا[25] [17] است.

تابع هزینة کلی در مرحلة مسیردهی، از رابطه (8) محاسبه می‌شود:

[1] Costn = Criticality (i, j) × delayn

(8)

Criticality (i, j) =

(9)

 

در این رابطه، Criticality از رابطه (9) محاسبه می‌شود که در آن، Dij برابر با ماکزیمم تأخیر مسیرِ ترکیبی از منبع i به مقصد j مربوط به شبکه n است و Dmax برابر با تأخیر مسیر بحرانی مدار است. در رابطه (8)، Delayn با تقریب بسیار خوب، از روش تأخیر المور محاسبه می‌شود. در مدل المور با توجه به طول سیم‌ها و ویژگی‌های الکتریکی آنها (مقدار مقاومت و اثر خازنی سیم‌ها)، بین منبع یک شبکة مسیردهی و مقاصد آن یک شبکة RC معادل ایجاد می‌شود و درنهایت با استفاده از قواعد توسعه داده شده توسط المور، تأخیر بین منبع و هرکدام از مقاصد محاسبه می‌شود. در مدل تأخیر المور، برای TSVها از رابطه (10) استفاده می‌کنیم:

DelayTSV=0.69(Rdown . Cdown) +

0.69(0.5(RTSV) + Rdown) CTSV +

0.69(RTSV+ Rup + Rdown) Cup

(10)

 

در این رابطه، Rup و Rdown مقاومت‌های لایة‌ بالایی و لایة پایینی در صورت وجود و Cup و Cdown خازن‌های لایة بالایی و لایة پایینی‌اند. CTSV خازن و RTSV مقاومت مربوط به TSV هستند. مطالعة موجود در [18] روی مدل الکتریکی TSVها نشان می‌دهد خازن مربوط به TSV (CTSV) بیشترین اثر را بر جای می‌گذارد. همچنین، چون حداکثر مقدار مقاومت TSV (RTSV) برابر با 1 اهم است [19]، می‌توان از مقاومت TSV در مقایسه با Rup و Rdown چشم‌پوشی کرد. خطوط انتقال سیگنال اصلی دارای عرض 500 نانومتر با گام‌های 1 میکرومتر در نظر گرفته شده‌اند. مشخصة اندازة امپدانس خطوط انتقال، در شکل (7) نشان داده شده است. مقادیر مقاومت و خازن به‌ترتیب برابر با 60 اهم بر میلی‌متر (60Ω/mm) و 200 پیکوفاراد بر میکرومتر (200 pf/µm) است.

 

 

شکل (7): مشخصة اندازة امپدانس برحسب فرکانس در خطوط انتقال

 

4- نتایج شبیه‌سازی

فرایند طراحی سه‌بعدی پیشنهادی با استفاده از زبان برنامه‌نویسی C++ در بستر لینوکس توسعه داده شده و روی پردازندة چهار هسته‌ای (9/2 گیگاهرتز) و حافظة RAM 8 گیگابایتی پیاده‌سازی شده است.

در این بخش، از مدارهای معیار MCNC برای اعتبارسنجی‌ شبیه‌سازی‌ها استفاده شده است. ویژگی‌های اصلی این مدارهای معیار، شامل تعداد ورودی - خروجی‌های اصلی و تعداد سلول‌ها (گیت‌های منطقی) در جدول (2) گزارش شده‌اند. یکی از ویژگی‌های سنتزگر ODIN_II امکان تعیین تعداد ورودی‌های گیت‌های منطقی استفاده‌شده در فایل BLIF است. برای انجام شبیه‌سازی‌ها از سه ساختار با گیت‌های 4 ورودی (4 K=)، 6 ورودی (6 K=) و 8 ورودی (8 K=) استفاده ‌شده است. با توجه به یکسان‌بودن ارتفاع گیت‌ها در سلول‌های استاندارد، عرض گیت‌ها با افزایش تعداد ورودی‌ها افزایش می‌یابد؛ بنابراین، مقایسة نتایج این سه نوع ساختار، تأثیر تغییر اندازة سلول‌ها را نشان می‌دهد. 

برای طراحی جانمایی[26] مربوط به گیت‌های منطقی اصلی (NAND, NOR, …) از ترانزیستورهای ساخته‌شده با فناوری 22 نانومتریِ PTM استفاده شده است. مشابه کار انجام‌شده در [26]، یک کتابخانة استاندارد برای گیت‌های پایه‌ای با تعداد ورودی‌های مختلف طراحی شده است. همان‌طور که پیش‌تر اشاره شد، این گیت‌های استاندارد دارای ارتفاع یکسان و عرض‌های متفاوت‌اند.

 محاسبة تأخیر انتشار هر گیت یک گام اساسی در انجام تحلیل زمانی است. با استفاده از مدل HSPICE برای ترانزیستورهای PTM [20] و با در نظر گرفتن طراحی گیت‌های پایه‌ای در سطح ترانزیستور، میزان تأخیرها با استفاده از شبیه‌سازی HSPICE محاسبه شده است؛ برای مثال، تأخیر هر گیت NAND دو ورودی به‌طور میانگین 40 پیکوثانیه است. در این نوع گیت، نسبت W/L برای ماسفت‌های نوع N و P به‌ترتیب برابر با 100:20 و 250:20 است.

همان‌طور که در بخش 3 اشاره شد، مدل‌سازی تأخیر برای مسیرها با استفاده از مدل RC و رهیافت المور انجام می‌گیرد. مشخصه‌های در نظر گرفته شده در شبیه‌سازی برای TSVها در جدول (1) آمده‌اند.

مشخصه‌های اصلی در الگوریتم SA عبارت‌اند از ضریب خنک‌کنندگی α، دمای نهایی (Tmin) و مقدار دمای اولیه (T0). این مشخصه‌ها باید متناسب با اندازه و پیچیدگی مسئله و توسط کاربر تعیین شوند. انتخاب بهینة این مشخصه‌ها، نقشی اساسی در عملکرد الگوریتم SA و ایجاد مصالحه بین سرعت اجرا و کیفیت نتایج دارد. برای تعیین مقدار مشخصه‌های α و T0 در فاز بخش‌بندی، شبیه‌سازی‌های متعددی انجام شده است. نتایج شبیه‌سازی‌ها در شکل‌های (8) تا (11) نشان داده شده‌اند. در این نمودارها محور عمودی، میزان بهبود در تعداد TSV و زمان اجرا را در مدارهای معیار با K=6 نشان می‌دهد. همچنین در نمودارهای 10 و 11، C برابر اندازة بلوک‌ها یا سلول‌های استاندارد در مدار معیار است.

درصد کاهش تعداد TSVها، با افزایش مقدار ضریب خنک‌کنندگی روندی افزایشی دارد. دلیل این امر افزایش تعداد دورهای الگوریتم (افزایش تعداد گام‌های دمایی) با افزایش α است که به یافتن جواب‌های بهتری توسط الگوریتم SA منجر می‌شود. زمان اجرا با افزایش α روندی افزایشی دارد و دلیل آن، اجرای حلقة داخلی الگوریتم SA به تعداد دفعات بیشتر است. روند افزایشی نمودار کاهش تعداد TSVها (شکل 8) و روند نزولی نمودار بهبود زمان اجرا (شکل 9) در 9/0 = α تلاقی می‌کنند.

 مشخصة مهم دیگر، مقدار دمای اولیه (T0) است که براساس تعداد گیت‌های مدار (C) بیان می‌شود. با افزایش دمای اولیه مقدار کاهش در تعداد TSVهای مورد نیاز، روندی افزایشی دارد. دلیل این روند را می‌توان در افزایش تعداد گام‌های دمایی در صورت انتخاب مقدار T0 بزرگ دانست که به یافتن جواب‌های بهتر توسط الگوریتم SA منجر می‌شود. همچنین، همین امر منجر به صرف زمان بیشتری توسط الگوریتم برای رسیدن به جواب نهایی خواهد شد. روند افزایشی نمودارِ کاهش تعداد TSVها (شکل 11) و روند کاهشی نمودار بهبود زمان اجرا (شکل 10) در C = T0 تلاقی می‌کنند؛ بنابراین، بهترین مقادیر ممکن برای α و T0 به‌ترتیب برابر 9/0 وC  هستند.

با انجام شبیه‌سازی‌های مشابه، مشخصه‌های الگوریتم SA در فاز جانشانی به‌صورت زیر به دست آمده‌اند: ضریب خنک‌کنندگی α برابر 95/0، Tmin (دمای نهایی) برابر 1/0 و مقدار T0 (دمای اولیه) برابر با ربع تعداد سلول‌های هر مدار (ستون آخر از جدول 2).

 

جدول (1) مشخصه‌های مدل TSV

Resistance                    0.35 Ω

Capacitance                 3 fF

Diameter                      2 µm

Pitch                             4 µm

Height                          20 µm

 

شکل (8): میزان وابستگی تعداد TSVها به ضریب α

 

شکل (9): میزان وابستگی زمان اجرا به ضریب α

 

شکل (10): میزان وابستگی زمان اجرا به مشخصة T0

 

شکل (11): میزان وابستگی تعداد TSVها به مشخصة T0

 

برای انجام مقایسه، دو روش پیاده‌سازی تراشه‌های سه‌بعدی براساس الگوریتم‌های بخش‌بندی FSA و hMetis در نظر گرفته شده‌اند. روش بخش‌بندی hMetis، به‌عنوان یک روش استاندارد در نرم‌افزارهای طراحی تراشه‌های دوبعدی کاربرد وسیعی دارد. همچنین، روش FSA با توجه به سرعت و نتایج قابل قبول، در بخش‌بندی تراشه‌های سه‌بعدی درخور توجه پژوهشگران قرار گرفته است؛ بنابراین، مقایسة عملکرد روش پیشنهادی با این دو روش، مزیت‌های آن را به وضوح بیان می‌کند.

نتایج مربوط به کاهش تعداد TSVها و همچنین کاهش زمان اجرا در مقایسة روش بخش‌بندی پیشنهادی با روش FSA، در جدول‌های (3، 4 و 5) گزارش شده‌اند. این جدول‌ها به‌ترتیب برای حالت‌هایی است که سنتزگر ODIN_II تعداد ورودی‌های مجاز گیت‌های مدار را به‌ترتیب 4 (K=4)، 6 (K=6) و 8 (K=8) در نظر گرفته است.

در ستون آخر از جدول‌های (3، 4 و 5) میزان بهبود پارامترهای زمان اجرا و تعداد TSVها برای هرکدام از مدارها نشان داده شده است. همان‌طور که دیده می‌شود، در جدول (3) فقط در دو مدار معیار {elliptic, ex5p} تعداد TSVها بهبود نیافته‌اند. میزان بهبود متوسط در این مدارها، 24/6 درصد برای TSVها و 64/27 درصد برای زمان اجرا است.

 

جدول (2): مشخصات مدارهای معیار MCNC با استانداردهای مختلف

Circuit

I/O

Cell #

K = 8               K = 6       K = 4

ex5p

71

76               748             1072

des

501

787             810             1847

alu4

22

807             1187           1536

tseng

174

1187           1233           1482

diffeq

103

1211           1308           1934

seq

76

1150           1366           1791

apex2

42

1275           1517           1917

bigkey

460

1395           1177           2193

ex1010

20

850             3103           4608

elliptic

245

3428           3385           4854

s38417

135

4039           4583           7587

s38584.1

343

4041           5461           7579

clma

465

5445           7102           8769

 

در جدول (4)، در همه مدارهای معیار بهبود وجود دارد که میانگین آن، 15/6 درصد برای TSV و 79/27 درصد برای زمان اجرا است. همان‌طور که در جدول (5) مشخص شده است، تنها در یک مورد در تعداد TSVها بهبودی حاصل نشده است. ضمن اینکه در حالت کلی، 49/5 درصد برای تعداد TSVها و 99/23 درصد برای زمان اجرا بهبود مشاهده می‌شود. به‌طور میانگین، الگوریتم پیشنهادی نسبت به روش FSA به اندازة 15/6 درصد از تعداد TSVها کاسته (که قطعاً به کاهش مساحت هم منجر می‌شود) و زمان اجرای الگوریتم به میزان چشمگیری (79/27 درصد) کاهش یافته است.

از مقایسة تعداد TSVهای لازم برای پیاده‌سازی هرکدام از مدارهای معیار از جدول‌های 3 تا 5 می‌توان دریافت با افزایش اندازة گیت‌ها از 4 ورودی به 8 ورودی، تعداد اتصالات بین لایه‌ها روندی کاهشی دارد. دلیل این امر کاهش اندازة مدار سنتزشده ازنظر تعداد گیت‌ها و در پی آن کاهش تعداد یال‌ها در گراف مدار است. نکتة دیگر مربوط به کاهش زمان اجرای الگوریتم‌های بخش‌بندی با افزایش اندازة گیت‌های پایه‌ای است. دلیل اصلی این رفتار، کاهش اندازة گراف مدار و کمترشدن پیچیدگی فضای جستجوی الگوریتم SA است.

در الگوریتم ابتکاری hMetis [21]، گراف مدار ابتدا براساس کاهش تعداد اتصالات مشترک به دو زیرگراف تقسیم می‌شود. سپس طی چند مرحله‌ همین فرایند دوبخشی‌کردن برای زیرگراف‌ها تکرار می‌شود تا زیرگراف‌هایی شامل تنها دو رأس تولید شوند. در فاز دوم، زیرگراف‌های تولیدشده به‌گونه‌ای با هم ادغام می‌شوند که هدف اصلی بخش‌بندی (ساختن دو بخش با کمترین اتصال مشترک) محقق شود. فرایند بخش‌بندی در الگوریتم hMetis براساس بخش‌بندی به دو گراف است که می‌توانند اندازه‌های متفاوت داشته باشند. کیفیت نتیجة الگوریتم به میزان زیادی به کیفیت جستجو در فاز بازترکیب زیرگراف‌ها وابسته است.

در جدول (6)، الگوریتم بخش‌بندی پیشنهادی با الگوریتم hMetis، با استاندارد 6 ورودی (K = 6) مقایسه شده است. زمان اجرا به میزان 73/31 درصد و تعداد TSVها به میزان 78/9 درصد کاهش یافته‌اند. الگوریتم بخش‌بندی hMetis در مقایسه با الگوریتم پیشنهادی و الگوریتم FSA (جدول 4) که هردو بر مبنای الگوریتم SA توسعه یافته‌اند، از لحاظ کاهش تعداد TSV، عملکرد بدتری دارد. دلیل این امر را در قدرت جستجوی بسیار بهتر الگوریتم SA نسبت به الگوریتم ابتکاری به‌کاررفته در hMetis می‌توان دانست. زمان اجرای الگوریتم hMetis نیز به‌دلیل پیچیده‌بودن فرایند تبدیل هر گراف به دو زیرگراف و نیز جستجو برای ادغام بهینة زیرگراف‌ها، به میزان چشمگیری از الگوریتم پیشنهادی بیشتر است.

در جدول (7)، جانشانی و مسیردهی رهیافت FSA و فرایند پیشنهادی این مقاله از نقطه‌نظر تأخیر مسیر بحرانی[27] (CPD) مقایسه شده‌اند. مسیر بحرانی در پیاده‌سازی یک مدار مجتمع دیجیتال، مسیری از یک ورودی اصلی به یک خروجی اصلی است که انتشار تغییرات سیگنال (0 به 1 یا 1 به 0) در آن از سایر مسیرها بیشتر است. پس از انجام مسیردهی، برای محاسبة تأخیر مسیر بحرانی، مقدار تأخیر مسیر بین خروجی گیت‌های منبع و ورودی گیت‌های مقصد با استفاده از مدل المور محاسبه می‌شود. سپس گراف وزن‌دار مدار ساخته می‌شود که در آن تأخیر از ورودی به خروجی گیت‌ها و تأخیر مسیر بین گیت‌ها به‌صورت وزن یال‌های گراف در نظر گرفته می‌شوند. الگوریتم تحلیل زمانی، این گراف را با شروع از ورودی‌های اصلی و عبور از یال‌ها و رأس‌ها سطح به سطح طی می‌کند. در طی این فرایند، حداکثر تأخیر برای رسیدن سیگنال به هرکدام از رأس‌ها مشخص می‌شود. در مرحلة آخر، با فرایند بازگشت به عقب از خروجی اصلیِ با بیشترین زمان تأخیر به سمت ورودی‌ها، مسیر با بیشترین تأخیر شناسایی می‌شود.

نتایج جدول 7 نشان می‌دهند تأخیر مسیر بحرانی در روش پیاده‌سازی پیشنهادی نسبت به FSA، برای حالت‌های K=4، K=6 و K=8 به‌ترتیب به میزان 11/8، 44/10 و 58/11 درصد کاهش یافته است. دلیل اصلی این کاهش را در کیفیت بهتر مرحلة بخش‌بندی و توجه به میزان تأخیر شبکه‌ها در مرحلة جانشانی و مسیردهی در الگوریتم پیشنهادی می‌توان مرتبط دانست. با افزایش اندازة سلول‌های استاندارد از K=4 تا K=8 میزان تأخیر مسیر بحرانی کاهش چشمگیری دارد. دلیل این امر کاهش تعداد گیت‌ها و به تبع آن کاهش پیچیدگی شبکة مسیردهی است.

 

5- نتیجه‌گیری

در این مقاله، الگوریتم‌های بخش‌بندی، جانشانی و مسیردهی، با هدف پیاده‌سازی مدارهای مجتمع روی تراشه‌های سه‌بعدی ASIC گسترش‌ داده شده‌اند. در فاز بخش‌بندی نسبت به روش FSA، تعداد TSVها به اندازة 15/6 درصد و زمان اجرا به میزان 79/27 درصد کاهش داشته است. همچنین، نسبت به الگوریتم بخش‌بندی hMetis به اندازة 78/9 درصد کاهش در تعداد TSVها صورت گرفته است؛ در‌ حالی که الگوریتم پیشنهادی به میزان 73/31 درصد سریع‌تر عمل می‌کند. در فاز جانشانی و مسیردهی، الگوریتم پیشنهادی نسبت به FSA به‌صورت میانگین به اندازة 44/10 درصد به مدار سرعت بخشیده است.

 

 

جدول (3): مقایسة روش FSA و روش پیشنهادی با استاندارد 4 ورودی (K = 4)، از نقطه‌نظر زمان اجرا و تعداد TSV

Circuit

FSA

Proposed

Improvement (%)

TSV#      Time (MS)

TSV#    Time (MS)

TSV#            Time

ex5p

139              457

134              381

3.59                16.63

des

182              1673

177              1375

2.74                17.81

alu4

268              1718

256              1197

4.47                30.32

tseng

162              1648

169              973

-4.32               40.95

diffeq

189              1861

177              1498

6.34                19.50

seq

257              1807

246              1307

4.28                27.67

apex2

152              1592

134              1201

11.84              24.56

bigkey

227              2173

215              1564

5.28                28.02

ex1010

365              4951

341              3750

6.57                24.25

elliptic

458              5432

429              4002

6.33                26.32

s38417

319              8724

280              6825

12.22              21.76

s38584.1

486              8640

455              6638

6.37                23.17

clma

897              9347

863              7309

3.79                21.80

Avg

 

 

5.49                23.99

 

جدول (4): مقایسة روش FSA و روش پیشنهادی با استاندارد 6 ورودی (K = 6)، از نقطه‌نظر زمان اجرا و تعداد TSV

Circuit

FSA

Proposed

Improvement (%)

TSV#      Time (MS)

TSV#    Time (MS)

TSV#            Time

ex5p

44                 401

42                 247

4.54                  38.40

des

91                 635

86                 413

5.49                  34.96

alu4

109               1230

102               927

6.42                  24.63

tseng

218               1185

209               862

4.12                  27.25

diffeq

157               1602

144               1086

8.28                  32.21

seq

206               1417

202               958

1.94                  32.39

apex2

153               1792

151               1201

1.30                  32.97

bigkey

219               1342

208               944

5.02                  29.65

ex1010

324               3524

305               2413

5.86                  31.52

elliptic

458               3786

427               2897

6.76                  23.48

s38417

207               4937

185               3815

10.62                22.72

s38584.1

258               5761

239               4239

7.36                  26.41

clma

758               9173

705               6558

6.99                  28.51

Avg

 

 

6.15                  27.79

جدول (5): مقایسة روش FSA و روش پیشنهادی با استاندارد 8 ورودی (K = 8)، از نقطه‌نظر زمان اجرا و تعداد TSV

Circuit

FSA

 

Proposed

Improvement (%)

TSV#       Time (MS)

 

TSV#      Time (MS)

TSV#              Time

ex5p

32                 165

 

35                 89

-9.37               46.06

des

110               438

 

103               354

6.36                19.17

alu4

97                1095

 

81                 836

16.49              23.65

tseng

248              1136

 

235               718

5.24                36.79

diffeq

234              1307

 

213               891

8.97                31.82

seq

226              1183

 

209               872

7.52                26.28

apex2

91                1376

 

88                 1008

3.29                26.74

bigkey

199              1270

 

186               982

1.50                22.67

ex1010

294              1073

 

279               814

5.10                24.13

elliptic

463              4157

 

478               3016

-3.24               27.44

s38417

215              5032

 

197               4211

8.37                16.31

s38584.1

321              5268

 

298               3957

7.16                24.88

clma

1106            8241

 

997               5218

+9.85              36.68

Avg

 

 

 

6.24               27.64

 

 

جدول (6): مقایسة الگوریتم hMetis از نقطه‌نظر زمان اجرا و تعداد TSV

Circuit

hMetis

Proposed

Improvement (%)

TSV#      Time (MS)

TSV#    Time (MS)

TSV#               Time

ex5p

53                 462

42                 247

20.75                 46.53

des

98                 670

86                 413

12.24                 38.35

alu4

117               1403

102               927

12.82                 33.92

tseng

234               1109

209               862

10.68                 22.27

diffeq

163               1761

144               1086

11.65                 38.33

seq

213               1502

202               958

5.16                   36.21

apex2

169               1863

151               1201

10.65                 35.53

bigkey

228               1417

208               944

8.77                   33.38

ex1010

337               3623

305               2416

9.49                   33.39

elliptic

456               3679

427               2897

6.35                   21.25

s38417

216               5135

185               3815

14.35                 25.70

s38584.1

271               6034

239               4239

11.80                 29.74

clma

776               10248

705               6558

9.14                   36.01

Avg

 

 

9.78                   31.73

 

 

 

 

 

 

جدول (7): مقایسة خروجی اعمال‌شده به فاز جانشانی و مسیردهی حاصل از خروجی بخش‌بندی ناشی از الگوریتم پیشنهادی و الگوریتم FSA

Circuit

Proposed

FSA

CPD (ns)

CPD (ns)

 

K = 8

K = 6

K = 4

K = 8

K = 6

K = 4

ex5p

1.51

2.75

6.79

1.72

2.53

5.84

des

2.48

2.83

5.94

2.94

3.27

6.37

alu4

3.67

4.09

6.21

4.29

4.52

7.93

tseng

3.21

4.57

5.06

3.06

4.77

6.32

diffeq

4.16

4.51

6.12

4.34

4.64

6.28

seq

4.32

4.34

6.71

4.25

4.31

7.08

apex2

5.07

4.89

6.93

5.22

4.73

7.49

bigkey

3.61

2.93

4.69

4.57

3.82

5.26

ex1010

4.49

7.59

8.78

4.38

8.71

7.68

elliptic

6.12

6.64

8.94

6.78

6.47

9.51

s38417

4.26

5.62

7.79

5.89

6.39

9.07

s38584.1

3.74

5.16

6.84

5.10

7.26

8.14

clma

6.43

9.14

8.86

7.48

11.23

10.61

Avg

4.08

5.01

6.89

4.61

5.58

7.50

Imp (%)

11.58

10.44

8.11

     

 

 

 

[1] تاریخ ارسال مقاله: 27/10/1399

تاریخ پذیرش مقاله: 17/05/1400

نام نویسندۀ مسئول: هادی جهانی‌راد

نشانی نویسندۀ مسئول: ایران - سنندج - دانشگاه کردستان - دانشکده مهندسی - گروه مهندسی برق

 

[1] Interconnect Delays

[2] 3D Integrated Circuits

[3] Through Silicon Via

[4] Simulated Annealing

[5] Pathfinding

[6] Stack

[7] Manhattan distance

[8] Reliable

[9] Cost effective

[10] filler material

[11] Polycrystalline silicon

[12] Nano-interconnects Graphene-based

[13]  Pitch

[14] Cut-size

[15] Place and Route

[16] Net

[17] Berkeley Logic Interchange Format

[18] Semi-Custom

[19] Stall

[20] External Cost

[21] Internal Cost

[22] Steiner Tree

[23] Elmore Delay Model

[24] Shortest path

[25] Dijkstra

[26] Layout

[27] Critical Path Delay

[1] Moore, G. E., , “Cramming More Components On to Integrated Circuits”, Electronics Magazine, Vol. 38, No. 8, April 1965.
International Technology Roadmap for Semiconductors (ITRS). 2015 edition. [online], available: https://www.dropbox.com/sh/3jfh5fq634b5yqu/AADYT8V2Nj5bX6C5q764kUg4a?dl=0
[2] Jahanirad, H., “Efficient reliability evaluation of combinational and sequential logic circuits”, J Comput Electron, Vol. 18, No. 1, March 2019.
[3] Jahanirad, H.,”CC-SPRA: Correlation coefficients approach for signal probability-based reliability analysis”. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 27, No. 4, April 2019.
[4] Sharma, R., “Design of 3D integrated circuits and systems”, CRC Press, 2014.
[5] Ababei, C., Yan Feng, Goplen, B., Mogal, H., Tianpei Zhang, Bazargan, K., & Sapatnekar, S., “Placement and Routing in 3D Integrated Circuits”, IEEE Design and Test of Computers, Vol. 22, No. 6,  April 2005.
[6] Cuesta, D., Risco-Martin, J.L., Ayala, J.L. and Hidalgo, J.I., “3D thermal-aware floorplanner using a MOEA approximation”,  Integration, Vol. , No. 1, Januray 2013.
[7] Saha, D., and Sur-Kolay, S., “Guided GA-Based Multiobjective Optimization of Placement and Assignment of TSVs in 3-D ICs”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 27, No. 8, April 2019.
[8] Meitei, N.Y., Baishnab, K.L. and Trivedi, G., “3D-IC partitioning method based on genetic algorithm”, IET Circuits, Devices & Systems, Vol. 14, No. 7, November 2020.
[9] Sait, S.M., Oughali, F.C. and Al-Asli, M., “Design partitioning and layer assignment for 3D integrated circuits using tabu search and simulated annealing”, Journal of applied research and technology, Vol. 14, No. 1, Februrey 2016.
[10] Fakheri Tabrizi, A., Behjat, L., Swartz, W., & Rakai, L., “A fast force-directed simulated annealing for 3D IC partitioning”, Integration, the VLSI Journal, Vol. 55, No. 1, September 2016.
[11] Siddique, N., & Adeli, H., “Simulated Annealing, Its Variants and Engineering Applications”, International Journal on Artificial Intelligence Tools, Vol. 25, No. 6, December 2016.
[12] McMurchie, L., Ebeling, C., “PathFinder: a negotiation based performance driven router for FPGAs”, in Conference of Field Programmable Gate Arrays FPGA, pp. 291–301, 1995.
[13] Lee, M., Pak, J. S., & Kim, J., “Electrical Design of Through Silicon Via”, Springer, 2014.
[14] Kaushik, B. K., Majumder, M. K., and Kumari, A., “Fabrication and Modelling of Copper and Carbon Nanotube Based Through-Silicon Via, Design of 3D Integrated Circuits and Systems”. CRC Press/Taylor & Francis Group, 2014.
[15] Sherwani, N., “Algorithms for VLSI Physical Design Automation”, Springer Science & Business Media, 2012..
[16] Gbadamosi, O. A. and Aremu, D. R., "Design of a Modified Dijkstra’s Algorithm for finding alternate routes for shortest-path problems with huge costs.", International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS), pp. 1-6, 2020.
[17] Lau, J.H., “Heart and Soul of 3D IC Integration”, posted at 3D InCites on June 2010.
[18] Bamberg, L., & Garcia-Ortiz, A., “ High-Level Energy Estimation for Submicrometric TSV Arrays”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 25, No. 10, June 2017.
[19] Predictive technology model, available [online] : http://ptm.asu.edu/latest.html.
[20] Karypis, G., Aggarwal, R., Kumar, V., & Shekhar, S., “Multilevel hypergraph partitioning: applications in VLSI domain”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 7, No. 1, March 1999.
[21] Nvidia Ampere architecture, (May 2020), available [online] : https://www.nvidia.com/en-gb/data-center/nvidia-ampere-gpu-architecture/.
[22] Jamieson,P., Kent,K., Gharibian,F., and Shannon, L., “Odin ii-an open-source verilog hdl synthesis tool for cad research”, In International Symposium on Field-Programmable Custom Computing Machines, pp. 149–156. 2010.
[23] Jahanirad, H., Mohammadi, K., “Reliable Implementation on SRAM-based FPGA using Evolutionary Methods”, IETE Journal of Research, Vol. 59, No. 5, September 2013.
[24] Rabaey, J. M., Chandrakasan, A. P., & Nikolić, B., “Digital integrated circuits: a design perspective”,  Pearson education 2003.
[25] Østerhus, S., “Subthreshold CMOS Cell Library by 22 nm FDSOI Technology”, MS thesis. NTNU, 2018.