Потоки. Оптимальный вариант реализации

[s-andriano]

Сообщение от veniside

Оказалось, что в Дельфи настолько криво сделана...

...и расширил тест до 64 потоков.

Я делал тест не на Делфи. И у меня количество потоков было то ли до 2048, то ли до 4096. Тормоза начинались при нескольких сотнях потоков. Кстати, при попытке портировать этот тест на Делфи столкнулся с тем, что Делфи сама по себе затыкается при гораздо меньшем количестве потоков. Т.е. 2048 потоков я не смог запустить вообще, а при 256 задача практически останавливалась.

стоп, мы говорим, что все потоки одинаково загружены.

Кто это говорит?
И что значит "одинаково загружены"?
По условию объем вычислений в разных потоках различается. Почитайте, что пишет об этом ТС. В разных потоках решаются разные задачи.

Не важно чем, но они не простаивают. Тезис простой: если потоки не простаивают, то их не должно быть больше, чем ядер. Если 100% работы можно разбить на 100 частей, то оптимальное разбиение по ядрам:

1 ядро: 1 поток, 100 частей
2 ядра: 2 потока, по 50 частей каждый
4 ядра: 4 потока, по 25 частей каждый
и т.д.

Отнюдь.
Отимальное распределение существенно зависит от того, как соотносятся объемы вычислений в разных потоках.
Если нам это неизвестно, то целесообразно (при возможности) подробить задачу на большее количество потоков (и сделать это не на Делфи, а на WinAPI), а также (при возможности) начинать вычисления с более ресурсоемких фрагментов, а заканчивать менее ресурсремкими.

[veniside]

> Я делал тест не на Делфи.

если не лень, портируйте в вашу среду код из поста #18 (там 94% чистого WinAPI, никаких средств Дельфи (кроме writeln() и IntToStr()) не используется, так что проблем быть не должно) и скиньте сюда результат, спасибо.

[s-andriano]

Сообщение от veniside

если не лень, портируйте в вашу среду код из поста #18 и скиньте сюда результат, спасибо.

1 threads: 43454 ms / 64 jobs.
2 threads: 29078 ms / 64 jobs.
4 threads: 29328 ms / 64 jobs.
8 threads: 29906 ms / 64 jobs.
16 threads: 28891 ms / 64 jobs.
32 threads: 29015 ms / 64 jobs.
64 threads: 28985 ms / 64 jobs.

Без проблем.
Да, CPU Atom-1600, 1 ядро, гипертрединг.

[veniside]

спасибо, я понял. эта читерская винда даёт больше тому, у кого больше потоков ) надо под линухом потестить, может там не всё так плохо )

[gusluk]

Сделал так:

var
  Form1: TForm1;
  h: TWOHandleArray;
  Res1,Res2,Res3:real;
implementation

{$R *.dfm}

Function Fx(a,b:real):real;
begin
Fx:=a+b;
end;

Function Fy(a,b:real):real;
begin
Fy:=a-b;
end;

Function Fz(a,b:real):real;
begin
Fz:=a*b;
end;

Function Fxyz(x,y,z:real):real;
begin
Fxyz:=x*y/z;
end;

procedure Thread0();
begin
Res1:=Fx(1,2);
end;
procedure Thread1();
begin
Res2:=Fy(2,3);
end;
procedure Thread2();
begin
Res3:=Fz(3,4);
end;

Procedure CalcFxyz;
var i:integer;
begin
for i:=1 to 10 do
       begin
       h[0] := CreateThread(nil, 0, @Thread0, nil, 0, id);
       h[1] := CreateThread(nil, 0, @Thread1, nil, 0, id);
       h[2] := CreateThread(nil, 0, @Thread2, nil, 0, id);
       WaitForMultipleObjects(3, @h, true, INFINITE);
       CloseHandle(h[0]);
       CloseHandle(h[1]);
       CloseHandle(h[2]);
       form1.Memo1.Lines.Add(floattostr(Fxyz(Res1,Res2,Res3)));
       end;
end;

Вроде все работает как надо.
Спасибо всем за помощь.

[s-andriano]

Сообщение от veniside

спасибо, я понял. эта читерская винда даёт больше тому, у кого больше потоков ) надо под линухом потестить, может там не всё так плохо )

Нет, просто вся разница в пределах погрешности. (Тем более, что GetTickCount - не самая точная функция)
А по поводу "все так плохо" - категорически не согласен: накладные затраты на организацию потоков и переключение между ними оказались существенно меньше ожидаемого - чего ж тут плохого?

[veniside]

gusluk, только не забывайте, что процедура потока должна быть объявлена так:

DWORD WINAPI ThreadProc(
  __in  LPVOID lpParameter
);

аналог на Дельфи:

function ThreadProc(param: pointer): DWORD; stdcall;

иначе возможны глюки.


> чего ж тут плохого

плохо, что самый наглый получает больше других ) по-идее процессы с 2 и с 64 потоками должны получать одинаковые кванты процессорного времени на свою работу. Реально же, даже по грубым тестам, выходит, что чем больше потоков ты создал, тем больше цпу отжал у других. Это ерунда.

[gusluk]

Есть еще один вопрос по другой задаче. Вернее задача все та же, методика её решения другая. В этой мы считали перенос вещества, энергии и прочее в узлах регулярной сетки, во втором варианте моделируем уже сами частицы и их движение.
Движение частиц считал так:

