Проблеми розробки паралельних додатків

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

Декомпозиція

Під декомпозицією розуміється розбиття задачі на відносно незалежні частини (підзадачі). Декомпозиція задачі може бути проведена кількома способами: за завданнями, за даними, з інформаційних потоків.
Декомпозиція за завданнями (функціональна декомпозиція) припускає присвоєння різним потокам різних функцій. Наприклад, додаток що виконує правку документа включає наступні функції: перевірка орфографії CheckSpelling, перевірка пунктуації CheckPuncto, форматування тексту у відповідність із вибраними стилями Format, підрахунок статистики по документу CalcStat, збереження змін у файлі SaveChanges і відсилання документа електронною поштою SendDoc.

Рисунок 1.1 — Функціональна декомпозиція

Функціональна декомпозиція розбиває роботу програми на під задачі таким чином, щоб кожна підзадача була пов'язана з окремою функцією. Але не всі операції можуть виконуватися паралельно. Наприклад, збереження документа і відсилання документа виконуються тільки після завершення всіх попередніх етапів. Форматування та збір статистики можуть виконуватися паралельно, але тільки після завершення перевірки орфографії та пунктуації.

Рисунок 1.2 — Розбиття функціональної декомпозиції

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

1. Робота з чорновим документом (орфографія і пунктуація):
   
2. Робота з виправленим документом (форматування і збір статистики);
   
3. Робота з готовим документом (збереження і відсилання);
   

При декомпозиції за даними кожна підзадача працює зі своїм фрагментом даних, виконуючи звістку перелік дій. У розглянутому прикладі декомпозиція за даними може застосовуватися до завдань, що допускають роботу з фрагментом документа. Таким чином, функції CheckSpelling, CheckPuncto, CalcStat, Format об'єднуються в одну підзадачу, але створюється кілька екземплярів цієї підзадачі, які паралельно працюють з різними фрагментами документа. Функції SaveChanges і SendDoc становлять окремі підзадачі, оскільки не можуть працювати з частиною документа.

Декомпозиція за даними

Рисунок 2.1 — Поділ масиву елементів може здійснюватися за рівним діапазонами індексу між потоками (range partition).

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

Рисунок 2.2 — Обчислювальне навантаження обробки i-елемента може залежати від індексу елемента.

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

Рисунок 2.3 — При динамічній декомпозиції кожен потік, який бере участь в обробці, звертається за блоком даних (порцією).

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

Масштабування підзадач

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

Проблема гонки даних

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

1. Кілька потоків працюють з ресурсом.
   
2. Кінцевий результат залежить від черговості виконання командних послідовностей різних потоків.
   

Для ілюстрації проблеми гонки даних розглянемо наступний фрагмент. Два потоки виводять на екран значення загальної змінної Msg.

