Южно-Уральский государственный университет В работе описана параллельная версия алгоритма кластеризации Partitioning Around Medoids для сопроцессора Intel Xeon Phi. Распараллеливание выполнено на основе OpenMP. Циклические операции преобразованы для выполнения векторизации. Алгоритм использует матрицу предвычисленных расстояний, которая хранится в памяти сопроцессора. Представлены результаты вычислительных экспериментов, подтверждающие эффективность разработанного алгоритма.
2. Контекст исследования и обзор работ 2.1. Обзор работ
Существует большое количество работ по кластерному анализу. Классические
алгоритмы кластеризации k-Means и k-Medoids были описаны в [
Следующие работы посвящены ускорению алгоритмов кластеризации с помощью
параллельных аппаратных средств. В статье [
По нашему мнению потенциал ускорителей на архитектуре Intel MIC для решения
задач кластеризации недооценен. Насколько нам известно существует только одна
работа [
Сопроцессор поддерживает следующие режимы запуска приложений: native, ofload и
symmetric. В режиме native приложение выполняется независимо, исключительно на
сопроцессоре. В режиме ofload приложение запускается на процессоре и выгружает
вычислительно интенсивную часть работы (код и данные) на сопроцессор. Режим symmetric
позволяет сопроцессору и процессору взаимодействовать в рамках модели обмена сообщениями
(Message Passing Interface).
3. Описание алгоритма Partitioning Around Medoids
Введем следующие обозначения для формального описания алгоритма PAM [
Алгоритм PAM является разновидностью метода наискорейшего подъема. На каждой итерации выбирается пара медоид ci и не-медоид oj такая, что замена медоида на не-медоид дает лучшую кластеризацию из возможных. Оценка кластеризации выполняется с помощью целевой функции, вычисляемой как сумма расстояний от каждого объекта до ближайшего медоида: (1) Вход : Множество объектов O, количество кластеров k Выход: Множество кластеров C 1 Инициализировать C ; // фаза BUILD 2 repeat// фаза SWAP 3 Вычислить Tmin ; 4 Поменять местами cmin и omin; 5 until Tmin < 0;
Рис. 1. Псевдокод алгоритма PAM Псевдокод алгоритма PAM представлен на рис. 1. PAM состоит из двух фаз: BUILD и SWAP. В фазе BUILD выполняется первичная кластеризация, в которой последовательно выбирается k объектов в качестве медоидов. Первый объект c1 — это объект, сумма расстояний от которого до всех остальных объектов является наименьшей: n c1 = arg min \sum \rho (oh, oj).
1l\eq hl\eq n j=1 Затем выбирается следующий объект, минимизирующий целевую функцию. Для этого производится вычисление целевой функции относительно ранее выбранных объектов c и каждого из невыбранных объектов o:
n c2 = arg min \sum min(\rho (c1, oj), \rho (oh, oj)), 1l\eq hl\eq n j=1
n c3 = arg min \sum min( min (\rho (cl, oj)), \rho (oh, oj)), 1l\eq hl\eq n j=1 1l\eq ll\eq 2
n ck = arg min \sum min( min (\rho (cl, oj)), \rho (oh, oj)).
1l\eq hl\eq n j=1 1l\eq ll\eq k- 1 ... Эта процедура повторяется, пока не будет выбрано k объектов.
В фазе SWAP алгоритм PAM пытается улучшить множество медоидов C. Алгоритм выполняет поиск пары объектов (cmin, omin), минимизирующих целевую функцию. Для этого перебираются все пары объектов (ci, oh), где ci — это медоид, а oh не-медоид. Вычисляется изменение целевой функции при исключении ci из множества медоидов и включении oh вместо него. Обозначим это изменение как Tih, а минимальное значение Tmin достигается на паре (cmin, omin). Если Tmin > 0, тогда множество C не может быть улучшено, и алгоритм завершается.
Для описания вычисления Tih введем следующие обозначения. Пусть D = \{ d1, d2, . . . , dn\} — это множество расстояний от каждого объекта до ближайшего медоида. Пусть S = \{ s1, s2, . . . , sn\} — это множество расстояний от каждого объекта до второго ближайшего медоида. Пусть Cjih — это вклад не-медоида oj в Tih при замене ci на oh. В этом случае Tih определяется как сумма Cjih:
n Tih = \sum Cjih.
j=1
Псевдокод вычисления Cjih представлен на рис. 2 [
Рис. 2. Вычисление Cjih 4. Параллельный алгоритм
В данном разделе мы описываем подход к реализации алгоритма PAM на сопроцессоре Intel Xeon Phi. Подход основан на следующих принципах.
Параллелизм по данным и векторизация. С помощью технологии OpenMP мы обеспечиваем одновременное исполнение одной и той же функции над элементами исходного набора данных. Большинство циклов алгоритма PAM с арифметическими операциями были реорганизованы из скалярной формы в векторную, для эффективного исполнения на векторных арифметических устройствах сопроцессора.
В нашей реализации используется несколько механизмов для достижения локальности данных, то есть программа обращается к данным, расположенным близко к недавно запрошенным областям памяти. Так как сопроцессор загружает данные в кэш блоками, то области памяти близкие к ранее загруженным областям так же попадут в кэш, что приведет к росту производительности алгоритма.
На рис. 3 представлен псевдокод алгоритма PAM, адаптированного для сопроцессора Intel Xeon Phi.
Вход : Множество объектов O, количество кластеров k Выход: Множество кластеров C 1 Выгрузить (ofload) O, k из памяти CPU на сопроцессор; 2 M \leftarow P repareDistanceM atrix(O); 3 C \leftarow BuildM edoids(M ) ; // фаза BUILD 4 repeat// фаза SWAP 5 Tmin \leftarow F indBestSwap(M, C) ; 6 Поменять местами cmin и omin; 7 until Tmin < 0; 8 Выгрузить (ofload) C из памяти сопроцессора в память CPU;
Рис. 3. Распараллеленный алгоритм PAM для сопроцессора Intel Xeon Phi Сводная информация о подалгоритмах PAM представлена в таблице 1. Для улучшения производительности мы используем технику предвычисления расстояТаблица 1. Сводная информация о подалгоритмах PAM Название PrepareDistanceMatrix BuildMedoids FindBestSwap Временная сложность Техники распараллеливания
O(pn2)
O(kn2) O(k(n - k)2)
OpenMP ний между всеми объектами множества O. В этом случае нет необходимости в вычислении расстояний на каждой итерации алгоритма PAM, так как все расстояния сохранены в матрице расстояний M .
Алгоритм PAM оперирует большим количеством массивов данных, не помещающихся
в кэш-памяти L2 сопроцессора Intel Xeon Phi. Мы обрабатываем данные блоками по L
элементов для обеспечения локальности данных. Рекомендуемое [
Подалгоритм PrepareDistanceMatrix инициализирует матрицу расстояний (см. рис. 4).
В отличие от [
end end end Вход : Множество объектов O Выход: Матрица расстояний M 1 forall the oi таких, что 1 \leq i l\eq n do // parallelized 2 for j = 1 до n шаг L do 3 for k = 1 to p do 4 for l такое, что j \leq l l\eq j + L do // vectorized // доступ к ol организован с применением тайлинга mil \leftarow mil + (oi[k] - ol[k])2; end for l такое, что j \leq l l\eq j + L do // vectorized mil \leftarow s\urd mil;
Рис. 4. Вычисление матрицы расстояний Подалгоритм BuildMedoids реализует фазу BUILD (см. рис. 5) в соответствии с формулами (2)–(5).
Подалгоритм FindBestSwap реализует фазу SWAP (см. рис. 6). Он перебирает все пары (ci, oh) объектов, где ci медоид, а oh не-медоид, вычисляет величину Tih для каждой пары и возвращает минимальное значение Tmin. 5. Вычислительные эксперименты
Для оценки разработанного алгоритма мы выполнили эксперименты на узле суперкомпьютера «Торнадо ЮУрГУ»1, спецификации которого представлены в таблице 2. Экспе10 11 12 13 14 end
end end Обновить D; Вход : Матрица расстояний M Выход: Множество медоидов C 1 forall the i = 1 to n do // parallelized
n 2 if \sum mij минимальна then // вычисление суммы векторизовано j=1 c1 \leftarow oi; рименты проводились над данными одинарной точности. Сопроцессор Intel Xeon Phi использован в режиме ofload . Мы измеряли время работы алгоритма PAM в зависимости от количества обрабатываемых данных и исследовали влияние свойств наборов данных на время работы подалгоритмов PAM.
Характеристики наборов данных, использованных в экспериментах, представлены в таблице 3.
Результаты экспериментов на данных FCS Human представлены на рис. 7(a). Данные из набора FCS Human имеют большую размерность, поэтому наибольшее время работы занимает процесс вычисления матрицы расстояний. Вычисление матрицы расстояний на Intel Xeon Phi в два раза эффективнее, чем на процессоре Intel Xeon.
Результаты экспериментов на данных гистограмм фотобазы Corel представлены на рис. 7(b). Размерность данных небольшая, поэтому подготовка матрицы расстояний не заТаблица 2. Спецификация узла суперкомпьютера «Торнадо ЮУрГУ» Спецификации Модель Количество ядер Тактовая частота, ГГц Количество нитей на ядро Пиковая производительность, TFLOPS Процессор
Сопроцессор Intel Xeon X5680 Intel Xeon Phi SE10X 61 1,1 4 1,076 6 2 3,33 0,371 p
k нимает много времени. Алгоритм PAM в два раза медленнее на процессоре Intel Xeon, чем на сопроцессоре Intel Xeon Phi.
(a) Производительность на данных FCS Human (b) Производительность на данных гистограмм фотобазы Corel Рис. 7. Результаты экспериментов Эксперименты показали, что скорость работы алгоритма PAM определяется природой кластеризуемых данных. Наиболее трудоемким этапом для обработки данных большой размерности является вычисление матрицы расстояний. При работе с данными небольшой размерности время работы подалгоритмов PAM значительно превосходит время вычисления матрицы расстояний. 6. Заключение
В работе описана параллельная версия алгоритма кластеризации Partitioning Around Medoids для сопроцессора Intel Xeon Phi. Распараллеливание выполнено на основе OpenMP. Циклические операции преобразованы для выполнения векторизации. Алгоритм использует матрицу предвычисленных расстояний, которая хранится в памяти сопроцессора. Алгоритм хранит данные в непрерывных массивах и обрабатывает данные блоками для обеспечения локальности данных и, как следствие, лучшей производительности.
Представлены результаты вычислительных экспериментов, подтверждающие эффективность разработанного алгоритма. Эксперименты показали, что скорость работы алгоритма PAM определяется природой кластеризуемых данных. Наиболее трудоемким этапом для обработки данных большой размерности является вычисление матрицы расстояний. При работе с данными небольшой размерности время работы подалгоритмов PAM значительно превосходит время вычисления матрицы расстояний.
В качестве возможного направления дальнейших исследований интересными представляются следующие направления: модернизация разработанного алгоритма для случая вычислительного узла с несколькими сопроцессорами Intel Xeon Phi и расширение данного алгоритма для кластерной системы, вычислительные узлы которой оснащены сопроцессорами Intel Xeon Phi. Литература Parallel clustering algorithm for Intel Xeon Phi coprocessor Timofey Rechkalov