Есть неоходимость создать систему абсолютного распараллеливания.
Принцип прост: есть пул потоков. Ему кидаются задачи, которые имеют зависимость. Например: задача А может быт выполнена в любое свободное время.
задача Б только после задачи А
задача В только после задачи А
задача Г только после задачи Б
задача Д только после Б и В
и так далее.
Сами задачи могут генерироваться, как в любом из потоков пула, так и вовне.
Допустим все эти задачи поступили одновременно, то ожидается следующее поведение:
1. выполнить А одним потоком
2. потом начать выполнять Б и В двумя потоками
3. поток выполнявший Б сразу приступит к Г
4. как только закончится Б и В свободный поток (скорее всего тот что выполнил В) начинает выполнение Д
Ну в общем надеюсь понятно.
Реализовать нужно в с++.
Знаю, что похожую функциональность дает OpenMP, однако там сложно задать зависимость между задачами содаваемыми в разных функциях и потоках.
Перед тем, как начать писать велосипед , хочу узнать, есть ли что либо близкое или(лучше ) полностью соответствующее таким требовамиям?
Здравствуйте, Caracrist, Вы писали:
C>Есть неоходимость создать систему абсолютного распараллеливания. C>Принцип прост: есть пул потоков. Ему кидаются задачи, которые имеют зависимость. Например: задача А может быт выполнена в любое свободное время. C>задача Б только после задачи А C>задача В только после задачи А C>задача Г только после задачи Б C>задача Д только после Б и В C>и так далее. C>Сами задачи могут генерироваться, как в любом из потоков пула, так и вовне. C>Допустим все эти задачи поступили одновременно, то ожидается следующее поведение: C>1. выполнить А одним потоком C>2. потом начать выполнять Б и В двумя потоками C>3. поток выполнявший Б сразу приступит к Г C>4. как только закончится Б и В свободный поток (скорее всего тот что выполнил В) начинает выполнение Д
C>Ну в общем надеюсь понятно. C>Реализовать нужно в с++.
Граф.
Если задач немного и фиксированное число, то можно его реализовать матрицей смежности. Строка — задача, столбец — кого ждет. Когда задача заканчивается, она ( а лучше некий менеджер, которого она уведомляет о своем окончании) проходит по столбцу этой матрицы и зануляет его, после чего проверяет все строки, в которых было зануление — остался ли там хоть один ненулевой элемент. Если нет — в пул эту задачу. Если задач не фиксированное число, можно оставить тот же алгоритм, но добавлять строки (столбцы не придется — не могут же ранее появившиеся задачи ждать новых).
Здравствуйте, Caracrist, Вы писали:
C>Есть неоходимость создать систему абсолютного распараллеливания. C>Ну в общем надеюсь понятно. C>Реализовать нужно в с++. C>Знаю, что похожую функциональность дает OpenMP, однако там сложно задать зависимость между задачами содаваемыми в разных функциях и потоках.
Единственная проблема, что TBB не очень хорошо поддерживает задачи засабмиченные из сторонних потоков.
Так же могу порекомендовать библиотеку QuickThread: http://www.quickthreadprogramming.com/
Она в полной мере поддерживает асинхронное программирование, т.ч. нет проблем с задачами засабмиченными из сторонних потоков. Так же полностью поддерживает IO задачи (в отличие от TBB). Плюс поддерживает NUMA архитектуры.
И так же есть библиотека just::thread (которая разрабатывается разработчиком boost::thread): http://www.stdthread.co.uk/
Это, в принципе, не более, чем реализация поддержки многопоточности из C++0x, но те же std::async/feature/promise там есть.
R>И так же есть библиотека just::thread (которая разрабатывается разработчиком boost::thread): R>http://www.stdthread.co.uk/ R>Это, в принципе, не более, чем реализация поддержки многопоточности из C++0x, но те же std::async/feature/promise там есть.
Автор буквально только что выпустил новый релиз с лучшей поддержкой асинхронных задач, и написал блог по этому поводу: http://www.justsoftwaresolutions.co.uk/threading/multithreading-in-c++0x-part-8-futures-and-promises.html
Рассмотрено несколько реальных примеров использования std::async/feature/promise.
В С++0х поддержка асинхронных задач, конечно, без особых наворотов, но в перспективе хочется верить, что это зато будет портируемая, встроенная в компиляторы, функциональность.
У Intel TBB что за лицензия такая? GPL v2 with the libstdC++ Runtime Exception.
Не пойму, можно в не опенсорс использовать без покупки коммерческой лицензии или нет
Здравствуйте, 8bit, Вы писали:
8>Здравствуйте, remark, Вы писали:
8>У Intel TBB что за лицензия такая? GPL v2 with the libstdC++ Runtime Exception. 8>Не пойму, можно в не опенсорс использовать без покупки коммерческой лицензии или нет
Можно.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Если задач немного и фиксированное число, то можно его реализовать матрицей смежности. Строка — задача, столбец — кого ждет. Когда задача заканчивается, она ( а лучше некий менеджер, которого она уведомляет о своем окончании) проходит по столбцу этой матрицы и зануляет его, после чего проверяет все строки, в которых было зануление — остался ли там хоть один ненулевой элемент. Если нет — в пул эту задачу. Если задач не фиксированное число, можно оставить тот же алгоритм, но добавлять строки (столбцы не придется — не могут же ранее появившиеся задачи ждать новых).
Интересно, а существует решение, в котором сложность "постановки задачи в очередь" равна O(n), где n — число задач, от которых данная зависит, а сложность обработки завершения задачи не превышает O(m), где m — число задач, зависящих от данной?
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Если задач немного и фиксированное число, то можно его реализовать матрицей смежности. Строка — задача, столбец — кого ждет. Когда задача заканчивается, она ( а лучше некий менеджер, которого она уведомляет о своем окончании) проходит по столбцу этой матрицы и зануляет его, после чего проверяет все строки, в которых было зануление — остался ли там хоть один ненулевой элемент. Если нет — в пул эту задачу. Если задач не фиксированное число, можно оставить тот же алгоритм, но добавлять строки (столбцы не придется — не могут же ранее появившиеся задачи ждать новых).
Pzz>Интересно, а существует решение, в котором сложность "постановки задачи в очередь" равна O(n), где n — число задач, от которых данная зависит, а сложность обработки завершения задачи не превышает O(m), где m — число задач, зависящих от данной?
Ну можно так изменить выделенное выше. Если для каждой строки хранить число ненулевых элементов, то уйдет проверка строки на 0 и будет O(m)
Здравствуйте, 8bit, Вы писали:
8>У Intel TBB что за лицензия такая? GPL v2 with the libstdC++ Runtime Exception. 8>Не пойму, можно в не опенсорс использовать без покупки коммерческой лицензии или нет
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>>Если задач немного и фиксированное число, то можно его реализовать матрицей смежности. Строка — задача, столбец — кого ждет. Когда задача заканчивается, она ( а лучше некий менеджер, которого она уведомляет о своем окончании) проходит по столбцу этой матрицы и зануляет его, после чего проверяет все строки, в которых было зануление — остался ли там хоть один ненулевой элемент. Если нет — в пул эту задачу. Если задач не фиксированное число, можно оставить тот же алгоритм, но добавлять строки (столбцы не придется — не могут же ранее появившиеся задачи ждать новых).
Pzz>>Интересно, а существует решение, в котором сложность "постановки задачи в очередь" равна O(n), где n — число задач, от которых данная зависит, а сложность обработки завершения задачи не превышает O(m), где m — число задач, зависящих от данной?
PD>Ну можно так изменить выделенное выше. Если для каждой строки хранить число ненулевых элементов, то уйдет проверка строки на 0 и будет O(m)
Обычно это делается подсчётом кол-ва оставшихся зависимых задач.
Если может быть не более одной зависимый задачи, то в задачу нужно добавить только:
, хочу узнать, есть ли что либо близкое или(лучше 
) полностью соответствующее таким требовамиям?
