multi-threading porting

[Igors]

Добрый день

Нужно "разпоточить" задачу которая изначально была написана без всякого учета multi-threaded. Певдокод

Код

C++ (Qt)
struct CData {
  void DoCalc( float x, float y );
 ... 
 int mX, int mY;
 CCube mCube[9];
 ...
};
 
void CData::DoCalc( float x, float y )
{
 int ix = (int) floor(x);
 int iy = (int) floor(y);
 
 if (ix != mX || iy != mY) {
  mX = ix;
  mY = iY;
  for (int i = -1; i <= +1; ++i)
   for (int j = -1; j <= +1; ++j)
     SetupCube(mCube[(j + 1) * 3 + i + 1], mX + i, mY + j);
 } 
 
 DoSomethingWithCubes(mCube);
 ...
}
 

Как это приспособить для выполнения 2-мя или более нитками. учитывая что вызовы SetupCube обычно съедают намного больше половины времени выполнения?

Спасибо

[LisandreL]

Смотря что SetupCube делает.
OpenMP тут не срабатывает?

[Igors]

Смотря что SetupCube делает.
OpenMP тут не срабатывает?

SetupCube заполняет содержимое CCube генерируя случайные данные (seed привязан к аргументам). OpenMP конечно срабатывает, но не делает метод thread-safe

[Serr500]

SetupCube влияет на весь массив mCube или только на элемент, который в неё передаётся?

[Igors]

SetupCube влияет на весь массив mCube или только на элемент, который в неё передаётся?

Только на элемент, но вызывается для всех 9 кубов (27 в оригинале)

[Serr500]

Ну, если предположить, что SetupCube не только не влияет на иные элементы mCube, но и не использует их, то все вызовы SetupCube оказываются независимыми:

Код:

 i  j (j + 1) * 3 + i + 1
-1 -1    0
-1  0    3
-1 +1    6
 0 -1    1
 0  0    4
 0 +1    7
+1 -1    2
+1  0    5
+1 +1    8

Поэтому можно выполнять каждое вычисление независимо в отдельном потоке. Например, можно сделать так (псевдокод):

Код:

for (int i = -1; i <= +1; ++i)
{
    QSetupCubeThread Threads[3];
    for (int j = -1; j <= +1; ++j)
    {
        Threads[j+1].arg1 = (j + 1) * 3 + i + 1;
        Threads[j+1].arg2 = mX + i;
        Threads[j+1].arg3 = mY + j;
        Threads[j+1].start();
    }
    for (int j = -1; j <= +1; ++j)
         Threads[j+1].wait();
}

[Igors]

Поэтому можно выполнять каждое вычисление независимо в отдельном потоке.

Запуск неприемлем - он съест больше времени чем само SetupCube. Да, основное время съедается именно на SetupCube, но за счет хорошей кратности DoCalc  (миллионы)

[Serr500]

Тогда я чего-то не понимаю. Надо сделать DoCalc многопоточным внутри или сделать DoCalc thread-safe, чтобы его безопасно было запускать из разных потоков?

[Igors]

Тогда я чего-то не понимаю. Надо сделать DoCalc многопоточным внутри или сделать DoCalc thread-safe, чтобы его безопасно было запускать из разных потоков?

Делать thread-safe

[Serr500]

Тогда, к примеру, так:

Код:

class CData
{
    private :
        int mX, int mY;
        CCube mCube[9];
        mutable QReadWriteLock m_Locker;
    public :
        void DoCalc(float x, float y);
        CCube cube(int i) const;
}

void CData::DoCalc(float x, float y)
{
    QWriteLocker WL(&m_Locker);
    // ... вычисляем ...
}

CCube CData::cube(int i) const
{
    QReadLocker RL(&m_Locker);
    return mCube[i];
}

[Igors]

Тогда, к примеру, так:

А Вас не смутило что это уж слишком очевидно? Так конечно thread-safe, но на 4-х ядрах это работает в неск раз медленне чем на одном.

От бывшего математика я ожидал большего 

[Serr500]

А Вас не смутило что это уж слишком очевидно?

Вообще-то смутило... У меня до сих пор стойкое ощущение, что я чего-то не понял...

