Как писать задания? (параллельный код)

Ответ 1

Java имеет параллельную структуру задач, аналогичную структуре Thread Building Blocks - она ​​называется инфраструктурой Fork-Join. Это доступно для использования с текущим Java SE 6 и быть включенным в предстоящий Java SE 7.

В дополнение к документации класса javadoc доступны ресурсы для начала работы с каркасом. На странице jsr166 упоминается, что "Существует также вики, содержащие дополнительную документацию, заметки, советы, примеры и т.д. Для этих классов".

примеры fork-join, такие как матричное умножение, являются хорошим местом для начала.

Я использовал фреймворк fork-join для решения некоторых задач для потоковой передачи Intel 2009. Структура легкая и низкая накладные расходы - шахта была единственной Java-записью для проблемы Kight Tour, и она превзошла другие записи в конкурсе. Источники и записи java доступны на сайте для загрузки.

ИЗМЕНИТЬ:

Я не знаю, как класс или куски кода может выглядеть после нажатия на пул [...]

Вы можете создать свою собственную задачу, выполнив подкласс одного из подклассов ForKJoinTask, например RecursiveTask. Здесь, как вычислить последовательность фибоначчи параллельно. (Взято из RecursiveTask javadocs - комментарии мои.)

 // declare a new task, that itself spawns subtasks. 
 // The task returns an Integer result.
 class Fibonacci extends RecursiveTask<Integer> {
   final int n;      // the n'th number in the fibonacci sequence to compute
   Fibonnaci(int n) { this.n = n; } // constructor
   Integer compute() {   // this method is the main work of the task
     if (n <= 1)         // 1 or 0, base case to end recursion
        return n;
     Fibonacci f1 = new Fibonacci(n - 1);  // create a new task to compute n-1
     f1.fork();                            // schedule to run asynchronously
     Fibonacci f2 = new Fibonacci(n - 2);  // create a new task to compute n-2
     return f2.invoke() + f1.join();       // wait for both tasks to compute.
       // f2 is run as part of this task, f1 runs asynchronously. 
       // (you could create two separate tasks and wait for them both, but running
       // f2 as part of this task is a little more efficient.
   }
 }

Затем вы запустите эту задачу и получите результат

// default parallelism is number of cores
ForkJoinPool pool = new ForkJoinPool(); 
Fibonacci f = new Fibonacci(100);
int result = pool.invoke(f);

Это тривиальный пример, чтобы все было просто. На практике производительность не будет такой хорошей, поскольку работа, выполняемая этой задачей, тривиальна по сравнению с накладными расходами на платформу задач. Как правило, задача должна выполнять некоторые значимые вычисления - достаточно, чтобы сделать накладные расходы на структуру незначительными, но не настолько, чтобы вы в конечном итоге столкнулись с одним ядром в конце проблемы, выполняющей одну большую задачу. Разделение больших задач на более мелкие гарантирует, что одно ядро ​​не останется много работы, в то время как другие ядра простаивают - использование меньших задач заставляет больший объем загружать, но не настолько мал, что задача не делает реальной работы.

[...] или как странный код может выглядеть, когда вам нужно сделать копию всего и сколько всего толкнул на пул.

Только сами задачи вставляются в пул. В идеале вы не хотите копировать что-либо: чтобы избежать помех и необходимости блокировки, что замедлит вашу программу, ваши задачи в идеале должны работать с независимыми данными. Данные, доступные только для чтения, могут быть разделены между всеми задачами и не нужно копировать. Если потоки должны взаимодействовать с созданием некоторой большой структуры данных, лучше всего построить куски отдельно, а затем объединить их в конце. Комбинация может быть выполнена как отдельная задача, или каждая задача может добавить ее часть головоломки в общее решение. Это часто требует некоторой формы блокировки, но это не является значительной проблемой производительности, если работа задачи намного больше, чем работа по обновлению решения. Решение My Knight Tour использует этот подход, чтобы обновить общий репозиторий туров на борту.

Работа с задачами и concurrency - это довольно парадигма, переход от обычного однопоточного программирования. Для решения данной проблемы часто существует несколько конструкций, но только некоторые из них подходят для решения с резьбой. Может потребоваться несколько попыток понять, как переделать знакомые проблемы многопоточным способом. Лучший способ узнать - посмотреть на примеры, а затем попробовать это для себя. Всегда профиль, и меняют влияние изменения количества потоков. Вы можете явно указать количество потоков (ядер) для использования в пуле в конструкторе пула. Когда задачи разбиваются линейно, вы можете ожидать приближения линейного ускорения по мере увеличения количества потоков.

Ответ 2

Игра с "фреймворками", претендующими на решение неразрешимых (оптимальное планирование задач - NP), не поможет вам вообще - читать книги, а не статьи о параллельных алгоритмах. Так называемые "задачи" - это не что иное, как причудливое имя для определения разделимости проблемы (части, которые могут быть вычислены независимо друг от друга). Класс разделимых задач очень мал - и они уже покрыты старыми книгами.

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

Когда вы вводите высокий parallelism, вы даже не можете поддерживать очередь, у вас даже нет шины памяти. Представьте себе, что 100 CPU пытаются синхронизировать только один общий доступ или пытаться сделать память автобусный арбитраж. Вы должны предварительно спланировать и предварительно настроить все, что будет выполняться, и по существу доказать правильность на белой доске. Intel Threading Building Blocks - маленький ребенок в этом мире. Они предназначены для небольшого количества ядер, которые могут совместно использовать шину памяти. Бегущие сепарабельные проблемы - это без проблем, с которыми вы можете обойтись без каких-либо "фреймворков".

Итак, вы вернулись к тому, чтобы читать как можно больше различных параллельных алгоритмов. Обычно требуется 1-3 года для исследования примерно оптимальной компоновки барьера данных для одной проблемы. Он становится макетом, когда вы идете на 16+ ядер на одном чипе, поскольку только первые соседи могут эффективно обмениваться данными (в течение одного цикла защиты данных). Таким образом, вы действительно узнаете гораздо больше, посмотрев на CUDA и документы и результаты с экспериментальным 30-ядерным процессором IBM, чем на рынке продаж Intel или на игру Java.

Остерегайтесь демонстрационных проблем, для которых размер ресурсов впустую (количество ядер и памяти) намного больше, чем ускорение, которое они достигают. Если требуется 4 ядра и 4x ОЗУ для решения чего-то в 2 раза быстрее, решение не масштабируется для распараллеливания.