Разработка эффективных параллельных алгоритмов с использованием технологий Интел. Параллельные алгоритмы спектрального анализа Панкратов Антон Николаевич. - презентация

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

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

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

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

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

6 Как получать значения полиномов? Рекуррентное соотношение Такой цикл не может быть распараллелен! 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; }

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

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

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

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

11 Распараллеливание матричного алгоритма 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

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

13 Распараллеливание «рекуррентного» алгоритма Внешний цикл нельзя распараллелить Каждый узел квадратурной сетки вносит вклад во все коэффициенты 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:+)

14

15 Распараллеливание «рекуррентного» алгоритма #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]; } Распараллеливание «вручную» по узлам сетки

16 Векторизация «рекуррентного» алгоритма 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 Необязательный внешний цикл обусловлен дополнительной нарезкой сетки в случае фиксированной глубины векторизации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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