One model of optimal resource allocation in homogeneous multiprocessor system

This paper deals with the control model of optimal recourse allocation in homogeneous multiprocessor system. We proposed an approach to developing optimal control using fluid models theory domain. We obtain analytic solution for time depending of parallel execution parameters. Results are validated...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2025
Автори:	Doroshenko, A.Yu., Ignatenko, O.P., Ivanenko, P.A.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	PROBLEMS IN PROGRAMMING 2025
Теми:	UDC 681.3
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/795
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-795
record_format	ojs
resource_txt_mv	ppisoftskievua/e4/c57f5aff5435c1c8e7224ed4fc5f81e4.pdf
spelling	pp_isofts_kiev_ua-article-7952025-09-02T15:47:58Z One model of optimal resource allocation in homogeneous multiprocessor system Про одну модель оптимального розподілу ресурсів у багатопроцесорних середовищах Doroshenko, A.Yu. Ignatenko, O.P. Ivanenko, P.A. UDC 681.3 УДК 681.3 This paper deals with the control model of optimal recourse allocation in homogeneous multiprocessor system. We proposed an approach to developing optimal control using fluid models theory domain. We obtain analytic solution for time depending of parallel execution parameters. Results are validated by experimentation for matrix multiplication example.Problems in programming 2011; 1: 29-38 Розглядається модель керування ресурсами в однорідному багатопроцесорному середовищі. Запропоновано підхід на основі потокових моделей, який дозволяє отримати оптимальне у сенсі швидкодії керування. Отримано аналітичний вид часу закінчення роботи в залежності від параметрів розпаралелювання. Результати проілюстровані на відомому прикладі множення матриць. Виконано експериментальне підтвердження теоретичних моделей.Problems in programming 2011; 1: 29-38 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-28 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/795 PROBLEMS IN PROGRAMMING; No 1 (2011); 29-38 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2011); 29-38 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2011); 29-38 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/795/847 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-09-02T15:47:58Z
collection	OJS
language	Ukrainian
topic	UDC 681.3
spellingShingle	UDC 681.3 Doroshenko, A.Yu. Ignatenko, O.P. Ivanenko, P.A. One model of optimal resource allocation in homogeneous multiprocessor system
topic_facet	UDC 681.3 УДК 681.3
format	Article
author	Doroshenko, A.Yu. Ignatenko, O.P. Ivanenko, P.A.
author_facet	Doroshenko, A.Yu. Ignatenko, O.P. Ivanenko, P.A.
author_sort	Doroshenko, A.Yu.
title	One model of optimal resource allocation in homogeneous multiprocessor system
title_short	One model of optimal resource allocation in homogeneous multiprocessor system
title_full	One model of optimal resource allocation in homogeneous multiprocessor system
title_fullStr	One model of optimal resource allocation in homogeneous multiprocessor system
title_full_unstemmed	One model of optimal resource allocation in homogeneous multiprocessor system
title_sort	one model of optimal resource allocation in homogeneous multiprocessor system
title_alt	Про одну модель оптимального розподілу ресурсів у багатопроцесорних середовищах
description	This paper deals with the control model of optimal recourse allocation in homogeneous multiprocessor system. We proposed an approach to developing optimal control using fluid models theory domain. We obtain analytic solution for time depending of parallel execution parameters. Results are validated by experimentation for matrix multiplication example.Problems in programming 2011; 1: 29-38
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/795
work_keys_str_mv	AT doroshenkoayu onemodelofoptimalresourceallocationinhomogeneousmultiprocessorsystem AT ignatenkoop onemodelofoptimalresourceallocationinhomogeneousmultiprocessorsystem AT ivanenkopa onemodelofoptimalresourceallocationinhomogeneousmultiprocessorsystem AT doroshenkoayu proodnumodelʹoptimalʹnogorozpodíluresursívubagatoprocesornihseredoviŝah AT ignatenkoop proodnumodelʹoptimalʹnogorozpodíluresursívubagatoprocesornihseredoviŝah AT ivanenkopa proodnumodelʹoptimalʹnogorozpodíluresursívubagatoprocesornihseredoviŝah
first_indexed	2025-09-17T09:23:03Z
last_indexed	2025-09-17T09:23:03Z
_version_	1850409897819111424
fulltext	Паралельне програмування 29 УДК 681.3 А.Ю. Дорошенко, О.П. Ігнатенко, П.А. Іваненко ПРО ОДНУ МОДЕЛЬ ОПТИМАЛЬНОГО РОЗПОДІЛУ РЕСУРСІВ У БАГАТОПРОЦЕСОРНИХ СЕРЕДОВИЩАХ Розглядається модель керування ресурсами в однорідному багатопроцесорному середовищі. Запропо- новано підхід на основі потокових моделей, який дозволяє отримати оптимальне у сенсі швидкодії ке- рування. Отримано аналітичний вид часу закінчення роботи в залежності від параметрів розпаралелю- вання. Результати проілюстровані на відомому прикладі множення матриць. Виконано експеримента- льне підтвердження теоретичних моделей. Вступ Сучасні задачі науки і техніки часто вимагають значних обсягів обчислюваль- них ресурсів, тому важливою задачею є підвищення ефективності виконання про- грам у багатопроцесорних середовищах. Керування виконанням заданої програми залежить від різних факторів: архітектури системи, операційної системи та організа- ції виконання (розпаралелювання програ- ми). Архітектура і операційна система, як правило, фіксовані, тому основним напря- мком керування є організація виконання програми. Для забезпечення ефективного використання ресурсів багатопроцесорної системи необхідно розв’язати дві основні задачі [1]. По-перше, обчислювальне наванта- ження програми має бути рівномірно роз- ділене між процесорами з мінімально можливими обмінами між ними. Це – задача розподілу. По-друге, потрібно поставити у від- повідність кожному завданню час початку виконання і процесор, на якому це завдан- ня буде виконуватись. При цьому бажано, щоб процесори були завантажені непере- рвно. Це – задача планування. Обидві ці задачі NP-складні. Загальна задача керування є оптимі- заційною, де як міра ефективності може виступати загальний час виконання, вар- тість використання, усереднений час вико- нання кожного завдання (час очікування + час виконання + час передачі користува- чу). Яскравим прикладом розподіленої обчислювальної системи є Грід. Грід [2] це конгломерат обчислювальних ресурсів, з’єднаних у мережу, який використовуєть- ся для розв’язання ресурсоємних задач. Характерною особливістю Грід є значна розподіленість і неоднорідність. Окремі ресурси можуть бути поєднані напряму, через локальну мережу або Інтернет, що спричиняє зміни у доступності та вартості використання різних частин системи. Існує дві основні категорії схем розподілу (або керування) – статичні і динамічні [3]. Статичні схеми керування використовують накопичені статистичні дані про роботу системи і не враховують поточний стан. Такий підхід дозволяє побудувати швидку і просту програму керування. Динамічні схеми використову- ють для прийняття рішень поточний стан системи (розміри черг, завантаженість і доступність вузлів, параметри вхідного потоку завдань). У рамках цього підходу окремі вузли мережі можуть обмінюватися інформацією і намагаються збалансувати навантаження шляхом перерозподілу ресурсів між вузлами. Хоча це і вимагає витрат певної частини ресурсів системи на забезпечення обміну повідомленнями і обчислення керування, динамічні схеми, взагалі кажучи, гарантують значно кращу ефективність роботи. Завдання, що виконуються в розпо- діленій системі можуть бути як однорідні так і розділені на класи. Таке розділення може здійснюватися за ознакою користу- вача (всі завдання одного користувача виділяють у окремий клас), за розміром або пріоритетом. Критерії ефективності схеми керування розділяють на [4]. © А.Ю. Дорошенко, О.П. Ігнатенко, П.А. Іваненко, 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 1 Паралельне програмування 30 • Загально-оптимальні. Всі завдання належать одному класу і мінімізується загальна характеристика. • Індивідуально-оптимальні. Мінімі- зується час виконання кожного окремого завдання. • Оптимальні за типами. Виділяється скінченна кількість типів завдань, схема мінімізує час виконання завдань кожного типу. Задача статичного керування ресур- сами для одного і багатьох класів завдань досліджена досить добре. Більшість робіт розглядають ситуацію з точки зору глоба- льного підходу, коли основна увага зосе- реджена на мінімізації очікуваного часу відклику системи у цілому. При цьому розглядались різні конфігурації мережі як для нелінійних [5 – 6], так і для лінійних [7] моделей. У цих роботах вирішується задача мінімізації часу відклику. Дана робота також будує статичну схему керу- вання, яка мінімізує час завершення за- вдання. Деякі автори розглядають статичні алгоритми, що забезпечують індивідуаль- но-оптимальний розв’язок [8] та спира- ються на методи класичної теорії ігор. Теоретико-ігровий підхід застосовувався, зокрема, у роботах [8] (дослідження неко- оперативних ігор), [9, 10] (кооперативні ігри, рівновага за Нешем), для моделюван- ня динаміки Грід систем [11 – 13]. Динамічне керування, на відміну від статичного, має обчислюватись у реа- льному часі. Для розподілених систем це означає, що вузли мають обмінюватись інформацією про свій поточний стан. Для великої кількості вузлів такі обміни мо- жуть негативно впливати на роботу всієї системи, тому розглядають окремо централізоване і розподілене керування. У першому випадку виділяється окремий комп’ютер (вузол), відповідальний за відстеження глобального стану системи. На основі зібраної інформації цей керую- чий вузол приймає рішення щодо розподі- лу завдань і ресурсів. При побудові централізованих схем керування застосо- вують теорію черг та інші моделі. Розподілене або децентралізоване керування характерне для систем зі знач- ною кількістю вузлів. У цьому випадку кожен окремий вузол приймає рішення про розподіл ресурсів на основі доступної йому локальної інформації (яка може бути неповною). Тому більшість розподілених схем є субоптимальними або евристични- ми саме через неможливість отримати повну й достовірну інформацію про пото- чний стан системи. Розподілені динамічні схеми досліджувались у роботах [14]. Великий клас алгоритмів був отриманий з використанням ідей штучного інтелекту [15] та генетичних алгоритмів [16]. 2. Задача розподілу ресурсів при виконанні паралельних обчислень Задача розподілу ресурсів у неод- норідних багатопроцесорних системах при здійсненні паралельних обчислень є скла- дною проблемою, оскільки включає у себе розподіл за двома вимірами – час і ресур- си, у два етапи – маршрутизація (передача пакетів на вузли) і планування (надання ресурсів вузлам для здійснення обчис- лень). Існують різні підходи до розв’язання цієї задачі. Найбільш відомі з них: спільна черга, кластерізація і дворів- невий розподіл. Спільна черга. Можливо найпрос- тішим способом організації паралельного розподілу ресурсів є спільна черга (Global queue). У цьому випадку на кожному вузлі записується екземпляр програми, яка об- мінюється даними зі спільною структурою в якій зберігається інформація про всі поточні завдання. Система переносить першу задачу з черги на вільний процесор для виконання. Основною перевагою спі- льної черги є простота й автономність розподілу. Крім цього, процесор заванта- жується роботою відразу після завершення і працює поки в черзі є завдання. Однак недоліки схеми також значні. По-перше, при зростанні кількості проце- сорів спільна черга починає негативно впливати на роботу системи. По-друге, при завантаженні нового завдання втрачаються всі дані локальної пам’яті (при скоордино- ваному плануванні, можливо, деякі дані могли б бути використані вдруге). І, наре- Паралельне програмування 31 шті, останнє – дана схема не враховує необхідності взаємодії різних завдань під час виконання. Кластерізація. Іншим підходом є розділення процесорів на окремі незалежні множини (кластери) і виконання кожної роботи на окремому кластері. Існують різні способи розділення: фіксоване, за вимогою користувача, адаптивне і динамі- чне. Розділення за запитом користувача є одним з найбільш популярних. Перевагою підходу є врахування потреб користувача в першу чергу і ексклюзивний доступ до ресурсів і пам’яті вузлів, виділених для задачі. Звичайно, розділення за запитом має свої недоліки. Причина їх виникнення полягає у можливій невідповідності запи- тів користувачів і наявних ресурсів. У зв’язку з цим виникають дві проблеми: • перерозподіл вільних вузлів, якщо їх ресурсів недостатньо для виконання поточних завдань; • виконання великого завдання, що вимагає значних ресурсів. Така задача може очікувати досить довго поки не звільниться достатня кількість ресурсів. Динамічний дворівневий розпо- діл. Одним з способів зменшення часу очікування завдань у черзі є попередження монополізації великої кількості процесорів одним завданням. Ефективним способом організації обчислень є використання адаптивних схем розподілу ресурсів. Од- нак, для застосування ідеї адаптивного розподілу необхідно розв’язати проблему керування завантаженням вузла під час виконання завдання. Кількість процесорів, виділену для завдання, змінювати під час виконання не можна, тому для організації динамічного розділення виділяють два рівня розміщення задачі. Операційна сис- тема виділяє вузли для обчислень, а спеці- альне програмне забезпечення розміщує обчислення в залежності від наявної кіль- кості ресурсів. Динамічний дворівневий розподіл – схема, що широко застосовується і, як показано, має кращі характеристики ніж інші схеми. Це досягається завдяки тому, що 1. Ресурси не витрачаються на пе- рерозподіл вільних вузлів. 2. Непотрібно здійснювати син- хронізацію на глобальному рівні. 3. Рівень розпаралелювання за- вдань автоматично змінюється за умов перевантаження, що покращує ефектив- ність використання системи. 3. Модель системи Будемо розглядати систему з P не- залежних процесорів, які утворюють клас- тер. Існує нульовий вузол, який ми позна- чимо 0p – маршрутизатор, на який потра- пляють завдання. Вузол 0p здійснює пере- силку завдань на процесори. Потужність процесорів описується функціями )(tuiiμ , Pi ,..,1= , де ]1,0[)( ∈tui – нормалізоване керування, iμ – параметр потужності даного процесора. У відповідності до підходу, викла- деному в роботі [17] будемо моделювати процес планування за допомогою потоко- вої моделі, вважаючи, що кількість обчис- лень, які необхідно здійснити на момент часу t для виконання заданих робіт може бути представлена неперервною функцією часу. В певному розумінні, даний підхід є двоїстим до ідеї, викладеної у [1], де непе- рервними функціями описується сумарна потужність процесорів, що розв’язують задачу. Отже, позначимо )(tqi , Pi ,..,1= – кількість обчислень, які необхідно викона- ти ip процесору для завершення поточно- го завдання. Тоді в початковий момент часу 0)0( >= ii cq . Причому під час вико- нання на процесори можуть надходити нові завдання. Якщо визначена функція керування )(tui і нових надходжень немає, то )(tuq iii μ−=& , Pi ,..,1= . Тобто вважається, що швидкість обчислення залежить тільки від поточної потужності процесора. Опишемо тепер процес маршрути- зації завдань. Нехай )(tλ – функція, що описує завантаження завдань на вузол 0p . Паралельне програмування 32 Наприклад, така функція може мати ви- гляд подібний до зображеного на рис. 1. Рис. 1. Приклад функції )(tλ При цьому природно обмежити )(tλ наступним чином: ],0[)( maxλ∈λ t , int 0 )( λ=λ∫ ∞ dtt . Тоді динаміка системи буде опису- ватися потоковою моделлю: )(...)()()( 10 tvtvttq Pρ−−ρ−λ=& , )())(()( 1111 tutvftq c μ−=& , M )())(()( tutvftq PPPcP μ−=& , (1) або у скороченому вигляді: ))(),(),((~)( tutvtf dt tdq λ= . При цьому: )(tv = Vtvtv P ∈))(),...,(( 1 – функція маршрутизації, )(tu = Ututu P ∈))(),...,(( 1 – функція керування виконанням, )(tλ – функція завантаження вхід- них завдань, )(⋅cf буде введена далі. Множини керування PRU ⊂ , PRV ⊂ описують обмеження на ресурси. Простим і поширеним випадком [18] є випадок лінійних обмежень, коли, напри- клад, U – поліедральна множина, задана співвідношенням: { }IiuCuRuU i P ∈≥≤∈= ,0,1: , де C – дійсна матриця, 1 – вектор з оди- ниць і нерівність виконується по рядкам. Кожен рядок матриці C відповідає певно- му ресурсу. В рамках задачі множення матриць і кластерної архітектури прийме- мо, що ICC == 21 , тобто { }IiuuRuU ii P ∈≥≤∈= ,0,1: , { }IivvRvV ii P ∈≥≤∈= ,0,1: . У рамках даної моделі враховується відмінність між передачею даних для обчислень на процесорі ip і самими обчи- сленнями (існуючі потокові моделі, напри- клад, [17] ці процеси не розрізняють). Тим не менше відмінність існує. Наприклад, у задачі множення квадратних матриць розмірності NN × необхідно передавати на процесори 22N чисел, при цьому по- трібно виконати обсяг обчислень порядку )( 3NO . Для врахування цієї нелінійної залежності й вводиться функція RRfc →⋅ :)( , яка перетворює інтенсив- ність передачі даних )(tvi в інтенсивність отримання завдання на обчислення ))(( tvf ic . Задача оптимального керування. Тепер ми можемо поставити задачу опти- мальної організації обчислень. Нехай }0)(,0)(:0min{ 0 int =ττλ−λ=≥= ∫ t dtqtT , тоді задача зводиться до мінімізації часу за наступних умов: min→T , ))(),(),((~)( tutvtf dt tdq λ= , Vtv ∈)( , 0)( ≥tq . (2) При цьому функція )(tλ – фіксова- ний параметр. Задача (2) це задача опти- мального керування з нефіксованим часом за наявності фазових обмежень. Для цієї задачі вірна теорема про принцип макси- муму, якщо функція ),,(~ uvf λ гладко залежить від параметрів [19]. Оскільки Паралельне програмування 33 залежність від u,λ лінійна, то умова вико- нується якщо )(⋅cf гладка функція. Твердження. Якщо існує оптима- льний розв’язок задачі (2), то мінімальний час T досягається для max)(ˆ λ=λ t , ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ λ λ ∈ max int ,0t . Доведення. T не може бути менше за момент часу, коли 0)( 0 int =ττλ−λ ∫ t d . Цей момент мінімальний при вказаному )(ˆ tλ . Залишилось показати, що для всіх інших функцій )(tλ }0)(:0min{ =≥ tqt принаймі не зменшується. Дійсно, наприклад, для )(0 tq такий момент часу визначається рівнянням: td t ρ=λ=ττλ∫ int 0 )( , за інших )(tλ цей момент часу може зрос- ти або залишитися незмінним. Наслідок. Для оптимального розв’язку задачі (2) функції керування )(tv , )(tu – кусково лінійні та мають не більше одного переключення. Це випливає з того, що )(~ ⋅f не залежить від )(tq . 4. Задача множення матриць 4.1. Постановка задачі. Результатом множення матриці A розмірністю nm× й матриці B розмірності ln× є матриця C розмірності lm× , кожен елемент якої обчислюється наступним чином: ljmibac n k kjikij <≤<≤×=∑ − = 0,0, 1 0 . Цей алгоритм вимагає lnm ×× опе- рацій множення й додавання елементів матриць. При множенні квадратних мат- риць розмірності nn× кількість викона- них операцій має порядок )( 3nO . Необхід- но побудувати паралельний алгоритм, який буде виконувати множення матриць за найкоротший час для довільної архітек- тури кластера. 4.2. Блочний алгоритм. Для експе- рименту було обрано наступну паралельну модифікацію послідовного алгоритму: Рис. 2 Схема множення Якщо ми множимо дві квадратні матриці розмірністю nn× , то результуюча матриця C буде тієї самої розмірності, що й вхідні матриці A і B . Спочатку матриця C розбивається на прямокутні блоки роз- мірністю yCount n xCount n × , де xCount та yCount – кількість блоків по вертикалі й горизонталі. Кожен з цих блоків обчислю- ється незалежно окремою під-задачею, для чого під-задача потребує блок матриці A розмірністю xCount nn× й аналогічний блок матриці B розмірністю n yCount n × . Перевагою такого алгоритму є те, що задачу можна розбивати на довільну кількість підзадач, а не тільки на квадратні блоки. Також відсутність будь-яких зале- жностей між підзадачами дозволяє ефек- тивно виконувати обчислення у випадку коли кількість наявних процесорів значно менша за кількість під-блоків – у такому випадку підзадачі отримують нові блоки «за готовністю». Недоліком є додаткові витрати пам’яті, які виникають при частковому дублюванні вхідних даних для різних під- задач. Загальна кількість операцій не від- різняється від послідовного алгоритму й має порядок )( 3nO . Кожна підзадача виконує )12( −×× n yCount n xCount n скалярних опе- рацій. Тому час обрахунків кожної під- задачі буде рівним: Паралельне програмування 34 τ×−××= )12()( n yCount n xCount ncalcT . Оцінка комунікаційних затрат для кожної під-задачі буде наступною: yCountxCount n yCount n xCount nTCount ⋅ ++= 222 , β ×ω +α= TCountcommT )( , де α – латентність, β – пропускна здат- ність мереж, ω – розмір елемента матриці в байтах. Для реалізації обчислень була обра- на схема «постачальник – споживач» в якій підготовкою, розсилкою даних, а також обробкою результатів обчислень займається задача – «постачальник». Об- числення виконуються на «споживачах». Перевагою такої схеми є відсутність затрат на синхронізацію обчислень й міні- мальний час очікування «споживачів», особливо коли кількість під-задач значно більше кількості задіяних процесорів. Недоліком є використання додаткового процесора для «майстра», який не приймає участь в обчисленнях. 4.3. Математична потокова модель. Розглянемо випадок P однакових серверів з окремою пам’яттю та незалежними кана- лами зв’язку (рис. 3). )(1 tuμ )(2 tuμ )(1 tq )(2 tq )(tqP )(tuPμ . . . 1)( ≤tui Рис. 3. P однакових серверів з окремою пам’яттю Обмеження на керування мають вигляд: ∑ ≤ i i tv 1)( , 1)(0 ≤≤ tvi , Pi ,...,1= , 1)(0 ≤≤ tui , Pi ,...,1= . Будемо вважати, що 0)( 0 =tqR , 0)( 0 =tqi , Pi ,...,1= . Якщо ρ<λmax , тоді визначимо фу- нкції маршрутизації ⎪⎩ ⎪ ⎨ ⎧ =λ >λ ρ λ = .0)(,0 ,0)(,)( )( t t n t tvi ,0)( =tqR& .0)( =tqR Час завантаження задач .max int 1 λ λ =T Черги на серверах дорівнюють tdvftq t i μ−ττ= ∫ 0 ))(()( при керуванні ⎩ ⎨ ⎧ = > = .0)(,0 ,0)(,1 )( tq tq tu i i i Введемо позначення int maxint max λ λ⋅λ =λ f f , де ).( intint λ=λ cf f Якщо μ<λmax f , то 12 TT = , де 2T – мінімальний час закінчення роботи. Якщо μ≥λmax f , то , ))(())(( int int maxint max int max 1 00 2 1 PP T dvfdvfT ff f T λ = λ λλ ⋅ λ λ =λ= =ττ=ττ=μ ∫∫ ∞ . int 2 μ λ = P T f Максимальна черга при цьому до- рівнює Паралельне програмування 35 .)( max intint max λ λ μ− λ = P tq f i Якщо ρ≥λmax , тоді визначимо фу- нкції маршрутизації ⎪⎩ ⎪ ⎨ ⎧ =λ >λ= .0)(,0 ,0)(,1 )( t t Ptvi .)(... )()()( 0 0 1 0 ∫ ∫∫ ττ⋅ρ− −ττ⋅ρ−ττλ= Κ t tt R dv dvdtq Час закінчення завантаження задач . int 1 ρ λ =T Максимальна черга .max int intmax λ λ ρ−λ=Rq Черги на серверах дорівнюють .))(()( 0 tdvftq t i μ−ττ= ∫ при керуванні ⎩ ⎨ ⎧ = > = .0)(,0 ,0)(,1 )( tq tq tu i i i Якщо μ<λmax f , то 12 TT = . Якщо μ≥λmax f , то , ))(())(( int int intint max 1 00 2 1 PP T dvfdvfT ff f T λ = λ ρλ ⋅ ρ λ =λ= =ττ=ττ=μ ∫∫ ∞ . int 2 μ λ = P T f Максимальна черга при цьому до- рівнює .max intint max λ λ μ− λ = n q f i Таким чином, час закінчення заван- таження дорівнює . ),min( max int 1 λρ λ =T Мінімальний час виконання . ),min( ,min int maxint int 2 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ λ⋅ λρ⋅λ μ⋅ λ = P P T f f Припустимо, що вхідний потік роз- ділено на k частин, і використаємо щойно отриману формулу. Для реальної системи виконуються співвідношення: ρ>λmax , μ>λmax f . Якщо Pk ≤ , то час виконання до- рівнює μ λ = kP T f k int . Якщо Pk > , то час обчислюється за формулою: ⎥⎦ ⎤ ⎢⎣ ⎡−⎥⎦ ⎤ ⎢⎣ ⎡ += P kk P kk TTT , (3) де [ ]a – ціла частина числа a . 5. Експериментальне підтвер- дження результатів Для перевірки отриманих результа- тів та обґрунтування подальших дослі- джень були проведені експерименти з обчислень добутку матриць на кластері Інституту програмних систем НАН Украї- ни. Конфігурація експериментального середовища приведена в табл. 1. Було взято матрицю з розмірами 4000 на 4000 елементів. Результати обчис- лень на одному процесорі для різних роз- різань матриці приведено в табл. 2. Паралельне програмування 36 Таблиця 1 Операційна система: Scientific Linux 5 Тип системи 64-бітна ОС Процесори 2хIntel® Xeon® Processor E5405 Quad Core Кількість ядер 4 Кількість пото- ків 4 Об’єм L2-кеша 12 Mb Об’єм операти- вної пам’яті 16 Gb На основі даних табл. 2 виконано апроксимацію функції )(⋅cf та інших па- раметрів моделі (1). В результаті ми отри- мали змогу оцінити час виконання задачі для довільної кількості однорідних проце- сорів. На рис. 4 показані криві – залеж- ність часу виконання (вертикальна вісь) від способу розбиття (кількості блоків на які ділиться матриця – горизонтальна вісь) для різної кількості процесорів. Таблиця 2 № Кількість частин Час на множен- ня однієї части- ни (секунди) 1 1 2286.21 2 2 1072.28 3 4 683.25 4 8 260.25 5 16 130.43 6 20 103.41 7 25 82.97 8 32 63.69 9 40 51.03 10 64 32.48 11 80 26.04 12 100 20.81 13 128 14.8 Для перевірки моделі були здійснені екс- перименти обчислення часу виконання для 2 і 3 процесорів. На рис. 5 показані порів- няння отриманих кривих. Рис. 4. Залежність часу виконання від способу розбиття для різної кількості процесорів Паралельне програмування 37 Рис. 5. Теоретична (неперервна лінія) і експериментальна (пунктирна лінія) криві для 3 і 2 процесорів Висновки У даній роботі досліджувалась мо- дель керування ресурсами в однорідному багатопроцесорному середовищі. Запропо- новано підхід на основі керованих потоко- вих моделей, який дозволяє отримати оптимальне у сенсі швидкодії керування. Для задачі множення матриць було отри- мано аналітичний вид часу закінчення роботи в залежності від параметрів розпа- ралелювання та відповідне екстремальне керування. Виконані експерименти на кластері Інституту програмних систем підтверджують теоретичні результати роботи. 1. Srinivasa Prasanna G.N., Musicus B. Gener- alized Multiprocessor Scheduling Using Op- timal Control // Proc. SPAA. – 1991. – P. 216 – 228. 2. Foster I., Kesselman C. The Grid: Blueprint for a new Computing Infrastructure. Morgan Kaufmann, 2004. – 676 p. 3. Shivaratri N.G., Krueger P., Singhal M. (1992, December). Load distribution for lo- cally distributed systems. IEEE Computer 8 (12), P. 33 – 44. 4. Chronopoulos A.T., Penmatsa S., Yu N. Scalable Loop Self-Scheduling Schemes for Heterogeneous Clusters // Proc. of IEEE Intern. Conf. on Cluster Computing, Chicago, Illinois, USA, 2002. – P. 353 – 359. 5. Tantawi A.N., Towsley D. Optimal static load balancing in distributed computer systems // J. of the ACM, 32 (2), 1995. – P. 445 – 465. 6. Tang X., Chanson S.T. Optimizing static job scheduling in a network of heterogeneous computers // Proc. of the Intern. Conf. on Par- allel Processing, 2002. – P. 373 – 382. 7. Ross K.W., Yao D.D. Optimal load balancing and scheduling in a distributed computer sys- tem // Journal of the ACM, 38 (3), 1991. – P. 676 – 690. 8. Grosu D., Chronopoulos A.T. A game- theoretic model and algorithm for load bal- ancing in distributed systems // In Proc. of the 16th IEEE Intern. Parallel and Distributed Processing Symposium, Ft Lauderdale, Flor- ida, USA, 2002. – P. 146 – 153. 9. Grosu D., Chronopoulos A.T. Noncooperative load balancing in distributed systems // J. of Parallel and Distributed Computing, 65 (9), 2005. – P. 1022 – 1034. 10. Kwok Y.K., Hwang K., Song S. Selfish grids: Game-theoretic modeling and nas/psa bench- mark evaluation // IEEE Trans. on Parallel and Distributed Systems, 18 (5), 2007. – P. 621 – 636. 11. Ghosh P., Roy N., Das S.K., Basu K. A pricing strategy for job allocation in mobile grids using a non-cooperative bargaining the- ory framework // J. of Parallel and Distributed Computing, 65 (11), 2005. – P. 1366 – 1383. 12. Kwok Y.K., Song S., Hwang K. Selfish grid computing: Game-theoretic modelling and nas performance results // In Proc. of the CCGrid, 2005. – P. 1143 – 1150. 13. Hui C.C., Chanson S.T. (1999, July-Sept.). Improved strategies for dynamic load balanc- ing. IEEE Concurrency, 7 (3), 1999. – P. 58 – 67. Паралельне програмування 38 14. Campos L.M., Scherson I. Rate of change load balancing in distributed and parallel sys- tems // Parallel Computing, 26 (9), 2000. – P. 1213 – 1230. 15. Corradi A., Leonardi L., Zambonelli F. Diffu- sive load-balancing policies for dynamic ap- plications // IEEE Concurrency, 7 (1), 1999. – P. 22 – 31. 16. Lee S.H., Hwang C.S. A dynamic load bal- ancing approach using genetic algorithm in distributed systems // In Proc. of the IEEE Intl. Conf. on Evolutionary Computation, 1998. – P. 639 – 644. 17. Nazarathy Y., Weiss G. A Fluid Approach to Large Volume Job Shop Scheduling // J. of Scheduling, 13 (5), 2010. – P. 509 – 529. 18. Meyn S. Control Techniques for Complex Networks. – Cambridge University Press, 2007. – 582 p. 19. Милютін А.А., Дмитрук А.В., Осмоловский М.П. Принцип максимума в оптимальном управлении. – М.: Изд-во МГУ, 2004. – 168 с. Отримано 28.01.2011 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, докторант, Іваненко Павло Андрійович, аспірант. Місце роботи авторів: Інститут програмних систем НАН України, 03187, Київ - 187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. e-mail: o.ignatenko@gmail.com

One model of optimal resource allocation in homogeneous multiprocessor system

Репозитарії

Схожі ресурси