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

Ускорение сортировки и поиска с помощью классов ParallelArray в Java 7

Одно из дополнений к пакетам java.util.concurrent, ожидаемое в Java™ 7 — это библиотека для распараллеливания в стиле fork-join. В первой части этой серии автор Брайан Гетц показал, как fork-join предоставляет естественный механизм разложения многих алгоритмов для эффективного использования аппаратного параллелизма. В этой статье он рассмотрит классы ParallelArray, упрощающие операции параллельной сортировки и поиска в структурах данных, находящихся в памяти.

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

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



01.10.2009

В предыдущей части серии "Теория и практика Java" мы изучили библиотеку fork-join, которая будет добавлена к пакету java.util.concurrent в Java 7. Метод fork-join облегчает выражение параллельных механизмов «разделяй и властвуй», делая возможным эффективное выполнение программ на широком диапазоне аппаратных средств без изменения программы.

Чтобы по мере роста числа процессоров эффективно использовать имеющиеся аппаратные средства, нам нужно выявить и использовать мелкозернистый параллелизм в наших программах. В последние годы выбор крупнозернистых границ задачи (например, обработка одного запроса в web-приложении) и выполнение задач в пулах потоков обычно обеспечивали достаточный параллелизм для достижения приемлемого использования аппаратных средств. Но, чтобы двигаться вперед, нам нужно будет копать глубже, чтобы найти достаточно параллелизма для загрузки аппаратных средств. Одной из областей, созревших для распараллеливания, является сортировка и поиск в больших наборах данных. Такие задачи легко выразить с помощью fork-join, как было показано в предыдущей части. Но, поскольку эти задачи являются такими распространенными, библиотека классов предоставляет еще более легкий способ —ParallelArray.

Обзор: разложение задач с помощью fork-join

Fork-join воплощает метод «разделяй-и-властвуй»; возьмите задачу и рекурсивно разбивайте ее на подзадачи, пока эти подзадачи не станут настолько маленькими, что их эффективнее будет решить последовательно. Шаг рекурсии включает в себя разделение задачи на две или более подзадач, постановку подзадач в очередь на решение (шаг fork), ожидание результатов от подзадач (шаг join) и слияние результатов. Одним из примеров такого алгоритма является сортировка слиянием с помощью библиотеки fork-join, показанная в листинге 1:

Листинг 1. Сортировка слиянием с использованием библиотеки fork-join
public class MergeSort extends RecursiveAction {
    final int[] numbers;
    final int startPos, endPos;
    final int[] result;

    private void merge(MergeSort left, MergeSort right) {
        int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
        while (leftPos < leftSize && rightPos < rightSize)
            result[i++] = (left.result[leftPos] <= right.result[rightPos])
                    ? left.result[leftPos++]
                    : right.result[rightPos++];
        while (leftPos < leftSize)
            result[i++] = left.result[leftPos++];
        while (rightPos < rightSize)
            result[i++] = right.result[rightPos++];
    }

    public int size() {
        return endPos-startPos;
    }

    protected void compute() {
        if (size() < SEQUENTIAL_THRESHOLD) {
            System.arraycopy(numbers, startPos, result, 0, size());
            Arrays.sort(result, 0, size());
        }
        else {
            int midpoint = size() / 2;
            MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
            MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
            coInvoke(left, right);
            merge(left, right);
        }
    }
}

Сортировка слиянием по своей природе не является параллельным алгоритмом, поскольку она может быть выполнена последовательно, и очень популярна в случаях, когда набор данных слишком велик, чтобы уместиться в памяти, и потому его приходится сортировать по частям. Производительность сортировки слиянием в худшем и среднем случаях имеет порядок O(n log n). Но из-за того, что слияние трудно сделать на месте, потребности в памяти в общем случае гораздо больше, чем у алгоритмов сортировки на месте, таких как quicksort. Но поскольку сортировка подзадач может делаться параллельно, она распараллеливается лучше, чем quicksort.

При фиксированном числе процессоров распараллеливание все же не может превратить задачу O(n log n) в задачу O(n), но чем больше задача поддается распараллеливанию, тем коэффициент сокращения времени выполнения ближе к ncpus, — теоретическому значению для параллельной обработки. Уменьшение суммарного времени выполнения означает, что пользователь быстрее получает результат — даже если для параллельной работы требуется больше тактов ЦПУ, чем для последовательной.

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

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

