LINUX.ORG.RU

Реализация дерева зависимостей по данным для многопоточных приложений на C

 , ,


0

2

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

Например если надо посчитать (sin((a+b+c+d)*(e+f+g)))^((a+b+c+d)+(h+i+j)) то можно построить такое дерево:

              (_^_)
               ^ ^
               | |
          +----+ +---+
          |          |
      sin(_)         |
          ^          |
          |          |
        (_*_)      (_+_)
         ^ ^        ^ ^
         | |        | |
    +----+ +-+------+ |
    |        |        |
 (e+f+g) (a+b+c+d) (h+i+j)

Как я себе это представляю:

Надо строить направленный ациклический граф, в каждой вершине храним указатель на следующие вершины(в примере у (a+b+c+d) две следующих вершины: (_*_) и (_+_)); счетчик числа вершин, указывающих на эту вершину, указатель на функцию, которую надо вызвать; массив указателей на данные, которые в эту функцию надо передавать; указатель на область памяти, куда надо записать результат выполнения функции.

Вначале нужно создать очередь, в которую помещаем указатели на те вершины, на которые никакие другие вершины не указывают. Запускаем некоторое количество тредов. По завершени обработки задачи, каждый тред декрементирует счетчик числа вершин в тех вершинах, на которые указывает та вершина, задача из которой была завершена этим тредом(например по завершении (a+b+c+d) надо декрементировать счетчик у вершин (_*_) и (_+_)). Если оказывается что после декрементирования счетчика в только одной вершине оказался 0, тред немедленно приступает к выполнению задачи из той вершины. Если в двух и более счетчиках в вершинах оказался 0, тред добавляет в очередь указатели на все такие вершины, кроме одной, и выполняет задание из той «одной» вершины, которая не добавлена в очередь. Иначе он берет задачу из очереди. Если в очереди ничего нет, тред выставляет особое значение в некоторой переменной, означающее что этот тред бездействует, после чего этот тред сам себе шлет сигнал SIGSTOP. И надо сделать так, чтобы при добавлении задач в очередь, проверялось наличие бездействующих тредов, и слать им сигнал SIGCONT.

Как подобная модель многопоточности называется? Есть ли уже готовые реализации подобного для C или других языков программирования? Через вызов clone() и всякие там CAS спинлоки такое реализовать нетрудно, как мне кажется. Поверх этого можно еще сделать реактивное программирование.

★★★★★

Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

TASK 2

Потенциальный трупут 2.5 такта.

Вырожденное дерево суммы - т.е. реальный трупут твоего таска будет в 5-10раз ниже.

Т.е. утилизация ведра будет 10-20%(реально вообще 2-4%) и выйдешь ты на 100% утилизацию ведра только с 4-х тредов.

Что является абсолютно бесполезной задачей. Я уж не говорю о том, как ты собрался эти таски по 10-20тактов шедулдить - это нереально.

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

anonymous
()
Ответ на: комментарий от anonymous

Пфф, это просто ПРИМЕР. Реальные таски будут значительно больше. Совершенно очевидно, что нет смысла так сильно все мельчить

SZT ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Запили дсл для математики

царь решил под умного косить? дсл для математики запилили уже 4000 лет как.

anonymous
()
Ответ на: комментарий от SZT

Реальные таски будут значительно больше.

Значительно - это 3порядка?

Совершенно очевидно, что нет смысла так сильно все мельчить

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

Это уже очень дорого и в считалках нахрен не нужно. Проще распаралелить по данным и всё. Это умеют все и вся уже сотни лет. Разбил на равные части - запустил - отработало всё почти одновременно. Утилизация близка к максимальной.

В чем суть предложения?

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.