Оригинальная ссылка:A Java Fork/Join Framework(PDF) - Doug Lea
на основеСеть параллельного программирования — ifeve.comначальствоAlex/Сяо Хуанперевести,Фан ТэнфэйВыверенный перевод:Платформа соединения Java Fork
Переводы размещены вСеть параллельного программирования — ifeve.com:Java Fork/JoinРамка, 2017-11-02

заказ перевода

Doug LeaБог оJava 7Представленный имFork/JoinРамочный тезис.

реактивное программирование(Reactive Programming / RP) как парадигма постепенно признается и внедряется во всей отрасли.Это краткое изложение усовершенствования модели системного технологического проектирования/архитектуры после понимания и определения бизнес-требований предыдущей системы.JavaБудучи зрелой платформой, она всегда была несколько стабильной в принятии и следовании тенденциям и обладает удивительной жизнеспособностью:

Java 7при условииForkJoinPool, поддерживаетсяJava 8который предоставилStream(Reactive StreamдаRPосновной компонент).
Кроме тогоJava 8также обеспечиваетLamda(выражать и эффективно использоватьRPнеобходимостьFPязыковые конструкции и идеи).
С этими постоянными, но вечными приготовлениями впереди, вJava 9предоставлено вRPизFlow API,заJavaКруг обеспечивает официальноеRP API, маркировкаRPПереход от фазы свободного исследования в рыночном стиле к унифицированному использованию в церковном стиле.

Из вышеприведенного описания видно, чтоForkJoinPoolпринципиальное значение.

Кстати, еще одно упоминаниеJava 9изFlow APIиз@authorСлишкомDoug LeeО~

PS:
СвояПонимание поверхностное, а недочетов и неточностей в переводе точно будет много.Предложения приветствуются(Отправить вопрос) и исправления (Отправить код после форка)! :two_hearts:

0. Аннотация
1. Введение
2. Дизайн
- 2.1 work−stealing
3. Реализация
- 3.1 Дек
- 3.2 Перехваты и бездействие
4. Производительность
5. Заключение
6. Благодарности
7. Ссылки

0. Аннотация

В этой статье описываетсяFork/JoinДизайн, реализация и производительность фреймворка, которые поддерживаются (рекурсивным) разделением задачи на подзадачи, параллельным выполнением этих подзадач и объединением окончательных результатов после завершения всех подзадач Программирование параллельных вычислений. Общий дизайн основан наCilkРазработаноwork-stealingРамка. На уровне проектирования в основном речь идет о том, как эффективно создавать очереди задач и рабочие потоки и управлять ими. Данные тестов производительности показывают, что хорошая программа для параллельных вычислений улучшит большинство приложений, а также указывают на некоторые потенциальные возможности для улучшения.

Примечание 1:Cilkэто IntelCilkязык. ИнтелC++Новые возможности редактораCilkметоды расширения языка дляC/C++Язык добавляет поддержку мелких задач, упрощая добавление параллелизма к новому и существующему программному обеспечению, чтобы полностью использовать мощность нескольких процессоров.

1. Введение

Fork/JoinПараллелизм — один из самых простых и наиболее эффективных методов проектирования для получения хорошей производительности параллельных вычислений.Fork/JoinПараллельный алгоритм — это параллельная версия знакомого алгоритма «разделяй и властвуй».

Result solve(Problem problem) {
    if (problem is small) {
        directly solve problem
    } else {
        split problem into independent parts
        fork new subtasks to solve each part
        join all subtasks
        compose result from subresults
    }
}

forkоперация начнет новую параллельFork/JoinПодзадачи.joinОперация будет ожидать завершения всех подзадач.Fork/JoinАлгоритмы, как и другие алгоритмы «разделяй и властвуй», всегда рекурсивно и неоднократно разделяют подзадачи до тех пор, пока эти подзадачи не смогут выполняться достаточно простым коротким последовательным способом.

Некоторые связанные методы программирования и примеры находятся в"JavaПараллельное программирование — принципы проектирования и шаблоны, второе издание^[7]Это обсуждалось в разделе 4.4. В этой статье будет обсуждатьсяFJTaskДизайн (раздел 2), реализация (раздел 3) и производительность (раздел 4)Java™Рамка.FJTaskв видеutil.concurrentчасть пакета, в настоящее время доступного наgee.cs.oswego.edu/полученный.

2. Дизайн

Fork/JoinПрограммы могут работать в любой среде, которая поддерживает возможность распараллеливания выполнения подзадач сборки и имеет механизм ожидания завершения выполнения подзадач. Тем не мение,java.lang.Threadкласс (в том числеPOSIX pthread, это тожеJavaоснова, на которой базируется нить)Fork/JoinНе лучший выбор для программ:

