Параллельный алгоритм вычисления матрицы Евклидовых расстояний для многоядерного процессора Intel Xeon Phi поколения Knights Landing

Вычисление матрицы Евклидовых расстояний требуется в широком спектре задач, связанных с интеллектуальным анализом данных. В настоящее время большое количество параллельных алгоритмов решения этой задачи реализовано для графических процессоров. Однако данные разработки не могут быть просто перенесены на многоядерные системы архитектуры Intel Many Integrated Core. В статье предлагается параллельный алгоритм вычисления матрицы Евклидовых расстояний на многоядерном процессоре Intel Xeon Phi поколения Knights Landing для случая, когда входные данные могут быть размещены в оперативной памяти. Данный алгоритм использует блочно-ориентированную схему организации вычислений, которая позволяет эффективно использовать возможности векторизации вычислений Intel Xeon Phi. В алгоритме применена нетривиальная компоновка данных в оперативной памяти для уменьшения количества кэш-промахов процессора во время вычислений. Эксперименты на реальных и синтетических наборах данных показали, что предложенный алгоритм хорошо масштабируется и опережает аналоги в случае прямоугольных матриц с данными малой размерности.