Решено Реализация игры Жизнь (поле замкнуто в тор) на С++ и OpenMP

R

rrrFer

#1
Задание
Реализовать компьютерную реализацию классического варианта игры «Жизнь». С использование средств OpenMP.

Классический вариант игры «Жизнь»:
  • Поле – двумерная матрица, замкнутая в тор;
  • Состояние автомата – бинарное (0-мертв, 1-жив);
  • S(t) – исходное состояние;
  • N(t) – количество «живых» соседей.
Описание переходов автомата:
  1. S(t) = 1, N(t) < 2 –> S(t+1) = 0;

  2. S(t) = 1, N(t) > 3 –> S(t+1) = 0;

  3. S(t) = 0, N(t) = 3 –> S(t+1) = 1.
Описание алгоритма

В компьютерных реализациях игры обычно верхняя граница поля «соединена» с нижней, а левая граница — с правой, что представляет собой эмуляцию поверхности тора, но на экране поле всегда отображается в виде равномерной сетки.

Простейший алгоритм «смены поколения» последовательно просматривает все ячейки решетки и для каждой ячейки подсчитывает живых соседей, определяя судьбу каждой клетки (не изменится, умрет, родится). Такой простейший алгоритм использует два двумерных массива — один для текущего поколения, второй — для следующего.

В нашей программе, изначальную матрицу мы задаем случайными числами (0 или 1).

Код:
for(int i=0;i<field_width;i++)

    {
        for(int j=0;j<field_height;j++)
        {
            fields[i][j]=rand()%2+0;
            temp_fields[i][j]=fields[i][j];
            new_fields[i][j]=0;
        }
    }
Далее распаралливаем программу, воспользовались директивой
Код:
#pragma omp parallel for
, которая распараллеливает цикл, следующий за директивой. Также указываем с помощью команды
Код:
shared()
те переменные, которые потоки будут использовать совместно:
Код:
do
    {
        isChange=0;
        {
            #pragma omp parallel for   
                    shared(field_height,field_width,new_fields,fields) reduction(+:isChange)
            for (int i=0;i<field_width;i++)
                for(int j=0;j<field_height;j++)
                {
                    int r = ChangeNeibours(flag, i, j, isChange);
                    if (r != 0)
                    {
                        isChange += r;
                    }
                }
        }
        if (flag==0) flag++;
        else flag--;
        toCount++;
        if(isChange==0)
        {
            cout << "Достигнуто стационарное состояние!";
            break;
        }
    }while(toCount!=count);
Далее в программе, мы прозводим анализ нашей матрицы. Функция «ChangeNeibours» отвечает за расчет будущего значения проверяемой клетки.

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


Код:
int checkBorders(int index,int size)

{
    int result;
    if (index==-1)
    {
        result=size-1;
        return result;
    }
    if (index==size)
    {
        result=0;
        return result;
    }
    return index;
}

Пояснения к коду:

В программе распараллеливание происходит по стобцам проверяемой матрицы. Для всех потоков задействованы глобальные переменные ( field_height, field_width, new_fields, fields) – соответственно высота матрицы, ширина матрицы, и две матрицы, ответственные за хранение текущего и будущего игровых полей). Переменная «isChange» вынесена в директиву reduction, что позволяет отслеживать стационарность системы в целом.

Загруженность ядер процессора:
Последовательное выполнение программы:
1.png
Параллельное выполнение программы (с подключенным openMP):
2.png
Из графиков видно что во время запуска двух разных программ ядра процессора компьютера загружены по разному. При последовательном запуске компьютер выделяет 25% процессорного времени. При параллельном загрузка происходит на все 100%.


Сравним длительность работы программы при последовательном и параллельном выполнениях. Начальные условия: поле размером 100 на 100, количество итераций 10000.

Как мы видим из результататов: параллельное выполнение программы значительно меньше тратит времени на ее выполнение. Программа выполнялась на 4 ядерном процессоре с 8 потоками.

Снимок экрана из 2016-09-26 15-07-15.png

Исходный код программы целиком:
Код:
int checkBorders(int index,int size);
void printFields(int flag);
int ChangeNeibours(int flag,int i,int j,int isChange);


