Алгоритм додавання ряду чисел

Размещено на http://www.allbest.ru/

1. Класифікація багатопроцесорних систем з організації пам'яті

1.1 Векторно-конвеєрні комп'ютери

Конвеєрні функціональні пристрої і набір векторних команд - це дві особливості таких машин. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри, тобто команда виду A = B + C може означати складання двох масивів, а не двох чисел.

Як правило, кілька спеціальних векторно-конвеєрних процесорів (1-16) працюють одночасно над загальною пам'яттю (аналогічно SMP) у рамках багатопроцесорних конфігурацій. Кілька таких вузлів можуть бути об'єднані за допомогою комутатора (аналогічно MPP).

Характернимпредставникомданогонапрямкуєсімействовекторно-конвеєрнихкомп'ютерівCRAY, куди входять, наприклад, CRAYEL, CRAYJ90, CRAYT90 (у березні 2000 року американська компанія TERA перекупила підрозділ CRAY у компанії Silicon Graphics, Inc.).

1.2 Масивно-паралельні комп'ютери (MPP системи)

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

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

До даного класу можна віднести комп'ютери Intel Paragon, IBMSP1, Parsytec, якоюсь мірою IBM SP2 і CRAY T3D/T3, хоча в цих комп'ютерах вплив зазначеного мінуса значно послаблено. До цього ж класу можна віднести і мережі комп'ютерів, які все частіше розглядають як дешеву альтернативу вкрай дорогим суперкомп'ютерів.

Рис. 1.1. Системи з розподіленою пам'яттю

1.3 Комп'ютери з загальною пам'яттю (SMP системи)

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

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

Рис. 1.2. Системи із загальною пам'яттю

У чистому вигляді SMP системи складаються, як правило, не більше ніж з 32 процесорів, а для подальшого нарощування використовується NUMA-технологія, яка в даний час дозволяє створювати системи, що включають до 256 процесорів з загальною продуктивністю близько 150 млрд. операцій в секунду. Системи цього типу виробляються багатьма комп'ютерними фірмами як багатопроцесорні сервери з кількістю процесорів від 2 до 64 і міцно утримують лідерство у класі малих суперкомп'ютерів з продуктивністю до 60 млрд. операцій в секунду.

УданийнапрямоквходятьбагатосучаснихбагатопроцесорніSMP-комп'ютериабо, наприклад, окремі вузли комп'ютерів HP Exemplarі SunStarFire.

1.4 Системи з неоднорідним доступом до пам'яті (NUMA)

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

1.5 Комп'ютерні кластери

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

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

Для створення кластера використовуються комп'ютери, які можуть являти собою як прості однопроцесорні системи, так і володіти складною архітектурою SMP і навіть NUMA.

До теперішнього часу розроблено безліч технологій з'єднання комп'ютерів в кластер. Найбільш простим варіантом є використання технології Ethernet, однак за цю простоту доводиться розплачуватися завідомо недостатньою швидкістю обмінів. Розробники пакету підпрограм ScaLAPACK, призначеного для вирішення задач лінійної алгебри на багатопроцесорних системах, в яких велика частка комунікаційних операцій, формулюють наступним чином вимога до багатопроцесорної системі: «Швидкість міжпроцесорних обмінів між двома вузлами, виміряна в Mbyte / sec, повинна бути не менше 1 / 10 пікової продуктивності обчислювального вузла, виміряної в MFLOPS». Коефіцієнт 1/10 отримано з практичного досвіду, що показує, що на більшості додатків реальна продуктивність обчислювальних систем становить приблизно 10% від пікової продуктивності. Таким чином, якщо в якості обчислювальних вузлів використовувати комп'ютери класу PentiumIII 500 Mhz (пікова продуктивність 500 MFLOP), то апаратура Fast Ethernet (швидкість передачі приблизно 10 Mbyte / sec) забезпечує лише 1/5 від необхідної швидкості. Це положення може істотно поправити перехід на технології Gigabit Ethernet.

Рядфірмпропонуютьспеціалізованікластернірішеннянаосновібільшшвидкіснихмережтаких, як SCI фірми Scali Computer (~ 80 Mbyte / sec) іMirynet (~ 40 Mbyte / sec). Активно включилися в підтримку кластерних технологій і фірми-виробники високопродуктивних робочих станцій (SUN, Compaq, SiliconGraphics).

За таким принципом побудовані CRAYSV1, HPExemplar, SunStarFire, NECSX-5, останні моделі IBMS2 та інші. Саме цей напрямок є в даний час найбільш перспективним для конструювання комп'ютерів з рекордними показниками продуктивності.

1.6 Мета-комп'ютинг

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

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

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

2. Алгоритм додавання ряду чисел

2.1 Словесний опис алгоритму

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

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

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

2.2 Блок-схеми алгоритмів

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

Рис. 2.1. Загальна блок-схема послідовного алгоритму

Рис. 2.2. Загальна блок схема паралельного алгоритму

Рис. 2.3. Блок-схема підпрограми паралельного алгоритму

3. Лістинг програми

Лістинг програми паралельного додавання ряду чисел

#include<stdio.h>

void main()

{

printf («Input number of elements:»);

int n;

scanf («%d»,&n);

int *arr=new int[n];

int i;

for (i=0; i<n; i++)

{

printf («Input element number % d:», i+1);

scanf («%d»,&arr[i]);

}

int sum=0;

for (i=0; i<n; i++)

{

sum+=arr[i];

}

printf («Sum =%d», sum);

getch();

}

Лістинг програми паралельного додавання ряду чисел

#include<stdio.h>

#include <conio.h>

int result = 0;

void Sum (int proc, int *a, int num)

{

int res = 0;

for (int i=0; i<num; i++)

{

If(! (i % proc))

res += a[i];

}

result += res;

}

void main()

{

4. Результат виконання програми

Рис. 4.1. Додавання ряду чисел

багатопроцесорний додавання число програма

Висновок

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

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

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