Модель Вилкового З’єднання в Java™ SE

Original: http://coopsoft.com/ar/ForkJoinArticle.html

Вилкове з’єднання для повсякденних, багатоядерных додатків Java ™

Техніка розгалуження або поділу навантаження на кілька завдань для паралельної обробки і приєднання результататів використовується у багаточисленних наукових додатках з великою кількістю обчислень. Багато інших додатків можуть отримати вигоду з моделі вилочного з’єднання, якщо не використовувати його з боку наукового підходу.

Ця стаття описує “приголомшливо паралельний” підхід вилочного з’єднання, який добре працює з повсякденними, багатоядерними додатками Java ™ SE, ME, а також Android. ™ (3000 слів)

Edward Harned ( eh at coopsoft dot com)
Старший розробник, Cooperative Software Systems, Inc.
Лютий, 2010 [оновлено у червні 2013]

Що таке вилкове з’єднання?

Уявіть собі розвилку, де кожен шлях в кінцевому підсумку один до одного в одному місці приєднується.

Вилкове з’єднання розриває додаток на кілька частин для паралельної обробки і врешті приєднує результати.

Малюнок 1: Структура вилкового з’єднання

Скажімо, у нас є масив однієї тисячі чисел. Нам потрібно виконати обчислення по кожному з них і додати підсумок.

Лістинг 1: Обробка масивів

for (int i = 0; i < 1000; i++) {
     total += doProcedure(array[i]);
}

Якщо кожне обчислення вимагає одну секунду (фізичний час), тоді нам знадобиться тисяча секунд (більше 16½ хвилин) для завершення завдання.

Вилкове з’єднання може:

  • розділити (розгалузившись) великий масив на 10 масивів по 100 елементів кожний,
  • обробити кожен масив на окремому ЦП,
  • об’єднати результати після завершення.

На все це піде сто секунд (трохи більше 1 ½ хвилини), одна десята від початкового часу. Чим більше доступних ЦП, тим швидше виводиться результат.

От і все, що являють собою наукові обчислення – одночасна обробка величезного обсягу даних на всіх можливих доступних центральних процесорах. Ця абстракція нагадує стандартну наукову модель – «Розділяй і володарюй».

«Розділяй і володарюй» – це природна парадигма паралельних алгоритмів. Після поділу завдання на дві і більше підзадачі, метод вирішує підзадачі паралельно. Як правило, підзадачі вирішуються рекурсивно і, таким чином, наступний крок ділить ще на підзадачі для вирішення їх паралельно.

Малюнок 2: Розділяй і-володарюй

Проблеми, що виникають під час використання наукової моделі вилочного з’єднання в повсякденних додатках.

У створенні завдань проблеми немає; це тільки об’єкти. Проблема у великій кількості потоків, що обробляють задачі, коли таким задачам потрібні:

Підключення
Для доступу до віддалених службам (СУБД, повідомлення, і багато інших) потрібне підключення. Як правило, віддалені служби використовують потік для обробки підключення, на що потрібно пам’ять, перемикання контексту, синхронізація і координація. Чим більше підключень до службі, тим більше ресурсів необхідно, і тим менше підключень доступно для інших завдань у віртуальній машині Java. Це впливає на кожного користувача.

Блокування
Блокування – це вбивці високої продуктивності. Мертві / живі блокування, інверсія пріоритетів, зависання, супровід і витрати ресурсів (що йде в геометричній прогресії з довжиною переліку адрес завдань) виникають під час використання блокувань.

Семафори
Чим більше потоків запитують дозвіл одночасно, тим більше потоків, яким необхідно чекати доступності дозволу. Це викликає всі проблеми, існуючі під час використання блокувань.

Когерентність кеша
Коли кілька процесорів звертаються / оновлюють ту ж змінну всередині рядка кеша (блок даних, скопійованих з основної пам’яті, що містить безліч полів), блок пам’яті може призвести до анулювання рядка кеша. Це не тільки сповільнює додатки, але також впливає і на інші.

