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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Ігнатенко, О.П., Парусімов, Г.В., Синецький, О.Б.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут програмних систем НАН України 2015
Schriftenreihe:	Проблеми програмування
Schlagworte:	Прикладні засоби програмування та програмне забезпечення
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/113713
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Одна модель виконання обчислень у гетерогенних розподілених середовищах / О.П. Ігнатенко, Г.В. Парусімов, О.Б. Синецький // Проблеми програмування. — 2015. — № 1. — С. 71-77. — Бібліогр.: 6 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-113713
record_format	dspace
spelling	irk-123456789-1137132017-02-12T03:04:08Z Одна модель виконання обчислень у гетерогенних розподілених середовищах Ігнатенко, О.П. Парусімов, Г.В. Синецький, О.Б. Прикладні засоби програмування та програмне забезпечення В даній роботі досліджується потокова модель паралельних обчислень у гетерогенній багатопроцесорній системі. Використання потокової моделі дозволяє обчислити «ідеальний» час закінчення, який дає нижню оцінку реального часу. Пропонується ігрова модель взаємодії користувачів, що виконують задачі у спільному обчислювальному середовищі на прикладі задачі множення матриць. Дією користувачів у даному випадку є розмір блоку на яку розрізається матриця. Проведені експерименти з використанням середовища імітаційного моделювання GridSim, що підтверджують теоретично отримані результати. 2015 Article Одна модель виконання обчислень у гетерогенних розподілених середовищах / О.П. Ігнатенко, Г.В. Парусімов, О.Б. Синецький // Проблеми програмування. — 2015. — № 1. — С. 71-77. — Бібліогр.: 6 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/113713 004.7 uk Проблеми програмування Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення
spellingShingle	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення Ігнатенко, О.П. Парусімов, Г.В. Синецький, О.Б. Одна модель виконання обчислень у гетерогенних розподілених середовищах Проблеми програмування
description	В даній роботі досліджується потокова модель паралельних обчислень у гетерогенній багатопроцесорній системі. Використання потокової моделі дозволяє обчислити «ідеальний» час закінчення, який дає нижню оцінку реального часу. Пропонується ігрова модель взаємодії користувачів, що виконують задачі у спільному обчислювальному середовищі на прикладі задачі множення матриць. Дією користувачів у даному випадку є розмір блоку на яку розрізається матриця. Проведені експерименти з використанням середовища імітаційного моделювання GridSim, що підтверджують теоретично отримані результати.
format	Article
author	Ігнатенко, О.П. Парусімов, Г.В. Синецький, О.Б.
author_facet	Ігнатенко, О.П. Парусімов, Г.В. Синецький, О.Б.
author_sort	Ігнатенко, О.П.
title	Одна модель виконання обчислень у гетерогенних розподілених середовищах
title_short	Одна модель виконання обчислень у гетерогенних розподілених середовищах
title_full	Одна модель виконання обчислень у гетерогенних розподілених середовищах
title_fullStr	Одна модель виконання обчислень у гетерогенних розподілених середовищах
title_full_unstemmed	Одна модель виконання обчислень у гетерогенних розподілених середовищах
title_sort	одна модель виконання обчислень у гетерогенних розподілених середовищах
publisher	Інститут програмних систем НАН України
publishDate	2015
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	http://dspace.nbuv.gov.ua/handle/123456789/113713
citation_txt	Одна модель виконання обчислень у гетерогенних розподілених середовищах / О.П. Ігнатенко, Г.В. Парусімов, О.Б. Синецький // Проблеми програмування. — 2015. — № 1. — С. 71-77. — Бібліогр.: 6 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT ígnatenkoop odnamodelʹvikonannâobčislenʹugeterogennihrozpodílenihseredoviŝah AT parusímovgv odnamodelʹvikonannâobčislenʹugeterogennihrozpodílenihseredoviŝah AT sinecʹkijob odnamodelʹvikonannâobčislenʹugeterogennihrozpodílenihseredoviŝah
first_indexed	2025-07-08T06:16:56Z
last_indexed	2025-07-08T06:16:56Z
_version_	1837058403334094848
fulltext	Прикладні засоби програмування та програмне забезпечення © О.П. Ігнатенко, Г.В. Парусімов, О.Б. Синецький, 2015 ISSN 1727-4907. Проблеми програмування. 2015. № 1 71 УДК 004.7 О.П. Ігнатенко, Г.В. Парусімов, О.Б. Синецький ОДНА МОДЕЛЬ ВИКОНАННЯ ОБЧИСЛЕНЬ У ГЕТЕРОГЕННИХ РОЗПОДІЛЕНИХ СЕРЕДОВИЩАХ В даній роботі досліджується потокова модель паралельних обчислень у гетерогенній багатопроцесор- ній системі. Використання потокової моделі дозволяє обчислити «ідеальний» час закінчення, який дає нижню оцінку реального часу. Пропонується ігрова модель взаємодії користувачів, що виконують за- дачі у спільному обчислювальному середовищі на прикладі задачі множення матриць. Дією користува- чів у даному випадку є розмір блоку на яку розрізається матриця. Проведені експерименти з викорис- танням середовища імітаційного моделювання GridSim, що підтверджують теоретично отримані ре- зультати. Вступ Важливим напрямком сучасних на- укових досліджень є надання сервісів дос- тупу до обчислювальних ресурсів через мережу Інтернет. Ідея надання доступу до різноманітних обчислювальних ресурсів для за вимогою користувача або – обчис- лення як сервісу вже виникала в середині 90-х років у вигляді Grid інфраструктури. Починаючи з 2008 року виникає термін – хмарні обчислення (Cloud com- puting), який представляє нову парадигму обчислень, що дозволяє отримувати дос- туп до програмних, обчислювальних та інформаційних ресурсів у вигляді мереже- вих сервісів. З розвитком та ускладненням хмар- них сервісів виникає проблема побудови ефективних алгоритмів забезпечення їх безперешкодної роботи. Одним з перспек- тивних напрямків розвитку є теоретико- ігровий підхід, який дозволяє побудувати аналітичні моделі та дослідити динаміку системи з багатьма конфліктуючими за ре- сурси користувачами. Хмарні обчислення стали новим на- прямком розвитку інформаційних техно- логій, об’єднавши у собі ідеї комп’ютерних мереж та обчислювальних дата центрів. Власне хмара – це можли- вість надавати сервіси користувачам через мережу Інтернет. Існують три основні ти- пи сервісів: програми у вигляді сервісів (Software as a Service (SaaS)), платформи у вигляді сервісів (Platform as a Service (PaaS)) та інфраструктура у вигляді сервісу (Infrastructure as a Service (IaaS)). Будемо називати такі системи – C/G системами. Ефективність C/G системи забезпе- чують великі дата центри та технологія віртуалізації. Користувачі, таким чином, отримують доступ на основі принципу pay-as-you-use (сплати за використання) до найбільш сучасної інфраструктури не витрачаючи коштів на її створення та під- тримку. Провайдери в свою чергу макси- мізують використання своїх потужностей та можуть балансувати навантаження че- рез мережі для досягнення рівномірної загрузки. Таким чином, ключовим елементом роботи C/G системи є ефективні алгоритми надання сервісів користувачам. Сучасна хмарна система існує у середовищі постій- них змін. Змінюються технології, протоко- ли та програмне забезпечення. Змінюються користувачі, їх пріоритети, задачі і поведі- нка. Всі ці зміни є непередбачуваними. Тому теорія ігор, яка вже має історію ус- пішного застосування до розв’язання задач маршрутизації, планування, керування по- токами даних і перевантаженнями, є голо- вним напрямком аналітичного моделю- вання хмарних систем. Аналітичне моделювання дозволяє формалізувати роботу системи, поведінку користувачів і залучити їх у побудовану модель. Кожен гравець тут є автономним агентом, що прагне отримати певну части- ну обчислювального ресурсу. Припускаю- чи, що гравці діють раціонально – тобто Прикладні засоби програмування та програмне забезпечення 72 максимізують свою функцію корисності можна здійснити аналіз отриманої гри. Ключовим елементом аналізу є пошук то- чки рівноваги та її характеристика. Рівно- вага – це одна з головних ідей теорії ігор. Буквально – рівноважний стан відповідає ситуації, коли гравці досягли максимуму своїх функцій корисності. В залежності від зовнішніх факторів можливі стійкі і не- стійкі рівноваги. Взагалі, концепцій рівно- ваги в іграх існує більш ніж два десятки. Найбільш відомою є рівновага за Нешем: множина стратегій гравців утво- рюють рівновагу за Нешем, якщо ніхто з них не може покращити свою функцію ко- рисності змінюючи окремо свою страте- гію. Іншими словами кожен гравець вико- ристовує найкращу можливу стратегію у відповідь на стратегії своїх опонентів. Задача множення матриць Паралельне множення матриць – це одна з найбільш розповсюджених опера- цій, яка застосовується при обробці зобра- жень, задачах метеорологічного прогнозу та багатьох інших. У реальних системах доводиться оперувати з матрицями великої розмірності, множення яких потребує )( 3NO операцій, де N – розмірність мат- риць. Тому важливою проблемою є забез- печення максимальної ефективності обчи- слень. Алгоритми множення матриць дос- ліджуються вже більше 50 років. На сього- дні досягнуто значних результатів, зокрема алгоритм Штрассена дозволив зменшити кількість операцій до )( 82.2NO , однак це не змінює ситуації принципово. Іншим на- прямком є паралельне обчислення, яке до- зволяє скоротити час виконання пропор- ційно до кількості задіяних ресурсів. Пропонується розрізати матриці на блоки, які можуть обчислюватись незале- жно або принаймні паралельно (обмінюю- чись інформацією у певні моменти часу). Кожен процесор обчислює свою частину і потім передає результат далі за визначе- ною схемою взаємодії. В кінці роботи ре- зультуюча матриця збирається з частин. Особливо плідним напрямком є по- будова аналітичної моделі алгоритму під конкретну конфігурацію обчислювальної системи з метою пошуку оптимального розв’язку [1]. В даному напрямку було до- сягнуто значних результатів, наприклад [2–4]. Архітектура обчислювальної сис- теми. В даній роботі будемо вважати, що обчислювальні вузли не зв’язані один з одним і не можуть обмінюватись напрямку даними. Кожен вирішує свою задачу неза- лежно і повертає користувачу результат по закінченню. Будемо вважати, що в системі є m обчислювальних елементів та кожен з них характеризується швидкістю роботи ip , mi ,...,1 – тобто кількістю операцій з плаваючою точкою за секунду, які він мо- же здійснити. Обчислювачі з’єднані лініями зв’язку з планувальником, який передає задачі та приймає від них результат. Буде- мо вважати, що лінії зв’язку ідентичні та мають швидкість передачі даних q . Блочний алгоритм. Результатом множення матриці A розмірністю nm і матриці B розмірності ln є матриця C розмірності lm , кожен елемент якої об- числюється наступним чином:     1 0 n k kjikij bac , mi ,...,1 , lj ,...,1 . Цей алгоритм вимагає lnm  опе- рацій множення й додавання елементів ма- триць. При множенні квадратних матриць розмірності nn кількість виконаних опе- рацій має порядок )( 3nO . Необхідно по- будувати паралельний алгоритм, який буде виконувати множення матриць за найкоро- тший час для довільної кількості неодно- рідних процесорів (рис. 1). Для експерименту було обрано на- ступну паралельну модифікацію послідов- ного алгоритму: Рис. 1. Схема множення Прикладні засоби програмування та програмне забезпечення 73 Якщо ми множимо дві квадратні матриці розмірністю nn , то результуюча матриця C буде тієї самої розмірності, що й вхідні матриці A і B . Спочатку матриця C розбивається на прямокутні блоки роз- мірністю yx n n n n  , де xn та yn – кількість блоків по вертикалі й горизонталі. Кожен з цих блоків обчислюється незалежно окре- мою під-задачею, для чого підзадача пот- ребує блок матриці A розмірністю xn n n  й аналогічний блок матриці B розмірністю yn n n  . Перевагою такого алгоритму є те, що задачу можна розбивати на довільну кількість підзадач, а не тільки на квадратні блоки. Також відсутність будь-яких зале- жностей між підзадачами дозволяє ефек- тивно виконувати обчислення у випадку коли кількість наявних процесорів значно менша за кількість підблоків – в такому випадку підзадачі отримують нові блоки «за готовністю». Недоліком є додаткові витрати пам’яті, які виникають при частковому ду- блюванні вхідних даних для різних під- задач. Загальна кількість операцій не від- різняється від послідовного алгоритму й має порядок )( 3nO . Кожна підзадача виконує          n n n n n O yx скалярних операцій та потребує пересилки          yx n n n n O 22 елементів. Якщо враховувати тільки операції множення (вони дають головний вклад у час виконання задачі), то для обчислення однієї підзадачі потрібно виконати yxnn n3 операцій. Також потрібно переслати yx n n n n 22  елементів та прийняти yxnn еле- ментів. Зауваження. Описаний алгоритм множення матриць дозволяє розбивати за- дачу на блоки без «штрафів», тобто зага- льна кількість обчислень при розбитті на менші підзадачі не змінюється. Потокова модель обчислення множення матриць. Будемо вважати, що виконуються наступні припущення. 1. Всі процесори починають робо- ту одночасно. 2. Планувальник здійснює приз- начення миттєво. Зрозуміло, що мінімально можливі блоки досягаються при nnn yx  . Нехай задане довільне розбиття xn , yn , яке за- безпечує виконання задачі за час ),( yxk nnTT  . Припустимо, що планува- льник забезпечує найкраще можливе вико- нання, тоді задача користувача полягає у розв’язанні наступної задачі: min),( yx nnT . Функція ),( yx nnT , взагалі кажучи, може мати багато локальних мінімумів [4], оскільки існує мінімальна фіксована вели- чина блоку, яка визначається розбиттям. При переплануванні блоку з одного проце- сора на інший відбувається дискретна змі- на часу виконання. Тому задача визначен- ня мінімуму є складною. Одним з розповсюджених підхо- дів до аналізу таких задач є ідеалізація, яка полягає у дослідженні потокової мо- делі [3]. Припустимо, що користувач розді- лив задачу на m підзадач, кожна з яких має складність ix , mi ,...,1 та признача- ється процесору відповідного номера. Тоді 3 1 nx m i i   . Потокова модель передбачає можливість розділення задачі на «шматоч- ки» розміру  , компонування з них підхо- дящих підзадач та визначення загального часу при 0 . Прикладні засоби програмування та програмне забезпечення 74 Твердження 1. Мінімальний час закінчення обчислень (без пересилок) для потокової моделі з одним користувачем дорівнює 1 1 3             m i ipnT . Це оцінка знизу будь-якого експе- риментального часу виконання. Доведення. Нехай задано розбиття ),...,( 1 mxxx  , тоді час завершення роботи i -го процесора дорівнює i i p x , у потоковій моделі всі процесори закінчують роботу одночасно – інакше можливо було б пере- розподілити вектор x , зменшивши час. Отже c m m T p x p x  ... 1 1 . Підставивши ici pTx  у 3 1 nx m i i   отримуємо результат для часу обчислен- ня. Даний час буде мінімально можливим, оскільки не враховує мінімально можливі блоки при розбитті матриць на підзадачі. Дискретна модель обчислення множення матриць. Нехай заданий міні- мальний розмір блоку yxnn n2 (будемо вва- жати, що це ціле число), тоді для обчис- лення кожного елемента цього блоку пот- рібно виконати n множень, отже загальна складність мінімальної задачі дорівнює yxnn n3 операцій. Потокова модель визначає оптима- льний розподіл           i n i p p p p nx ,...,13 . Побудуємо сітку допустимих роз- поділів з урахуванням мінімального бло- ку. Позначимо множину можливих розпо- ділів },0\|),...,{( 1 1 yx m j jjm nnkkkkK    . Визначимо вектор z наступним чи- ном: yx i i nn k nkz 3)(  , даний вектор визначає обсяг обчислень, що призначений відповідному процесору. Зауважимо, що за припущенням елементи вектора z – цілі числа і 3 1 )( nkz m i i   , для будь-якого Kk . Тоді для фіксованого Kk час за- кінчення обчислень дорівнює j j j p kz kzT )( max))((  . Визначимо множину ))(( kzR            yx ii m i i m nn n ykznyRy 2 2 )(,\| 3 3 1 . Твердження 2. Мінімальний час закінчення обчислень для дискретної мо- делі з мінімальним блоком yxnn n2 та одним користувачем дорівнює ))(( kzT , де індекс Kk визначається включенням ))(( kzRx . Доведення. Розглянемо всі можливі розподіли на блоки, які описується векто- рами )(kz , Kk . Множина цих точок утворює цілочисельну сітку в просторі mR , яка належить гіперплощині          3 1 \| nyRyY m i i m . При пошуку розподілу, який відповідає мінімальному часу розглянемо процедуру руху за даною сіткою. При переміщенні з вузла )(1 kz на сусідній вузол )(2 kz одна з координат збільшується, інша зменшуєть- ся а решта залишається незмінними. Відс- тань між сусідніми вузлами дорівнює Прикладні засоби програмування та програмне забезпечення 75 yxnn n32 . Обчислимо множину точок з Y , відстань від яких до )(1 kz менша за відс- тань до будь-якої іншої точки сітки. Оскі- льки функція j j j p x xT max)(  є кусково лі- нійною, то мінімум функції часу ))(( kzT буде досягатися на точці сітки, найближ- чій до розв’язку потокової задачі. Цей факт описується включенням ))(( kzRx . Некооперативна ігрова модель обчислення множення матриць. Некоо- перативна гра описує ситуацію прийняття рішень гравцями за умов конфлікту інте- ресів. Під терміном гравець тут ми розу- міємо користувача, який впливає на сис- тему шляхом вибору стратегій – дій, які він може застосовувати. В залежності від дій його та інших учасників відбувається визначення виграшів гравців. Говорять, що гравець раціональний, якщо його дії спрямовані на максимізацію власного ви- грашу. Якщо у грі приймають участь хоча б двоє учасників, можлива ситуація, коли перший гравець може покращити свій ви- граш за рахунок зменшення виграшу ін- ших. В такому випадку кажуть про конф- ліктну взаємодію. Частинним випадком конфлікту є ситуація повністю протилеж- них інтересів – коли виграш одного є про- грашем іншого. Такі ігри називають анта- гоністичними або іграми з нульовою су- мою. Зауважимо, що некооперативність не означає, що гравці взагалі не кооперу- ються, а тільки те, що немає зовнішніх причин, які б спричиняли координацію або узгодження їх стратегії. Будь-яка коо- перація що може виникнути має виходити зі структури гри і визначатися функціями корисності учасників. Гру називають статичною, якщо гравці приймають свої рішення одноразо- во, незалежно один від одного. В певному розумінні, статична гра не залежить від часу. Навіть якщо гравці приймають рі- шення протягом певного часового інтер- валу, якщо вони не володіють інформаці- єю щодо дій інших гравців, така гра є ста- тичною. У динамічних іграх гравці отриму- ють певну інформацію щодо рішень ін- ших учасників і можуть змінювати свою стратегію у часі, тобто приймають рішен- ня більше одного разу. Динамічні ігри є найбільш складним для аналізу і відігра- ють важливу роль у дослідженні процесів у мережах [5, 6]. Опишемо задачу множення мат- риць у вигляді статичної некооперативної гри. Основні визначення. При визна- ченні статичних ігор загальновживаною є стратегічна або нормальна форма, яка включає опис трьох компонентів: множи- ни гравців, їх стратегій і виграшів. Гравцями в даному випадку явля- ються користувачі   Liiu  , L – множина індексів, які мають доступ до спільного ресурсу з m обчислювальних елементів з швидкістю роботи ip , mi ,...,1 . Будемо вважати, що для кожного користувача за- дані квадратні матриці розмірності ln , Ll . Тоді стратегіями користувачів є до- пустиме розбиття матриць на блоки ll Kk  , Ll . Після розбиття матриць, блоки потрапляють у планувальник, який надсилає їх на процесори згідно з певним визначеним алгоритмом роботи. Часом закінчення обчислень lT , Ll будемо на- зивати час закінчення останньої задачі користувача lu . Кожен користувач нама- гається зменшити свій час закінчення і через обмеженість спільних ресурсів ви- граш одного користувача спричинить програш інших. Середовище моделювання GridSim GridSim розроблений в Університе- ті Монаш (Австралія) з метою моделюван- ня роботи GRID-системи з можливістю імітаційного моделювання характеристик ресурсів і обчислювальних мереж при різ- них конфігураціях планувальників про- грам для розподілених обчислювальних систем, таких як кластери і Grid. GridSim Прикладні засоби програмування та програмне забезпечення 76 розроблений на мові програмування Java і дозволяє моделювати різні класи гетеро- генних ресурсів, брокерів ресурсів (RBS), користувачів, програм і планувальників у розподіленому обчислювальному середо- вищі. До основних характеристик GridSim можна віднести:  моделювання різних конфігура- цій обчислювальної мережі GRID-систем різних топологій;  моделювання різних політик планування завдань на обчислювальному кластері, як вже реалізованих, так і роз- роблених користувачем;  використання даних про заван- таження реальних суперкомп’ютерів для проведення експериментів; Опишемо архітектуру GridSim. Ни- жній рівень – Java Virtual Machine (JVM), основна частина виконавчої системи Java, так званої Java Runtime Environment (JRE). Віртуальна машина Java інтерпретує і ви- конує байт-код Java, попередньо створе- ний з вихідного тексту Java-програми ком- пілятором Java. Другий рівень являє собою SimJava бібліотеку, яка використовується для уп- равління моделюванням і взаємодією об’єктів GridSim. Третій рівень – безпосе- редньо GridSim. Вона моделює основні об’єкти Grid такі, як ресурси та інформа- ційні сервіси. Цей рівень містить підрівень моделювання ресурсів і визначення топо- логії мережі. Статистичні дані автоматич- но збираються і доступні через об’єкт GridStatistics. Також на цьому рівні знахо- дяться об’єкти для моделювання DataGrid: ReplicaCatalogue і ReplicaManager. Останній, четвертий рівень визна- чає функціональні можливості для плану- вальників і брокерів ресурсів. Верхній рі- вень призначений для конфігурування па- раметрів моделювання. Опишемо виконання експерименту в GridSim. Об’єкт GridUser представляє собою користувача. Важливим парамет- ром для користувача є пропускна здат- ність передачі даних (baud_rate) за яким рахується час передачі даних та повер- нення результату. Завдання від користу- вача направляється на відповідний Брокер Ресурсів (RBS) у вигляді об’єкта Gridlet. Gridlet є пакетом, який містить всю інфо- рмацію, пов’язану з завданням – довжину завдання (виражену в мільйонах операцій, MI), розмір вхідних і вихідних файлів, ха- рактеристики користувача. Ці основні па- раметри допомагають визначити час ви- конання, час, необхідний на передачу файлів і повернення обробленого об’єкту Gridlet користувачу разом з результатами обробки. RBS запитує у GRID Information Service (GIS) список доступних GridResource. GIS реєструє ресурси, що дає можливість відстежувати список дос- тупних ресурсів GRID. Після чого, RBS виконує вибір ресурсу і направляє Gridlet на обробку, згідно з установленим сцена- рієм. GridResource – об’єкт, складений з однієї або більше машин (Machine). Machine містить один або більше CPU (processing elements, PE), для кожного з яких потужність задається кількістю опе- рацій за секунду (mipsRating-millions of instructions per second (MIPS)). Після ви- конання Gridlet, GridResource повідомляє RBS про завершення. Слід зазначити, що ресурс може виконувати кілька завдань одночасно. Для розглянутого прикладу задачі паралельного множення матриць блочним методом задача поділяється на незалежні підзадачі – множення блоків матриці , ко- жна з яких обчислюється на окремому вуз- лі CPU. Якщо N – розмірність квадратної матриці, m – кількість блоків по одному з вимірів матриці, то загальна кількість не- залежних підзадач буде mm і розмір- ність блоку mNn  . Тому одне завдання користувача Gridlet буде складатися з MINnnlength 1000000)12(  операцій, розмір вхідних даних 82_  nnsizefile та вихідних 8_  nnsizeoutput байтів. Експериментальні дані Для перевірки отриманих результа- тів та обґрунтування подальших дослі- Прикладні засоби програмування та програмне забезпечення 77 джень були проведені експерименти з імі- таційного моделювання обчислення добу- тку матриць на різних Grid системах. На рис. 2 показані результати зале- жності часу закінчення виконання від кі- лькості блоків для системи з одним, двома, трьома і чотирма процесорами. Також показані аналогічні залежно- сті для неоднорідних систем. Отримані графіки залежностей добре узгоджуються з результатами, отриманими при експери- ментальних вимірах на кластері Інституту програмних систем НАН України [4]. Рис. 2. Однакові процесори Рис 3. Неоднорідні процесори Висновки В даній роботі досліджується пото- кова модель паралельних обчислень у не- однорідних багатопроцесорних системах. Використання потокової моделі дозволяє обчислити «ідеальний» час закінчення, який дає нижню оцінку реального часу. Проведені експерименти, що підтверджу- ють теоретично отримані результати. 1. Srinivasa Prasanna G.N., Musicus B. Generalized Multiprocessor Scheduling Using Optimal Control // Proc. SPAA. – 1991. – P. 216–228. 2. Grosu D., Chronopoulos A.T. Noncooperative load balancing in distributed systems // Journal of Parallel and Distributed Computing, 2005. – 65 (9). – P. 1022 – 1034. 3. Nazarathy Y., Weiss G. A Fluid Approach to Large Volume Job Shop Scheduling // Journal of Scheduling, 13(5). – 2010. P. 509–529. 4. Дорошенко А.Ю., Ігнатенко О.П., Іваненко П.А. Про одну модель оптимального роз- поділу ресурсів у багатопроцесорних сере- довищах // Проблеми програмування. – № 1. – 2011. – С. 21–28. 5. Андон Ф.И., Игнатенко А.П. Моделирова- ние конфликтных процессов в сети Интер- нет // Кибернетика и системный анализ. – 2013. – № 4. – C. 153–162. 6. Ignatenko O., Synetskyi O. Evolutionary Game of N Competing AIMD Connections. In Information and Communication Technolo- gies in Education, Research, and Industrial Applications. Springer International Publish- ing. – 2014. – P. 325–342. Одержано 20.01.2015 Про авторів: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, Синецький Олександр Борисович, аспірант, Парусімов Генадій Вікторович, аспірант. Місце роботи авторів: Інститут програмних систем НАН України, 03187, Київ-187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. E-mail: o.ignatenko@gmail.com mailto:o.ignatenko@gmail.com

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

Institution

Ähnliche Einträge