Введение
Современные системы проектирования микроэлектроники оперируют огромными объемами геометрических данных. На этапе подготовки фотошаблонов выполняются операции объединения, пересечения и вычитания полигонов, определяющие корректность топологии будущих интегральных схем. Использование существующих открытых решений не всегда обеспечивает необходимую производительность при работе с многомиллионными наборами вершин [1, с. 12]. В связи с этим была поставлена задача разработки специализированного программного модуля вычислительной геометрии, ориентированного на высокую скорость обработки данных и возможность интеграции в отечественные САПР.
Основная часть
ПМ АВГ представляет собой вычислительное ядро, реализованное на языке C++. Модуль функционирует как динамическая библиотека и взаимодействует с внешними приложениями через C-совместимый интерфейс. Такой подход обеспечивает возможность использования модуля из Python, Ruby и других языков программирования посредством механизма FFI. Основной задачей ПМ АВГ является выполнение булевых операций над полигональными регионами: объединения, пересечения, разности и симметрической разности.
Рис. 1. Архитектура взаимодействия ПМ АВГ с внешними системами
Алгоритм обработки данных основан на методе заметающей прямой. На первом этапе определяется множество точек пересечения ребер. После этого выполняется маркировка сегментов и формирование результирующих контуров в зависимости от выбранной операции. Для хранения координат используются 64-битные целочисленные значения, что исключает ошибки округления и обеспечивает высокую точность при работе с нанометровой сеткой [2, с. 45].
Особое внимание при разработке уделялось вопросам производительности. В отличие от универсальных библиотек, модуль ориентирован на обработку крупных массивов данных с минимальными накладными расходами памяти. Применение контейнеров стандартной библиотеки C++ и отказ от автоматической сборки мусора позволили обеспечить предсказуемое время отклика даже при выполнении сложных операций над большими наборами полигонов.
Рис. 2. Схема алгоритма выполнения ПМ АВГ
Для проверки корректности реализации использовался фреймворк GoogleTest. Модульное тестирование включало проверку операций над самопересекающимися полигонами, коллинеарными ребрами и вырожденными контурами. Интеграционное тестирование проводилось через Python-обертку с использованием ctypes. Дополнительно применялись инструменты Valgrind и clang-tidy для выявления утечек памяти и потенциально опасных конструкций.
Результаты
Экспериментальная апробация ПМ АВГ проводилась на тестовых топологических слоях, содержащих до одного миллиона вершин. В ходе испытаний модуль продемонстрировал стабильную обработку булевых операций при среднем потреблении памяти около 462 Мб. По сравнению с рядом открытых решений наблюдалось сокращение времени обработки и повышение стабильности работы при выполнении многопоточных вычислений. Полученные результаты подтверждают возможность использования ПМ АВГ в составе отечественных систем подготовки фотошаблонов.
Заключение
Разработанный программный модуль ПМ АВГ решает задачу выполнения булевых операций над полигональными структурами в условиях высокой нагрузки и больших объемов данных. Использование языка C++, эффективных алгоритмов вычислительной геометрии и оптимизированных структур данных позволило добиться высокой производительности и обеспечить возможность интеграции модуля в существующие программные комплексы. Практические испытания подтвердили корректность работы и перспективность применения модуля в задачах микроэлектронного производства.
Литература:
- Леонов М. В., Никитин А. Г. Алгоритмы булевых операций над многоугольниками. — Москва: Наука, 2021.
- Computational Geometry in CAD Systems // Springer Publishing, 2022.
- Официальная документация GoogleTest [Электронный ресурс].
- Stroustrup B. The C++ Programming Language. — Addison-Wesley, 2013.
