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

Найбільш поширеною технологією програмування для кластерних систем і паралельних комп'ютерів з розподіленою пам'яттю в даний час є технологія MPI. Основним способом взаємодії паралельних процесів в таких системах є передача повідомлень один одному. Це і відображено в назві даної технології - Message Passing Interface (інтерфейс передачі повідомлень). Стандарт MPI фіксує інтерфейс, який має дотримуватися як системою програмування на кожній обчислювальної платформі, так і користувачем при створенні своїх програм. MPI підтримує роботу з мовами Фортран і Сі. Повна версія інтерфейсу містить опис більше 125 процедур і функцій.

Інтерфейс MPI підтримує створення паралельних програм в стилі MIMD (Multiple Instruction Multiple Data), що має на увазі об'єднання процесів з різними вихідними текстами. Однак писати і налагоджувати такі програми дуже складно, тому на практиці програмісти, набагато частіше використовують SPMD-модель (Single Program Multiple Data) паралельного програмування, в рамках якої для всіх паралельних процесів використовується один і той же код. В даний час все більше і більше реалізацій MPI підтримують роботу з так званими "нитками".

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

Для локалізації взаємодії паралельних процесів програми можна створювати групи процесів, надаючи їм окрему середовище для спілкування - комунікатор. Склад утворених груп довільний. Групи можуть повністю збігатися, входити одна в іншу, не перетинатися або перетинатися частково. Процеси можуть взаємодіяти тільки всередині деякого комунікатора, повідомлення, відправлені в різних комунікаторах, не перетинаються і не заважають один одному. Комунікатори мають в мові Фортран тип INTEGER (в мові Сі - зумовлений тип MPI Comm).

1.1 Загальні питання розв'язку "великих задач"

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

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

1.2 Сучасні задачі науки і техніки, необхідні для розв'язку суперкомп'ютерних потужностей

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

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

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

- Передбачення погоди, клімату і глобальних змін в атмосфері;

- Науки про матеріали;

- Побудова напівпровідникових приладів;

- Надпровідність;

- Розробка фармацевтичних препаратів;

- Генетика людини;

- Астрономія;

- Транспортні задачі великої розмірності;

- Гідро і газодинаміка;

- Керований термоядерний синтез;

- Розвідка нафти і газу;

- Обчислювальні задачі наук про світовий океан;

- Розпізнавання і синтез мови, розпізнавання зображень.

Необхідно відзначити, що існують аргументи проти широкого практичного застосування паралельних обчислень:

1. Паралельні обчислювальні системи надмірно дороги. За підтверджується практикою законом Гроша, продуктивність комп'ютера зростає пропорційно квадрату його вартості; внаслідок набагато вигідніше отримати необхідну обчислювальну потужність придбанням одного продуктивного процесора, ніж використання декількох менш швидкодіючих процесорів.

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

2. При організації паралелізму надмірно швидко ростуть втрати продуктивності. За гіпотезою Мінського (Marvin Minsky) досягається при використанні паралельної системи прискорення обчислень пропорційно двійковому логарифму від числа процесорів (при 1000 процесорах можливе прискорення виявляється рівним всього 10).

Контраргумент. Наведена оцінка прискорення вірна для розпаралелювання певних алгоритмів. Однак існує велика кількість завдань, при паралельному вирішенні яких досягається близьке до 100% використанню всіх наявних процесорів паралельної обчислювальної системи.

3. Послідовні комп'ютери постійно удосконалюються. За широко відомому закону Мура складність послідовних мікропроцесорів зростає вдвічі кожні 18 місяців, тому необхідна продуктивність може бути досягнута і на "звичайних" послідовних комп'ютерах.

Контраргумент. Аналогічний розвиток властиво і паралельним системам.

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

Контраргумент. При реально наявному розмаїтті архітектур паралельних систем існують і певні "усталені" способи забезпечення паралелізму. Інваріантність створюваного програмного забезпечення забезпечується за допомогою використання стандартних програмних засобів підтримки паралельних обчислень (програмні бібліотеки PVM, MPI, DVM та ін.) PVM та MPI використовуються в суперкомп'ютерах Cray-T3.

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

6. Існує обмеження на прискорення обчислення при паралельній реалізації алгоритму в порівнянні з послідовною. Контраргумент. У самому справі, алгоритмів взагалі без (певної) частки послідовних обчислень не існує. Однак це суть властивість алгоритму і не має відношення до можливості паралельного розв'язання задачі взагалі. Необхідно навчитися застосовувати нові алгоритми, більш підходящі для вирішення завдань на паралельних системах. Таким чином, на кожне критичне міркування проти використання паралельних обчислювальних технологій знаходиться більш-менш істотний контраргумент.

1.3 Паралельна обробка даних

• Принципова можливість паралельної обробки

