Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский государственный университет»

Математический факультет

Кафедра ЮНЕСКО по новым информационным технологиям

ОТЧЕТ ПО СЕМЕСТРОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ

“Технологии параллельного программирования”

«Задача о 5 ферзях»

студентки 2 курса

Ладан Людмилы Эдуардовны

Направление 010500.62 - Математическое обеспечение и администрирование информационных систем

Кемерово 2013

Содержание

• Введение
• 1. Постановка задачи
• 2. Последовательный алгоритм
• 3. Параллельный алгоритм
• Заключение
• Литература
• Введение
• Реализовано две версии алгоритма: параллельная и последовательная.
• Основной принцип каждого из алгоритмов следующий: методом перебора на шахматной доске расставляются пять ферзей, таким образом, чтобы все поля были биты, причем второй ферзь всегда стоит после первого, третий всегда после второго и т.д.. За позицию ферзя отвечает соответствующий ему цикл. Программа останавливается, когда ферзи становятся в конечное положение, а именно последние пять полей на доске. В начале и в конце программы ставятся временные метки, считается их разность; полученное значение обозначает время, потраченное на выполнение алгоритма. Запуская параллельную программу на разном количестве процессоров, мы найдем время для каждого из случаев. На основе этих результатов можно будет говорить об ускорении и эффективности.
• 1. Постановка задачи
• Запрограммируйте параллельную программу, реализующую задачу о расстановке пяти ферзей на шахматной доске, при которой каждое поле будет находиться под ударом одного из них.
• 2. Последовательный алгоритм
• 1. Решение задачи находится полным перебором всех возможных расстановок ферзей на поле.
• 2. Выполняется 5 циклов по i1, i2, i3, i4, i5 (каждый для своего ферзя).
• 3. На каждом шаге цикла ферзи расставляются на поле. Это делается следующим образом:
• · Массив a из 64 элементов сначала обнуляется (для того чтобы подготовить его к новой расстановке ферзей)
• · В массив расставляются ферзи: первый ставится в начало массива, остальные выстраиваются относительно первого. Начальная позиция: заняты первые пять позиций, конечная: заняты последние пять позиций. Элемент массива, куда поставлен ферзь, обозначается за 2. Получаем пять элементов, равных 2, и шестьдесят один элемент, равных 0.
• · Заносим значения массива a[] в матрицу f[][]. В результате получается расстановка ферзей на шахматной доске.
• 4. После расстановки ферзей, помечаем клетки, которые находятся под ударом ферзя. В матрице f «подударные» элементы обозначаем за единицу. Делаем перебор матрицы, если элемент равен 2 (т.е. это ферзь), то заполняем для него подударные элементы (клетки). Это делается в 6 циклах: один для горизонтали, один для вертикали и 4 для диагоналей (вниз и вправо, вверх и влево, вверх и вправо, вниз и влево относительно позиции ферзя).
• 5. После расстановки ферзей и заполнения подударных клеток делаем проверку расстановки. Если есть в матрице нули, то расстановка не верная, т.е. под ударом находятся не все поля, переходим к следующему шагу цикла. Если нет нулей, то к счетчику количества найденных решений qs прибавляем единицу и переходим к следующему шагу цикла.
• Реализация последовательного алгоритма
• #include <stdio.h>
• #include <conio.h>
• #include <stdlib.h>
• #include <time.h>
• int main () {
• const int LBOX=9; ///длина стороны доски + 1
• const int QCELL=65; ///кол-во клеток на шахматной доске + 1
• const int LD=8; ///длина стороны доски
• const int CH=64; ///кол-во клеток на шахматной доске
• int f[LBOX][LBOX]; ///2х-мерный массив, шахматная доска
• int a[QCELL]; ///одномерный массив
• int i1=1, i2=1, i3=1, i4=1, i5=1; ///счетчики для каждого ферзя
• int i, j, k, l, m; ///счетчики
• int qzero=0, qs=0; ///кол-во нулей в матрице f и кол-во найденных решений
• double t1, t2; /// начальное и конечное время
• t1 = clock();
• for ( i1=1; i1<=CH-4; i1++ )
• {
• for ( i2=i1+1; i2<=CH-3; i2++ )
• {
• for ( i3=i2+1; i3<=CH-2; i3++ )
• {
• for ( i4=i3+1; i4<=CH-1; i4++ )
• {
• for ( i5=i4+1; i5<=CH; i5++ )
• {
• for ( l=1; l<=CH; l++ )
• {
• a[l]=0; ///обнуляем массив (0 - не размеченная клетка)
• }
• ///ферзи ставятся один за другим
• a[i1] = 2; ///клетка с 1-ым ферзем
• a[i2] = 2; ///клетка со 2-ым ферзем
• a[i3] = 2; ///клетка с 3-им ферзем
• a[i4] = 2; ///клетка с 4-ым ферзем
• a[i5] = 2; ///клетка с 5-ым ферзем
• k = 1;
• ///сохраняем значение из a[] в f[][] ("переносим" порядок ферзей на шахматную доску)
• for ( i=1; i<=LD; i++ )
• for ( j=1; j<=LD; j++ )
• {
• f[i][j] = a[k];
• k++;
• }
• for ( i=1; i<=LD; i++ )
• {
• for ( j=1; j<=LD; j++ )
• {
• if ( f[i][j]==2 ) ///если в клетке стоит ферзь
• {
• for ( m=1; m<=LD; m++ )
• if ( f[i][m]!=2 )
• f[i][m] = 1; ///заполняем горизонталь единицами (это строка находится под ударом ферзя)
• for ( m=1; m<=LD; m++ )
• if ( f[m][j]!=2 )
• f[m][j] = 1; ///заполняем вертикаль единицами (этот столбец находится под ударом ферзя)
• for ( m=1; m<=LD; m++ )
• if ( f[i+m][j+m]!=2 )
• if ( (i+m<=LD) && (j+m<=LD) )
• f[i+m][j+m] = 1; ///заполняем диагональ вниз-вправо единицами
• for ( m=1; m<=LD; m++ )
• if ( f[i-m][j-m]!=2 )
• if ( (i-m>=1) && (j-m>=1) )
• f[i-m][j-m] = 1; ///заполняем диагональ вверх-влево единицами
• for ( m=1; m<=LD; m++ )
• if ( f[i-m][j+m]!=2 )
• if ( (i-m>=1) && (j+m<=LD) )
• f[i-m][j+m] = 1; ///заполняем диагональ вверх-вправо единицами
• for ( m=1; m<=LD; m++ )
• if ( f[i+m][j-m]!=2 )
• if ( (i+m<=LD) && (j-m>=1) )
• f[i+m][j-m] = 1; ///заполняем диагональ вниз-влево единицами
• }
• }
• }
• qzero = 0;
• ///теперь ищем нули (т.е. клетки, непопавшие под удар ни одного из ферзей)
• for ( i=1; i<=LD; i++ )
• for ( j=1; j<=LD; j++ )
• {
• if ( f[i][j]==0 )
• qzero++;
• }
• if ( qzero==0 )
• {
• qs++;
• printf("%d\n",qs);
• }
• }
• }
• }
• }
• }
• t2 = clock();
• printf("\nQuantity of solutions = %d",qs);
• double t0;
• t0 = (t2-t1)/CLOCKS_PER_SEC;;
• printf("\n Time: %f", t0);
• getch();
• return 1;
• }