Fork/JoinЗадачи имеют простые и регулярные потребности в синхронизации и управлении. По сравнению с обычными нитями,Fork/JoinСхема вычислений, отображаемая задачей, приведет к более гибкой стратегии планирования. Например,Fork/JoinПомимо ожидания подзадач, задачи не нужно блокировать в других случаях. Таким образом, традиционные затраты на отслеживание заблокированных потоков в данном случае на самом деле пустая трата времени.
Для разумной детализации базовой задачи создание потока и управление им может быть даже дороже, чем само выполнение задачи. Хотя степень детализации должна быть скорректирована соответствующим образом, поскольку приложение работает на разных конкретных платформах. Но чрезвычайно крупномасштабные накладные расходы на потоки ограничивают параллелизм.

короче,JavaПара стандартных резьбовых рамокFork/JoinЭто слишком громоздко для программирования. Но поскольку потоки составляют основу многих других параллельных и параллельных программ, невозможно (или нецелесообразно) полностью исключить эти затраты или настроить планирование потоков для этой цели.

Хотя эта идея существует уже давно, первая опубликованная структура для систематического решения этих проблем былаCilk^[5].Cilkи другие облегченные фреймворки основаны на базовых механизмах потоков и процессов операционной системы для поддержки специальных задач.Fork/Joinпрограмма. Эта стратегия также применима кJava,несмотря на то чтоJavaПотоки реализованы на основе низкоуровневых возможностей операционной системы. Основным преимуществом создания такой облегченной среды выполнения является возможность сделатьFork/JoinПрограммы написаны более интуитивно понятным способом, что позволяет имJVMработает в системе.

FJTaskкаркас основан наCilkЭволюция дизайна. Другие подобные фреймворкиHood^[4],Filaments^[8],Stackthreads^[10]и некоторые связанные системы, которые полагаются на облегченное выполнение задач. Все эти платформы используют операционную систему для сопоставления потоков сCPUСопоставьте задачи с потоками так же, как описано выше. просто они будут использоватьFork/JoinПростота, регулярность и последовательность программы для выполнения этого сопоставления. Хотя эти фреймворки могут работать с неформально параллельными программами, они оптимизируютFork/Joinдизайн:

Набор пулов рабочих потоков готов. Каждый рабочий поток является стандартным («тяжеловесным») потоком, который обрабатывает задачи, хранящиеся в очереди (это относится кThreadподкласс классаFJTaskRunnerобъект экземпляра). Как правило, рабочие потоки должны соответствовать количеству процессоров в системе. Для некоторых собственных фреймворков, таких какCilk, они сначала будут отображены в потоки ядра или облегченные процессы, а затем запущены на процессоре. существуетJava, виртуальная машина и операционная система должны быть объединены друг с другом, чтобы выполнить сопоставление потоков и процессоров. Тогда для операций с интенсивными вычислениями это отображение является относительно простой задачей для операционной системы. Любая разумная стратегия отображения приведет к отображению потоков на разные процессоры.
всеFork/JoinЗадачи — это экземпляры облегченных классов выполнения, а не экземпляры потоков. существуетJava, должны быть реализованы независимые исполняемые задачиRunnableинтерфейс и переопределениеrunметод. существуетFJTaskframework эти задачи будут наследоваться как подклассыFJTaskвместоThread, все они достигаютRunnableинтерфейс. (Для приведенных выше двух случаев класс также может реализоватьRunnableИнтерфейс, экземпляр объекта класса может выполняться как в задаче, так и в потоке. Поскольку на выполнение задачи влияетFJTaskОграничения строгого правила метода, подклассыFJTaskУсловно говоря, удобнее вызывать их напрямую. )
Мы будем использовать специальную очередь и принцип планирования для управления задачами и их выполнения через рабочие потоки. Эти механизмы реализуются родственными методами, представленными в классе задач:fork,join,isDone(идентификатор конечного состояния) и некоторые другие удобные методы, такие как вызовcoInvokeдекомпозировать и объединить две или более задач.
Простой класс контроля и управления (здесь имеется в видуFJTaskRunnerGroup) для запуска пула рабочих потоков и первоначального выполнения вызова, инициированного обычным потокомFork/Joinзадание (аналогичноJavaв программеmainметод).

В качестве стандартного примера, демонстрирующего программисту, как работает фреймворк, это класс, вычисляющий функцию Фибоначчи.

class Fib extends FJTask {
    static final int threshold = 13;
    volatile int number; // arg/result

    Fib(int n) {
        number = n;
    }

    int getAnswer() {
        if (!isDone())
            throw new IllegalStateException();
        return number;
    }

    public void run() {
        int n = number;
        if (n <= threshold) // granularity ctl
            number = seqFib(n);
        else {
            Fib f1 = new Fib(n - 1);
            Fib f2 = new Fib(n - 2);
            coInvoke(f1, f2);
            number = f1.number + f2.number;
        }
    }

    public static void main(String[] args) {
        try {
            int groupSize = 2; // for example
            FJTaskRunnerGroup group = new FJTaskRunnerGroup(groupSize);
            Fib f = new Fib(35); // for example
            group.invoke(f);
            int result = f.getAnswer();
            System.out.println("Answer: " + result);
        } catch (InterruptedException ex) {
        }
    }

