Параллельная реализация алгоритма логических операций над множествами ортогональных многоугольников
Автор: Старостин Николай Владимирович, Штанюк Антон Александрович, Годовицын Максим Михайлович, Живчикова Юлия Алексеевна
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 1 (54), 2022 года.
Бесплатный доступ
В рамках разработки отечественных САПР для верификации норм конструкторско- технологических ограничений (КТО) необходима разработка библиотеки выполнения логических операций над ортогональными многоугольниками, составляющими топологию интегральной схемы. Функции библиотеки выполняют операции над слоями. Под слоем понимается множество ортогональных прямоугольников (полигонов). К этим операциям предъявляются жесткие требования по времени выполнения. Существует реализация, построенная на основе алгоритма заметающей прямой и позволяющая добиться времени работы алгоритма порядка O(NlogN ). Для эффективного функционирования в высокопроизводительной вычислительной среде разработана параллельная реализация, основанная на геометрической декомпозиции исходных данных. Проведенное теоретическое исследование показало линейную масштабированность данной реализации на системах с распределенной памятью, но реализация в виде многопоточного приложения выявила конкуренцию за разделяемый ресурс. В работе приводятся результаты вычислительного эксперимента и намечаются пути устранения эффекта конкуренции. Представленные в работе реализации алгоритмов и процедур вошли в состав подключаемой библиотеки функций работы со слоями топологического описания, которая, в свою очередь, является частью разрабатываемой системы верификации норм КТО. Данная библиотека реализована на языке C++ с использованием стандарта C++17. Имплементация параллельных схем реализации логических операций выполнена с использованием библиотеки OpenMP.
Сапр, проверка конструктивно-технологических ограничений, логические операции, полигоны, параллельная реализация алгоритма заметающей прямой
Короткий адрес: https://sciup.org/143178946
IDR: 143178946 | DOI: 10.24412/2073-0667-2022-1-55-65
Список литературы Параллельная реализация алгоритма логических операций над множествами ортогональных многоугольников
- Батищев Д. И., Старостин Н.В., Филимонов А. В. Многоуровневый алгоритм решения задачи компоновки интегральных схем // Системы управления и информационные технологии. 2007. № 3 29. С. 48-52.
- Старостин Н.В., Филимонов А. В., Балашов В. В. Решение задачи размещения элементов специализированных больших интегральных схем на основе базовых матричных кристаллов // Системы управления и информационные технологии. 2009. № 2-1 36. С. 189-194.
- Старостин Н.В., Балашов В. В. Использование гиперграфов для решения задачи ортогональной трассировки больших интегральных схем с нерегулярной структурой // Радиотехника и электроника. 2008. Т. 53. № 5. С. 618-623.
- Власов С.Е., Годовицын М.М., Старостин Н.В. Концепция многоуровневой трассировки цепей интегральных схем с использованием виртуальных каналов // Успехи кибернетики. 2020. Т. 1. № 1. С. 8-16.
- Афраймович Л. Г., Власов В. С., Куликов М.С., Прилуцкий М.Х., Старостин Н.В., Филимонов А. В. Планирование и оперативное управление процессом изготовления сложных изделий //В сборнике: XII всероссийское совещание по проблемам управления ВСПУ-2014. Институт проблем управления им. В. А. Трапезникова РАН. 2014. С. 5138-5149.
- Афраймович Л. Г., Власов В. С., Прилуцкий М.Х., Седаков Д. В., Старостин Н.В., Филимонов А. В., Куликов М.С. Задачи планирования и оперативного управления процессом изготовления интегральных схем с микронными и субмикронными топологическими нормами // Автоматизация в промышленности. 2014. № 8. С. 17-21.
- Штанюк А. А., Семенов А. О. Проблема анализа топологии интегральных схем на основе GDSII файлов // Инженерные и информационные технологии, экономика и менеджмент в промышленности: Сборник научных статей по итогам второй международной научной конференции. Волгоград, 2020. С. 334-336.
- Балашов Д. А., Штанюк А. А. Постановка задачи исследования алгоритмов проверки изоморфизма гиперграфов при анализе топологии интегральных схем на основе GDSII и DEF файлов // Информационные системы и технологии ИСТ-2020: сборник трудов Международной научнотехнической конференции. Нижний Новгород, 2020. С. 743-749.
- Godovitsyn Maxim, Zhivchikova Julia, Starostin Nickolay, Shtanyuk Anton. Algorithm for Implementing Logical Operations on Sets of Orthogonal Polygons. Proceedings of the 31st International Conference on Computer Graphics and Vision (GraphiCon 2021) Nizhny Novgorod, Russia, September 27-30, 2021 // CEUR Workshop Proceedings, 2021, 3027, S. 1088-1097.