Так конечно thread-safe, но на 4-х ядрах это работает в неск раз медленне

Это меня удивляет. Замедление, конечно, возникает, но не до такой же степени. Может, надо ещё и вызывающий код оптимизировать?

От бывшего математика я ожидал большего 

Так ведь бывший... 

Хорошо, вот ещё одна идея. Создавать при начале выполнения программы несколько потоков (по числу ядер), ставить на паузу. Каждый поток должен будет выполнять SetupCube. Но после завершения вычислений не завершать работу, а приостанавливаться (например, на мьютексе). После инициализации переменных мьютекс разблокируется и поток выполняет вычисление. Пауза на мьютексе намного "легче", чем пересоздание потока. Если пофиг загрузка процессора, то можно сделать даже спин-блокировку, тогда реагировать на снятие с паузы поток будет почти моментально.

[Igors]

Это меня удивляет. Замедление, конечно, возникает, но не до такой же степени.

Ничего удивительного. На одной нитке трудоемкие вызовы SetupCube в 90% успешно пропускаются, а на 4-х каждая прется со своими x, y которых ничего общего. Ну и все уходит в SetupCube как вода в песок.

Хорошо, вот ещё одна идея. Создавать при начале выполнения программы несколько потоков (по числу ядер), ставить на паузу. Каждый поток должен будет выполнять SetupCube. Но после завершения вычислений не завершать работу, а приостанавливаться (например, на мьютексе). После инициализации переменных мьютекс разблокируется и поток выполняет вычисление. Пауза на мьютексе намного "легче", чем пересоздание потока. Если пофиг загрузка процессора, то можно сделать даже спин-блокировку, тогда реагировать на снятие с паузы поток будет почти моментально.

Создание "бригады ниток" не вопрос, также как и натравить ее на что-то. В OpenMP делается напр так

Код

C++ (Qt)
#pragma omp parallel for
for (int i = 0; i < data.size(); ++i)
 DoCalc(data[i].x, data[i].y); 
 

Однако даже такой (пере) запуск имеет смысл на приличном size() или DoCalc. А запускать бригаду на 9 вызовов SetupCube - в минус. Ну и потом - посчитанные кубы используются в DoCalc до его завершения.

[LisandreL]

Запуск неприемлем - он съест больше времени чем само SetupCube. Да, основное время съедается именно на SetupCube, но за счет хорошей кратности DoCalc  (миллионы)

Ну, тогда моё неэкспертное мнение:
распараллеливать там, где вызывается DoCalc эти миллионы раз
  1) Если данные и обработка независимы, то всё хорошо, но я думаю при этом вопросов у вас не возникло бы.
  2) Если DoSomethingWithCubes(mCube); обращается к общим ресурсам, но не важен порядок его вызова то можно попробовать прикрыть его или его части мьютексами/критическими секциями/атомарными операциями. При условии, что дольше работает SetupCube - есть шанс получить profit.
Поиграться с числом потоков. Учитывая, что некоторые потоки будут стоять в мьютексах есть вероятность того, что оптимальное их число будет несколько больше количества ядер.
  3) Если важен порядок вызова, то выделить генерацию данных (вызовы SetupCube) и параллелить их, а уже DoSomethingWithCubes(mCube);... выполнять в один поток, когда данные сгенерированы (более сложный вариант - по мере генерации данных).

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

[Igors]

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

Собственно DoCalc и параллелится, т.е. вызывается многими нитками с разными аргументами. Это просто плагин, процедуральная текстура (ну можно сказать фрактал). Метод DoCalc вызывается хостом, когда хост сочтет нужным, обычно очень много раз. В связи с тем что хост стал multi-threaded необходимо сделать этот метод thead-safe - в том виде как сейчас он рухнет.  Простое решение

Код:

// if (ix != mX || iy != mY) {
if (1) {
..
// и сделать mCube локальным массивом (а не членом класса)

Это лучше чем блокировка, все-таки все нитки в работе, но масса времени съедается на SetupCube, в результате "мульти" версия оказывается медленнее - что не рекомендует программиста с хорошей стороны