    int seqFib(int n) {
        if (n <= 1) return n;
        else return seqFib(n − 1) + seqFib(n − 2);
    }
}

Эта версия работает как минимум быстрее, чем любая задача на платформах, упомянутых в разделе 4.ThreadКласс работает в 30 раз быстрее. Сохраняя производительность, программа по-прежнему поддерживаетJavaПереносимость многопоточных программ. Для программистов обычно есть два значения параметра, которые их беспокоят:

Количество создаваемых рабочих потоков обычно может быть таким же, как и количество процессоров на платформе (или меньше, для других связанных задач, или, в некоторых случаях, больше, для повышения производительности задач, не связанных с интенсивными вычислениями)).
Параметр детализации представляет собой точку, в которой стоимость создания задач перевешивает потенциальный выигрыш в производительности от распараллеливания. Этот параметр больше зависит от алгоритма, чем от платформы. Переломный момент, который обычно хорошо работает на одном процессоре, также будет хорошо работать на многопроцессорной платформе. В качестве побочного эффекта этот подход можно комбинировать сJavaМеханизм динамической компиляции виртуальной машины — хорошее сочетание, и этот механизм лучше оптимизирует методы малых блоков, чем монолитные программы. Таким образом, в сочетании с преимуществами локализации данных,Fork/JoinПроизводительность алгоритма лучше, чем у других алгоритмов даже на одном процессоре.

2.1 `work−stealing`

Fork/JoinЯдром фреймворка является легкий механизм планирования.FJTaskУсыновленныйCilkизwork-stealingПринята базовая стратегия планирования:

Каждый рабочий поток поддерживает свою собственную очередь отправки выполняемых задач.
Очереди поддерживаются в виде двусторонних очередей (Примечание:dequesЧасто произносится как «колоды»), поддерживает не только LIFO —LIFOизpushиpopОперация также поддерживает принцип "первым пришел - первым вышел" --FIFOизtakeработать.
Для данного рабочего потока подзадачи, сгенерированные задачей, будут помещены в собственную очередь рабочего потока.
Рабочие потоки используют LIFO --LIFO(последний элемент первым) упорядочить, выталкивая задачи для обработки задач в очереди.
Когда у рабочего потока нет локальных задач для запуска, он будет использовать FIFO.FIFOПравила пытаются случайным образом взять («украсть») задачу из другого рабочего потока для запуска.
когда рабочий поток касаетсяjoinоперация, которая будет обрабатывать другие задачи, если это возможно, до тех пор, пока целевой задаче не будет сообщено, что она завершена (черезisDoneметод). Все задачи будут выполнены без блокировки.
Когда рабочий поток больше не может получать задачи и не может обрабатываться другими потоками, он завершается (черезyield,sleepи/или настройку приоритета, см. раздел 3) и повторить попытку через некоторое время, пока всем рабочим потокам не будет сообщено, что они простаивают. В этом случае они будут блокироваться до тех пор, пока другие задачи не будут снова вызваны верхним уровнем.

Используйте ЛИФО—LIFOИспользуется для обработки собственной задачи каждого рабочего потока, но с использованием FIFO --FIFOПравила используются для получения других задач, что является широко используемой рекурсией.Fork/JoinСредство тюнинга дизайна. Цитировать^[5]Детали подробно обсуждаются.

Если задачи захвата потоков выполняются с направления, противоположного владельцу очереди, это снижает конкуренцию за потоки. Он также отражает стратегию приоритета больших задач рекурсивного алгоритма «разделяй и властвуй». Следовательно, возможно, что более ранняя украденная задача предоставит более крупную единичную задачу, что позволит рекурсивно разложить украденный поток в будущем.

Как следствие приведенных выше правил, для некоторых основных операций задачи с относительно небольшой степенью детализации будут выполняться быстрее, чем те, которые используют только грубое разбиение на разделы и те, которые не используют рекурсивную декомпозицию. Хотя соответствующие несколько задач находятся в большинствеFork/JoinКадры могут быть украдены другими рабочими потоками, но создание множества хорошо организованных задач означает, что пока рабочий поток находится в состоянии выполнения, эта задача потенциально может быть выполнена.

3. Реализация

Этот кадр состоит примерно из 800 строк чистогоJavaСостав кода, основной классFJTaskRunner,этоjava.lang.Threadподкласс .FJTaskОн поддерживает только логическое значение конечного состояния, а все остальные операции делегируются текущим рабочим потоком.JFTaskRunnerGroupКлассы используются для создания рабочих потоков, поддержания некоторого общего состояния (например, идентификаторов для всех рабочих потоков, необходимых для операций кражи), а также координации запуска и завершения работы.

Более подробную документацию по реализации можно найти по адресуutil.concurrentПросмотр параллельных пакетов. Этот раздел фокусируется только на двух типах проблем и некоторых решениях, которые были сформированы при реализации этой структуры: поддержка эффективных операций с двусторонними списками (push,popиtake) и поддерживает протокол кражи, когда рабочие потоки пытаются получить новые задачи.

