3.2 Топологія типу «Дерево»

Деревоподібна топологія (tree) – побудова мережі за схемою двійкового дерева, де кожен вузол більш високого рівня пов'язаний з двома вузлами наступного по порядку більш низького рівня. (Див. Додаток Б)

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

Таку мережу можна охарактеризувати наступними параметрами:

D = 2log2 [(N + 1) / 2]; (3.2)

де

d = 1 для крайових вузлів,

d = 2 для кореневого вузла

d = 3 для інших вузлів;

I = N-1;

В = 1.

Діаметр для двійкового дерева зростає пропорційно лише логарифму числа

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

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

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

Рис. 3.7 – Топологія «товстого» дерева

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

До переваг даної топології можна віднести те, що мережа з даною топологією легко збільшити і легко її контролювати (пошук обривів і несправностей).

Недоліками є те, що при виході з ладу батьківського вузла, вийдуть з ладу

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

4 Закон амдаля і його застосування при створенні комп’ютерних систем

4.1 Теоретичні відомості

Закон Амдаля  –  ілюструє обмеження зростання продуктивності обчислю-вальної системи зі збільшенням кількості обчислювачів. Амдал сформулював закон в 1967 році, виявивши просте по суті, але непереборне за змістом обмеження на зростання продуктивності при розпаралелюванні обчислень: «У разі, коли завдання розділяється на кілька частин, сумарний час її виконання на паралельній системі не може бути менше часу виконання самого довгого фрагмента». Згідно з цим законом, прискорення виконання програми за рахунок розпаралелювання її інструкцій на безлічі обчислювачів обмежена часом, необхідним для виконання її послідовних інструкцій.

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

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

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

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

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

Локальне розпаралелювання

Глобальне розпаралелювання

P1

P2

P1

Pn

…

…

Етапи обчислень

…

…

i-1

i

i+1

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

Рисунок 4.1 – Схеми паралельних алгоритмів

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

, (4.1)

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

Паралельна программа рішення складної задачі допускає подання у вигляді композиції

, (4.2)

У якій єi - я галузь програми, -n припустиме число галузей.

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

Наявність послідовних частин коду. Закон Амдаля і його наслідки.

Нехай f – це частка послідовних обчислень, 0<f<1. Максимальне прискорення , досяжне на обчислювальній системі зN процесорів, можна оцінити за допомо-гою наступної формули, закона Амдала

, (4.3)

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

, (4.4)

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

, (4.5)

тобто якщо, наприклад, необхідно на 10 процесорах дістати прискорення в 9 разів, то необхідно, щоб 99% коду виконувалося паралельно (f=1,2%).

Із закону Амдаля виходить висновок про те, що наявність навіть невеликих послідовних частин коду істотно знижує паралельну ефективність програми.