Электрондық тізбектерді жобалауда компоненттерді орналастыру кезеңі

Кіріспе

Электрондық схемаларды жобалау сатысы

Орналастыру – электрондық дизайнды автоматтандырудың маңызды қадамы – физикалық жобалау ағынының чиптің негізгі аймағындағы әртүрлі схемалық компоненттерге нақты орындарды тағайындайтын бөлігі. Орналастырудың нашар тағайындалуы чиптің өнімділігіне ғана емес, сонымен қатар қол жетімді маршруттау ресурстарынан асып түсетін, артық сым ұзындығын тудырып, оны өндіруге жарамсыз етуі мүмкін. Сондықтан, пласер схеманың талаптарына сәйкес келетініне көз жеткізу үшін бірнеше мақсатты оңтайландыру арқылы тағайындауды жүзеге асыруы керек. Интегралды схеманы (IC) жобалаудың орналастыру және маршруттау қадамдары жиынтысы «орналастыру және маршруттау» деп аталады. Пласер берілген синтезделген схемалық желілік тізімді және технологиялық кітапхананы қабылдап, жарамды орналастыру макетін жасайды. Бұл макет жоғарыда аталған мақсаттарға сәйкес оңтайландырылады және уақыт және сигнал тұтастығын қамтамасыз ету үшін маңызды қадам – жасуша өлшемдерін өзгертуге және буферлеуге дайын болады. Сағат ағашының синтезі және маршруттау физикалық жобалау процесін аяқтайды. Көптеген жағдайларда, физикалық жобалау ағынының бөліктері немесе толығымен жобалау аяқталғанға дейін бірнеше рет қайталанады.

Қолдану ерекшеліктері

Қолданбаға арналған арнайы интегралдық схемалар, немесе ASIC-тер жағдайында, чиптің негізгі орналасу аймағы бірнеше белгілі бір биіктіктегі қатарлардан тұрады, олардың арасында белгілі бір мөлшерде немесе еш бос орын болмайды. Әрбір қатар схема компоненттерімен толтырыла алатын орындардан құралады. Бос орын – ешқандай компонентпен толтырылмаған орын. Схема компоненттері стандартты элементтер, макроблоктар немесе кіріс-шығыс тіректері (I/O) болып табылады. Стандартты элементтердің биіктігі қатардың биіктігімен тең, ал ені өзгеріп отырады. Элементтің ені – орындардың толық саны. Ал блоктар әдетте элементтерден үлкен болады және бірнеше қатарды қамтуға мүмкіндік беретін өзгеріп отыратын биіктікке ие. Орналастыру схеманың кіші схемаларын бағдарламаланатын FPGA логикалық блоктарына бейімдеу арқылы маршруттаудың келесі кезеңінің аяқталуын қамтамасыз етеді.

Негізгі әдістер