3.1 Дек

(Примечание: элементы в двухсторонней очереди могут быть извлечены с обоих концов, а операции вставки и удаления ограничены обоими концами очереди.)

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

JavaВиртуальная машина отвечает за выделение памяти для задач.JavaСборщик мусора избавляет нас от необходимости писать специальный распределитель памяти для обслуживания задач. По сравнению с аналогичными фреймворками на других языках эта причина позволяет значительно сократить реализациюFJTaskсложность и объем необходимого кода.

Базовая структура дека использует очень обычную структуру — массив (хотя и переменной длины) для представления каждой очереди с двумя индексами:topИндекс подобен указателю стека в массиве.pushиpopоперация по изменению.baseиндекс может быть передан толькоtakeоперация по изменению. с учетомFJTaskRunnerОперации плавно связаны с деталями двухсторонней очереди (например,forkпозвонить напрямуюpush), поэтому эта структура данных размещается непосредственно внутри класса, а не как отдельный компонент.

Но доступ к элементам двухсторонней очереди будет осуществляться одновременно несколькими потоками при отсутствии достаточной синхронизации и единственногоJavaЭлементы массива также не могут быть объявлены какvolatileпеременная (столкновение:объявлен какvolatileмассив, элементы которого не имеютvolatileсемантики), каждый элемент массива на самом деле является фиксированной ссылкой на массив, который поддерживает единуюvolatileСсылочный объект пересылки. Это решение было принято с самого начала в основном из-заJavaНепротиворечивость модели памяти. Но на этом уровне было показано, что требуемая косвенность повышает производительность на некоторых протестированных платформах. Вероятно, потому что доступ к соседним элементам снижает конкуренцию за кеш, косвенное обращение к памяти происходит немного быстрее.

Основная проблема реализации двухсторонней очереди связана с синхронизацией и ее отменой. Хотя вJavaИспользуя оптимизированный инструмент синхронизации на виртуальной машине, для каждогоpushиpopДолжна ли операция получить блокировку или позволить всему этому стать узким местом в производительности? Затем, основываясь на следующих наблюдениях, мы можем изменитьClikстратегии в , что дает нам допустимое решение:

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

ПучокtopиbaseИндекс определяется какvolatileПеременная может гарантировать, что если в очереди более одного элемента,popиtakeОперации могут выполняться без блокировки. Это делается черезDekkerАлгоритм достижения. когдаpushпредварительно уменьшить доtopВремя:

if (–top >= base) ...

иtakeпредварительно уменьшить доbaseВремя:

if (++base < top) ...

В каждом из приведенных выше случаев они проверяют, не приведет ли это к тому, что дек станет пустой очередью, сравнивая два индекса. Асимметричное правило будет использоваться для предотвращения потенциальных конфликтов:popперепроверит состояние и продолжит работу после получения блокировки (дляtakeдержится) и не завершается до тех пор, пока очередь действительно не станет пустой. иtakeОперация завершится немедленно, особенно при попытке получить другую задачу. Используйте с другими подобнымиClikизTHEКак и в протоколе, эта асимметрия является единственным существенным изменением.

использоватьvolatileпеременный индексpushОперации могут выполняться без синхронизации, если очередь не заполнена. Если очередь вот-вот переполнится, она сначала должна получить блокировку очереди, чтобы сбросить длину очереди. В остальных случаях просто убедитесь,topОперация ставится в очередь для обновления после того, как слот массива очередей окажется в полосе подавления помех.

При последующей реализации инициализации было обнаружено, что существует несколькоJVMне встречаетсяJavaПравильное чтение и запись в модели памятиvolatileпеременные правила. как рабочее место,popУсловие для повторной попытки операции при удержании блокировки изменено на: если есть два или меньше элементов, иtakeОперация добавляет вторую блокировку для обеспечения эффекта барьера памяти, затем запускается повторная попытка. Это удовлетворительно, пока поток-владелец теряет не более одного индекса, и это приводит лишь к небольшому снижению производительности.

3.2 Перехваты и бездействие

В среде упреждающей работы рабочие потоки ничего не знают о требованиях синхронизации программ, которые они запускают. Они просто создают, публикуют, извлекают, получают, управляют состоянием и выполняют задачи. Эта простая схема делает ее эффективной, когда у всех потоков есть много задач для выполнения. Однако этот подход имеет свою цену, он будет полагаться на эвристику, когда работы недостаточно. То есть после запуска основной задачи до ее окончания, в некоторыхFork/JoinВ алгоритме используются указатели синхронизации с точкой.

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