Практично всі розроблені до теперішнього часу алгоритми є послідовними. Наприклад, при обчисленні виразу a + b Ч c, спочатку необхідно виконати множення і тільки потім виконати додавання. Якщо в електронно-обчислювальних машин присутні вузли додавання і множення, які можуть працювати одночасно, то в даному випадку вузол складання буде простоювати в очікуванні завершення роботи вузла множення. Можна довести твердження, яке у тому, що можливо побудувати машину, яка заданий алгоритм буде обробляти паралельно. Можна побудувати m процесорів, які при одночасній роботі видають потрібний результат за один-єдиний такт роботи обчислювача.

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

Абстрактні моделі паралельних обрахунків

Модель паралельних обчислень забезпечує високорівневий підхід до визначення характеристик і порівнянні часу виконання різних програм, при цьому абстрагуються від апаратного забезпечення і деталей виконання. Першою важливою моделлю паралельних обчислень з'явилася машина з паралельним випадковим доступом (PRAM - Parallel Random Access Machine), яка забезпечує абстракцію машини з пам'яттю, що розділяється (PRAM є розширенням моделі послідовної машини з довільним доступом RAM - Random Access Machine). Модель BSP (Bulk Synchronous Parallel, масова синхронна паралельна) об'єднує абстракції як розділеної, так і розподіленої пам'яті. Вважається, що всі процесори виконують команди синхронно; у разі виконання однієї і тієї ж команди PRAM є абстрактною SIMD-машиною, (SIMD - Single Instruction stream / Multiple Data stream - одиночний потік команд поряд з множинним потоком даних), однак процесори можуть виконувати і різні команди. Основними командами є зчитування з пам'яті, запис в пам'ять і звичайні логічні і арифметичні операції.

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

Базова модель PRAM підтримує конкурентні (в даному контексті паралельні) зчитування та запис. Відомі підмоделі PRAM, що враховують правила, що дозволяють уникнути конфліктних ситуацій при одночасному зверненні декількох процесорів до загальної пам'яті. Моделювати схеми з функціональних елементів за допомогою паралельних машин з довільним доступом (PRAM) дозволяє теорема Брента. В якості функціональних елементів можуть виступати як 4 основних (здійснюють логічні операції NOT, AND, OR, XOR - заперечення, логічне І, логічне АБО і виключає АБО відповідно), більш складні NAND і NOR (І-НЕ і АБО-НЕ), так і будь-якої складності.

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

Наведення результат моделювання схеми розміром (загальна кількість процесорів) n = 15 при глибині схеми (максимальне число елементів на кожному з рівнів глибини) d = 5 із кількістю процесорів p = 2 (одночасно модельований елементи об'єднані в групи прямокутними областями, причому для кожної групи зазначений крок, на якому моделюються її елементи; моделювання відбувається послідовно зверху вниз у порядку зростання глибини, на кожній глибині по р штук за раз). Згідно теореми Брента моделювання такої схеми займе не більше ceil (15/2 +1) = 9 кроків.

• Способи паралельної обробки даних, похибки обчислень

Можливі наступні режими виконання незалежних частин програми:

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

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

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

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

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

Прискорення обчислень досягається за рахунок використання всіх ступенів конвеєра для потокової обробки даних (дані потоком надходять на вхід конвеєра і послідовно обробляються на всіх щаблях). Конвеєри можуть бути скалярними або векторними пристроями (різниця полягає лише в тому, що в останньому випадку можуть бути використані обробні вектори команди). У разі довжини конвеєра l час обробки n незалежних операцій складе l + n-1 (кожен ступінь спрацьовує за одиницю часу). При використанні такого пристрою для обробки єдиною порції вхідних даних буде потрібно час l Ч n і тільки для безлічі порцій отримаємо прискорення обчислень, близьке до l.

З рисунку 1.2 видно, що продуктивність E конвеєрного пристрою асимптомно зростає із збільшенням довжини n набору даних на його вході, прагнучи до теоретичного максимуму продуктивності 1 / ф

1.4 Поняття паралельного процесу і гранули розпаралелювання

Найбільш загальна схема виконання послідовних і паралельних обчислень моменти часу S і E - початок і кінець завдання відповідно.

Процесом називають певні послідовності команд, нарівні з іншими процесами претендують для свого виконання на використання процесора; команди (інструкції) всередині процесу виконуються послідовно, внутрішній паралелізм при цьому не враховують.

Характерна довжина послідовно виконується групи команд у кожному з паралельних процесів називається розміром гранули (зерна). У будь-якому випадку доцільно прагнути до "грубозернистий". Зазвичай розмір зерна (гранули) складає десятки-сотні тисяч машинних операцій (що на порядки перевищує типовий розмір оператора мов Fortran або C / C + +). В залежності від розмірів гранул говорять про дрібнозернистому і грубозернистому паралелізмі.

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

Для реальних завдань (традиційно) характерний розмір зерна розпаралелювання на кілька порядків перевищує характерний розмір оператора традиційної мови програмування (C / C + + або Fortran).

• 1.5 Взаємодія паралельних процесів, синхронізація процесів