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

Abstract

Рассматриваются алгоритмы операций пересечения и объединения (мульти) множеств, выполненные как часть решения задачи анализа формальных понятий и допускающие реализацию на параллельной вычислительной архитектуре за время O-n-p-log-n-- c пространственной сложностью O-m- (O-n- для операции объединения), где n и m – соответственно суммарная и минимальная мощности пересекаемых множеств, а p – количество процессоров. Приводятся результаты тестирования реализации алгоритма операции пересечения, выполненной средствами платформы OpenCL.