JavaНет очень надежной работы, чтобы гарантировать это, но на практике это часто приемлемо. Поток, которому не удалось украсть, понизит свой приоритет перед попыткой другого угона, выполняясь между попытками угона.Thread.yeildоперацию, а затем поместить ее состояние вFJTaskRunnerGroupустанавливается в неактивное состояние. Они будут блокироваться до тех пор, пока не появится новый основной поток. В других случаях после определенного количества спинов потоки уйдут в сон и будут спать вместо того, чтобы отказаться от кражи. Усовершенствованный механизм сна может создавать иллюзию того, что разделение задач занимает много времени. Но это кажется лучшим и общим компромиссом. Будущие версии платформы могут поддерживать дополнительные методы управления, позволяющие программистам переопределять реализацию по умолчанию, если они почувствуют снижение производительности.

4. Производительность

Сегодня с компиляторами иJavaВ связи с постоянным улучшением производительности виртуальных машин результаты тестов производительности применимы лишь некоторое время. Однако данные результатов испытаний, представленные в этом разделе, показываютFork/JoinОсновные возможности фреймворка.

В следующей таблице кратко описывается наборFork/Joinтестовая программа. Эти программы изutil.concurrentПример кода в пакете адаптирован для демонстрацииFork/JoinПолучены различия в производительности фреймворка при решении разных типов моделей задач, а также результаты тестирования фреймворка на некоторых общих параллельных тестовых процедурах.

программа	описывать
`Fib`(последовательность Фибоначчи)	как описано в разделе 2`Fibonnaci`программа, где значение параметра равно 47, а пороговое значение равно 13
`Integrate`(за баллы)	Используйте формулу рекурсивной квадратурной пары Гаусса $(2 \cdot i - 1) \cdot x ^ {(2 \cdot i - 1)}$ Найдите интеграл от -47 до 48,*`i`*четное число от 1 до 5
`Micro`(для дифференциации)	Найдите наилучшую стратегию ходов для настольной игры, каждый раз рассчитывая следующие четыре хода.
`Sort`(Сортировать)	Отсортируйте 100 миллионов чисел, используя алгоритм слияния/быстрой сортировки (на основе`Cilk`алгоритм)
`MM`(умножение матриц)	2048 х 2048`double`тип матрицы для умножения
`LU`(разложение матрицы)	4096 х 4096`double`тип матрицы для разложения
`Jacobi`(метод итераций Якоби)	для 4096 х 4096`double`Матрица релаксируется итерационным методом с верхним пределом 100 итераций.

Основные тесты, упомянутые ниже, тестовые программы выполняются вSun Enterprise 10000На сервере на сервере 30CPU, операционная система естьSolaris 7система работаетSolarisкоммерческая версия1.2 JVM(2.2.2_05более ранняя версия релизной версии). в то же время,JavaПараметр среды виртуальной машины о сопоставлении потоков выбран как "bound threads(Примечание переводчика:XX:+UseBoundThreads, связывает потоки пользовательского уровня с потоками ядра, только сSolarisсвязанных), а настройки параметров памяти виртуальной машины обсуждаются в разделе 4.2. Кроме того, следует отметить, что некоторые из упомянутых ниже тестов выполняются с 4CPUизSun Enterprise 450на сервере.

Чтобы уменьшить детализацию таймера иJavaВлияние факторов запуска виртуальной машины на результаты тестирования, программа тестирования использует огромное количество входных параметров. И некоторые другие факторы запуска мы маскируем, запуская задачу инициализации перед запуском таймера. Большинство полученных результатов тестов находятся в середине трех результатов тестов, но некоторые данные тестов получены только из результатов одного запуска (включая многие тесты в разделах 4.2 ~ 4.4), поэтому эти результаты тестов будут зашумлены.

4.1 Эффект ускорения

Тестируя один и тот же набор задач с разным количеством (1 ~ 30) рабочих потоков, он используется для получения результатов теста масштабируемости фреймворка. Хотя мы не можем гарантироватьJavaВсегда ли виртуальная машина может сопоставить каждый поток с другимCPUВ то же время у нас нет доказательств, подтверждающих это. Можно сопоставить новый поток сCPUЗадержка будет увеличиваться с увеличением количества потоков и может различаться в разных системах и разных тестовых программах. Однако полученные результаты тестирования показывают, что увеличение количества потоков увеличивает использованиеCPUКоличество.

Ускорение обычно выражается какTime_n / Time₁. Как показано на рисунке выше, лучшее ускорение показывает программа, вычисляющая интегрирование (28,2 для 30 потоков), а худшее — программа матричной факторизации (30 потоков — это всего лишь 15,35 для ускорения).

Другой мерой масштабируемости является скорость выполнения задачи и среднее время, необходимое для выполнения одной задачи (здесь задача может быть задачей узла рекурсивной декомпозиции или задачей корневого узла). Приведенные ниже данные показывают данные о скорости выполнения задачи, полученные при выполнении каждой программы за один раз. Очевидно, что количество задач, выполняемых в единицу времени, должно быть фиксированной константой. Однако на самом деле по мере увеличения количества потоков полученные данные будут демонстрировать небольшое уменьшение, что также указывает на некоторые ограничения масштабируемости. Здесь необходимо пояснить, что огромная разница в производительности скорости выполнения задач в каждой программе вызвана разницей в степени детализации ее задач. Программа с наименьшей скоростью выполнения задачиFib(последовательность Фибоначчи) с порогом, установленным на 13, в общей сложности было выполнено 2,8 миллиона модульных задач с 30 потоками.