Розширена пам’ять
Чим більше об’єктів або чим об’єкти більше, тим більше потрібно пам’яті. Чим активніше потоки, обробні завдання, тим більше пам’яті використовується. Природно, завдання, що вимагають багато пам’яті, повинні регулюватися.

Необхідність грати за правилами
Ваше додаток може бути не єдиним, працюючим на комп’ютері. Коли один додаток захоплює всі ресурси, кожен це відчує. Грати за правилами з іншими йде корінням до того, що ми всі дізналися в дитинстві. Та ж справедливість застосовується і для розробки програмного забезпечення, яке не працює як окремий додаток.

Ідеєю багатоядерних розробок служить привести змагання завдань, що конкурують за ті ж ресурси, до мінімуму.

Якщо парадигма динамічної декомпозиції «розділяй і володарюй» відповідає вашим потребам, то прочитайте цю статтю про високу продуктивність DSE версії Tymeac. В іншому випадку Структура функціонального розгалуження вам на допомогу.

Структура функціонального розгалуження

Java ™ SE / ME багатоядерні додатки, а також Android- ™ додатки, які не можуть використовувати модель «розділяй і володарюй”, не обробляють великі масиви чисел, або не мають обчислювальну інтенсивну структуру, потребують структурі функціонального розгалуження для розпаралелювання додатків. Зокрема, вони повинні розгалузившись свою роботу на функціональні компоненти, а не розбивати масив на однакові підзадачі.

Малюнок 3: Структура функціонального розгалуження

Структура функціонального розгалуження має дві властивості. Вона повинна:

  • Обмежити змагання.
  • Бути простою у використанні або надзвичайно паралельної.

Обмеження змагання

Утримання числа активних конкуруючих потоків до абсолютного мінімуму має першорядне значення. Найпростіший спосіб обмежити потокове змагання – це використовувати порогові значення для кожного пулу потоків, обслуговуючого чергу завдань. Перегляньте цю статтю про Високопродуктивних пріоритетних чергах в Java SE як приклад того, як за допомогою списків очікування можна зберегти потокові ресурси.

Повторне використання ресурсів, а не придбання нових копій, перемагає в будь-якому випадку. Ми повинні враховувати не тільки код завдання, а й код управління ресурсами.

Візьмемо, приміром, задачу запитуючу доступ до бази даних, що вимагає [java.sql.] Оператор. При використанні черги запитів, код задачі може розділити той же оператор на багато звернень, а не запитувати новий оператор для кожного доступу. Загальне використання оператора неабияк економить на витратах ресурсів і обмежує змагання в коді управління.

Що значить надзвичайно паралельний?

Надзвичайно паралельні алгоритми – це такі, які можуть вирішувати багато подібних, але незалежних завдань одночасно з малою необхідністю координації між завданнями. Ці види проблем так легко распаралелені, що “зі збентеженням” варто говорити, як просто задіяти ефективно процесори.

Надзвичайно паралельне рішення може легко виконати розгалуження на повністю незалежні компоненти, що виконуються на окремому процесорі кожен.

Малюнок 4: Надзвичайно паралельний

Наприклад:
Припустимо, бізнес вимагає автоматизованої системи котируваної ціни. Щоб розробити кошторис, система потребує даних про базову ціну продукту (база даних ціни), знижці клієнта на продукти і відвантаження (база даних клієнтів), про основні транспортних витратах (база даних вантажовідправника).

Традиційно, програма звертається до кожної базі даних послідовно, чекаючи кожного доступу для завершення процесу до переходу до наступного запитом доступу.

У паралельній системі, програма розгалужує () запит в три черги, кожна обслуговується пулом потоку, чекає завершення останнього запиту доступу і об’єднує () результати разом.

Малюнок 5: Котирування ціни

Вищевказана котирування цін – це приклад синхронного запиту, де викликає оператор чекає завершення. Це тільки маленький крок вперед, щоб додати підтримку для асинхронного або автономного запиту, де викликає оператор не чекає завершення.

