Реализация очереди кражи работы в C/C++? [закрытый]

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

Посмотрите на резьбовые блоки Intel.

http://www.threadingbuildingblocks.org/

Не знаю, если это будет какая-либо помощь для вас, но посмотрите на статью этой статьи на сеть разработчиков AMD, простым, но должны дать вам что-то полезное

Constructured_Task_Group класс PPL использует очередь кражи работы для его реализации. Если вам нужен WSQ для резьбы, я бы порекомендовал.
Если вы на самом деле ищете источник, я не знаю, приведен ли код в PPL.h или если есть предложенная объект; Мне придется проверить, когда вернусь домой сегодня вечером.

Существует инструмент, чтобы просто сделать это очень элегантным образом. Это действительно эффективный способ популярности вашей программы в течение очень короткого времени.

Проект CILK

Премия HPC Challenge

Наша запись Cilk для CPC Challenge Премия класса 2 выиграла награду 2006 года за `` Лучшее сочетание элегантности и Представление''. Награда была сделана в SC'06 в Тампе 14 ноября 2006 года.

Если вы ищете внедрение класса в очередь в очереди автономной работы в C ++, построенные на Pthread или Boost :: Threade, удачи, мне это не так.

Однако, поскольку другие сказали, что Cilk, TBB и Microsoft's PPL у всех есть реализации рабочего стола под капотом.

Вопрос в том, вы хотите использовать очередь рабочей позиции или реализовать один? Если вы просто хотите использовать один, то выбор выше, являются хорошими отправными точками, просто планируя «задачу» в любом из них, будет достаточно.

Как сказал Blueraja, Task_Group & Structured_Task_Group в PPL сделает это, также обратите внимание, что эти классы доступны в последней версии TBB Intel TBB. Параллельные петли (Parallel_for, Parallel_For_each) также реализуются с помощью рабочего стола.

Если вы должны посмотреть на источник, а не использовать реализацию, TBB является Opensource, и Microsoft отправляет источники для его CRT, чтобы вы могли пойти спелангировать.

Вы также можете посмотреть в блоге Джо Дафери для реализации C # (но это C # и модель памяти отличается).

-Rick

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

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

Пока это все довольно общие вещи, за одним большим исключением: 1) переключение контекстов (например, установка регистров контекста процессора, таких как "стек") не может быть заявлено в чистом C или C++. Вы можете решить эту проблему, согласившись написать часть вашего пакета в машинном коде, специфичном для целевой платформы. 2) Атомный доступ к очередям для мультипроцессора не может быть сделан чисто на Си или Си++ (игнорируя алгоритм Деккера), и поэтому вам придется кодировать те, кто использует примитивы синхронизации ассемблерного языка, такие как X86 LOCK XCH или Compare and Swap. Теперь код, участвующий в обновлении очереди после безопасного доступа, не очень сложен, и вы легко можете написать это в нескольких строчках на C.

Однако, я думаю, что попытка закодировать такой пакет на C и C++ со смешанным ассемблером все же довольно неэффективна, и в конце концов, вы все равно закончите кодированием всего этого в ассемблере. Все, что осталось - это точки входа, совместимые с Си/Си++ :-}

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

Настоящая муха в мази для С и С++ заключается в том, что когда вы создаете задачу, представляющую работу, сколько места в стеке вы назначаете? Последовательные программы на С/С++ избегают этого вопроса, просто перебирая огромные суммы (например, 10Мб) из одного линейного стека, и никого не волнует, сколько это пространство стека потрачено впустую. Но если вы можете создать тысячи задач и все они будут жить в определенный момент, то вы не сможете разумно выделить по 10 Мб для каждой из них. Так что теперь вам либо нужно статически определить, сколько стекового пространства понадобится задаче (Turing-hard), либо вам нужно выделить куски стека (например, для каждого вызова функции), чего не делают широко доступные компиляторы C/C++ (например, тот, который вы, скорее всего, используете). Последний выход - это дросселирование создания задачи, чтобы ограничить ее до нескольких сотен в любой момент времени, и мультиплексирование нескольких сотен действительно огромных стеков среди живых задач. Вы не можете сделать последнее, если задачи могут блокировать/приостанавливать состояние, потому что вы столкнетесь с вашим порогом. Так что это можно сделать только в том случае, если задачи только выполняют вычисления. Похоже, что это довольно серьезное ограничение.

Для PARLANSE мы построили компилятор, который распределяет записи активации на куче для каждого вызова функции.

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