Четыре фактора способствовали тому, что показатели выполнения задач для этих программ не отображались в виде горизонтальной линии. Три из них являются общими причинами для всех сред параллелизма, поэтому мы начнем сFJTaskрама (в отличие отCilkи другие фреймворки), а именно сбор мусора.

4.2 Сбор мусора

В целом, производительность текущего механизма сборки мусора сравнима сFork/JoinРамка соответствует:Fork/JoinПрограммы будут генерировать огромное количество блоков задач во время выполнения, но эти задачи быстро превратятся в мусор памяти после их выполнения. По сравнению с однопоточной программой, выполняемой последовательно в любое время, ее соответствующаяFork/JoinПрограмма требует максимальноpумноженное на объем памяти (гдеpэто количество потоков). Сборщик мусора с копией полупространства на основе генерации (то есть тот, который используется в тестовой программе в этой статье)JavaСборщик мусора, используемый виртуальной машиной, может очень хорошо справиться с этой ситуацией, потому что этот механизм сборки мусора копирует только блоки памяти, не являющиеся мусором, во время высвобождения памяти. Это позволяет избежать сложной проблемы с ручным параллельным управлением памятью, когда отслеживаются единицы памяти, выделенные одним потоком, но используемые другим потоком. Этому механизму сборки мусора не нужно знать источник выделения памяти, поэтому ему не нужно решать эту сложную проблему.

Типичное проявление преимуществ этого механизма сборки мусора: при использовании этого механизма сборки мусора выполняются четыре потокаFibПроцедура занимает всего 5,1 секунды, и еслиJavaВиртуальная машина настроена на отключение повторного использования копий генерации (в этом случае используется метка-очистка (mark−sweep) механизм сборки мусора), который занимает 9,1 секунды.

Однако механизм сборки мусора становится фактором масштабируемости только в том случае, если использование памяти достигает высокого значения, потому что в этом случае виртуальная машина должна часто останавливать другие потоки для сборки мусора. Приведенные ниже данные показывают три различных параметра памяти (JavaВиртуальная машина поддерживает настройку параметров памяти через дополнительные параметры), разница показана в коэффициенте ускорения: по умолчанию полупространство 4M, полупространство 64M, и по количеству потоков по формуле (2 + 2p) M задает полупространство. При меньшем полупространстве накладные расходы на остановку других потоков и сборку мусора начинают влиять на запечатывание в тех случаях, когда дополнительные потоки вызывают увеличение скорости сборки мусора.

Учитывая приведенные выше результаты, мы используем полупространство 64M в качестве рабочего стандарта для других тестов. На самом деле лучшей стратегией для установки размера памяти является определение фактического количества потоков на тест. (Как и в случае с тестовыми данными выше, мы обнаружили, что в этом случае ускорение будет более плавным). С другой стороны, установленный программой порог детализации задачи также должен увеличиваться пропорционально количеству потоков.

4.3 Распределение памяти и размер слова

Среди тестовых программ, упомянутых выше, четыре программы создают и манипулируют большим количеством общих массивов и матриц: числовая сортировка, матричное умножение/разложение на множители и релаксация. Среди них алгоритм сортировки должен быть операцией перемещения данных (переместить данные памяти вCPUcache) и общая пропускная способность системной памяти, наиболее чувствительные. Чтобы определить характер этих влияющих факторов, мы ранжируем алгоритмsortПереписан в четыре версии соответственноbyteбайтовые данные,shortтип данных,intвведите данные иlongСортировать данные. Все данные, которыми манипулируют эти программы, равны 0. ~ 255 для обеспечения равенства между этими сравнительными тестами. Теоретически, чем больше разрядность операционных данных, тем больше нагрузка на память.

Результаты тестов показывают, что увеличение нагрузки на память приводит к снижению ускорения, хотя мы не можем предоставить четких доказательств того, что это единственная причина такого поведения. Но разрядность данных влияет на производительность программы. Например, с помощью потока, сортирующего байтыbyteДанные занимают 122,5 секунды, однако сортировкаlongДанные занимают 242,5 секунды.

4.4 Синхронизация задач

Как обсуждалось в разделе 3.2, модель кражи задач часто сталкивается с проблемами синхронизации обработки задач.Если рабочий поток получает задачу, но в соответствующей очереди нет задач для получения, это вызовет конкуренцию. существуетFJTaskВо фреймворке эта ситуация иногда приводит к принудительному переходу потока в спящий режим.