Є безліч ситуацій, де бажано виконати розгалуження роботи:

  • Візьміть ігровий додаток, в якому ми можемо розгалузившись подія на окремі компоненти. Перевага тут – азарт; Чим більше сегментів подій відбуваються одночасно, тим цікавіше гра.
  • Візьміть додаток з кількома анімаціями, де ми можемо розгалузившись кожну анімацію для роботи на своєму власному процесорі.
  • Візьміть операцію обробки зображень, де кожен піксель в зображенні вимагає звернути свій колір. Структура може легко розподілити дані зображення для безлічі завдань, які будуть працювати незалежно один від одного.
  • Візьміть фінансова установа, де переоцінка портфеля включає в себе компоненти, які взаємодіють з різними ринками по всьому світу.
  • Візьміть медичний додаток, де різні тести – це компоненти в діагностиці.

Це спроба побачити яке додаток не може використовувати розпаралелювання з структурою функціонального розгалуження.

Як ця структура виглядає в додатку Java ™?

Для структури розгалуження запиту на його функціональні компоненти необхідна:

Інформація про компонентах (чергах) для кожної операції запиту (функції). Простий клас, що містить ім’я строковой функції і список відповідної черги є основним у Java ™ програмуванні.

Лістинг 2: Клас функції

public class Function {

private String name; // ім’я функції

private Queue[] que; // Черги для цього класу }

Помістіть запит (містить вхідні об’єкти) в кожну з черг, повертаючи масив об’єктів зухвалому оператору або ігноруючи повертані об’єкти.

Лістинг 3: Введення в чергу

public Object[] fork(Queue[] que, Object request) {

      Object[] return_obj = new Object[] {null, null, null};

      for (int i = 0; i < que.length; i++) {
           putInQueue(que[i], return_obj [i], request);
      }

       return return_obj;
}

Чекайте завершення / перерви або не чекайте.

Лістинг 4: Чекайте / Не чекайте

public boolean join(Object[] obj) {

    /* when all elements are non-null, return true
     * wait for a while
     * after an interval, return false
     */

  }

Поверніть результат зухвалому оператору або ігноруйте об’єкти.

Малюнок 6: Повернення зухвалому оператору

Для створення структури, нам необхідно:

1. підтримувати фактичний код завдання, який робить роботу

2. підтримувати список черг і функцій

3. підтримувати клас “запуску”, який завантажує черги і функції в пам’ять

(1) Код, який робить роботу, повинен виглядати так:

Лістинг 5: Робочий код

public static Object main(Object obj) {}

Основний () метод, який приймає об’єкт (введення від зухвалої оператора) і повертає об’єкт (результат роботи).

(2) Ми могли б підтримувати черги і функції як об’єкти в межах простого списку класу.

(3) При запуску можуть бути просто завантажені списки класів в пам’ять з новим (Списком класу) і почати потоки кожної черги.

Як простий виклик може виглядати:

Лістинг 6: Простий виклик

     Framework fw = new Framework();

