Распараллеливание программы (ядра/потоки)

[Andrey_Kireew]

Проверил вариантDmitriy40, только CreateThread у меня почему то не компилировалась, оставил beginthreadex(), задачу не делил, а просто прибавлял кол-во потоков. Для M=1,2,3,4 время выполнения практически одинаковое, для N=5 сразу заметно увеличивается. Для N=8 становится ровно в 2 раза больше. Добавил создание и удаление всех динамических массивов - это ни на что не влияет.

Видимо, всё дело в структуре, которая передаётся в потоковую функцию. Выяснилось, что если её объявить как static, то время выполнения программы увеличивается в разы.

[Dmitriy40]

Зачем структуру static если достаточно обеспечить её существование на всё время выполнения потоков? Она даже локальной в main() может быть, главное создать до CreateThread и удалить не раньше WaitForMultipleObjects.
С другой стороны почему static на данные изменяет время мне совсем непонятно.
Создать и удалить динамические массивы мало, даже в том же порядке и объёма, надо ещё к ним и обращаться примерно в том же порядке.
Разбираться по шагам я уже предлагал ...

А, вы структуру то одну на все потоки что ли передаёте? Надо массив структур и передавать каждому потоку свой экземпляр. Ну и заполнить его желательно до начала запуска потоков, чтобы записи не перемешивались с чтениями.

Уж сколько Вам говорят, покажите полностью код, для начала хотя бы без ваших вычислений справа от знаков "=" (слева желательно видеть чтобы проверить что области записи в потоках не пересекаются). Или сами упростите до правильно работающего многопоточно и потом возвращайте по шагам. Чё мы тут гаданиями занимаемся ...

[Andrey_Kireew]

Dmitriy40 в сообщении #1433380 писал(а):

Она даже локальной в main() может быть

так и есть

Dmitriy40 в сообщении #1433380 писал(а):

Создать и удалить динамические массивы мало, даже в том же порядке и объёма, надо ещё к ним и обращаться примерно в том же порядке

понятно, что к ним обращался

Dmitriy40 в сообщении #1433380 писал(а):

А, вы структуру то одну на все потоки что ли передаёте? Надо массив структур и передавать каждому потоку свой экземпляр

так и есть, массив структур, в разные функции подаются разные элементы, и понятно, что он заполняется, иначе как к нему обращаться?

Вот я и упрощаю весь день ...

[Dmitriy40]

Andrey_Kireew в сообщении #1433376 писал(а):

задачу не делил, а просто прибавлял кол-во потоков. Для M=1,2,3,4 время выполнения практически одинаковое, для N=5 сразу заметно увеличивается. Для N=8 становится ровно в 2 раза больше.

И кстати у меня моя же программа но без деления задачи выдаёт весьма неожиданные результаты:

Times: 13.3s 16.2s 15.7s 15.8s 23.2s 23.7s 27.3s 30.8s 35.9s 39.7s

Неожиданные потому что не все потоки выполняются равномерно вперемешку, один-два занимают по 25% (целому ядру), а 50% делятся между остальными и соответственно не успевают завершиться все почти одновременно, хорошо видно как загрузка проца падает со 100% до 75%-50% в конце на несколько секунд. Плюс возрастание времени при переходе 7-8 потоков. Вот так винда распределяет процессорные ресурсы. Почему я и говорил что делить задачу надо на меньшие куски, чтобы гранулярность завершения потоков была поменьше. Ещё можно каждую секунду возвращать управление ОС из потока командой Sleep(1), но это может и не дать эффекта.

-- 04.01.2020, 15:18 --

Andrey_Kireew в сообщении #1433385 писал(а):

и понятно, что он заполняется, иначе как к нему обращаться?

Заполнять можно прямо в цикле for запускающем потоки (что плохо) или до начала этого цикла (что лучше). Влияние не особо сильное, намного менее секунды думаю, но всё же.

[SergeCpp]

Dmitriy40 в сообщении #1433380 писал(а):

...почему static на данные изменяет время мне совсем непонятно.

Верно, в другую секцию помещается. Секции, впрочем, можно и объединить (опцию не помню).