Орналастыру жалпы орналастыру және егжей-тегжейлі орналастыруға бөлінеді. Жалпы орналастыру шағын ауыспалы жағдайларға жол бере отырып, барлық инстанстарды жаһандық масштабта тиісті орындарға тарату арқылы күрт өзгерістер енгізеді. Егжей-тегжейлі орналастыру әрбір инстансты өте орташа өзгеріспен жақын орналасқан заңды орынға жылдырады. Орналастырудың және жалпы жобалау сапасының ең маңызды факторы – жалпы орналастырудың нәтижелілігі. Интегралды схемаларды орналастырудың алғашқы әдістерін комбинаторлық оптимизация деп жіктеуге болады. Мыңдаған немесе он мыңдаған компоненттері бар ИС жобалары үшін TimberWolf сияқты симуляцияланған оттану әдістері ең жақсы нәтижелерді көрсетеді. ИС жобалары миллиондаған компоненттерге дейін өскенде, орналастыру гиперграфты бөлуді пайдаланды, мысалы Capo сияқты ұялы бөлу жүйелерін қолданды. Комбинаторлық әдістер компоненттердің қабаттасуын тікелей болдырмайды, бірақ үлкен масштабта өзара байланысты оптимизациялауда қиындық тудырады. Олар көбінесе стохастикалық болып табылады және бірнеше рет іске қосылғанда бірдей кіріс деректері үшін әртүрлі нәтижелер бере алады. Жалпы орналастырудың аналитикалық әдістері өзара байланыстың ұзындығын үздіксіз функция арқылы модельдейді және компоненттік тығыздық шектеулеріне бағынышты осы функцияны тікелей азайтады. Бұл әдістер комбинаторлық әдістерге қарағанда жылдам жұмыс істейді және жақсы масштабталады, бірақ компоненттердің қабаттасуын болдырмайды және егжей-тегжейлі орналастыру үшін комбинаторлық әдістермен өңделуі керек. Квадраттық орналастыру – бұл ұзындықты квадраттық функциямен модельдейтін және жоғары өнімділікті квадраттық оптимизация техникаларын қолданатын ерте аналитикалық әдіс. Ол дамыған кезде, нәтижелерінің бәсекеге қабілеттілігі мен тұрақтылығын көрсетті, комбинаторлық әдістерден өзгеше. GORDIAN сым ұзындығының шығындарын квадраттық функция ретінде қалыптастырады, сонымен қатар жасушаларды рекурсивті бөлу арқылы бір-бірінен бөліп таратады. Алгоритм орналасу тығыздығын квадраттық шығын функциясына сызықтық мүше ретінде модельдейді және орналасу мәселесін таза квадраттық бағдарламалау арқылы шешеді. Әдеттегі жақсарту – әрбір желіні алдыңғы итерациядағы ұзындығының кері шамасымен салмақтау. Егер процесс конвергенцияға жетсе, бұл сым ұзындығы бойынша объективті сызықтықты азайтады. Қазіргі заманғы квадраттық орналастыру құралдарының көпшілігі (KraftWerk, FastPlace, SimPL) осы қағиданы ұстанады, әрқайсысы сызықтық тығыздық күшін анықтау үшін әртүрлі эвристикалық тәсілдерді қолданады. Сызықтық емес орналастыру желі ұзындығын экспоненциалды (сызықтық емес) функциялармен, ал тығыздықты – жергілікті бөлшектелген квадраттық функциялармен модельдейді, осылайша жақсы дәлдікке және сапаға қол жеткізеді. APlace және NTUplace осы жұмыстың жалғасы болып табылады. ePlace – бұл заманауи жалпы орналастыру алгоритмі. Ол инстанстарды электростатикалық өрісті модельдеу арқылы бөліп таратады, бұл сапаның төмендеуін азайтады және жақсы өнімділікке қол жеткізеді. 2021 жылы Google Brain орналастыру мәселесі үшін жасанды интеллект техникаларын (әсіресе, күшейту оқытуын) қолданудан жақсы нәтижелер алғанын хабарлады. Дегенмен, бұл нәтиже даулы, өйткені мақалада қазіргі орналастыру құралдарымен тікелей салыстыру жоқ және меншік құқығындағы мазмұнға байланысты қайталау қиын. Кем дегенде бір бастапқы оң пікірлер кейінірек қосымша тексеруден кейін қайтарылып алынды.

Placement is divided into global placement and detailed placement. Global placement introduces dramatic changes by distributing all the instances to appropriate locations in the global scale with minor overlaps allowed. Detailed placement shifts each instance to nearby legal location with very moderate layout change. Placement and overall design quality is most dependent on the global placement performance. Early techniques for placement of integrated circuits can be categorized as combinatorial optimization. For IC designs with thousands or tens of thousands of components, simulated annealing methodologies such as TimberWolf exhibits the best results. When IC designs grew to millions of components, placement leveraged hypergraph partitioning using nested partitioning frameworks such as Capo. Combinatorial methods directly prevent component overlaps but struggle with interconnect optimization at large scale. They are typically stochastic and can produce very different results for the same input when launched multiple times. Analytical methods for global placement model interconnect length by a continuous function and minimize this function directly subject to component density constraints. These methods run faster and scale better than combinatorial methods, but do not prevent component overlaps and must be postprocessed by combinatorial methods for detailed placement. Quadratic placement is an early analytical method that models interconnect length by a quadratic function and uses high performance quadratic optimization techniques. When it was developed, it demonstrated competitive quality of results and also stability, unlike combinatorial methods. GORDIAN formulates the wirelength cost as a quadratic function while still spreading cells apart through recursive partitioning. The algorithm models placement density as a linear term into the quadratic cost function and solves the placement problem by pure quadratic programming. A common enhancement is weighting each net by the inverse of its length on the previous iteration. Provided the process converges, this minimizes an objective linear in the wirelength. The majority of modern quadratic placers (KraftWerk, FastPlace, SimPL) follow this framework, each with different heuristics on how to determine the linear density force. Nonlinear placement models wirelength by exponential (nonlinear) functions and density by local piece wise quadratic functions, in order to achieve better accuracy thus quality improvement. Follow up academic work includes APlace and NTUplace. ePlace is a state of the art global placement algorithm. It spreads instances apart by simulating an electrostatic field, which minimizes quality overhead thus achieves good performance. In 2021, Google Brain reported good results from the use of AI techniques (in particular reinforcement learning) for the placement problem. However, this result is quite controversial, as the paper does not contain head to head comparisons to existing placers, and is difficult to replicate due to proprietary content. At least one initially favorable commentary has been retracted upon further review.