10.3.7 Зміна елементів даних

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

 

10.3.8 Область перекриття

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

 

 

Рисунок 10.8 – Область процесу перекриття

 

Елементи в тіньовій області повинні бути доступні для процесу в режимі «тільки читання». Такі тіньові області називаються областями перекриття. Локальний блок даних оточений областю перекриття ми будемо називати процесом даних. Треба зауважити, що процес даних не обов'язково повинен мати області перекриття однакової товщини по всіх напрямах. У деяких випадках область перекриття може бути відсутньою по одному, декількох чи всіх напрямках або мати різну товщину за різними напрямками. Також, форма області перекриття може відрізнятися у різних процесів. Товщина області перекриття для кожного процесу визначається особливостями обраного чисельного алгоритму.

 

10.3.9 Граничний обмін

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

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

 

 

Рисунок 10.9 – Процеси граничного обміну

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

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

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

Таким чином для процесів можна запропонувати наступний алгоритм виконання ітерацій:

1) Надсилаємо власні дані процесам, яким вони можуть знадобиться для проведення наступної ітерації.

2) Приймаємо дані від сусідніх процесів для заповнення власної області перекриття новими значеннями.

3) Виконуємо обробку даних.

Процес здійснення та прийому даних від інших процесів називається "граничний обмін".