Мелкозернистый параллелизм клеточно-автоматных моделей пространственной динамики Лекция 3 презентация

О.Л.
Лектор: к.ф.-м.н., Нечаева О. И.
Ассистент: Бессмельцев М.В.

к пространственно однородному устойчивому состоянию

Класс 2
предельный цикл, КА стремится к устойчивому образу, или циклу

Класс 3
хаотическое поведение, КА входит в «странный» аттрактор

Класс 4
сложное поведение, универсальные вычисления, КА стремится к локализованным структурам, возможно движущимся

Ω(t+1)

1

2

3

4

Фазовая плоскость

Ω(t)

КА, затем изучается его поведение на предмет схожести с каким-либо физическим процессом.
Класс 2. Правила переходов строятся на основании знания физики взаимодействия элементарных частиц и фундаментальных законов природы.
Класс 3. Построение правил переходов по заданным наборам «вход-выход» с помощью алгоритмов обучения - клеточно-нейронные сети. Например, требуется подобрать взвешенный шаблон для получения заданного устойчивого состояния или мотивов.

= 2O

CO + O = CO2+2O

CO + ∅ = ∅ + CO

адсорбция СО

адсорбция О2

реакция

диффузия

Окисление CO на платиновом катализаторе:

CO

O O

∅ CO

p2

p3

CO O

CO ∅

p1

Pt

Устойчивые глобальные состояния
от отношения парциальных давлений

p1/p2

if rand <0.5, u=0 otherwise}

W =

1

a=0.2

1

1

1

1

1

1

0

0

0

0

0

0

0

КА с разными режимами функционирования

Реализация параллельных алгоритмов

наличие общей (SMP) или распределенной памяти (MPP)

Симметричные мультипроцессорные системы (SMP)
Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей.
В модели общей памяти параллельная программа представляет собой систему нитей (threads), взаимодействующих посредством общих переменных и примитивов синхронизации.
Массивно-параллельные системы (MPP)
Система состоит из однородных вычислительных узлов, включающих:
один или несколько центральных процессоров,
локальную память (прямой доступ к памяти других узлов невозможен),
коммуникационный процессор или сетевой адаптер
К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.)
Кластерные системы являются более дешевым вариантом MPP
В модели передачи сообщений параллельная программа представляет собой систему процессов, взаимодействующих посредством сообщений.

процессоре к времени решения той же задачи на системе из p таких же процессоров:



Эффективность – это отношение ускорения к числу процессоров:

коммуникации (при пересылках сообщений требуется время для инициализации посылки сообщения (латентность) и время передачи сообщения по сети)
Расходы на синхронизацию процессов

→ {(v,(i,j),(u(i,j+1)}

Пример некорректного поведения:

A={0,1}, M={(i,j)}, синхронный режим

j

i

0 1 2 3 4 5

0
1
2
3
4

Θ(2,2): S’(2,2)={(1,(2,2))(1(2,3))}
Θ(2,3): S’(2,3)={(0,(2,3))(1(2,4))}

T(2,2) ∩ T(2,3) = (2,3)

Вспомним условия корректности КА

в случае промаха
Контроль порядка исполнения операторов подстановки (биномиальное распределение)
??

b – количество клеток в блоке.
Итерация состоит из b стадий.
На каждой стадии выполняется синхронное применение оператора подстановки ко всем клеткам одного цвета.
Поскольку на каждой стадии шаблоны не пересекаются, результат не зависит от порядка обработки блоков.

Если машина с распределенной памятью: обмен границами происходит после каждой стадии.

программирования компьютеров с разделяемой памятью (SMP/NUMA). OpenMP можно использовать для программирования на языках Fortran и C/C++.

MPI – message passing interface - хорошо стандартизованный механизм для построения программ по модели обмена сообщениями. Существуют стандартные "привязки" MPI к языкам С, С++, Fortran 77, Fortran 90. Существуют бесплатные и коммерческие реализации почти для всех суперкомпьютерных платформ, а также для сетей рабочих станций UNIX и Windows NT. В настоящее время MPI - наиболее широко используемый и динамично развивающийся интерфейс из своего класса.

rank, size;
MPI_Init( &argc, &argv );
MPI_Comm_rank( MPI_COMM_WORLD, &rank );
MPI_Comm_size( MPI_COMM_WORLD, &size );
printf( "I am %d of %d\n", rank, size );
MPI_Finalize();
return 0;
}

По мере передачи каждый процессор увеличивает число на 1
#include // включение библиотеки MPI
#include
 
int main(int argc, char ** argv)
{
int size, rank, count;
float D1=123; // число, которое будет передаваться и обрабатываться
MPI_Status st;
MPI_Init (&argc, &argv); // инициализация программы
MPI_Comm_size (MPI_COMM_WORLD, &size); // получаем количество процессоров
MPI_Comm_rank (MPI_COMM_WORLD, &rank); // получаем номер текущего процессора
if (rank==0) // обмен начинается от нулевого процессора
{
// отправляем число 1-му процессору
MPI_Send (&D1, 1, MPI_FLOAT, 1, 12, MPI_COMM_WORLD);
// принимаем результат от 3-го процессора
MPI_Recv (&D1, 1, MPI_FLOAT, 3, 12, MPI_COMM_WORLD, &st);
}
else // для остальных процессоров
{
// принимаем число от предыдущего процессора
MPI_Recv (&D1, 1, MPI_FLOAT, rank-1, 12, MPI_COMM_WORLD, &st);
// увеличиваем принятое число на 1
D1+=1;
// пересылаем следующему процессору
MPI_Send (&D1, 1, MPI_FLOAT, (rank+1)%4, 12, MPI_COMM_WORLD);
};
printf ("process %d, received %f\n",rank,D1); // вывод числа
MPI_Finalize(); // завершение работы в среде MPI
return 0;
};

в другой массив.
#pragma omp parallel
{
#pragma omp for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
Например, для четырехпроцессорного компьютера и size=100, выполнение итераций 1—25 могло бы быть поручено первому процессору, 26—50 — второму, 51—75 — третьему, а 76—99 — четвертому. Это статическая политика планирования.
Достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу.
Если исключить директиву #pragma omp for, каждый поток выполнит полный цикл for, проделав много лишней работы:
#pragma omp parallel
{
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
Можно написать короче:
#pragma omp parallel for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
Замечание: в этом цикле нет зависимостей, т. е. одна итерация цикла не зависит от результатов выполнения других итераций.

модель клеточного автомата
Параллельная реализация клеточно-автоматных алгоритмов

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

Третья часть
Рассмотрение конкретных КА-моделей в гидродинамике, поверхностной химии, биологии, кинетике и синтезе нано систем, и др.
Вычислительные свойства клеточных автоматов