Диссертация (1090534), страница 3
Текст из файла (страница 3)
Многие задачииз различных прикладных областей, таких как физика, финансы, здравохранение,логистика, разработка и проектирования, могут быть решены актуальнымипрограммными системами. Такие проблемы на практике могут быть решеныразличными методами, например, методами комбинаторной оптимизации. Какправило, эти задачи принадлежат классу N P –сложных и поиск оптимальногорешения может потребовать экспоненциально много вычилительных ресурсов.Одним из способов снижения сложности методов решения задач являетсяиспользование декларативного программирования и формальных методов.
Врамках данного подхода задача формулируется в терминах предметной области.Постановка задачи включает в себя описание свойств проблемы, желаемыхи нежелательных свойств результата. Для поиска решения различных задачпри этом используются одни и те же алгоритмы — вычислительное ядро.Формальные методы же позволяют формулировать задачу в виде теоремы,которая затем доказывается с использованием логических методов вывода.Результат доказательства может быть интерпретирован как решение исходнойзадачи.
Возможность формально доказывать соответствие найденного решениязаданным требованиям позволяет сократить временные затраты на поискрешения, удовлетворяющего всем заданным критериям.Примеромприкладнойобласти,вкоторойдекларативноепрограммирование и формальные методы активно используются прирешении различных задач, является разработка микро- и наноэлектроники.По мере усовершенствования проектных норм полупроводниковых изделийвозрастает сложность процессов проектирования и производства, что, в свою13очередь, увеличиватся стоимость различных ошибок. Одним из способовснижения рисков возникновения ошибок является использование различныхвычислительных комплексов на всех этапах разработки.
Основные этапыразработки микроэлетроники показаны на Рисунке 1.1.Рис. 1.1. Основные этапы разработки интегральных схемСтоит отметить, что большинство современных компаний-разработчиковмикроэлектроники не обладают своими производственными линиями —конечные изделия изготавливаются на специализированных предприятиях,предоставляющих описание поддерживаемых технологий и существующихограничений. Подобное разделение создает барьер между этапами логического ифизического синтеза.В основе современного подхода к разработке современной электроникилежит использование структурных компонентов ограниченной площади, т.н.стандартных ячеек. Одной из актуальных проблем разработки электроникиявляется решение проблемы вывода дополнительных геометрическихограничений, позволяющих разрабатывать стандартные ячейки, не нарушающиезаданных геометрических ограничений при размещении в функциональныхблоках.
Целью диссертационной работы является разработка вычислительногокомплекса, позволяющего автоматически выводить подобные ограниченияна границах элементов. Рассматриваемый подход формирует дополнительнуюобратную свзяь между этапами физического и логического синтеза, что позволяетсократить цикл проектирования. Отличительной особенностью предлагаемогоподхода является отделение деталей исследуемого технологического процесса отреализации конкретных алгоритмов.
Один и тот же вычислительный комплексможет быть использован для решения различных задач.141.1 Тенденции развития математических и программных средствНаучно-технический прогресс второй половины ХХ века привел кразрыву между практическими возможностями разработанных технологийизготовления и существующими методами и методологиями решениятрадиционных задач разработки. Опережающими темпами растет сложностьпроблем, которые требуется решать промышленности.
Сегодня природа задачоптимизации кардинально изменилась с переходом от задач оптимизациинескольких параметров к задачам огромной размерности с большим количествомпротиворечивых критериев.В частности, в работе [1] рассматривается задача оптимального управленияводными ресурсами на примере гидроэнергетического комплекса Оровиль–Термалито в Калифорнии, являющегося ключевым элементом водоснабженияштата.
Особенностью данной задачи является необходимость оптимизациинескольких целевых функций одновременно [2]. Для моделирования нелинейныхотношений между уровнями воды в резервуарах и выходной мощностью силовыхустановок была разработана математическая модель в виде полиномиальнойфункции. С целью уменьшения ошибок аппроксимации и более точногомоделирования реальных процессов были рассмотрены различные методыприближения с помощью кривых.
Также в рамках проведенного исследованиябыл проведен сравнительный анализ различных методов многопараметрическойоптимизации. Были рассмотрены такие многоцелевые подходы, как методимитации отжига [3], метод на основе генетических алгоритмов [4], метод роячастиц [5]. Разработанный в данной работе подход глобальной оптимизации наоснове эволюционных алгоритмов и с использованием метода главных компонент[6] продемонстрировал высокую точность и устойчивость.Многие актуальные проблемы, например, из областей мировой экономики,финансов, здравоохранения или логистики, естественным образом описываютсявероятностными моделями и должны учитывать неопределенность, заложеннуюв исследуемые процессы. При этом адекватные модели, описывающие такиезадачи, включают в себя сотни и тысячи параметров.
В месте с тем,подобные задачи должны быть решены в кратчайшие сроки и методы решениядолжны обеспечивать высокую точность результата. Стоит отметить, что15современные подходы к решению задач оптимизации как правило опираютсяна использование моделей, предполагающих детерминированность входныхданных, целевых функций и ограничений, и, таким образом, являются слишкомпростыми для описания реальных процессов.
В работе [7] предлагаетсяобщий метод использования и модификации метаэвристических алгоритмов длярешения стохастических задач комбинаторной оптимизации. В его основе лежитприменение имитационного моделирования при использовании традиционныхметодов оптимизации. Также в даной работе рассматриваются способы учетарисков или надежности при использовании произвольных методов оптимизации.Одним из способов упрощения сложности решения различных задачс позиции инфраструктуры является использование облачных вычислений— концепция, подразумевающая повсеместный сетевой доступ к общемумножеству настраеваемых вычислительных ресурсов [8]. Однако разработкасоответствующих систем управления ресурсами в условиях растущего спросаи распространения систем облачных вычислений [9] сама по себе являетсятрудоемкой задачей.
Одним из подходов к решению задачи назначенияоблачных ресурсов является использования локальной активности [10]. Принциплокальной активности был разработан в процессе исследований в областимикроэлектроники, но может быть применен к решению задач моделировая люойоднородной или неоднородной среды. В случае облачных технологий примеромлокально активного элемента является вычислительная машина, входящая воблако. Стоит отметить, что во многих работах при разработке планировщиковзадач эти элементы рассматриваются как пассивные, что оказывает негативноевлияние на результаты исследований.
В работе [11] рассматриваютсяразличные аспекты разработки облачных систем с использованием принципалокальной активности, обуславливающие сложность подобных проектов.Также предлагается планировщик задач, который может находиться в состоянии“порядка” или “хаоса” и приводятся параметры, описывающие каждое состояние.Для получения этих данных выполняется имитационное моделирование.В данной работе также рассматривается метод управления “хаосом” прираспределении ресурсов в облачных системах, основанный на введении уровнялокальной активности для вычислительных элементов, который используетсядля обеспечения требуемого качества обслуживания (англ. Quality of Service,QoS). Данный подход был реализован в качестве модуля для системы Apache16Spark [12].
Экспериментальные результаты показывают, что предложенныйпланировщик задач позволяет сократить расходы на сервера на 23%, увеличиваетсреднее время отклика на 15% – 20% и сокращается стандартное отклонениевремени отклика на 20% – 30%, по сравнению со стандартным планировщикомSpark.Начиная с 80–ых годов наблюдается “взрывной” рост объемов данных,которые необходимо хранить и обрабатывать [13–15]. Для обеспечениявозможности обрабатывать такие данные и решать различные задачи аналитикии прогнозирования используется ряд подходов под общим названием “big data”.Актуальные задачи big data могут включать сотни и тысячи параметров, чтоприводит к экспоненциальному росту пространства признаков.
Практическоезначение имеет решение задачи определения такого подмножества параметров,используемых в дальнейшем при построении моделей, которое бы обеспечивалотребуемую точность прогнозов. В работе [16] предлагается метод выбораподмножества признаков, котоорый может быть использован для анализапотоков данных в реальном времени. Метод основан на алгоритме роячастиц , позволяющего получить требуемый уровень точности при заданныхограничениях на доступные вычислительные ресурсы.Одним из источников больших объемов данных является распространениеИнтернета Вещей(англ. Internet–of–Things, IoT) — концепции вычислительнойсети машин, обеспеченных встроенными технологиями взаимодействия другс другом или с внешней средой [17–19]. Обеспечение инфраструктуры ивычислительных ресурсов для географически разразненной и гетерогенной среды, обеспечивающей функционирование IoT, является актуальной и трудоемкойзадачей.В работе [20] рассматривается метод распределния ресурсов облачнойвычслительной системы для обеспечения работоспособности IoT системы.Показывается, что данная задача принадлежит классу N P –сложных и можетбыть решена методами комбинаторной оптимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
