Библиотека параллельной декомпозиции больших сеток
GridSpiderPar
ОГЛАВЛЕНИЕ
Библиотека параллельной декомпозиции больших сеток GridSpiderPar
Библиотека включает в себя два метода декомпозиции GeomDecomp и IncrDecomp. Параллельный алгоритм геометрической декомпозиции сеточных данных GeomDecomp основан на алгоритме рекурсивной координатной бисекции [1], параллельный инкрементный алгоритм декомпозиции графов IncrDecomp - на инкрементном алгоритме декомпозиции графов [1, 2].
Для работы библиотеки GridSpiderPar необходимо наличие двух библиотек TetrMesh (библиотека распределенного хранения и обработки тетраэдральных сеток Сукова С.А., ИПМ им. М.В. Келдыша РАН) и ParSort (библиотека параллельной сортировки больших объемов данных Якобовского М.В., ИПМ им. М.В. Келдыша РАН, http://lira.imamod.ru/FondProgramm/Sort/). Также должна быть установлена библиотека сжатия zlib с сайта http://zlib.net/ .
Все функции в случае успеха возвращают 0, иначе 1.
int GeomDecomp(int *nvPr, float *xyz, int *part, float **treeCGl, int
**treePGl, float **treeCL, int **treePL, int
*dtPr, int *ntGl, int
ndim, int npart, int
ng, int mpid, int
nproc, MPI_Comm comm, MPI_Group group);
- параллельный алгоритм геометрической декомпозиции сеточных данных;
int *nvPr - массив чисел вершин на процессорах. Предполагается,
что вершины распределены по процессорам по номерам: первые nvPr[0] вершин расположены на нулевом процессоре,
следующие nvPr[1] – на первом процессоре и т.д.
Размер массива nproc;
float *xyz – массив координат вершин: xyz[0], .., xyz[ndim – 1] – координаты x, y, z нулевой
вершины, xyz[ndim], .., xyz[2 * ndim – 1] – координаты первой вершины и т.д. Размер
массива ndim * n, где n - число вершин
на данном процессоре (n = nvPr[mpid]);
int *part – массив доменов вершин, в который будет записано
итоговое разбиение. Размер массива n;
float **treeCGl – двоичное дерево глобального разбиения вершин по
процессорам, в котором будут сохранены координаты медиан разбиений на две части
на каждом этапе рекурсии. Память на массив будет выделена алгоритмом GeomDecomp. Если в сохранении данной информации нет
необходимости, следует передать NULL. Построение
деревьев позволяет определять домены, в которые попадают вершины при
существующем разбиении. В процессе выполнения параллельной геометрической
декомпозиции сетки на каждом процессоре создается глобальное дерево разбиения
вершин по процессорам и массив локальных деревьев разбиений вершин по доменам
на каждом из процессоров;
int **treePGl – двоичное дерево глобального разбиения по процессорам,
в котором будут сохранены номера вершин медиан разбиений на две части и номера
координат, по которым производилось деление, на каждом этапе рекурсии. Память
на массив будет выделена алгоритмом GeomDecomp. Если
в сохранении данной информации нет необходимости, следует передать NULL;
float **treeCL – двоичные деревья локального разбиения по доменам на
каждом из процессоров, в которых будут сохранены координаты медиан. Память на
массив будет выделена алгоритмом GeomDecomp. Если
информация не нужна, следует передать NULL;
int **treePL – двоичные деревья локального разбиения по доменам на
каждом из процессоров, в которых будут сохранены номера вершин медиан и номера
координат. Память на массив будет выделена алгоритмом GeomDecomp. Если информация не нужна, следует передать NULL;
int *dtPr – массив смещений локальных деревьев процессоров в treeCL и treePL. Размер массива nproc + 1. Память на массив будет выделена алгоритмом GeomDecomp. Если информация не нужна, следует передать NULL;
int *ntGl – в этот аргумент будет
записано число медиан в глобальных деревьях treeCGl и treePGl. Если информация не нужна, следует передать NULL;
int ndim – размерность сетки;
int npart – число доменов, на которое нужно
разбить;
int ng – параметр нужен, когда GeomDecomp используется
для предварительного распределения сетки по npart процессорам. Тогда ng – число доменов, которые потом будут сформированы на
процессорах. В этом случае GeomDecomp
распределит на каждый из процессоров столько вершин, сколько будет в
сформированных на нем доменах. При обычном разбиении на равные домены в ng следует
передать 0;
int mpid – идентификатор процесса;
int nproc – число процессов;
MPI_Comm comm – коммуникатор;
MPI_Group group – MPI группа. Группа для
коммуникатора MPI_COMM_WORLD создается вызовом MPI_Comm_group(MPI_COMM_WORLD,&group);
int IncrDecomp(int *nvPr, int *xadj,
int *adjncy, int
*vwgt, int *adjwgt, float
*xyz, char *bord, int
*part, int ndim, int
ng, int nprocGeom, int
mpid, int nproc, MPI_Comm comm, MPI_Group
group);
- параллельный
инкрементный алгоритм декомпозиции графов;
int *nvPr - массив чисел вершин на
процессорах. Предполагается, что вершины распределены по процессорам по
номерам: первые nvPr[0] вершин
расположены на нулевом процессоре, следующие nvPr[1] – на первом процессоре и т.д. Размер массива nproc;
int *xadj - индексы начал списков соседей
каждой вершины в массиве adjncy. Размер массива n + 1, где n - число вершин
на данном процессоре (n = nvPr[mpid]);
int *adjncy - массив соседей вершин. Соседи
вершины i хранятся в массиве adjncy, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n];
int *vwgt - массив весов вершин. Размер
массива n. Если все вершины одного веса,
следует передать NULL;
int *adjwgt - массив весов ребер. Веса ребер
вершины i хранятся в массиве adjwgt, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n]. Если весов на
ребрах нет, следует передать NULL;
float *xyz - массив координат вершин: xyz[0], .., xyz[ndim – 1] – координаты
x, y, z нулевой вершины, xyz[ndim], .., xyz[2 * ndim – 1] – координаты
первой вершины и т.д. Размер массива ndim * n;
char *bord - массив геометрической границы сетки. Если вершина i принадлежит
геометрической границе сетки, то bord[i] = 1, иначе - 0. Размер массива n;
int *part - массив доменов вершин, в который будет записано
итоговое разбиение. Размер массива n;
int ndim - размерность сетки;
int ng - число доменов, на которое нужно
разбить;
int nprocGeom - число процессоров, на котором
будет выполняться геометрическая предекомпозиция вершин по процессорам алгоритмом
GeomDecomp;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
MPI_Group group - MPI группа. Группа для коммуникатора MPI_COMM_WORLD создается вызовом MPI_Comm_group(MPI_COMM_WORLD,&group);
int LocalRef(int *nvPr, int *xadj,
int *adjncy, int
*vwgt, int *adjwgt, int
*part, int *partL, int
ng, int mpid, int
nproc, MPI_Comm comm, MPI_Group group);
- локальное уточнение существующего
разбиения алгоритмом KL/FM, или жадным уточнением (Greedy Refinement), в
зависимости от значения константы GREEDYREF;
int *nvPr - массив чисел вершин на процессорах. Предполагается,
что вершины распределены по процессорам по номерам: первые nvPr[0] вершин расположены на нулевом процессоре,
следующие nvPr[1] – на первом процессоре и т.д.
Размер массива nproc;
int *xadj - индексы начал списков
соседей каждой вершины в массиве adjncy. Размер
массива n + 1, где n - число вершин на данном процессоре (n = nvPr[mpid]);
int *adjncy - массив соседей вершин. Соседи вершины i хранятся
в массиве adjncy, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n];
int *vwgt - массив весов вершин. Размер массива n. Если все вершины одного веса, следует передать NULL;
int *adjwgt - массив весов ребер. Веса ребер вершины i хранятся
в массиве adjwgt, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n]. Если весов на
ребрах нет, следует передать NULL;
int *part - массив доменов вершин в существующем разбиении. Размер
массива n;
int *partL – массив доменов вершин, в который будет записано
уточненное разбиение. Размер массива n;
int ng – число доменов;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
MPI_Group group - MPI группа. Группа для коммуникатора MPI_COMM_WORLD создается вызовом MPI_Comm_group(MPI_COMM_WORLD,&group);
int CheckGraphPart(int *nvPr, int *xadj,
int *adjncy, int
*vwgt, int *adjwgt, char
*bord, int *part, int
*partM, int ng, int
mpid, int nproc, MPI_Comm comm, MPI_Group
group);
- вывод информации о
текущем разбиении на домены;
int *nvPr - массив чисел вершин на процессорах. Предполагается,
что вершины распределены по процессорам по номерам: первые nvPr[0] вершин расположены на нулевом процессоре,
следующие nvPr[1] – на первом процессоре и т.д.
Размер массива nproc;
int *xadj - индексы начал списков
соседей каждой вершины в массиве adjncy. Размер
массива n + 1, где n - число вершин на данном процессоре (n = nvPr[mpid]);
int *adjncy - массив соседей вершин. Соседи вершины i хранятся
в массиве adjncy, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n];
int *vwgt - массив весов вершин. Размер массива n. Если все вершины одного веса, следует передать NULL;
int *adjwgt - массив весов ребер. Веса ребер вершины i хранятся
в массиве adjwgt, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n]. Если весов на
ребрах нет, следует передать NULL;
char *bord - массив геометрической границы сетки. Если вершина i принадлежит
геометрической границе сетки, то bord[i] = 1, иначе - 0. Размер массива n;
int *part - массив микро-доменов вершин. Размер массива n. Если формировались сразу домены, то part – массив доменов вершин. Вместо массива partM в
этом случае следует передать NULL;
int *partM – массив доменов для каждого микро-домена. Размер
массива равен числу микро-доменов;
int ng – число доменов;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
MPI_Group group - MPI группа. Группа для коммуникатора MPI_COMM_WORLD создается вызовом MPI_Comm_group(MPI_COMM_WORLD,&group);
int GetDomain(float
*treeCGl, int *treePGl, float *treeCL, int *treePL, int *dtPr, float
*xyz, int pp, int
*gr, char ncmpP, int
mpid, int nproc);
- получение домена
вершины в существующем геометрическом разбиении;
float **treeCGl – двоичное дерево глобального разбиения вершин по
процессорам, в котором сохранены координаты медиан разбиений на две части на
каждом этапе рекурсии методом GeomDecomp;
int **treePGl – двоичное дерево глобального разбиения по процессорам,
в котором сохранены номера вершин медиан разбиений на две части и номера
координат, по которым производилось деление, на каждом этапе рекурсии методом GeomDecomp;
float **treeCL – двоичные деревья локального разбиения по доменам на
каждом из процессоров, в которых сохранены координаты медиан методом GeomDecomp;
int **treePL – двоичные деревья локального разбиения по доменам на
каждом из процессоров, в которых сохранены номера вершин медиан и номера
координат методом GeomDecomp;
int *dtPr – массив смещений локальных
деревьев процессоров в treeCL и treePL. Размер
массива nproc + 1;
float *xyz - массив координат вершины (x, y, z), домен которой
нужно определить;
int pp - номер вершины;
int *gr - параметр, в который будет записан
домен вершины;
char ncmpP - параметр равен 1, если номера
вершин при получении геометрического разбиения не сравнивались, 0 - в противном
случае;
int mpid - идентификатор процесса;
int nproc - число процессов, которое
проводило разбиение методом GeomDecomp;
int GetPartMacroGraph(int *nvPr, int *xadj,
int *adjncy, int
*vwgt, int *adjwgt, char
*bord, int *part, int
**xadjMG, int **adjncyMG, int **vwgtMG, int
**adjwgtMG, char **bordMG, int ng, int mpid, int nproc, MPI_Comm comm, MPI_Group group);
- получение макро-графа
связей доменов;
int *nvPr - массив чисел вершин на процессорах. Предполагается,
что вершины распределены по процессорам по номерам: первые nvPr[0] вершин расположены на нулевом процессоре,
следующие nvPr[1] – на первом процессоре и т.д.
Размер массива nproc;
int *xadj - индексы начал списков
соседей каждой вершины в массиве adjncy. Размер
массива n + 1, где n - число вершин на данном процессоре (n = nvPr[mpid]);
int *adjncy - массив соседей вершин. Соседи вершины i хранятся
в массиве adjncy, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n];
int *vwgt - массив весов вершин. Размер массива n. Если все вершины одного веса, следует передать NULL;
int *adjwgt - массив весов ребер. Веса ребер вершины i хранятся
в массиве adjwgt, начиная с ячейки xadj[i] до xadj[i + 1], не
включая xadj[i + 1]. Размер массива xadj[n]. Если весов на
ребрах нет, следует передать NULL;
char *bord - массив геометрической границы сетки. Если вершина i принадлежит
геометрической границе сетки, то bord[i] = 1, иначе - 0. Размер массива n;
int *part - массив доменов вершин. Размер массива n;
int **xadjMG - указатель на массив индексов начал списков соседей
каждого домена. Память на массив будет выделена алгоритмом GetPartMacroGraph;
int **adjncyMG - указатель на массив соседей
доменов. Память на массив будет выделена алгоритмом GetPartMacroGraph;
int **vwgtMG - указатель на массив весов доменов. Память на массив
будет выделена алгоритмом GetPartMacroGraph;
int **adjwgtMG - указатель на массив весов ребер
между доменами. Память на массив будет выделена алгоритмом GetPartMacroGraph;
char **bordMG - указатель на массив гометрической границы макро-графа
доменов. Геометрической границе
макро-графа доменов принадлежат те домены, в которых есть вершины из
геометрической границы исходного графа. Память на массив будет выделена
алгоритмом GetPartMacroGraph;
int ng – число доменов;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
MPI_Group
group - MPI группа. Группа для коммуникатора MPI_COMM_WORLD создается вызовом MPI_Comm_group(MPI_COMM_WORLD,&group);
int ExchangeGr(int
*gr, int *vPr, char
*pathOut, char *str, int
npart, int ng, int
mpid, int nproc, MPI_Comm comm);
- запись доменов
вершин в бинарный файл с названием "<str>_on<npart>_<ng>".
Домен каждой вершины записывается числом типа int. Размер файла n * sizeof(int), где n - число вершин
на данном процессоре;
int *gr - массив доменов вершин. Размер
массива n;
int *vPr - массив чисел вершин на
процессорах. Предполагается, что вершины распределены по процессорам по
номерам: первые vPr[0] вершин расположены
на нулевом процессоре, следующие vPr[1] – на
первом процессоре и т.д. Размер массива nproc;
char *pathOut - путь к каталогу, в котором будет лежать файл с доменами вершин;
char *str - название функции, проводившей разбиение;
int npart – число доменов в разбиении;
int ng – будущее число доменов при
геометрическом преразбиении на число процессоров. 0, если не используется;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
int ExchangeGrCompress(int *gr, int n, char *pathOut, char
*str, int npart, int
ng, int mpid, int
nproc, MPI_Comm comm);
- запись доменов
вершин в бинарные файлы со сжатием. На выходе будут сформированы два файла с
названиями "<str>_on<npart>_<ng>_c" и "<str>_on<npart>_<ng>_cb";
int *gr - массив доменов вершин. Размер
массива n;
int n - число вершин на данном процессоре;
char *pathOut - путь к каталогу, в котором будут лежать файлы с доменами вершин;
char *str - название функции, проводившей разбиение;
int npart – число доменов в разбиении;
int ng – будущее число доменов при
геометрическом преразбиении на число процессоров. 0, если не используется;
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
int getGroupsCompress(char *fName, int *gr,
int *vtxdist, int
mpid, int nproc, MPI_Comm comm);
- считывание доменов вершин из сжатых файлов, записанных функцией ExchangeGrCompress.
char *fName - имя файла с путем к нему без "_c" и "_cb";
int *gr - массив, в который будут записаны домены вершин. Размер
массива n, где n - число вершин на данном процессоре;
int *vtxdist - массив распределения вершин по процессорам.
Предполагается, что вершины распределены по процессорам по номерам: на i-м процессоре расположены вершины с номерами от vtxdist[i] до vtxdist[i + 1], не
включая vtxdist[i + 1]. Размер массива nproc + 1:
int mpid - идентификатор процесса;
int nproc - число процессов;
MPI_Comm comm - коммуникатор;
Основные параметры задаются в файле "allhead.h".
MPIDP_MAIN - идентификатор процесса, информация о работе которого
будет выводиться во всех функциях, кроме IncrDecomp;
MPIDP_INCRDECOMP - идентификатор процесса,
информация о работе которого будет выводиться в начале IncrDecomp. После перераспределения доменов по процессам
информация будет выводиться с того процесса, на котором окажется больше всего
доменов;
UNWRAP_POROG_CONST - минимальный номер первой
несвязной оболочки. Разбиение считается хорошим, если минимальный номер первой
несвязной оболочки больше, либо равен, UNWRAP_POROG_CONST;
MIN_ENV_CONST - в плохих доменах производится
освобождение оболочек с номерами, меньшими MIN_ENV_CONST;
DISBAL_POROG_CONST - дисбаланс по числу вершин,
допустимый при захвате вершин. Рекомендуемое значение 10;
COMPRESS_OUT - если параметр равен 1, запись доменов в файл
производится со сжатием. Считывание, соответственно, аналогично.
GREEDYREF -
если параметр равен 1, то в алгоритме LocalRef используется
жадное уточнение (Greedy Refinement), иначе алгоритм KL/FM. Жадное уточнение
имеет меньшую временную зависимость от числа доменов, но не обладает
способностью выбираться из локальных минимумов. Разбиения, полученные
алгоритмом KL/FM, имеют меньший вес разрезанных ребер.
pInf1 - для печати дополнительной
информации по временам и результатам работы функций параметр выставляется
равным 1;
pInf2 - для печати информации по временам и результатам работы
основных функций параметр выставляется равным 1;
1. Головченко Е.Н. Параллельный пакет декомпозиции больших сеток // Математическое моделирование. 2011. Т. 23. № 10. 3-18.
2. Якобовский М.В. Инкрементный алгоритм декомпозиции графов. Вестник Нижегородского университета им. Н.И.Лобачевского. Серия «Математическое моделирование и оптимальное управление», Вып. 1(28). Нижний Новгород: Издательство ННГУ, 2005, с. 243-250.