Разработка эффективных параллельных алгоритмов с использованием технологий Интел. Параллельные алгоритмы спектрального анализа Панкратов Антон Николаевич Летняя молодежная школа Разработка параллельных приложений для петафлопсных вычислительных систем, 26 июня - 3 июля 2011 года, НОЦ "Суперкомпьютерные технологии, МГУ имени М.В.Ломоносова

Особенности архитектуры, которые необходимо учитывать Кэш, Конвейеризация вычислений, Векторизация вычислений (Intel® IPP, MKL) Многоядерность (OpenMP)

Обобщенный спектрально- аналитический метод Вычисление коэффициентов разложения функции Восстановление функции по коэффициентам разложения Алгебра спектральных преобразований

Приложения Распознавание повторов в геномах и белках Аналитическое описание плоских и пространственных кривых, распознавание образов Обработка данных магнитной энцефалографии Обработка метеорологических данных Анализ данных ЯМР высокого разрешения, рентгеноструктурный анализ

Коэффициенты разложения Коэффициенты разложения по ортогональной на с весом системе полиномов : Определенные интегралы вычисляются с помощью соответствующих квадратурных формул Гаусса:

Как получать значения полиномов? Рекуррентное соотношение Такой цикл не может быть распараллелен! p2 = t; p1 = 1; u[0] = 1.0; for (m = 1; m < N; m++) { p3 = p2; p2 = p1; p1 = 2*t*p2-p3; u[m] = p1; }

Сохранять ли значения полиномов? Единожды вычислив, сохранить в матрице A Вычислять заново при разложении очередного сигнала

Матричный подход Если – матрица значений полиномов: то вычисление коэффициентов разложения есть умножение матрицы на вектор-столбец взвешенных значений: где

Матричный подход + вычисления выполняются заранее + возможность «включить» оператор интерполяции с одной сетки на другую + задача сводится к линейной алгебре интенсивное потребление памяти накладные расходы на доступ к памяти при работе на SMP-системах

Вычисление значений полиномов «на месте» + экономия памяти + эффективное использование кэша + эффективное распараллеливание на SMP-системах повторяющиеся вычисления

Распараллеливание матричного алгоритма for(k = 0; k < m; k++) { for(i = 0; i < n; i++) { c[k]+= f[i]*a[k*n+i]; } или в векторном виде (Matlab) c=A*f #pragma omp parallel for

Распараллеливание матричного алгоритма

Распараллеливание «рекуррентного» алгоритма Внешний цикл нельзя распараллелить Каждый узел квадратурной сетки вносит вклад во все коэффициенты for(i = 0; i < n; i++) { p2 = 1.0; p1 = t[i]; c[0] += y[i]; for (j = 1; j < m; j++) { p3 = p2; p2 = p1; p1 = 2*t[i]*p2-p3; c[j] += y[i]*p1; } #pragma omp parallel for reduction(c:+)

Распараллеливание «рекуррентного» алгоритма #pragma omp parallel sections num_threads(2) { #pragma omp section { cheb1_expand(t,y,N,0,N/2,c1,m); } #pragma omp section { cheb1_expand(t,y,N,N/2,N,c2,m); } for (k = 0; k < m; k++) { c[k] = c1[k] + c2[k]; } Распараллеливание «вручную» по узлам сетки

Векторизация «рекуррентного» алгоритма for i = 1:k p1 = f; p2 = t.*f; c(1) = sum(p1); for j = 2:m p3 = p2; p2 = p1; p1 = 2*t.*p2-p3; c(j) = с(j) + sum(p1); end Необязательный внешний цикл обусловлен дополнительной нарезкой сетки в случае фиксированной глубины векторизации

Распараллеливание «рекуррентного» алгоритма

Сравнение Получены параллельные версии для процедур разложения функций по ортогональным полиномам Проведены сравнительные тесты матричного и «рекуррентного» алгоритмов на двухъядерных машинах Распараллеливание матричного алгоритма позволило не более, чем в 1,5 раза ускорить вычисления Распараллеливание «рекуррентного» алгоритма позволило в 2 раза ускорить вычисления Однако то, какой из алгоритмов: матричный или «рекуррентный» – эффективнее в абсолютном выражении, зависит от архитектуры ЭВМ

Алгоритмы вычисления коэффициентов разложения Матричный Рекуррентный Векторно-рекуррентный Векторно-рекуррентный с фиксированной глубиной векторизации Быстрое преобразование Фурье (только тригонометрические функции, встроено практически во все библиотеки)

Использование векторизации и многоядерности

Intel MTL: 32-x ядерная архитектура

GPU vs CPU: однородность при изменении параметра

Поиск повторов в текстовых последовательностях …ATGCGCATTCTCTGCCTGCATAAATCGCCGTATAAACCGCTACAATGCTACTGC…

Алгоритм распознавания повторов Спектральное индексирование последовательности Построение решающего правила Отображение результатов на матрице спектральной гомологии Перевод текстовой последовательности в непрерывную функцию w1, окно частоты содержания букв w2, dw2 Окно и сдвиг окна аппроксимации N, число коэффициентов разложения

Шаг 1. Статистические профили текстовых последовательностей AATGCAGCGCATT Для однозначного представления текстовой последовательности в алфавите N букв требуется профилей

Шаг 2. Спектральное представление Разложение профилей содержания f i по ортогональным функциям {φ n }

Спектральное индексирование Скользящее окно аппроксимации w2w2 последовательность w2w2 dw2 С0С0 С1С1 С2С2 …СnСn С 0 С 1 С 2 …С n …………… С n 0 С n 1 С n 2 …С n n профиль

Поиск инвертированных повторов

Шаг 3. Определение решающего правила С0С0 С1С1 С2С2 …СnСn С 0 С 1 С 2 …С n …………… С n 0 С n 1 С n 2 …С n n Метрика монотонна по числу коэффициентов

Шаг 4. Построение матрицы спектральной гомологии ATGC CGTA

Устойчивость распознавания Устойчивость к мутациям Выбор базиса

Обучение алгоритма на тестовой последовательности Инвертированный повтор Прямой повтор 20 % мутаций

Сравнение точечной и спектральной матрицы гомологии Точечная (OWEN)Спектральная w2 = 5000 N = 50

Распределенная система сравнения геномов

Матрица гомологии: поиск мегасателлитных повторов