Результат работы последовательной программы

По завершению работы программа выводит количество найденных решений и время, потраченное на выполнения программы. Всего найдено 4860 решений, потраченное на нахождение время - 2,36 секунды.

3. Параллельный алгоритм

Распараллеливаем нахождение расстановок только для первого ферзя, т.е. решаем на разных процессорах только для внешнего цикла нахождения решения. Задаем изменение для первого ферзя, т.е. i1 , так чтобы

Для 2 процессоров:

1. будут искаться расстановки, когда 1 ферзь стоит на местах [1,1], [1,3], [1,5], [1,7] и т.д. Т.е каждая 2 клетка, начиная с первой.

2. Будут искаться расстановки, когда 1 ферзь стоит на местах [1,2], [1,4], [1,6] и т.д. Т.е каждая 2 клетка.

Причем, расстановки [1,1], [1,3], [1,5], [1,7] и т.д. для первого ферзя обсчитывает первый процессор, а расстановки [1,2], [1,4], [1,6] и т.д. - второй.

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

#include <mpi.h>

#include <stdio.h>

#include <stdlib.h>

int main (int argc,char *argv[])

{

const int LBOX=9; ///длина стороны доски + 1

const int QCELL=65; ///кол-во клеток на шахматной доске + 1

const int LD=8; ///длина стороны доски

const int CH=64; ///кол-во клеток на шахматной доске

int f[LBOX][LBOX]; ///2х-мерный массив = шахматной доске 8х8

int a[QCELL]; ///одномерный массив, нужно для расчета

int rank, size;

int i1=1,i2=1,i3=1,i4=1,i5=1;

int i, j, k, m, l, n0=0, qs=0, qzero=0, n1=0;

double t1,t2;

MPI_Status s;

MPI_Comm COMM;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&rank);

MPI_Comm_size(MPI_COMM_WORLD,&size);

for ( j=1; j<=64; j++ )

{

a[j]=0;

}

if ( rank==0 )

{

t1=MPI_Wtime();

}

for ( i1=rank+1; i1<=CH-4; i1=i1+size )

