• مقدمه[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ها انجام می‌شود.

پیاده‌سازی مدارهای منطقی روی تراشه‌های سه‌بعدی با تعداد N_L لایة فعال، در سه مرحله انجام می‌شود. ابتدا مدار مدنظر به N_L بخش‌ مساوی تقسیم می‌شود. سپس هرکدام از بخش‌ها روی یک لایه پیاده‌سازی می‌شوند. پیاده‌سازی روی لایه‌ها در دو مرحلة جانشانی (انتساب گیت‌ها به مکان‌هایی روی سطح لایه) و مسیردهی (ایجاد سیم‌بندی‌های لازم بین گیت‌ها) انجام می‌شود. از منظر پیچیدگی محاسباتی هر سه مرحلة‌ بخش‌بندی، جانشانی و مسیردهی از نوع مسائل 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)

 

در این معادله، h_TSV برابر با ارتفاع 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 = {v₁, v₂, v₃, … , v_n} مجموعه رأس‌ها و E = {e₁, e₂ , e₃, … , e_n} مجموعه یال‌ها هستند. در مسئلة بخش‌بندی، هدف تقسیم‌کردن مجموعه رأس‌های V از گراف G(V, E) به k زیرگراف V₁, V₂, V₃, … V_k است؛ به طوری که داشته باشیم:

|V₁| = |V₂| = … = |V_k|,

V_i ∩ V_j = Φ,   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

 

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

 

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

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

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

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

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

 

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

 

 

 

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

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

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

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

 

 

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

در خط 1، گراف ورودی به‌صورت تصادفی به N_L بخش (لایه) تقسیم می‌شود. سپس تابع 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( )

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

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

 

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

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

زمانی که دو رأس‌ از دو لایة مختلف (V_j و V_i) توسط تابع Selection() برای جابه‌جایی انتخاب می‌شوند، تابع هزینة مربوطه و اختلاف آن با تابع هزینة فعلی باید محاسبه شود تا مجاز بودن یا نبودن جابه‌جایی تعیین شود. برای محاسبة تابع هزینه، فرض کنید ارزش داخلی رأس‌های مربوطه، برابر با I_i و I­_j و ارزش خارجی آنها برابر با E_i و E_j باشند، در این صورت تابع هزینه از معادله (4) به دست می‌آید که در آن C_ij برابر با تعداد یال‌های مشترک بین دو رأس V_j و V_i است.

(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) مقدار تأخیر زمانی بین دو نقطه (x₁ , y₁) و (x₂ , y₂) را بیان می‌کند. میزان دقیق تأخیر زمانی، تنها بعد از انجام کامل مسیردهی محاسبه می‌شود؛ بنابراین، در مرحلة جانشانی، یک درخت استینر^[22] [24] تقریبی بین منبع شبکه و مقاصد در نظر گرفته می‌شود. سپس براساس مدل تأخیر المور^[23] [25] مقدار تأخیر تقریبی شبکه استخراج می‌شود. تابع هزینة کلی در رابطه (7) بیان شده است. ضریب V سهم هزینة زمان (Cost_T_3D) و هزینة طول سیم (Cost_W_3D) در تابع هزینة نهایی را تعیین می‌کند. اگر این ضریب، مقدار بزرگ (یعنی نزدیک به یک) داشته باشد، به تابع هزینة‌ زمان اهمیت بیشتری داده می‌شود. هچنین اگر این مقدار نزدیک به صفر باشد، هزینة طول سیم غالب خواهد شد. در الگوریتم پیشنهادی ما با آزمودن مقادیر متفاوت، این ضریب برابر با 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)، Delay_n با تقریب بسیار خوب، از روش تأخیر المور محاسبه می‌شود. در مدل المور با توجه به طول سیم‌ها و ویژگی‌های الکتریکی آنها (مقدار مقاومت و اثر خازنی سیم‌ها)، بین منبع یک شبکة مسیردهی و مقاصد آن یک شبکة RC معادل ایجاد می‌شود و درنهایت با استفاده از قواعد توسعه داده شده توسط المور، تأخیر بین منبع و هرکدام از مقاصد محاسبه می‌شود. در مدل تأخیر المور، برای TSVها از رابطه (10) استفاده می‌کنیم:

DelayTSV=0.69(Rdown . Cdown) + 0.69(0.5(RTSV) + Rdown) CTSV + 0.69(RTSV+ Rup + Rdown) Cup

(10)

 

در این رابطه، R_up و R_down مقاومت‌های لایة‌ بالایی و لایة پایینی در صورت وجود و C_up و C_down خازن‌های لایة بالایی و لایة پایینی‌اند. C_TSV خازن و R_TSV مقاومت مربوط به TSV هستند. مطالعة موجود در [18] روی مدل الکتریکی TSVها نشان می‌دهد خازن مربوط به TSV (C_TSV) بیشترین اثر را بر جای می‌گذارد. همچنین، چون حداکثر مقدار مقاومت TSV (R_TSV) برابر با 1 اهم است [19]، می‌توان از مقاومت TSV در مقایسه با R_up و R_down چشم‌پوشی کرد. خطوط انتقال سیگنال اصلی دارای عرض 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 عبارت‌اند از ضریب خنک‌کنندگی α، دمای نهایی (T_min) و مقدار دمای اولیه (T₀). این مشخصه‌ها باید متناسب با اندازه و پیچیدگی مسئله و توسط کاربر تعیین شوند. انتخاب بهینة این مشخصه‌ها، نقشی اساسی در عملکرد الگوریتم SA و ایجاد مصالحه بین سرعت اجرا و کیفیت نتایج دارد. برای تعیین مقدار مشخصه‌های α و T₀ در فاز بخش‌بندی، شبیه‌سازی‌های متعددی انجام شده است. نتایج شبیه‌سازی‌ها در شکل‌های (8) تا (11) نشان داده شده‌اند. در این نمودارها محور عمودی، میزان بهبود در تعداد TSV و زمان اجرا را در مدارهای معیار با K=6 نشان می‌دهد. همچنین در نمودارهای 10 و 11، C برابر اندازة بلوک‌ها یا سلول‌های استاندارد در مدار معیار است.

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

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

با انجام شبیه‌سازی‌های مشابه، مشخصه‌های الگوریتم SA در فاز جانشانی به‌صورت زیر به دست آمده‌اند: ضریب خنک‌کنندگی α برابر 95/0، T_min (دمای نهایی) برابر 1/0 و مقدار T₀ (دمای اولیه) برابر با ربع تعداد سلول‌های هر مدار (ستون آخر از جدول 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,362

تعداد دریافت فایل اصل مقاله: 244