Методы_прогонки (Весенний семестр), страница 2

Далееможно за один проход найти значения внутренних переменных.Н.Новгород, 2010 г.Параллельные численные методы.31 из 46Параллельная блочная прогонка (вариант 2)Рассмотренный способ распараллеливания уже дает хорошиерезультаты, но можно использовать лучшую стратегию исключениянеизвестных.Прямой ход нового алгоритма будет таким же.Обратный ход: каждый поток исключает наддиагональные элементы,начиная со своего предпоследнего, и заканчивая последним дляпредыдущего блока матрицы.Н.Новгород, 2010 г.Параллельные численные методы.32 из 46Параллельная блочная прогонка (вариант 2)a1c1a2d1c2a3d2c3d3a4c4b5a5f6f7f8d4c5a6d5c6a7d6c7a8c8b9a9f10f11f12Н.Новгород, 2010 г.d7Параллельные численные методы.d8c9a10d9c10a11d10c11d11a12d1233 из 46Параллельная блочная прогонка (вариант 2)a1c1d1a2a3g2d2c3d3a4c4b5a5f6f7f8d4c5d5a6a7g6d6c7d7a8c8b9a9f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.d8c9d9a10a11g10d10c11d11a12d1234 из 46Параллельная блочная прогонка (вариант 2)a1a2a3g1d1g2d2c3d3a4c4b5a5f6f7f8d4a6a7g5d5g6d6c7d7a8c8b9a9f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.d8a10a11g9d9g10d10c11d11a12d1235 из 46Параллельная блочная прогонка (вариант 2)a1a2a3g1d1g2d2c3d3a4b5f6f7f8a5a6a7g5d4g5d5g6d6c7d7a8b9f10f11f12Н.Новгород, 2010 г.Параллельные численные методы.a9a10a11g8d8g9d9g10d10c11d11a12d1236 из 46Параллельная блочная прогонка (вариант 2)Можно сформировать вспомогательную задачу меньшего размера.Исключим из матрицы все строки каждой полосы, кроме последней, врезультате получим систему уравнения относительно части исходныйнеизвестных.Даная система будет содержать всего p уравнений, и также будеттрехдиагональной.

Ее можно решить последовательным методомпрогонки.После того, как эта система будет решена, станут известны значениянеизвестных на нижних границах полос разделения данных. Далееможно за один проход найти значения внутренних переменных вкаждом потоке.Н.Новгород, 2010 г.Параллельные численные методы.37 из 46Параллельная блочная прогонка (вариант 2)Н.Новгород, 2010 г.a4g4f8a8g8d8f12a12d12Параллельные численные методы.d438 из 46Оценка эффективностиT1nnSp pTp 2 n  p2n  p 2pУскорениеДля систем с общей памятью n>>p, поэтомуускорениеН.Новгород, 2010 г.npSp  p22n  p2Параллельные численные методы.39 из 46Результаты экспериментовСравнение разных видов прогонкиT, сек.1,00,90,80,70,60,50,40,30,20,10,0168050408400117601512018480N, тыс.Правая прогонкаН.Новгород, 2010 г.Левая прогонкаПараллельные численные методы.MKL40 из 46Результаты экспериментовУскорение параллельной встречной прогонкиУскорение2,352,32,252,22,152,12,0521680504084001176015120Сравнение с правой прогонкойН.Новгород, 2010 г.Параллельные численные методы.18480218402520028560N, тыс.Сравнение с левой прогонкой41 из 46Результаты экспериментовСравнение параллельной встречной и параллельной блочной прогонкиT, сек.2,01,81,61,41,21,00,80,60,40,20,01680N, тыс.5040840011760 15120 18480 21840 25200Встречная прогонкаПараллельная в 2 потока (1 вар.)Параллельная в 2 потока (2 вар.)Н.Новгород, 2010 г.Параллельные численные методы.42 из 46Результаты экспериментовУскорение параллельной блочной прогонкиУскорение2,52,0N, тыс.168084001,51176018480252001,00,52Н.Новгород, 2010 г.345Параллельные численные методы.678Число потоков43 из 46ЛитератураВержбицкий В.М.

Численные методы (математическийанализ и обыкновенные дифференциальные уравнения).– М.: Высшая школа, 2001.2. Самарский А.А., Гулин А.В. Численные методы. – М.:Наука, 1989.3. Голуб Дж., Ван Лоун Ч. Матричные вычисления. – М.:Мир, 1999.1.Н.Новгород, 2010 г.Параллельные численные методы.44 из 46Ресурсы сети Интернет4.5.Интернет-университет суперкомпьютерных технологий.[http://www.hpcu.ru].Intel Math Kernel Library Reference Manual.[http://software.intel.com/sites/products/documentation/hpc/mkl/mklman.pdf].Н.Новгород, 2010 г.Параллельные численные методы.45 из 46Авторский коллективБаркалов Константин Александрович,к.ф.-м.н., старший преподаватель кафедрыМатематического обеспечения ЭВМ факультета ВМК ННГУ.barkalov@fup.unn.ruКоды учебных программ разработаны Маловой Анной иСафоновой ЯнойН.Новгород, 2010 г.Параллельные численные методы.46 из 46.