Наиболее доступные источники мелкозернистого параллелизма в основных серверных приложениях — это сортировка, поиск, выборка и агрегирование в наборах данных. Каждая из этих задач легко может быть распараллелена с помощью метода «разделяй-и-властвуй» и легко может быть представлена в виде задачи для fork-join. Например, чтобы распараллелить нахождение среднего в большом наборе данных, можно рекурсивно разбить его на меньшие наборы данных — как делалось в сортировке слиянием — усреднить подмножества, а на шаге объединения просто вычислить взвешенное среднее по средним значениям для подмножеств.

ParallelArray

В случае задач сортировки и поиска библиотека fork-join предоставляет еще более простые средства выражения распараллеливаемых операций над наборами данных: классы ParallelArray. Идея состоит в том, что ParallelArray представляет коллекцию структурно подобных элементов данных, а методы ParallelArray используются для создания описания того, как нужно обработать данные. Затем это описание используется для фактического параллельного выполнения операций с массивом (при этом внутренняя работа делается с помощью механизма fork-join). Такой подход дает возможность декларативно определять операции выбора данных, преобразования и последующей обработки, а также позволяет среде построить приемлемый план параллельного выполнения подобно тому, как системы баз данных дают возможность определять операции с данными на SQL, скрывая механизм осуществления операций. Имеется несколько реализаций ParallelArray для различных типов и размеров данных, в том числе для массивов объектов и для массивов различных примитивов.

В листинге 2 приводится пример использования ParallelArray для подведения итогов по оценкам студентов, здесь иллюстрируются основные операции выборки, прогнозирования и агрегирования. Класс Student содержит информацию о студентах (имя, год выпуска, средний балл). Вспомогательный объект isSenior используется для выбора только студентов, заканчивающих учебу в этом году, а вспомогательный объект getGpa извлекает поле со средним баллом для данного студента. Выражение в начале листинга создает ParallelArray , представляющий набор студентов, а затем использует его для выбора лучшего балла по студентам, заканчивающим учебу в этом году.

Листинг 2. Использование ParallelArray для выборки, обработки и агрегирования данных
ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data);
double bestGpa = students.withFilter(isSenior)
                         .withMapping(selectGpa)
                         .max();

public class Student {
    String name;
    int graduationYear;
    double gpa;
}

static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() {
    public boolean op(Student s) {
        return s.graduationYear == Student.THIS_YEAR;
    }
};

static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() {
    public double op(Student student) {
        return student.gpa;
    }
};

Текст программы для выражения операций с параллельными массивами несколько обманчив. Методы withFilter() и withMapping() на самом деле не ищут и не преобразуют данные; они только настраивают параметры "запроса". Фактическая работа делается на последнем шаге, в данном случае в вызове max().

Основные операции, поддерживаемые ParallelArray:

  • Фильтрация: Выбор подмножества элементов, участвующих в расчете. В листинге 2 фильтр задан с помощью метода withFilter().
  • Применение: Применение процедуры к каждому выбранному элементу. В листинге 2 это не показывается, но метод apply() дает возможность выполнить действие для каждого выбранного элемента.
  • Преобразование: Преобразование выбранных элементов в другую форму (например, извлечение поля с данными из элемента). В примере это преобразование делается методом withMapping(), где мы преобразуем Studentв среднюю оценку студента (GPA). Результатом является массив ParallelArray, полученный на основе заданных выборки и преобразования.
  • Замещение: Создание нового параллельного массива путем замены каждого элемента другим, полученным из него. Этот способ похож на преобразование, но он производит новый ParallelArray, на котором могут выполняться следующие запросы. Частным случаем замещения является сортировка, где элементы замещаются другими элементами таким образом, что получившийся в результате массив отсортирован (для этого есть встроенный метод sort()). Другим частным случаем является метод cumulate(), который замещает каждый элемент текущим накопленным значением в соответствии с заданной операцией комбинирования. Замещение может также использоваться для комбинирования нескольких ParallelArray, например, создание ParallelArray, элементы которого являются значениями a[i]+b[i] для параллельных массивов a и b.
  • Агрегирование: Объединение всех значений в одно, например, вычисление суммы, среднего, минимума или максимума. В примере в листинге 2 используется метод max(). Встроенные методы агрегирования, например min(), sum() и max(), созданы с помощью более общего метода reduce().