Dmitriy40 в сообщении #1433387 писал(а):

Ещё можно каждую секунду возвращать управление ОС из потока командой Sleep(1)

Для Relinquish нужен параметр 0 у Sleep. Кстати, даже в DOS работает (есть там прерывание для Windows).

[Dmitriy40]

SergeCpp в сообщении #1433388 писал(а):

Dmitriy40 в сообщении #1433380 писал(а):

...почему static на данные изменяет время мне совсем непонятно.

Верно, в другую секцию помещается.

И что? Какая процессору разница в какой секции лежат данные?! Все кэши минимум 8-ми ассоциативные, из-за разбивки данных на две области тормозить (аж в разы!) никак не должно.

[Andrey_Kireew]

Пребывая в полном уминании, решил я попробовать исходный вариант, на большом массиве, как он есть без обрезаний.
Произошло удивительное. На 4-х ядрах:

98,22
97,67
152,93
97,95
104,7
97,58
97,97

за исключением 3-й попытки, почти 4-х кратное ускорение (на 1-м ядре - время выполнения .372,44).
Правда 2 раза всё зависало, и причин этого я так и не обнаружил.
Единственное отличие от предыдущих испытаний - диспетчер задач запущен не был.

Dmitriy40 в сообщении #1433387 писал(а):

Почему я и говорил что делить задачу надо на меньшие куски

Я запустил 40 потоков на 4 ядрах, время выполнения 111,17. По идее это и есть разбиение задачи на 40 частей. За вычетом накладных расходов, тоже самое получается.

[slavav]

Из этих результатов можно предположить что ваша реализация недетерминированная. Это может быть из-за недерминированного алгоритма или ошибок в реализации.
Так или иначе, прежде чем пускаться в оптимизации надо убедится что исходная программа верна и соответствует алгоритму свойства которого вам известны. Ещё более это верно если вы пускаетесь в параллельное программирование.
Пока вы тратите время в обмен на отрицательный опыт.

[Dmitriy40]

slavav
В один поток у ТС по видимому всё работает, скорее всего даже правильно (как он утверждает), при переходе же к многопоточности происходит непонятное.
А уж почему программа может вообще зависать — это мрак.

[Andrey_Kireew]

slavav в сообщении #1433414 писал(а):

Из этих результатов можно предположить что ваша реализация недетерминированная

Предположить можно, но результат расчёта она выдаёт всё время один и тот же. Свою функцию программа выполняет полностью. Единственная проблема - многопоточная реализация. Тут и с быстродействием и много с чем ещё вопросы, на которые ответа как бы и нет. 1. Почему модификатор static так влияет, почему динамическое выделение памяти внутри потоковой функции работает лучше, чем в основном потоке, да и зависания эти - тоже доставляют ...
В общем, чем дальше в лес - тем больше дров

[slavav]

Работоспособность ещё не означает корректность. Однопоточное может совершать обращения мимо памяти и оставаться работоспособным. Синхронизация не нужна. Переход к многопоточности вытаскивает все эти проблемы на свет.
Отчасти поэтому я рекомендовал запускать много процессов. Да это может быть медленнее чем много потоков. А может и не быть. Но эато каждый процесс работает как однопоточное приложение, которое можно отлаживать и тестировать.
Многопоточное приложение значительно сложнее привести в чувство. Если вообще возможно.

[Andrey_Kireew]

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

[slavav]

Повторяйте три раза утром, три - в обед и три - перед сном:
"Оптимизировать правильные программы. Неправильные программы не оптимизировать."

[Andrey_Kireew]

slavav в сообщении #1433422 писал(а):

Отчасти поэтому я рекомендовал запускать много процессов

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

-- 04.01.2020, 22:00 --

По многочисленным просьбам представляю код программы

Используется синтаксис C++

#include <windows.h>  
#include <stdio.h>    
#include <stdlib.h>   
#include <string.h>   
#include <math.h>

#include<process.h>   
#include <ctime>      


struct DATA
{   int init;
    int Lim;
    double *Mat;
    double *vc;
    int sz;
    int nV;
    double q;
    int *index;
};


static unsigned int __stdcall select(void *a);