    // For each call:
    Function
func = fw.getFunction(name);
    Object[] back =
func.fork(request};

Framework fw = new Framework();// For each call:
Function func = fw.getFunction(name);
Object[] back = func.fork(request};

Структуру дуже легко використовувати, до збентеження легко.

Підсумок

До цього моменту ми бачили, як розгалуження запиту на його функціональні компоненти може працювати в якості вбудованої частини однієї програми (в тому ж JVM.) Для практичності, ми також повинні зробити структуру доступною іншими віртуальних машинах Java. Просто, він повинен підтримувати багато викликів користувачів одночасно в якості сервера.

Зробити сервер

Які зміни ми повинні зробити, щоб налагодити цю просту структуру в якості сервера?

1. Ми повинні відокремити викликає оператора від роботи.

2. Ми повинні забезпечити відновлення після помилок.

3. Ми повинні підтримувати структуру в якості віддаленого об’єкта.

4. Ми повинні забезпечити безпеку.

5. Ми повинні забезпечити адміністративну функціональність для управління сервером.

Відділення
По-перше потрібно відокремити посередницький запит (це метод вище розгалуження ()) від фактичної обробки. Ми повинні відокремити, але стежити за кожним запитом в унікальному об’єкті.

Лістинг 7: Запит об’єкта

private long unique_id; // унікальна ідентифікація цього запиту
private Object input; // вступне посилання, якщо таке є
private boolean type; // тип запиту вірно=sync не вірно=async
private Object[] output // об’єкти виведення з завдання
private AtomicInteger next_output; // додати індекс до елементу вище
private Queue[] que_names; // список всіх черг у функції
private Queue agent; // майбутня чергу, якщо така є
private AtomicInteger nbr_remaining; // черги, що залишилися для обробки
private int wait_time; // макс час очікування для запиту sync

Що означає поле “агент?”

Агент
Синхронний запит повертає масив об’єктів з обробки зухвалому оператору. Що структурі робити з масивом об’єктів, які повернулися з асинхронного запиту? Структура опціонально розташує масив об’єктів (як введення) в нової черги для обробки за допомогою агента. Таким чином, агент діятиме залежно від статусу завершення попереднього обробки.

Наприклад:
Функція створює котирування ціни і відправляє її користувачеві у вигляді асинхронного запиту.

1. Зухвалий оператор використовує асинхронний метод розгалуження ().

2. Структура розгалужує запит за своїми відповідним черг.

3. Коли закінчується остання Черга, структура передає повернутий масив об’єктів агенту, поставивши запит в чергу, зазначену як “агент”.

4. Агент відправляє нерозділене лист

Виправлення помилок
Друга зміна додає виправлення помилок, знак професіоналізму.

Що може піти тут не так? “Все, що може піти не так, піде не так.” Закон Мерфі.

Відновлення
Може виникнути помилка розгалуження. Обмежена Черга може бути повною або чергу може бути відключена (подробней нижче). Відновлення після помилок має повернути всі черги, які розгалузилися успішно і проінформувати викликає оператора про проблему. Наприклад:

