Отчёт_неявная_схема (Весенний семестр), страница 2

В нём можно свободно использоватьopenmp. Второй внутренний цикл выполняет прямой ход метода прогонки в730025064 узла( 256ядер )Ускорение200150256узлов( 1024ядра )1005000500010000150002000025000Размер сеткиРис 8: Ускорение алгоритма c openmp на 64, 256 узлах в сравнении с 1 узломлокальной области. Здесь НЕЛЬЗЯ использовать openmp ( например, для0.35Эффективность ( 1 ~ 100% )0.3256узлов( 1024ядра )0.250.20.1564 узла( 256ядер )0.10.05005000100001500020000Размер сеткиРис 9: Эффективность алгоритма c openmp на 64, 256 узлах825000организации встречной прогонки ), поскольку мы можем выполнить толькопрямой ход. Группа функций INTERACT отвечает за взаимодействие процессов( пересылку нижних строк матрицы. Здесь также нельзя использовать openmp.Однако openmp нужно и можно использовать для организации метода встречнойпрогонки в «главном» процессе каждого столбца на первом этапе и каждой строкина втором этапе, когда происходит решение трехдиагональной СЛАУ для матрицыиз последних строк; что и делается.Наконец, третий внутренний цикл представляет собой модифицированныйобратный ход метода прогонки и также может выполняться лишь последовательно.На Рис.

7 приведено соотношение времени работы программы c использованиемopenmp ( версия, использованная во всех остальных тестах ) и программы, откудаиспользование openmp было удалено. Для последовательной версии алгоритмаданные не приводятся, т. к. последовательная версия алгоритма не используетopenmp по определению.

На Рис. 8 и Рис. 9, однако, приводятся графики ускоренияалгоритма без openmp на 64, 256 узлах по сравнению с последовательнымвариантом ( Для сеток больших размеров, которые не были рассчитаныпоследовательным алгоритмов, используется линейная интерполяция дляустановления возможного времени вычисления последовательным алгоритмов.Сетки такого размера в умещаются в оперативную память ) а также ихэффективность относительно пиковой производительности системы.7. Анализ результатов и заключение.Необходимо вкратце описать свойства реализованного алгоритма. Во-первых,часть с построением СЛАУ может выполняться одновременно и параллельно навсех узлах в процессе выполнения каждого шага по времени. Во-вторых, каждыйузел при расчете очередного шага по времени производит пересылку 2 *(local_length + local_width) данных и принимает столько же посредством MPI.Между независимыми узлами пересылки также могут выполняться параллельно.Наконец, использован модифицированный вариант алгоритма блочной прогонки, вкотором на обратном проходе зануляются наддиагональные элементы строксобственной полосы матрицы, начиная с предпоследней + последней строки спредыдущей полосы.

Ускорение этого алгоритма составляет примерноpn /(2n+ p 2) , где p – число блоков, n – число строк матрицы. Для систем с общейпамятью n >> p, то есть ускорение должно быть близким к p / 2. Из этого можносделать вывод о достаточно высокой эффективности представленной реализацииалгоритма, т. к. на при достаточно большом размере сетки на p процессах онускоряется приблизительно в p / 2 раз по сравнению с последовательным9вариантом. Фактическое значение ускорение по всему алгоритму превосходит p / 2по нескольким причинам. Во-первых, один шаг по времени включает не толькоалгоритм блочной прогонки, и некоторые из операций ( например, формированиеСЛАУ ) ускоряются именно в p раз. Во-вторых, планировщик задач Blue Gene / Pне позволяет запускать на моём аккаунте задачи менее чем на 16 узлов.

Отсюдамогут происходить некоторые накладные расходы в последовательном алгоритме.Если говорить более конкретно, то на обработку одного столбца на одном шаге повремени уходит ~N операций на формирование СЛАУ и ~3 * N операций нарешение этой СЛАУ методом прогонки. Используя P процессоров, мы получим~N/P + 6 * N / P операций, которые необходимо выполнить последовательно. Этоозначает 7 * N / P операций по сравнению с 4 * N для последовательногоалгоритма. То есть ускорение последовательного алгоритма на 64 узлах составилобы 36.57142...

. Реальное ускорение несколько больше, т. к. операцииформирования СЛАУ имеют большую вычислительную сложность, особенно всравнении с вычислением значений неизвестных на последнем этапе методапрогонки. Еще одним источником ускорения являются N ^ 2 операций поопределению граничных условий в начале каждого шага по времени, которыетакже распараллеливаются на p процессоров.Также нужно отметить, что использование openmp не дало существенногоприроста производительности. Это вызвано в первую очередь ограниченностьюиспользования openmp только для составления первоначальных СЛАУ и решенияСЛАУ для «глобальной» матрицы, размеры которой невелики.

В случае с BG/Pнаилучшимспособомвидитсяиспользоватьрежим-VN(http://hpc.cmc.msu.ru/bgp/jobs/modes ), который позволяет каждому ядру на узлефункционировать как полноценный MPI процесс. Это средствоподдерживается на аппаратном уровне, кроме того, в рамках MPI процессвыполнения шага по времени распараллеливается полностью, в то время какв openmp область параллельного выполнения весьма ограничена.8.

Дополнительные материалы.Верификатор — простая консольная программа, которая сверяет результатыработы либо последовательного и параллельного алгоритмов, либо сверяет работупоследовательного алгоритма с файлом, содержащим финальное стабильноесостояние области, к которому стремится точное решение.// Basic inclusions.#include <cstdlib>#include <cstdio>10#include <fstream>#include <iostream>// No MPI and project inclusions here.// Using directives.using namespace std;// This function reads data from a filevoid read_file(double* matrix, const int size, const char* file_name) {// Filestream...ifstream read_file;read_file.open(file_name, ios::in);// Read data.for (int i = 0; i < size; ++i) {read_file >> matrix[i];}read_file.close();}// This function calculates the average mistake.

It should be close to zero for correctsolutions.// Performance doesn't matter at all here, since we run test examples.double calc_corr(double* left_mtrx, double* right_mtrx, int length, int width, int p_size,const int mode) {// Result and operational elements.double result = 0;double left_element = 0;double right_element = 0;// Number of blocks in matrix and global addresses.int side_size = (int)round(sqrt(p_size));int para_adress = 0;int test_adress = 0;// Local addresses.int l_para_adress = 0;int l_test_adress = 0;if (mode == 1) { // Verify parallel.// Operate each block separately.std::cout << "side:" << side_size << "\n";for (int i = 0; i < side_size; ++i) { // X axisfor (int j = 0; j < side_size; ++j) { // Y axis// Set rank and global address.para_adress = (i * side_size + j) * (length /side_size) * (width / side_size);test_adress = i * side_size * (length / side_size) *(width / side_size) + j * (width / side_size);// Inner cycle - work with elements.for (int p = 0; p < (length / side_size); ++p) { // X11axis in outer cycle.for (int q = 0; q < (width / side_size); ++q) {// Y axis in inner cycle.l_para_adress = para_adress + p *(width / side_size) + q;l_test_adress = test_adress + p *width + q;result +=pow(abs(left_mtrx[l_test_adress] - right_mtrx[l_para_adress]), 2);}}}}}else { // Verify sequental.for (int i = 0; i <= length * width; ++i) {result += pow(abs(left_mtrx[i] - right_mtrx[i]), 2);}}return sqrt(result / (length * width));}// Main function :)// This program is very simple.

It takes two files as arguments.// Also number of processors used for parallel calculation and// global field size should be passed as parameters. Then the program// calculates difference in sequental and parallel solutions.// It is NOT supposed to run on a supercomputer... it's just a check.void main(int argc, char* argv[]) {// Field size etc parameters...int p_size = atoi(argv[1]);int global_length = atoi(argv[2]);int global_width = atoi(argv[3]);// Memory for matrices.double* seq_matrix = new double[global_length * global_width];double* par_matrix = new double[global_length * global_width];// Here we read data.read_file(seq_matrix, global_length * global_width, argv[4]);read_file(par_matrix, global_length * global_width, argv[5]);// Here we set mode.int mode = atoi(argv[6]);// Now calculate the average mistake.std::cout << calc_corr(seq_matrix, par_matrix, global_length, global_width,p_size, mode);// Free memory.delete seq_matrix;delete par_matrix;}129.

Приложение 1. Последовательная версия программы.И последовательная, и параллельная версия программы состоят из трёх файлов —Trans_solver.h , Trans_solver.cpp , Main.cpp . Класс Trans_solver отвечает завычислительный процесс. Следует обратить внимание, что последовательнаяверсия программы также использует MPI, хотя процессы никак невзаимодействуют между собой. Это — необходимая мера для того, чтобыпрограмму можно было поставить в общую очередь на выполнение на системеBlue Gene / P.// ------------------------------------------------------------------------------// This file contains class to solve given transcalency equations.// ------------------------------------------------------------------------------#define _USE_MATH_DEFINES// MPI inclusions.#include <mpi.h>// Basic#include#include#include#include#includeinclusions.<cstdlib><cstdio><iostream><fstream><cmath>// Definitions// Material is considered to be stainless steel.#define DEFAULT_LAMBDA 1.0 // Lambda.#define DEFAULT_C 1.0 // C.#define DEFAULT_RO 1.0 // Ro.// Timestep is considered 0.01 second.#define DEFAULT_T_STEP 0.01// Grid steps are considered M_PI both for x and y axis.#define DEFAULT_X_STEP M_PI#define DEFAULT_Y_STEP M_PI// MPI_Sorter class is used to implement a sorting network to sort array fragments.