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
Keywords
در گذار از یک نسل تراشههای مجتمع دیجیتال به نسل بعد، همواره سعی بر آن است که براساس قانون مور [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].
در ادامة مقاله، در بخش دوم پیشنیازهای لازم و در بخش سوم، روش پیشنهادی بیان شده است. در بخش چهارم، نتایج حاصل از روش پیادهسازی بررسی شده و در بخش پنجم، نتیجهگیری مربوط به این تحقیق بیان شده است.
در این بخش ساختار مدارهای مجتمع سهبعدی و ساختار TSVها بهصورت اجمالی معرفی میشوند. توضیحاتی دربارة بخشبندی، جانشانی و مسیردهی ارئه خواهند شد و درنهایت الگوریتم SA معرفی میشود.
ساختار کلی یک مدار مجتمع سهبعدی در شکل (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 Sinit 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 Sinit 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 و Ij و ارزش خارجی آنها برابر با 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): مشخصة اندازة امپدانس برحسب فرکانس در خطوط انتقال
فرایند طراحی سهبعدی پیشنهادی با استفاده از زبان برنامهنویسی 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 میزان تأخیر مسیر بحرانی کاهش چشمگیری دارد. دلیل این امر کاهش تعداد گیتها و به تبع آن کاهش پیچیدگی شبکة مسیردهی است.
در این مقاله، الگوریتمهای بخشبندی، جانشانی و مسیردهی، با هدف پیادهسازی مدارهای مجتمع روی تراشههای سهبعدی 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