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

Тема в разделе "Общие вопросы по С и С++", создана пользователем rrrFer, 26 сен 2016.

  1. rrrFer

    rrrFer Well-Known Member
    Команда форума C\C++ Team

    Регистрация:
    6 сен 2011
    Сообщения:
    1.324
    Симпатии:
    36
    Задание
    Реализовать компьютерную реализацию классического варианта игры «Жизнь». С использование средств 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).

    Код (C):
    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;
            }
        }
    Далее распаралливаем программу, воспользовались директивой
    Код (C):
    #pragma omp parallel for
    , которая распараллеливает цикл, следующий за директивой. Также указываем с помощью команды
    Код (C):
    shared()
    те переменные, которые потоки будут использовать совместно:
    Код (C):
    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» отвечает за расчет будущего значения проверяемой клетки.

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


    Код (C):
    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

    Исходный код программы целиком:
    Код (C):
    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;
    }
     
Загрузка...

Поделиться этой страницей