// Код потоку №1
     Msg = “I’m thread one”;
     Console.WriteLine(“Thread #1: “ + Msg);
// Код потоку №2
     Msg = “I’m thread two”;
     Console.WriteLine(“Thread #2: “ + Msg);

Змінна Msg є спільною — зміна змінної в одному потоці буде видна в іншому потоці. При паралельній роботі потоків висновок визначається конкретною послідовністю виконання операторів.
Якщо оператори першого потоку виконуються до операторів другого потоку, тобто при послідовності (1) - (2) - (3) - (4), то ми отримуємо:

Thread #1: I’m thread one
Thread #2: I’m thread two

Якщо ж у виконання операторів одного потоку втрутяться оператори іншого потоку, наприклад, при послідовності (1) - (3) - (2) - (4), то отримаємо наступне:

Thread #1: I’m thread two
Thread #2: I’m thread two

Проблема гонки даних виникає не тільки при виконанні декількох операторів, але і при виконанні одного оператора. Розглянемо наступний випадок. Обидва потоки виконують один оператор над загальною змінної x типу int:
$x=x+5$ Даний оператор передбачає виконання таких дій:

• завантажити значення операндів у регістри процесора;
• здійснити підсумовування;
• записати результат за адресою змінної x.

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

Дія	Потік №1	Потік №2
Завантаження операндів	0	0
Обчислення	5	5
Запис результатів	5
Запис результатів		5
Значення змінної	5	5

Ще однією «пасткою» в багатопотокової обробці є робота з динамічними структурами даних (списки, словники). Додавання та видалення елементів у динамічні структури даних здійснюється за допомогою одного методу:

     list.Add(“New element”);
     dic.RemoveKey(“keyOne”);

Реалізація методів включає декілька дій. Наприклад, при додаванні елемента в список необхідно записати елемент за поточним індексом (вказівником) і зрушити індекс на наступну позицію. Для коректного здійснення додавання елемента одним потоком необхідно, щоб інші потоки дочекалися завершення маніпуляцій зі списком.

// Додавання елемента в масив за поточним індексом
     data[current_index] = new_value;
     current_index++;

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

// Загальна змінна
     bool b = false;
//Потік №1
     void f1()
          {
               DoSomeWork1();
               b = true;
          }
//Потік №2
     void f2()
          {
               DoSomeWork2();
               b = true;
          }
//Потік №3
     void f3()
          {
               while(!b) ;
               DoSomeWork3();
          }

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

Проблеми синхронізації

Рішення проблеми гонки даних вимагає застосування засобів синхронізації, що дозволяють забезпечити взаємно-винятковий доступ до критичної секції. Застосування синхронізації гарантує отримання коректних результатів, але знижує швидкодію програми. Чим більше розмір критичних секцій у додатку, тим більша частка послідовного виконання і нижча ефективність від розпаралелювання. Для підвищення швидкодії розмір критичної секції повинен бути гранично мінімальним — тільки ті оператори, послідовність яких не повинна перериватися іншим потоком.
У наступному фрагменті кожен потік зберігає в поділюваному масиві data дані з файлу. Для забезпечення узгодженого доступу до ресурсу використовуються засоби синхронізації.

// Потік №1
     <Вхід у критичну секцію>
     StreamReader sr = File.OpenText(“file” + ThreadNum);
     newValue = GetValue(sr);
     data[cur_index] = newValue;
     cur_index++;
     sr.Close();
     <Вихід із критичної секції>

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

// Потік №1
     StreamReader sr = File.OpenText(“file” + ThreadNum);
     newValue = GetValue(sr);
     <Вхід в критичну секцію>
     data[cur_index] = newValue;
     cur_index++;
     <Вихід із критичної секції>
     sr.Close();

Сучасні платформи для паралельного програмування, в тому числі і середовище Framework. NET, пропонують широкий вибір засобів синхронізації. У кожній задачі застосування того чи іншого інструмента синхронізації буде більш ефективним. Наприклад, для багатопотокового збільшення розділюваного лічильника можуть використовуватися засоби організації взаємно-виключного доступу (об'єкти Monitor, Mutex), сигнальні повідомлення (AutoResetEvent, ManualResetEventSlim), двійкові семафори (Semaphore). Але максимально ефективним буде використання неблокируючих атомарних операторів (Interlocked.Increment).
Для роботи з динамічними списками можна використовувати як звичайні колекції з тими чи іншими засобами синхронізації, так і конкурентні колекції з вбудованою неблокуючою синхронізацією.

Проблеми кешованої пам'яті

Наявність кешованої пам'яті збільшує швидкодію обробки даних, але ускладнює роботу системи при багатопотоковій обробці. Неоптимальна робота з кешованою пам'яттю може сильно знизити ефективність паралельної обробки.
Кеш-пам'ять кожного процесора (ядра процесора) наповнюється даними, необхідними для роботи потоку, що виконується на цьому процесорі. Якщо потоки працюють із загальними даними, то на апаратному рівні повинна забезпечуватися узгодженість вмісту кеш-пам'яті. Зміна загальної змінної в одному потоці, сигналізує про недійсність значення змінної, завантаженої в кеш-пам'ять іншого процесора. При цьому необхідно зберегти значення змінної в оперативній пам'яті й оновити кеш-пам'ять інших процесорів. Велика інтенсивність змін загальних змінних, які використовуються в декількох потоках, призводить до великого числа помилок кеш-пам'яті (кеш-промахи) і збільшенню накладних витрат, пов'язаних з оновленням кеш-пам'яті.
Поширеною проблемою кеш-пам'яті є так званий помилковий поділ даних (false sharing). Проблема пов'язана з тим, що потоки працюють з різними змінними, які в оперативній пам'яті розташовані фізично близько. Річ у тому, що в кеш-пам'ять завантажується не конкретна змінна, а блок пам'яті (рядок кешу), що містить необхідну змінну. Розмір рядка кешу може становити 64, 128, 512 байт. Якщо в одному рядку кешу розташовані кілька змінних, що використовуються в різних потоках, то в кеш-пам'ять кожного процесора буде завантажений один і той же рядок. При зміні в одному потоці своєї змінної, вміст кеш-пам'яті інших процесорів вважається недійсним і вимагає оновлення.
Як ілюстрацію проблеми помилкового поділу розглянемо наступний фрагмент. У програмі оголошена структура, яка містить кілька полів.

     struct data
          {
               int x;
               int y;
          }

Перший потік працює тільки з полем x, другий потік працює тільки з полем y. Таким чином, розділення даних і проблеми гонки даних між потоками немає. Але послідовне розташування в пам'яті структури data, призводить до того, що в кеш-пам'ять одного й іншого процесора завантажується рядок розміром 64 байт, що містить значення і поля x (4 байти), і поля y (4 байти). При зміні поля в одному потоці відбувається оновлення рядка кешу в іншому потоці.

// Потік №1
     for(int i=0; i<N; i++)
     data1.x++;
// Потік №2
     for(int i=0; i<N; i++)
     data1.y++;

Щоб уникнути послідовного розташування полів x і y в пам'яті, можна використовувати додаткові проміжні поля.
Інший підхід полягає в явному вирівнюванні полів в пам'яті за допомогою атрибута FieldOffsetAttribute, що визначений у просторі System.Runtime.InteropServices:

// Явне вирівнювання у пам'яті
     [StructLayout(LayoutKind.Explicit)]
     struct data
         {
              [FieldOffset(0)] public int x;
              [FieldOffset(64)] public int y;
         }

При досить великому значенні N, різниця у швидкодії коду з поділом кешу і без поділу може досягати 1.5–2 разів.
Все ж найефективнішим рішенням за незалежної обробки полів структури буде застосування локальних змінних усередині кожного потоку. Різниця у швидкодії може досягати декількох десятків.

Моделі паралельних додатків

Існують наступні поширені моделі паралельних додатків:

• модель делегування («керівник-робітник»);
• мережа з рівноправними вузлами;
• конвеєр;
• модель «виробник-споживач»

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

Модель	Опис
Модель делегування	Центральний потік ("керівний») створює «робочі» потоки і призначає кожному з них задачу. Керівний потік очікує завершення роботи потоків, збирає результати.
Модель з рівноправними вузлами	Всі потоки мають однаковий робочий статус.
Конвеєр	Конвеєрний підхід застосовується для поетапної обробки потоку вхідних даних.
Модель «виробник-споживач»	Окремий випадок конвеєра з одним виробником і одним споживачем.

Література

1. Ian Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995.
2. Корнєєв В.Д. "Паралельне програмування в МРІ". Друге видання, випр. Новосибірськ, 2002.
3. Бувайло Д.П., Толок В.А. "Розподілені обчислення". Навчальний посібник для студентів математичних спеціальностей, 2002.
4. А.А. Букатов, В.Н. Дацюк, А.И. Жегуло "Программирование многопроцессорных вычислительных систем".