Теория и практика Java: Часть 1. Разветвляемся

Научитесь использовать мелкозернистый детальный параллелизм с помощью схемы fork-join, ожидаемой в Java 7

Одно из дополнений к пакетам java.util.concurrent, ожидаемое в Java™, - это модель распараллеливания в стиле fork-join. Идея fork-join обспечивает естественный механизм разложения многих алгоритмов для эффективного использования аппаратного параллелизма.

В следующей части этой серии рассматриваются классы ParallelArray, которые упрощают операции параллельной сортировки и поиска в структурах данных, находящихся в памяти.

Брайан Гетц, главный консультант, Quiotix

Брайан Гетц (Brian Goetz) - консультант по ПО и последние 15 лет работал профессиональными разработчиком ПО. Сейчас он является главным консультантом в фирме Quiotix, занимающейся разработкой ПО и консалтингом и находящейся в Лос-Альтос, Калифорния. Следите за публикациями Брайана в популярных промышленных изданиях. Вы можете связаться с Брайаном по адресу brian@quiotix.com



27.10.2008

Аппаратные тенденции развивают идиомы программирования

Наши подходы к созданию программ определяются языками, библиотеками и моделями программирования. Алонзо Чёрч (Alonzo Church) показал в 1934 году, что все известные вычислительные системы эквивалентны по множеству программ, которые они могут представлять. Однако совокупность программ, разрабатываемых реальными программистами, формируется идиомами, которые позволяет выразить модель программирования, ведомую языками, библиотеками и системами.

В свою очередь, доминирующие в текущий момент аппаратные платформы формируют подход к созданию языков, библиотек и систем. С самого момента зарождения языка в Java была поддержка потоков и параллелизма; этот язык включает в себя такие примитивы синхронизации, как synchronized и volatile, а библиотека классов содержит классы наподобие Thread. Однако примитивы параллелизма, введенные в 1995 году, отражали реальность аппаратного обеспечения того времени: большинство доступных коммерческих систем вообще не предоставляли возможностей использования параллелизма, и даже наиболее дорогостоящие системы предоставляли такие возможности лишь в ограниченных масштабах. В те дни потоки использовались в основном, для выражения asynchrony, а не concurrency, и в результате, эти механизмы в целом отвечали требованиям времени.

Когда начался процесс удешевления многопроцессорных систем, от приложений стали требовать все большего использования предоставляемого системами аппаратного параллелизма. Тогда программисты обнаружили, что разрабатывать параллельные программы, использующие низкоуровневые примитивы, обеспечиваемые языком и библиотекой классов, сложно и чревато ошибками. В платформу Java 5 был добавлен пакет java.util.concurrent, предоставляющий набор полезных компонентов для построения параллельных приложений: параллельные коллекции, очереди, семафоры, защелки (latch), пулы потоков и т.д. Эти механизмы хорошо подходили к программам с довольно крупной гранулярностью задач: приложениям требовалось только разделить свою работу таким образом, чтобы число параллельных задач не было постоянно меньше (небольшого) числа имеющихся процессоров. Приложения, использующие в качестве единицы работы web-сервера (почтового сервера или сервера базы данных) обработку одного запроса, в целом удовлетворяли такому требованию, поэтому добавленные механизмы были достаточны для того, чтобы в достаточной степени использовать умеренно параллельное аппаратное обеспечение.

Перспективы аппаратных тенденций понятны: закон Мура будет выражаться не в увеличении тактовой частоты, а в росте количестве ядер на одной микросхеме. Легко представить, как можно занять десяток процессоров такими задачами, структурированными до уровня запросов пользователей, но этот метод не масштабируется на тысячи процессоров — трафик может экспоненциально увеличиться на короткие промежутки времени, но в конечном счете аппаратные тенденции одержат верх. Когда мы войдем в многоядерную эру, нам потребуется найти мелкогранулярный параллелизм, иначе риск простаивания процессоров будет даже тогда, когда необходимо выполнить огромный объем работы! По мере изменения доминирующей аппаратной платформы, должна соответственно изменяться и программная платформа. С этой целью в Java 7 будет включена система представления определенного класса мелкозернистых параллельных алгоритмов: модель fork-join framework.

