Програмування паралельних процесів

Уявимо величину зсуву у вигляді двоїстого коду. Кількість ненульових позицій коду визначає кількість етапів в схемі реалізації операції циклічного зсуву. На кожному етапі виконується операція зсуву з величиною кроку, яка задається найстаршою ненульовою позицією значення (наприклад, за умови вихідної величини зсуву на першому етапі виконується зсув з кроком 4, на другому етапі крок зсуву дорівнює 1). Виконання кожного етапу (окрім зсуву з кроком 1) полягає в передачі даних по шляху, який включає дві лінії зв'язку. Як результат, верхня оцінка для тривалості виконання операції циклічного зсуву визначається співвідношенням

Рис. 5. Схема відображення гіперкуба на кільце (в кружках наведені номери процесорів гіперкуба)

Передача пакетів

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

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

Методи логічного зображення топології комунікаційного середовища

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

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

- ущільнення дуг (congestion), яке виражається як максимальна кількість дуг логічної топології, які відображаються в одну лінію передачі фізичної топології;

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

- збільшення вершин (expansion), яке обчислюється як відношення кількості вершин в логічній та фізичній топологіях.

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

Представлення кільцевої топології у вигляді гіперкуба

Встановлення відповідності між кільцевою топологією та гіперкубом можна виконати з використанням двійкового рефлексивного коду Грея (binary reflected Gray code), який визначається у відповідності з виразами:

,

де задає номер значення в коді Грея, а N є довжиною цього коду. Для ілюстрації на рис. 8.5. показано відображення кільцевої топології на гіперкуб для мережі з процесорів.

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

Відображення топології решітки на гіперкуб

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

.

де операція || означає конкатенацію кодів Грея.

Оцінка трудомісткості операцій передачі даних для кластерних систем

Для кластерних обчислювальних систем одним з широко застосовуваних способів побудови комунікаційного середовища є використання концентраторів (hub) чи (switch) для об'єднання процесорних вузлів кластера в єдину обчислювальну мережу. В цих випадках топологія мережі кластера представляє собою повний граф, в якому є певні обмеження на одночасність виконання комунікаційних операцій. Так, за умови використання концентраторів передача даних в кожний поточний момент може виконуватися тільки між двома процесорними вузлами; комунікатори можуть забезпечувати взаємодію декількох пар процесорів, що не перетинаються. Інший часто використовуваний напрямок при створенні кластерів полягає у використанні методу передачі пакетів (часто реалізується на основі стеку протоколів ТСР/ІР) в якості основного способу виконання комунікаційних операцій.

Якщо вибрати для подальшого аналізу кластери цього поширеного типу (топологія у вигляді повного графа, пакетний спосіб передачі повідомлень), то трудомісткість операції комунікації між двома процесорними вузлами можна оцінити у відповідності з виразом (модель А)

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

З врахуванням наведених зауважень, схема побудови часових оцінок може бути уточнена; в рамках нової розширеної моделі трудомісткість передачі даних між двома процесорами визначається у відповідності з такими виразами (модель В):

де є кількістю пакетів, на яку розбивається повідомлення, що передається, величина визначає максимальний розмір пакета який може бути доставлений в мережу (для операційної системи MS Windows в мережі Fast Ethernet =1500 байт), а є об'єм службових даних в кожному з пакетів, що пересилаються (для протоколу ТСР/ІР, ОС Windows в мережі Fast Ethernet =78 байт). В наведених співвідношеннях константа характеризує апаратну складову латентності і залежить від параметрів використовуваного мережевого обладнання, значення задає тривалість підготовки одного байта даних для передачі по мережі. Як результат, величина латентності

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

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

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

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

це модель С, запропонована Хокні (the Hockney model).

Размещено на Allbest.ru