Типичные операции агрегирования

В листинге 2мы смогли определить расчет самого высокого среднего балла любого студента, но, пожалуй, нам нужно немного другое — какой студент имеет самый высокий средний балл. Этот расчет может быть сделан с помощью двух вычислений (одно для вычисления самого высокого среднего балла, другое — для выбора студентов, имеющих этот балл), но ParallelArray предоставляет более простые средства получения такой популярной сводной статистики, как максимум, минимум, сумма, среднее и индекс максимального и минимального элементов. Метод summary() вычисляет эту сводную статистику в одной параллельной операции.

В листинге 3 показывается, как метод summary() вычисляет сводную статистику, в том числе индексы минимального и максимального элементов, что позволяет избежать необходимости нескольких проходов над данными:

Листинг 3. Определение студента с самым высоким средним баллом
SummaryStatistics summary = students.withFilter(isSenior)
                            .withMapping(selectGpa)
                            .summary();
System.out.println("Самый плохой студент: " + students.get(summary.minIndex()).name;
System.out.println("Средний балл: " + summary.getAverage();

Ограничения

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

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

Чтобы оценить эффективность ParallelArray, я написал простую программу, которая выполняет запрос для различных размеров массива и пулов fork-join. Результаты определялись на системе с процессором Core 2 Quad, работающей под Windows. В таблице 1 результаты представлены в виде полученного ускорения по отношению к базовому случаю (1000 студентов, один поток):

Таблица 1. Измерение производительности для запроса максимального среднего балла
center


Потоки


1248
Студенты10001.000.300.351.20
100002.112.311.021.62
1000009.995.283.635.53
100000039.3424.6720.9435.11
10000000340.25180.28160.21190.41


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

Связь с замыканиями

ParallelArray предлагает хороший способ декларативно определить фильтрацию, обработку и агрегатные операции на наборах данных, упрощая в то же время автоматическое распараллеливание. Однако, даже несмотря на то, что с помощью этого синтаксиса легче описать операции, чем с помощью непосредственно библиотеки fork-join, синтаксис все же несколько громоздок; каждый фильтр, преобразователь и редуктор обычно определяется как внутренний класс, поэтому простые запросы типа "найти самый высокий средний балл любого студента, заканчивающего учебу в этом году" все еще составляют порядка десятка строк текста программы. Одним из возможных добавлений к языку в Java 7 являются замыкания; одним из аргументов в пользу замыканий является то, что это делает более компактными небольшие куски текста программы — например, фильтры, преобразователи и редукторы в ParallelArray.

В листинге 4 показан запрос максимального среднего балла, переписанный с использованием BGGA-замыканий. (В версии ParallelArray , дополненной типами функций, тип параметра для withFilter() не Ops.Predicate<T>, а тип функции { T => boolean }.) Нотация замыканий убирает шаблон, связанный с внутренними классами, позволяя выразить требуемую операцию с данными более компактно (и, что еще важнее, более прямолинейно). Теперь текст уменьшился до трех строк, причем почти весь он выражает важные аспекты результата, который мы стараемся получить.

Листинг 4. Запись примера с вычислением максимального среднего балла с использованием замыканий
double bestGpa = students.withFilter({Student s => (s.graduationYear == THIS_YEAR) })
                         .withMapping({ Student s => s.gpa })
                         .max();

Заключение

По мере роста числа имеющихся процессоров нам нужно находить все более мелкозернистые источники параллелизма в наших программах. Одним из привлекательных кандидатов для этого являются агрегатные операции с данными — сортировка, поиск и подведение итогов. Библиотека fork-join, которая будет введена в JDK 7, предоставляет средства "переносимого выражения" некоторых классов распараллеливаемых алгоритмов, что позволяет эффективно исполнять одну и ту же программу на целом ряде аппаратных платформ. Компонент ParallelArray библиотеки fork-join позволяет еще больше облегчить выражение параллельных агрегатных операций, декларативно описывая операцию, которую нужно выполнить, и предоставляя ParallelArray определять, как это сделать эффективно.

Ресурсы

Научиться

Обсудить

Комментарии

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=432557
ArticleTitle=Теория и практика Java: Разветвляемся. Часть 2
publish-date=10012009