Способы адресации массивов

Введение

В данном разделе будет рассмотрены несколько способов адресации массивов и описаны необходимые изменения в программе, чтобы привести ее к виду, наиболее подходящему для распараллеливания.

Рассмотрим классическую двумерную задачу теплопроводности, решаемую методом Якоби.

Явный обход двумерной области

Наиболее простой способ реализовать задачу задачу заключается в явном обходе двумерного массива размера I×J:

for (i = 1; i < I - 1; i++) {
   for (j = 1; j < J - 1; j++) {
       A_new[i][j] = ( A_old[i+1][j] + A_old[i][j+1] + A_old[i-1][j] + A_old[i][j-1] ) / 4;
   }
}


Этот способ прост, но если нужно обсчитать не прямоугольную область, а область сложной формы,
то, во-первых, придется завести массивы на весь объемлющий прямоугольник (лишние данные), и, во-вторых, будет сложно написать правильные циклы.

Этот способ также неудобен для распараллеливания, поэтому необходимо завести структуры, описывающие область.

Описание области

Массивы A_old и A_new теперь одномерные, содержащие все ячейки области.

Массив Grid (сетка) хранит информацию о каждой ячейке сетки. А именно, каждый элемент массива — это структура, содержащая:
  • логические координаты ячейки: поля i и j;
  • является ли ячейка внутренней: поле is_inner.

Подчеркнем, что все массивы A_old, A_new и Grid одинаковой длины. И информация про одну ячейку хранится в элементах с одинаковым индексом.

Так же потребуется функция GetCell, которая по двум координатам i и j вернет номер ячейки в массивах.

Тогда основной цикл запишется следующим образом:

for (n = 0; n < N; n++) {
   if (Grid[n].is_inner) { // если внутрення ячейка
       int i = Grid[n].i; // i-ая координата
       int j = Grid[n].j; // j-ая координата
       A_new[n] =  ( A_old[GetCell(i+1,j)] + A_old[GetCell(i,j+1)] + A_old[GetCell(i-1,j)] + A_old[GetCell(i,j-1)] ) / 4;
   }
}


Данный способ уже лучше применим для распаралленивания. Но еще мешает функция GetCell, от которой нужно избавиться, записав номера соседей в массив Grid.

Хранение соседей

Данный способ очень похож на предыдущий. В нем в каждом элементе массива Grid хранятся:
  • логические координаты ячейки: поля i и j;
  • является ли ячейка внутренней: поле is_inner;
  • номера (в массивах) соседних элементов: поля north,  east, south, west.

Тогда цикл запишется следующим образом:

for (n = 0; n < N; n++) {
   if (Grid[n].is_inner) { // если внутрення ячейка
       A_new[n] =  ( A_old[Grid[n].north] + A_old[Grid[n].east] + A_old[Grid[n].south] + A_old[Grid[n].west] ) / 4;
   }
}


Данный способ подходит для применения распараллеливания методом преобразования массивов, описанным выше. В нем массивы A_old, A_new, Grid вместо всех ячеек (в последовательном варианте) будут хранить свои ячейки для данного процесса.

Если предполагается использовать неструктурные сетки, то можно сделать еще одно обобщение.

Неструктурные сетки

В случае неструктурных сеток количество соседей может быть разное у разных ячеек. Поэтому вместо жесткого списка соседей в элементах массива Grid необходимо хранить список соседей. А так же для расчета потребуются физические координаты ячеек x и y. В итоге, в элементе массива Grid хранятся:
  • логические координаты ячейки: поля i и j;
  • физические координаты ячейки: поля x и y;
  • является ли ячейка внутренней: поле is_inner;
  • количество соседей: поле neighbours_num;
  • номера соседей: поле neighbours.

В результате цикл запишется следующим образом:

for (n = 0; n < N; n++) {
   if (Grid[n].is_inner) { // если внутрення ячейка
        A_new[n] = 0;
       for (m = 0; m < Grid[n].neighbours_num; m++) { // обход всех соседей
            A_new[n] += A_old[Grid[n].neighbours[m]];
       }
       A_new[n] /= Grid[n].neighbours_num; // вычисление среднего арифметического значения всех соседей
    }
}


Отметим, что данный пример программы не совсем корректен с физической точки зрения, т.к. не учитывает физические координаты ячеек.

Заключение

После проведенных модификаций получаем программу, в которой в отдельном массиве Grid хранятся данные о сетке (если сетка не адаптивная, то эти данные не изменяются), а в других массивах (таких как A_new и A_old) хранятся значения физических переменных в ячейках массива.

Когда данные представлены в таком виде, разделение их между параллельно работающими процессами становится обозримой и автоматизируемой задачей.
Comments