Исследование повышения производительности последовательной программы после преобразования ее алгоритма в параллельный

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

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

Осуществляется подсчет  суммы ряда несколькими способами: последовательным и параллельным.

Алгоритм программы  представлен на рисунке 6, код программы  приведен в приложении А.

Блок-схема 1 (рисунок 6) предоставляет выбор пользователю пунктов меню. Блок-схема 5 (рисунк 10) осуществляет последовательный алгоритм вычисления определенного интеграла. Для каждого параллельного способа подсчета определенного интеграла были выделены информационно независимые операции (блок-схемы 2-3 на рисунки 7-8). Время выполнения каждого блока засекается и является выходными данными программы.

Перед началом кодирования требуется  выбрать язык программирования, на котором будет реализована программа. Так как при составлении программы программист мыслит критериями, которые дает ему в распоряжение язык программирования, для конкретного воплощения абстрактной мысли необходим инструмент, помогающий процедуре проектирования программы. Язык должен способствовать написанию надежных программ и упрощать их сопровождение. Таким инструментом и выступает язык программирования С++, позволяющий выразить результат в простой, понятной и удобной форме. Поэтому для кодирования программы была выбрана среда разработки программного обеспечения MinGW 3.4.5.

 

 

 

 

 

 

         -

 

+

 

 

 

 

 

 

 

 

 

 

 

Рисунок 6 – Блок-схема основной программы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 7 – Блок-схема функции ServerFunc

 

 

Рисунок 8 – Блок-схема функции ClientFunc

 

 

 

 

 

 

 

 

 

 

 

Рисунок 9 – Блок-схема функции OneCampCalculate

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 10 – Блок-схема функции CalculateData

4 Результаты разработки MinGW 3.4.5

 4.1 Вычисления сервер-клиент

Серверная часть

IP is 192.168.1.3

Num of repeats is 10000000

 

  Menu

1.Server side

2.Client side

3.One camp

Enter number(0 - for exit): 1

 

Wait accept...

Accepted Client: 192.168.1.3:13518

Enter interval (A,B)...

-2

2

 

Initialized in '6.325' seconds

Sending data to client...

Server side, dt1 = '0.003' seconds

Calculating integral...

Calculation was finished in '42.414' seconds

Result of integration on [0.000000;2.000000] is 0.842899

Receiving data from client...

Server side, dt2 = '18.793' seconds

Result from client [-2.000000;0.000000] is 0.156137

And result of integral on interval [0.000000,2.000000] is 0.999036

Server side finished in  = '61.219' seconds

 

Клиентская часть

Server IP is 192.168.1.2

Num of repeats is 10000000

 

  Menu

1.Server side

2.Client side

3.One camp

Enter number(0 - for exit): 2

 

Initialized in '0.063' seconds

Have connected to the server

Waiting for messages:

A = -2

B = 2

Client side, dt1 = '4.906' seconds

We have received interval. A is -2.000000 , B is 0.000000

Calculating...

Calculating integral...

Calculation was finished in '61' seconds

Sending data to server...

Client side, dt2 = '0' seconds

Sent

Result on [-2.000000;0.000000] is 0.156137

Client side finished in '61' seconds 

4.2 Вычисления сервер-клиент: (вычисления только на клиенте)

Серверная часть

 

  Menu

1.Server side

2.Client side

3.One camp

4.Server side (client only)

5.Client side (client only)

Enter number(0 - for exit): 4

 

Wait accept...

Accepted Client: 192.168.1.3:13679

Enter interval (A,B)...

-2

2

 

Initialized in '5.48' seconds

Sending data to client...

Server side, dt1 = '0.003' seconds

Receiving data from client...

Server side, dt2 = '119.648' seconds

Result of integral on interval [-2.000000,2.000000] is 0.999036

Server side finished in  = '119.657' seconds

 

Клиентская часть

 

Menu

1.Server side

2.Client side

3.One camp

4.Server side (client only)

5.Client side (client only)

Enter number(0 - for exit): 5

 

Initialized in '0.032' seconds

Have connected to the server

Waiting for messages:

msgA = -2

msgB = 2

Client side, dt1 = '3.781' seconds

We receive interval. A is -2.000000 , B is 2.000000

Calculate...

Calculating integral...

Calculation was finished in '119.375' seconds

Sending data to server...

Client side, dt2 = '0' seconds

Sent

Result is 0.999036

Client side finished in '119.375' seconds

 

 

 

 

 

4.3 Вычисления на одном компьютере

 

Menu

1.Server side

2.Client side

3.One camp

4.Server side (client only)

5.Client side (client only)

Enter number(0 - for exit): 3

 

Enter interval (A,B)...

-2

2

 

Calculating integral...

Calculation was finished in '97.066' seconds

 

Оценка производительности при работе только сервера, только клиента  и при совместной работе сервера  и клиента представлены на рисунке 11.

 

Рисунок 11 – Диаграмма оценки производительности

 

 

 

 

 

 

 

 

 

Выводы

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы

1. В.М.Баканов; Параллельные вычисления: Учебное пособие / МГУПИ. Москва, 2006.
2. Шпаковский Г.И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие. — Мн.: Белгосуниверситет, 1996. — 296 с.: ил.
3. http://freekniga7.narod.ru/sovremkomp/
4. http://www.parallel.ru/vvv/lec1.html
5. http://www.computerra.ru/offline/2002/430/15838/
6. http://ru.wikipedia.org/wiki/Pentium
7. http://209.85.129.132/search?q=cache:2ZX-fIpSYVwJ:www2.sscc.ru/SORAN-INTEL/paper/Intel_Compilers_2009.ppt

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение А –  Текст программы

 

#include <iostream>

#include <fstream>

#include <time.h>

#include <windows.h>

#include <stdio.h>

#include <stdlib.h>

#include <vector.h>

#include <string.h>

#include <math.h>

//#include <winsock2.h>

 

#define SERVER_PORT_NUM         5155

#define SERVER_MAX_CONNECTIONS 1

#define MAX_MSG_SIZE   15

 

#define PI      3.14

 

using namespace std;

 

char * dtmp;

unsigned int NUM_OF_REPEATS=0;

 

/**

* Функция, интеграл которой мы находим

* @param

* x, dSredOtkl, m - аргументы функции

* @return

* Возвращает  численное значение функции по  заданым аргументам

*/

double Func(double x,const double dSredOtkl,const double m)

{

return ((exp(-(pow(x-m,2))/(2*dSredOtkl*dSredOtkl)))/(dSredOtkl*sqrt(2*PI)));

}

 

/**

* Функция  нахождения интеграла

* @param

* a, b - крайние значения интервала,  на котором необходимо проинтегрировать  функцию

* epsilon - значение желаемой погрешности,  устанавливается как дробь (0.05 - это 5%)

* dSredOtkl, m - аргументы функции

* @return

*  Возвращает численное значение  интеграла функции, на заданном  интервале

*/

double IntegralRect(const double& a, const double& b, const double& epsilon, const double& dSredOtkl,const double& m)

{

    double result;

    int i;

    int n;

    double h;

    double s1;

    double s2;

 

    n = 1;

    h = b-a;

    s2 = h*Func((a+b)/2,dSredOtkl,m);

    do

    {

        n = 2*n;

        s1 = s2;

        h = h/2;

        s2 = 0;

        i = 1;

        do

        {

            s2 = s2+Func(a+h/2+h*(i-1),dSredOtkl,m);

            i = i+1;

        }

        while(i<=n);

        s2 = s2*h;

    }

    while(fabs(s2-s1)>3*epsilon);

    result = s2;

    return result;

}

 

/**

* Функция  проводит вычисления и снимает  временной замер

* @param

*

* @return

*

*/

double CalculateData(const double & a, const double & b)

{

clock_t   start, finish;

double elapsed_time;

int i;

const double epsilon = 0.005;

const double dSredOtkl = 0.5;

const double m = 0.5;

double result;

 

cout<<"\nCalculating integral...";

start=clock();

for(i=0;i<NUM_OF_REPEATS;i++)

{

result=IntegralRect(a, b, epsilon, dSredOtkl, m);

}

finish = clock();

elapsed_time = static_cast<double> (finish - start)/ CLOCKS_PER_SEC;

 

cout<<"\nCalculation was finished in \'"<< elapsed_time<<"\' seconds";

return result;

}

 

/**

* Функция  вычислений для клиентов

* @param

*

* @return

*

*/

int ClientFunc ()

{

WORD winsock_version = MAKEWORD(2,0);

WSADATA wsaData;

SOCKET sd;

sockaddr_in serverAddr;

double a,b;

double result=0;

char messageA[MAX_MSG_SIZE]="";

char messageB[MAX_MSG_SIZE]="";

    int num=0,nbyte;

a=0;b=0;

clock_t   start, finish, t0, t1, t2, t3;

double elapsed_time;

 

start = clock();

 

    if(WSAStartup(winsock_version, &wsaData)!=0) {

printf("\nCould not initialize winsock");

        return 0;

    }

   

    sd = socket (AF_INET, SOCK_STREAM, IPPROTO_IP);

 

    serverAddr.sin_family = AF_INET;

    serverAddr.sin_port = htons(SERVER_PORT_NUM);

    serverAddr.sin_addr.s_addr = inet_addr(dtmp);

 

if(connect(sd, (sockaddr *)&serverAddr, sizeof(serverAddr)) == -1)

{

   printf("\nCould not connect to the server");

   return 0;

}

else {

t0 = clock();

elapsed_time = static_cast<double> (t0 - start)/ CLOCKS_PER_SEC;

cout<<"\nInitialized in \'"<<elapsed_time<<"\' seconds";

 

printf("\nHave connected to the server\nWaiting for messages:");

int recvA = recv(sd, (char *)messageA, MAX_MSG_SIZE, 0);

if (recvA != SOCKET_ERROR) {

printf("\nmsgA = %s",messageA);

a=atof(messageA);   

}

else if (recvA==0 || recvA<0)

{

printf("\nRECV: Error");

scanf("");

return 0;

}

 

int recvB=recv(sd, (char *)messageB, MAX_MSG_SIZE, 0);

if (recvB != SOCKET_ERROR) {

printf("\nmsgB = %s",messageB);

b=atof(messageB);

}

else if (recvB==0 || recvB<0)

{

printf("\nRECV: Error");

scanf("");

return 0;

}