{

for ( i2=i1+1; i2<=CH-3; i2++ )

{

for ( i3=i2+1; i3<=CH-2; i3++ )

{

for ( i4=i3+1; i4<=CH-1; i4++ )

{

for ( i5=i4+1; i5<=CH; i5++ )

{

for ( l=1; l<=CH; l++ )

{

a[l] = 0;

}

a[i1] = 2;

a[i2] = 2;

a[i3] = 2;

a[i4] = 2;

a[i5] = 2;

k = 1;

for ( i=1; i<=LD; i++ )

for ( j=1; j<=LD; j++ )

{

f[i][j] = a[k];

k++;

}

for ( i=1; i<=LD; i++ )

{

for ( j=1; j<=LD; j++ )

{

if ( f[i][j]==2 )

{

for ( m=1; m<=LD; m++ )

if ( f[i][m]!=2 )

f[i][m] = 1; ///заполняем горизонталь единицами

for ( m=1; m<=LD; m++ )

if ( f[m][j]!=2 )

f[m][j] = 1; ///заполняем вертикаль единицами

for ( m=1; m<=LD; m++ )

if ( f[i+m][j+m]!=2 )

if ( (i+m<=LD) && (j+m<=LD) )

f[i+m][j+m] = 1; ///диагональ вниз-вправо

for ( m=1; m<=LD; m++ )

if ( f[i-m][j-m]!=2 )

if ( (i-m>=1) && (j-m>=1) )

f[i-m][j-m] = 1; ///диагональ вверх-влево

for ( m=1; m<=LD; m++ )

if ( f[i-m][j+m]!=2 )

if ( (i-m>=1) && (j+m<=LD) )

f[i-m][j+m] = 1; ///диагональ вверх-вправо

for ( m=1; m<=LD; m++ )

if ( f[i+m][j-m]!=2 )

if ( (i+m<=LD) && (j-m>=1) )

f[i+m][j-m] = 1; ///диагональ вниз-влево

}

}

}

qzero = 0;

for ( i=1; i<=LD; i++ )

for ( j=1; j<=LD; j++ )

{

if ( f[i][j]==0 )

qzero = qzero + 1;

}

if ( qzero==0 )

{

qs++;

// printf("%d\n",qs);

}

}

}

}

}

}

MPI_Reduce(&qs,&n0,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);

printf("%d\n",qs);

if ( rank==0 )

{

t2 = MPI_Wtime();

printf("\nTime: %e result=%d\n",t2-t1, n0);

}

MPI_Finalize();

return 1;

}

Итоговые результаты:

1. Для 1 процессора время, потребовавшееся на выполнение программы: 2,36

2. Для 2 процессоров время, потребовавшееся на выполнение программы: 1,22

3. Для 4 процессоров время, потребовавшееся на выполнение программы: 6,65

4. Для 6 процессоров время, потребовавшееся на выполнение программы: 4,76

Найдем ускорения и эффективности для 2х процессоров:

1. Для 2 процессоров: S_p=T₁ / T_p

T₁ = 2,36

T₂ = 1,22

Ускорение:

S_p= T₁ / T₂

S₂= 1.93

Эффективность:

E_p=(S_p/p)*100%

E₂=(1.93/2)*100=0.965

2. Для 4 процессоров: S_p=T₁ / T_p

T₁ = 2,36

T₄ = 6,65

Ускорение:

S_p= T₁ / T₄

S₄=0.354

Эффективность:

E_p=(S_p/p)*100%

E₄=(0.354/4)*100=0.0885

3. Для 6 процессоров: S_p=T₁ / T_p

T₁ = 2,36

T₆ = 4,76

Ускорение:

S_p= T₁ / T₂

S₆=0.495

Эффективность:

E_p=(S_p/p)*100%

E₆=(0.495/6)*100=0.0825

Теоретическая оценка:

Т₁ =64^5 * 131* 3*10^(-9) =0.0128

131 - это кол-во циклов после 5-ти форов. Пересчитать. -

Т₂ =(64^5 * 131* 3*10^(-9))/2 +(131* 10^5 * 3*10^(-9)) =

Таблица 1

Кол-во процессоров	1	2	4	6
Tp	2,36	1,22	6,65	4,76
Sp=T1 / Tp	-	1.93	0.354	0.495
Ep=(Sp/p)*100%	-	0.965	0.0885	0.0825

программа параллельный алгоритм

Заключение

Реализованы последовательный и параллельный алгоритмы решения задачи о пяти ферзях. Было замерено время выполнения программы на каждом из алгоритмов, найдены ускорение и эффективность.

Литература

1. Многопроцессорные вычислительные системы и параллельное программирование: Учебное пособие / Афанасьев К.Е., Стуколов С.В., Демидов А.В., Малышенко В.В.; Кемеровский госуниверситет. - Кемерово: Кузбассвузиздат, 2003. - 182 с.

Размещено на Allbest.ru

...