отJacobiМы можем видеть такого рода проблемы в программе.JacobiПрограмма выполняется в течение 100 шагов, и ячейки вокруг соответствующих точек матрицы обновляются на каждом шаге. В программе есть глобальное барьерное разделение. Чтобы уточнить размер воздействия этой операции синхронизации. Мы делаем синхронизацию каждые 10 шагов в программе. Разница в масштабируемости, показанная на рисунке, иллюстрирует влияние этой стратегии параллелизма. Это также означает, что мы должны добавить дополнительные методы для переписывания программистами в последующих версиях этой структуры, чтобы настроить структуру для достижения максимальной эффективности в различных сценариях. (Обратите внимание, что этот график может немного преувеличивать влияние фактора синхронизации, так как версия с 10-этапной синхронизацией, скорее всего, должна управлять большей локальностью задач)

4.5 Локальность задачи

FJTask, или другойFork/JoinФреймворк максимально оптимизирован для распределения задач, чтобы рабочие потоки обрабатывали задачи, сгенерированные их собственной декомпозицией. Потому что, если вы этого не сделаете, производительность вашей программы пострадает по двум причинам:

Кража задач из других очередей обходится дороже, чем выполнение их в своей очередиpopОперация дорогая.
В большинстве программ операции задачи работают с общей единицей данных, и лучший доступ к локальным данным можно получить, запустив только собственную часть задачи.

Как показано выше, в большинстве программ относительные данные о краже задач поддерживаются в лучшем случае на очень низком уровне. тогда в которомLUиMMПо мере увеличения количества потоков программа будет создавать больший дисбаланс в рабочей нагрузке (относительно больший захват задач). Настроив алгоритм, мы можем уменьшить этот эффект, чтобы получить лучшее ускорение.

4.6 Сравнение с другими фреймворками

По сравнению с другими фреймворками на разных языках маловероятно получение каких-либо четких или значимых результатов сравнения. Однако с помощью этого метода, по крайней мере, можно узнатьFJTaskВ отличие от других языков (здесь в основном имеется в видуCиC++), чтобы сравнить сильные стороны и недостатки аналогичных фреймворков, написанных на . В следующей таблице показаны несколько похожих фреймворков (Cilk,Hood,Stackthreadsа такжеFilaments) проверенные данные о производительности. Участвующие тесты находятся в 4CPUизSun Enterprise 450Сервер работает в 4 потока. Чтобы избежать реконфигурации в другой среде или программе, все тестовые программы запускаются с немного меньшим набором задач, чем тесты выше. Полученные данные также являются лучшим значением из трех тестов, чтобы убедиться, что компилятор или конфигурация среды выполнения обеспечивают наилучшую производительность. вFibПрограмма не указывает порог детализации задачи, что означает, что значение по умолчанию равно 1. (это установлено вFilamentsверсияFibПрограмма установлена на 1024, так что программа будет вести себя более последовательно с другими версиями).

В тесте на ускорение результаты тестов, полученные разными фреймворками на разных программах, очень близки, количество потоков 1 ~ 4, а коэффициент ускорения находится между (3,0 ~ 4,0). Поэтому следующий рисунок посвящен только абсолютной производительности различных фреймворков.Однако, поскольку все фреймворки очень быстры с точки зрения многопоточности, большинство различий больше связано с качеством самого кода, компилятора. вызванные оптимизацией элементов конфигурации или настройки параметров. В практических приложениях разные фреймворки выбираются в соответствии с реальными потребностями, чтобы компенсировать огромную разницу в производительности между разными фреймворками.

FJTaskНизкая производительность при вычислениях с массивами и матрицами с плавающей запятой. Несмотря на тоJavaПроизводительность виртуальной машины продолжает улучшаться, но по сравнению с теми,CиC++Мощный внутренний оптимизатор, используемый языком, недостаточно конкурентоспособен. Хотя это и не показано на приведенной выше диаграмме,FJTaskВерсии всех программ по-прежнему быстрее, чем версии без оптимизации компиляции. И некоторые неофициальные тесты также показывают, что большинство различий в тестах связано с проверкой границ массива, обязательствами времени выполнения. Это тожеJavaРазработчики виртуальных машин и компиляторов были обеспокоены и продолжают решать проблемы.

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

5. Заключение

В этой статье описывается использование чистогоJavaРеализация поддерживает портативные (portable),Эффективный(efficient) и масштабируемый (scalable) возможность параллельной обработки и обеспечивает удобствоAPIПозволяет программистам следовать нескольким правилам и шаблонам проектирования (ссылки^[7]предложено и обсуждено), вы можете эффективно использовать структуру. Характеристики производительности, наблюдаемые и проанализированные в примерах программ в этом документе, также предоставляют дополнительные рекомендации для пользователей и подсказывают области, в которых сама структура потенциально может быть улучшена.

Хотя показанные результаты масштабируемости относятся к одномуJVM, но эмпирически эти основные выводы должны оставаться в силе и в более общем случае:

Хотя поколенияGC(generational GC) обычно хорошо работает с параллелизмом, но может быть форсирован при быстрой генерации мусораGCОчень часто это мешает масштабируемости программы. в такомJVMвыше, эта основная причина, по-видимому, приводит кGCВремя, необходимое для остановки потока, примерно пропорционально количеству запущенных потоков. Поскольку чем больше запущено потоков, тем больше мусора генерируется в единицу времени, а увеличение накладных расходов примерно пропорционально квадрату числа потоков. При этом только вGCКогда частота относительно высока, это окажет значительное влияние на производительность. Безусловно, этот вопрос требует дальнейших исследований и параллельных разработок.GCалгоритм. Результаты этой статьи также иллюстрируют, что в многопроцессорныхJVMПараметры оптимизации доступны на (tuning options) и адаптивные механизмы (adaptive mechanisms), так что память может быть активированаCPUНеобходимо расширение номера.
Большинство проблем с масштабируемостью возникают только тогда, когда запущенные программы используютCPUДоступно на большем количестве устройствCPUпоявится когда.FJTask(и другиеFork/Joinрама) в общем 2-х, 4-х и 8-х сторонниеSMPМашина показывает почти идеальный эффект ускорения. заstock multiprocessorпредназначен для работы на более чем 16CPUВверхFork/Joinрамки, эта статья может быть первой статьей, в которой систематически сообщаются результаты. Сохраняется ли паттерн этого результата в других структурах, требует дальнейшего измерения.
Характеристики приложений, включая локальность памяти, локальность задач и использование глобальной синхронизации, часто сложнее, чем у фреймворков.JVMили нижний слойOSФункции оказывают большее влияние на масштабируемость и абсолютную производительность. Например, как видно из неофициального тестирования, тщательно избегалиdequesОперации синхронизации с повышением частоты (обсуждаемые в разделе 3.1) полезны для программ, которые генерируют относительно мало задач (таких какLU) вообще не улучшилось. Однако минимизация накладных расходов на управление задачами может расширить область применения и полезность фреймворка и связанных с ним методов проектирования и программирования.

В дополнение к постепенным улучшениям платформы будущие возможности включают создание полезных приложений на платформе (а не демонстраций и тестов), последующую оценку под нагрузкой приложения в производственных средах и в различных средах.JVMИзмеряйте и разрабатывайте расширения для простоты использования в многопроцессорных кластерах.

6. Благодарности

Часть работы в этой статье была вдохновленаSunЛаборатория поддерживается совместным исследовательским грантом. благодарныйSunлабораторияJavaисследовательской группыOle Agesen,Dave Detlefs,Christine Flood,Alex GarthwaiteиSteve Hellerза советы, помощь и комментарии.David Holmes,Ole Agesen,Keith Randall,Kenjiro Tauraи полезные комментарии к проектам этой статьи рецензентами, имена которых мне неизвестны.Bill Pughуказывает на то, что обсуждалось в разделе 3.1.JVMОграничения чтения после записи (read−after−write limitations). Особая благодарностьDave DiceУделите время тестированию модели предприятия с 30 участниками.

7. Ссылки

[1]Агесен, Оле, Дэвид Детлефс и Дж. Элиот Б. Мосс Сборка мусора и локальная переменная — точность типов и живость в виртуальных машинах Java.Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[2]Агесен, Оле, Дэвид Детлефс, Алекс Гартуэйт, Росс Книппель, Ю. С. Рамакришна и Дерек Уайт Эффективная метаблокировка для реализации вездесущей синхронизации.Материалы OOPSLA ’99, ACM, 1999.
[3] Arora, Nimar, Robert D. Blumofe, and C. Greg Plaxton. Thread Scheduling for Multiprogrammed Multiprocessors. In Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Пуэрто Валларта, Мексика, 28 июня — 2 июля 1998 г.
[4] Blumofe, Robert D. and Dionisios Papadopoulos. Hood: библиотека потоков пользовательского уровня для мультипрограммных мультипроцессоров. Technical Report, University of Texas at Austin, 1999.
[5]Фриго, Маттео, Чарльз Лейзерсон и Кит Рэндалл Реализация многопоточного языка Cilk-5.Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1998.
[6] Gosling, James, Bill Joy, and Guy Steele. The Java Language Specification, Аддисон-Уэсли, 1996.
[7] Lea, Doug. Concurrent Programming in Java, second edition, Аддисон-Уэсли, 1999.
[8]Ловенталь, Дэвид К., Винсент В. Фри и Грегори Р. Эндрюс Эффективный мелкозернистый параллелизм на машинах с общей памятью.Параллелизм — практика и опыт, 10, 3:157-173, 1998.
[9] Simpson, David, and F. Warren Burton. Space efficient execution of deterministic parallel programs. IEEE Transactions on Software Engineering, December, 1999.
[10] Taura, Kenjiro, Kunio Tabata, and Akinori Yonezawa. "Stackthreads/MP: Integrating Futures into Calling Standards." In Proceedings of ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming (PPoPP), 1999.