  • У нас є три черги (A, B, C) у функції.
  • Черги А і Б успішно отримати запит.
  • Черги С не вдається отримати запит, тому що черга заповнена.
  • Тепер ми йдемо у зворотному напрямку, намагаючись витягнути запит з усіх черг, розгалужених успішно, і заощадити час обробки несправних запитів.

Виняток / Помилка
У нас може виникнути виключення / помилка в робочому коді завдання. Якщо він раз вийшов з ладу, найвірогідніше, це повториться знову. Тому, бажано, відключити черзі до тих пір, поки розробник не вирішить проблему. Коли код завдання чистий, ми не хочемо, щоб падав сервер. Ми хочемо повідомити сервер, що ми маємо нову копію коду завдань, що чисте, і ми хочемо включити черги.

Зупинка
Може статися в асинхронному запиті, і називається зупинкою (синхронні запити припинені, і можуть очиститися з системи). Оскільки функції не можуть завершитися, поки не закінчаться всі Черги, ми повинні помістити зайшли в безвихідь запити в Завислий Список. Коли черга виправлена, ми можемо заново запустити обробку з завислого списку.

Утруднення потоку
Блок потоку може виникнути назавжди на зовнішній ресурс або перейти в нескінченний цикл. У кожному разі, за часом події в житті потоку, структура може визнати цю ситуацію і викреслити потік, замінивши його на новий.

Викреслення є окремим питанням і вимагає обмеження потоку.
Ця стаття вводить в тему: Управління потоками в Java SE

Скасування
Ми можемо прописати зухвалому оператору бажання скасувати раніше поданий запит. Скасування схожа на тайм-аут помилки, але застосовна до обох синхронним і асинхронним запитам. Хоча і скасування запиту більш бажана, логіка для обробки скасування в багатокомпонентному запиті не для слабкодухих.

Моніторинг
Терміни марні, якщо модуль-демон потоку, контролюючий події, шукає реальні або потенційні проблеми.

Повідомлення
Жодна структура не може впоратися з будь-якою ситуацією; іноді необхідне втручання людини. Ми повинні повідомити адміністраторів, відправивши повідомлення будь-якими засобами, якими користується організація (миттєвих повідомлень, електронна пошта, або будь доморощені методи).

Віддалений об’єкт
Третя зміна – це підтримка структури в якості віддаленого об’єкта з додатковими активацією / деактивацією в цілях економії ресурсів.

Віддалене звернення до методів проходить у багатьох різновидах:

Основний

Фабрика користувальницького роз’єму (Custom Socket Factory)

Інтелектуальний процесор вводу-виводу

Стерпний об’єктний адаптер

Jini

Міжпроцесорная взаємодія

Ваша середа може складатися з хмари з окремими процесорами в різних місцях. Створення такої гнучкої структури має сенс.

Безпека
Четверта зміна – це безпека

Технологія безпеки Java ™ є частиною SE / ME платформ, це вимагає зв’язок сервера з класами безпеки для гнучкості.

Функції адміністратора
П’яте зміна – це додавання функції адміністратора.

Вхід в систему нудний і марний до того як щось піде не так.

Статистика є основою для аналізу і налаштуванням продуктивності.

Ми повинні забезпечити інтерфейсами внутрішню структуру, так щоб користувачі могли контролювати і управляти функціональністю. Це не дуже добре, якщо ніхто не знає, що інтерфейс робить. Як тільки люди дізнаються, що саме, вони, ймовірно, захочуть змінити його.

Важко написати структуру вилочного з’єднання, простий у використанні і ефективною для місцевих викликів. Роблячи те ж саме для доступу до мережі – це ціле захід.

Скільки займе часу побудувати такий сервер?

Близько 5-6 секунд. Стільки ж, скільки і розпакувати файл.

На щастя, є загальне призначення, структура вилочного сполуки, підтримуюча особливості, описані вище – для повсякденних, багатоядерних додатків в Java ™ SE, ME і Android- ™, доступних сьогодні. А так як структура може працювати як сервер RMI (стандартний / активується, IIOP і POA) він доступний для додатків Java EE ™.

Tymeac ™ для Java ™ SE / ME / Android ™ платформ – це підтримувані програмні проекти з відкритим вихідним кодом,

і ви можете завантажити останні версії на сайті.

Висновок

Структура вилочного з’єднання, розроблена для ресурсномістких груп, може не добре працювати для щоденного застосування.

Основна частина Java ™ багатоядерних додатків вимагає розгалуження роботи на функціональні компоненти за допомогою професійної класової структури, легкої у використанні, ефективною, і з відкритим вихідним кодом.

Посилання

Завантаження:

Завантажте останню версію SE Tymeac тут. З усією документацією, скриптами, класами і вихідним кодом.

Завантажте останню версію ME Tymeac тут. З усією документацією та вихідним кодом.

Завантажте останню версію AND Tymeac тут. З усією документацією і з усіма проектами затемнення.

Завантажте останню версію DSE Tymeac тут. Версія Розділяй і-Володарюй.

Статті:

Висока продуктивність версії Розділяй-і-Володарюй Tymeac – Завойовник вилочного з’єднання

Висока продуктивність Android- ™ версії Tymeac – Управління потоками в Android

Використання списків очікування для еффектівності- Висока продуктивність пріоритетних черг в Java SE

Java ™ SE потоковий контейнер – Управління потоками в Java SE

Інше:

Черга вилочного з’єднання, вики – http://en.wikipedia.org/wiki/Fork-join_queue

Закон Мерфі – http://en.wikipedia.org/wiki/Murphy%27s_law

ЦП кеш вікі – http://en.wikipedia.org/wiki/CPU_cache

Когерентність кеша, вики – http://en.wikipedia.org/wiki/Cache_coherence

Надзвичайна паралельність, вики – http://en.wikipedia.org/wiki/Embarrassingly_parallel

Про розробника

Edward Harned є розробником програмного забезпечення з досвідом більше тридцяти років. За першою він вів проекти в якості працівника в основних галузях промисловості, а потім працював в якості незалежного консультанта. Сьогодні, Ед старший розробник програмного забезпечення в Cooperative Software Systems, Inc., де протягом останніх дванадцяти років, використовує програмування на Java ™, в цілях застосування вилочного приєднання в широкому колі завдань.

© 2010 – 2011 E.P. Harned Всі права захищені