Диссертация (1090534), страница 20
Текст из файла (страница 20)
Для проведенияэкспериментов были использованы технологический процесс FreePDK15 ибилиотека стандартных ячеек NanGate FreePDK15 OCL. Данные открытыетехнологии позволяют проводить исследования в области проектированиямикро- и наноэлектроники с учетом актуальных технологических процессов.Однако, стоит отметить, что полученные результаты могут быть оптимистичны— коммерческие технологические процессы могут вводить более жесткиеограничения на топологии элементов библиотек, что, как следствие, приведет кменьшему сокращению площади элементов при использовании дополнительныхограничений.Для получения экспериментальных результатов были выбраны 5 правилпроектирования и 10 стандартных ячеек. Для заданных правил проектированиябыли сгенерированы в общей сложности 88 вариантов дополнительныхограничений на границах.
76 из них были признаны консервативными —с учетом заданных ограничений не удалось синтезировать ячейки тестовойбиблиотеки. 12 вариантов были проанализированы, в результате чего былопределен оптимальный вариант, позволивший оттрассировать все заданныеструктурные компоненты в указанной площади.Сравнительный анализ результатов предложеного подхода с подходомна основе увеличения площади стандартных элементов показал, что среднийвыигрыш по площади элементов составляет 28.2%. Стоит отметить, что данноезначение получено при использовании оптимистичного технологическогопроцесса FreePDK15. При работе с промышленными процессами,описывающими на порядки больше технологических ограничений, выигрыш поплощади может быть иным.102ЗаключениеРост сложности проблем, которые встают перед разработчиками, неуклоннорастет по мере развития технологий. Не являются исключением и задачитрадиционные задачи оптимизации, природа которых радикально изменилась —для многих задач практический интерес представляет поиск не оптимальногорешения, а удовлетворяющего всем заданным ограничениям в кратчайшие сроки.Требования к скорости получения результата обуславливаются высокой степеньюконкуренции на рынке — команда, сумевшая вывести свой продукт на рынокпервой, получает конкуретное преимущество.
В качестве примера подобнойзадачи можно привести синтез структурных компонентов СБИС, т.н. стандартныхячеек.Одним из способов снижения сложности разработки являетсяиспользование декларативного программирования и формальных методов.Отличительной особенностью данного подхода является то, что разработказаключается в описании задачи в терминах предметной области. Разработчикформулирует желаемые свойства результата, а не в описывает алгоритмполучения решения.
Полученная спецификация является входными данными кнекоему универсальному алгоритму. Такой подход позволяет переиспользоватьиспользуемы вычислительный комплекс для решения различных задач —детали реалации конкретных технологий становятся частью спецификации.
Врезльтате, полученное решение удовлетворяет всем заданным ограничениям,иначе генерируется доказательство, почему решение не может быть получено.Согласно цели диссертационного исследования был исследован методавтоматического вывода геометрических ограничений, используемых при синтезеструктурных компонентов ограниченной площади. Алгоритм, предложенный длядостижения поставленной цели, в ходе исследования был разделен на 4 основныхэтапа:1. Представление исходных геометрических ограничений в видевыражаней логики высказываний.2. Перечисление всех разрешенных топологий в рамках ограниченнойплощади методом решения задачи AllSAT.1033. Поиск групп разрешенных топологий, пары элементов которых необразуют нарушений при устнановке встык.
Задача сводится к решениюпроблемы перечисления максимальных клик.4. Вычисления компактного описания групп разрешенных топологийструктурных компонентов.Предложенный подход обладает следующими преимуществами:– Детали реализации исследуемых технологических процессов иархитектур отделены от используемых алгоритмов и методов, чтопозволяет использовать один и тот же вычислительный комплекс дляанализа различных технологий.– Задача вывода дополнительных ограничений на границах формулируетсяв терминах предметной области, что позволяет вносить корректировкив постановку задачи людям, не обладающим специфичными навыкамипрограммирования.– Использование формальных методов позволяет гарантироватькорректность полученного решения.По итогам проведенного исследования был реализован вычислительныйкомплекс автоматического вывода геометрических ограничений на границахструктурных компонентов ограниченной площади.
Полученная программнаясистема, где были реализованы предлагаемые модели и алгоритмы, внедренакомпанией АО “Интел А/О”. В приложении приведена копия акта о внедрении.К недостаткам предложенного подхода можно отнести высокие требованияиспользуемых методов к вычислительным ресурсам — ряд поставленных задачпринадлежит классу N P –сложных, алгоритмы решения которых в общемслучае требуют экспоненциально больших объемов вычислительных ресурсов.В диссертационной работе предлагается ряд методов, позволяющих снизитьалгоритмическую сложность данных этапов.
Перспективными можно назватьдальнейшие исследования методов снижения алгоритмической сложностиобозначенных этапов.Основные результаты работы заключаются в следующем.1. Показана практическая эффективность использования формальныхметодов для решения многопараметрических задач оптимизации.Анализ современного состояния систем автоматизации проектированиямикроэлектроники продемонстрировал практическую значимость104разработки вычислительного комплекса автоматического построениягеометрических ограничений на границах структурных компонентовс использованием декларативного программирования и формальныхметодов.2. В результате проведенных исследований обоснована возможностьавтоматического вывода геометрических ограничений на основерешения задачи выполнимости булевых функций.3. Предложен алгоритм построения геометрических ограничений награницах структурных компонентов ограниченной площади.4.
Разработан алгоритм автоматического выбора субоптимальногонабора вспомогательных геометрических ограничений на основеавтоматического синтеза структурных компонентов.5. Реализован вычислительный комплекс, позволяющий автоматическивыводить субоптимальные геометрические ограничения на границахструктурных компонентов.
Для тестовой библиотеки из 10 структурныхкомпонентов при использовании открытого технологического процессаFreePDK15 было получено сокращение площади на 28.2%.6. Результаты работы диссертационной работы докладывались на трехвсероссийских конференциях и одной международной.7. Разработанные алгоритмы и методы внедрены в АО “Интел А/О”.8. По теме диссертации опубликовано 8 печатных работ, в том числе 6работы в ведущих рецензируемых печатных изданиях, рекомендованныхВАК для публикации основных научных результатов диссертации насоискание ученой степени кандидата наук. Одна работа размещена вцифровой библиотеке IEEE Xplore и индексирована в международнойнаукометрической базе данных Web of Science.Научная новизна диссертационного исследования заключается вследующем:1.
Предложен метод построения всех разрешенных геометрийв ограниченной площади путем представления геометрическихограничений в виде булевых выражений и последующего решениязадачи AllSAT.2. Разработан алгоритм поиска классов геометрий, не приводящихк нарушениям заданных ограничений при любом разрешенном105размещении, заключающийся в построении графа с описаниемсовместных и несовместных топологий геометрий и перечислениивсех максимальных полных подграфов.3. Разработан алгоритм выбора субоптимальных геометрическихограничений на границах структурных компонентов, построенииограниченного множества элементов, анализе параметров их качестваи сравнительном анализе качества компонентов с учетом разныхвариантов ограничений на границах, позволивший сократить площадьтестового набора структурных компонентов на 28.2%.На защиту выносятся следующие положения:1.
Доказанаэффективностьпримененияформальныхметодовидекларативногопрограммированиядлярешениязадачмногопараметрической оптимизации большой размерности.2. Алгоритм перечисления множеств геометрических ограничений,предотвращающих нарушения указанных геометричеких ограничений,возникающих при установке структурных компонентов ограниченнойплощади встык друг к другу.3. Метод оценки качества полученных вспомогательных правилпроектирования на границах структурных компонентов ограниченнойплощади и процедура поиска множества правил, соответствующегозаданным критериям качества.4.
Вычислительныйкомплекс“Вычислительгеометрическихограничений”Для апробации вычислительного комплекса, разработанного в рамкахдиссертационной работы была выбрана задача из области физическогопроектирования СБИС, а именно, задача автоматического синтеза топологийструктурных элементов СБИС — стандартных ячеек.
Эффективностьпредложенного вычислительного комплекса проверялась с использованиемоткрытых технологий FreePDK15 и библиотеки стандартных ячеек NanGate,описывающих актуальный технологический процесс с проектной нормой15 нм. Стоит отметить, что данное значение получено при использованииоптимистичного технологического процесса FreePDK15. При работес промышленными процессами, описывающими на порядки большетехнологических ограничений, выигрыш по площади может быть иным.106Полученные экспериментальные результаты позволяют заключить, чтопредлагаемая математическая модель и программное обеспечение позволяютрешать актуальные задачи. Использование разработанного вычислительногокомплекса позволяет сократить разрыв между этапами логического и физическогосинтеза структурных компонентов СБИС — стандратных ячеек.107Литература1.
Improving the multi-objective evolutionary optimization algorithm for hydropower reservoir operations in the California Oroville–Thermalito complex /Tiantian Yang, Xiaogang Gao, Scott Lee Sellars, Soroosh Sorooshian // Environmental Modelling & Software. — 2015. — Vol. 69. — Pp. 262–279.2. Miettinen Kaisa. Nonlinear multiobjective optimization. — Springer Science &Business Media, 2012. — Vol. 12.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