int main()

{

/* интерфейс загрузуи данных */


  

SYSTEM_INFO sysinfo;
GetSystemInfo(&sysinfo);
int numCPU = sysinfo.dwNumberOfProcessors;
printf("numCPU= %d \n",numCPU);

numCPU =4; // при тестировании задаётся в ручную


DATA *a=new DATA [numCPU];

a[numCPU-1].Lim=N-L;

/* вычисление a[].Lim; */

a[0].init=0;
for (int j=1;j<numCPU;j++) a[j].init= ... ;

for (int j=0; j<numCPU; j++)
{ a[j].Mat= ... ; a[j].vc= ... ;
  a[j].sz= ... ; a[j].nV= ... ;
  a[j].index=new int[L];
}


unsigned int start_time =  GetTickCount(); //clock(); // начальное время

HANDLE *Th=new HANDLE[numCPU];
for (int j=0;j<numCPU;j++)
  Th[j]=(HANDLE)_beginthreadex(NULL, 0, &select, (void *) &a[j], 0, NULL); 

WaitForMultipleObjects(numCPU, Th, TRUE, INFINITE);

unsigned int dT = GetTickCount()-start_time; // конечное время;clock()
printf("T=%d ms \n",dT);

id=0;
for (int j=1; j<numCPU; j++) if (a[j].q>=a[0].q) {a[0].q=a[j].q; id=j;}
    
for (int ii=0; ii<L; ii++) *(ind+ii)=double((a[id].index)[ii]+1); 



  
for (int j=0; j<numCPU; j++) 
{
    delete [] a[j].index; CloseHandle(Th[j]);
}
    delete [] a;  delete [] Th; 
return 0;
}


//////////////////////////////////////////////////////////////////////

static unsigned int __stdcall select(void *a)   
{

int i0=((DATA *)a)->ini;
int iLim=((DATA *)a)->Lim;
double *Cm=((DATA *)a)->Mat;
double *r=((DATA *)a)->vc;
int N=((DATA *)a)->sz;
int L=((DATA *)a)->nV;
int *ind=((DATA *)a)->index;

int ii, j, k=0;  
double *A,*B,*C, q, q0, q_max=0;

int *id=new int[L];               // вспом. массив индексов 
double  *v=new double [L];        // вспом. вектор
double **M=new double*[L];        // массив указателей на вспом. матрицы
for (ii=0; ii<L; ii++) M[ii]=new double[(ii+2)*(ii+1)/2];

id[0]=i0-1;

NEXT:   id[k]++;

    ........текст программы .......
     
        if (k<L-1) {k++; id[k]=id[k-1]; goto NEXT;}

    ........текст программы .......

q+=12*q0;

if (q>q_max)
{ q_max=q; for (ii=0; ii<L; ii++) *(ind+ii)=id[ii];}  

while (id[k]==N-L+k) 
{// условие завершения 
 if (k==1 && id[0]==iLim) { for (ii=0; ii<L; ii++) delete [] M[ii]; delete [] M; delete [] v; delete [] id;
            
        ((DATA *)a)->q=q_max; return 0;}
            
  k--;
}
        goto NEXT;
}

 

[slavav]

Трудоемкость многопоточного решения в три раза выше чем многопроцессного. Это такое правило большого пальца.
Трудоемкость многопроцессного решения в три раза выше чем однопроцессного. Ещё один большой палец.
Вы замахнулись на задачу в девять раз сложнее исходной. Сколько вы писали исходную программу? Умножайте на девять.

Если рассматривать вашу задачу как учебную, то:
1. надо сделать программу корректной. Не "она выдает один и тот-же результат", а корректной-корректной.
2. всё остальное (процессы, потоки).

Вычисление надо представить в виде функции, которая не имеет побочных эффектов и имеет чёткий контракт по отношению к своим аргументам (это только читаю, это только пишу, это пишу-читаю). Третьего типа желательно избегать, но не всегда возможно.
Затем под контракт подводятся структуры данных.
Затем код.

Всё это вам надо сделать самому или попросить помощи. Чтобы попросить помощи, придётся раскрыть задачу помощникам.