type
TAtom = record  //частица с координатами X,Y и скоростью u,v
  X: real;
  Y: real;
  u:real;
  v:real;
end;

Procedure CalcStep;
var r:real; i,j:integer; dV,dVcurr,dx,dy:real;
begin
for i:=1 to N do
      begin
      Atom[i].X:=Atom[i].X+Atom[i].u;
      Atom[i].Y:=Atom[i].Y+Atom[i].v;
      end;

for i:=1 to N do
  begin
  for j:=1 to N do
      begin
      if i<>j then
           begin
           r:=sqrt(sqr(Atom[i].X-Atom[j].X)+sqr(Atom[i].Y-Atom[j].Y));//расстояние между частицами
           dV:=G*m/(r*r);   //гравитация
           if r<10 then dV:=dV-8.98*1000000000*q*q/(r*r);    //закон кулона

           dx:=Atom[i].X-Atom[j].X;
           dy:=Atom[i].Y-Atom[j].Y;

           dVcurr:=P2PAgle(Atom[i].X,Atom[i].Y,Atom[j].X,Atom[j].Y);//направление на частицу 2

           Atom[i].u:=Atom[i].u+dV*sin(dVcurr*3.14/180);
           Atom[i].v:=Atom[i].v+dV*cos(dVcurr*3.14/180);
           end;
      end;
  end;

Потом решил чуть оптимизировать и сделал так:

Procedure CalcStep;
var r:real; i,j:integer; dV,dVcurr,CosA,SinA:real;
begin
for i:=1 to N-1 do
  begin
  for j:=i+1 to N do
      begin
      r:=sqrt(sqr(Atom[i].X-Atom[j].X)+sqr(Atom[i].Y-Atom[j].Y));
      dV:=G*Atom[j].Mass/(r*r);   //гравитация
      if r<10 then dV:=dV-8.98*1000000000*q*q/(r*r);    //закон кулона

      dVcurr:=P2PAgle(Atom[i].X,Atom[i].Y,Atom[j].X,Atom[j].Y);
      dVcurr:=dVcurr*0.017453292519;
      SinA:=sin(dVcurr);
      CosA:=cos(dVcurr);
      Atom[i].u:=Atom[i].u+dV*SinA;
      Atom[i].v:=Atom[i].v+dV*CosA;

      SinA:=-SinA;
      CosA:=-CosA;
      Atom[j].u:=Atom[j].u+dV*SinA;
      Atom[j].v:=Atom[j].v+dV*CosA;

      end;
  end;
end;

В первом варианте берем частицу и рассчитываем влияние на неё всех остальных частиц, во втором варианте считается влияние не только на частицу, но и её ответное влияние на все остальные частицы. В итоге уменьшаем в два раза количество расчетов синуса и косинуса, что дает существенную прибавку в производительности.
Чтобы уменьшить объем вычислений все сразу пересчитывается на скорость по осям.
Теперь, при попытке разбить расчеты на потоки, в первом варианте вопросов не возникает, если потоков k, а частиц N, то каждый поток рассчитывает свои N/k частиц и все хорошо работает. Во втором случае могут возникнуть ситуации когда два разных потока будут рассчитывать свои частицы и их ответное влияние на одну и туже частицу. Соответственно придется как то делать синхронизацию, что в свою очередь приведет к замедлению.
Так вот как именно тут сделать синхронизацию, и не приведет ли она к тому что первый вариант будет быстрее чем второй?

[s-andriano]

Сообщение от veniside

плохо, что самый наглый получает больше других ) по-идее процессы с 2 и с 64 потоками должны получать одинаковые кванты процессорного времени на свою работу. Реально же, даже по грубым тестам, выходит, что чем больше потоков ты создал, тем больше цпу отжал у других. Это ерунда.

Думаю, для [одно]пользовательской ОС такое поведение не только допустимо, но и разумно.
Другое дело - ОС серверная. Но и в этом случае ресурсы должны делиться между пользователями, а не между процессами. И, кроме того, внутри ресурса одного пользователя, опять же, не вижу ничего плохого в том, чтобы раздавать ресурс по потокам.

[s-andriano]

gusluk, посмотрел на реализацию.
Первое, что озадачило, обычно интегрирование по времени производится с определенным шагом DeltaT. Ничего подобного я в Вашем коде не обнаружил.
Я крайне надеюсь, что Вы привели не весь код процедур, а только его фрагменты.
В коде то появляются, то исчезают какие-то странные константы типа:

      dVcurr:=dVcurr*0.017453292519;

Этот фрагмент:

      Atom[i].u:=Atom[i].u+dV*SinA;
      Atom[i].v:=Atom[i].v+dV*CosA;

      SinA:=-SinA;
      CosA:=-CosA;
      Atom[j].u:=Atom[j].u+dV*SinA;
      Atom[j].v:=Atom[j].v+dV*CosA;

можно записать короче:

      Atom[i].u:=Atom[i].u+dV*SinA;
      Atom[i].v:=Atom[i].v+dV*CosA;
      Atom[j].u:=Atom[j].u-dV*SinA;
      Atom[j].v:=Atom[j].v-dV*CosA;

и при этом еще будут исключены лишние операции с памятью.

Ну и главный вопрос: Вам нужно распараллелить задачу или сделать, чтобы задача работала быстрее?