Мелкозернистый параллелизм

Сегодня в большинстве серверных приложений в качестве единицы работы используется обработка запроса пользователя. Обычно в серверных приложениях работает гораздо больше параллельных потоков (запросов), чем имеется процессоров. Причина этого в том, что обработка запроса, как правило, включает в себя значительное количество операций ввода-вывода, для которых не требуется много процессорного времени. (Все сетевые серверные приложения производят много операций ввода-вывода через сокеты, поскольку запросы поступают через сокеты; многие производят еще и довольно много дисковых операций ввода-вывода (или операций с базами данных). Если в каждой задаче 90 процентов времени тратится на ожидание завершения операций ввода-вывода, потребуется в 10 раз больше параллельных задач, чтобы полностью использовать все процессоры. По мере возрастания числа процессоров может возникнуть нехватка параллельных запросов для загрузки всех процессоров. Тем не менее параллелизм можно использовать для улучшения еще одного показателя производительности: количества времени, в течение которого пользователь ожидает получения ответа.

В качестве примера типичного сетевого серверного приложения рассмотрим сервер базы данных. Когда запрос поступает на сервер базы данных, он проходит целый ряд шагов. Сначала делается грамматический разбор SQL-предложения и проверка. Потом необходимо выбрать план запроса: в случае сложных запросов сервер баз данных может делать оценку множества различных планов для сведения к минимуму ожидаемого числа операций ввода-вывода. Поиск плана запроса может являться задачей с большой загрузкой процессора; с какого-то момента увеличение числа рассматриваемых предполагаемых планов будет давать больше издержек, чем выгод, однако оценка слишком малого числа вариантов почти наверняка приведет к большому количеству ненужных операций ввода-вывода. После получения необходимых данных с диска может потребоваться дополнительная обработка итогового набора данных: запрос может содержать агрегатные функции, например, SUM или AVERAGE, или может потребоваться сортировка набора данных. Затем результат должен быть преобразован в требуемый формат и возвращен тому, кто сформировал запрос.

Подобно большинству серверных запросов, обработка SQL-запроса порождает смесь расчетов и операций ввода-вывода. Никакой дополнительной мощностью процессора нельзя уменьшить время, требуемое для завершения операций ввода-вывода (хотя можно использовать дополнительную memory для уменьшения числа операций ввода-вывода за счет кэширования результатов предыдущих операций), но можно путем распараллеливания сократить количество времени, требуемое для интенсивно использующих процессор этапов обработки запроса (таких как оценка плана и сортировка). На этапе предварительной оценки различные планы запроса могут оцениваться параллельно; при сортировке наборов данных большие наборы данных могут быть разбиты на меньшие, индивидуально отсортированы параллельно друг другу, а затем объединены. Такой подход улучшает восприятие пользователем производительности сервера (даже если в сумме может потребоваться больше работы для обслуживания запроса), так как результаты выдаются быстрее.

Разделяй и властвуй

Примером алгоритма разделяй и властвуй является сортировка слиянием, когда задача рекурсивно разбивается на подзадачи, а решения подзадач объединяются для получения окончательного результата. Алгоритмы «разделяй и властвуй» часто оказываются полезными в последовательных системах, но могут стать еще более эффективными в параллельных системах, потому что подзадачи зачастую могут решаться параллельно.

Типичный параллельный алгоритм «разделяй и властвуй» имеет вид, приведенный в листинге 1:

Листинг 1. Псевдокод для обобщенного параллельного алгоритма «разделяй и властвуй»
// PSEUDOCODE
Result solve(Problem problem) { 
    if (problem.size < SEQUENTIAL_THRESHOLD)
        return solveSequentially(problem);
    else {
        Result left, right;
        INVOKE-IN-PARALLEL { 
            left = solve(extractLeftHalf(problem));
            right = solve(extractRightHalf(problem));
        }
        return combine(left, right);
    }
}

Первое, что выполняет параллельный алгоритм «разделяй и властвуй», - это оценка: не является ли задача настолько малой, что последовательное решение будет быстрее? Обычно это делается путем сравнения размера задачи с некоторым пороговым значением. Если задача достаточно велика, чтобы имело смысл ее распараллеливать, то она разделяется на две или более подзадач, и алгоритм рекурсивно запускает себя параллельно на подзадачах, ожидает результатов выполнения этих подзадач, а затем объединяет результаты. Идеальным порогом выбора между последовательным и параллельным выполнением является функция стоимости координирования параллельных задач. Если стоимость координирования нулевая, то чем больше число мелкозернистых задач, тем лучше будет параллелизм; чем ниже стоимость согласования, тем меньше может быть зернистость, прежде чем потребуется переключиться на последовательный метод.

Fork-join

В примере из листинга 1 используется вымышленная операция INVOKE-IN-PARALLEL; она работает таким образом, что текущая задача приостанавливается, две подзадачи выполняются параллельно, а текущая задача ждет их завершения. Затем результаты этих двух подзадач можно объединить. Этот вид разложения на параллельные задачи часто называется fork-join, потому что выполнение задачи ответвляет (запускает) множество подзадач, а затем соединяет их (ожидает завершения).

В листинге 2 показан пример задачи, пригодной для решения методом fork-join: поиск максимального элемента в большом массиве. Конечно, это очень простой пример, но метод fork-join пригоден для большого числа задач поиска, сортировки и анализа данных.

Листинг 2. Выбор максимального элемента из большого массива
public class SelectMaxProblem {
    private final int[] numbers;
    private final int start;
    private final int end;
    public final int size;

    // функция-конструктор пропущена 

    public int solveSequentially() {
        int max = Integer.MIN_VALUE;
        for (int i=start; i<end; i++) {
            int n = numbers[i];
            if (n > max)
                max = n;
        }
        return max;
    }

    public SelectMaxProblem subproblem(int subStart, int subEnd) {
        return new SelectMaxProblem(numbers, start + subStart, 
                                    start + subEnd);
    }
}

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

Листинг 3 иллюстрирует решение SelectMaxProblem с помощью пакета fork-join, который планируется включить в Java 7. Этот пакет — публичная разработка JSR 166 Expert Group под названием jsr166y, и его можно загрузить отдельно и использовать с Java 6 и выше (он будет находиться в пакете java.util.concurrent.forkjoin.) Операция invoke-in-parallel осуществляется методом coInvoke() который одновременно запускает множество действий и ждет их завершения. ForkJoinExecutor подобен Executor, так как он предназначен для запуска задач, однако он в большей степени предназначен для требующих интенсивных расчетов задач, которые не блокируются, исключая случай ожидания завершения другой задачи, обрабатываемой этим же ForkJoinExecutor.

Модель fork-join поддерживает несколько стилей ForkJoinTasks, включая стили, требующие явного завершения и выполняющиеся циклично. Класс RecursiveAction, используемый здесь, напрямую поддерживает стиль параллельного рекурсивного разложения для задач, не возвращающих результат; класс RecursiveTask делает то же самое для возвращающих результат задач. (Для задач fork-join есть еще классы CyclicAction, AsyncAction, и LinkedAsyncAction; подробности об их использовании см. в Javadoc.)

Листинг 3. Решение задачи выбора максимума с помощи модели fork-join
public class MaxWithFJ extends RecursiveAction {
    private final int threshold;
    private final SelectMaxProblem problem;
    public int result;

    public MaxWithFJ(SelectMaxProblem problem, int threshold) {
        this.problem = problem;
        this.threshold = threshold;
    }

    protected void compute() {
        if (problem.size < threshold)
            result = problem.solveSequentially();
        else {
            int midpoint = problem.size / 2;
            MaxWithFJ left = new MaxWithFJ(problem.subproblem(0, midpoint), threshold);
            MaxWithFJ right = new MaxWithFJ(problem.subproblem(midpoint + 
              1, problem.size), threshold);
            coInvoke(left, right);
            result = Math.max(left.result, right.result);
        }
    }

    public static void main(String[] args) {
        SelectMaxProblem problem = ...
        int threshold = ...
        int nThreads = ...
        MaxWithFJ mfj = new MaxWithFJ(problem, threshold);
        ForkJoinExecutor fjPool = new ForkJoinPool(nThreads);

        fjPool.invoke(mfj);
        int result = mfj.result;
    }
}

В таблице 1 приводятся некоторые результаты оценки производительности нахождения максимального элемента в массиве из 500 000 элементов на различных системах и с различными порогами минимальной размерности задачи для разбиения. В большинстве прогонов число потоков пула fork-join равнялось числу доступных аппаратных потоков (число ядер, умноженное на число потоков одного ядра). Числа в таблице показывают ускорение параллельного варианта по сравнению с последовательным.

Таблица 1. Результаты запуска select-max на массиве из 500 тыс. элементов на различных системах

Порог=500 тыс.Порог=500 тыс.Порог=5 тыс.Порог=500Порог=-5
Pentium-4 HT (2 потока)1.01.071.02.82.2
Dual-Xeon HT (4 потока).883.023.22.22.43
8-процессорный Opteron (8 потоков)1.05.295.734.532.03
8-ядерный Niagara (32 потока).9810.4617.2115.346.49

Эти результаты выглядят вполне обнадеживающими в том смысле, что они показывают хорошие результаты в широком диапазоне параметров. Поэтому, если избегать совсем уж неподходящих для задачи или аппаратуры параметров, то можно получить хорошие результаты при минимуме настроек. Для процессоров с многопоточной технологией (CMT — chip multithreading) непонятно, каким должно быть оптимальное ускорение; очевидно, что технологии CMT, как, например, Hyperthreading, обеспечивают меньшую производительность, чем эквивалентное число настоящих ядер, но вот насколько меньшую — это зависит от большого числа факторов, включая количество непопаданий в кэш выполняемого кода.

Пороги (минимальная размерность задачи для разбиения) для перехода на последовательную обработку выбирались от 500тыс. (размер всего массива, фактическое отсутствие параллелизма) до 50. В данном случае последовательный порог 50 попадает далеко в область «смехотворно маленьких» значений, и результаты показывают, что с таким низким последовательным порогом доминируют накладные расходы, связанные с управлением задачами fork-join. Однако если избегать очень высоких и очень малых значений параметров, то можно получить хорошие результаты без дополнительной настройки. Выбор числа рабочих потоков равным Runtime.availableProcessors() в целом близок к оптимальным результатам, поскольку считается, что задачи, выполняемые в пулах fork-join, привязаны к процессорам, но с другой стороны, результаты не очень чувствительны к этому параметру, если избегать слишком больших или слишком малых размеров пула.

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

Анатомия модели fork-join

Модель fork-join, пример работы которой показан в листинге 3, может быть реализована многими способами. Например, можно использовать необработанные потоки: Thread.start() и Thread.join() обеспечивают всю необходимую функциональность. Однако этот подход может потребовать большего количества потоков, чем виртуальная машина может поддерживать. Для решения задачи размера N (в предположении очень маленького порога последовательной обработки) потребуется O(N) потоков (дерево задачи имеет глубину log2N, а двоичное дерево глубиной k имеет 2k узлов), и половина из них большую часть времени простоят в ожидании завершения подзадач. Потоки дорого создавать, и они используют много памяти, что делает этот подход недопустимым. (Этот подход сделать работающим, но для этого программу придется сильно усложнить и потребуется тщательная настройка всех параметров под размер задачи и оборудование).

Использование обычных пулов потоков для реализации fork-join также затруднено, потому что задачи с fork-join тратят большую часть своего времени на ожидание других задач. Такой режим может привести к вечной взаимной блокировке потоков, если толькоьно не подобрать тщатеетры, ограничив число создаваемых задач, или если сам пул неограничен. Обычные пулы потоков преднатаны на задачи, не зависящиех другот друга, а также они рможующиеся крупнозернистые задачи — решения, использующие fork-join, не дают ни того, ни другого. Мелкозернистые задачи в пулах обычных потоков также могут привести к чрезмерной конкуренции за очередь задач, разделенную между всеми потоками.

Захват работы

Схема с fork-join уменьшает состязание за очередь с помощью следующего метода, называемого захват работы (work stealing). Каждый рабочий поток имеет свою собственную рабочую очередь, которая реализована с помощью двусторонней очереди, deque. (В Java 6 к библиотеке классов добавлено несколько реализаций deque, в том числе ArrayDeque и LinkedBlockingDeque.) Когда задача порождает новый поток, она помещает его в начало своей собственной двусторонней очереди. Когда задача выполняет операцию присоединения к другой еще не завершенной задаче, то вместо того, чтобы перейти в состояние ожидания завершения намеченной задачи (как это было бы в Thread.join(), она извлекает еще одну задачу из начала своей очереди и выполняет ее. В случае, если очередь задач потока пуста, рабочий поток пытается захватить другую задачу с конца двухсторонней очереди другого потока.

Захват работы можно осуществить и со стандартными очередями, но использование двусторонней очереди имеет два важных преимущества по сравнению со стандартной очередью: уменьшение конкуренции и уменьшение захвата. Поскольку только рабочий поток имеет доступ к началу своей собственной двунаправленной очереди, никогда не бывает конкуренции за работу, находящуюся в начале очереди; а поскольку доступ к концу двухсторонней очереди осуществляется только при завершении работ потока, то также редко возникает состязание за конец очереди какого-либо потока. (Реализация deque, встроенной в модель fork-join, использует эти модели доступа для дальнейшего снижения стоимости координирования.) Такое уменьшение конкуренции значительно снижает стоимость синхронизации по сравнению с традиционным подходом на основе пула потоков. Кроме того, очередность задач по принципу «последний вошел, первый вышел» (LIFO), реализуемая в этом подходе, означает, что самые крупные задачи находятся в конце очереди, и, следовательно, когда другому потоку нужно захватить задачу, он захватывает большую задачу, которая может быть разложена на небольшие задачи, что снижает потребность в повторном захвате в ближайшем будущем. Таким образом, захват работы дает приемлемую балансировку нагрузки без центрального координирования и при минимальных затратах на синхронизацию.

Заключение

Принцип fork-join предоставляет переносимый подход реализации параллелизуемых алгоритмов, когда уровень параллелизма, предлагаемый целевой системой, неизвестен заранее. Все виды сортировки, поиска и численных алгоритмов поддаются распараллеливанию. (В будущем стандартные библиотечные механизмы, такие как Arrays.sort(), могут начать использовать модель fork-join, давая приложениям возможность частично использовать преимущества распараллеливания.) В условиях, когда число процессоров продолжает расти, нам нужно выявлять в наших программах еще больше параллелизма, чтобы эффективно использовать эти процессоры; распараллеливание действий с большой вычислительной нагрузкой, таких как сортировка, помогает программам использовать преимущества будущих аппаратных средств.

Ресурсы

Научиться

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


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

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=347970
ArticleTitle=Теория и практика Java: Часть 1. Разветвляемся
publish-date=10272008