const int field_width=100; //длина поля
const int field_height=100;    //ширина поля
bool fields[field_width][field_height];
bool new_fields[field_width][field_height];
bool fields2[field_width][field_height];
bool new_fields2[field_width][field_height];
bool temp_fields[field_width][field_height];
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"Russian");
    int isChange;
    int count;
    int toCount;
    int flag=0;
    long t1=0;
    long t2=0;
    int iter=0;
    srand(time(NULL));
    for(int i=0;i<field_width;i++)
    {
        for(int j=0;j<field_height;j++)
        {
            fields[i][j]=rand()%2+0;
            temp_fields[i][j]=fields[i][j];
            new_fields[i][j]=0;
        }
    }
    count=100000; //количество ходов
    toCount=0;
    t1=GetTickCount();
    do
    {

        isChange=0;
        {
            for (int i=0;i<field_width;i++)
            {
                for(int j=0;j<field_height;j++)
                {
                    iter++;
                    isChange+=ChangeNeibours(flag,i,j,isChange);
                }
            }
        }
        if (flag==0) flag++;
        else flag--;
        toCount++;
        if(isChange==0)
        {
            cout << "Достигнуто стационарное состояние!";
            break;
        }
    }while(toCount!=count);
    t2=GetTickCount();
    cout<<"Длительность последовательного процесса "<< t2-t1 << "\n";
    //cout<<"Количество итераций: "<<iter<<"\n";
    iter=0;
    for(int i=0;i<field_width;i++)
    {
        for(int j=0;j<field_height;j++)
        {
            fields2[i][j]=fields[i][j];
            fields[i][j]=temp_fields[i][j];
        }
    }
    flag=0;
    toCount=0;
    t1=GetTickCount();
    do
    {
        isChange=0;
        {
            #pragma omp parallel for shared(field_height,field_width,new_fields,fields) reduction(+:isChange)
            for (int i=0;i<field_width;i++)
            {
                for(int j=0;j<field_height;j++)
                {
                    int r = ChangeNeibours(flag, i, j, isChange);
                    if (r != 0)
                    {
                        isChange += r;
                    }

                }
            }
        }
        if (flag==0) flag++;
        else flag--;
        toCount++;
        if(isChange==0)
        {
            cout << "Достигнуто стационарное состояние!";
            break;
        }
    }while(toCount!=count);
    t2=GetTickCount();
    cout<<"Длительность параллельного процесса "<< t2-t1;
    _getch();
    return 0;
}

int checkBorders(int index,int size)
{
    int result;
    if (index==-1)
    {
        result=size-1;
        return result;
    }
    if (index==size)
    {
        result=0;
        return result;
    }
    return index;
}

int ChangeNeibours(int flag,int i,int j,int isChange)
{
    int neib=0;
    switch (flag)
    {
    case 0:{
        if (fields[i][checkBorders(j-1,field_height)]==1) //down
            neib++;
        if (fields[i][checkBorders(j+1,field_height)]==1) //up
            neib++;
        if (fields[checkBorders(i-1,field_width)][j]==1) //left
            neib++;
        if(fields[checkBorders(i+1,field_width)][j]==1) //right
            neib++;
        if (fields[i][j]==0)
        {
            if ((neib>=2)&&(neib<4))
            {
                new_fields[i][j]=1;
                isChange++;
            }
            else
            {
                new_fields[i][j]=0;
            }
        }
        else
        {   
            if ((neib<2)||(neib==4))
            {
                new_fields[i][j]=0;
                isChange++;
            }
            else
            {
                new_fields[i][j]=1;
            }
        }
           }
           break;
    case 1:{
        if (new_fields[i][checkBorders(j-1,field_height)]==1) //down
            neib++;
        if (new_fields[i][checkBorders(j+1,field_height)]==1) //up
            neib++;
        if (new_fields[checkBorders(i-1,field_width)][j]==1) //left
            neib++;
        if(new_fields[checkBorders(i+1,field_width)][j]==1) //right
            neib++;
        if (new_fields[i][j]==0)
        {
            if ((neib>=2)&&(neib<4))
            {
                fields[i][j]=1;
                isChange++;
            }
            else
            {
                fields[i][j]=0;
            }
        }
        else
        {   
            if ((neib<2)||(neib==4))
            {
                fields[i][j]=0;
                isChange++;
            }
            else
            {
                fields[i][j]=1;
            }
        }
        break;
           }
    }
    return isChange;
}