10.3 Розпаралелювання програм

 

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

Розпаралелювання програм - це процес адаптації алгоритмів, записаних у вигляді програм, для їх ефективного виконання на обчислювальній системі паралельної архітектури. Полягає або в переписуванні програм на спеціальний мову, що описує паралелізм і зрозумілий трансляторам цільової обчислювальної системи, або до вставки спеціальної розмітки (наприклад, інструкцій MPICH / MPI).

Розпаралелювання може бути ручним, автоматизованим та напівавтоматизованим. При розпаралелюванні важливо враховувати не тільки формальний паралелізм структури алгоритму, але й те, що обмінні операції в паралельних ЕОМ відбуваються, як правило, значно повільніше арифметичних. З цим пов'язане існування левової частки накладних витрат на організацію паралелізму.

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

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

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

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