Параллельная реализация алгоритма логических операций над множествами ортогональных многоугольников

В рамках разработки отечественных САПР для верификации норм конструкторско-технологических ограничений (КТО) необходима разработка библиотеки выполнения логических операций над ортогональными многоугольниками, составляющими топологию интегральной схемы. Функции библиотеки выполняют операции над слоями. Под слоем понимается множество ортогональных прямоугольников (полигонов). К этим операциям предъявляются жесткие требования по времени выполнения. Существует реализация, построенная на основе алгоритма заметающей прямой и позволяющая добиться времени работы алгоритма порядка 𝑂(𝑁 𝑙𝑜𝑔 𝑁).

Для эффективного функционирования в высокопроизводительной вычислительной среде разработана параллельная реализация, основанная на геометрической декомпозиции исходных данных. Проведенное теоретическое исследование показало линейную масштабированность данной реализации на системах с распределенной памятью, но реализация в виде многопоточного приложения выявило конкуренцию за разделяемый ресурс. В работе приводятся результаты вычислительного эксперимента и намечаются пути устранения эффекта конкуренции.

Представленные в работе реализации алгоритмов и процедур вошли в состав подключаемой библиотеки функций работы со слоями топологического описания, которая, в свою очередь, является частью разрабатываемой системы верификации норм КТО. Данная библиотека реализована на языке С++, с использованием стандарта С++17. Имплементация параллельных схем реализации логических операций выполнена с использованием библиотеки OpenMP.