65517

Методи та алгоритми диспетчеризації завдань у розподілених комп’ютерних системах

Автореферат

Информатика, кибернетика и программирование

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

Украинкский

2014-07-31

572.5 KB

2 чел.

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова

тягунова МАРІЯ ЮРІЇВНА

УДК 004.75

МЕТОДИ ДИСПеТЧЕРИЗАЦІЇ ЗАВДАНЬ У РОЗПОДІЛЕНИХ КОМП’ЮТЕРНИХ СИСТЕМАХ

Спеціальність 05.13.05 – комп’ютерні системи та компоненти

Автореферат
дисертації на здобуття наукового ступеня
кандидата технічних наук

Київ – 2010


Дисертацією є рукопис.

Робота виконана в Запорізькому національному технічному університетi Міністерства освіти і науки України.

Науковий керівник

к.т.н., доцент

Кудерметов Равіль Камілович,

Запорізький національний технічний університет МОН України,

завідувач кафедри комп’ютерних систем та мереж

Офіційні опоненти:

доктор технічних наук, професор

Скобцов Юрій Олександрович,

Донецький національний технічний університет МОН України,

завідувач кафедри автоматизованих систем управління;

кандидат технічних наук, старший науковий співробітник

Кисельов Геннадій Дмитрович,

Навчально-науковий комплекс «Інститут прикладного системного аналізу» Національного технічного університету України «КПІ» МОН України,

доцент кафедри системного проектування.

Захист відбудеться «25» листопада 2010 р. о 14 годині
на засіданні спеціалізованої вченої ради Д 26.185.01
Iнституту проблем моделювання в енергетиці iм. Г.Є. Пухова НАН України за адресою:
м. Київ, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитися в бібліотеці Iнституту проблем моделювання в енергетиці iм. Г.Є. Пухова НАН України за адресою:
м. Київ, вул. Генерала Наумова, 15.

Автореферат розісланий  «19» жовтня 2010 р.

Вчений секретар спеціалізованої вченої ради,

кандидат технічних наук         Е.П. Семагіна


1

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. У теперішній час застосування розподілених і паралельних комп’ютерних систем та обчислень стає однією з основних умов успішного вирішення складних наукових і практичних задач, основою створення розподілених і віртуальних організацій, засобом для вирішення глобальних задач людства і фундаментом у загальній інформатизації суспільства. Сьогодні участь у міжнародних програмах стає стратегічним питанням інформаційного розвитку держав. Україна також стоїть на шляху науково-технічної інтеграції у європейський та світовий простір, про що говорить низка проектів, в яких Україна є повноправним учасником. Прикладом тому є створення національної GRID-інфраструктури – UkrGRID, що розвивається та успішно функціонує з 2002 року.

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

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

Розробці методів і засобів, що підвищують ефективність розподілених комп’ютерних систем (в т.ч. GRID-системи) присвячено безліч робіт. Значний внесок у розвиток даної галузі науки внесли роботи зарубіжних вчених: А. Доунея, Р. Гиббонса, М. Ливного, К. Кессельмана, Я. Фостера; науковців з країн СНД: Р.М. Алгуліева, Р.К. Алекперова, В.П. Гергеля, В.М. Коваленка, Є.І. Коваленка, Д.А. Корягіна, Е.З. Любимського, В.В. Топоркова; вчених з України: В.А. Гуменюка, І.А. Жукова, Г.М. Кременецького, А.І. Петренка.

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

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

Зв’язок роботи з науковими програмами і планами. Основні дослідження з теми дисертації проводилися на кафедрі комп’ютерних систем та мереж Запорізького національного технічного університету в рамках виконання науково-дослідних робіт за держбюджетною НТР № IT506-2007 «Створення національної Grid інфраструктури для забезпечення наукових досліджень» (номер державної реєстрації 0107U007931), у якій здобувач брала участь як виконавець.

2

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

Для досягнення поставленої мети необхідно виконати такі основні завдання:

1. Провести аналіз методів і систем диспетчеризації завдань у розподілених комп’ютерних системах;

2. Розробити математичну модель диспетчеризації завдань, що враховує тривалість виконання завдання на певному обчислювальному ресурсі розподіленої комп’ютерної системи;

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

4. Розробити структуру системи диспетчеризації завдань, що використовує розроблені методи у розподілених комп’ютерних системах.

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

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

Методи дослідження базуються на використанні теорії масового обслуговування, комбінаторики, методах штучного інтелекту, зокрема, нейронних мережах та генетичних алгоритмах.

Наукова новизна отриманих результатів:

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

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

3. Розроблено гібридний метод, який є ефективним для систем з кількістю завдань більшою за кількість комп’ютерів, та який є поєднанням методики знаходження рішення, що базується на принципах жадібних алгоритмів, і удосконаленого еволюційного методу;

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

Практичне значення отриманих результатів:

Розроблено гібридний алгоритм, що реалізує запропонований гібридний метод диспетчеризації завдань. Використання гібридного методу скорочує максимальний час виконання завдань у середньому на 28.4%, а сумарний – на 6.5% у порівнянні з алгоритмами FCFS і Backfill.

Розроблені структура диспетчера завдань, математичні моделі та методи диспетчеризації є основою планувальника завантаженості, апробованого на обчислювальних ресурсах Запорізького національного технічного університету та ВАТ «Мотор Січ» (акти впровадження). Розроблені методи диспетчеризації завдань можуть бути основою для розробки будь-якого іншого програмного забезпечення (ПЗ), спрямованого на оптимізацію управління розподіленими обчислювальними системами,

3

а запропонована структура диспетчера завдань дозволить скоротити час розробки цього ПЗ.

Отримані результати використовуються при вивченні дисциплін за напрямами «Основи теорії інтелектуальних систем», «Комп’ютерні системи», «Паралельні та розподілені системи», «Оптимізація в комп’ютерних системах та мережах» на кафедрі комп’ютерних систем і мереж Запорізького національного технічного університету (акт впровадження).

Особистий внесок здобувача. Всі основні положення і результати дисертаційної роботи, винесені на захист, отримано самостійно. У роботах, написаних у співавторстві, здобувачеві належать: [3] – застосування автоматичного вибору алгоритму сортування для задачі розподілення завантаженості в комп’ютерних системах; [9] – математична модель і застосування в якості методу розв’язання поставленої задачі нейронної мережі Хопфілда; [11] – застосування методів штучного інтелекту для диспетчеризації завдань у розподілених комп’ютерних системах; [12] – критерії для вибору алгоритму сортування; застосування алгоритмів сортування для диспетчеризації завдань; [13] – застосування паралельних генетичних алгоритмів для розв’язання оптимізаційних завдань; [16] – застосування навантажувальних модулів для високопродуктивних систем і можливий напрямок класифікації обчислювальних завдань.

Апробація результатів дисертації. Основні положення дисертаційної роботи та результати досліджень доповідалися і обговорювалися на 13 конференціях і семінарах: Седьмая Международная Конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Нижний Новгород, 2007 р.); Дев’ята Міжнародна науково-практична конференція TCSET’2008 (м. Львів-Славське, 2008 р.); Науково-технічні конференції «Тиждень науки» (м. Запоріжжя, 2008-2009 р.); Дев’ята Міжнародна науково-практична конференція «Сучасні інформаційні та електронні технології «СІЕТ-2008» (м. Одеса, 2008 р.); Четверта Міжнародна науково-практична конференція «Сучасні проблеми і досягнення в галузі радіотехніки, телекомунікацій та інформаційних технологій» (м. Запоріжжя, 2008 р.); Восьмая Международная Конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Казань, 2008 р.); Четверта Міжнародна науково-технічна конференція «Інформаційно-комп’ютерні технології 2008» (м. Житомир, 2008 р.); Четверта Міжнародна науково-технічна конференція «Гарантоздатні (надійні та безпечні) системи, сервіси та технології, DeSSerT-2009» (м. Кіровоград, 2009 р.); Десята Міжнародна науково-практична конференція «Сучасні інформаційні та електронні технології «СІЕТ-2009» (м. Одеса, 2009 р.), Одинадцята Міжнародна науково-практична конференція «Системний аналіз та інформаційні технології САІТ-2009» (Київ, 2009 р.); Девятая Международная Конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Владимир, 2009 р.); Одинадцята Міжнародна науково-практична конференція «Сучасні інформаційні та електронні технології «СІЕТ-2010» (м. Одеса, 2010 р.).

Публікації. Результати дисертації відображено у 17 публікаціях: 8 статей у провідних фахових журналах (з них 7 без співавторів), 9 тез доповідей на конференціях.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів оригінальних досліджень, висновків, списку використаних джерел. Вона містить 140 сторінок, із них 121 сторінка основного тексту, 19 рисунків і 10 таблиць, список використаних джерел з 113 найменувань на 14 сторінках, 3 акти впровадження.

4

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

Математичне обґрунтування необхідності розподілення завдань надано наступним чином. Нехай маємо n комп’ютерів та n задач. Позначимо через  число результатів, при яких жодна задача не буде розподілена оптимально. Тоді вірогідність того, що відбудеться збіг хоча б однієї пари «завдання – комп’ютер», які будуть відповідати оптимальному розподіленню завдань, дорівнює

.                                                        (1)

Обчислимо число . Для цього зазначимо, що

.                                          (2)

При несприятливому результаті перша задача, яку необхідно розподілити на перший комп’ютер, може бути розподілена на другий, третій, тощо, n-й комп’ютер. Нехай, наприклад, вона розподілена на другий комп’ютер. Якщо друга задача буде розподілена на перший комп’ютер, то для решти  задач маємо  несприятливих можливостей. Якщо ж другу задачу дозволяється розподілити тільки на третій, четвертий, тощо, n-й комп’ютер, то таких можливостей маємо . Отже, загальне число несприятливих можливостей, при яких перша задача розподіляється для розв’язання на другий комп’ютер, дорівнює . Такі ж значення одержимо, розподіляючи першу задачу на третій, четвертий, тощо, n-й комп’ютер. Отже, виконується (2).

Звідки витікає, що

                           (3)

оскільки , .

Розглянемо рівності:

,                                               (4)

,                                        (5)

... … …

.                                               (6)

Помножимо другу рівність (5) на n, а третю – на , тощо, і складемо. Одержимо наступну рівність:

5

                                (7)

Тоді, шукана вірогідність дорівнює:

.                  (8)

6

Таким чином, у результаті математичного обґрунтування необхідності оптимізації при диспетчеризації завдань у розподілених комп’ютерних системах доведено, що ймовірність того, що відбудеться збіг хоча б однієї пари «завдання – комп’ютер», які будуть відповідати оптимальному розподіленню завдань приблизно дорівнює 0.6. Це дає підставу для необхідності застосування деяких методів оптимізації процесу розподілення завдань на обчислювальні ресурси.

Змістовну постановку задачі диспетчеризації завдань у розподілених комп’ютерних системах представлено наступним чином.

Нехай до моменту часу t в обчислювальну систему, що складається з n комп’ютерів, для розв’язку надійшло деяке число завдань m, де n і m – деякі натуральні числа. Кожен комп’ютер має свої характеристики, однією з яких є потужність комп’ютера , . Кожне завдання має свою оціночну тривалість ,  для розв’язання на деякому певному комп’ютері з потужністю . Необхідно розподілити всі завдання для розв’язку в обчислювальній системі таким чином, щоб обчислювальні ресурси були використані найбільш ефективно.

Основними цілями планування обчислень є:

1. Мінімізація часу обробки запитів;

2. Обробка запитів за час, менший заданого;

3. Мінімізація максимального часу роботи вузла з обробки запиту;

4. Рівномірна завантаженість обчислювальних ресурсів;

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

Для досягнення кожної з поставлених цілей необхідно знати час розв’язання i-го завдання на j-му комп’ютері. Задамо це значення через . Знаходимо значення за наступною формулою:

.                                                        (9)

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

Для випадку, коли число завдань більше за число комп’ютерів, введемо наступні позначення.

Кількість завдань, яку необхідно розв’язати на j-му комп’ютері при оптимальному розподіленні завдань на існуючі ресурси задається числом .

Існує деяка матриця оптимального розподілення завдань, в якій кожен елемент може приймати такі значення:

 (10)

Необхідно оптимально розподілити завдання на комп’ютери.

6

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

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

знайти

 (11)

при дотриманні наступних умов:

1. Кожне завдання буде розв’язано на будь-якому з комп’ютерів лише один раз:

;                                                         (12)

2. Всі завдання, що надійшли для розв’язання, будуть розподілені для розв’язання на будь-якому з комп’ютерів:

;                                           (13)

3. Кількість завдань, розв’язуваних на комп’ютері j, при оптимальному розподіленні завдань дорівнює сумі одиниць, записаних до матриці оптимального розподілення завдань у стовпець j:

;                                                    (14)

4. При цьому всі комп’ютери будуть задіяні для розв’язання завдань, що надійшли:

;                                              (15)

5. Тривалість завдань, потужність комп’ютерів, кількість комп’ютерів та завдань існуючі, тобто

.                                             (16)

Вважаючи, що сумарна тривалість завдань, які необхідно розв’язати на
j-му комп’ютері при оптимальному розподіленні завдань, дорівнює (), то завжди будуть виконуватися такі умови:

7

,                                           (17)

.                                                (18)

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

Для досягнення цілі 1 (див. вище) – мінімізація часу обробки запитів – математична модель задачі виглядає наступним чином:

знайти

                                          (19)

за умови наступного обмеження:

,                                                 (20)

де  – обсяг необхідної оперативної пам’яті для i-го завдання ();

 – обсяг оперативної пам’яті j-го комп’ютера ().

Для досягнення цілі 2 – обробки запитів за час, менше заданого, будується математична модель аналогічно математичній моделі цілі 1 – мінімізація часу обробки запитів, але при цьому додатково вводиться час обмеження  і математична модель задачі приймає вигляд:

знайти

.                                              (21)

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

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

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

Модель 1. Знайти (11) при обмеженнях (12) – (18);

Модель 2. Знайти (19) при обмеженнях (12) – (18), (20);

Модель 3. Знайти (21) при обмеженнях (12) – (18), (20).

Перша математична модель описує класичну транспортну задачу з додатково введеними обмеженнями (12), (13), (15) – (18). При цьому введено ще одну цільову функцію та її критерій пошуку , при . Друга математична модель описує класичну транспортну задачу з додатково введеними обмеженнями (12), (13), (15) – (18) і (20). Третя математична модель має додатково введені обмеження (12), (13), (15) – (18) і (20) та змінений критерій пошуку – обмеження значенням часу . Таким чином, математична модель задачі

8

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

З метою вирішення задачі розподілення ресурсів для системи, в якій кількість завдань менше за кількість комп’ютерів, у роботі застосовано алгоритми сортування. При цьому постановку задачі надано наступним чином. Нехай є m завдань тривалістю рішення  і n комп’ютерів, на яких мають бути розв’язані завдання. Кожен з комп’ютерів має свою потужність . Оскільки , то доцільно буде, щоб найбільш тривалій задачі було надано найпотужніший комп’ютер. Таким чином, задача зводиться до сортування значень масиву обсягів завдань і значень масиву потужностей комп’ютерів обчислювальної системи. Далі, працюючи з вже відсортованими масивами, відсилаємо перше завдання з масиву тривалостей завдань на перший комп’ютер масиву потужностей комп’ютерів обчислювальної системи.

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

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

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

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

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

2. Елементи для використання обираються, починаючи від максимального до мінімального з існуючих можливих варіантів;

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

Друга частина гібридного методу використовує удосконалений еволюційний метод, а саме модифікований ГА. Він полягає в наступному:

1. Створення початкової популяції. Для цього випадковим чином обирається комп’ютер, який буде першим для проведення набирання необхідної суми, і випадковим чином обираються завдання для розв’язання на ньому, сума яких є потрібним значенням тривалості виконання на даному комп’ютері. Далі випадковим чином обирається наступний комп’ютер, і проводяться для нього аналогічні операції, далі наступний комп’ютер і так, поки не будуть задіяні всі комп’ютери системи. Описана в даному пункті послідовність виконується  раз, забезпечуючи, таким чином,  індивідів початкової популяції. Параметр d впливає на точність отриманих результатів і, в той же час, на обчислювальну складність алгоритму; m – кількість завдань, які необхідно розподілити в комп’ютерній системі;

9

2. Визначення функцій пристосованості для особин популяції (оцінювання). Функція пристосованості в даному випадку відома спочатку з математичної моделі поставленої задачі розподілення завдань в обчислювальній системі і є також цільової функцією, яка обчислюється тільки для тих випадків, коли всі завдання розподілені між комп’ютерами. Виражається вона у вигляді (11), а в разі необхідності у вигляді (19) або (21), в залежності від розв’язуваної задачі;

3. Вибір індивідів із поточної популяції. На даному етапі обирається тільки одне найкраще рішення, тобто тільки один індивід з найкращою функцією пристосованості;

3а. Потім виконується коригування значення суми тривалостей завдань, розподілених на кожний з комп’ютерів, до якого прагнули в п.1 і виконується перехід до п.3б, а не виконується перехід до п.4, як це робиться в класичному ГА;

3б. Далі виконуються дії, описані в п.1 – створюється нова популяція, але сума тривалостей завдань, що виконуються на кожному з комп’ютерів, до якої будемо прагнути, тепер дорівнюватиме значенню, знайденому в п.3а. Потім виконуємо пп.2, 3, 3а, 3б до тих пір, поки існує можливість знайти таке рішення;

4. Схрещування і/або мутація. Розділимо на дві частини даний етап: схрещування і мутацію. Спочатку розглянемо схрещування. Особливістю запропонованого ГА є те, що схрещування відбувається не між різними індивідами популяції, а всередині самого індивіда. Оскільки у розглянутій задачі мова йде про n комп’ютерів і m завдань, які необхідно розподілити на ці комп’ютери, то схрещування означає зміну номера виконуючого завдання комп’ютера для завдань, які «знаходяться» між двома точками кросовера. Комп’ютери, що використовуються при схрещуванні, вибираються такі, у яких сума тривалостей розподілених на них завдань мінімальна і максимальна. Тобто обираються випадковим чином дві точки кросовера та для  () змінюються між собою значення j (). Дана операція виконується лише раз, проводячи схрещування кожного разу тільки для найкращого отриманого рішення (тобто обов’язково після кожного разу схрещування виконуються пункти 5 і 6);

4а. Змінюємо номери комп’ютерів для завдань, що потрапляють на комп’ютер з сумарною тривалістю виконання завдань найменшою, починаючи від найбільш потужного комп’ютера – таким чином відбувається мутація. Далі виконуємо пп.5, 6, 7.

5. Обчислення функцій пристосованості для всіх особин. Дана операція проводиться аналогічно описаній в п.2;

6. Формування нового покоління (селекція). У вигляді формування нового покоління відбувається вибір найбільш пристосованого одного індивіда, обраного за результатами попередніх кроків алгоритму;

6а. Для обраного в п.6 індивіда за підсумками п.4 проводиться друга частина п.4 класичного ГА – мутація, тобто переходимо до п.4а;

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

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

На основі розробленого гібридного алгоритму створено програмну реалізацію гібридного методу.

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

10

Таблиця 1

Результати роботи гібридного алгоритму

Номер експери-менту

Кількість комп’ютерів, n

Кількість завдань, m

Кількість кроків коригування суми, k

Параметр точності, d

Час роботи алгоритму,

t (c)

1

5

15

5

2

0.049

2

5

60

1

2

0.701

3

5

70

3

2

2.234

4

5

90

2

2

3.539

5

5

100

1

2

3.207

6

5

170

2

2

24.500

7

5

180

1

2

19.457

8

10

100

4

2

14.528

9

20

100

5

2

32.303

10

30

100

8

2

66.667

11

40

100

6

2

66.140

12

50

200

8

2

930.654

13

60

200

9

2

1215.202

14

70

200

7

2

1101.171

15

50

200

8

1

5.000

16

50

2000

7

1

932.000

17

57

567

5

1

34.780

18

100

2000

9

1

2296.372

19

234

2345

15

1

115205.511

20

500

6000

8

1

167470.597

Пояснімо деякі наведені результати. Розглянемо експеримент під номером 6. Кількість комп’ютерів серед яких розподіляємо 170 завдань дорівнює 5. При цьому задача набула розв’язку при кількості кроків коригування . Параметр точності методу d при цьому дорівнює двом. Час знаходження рішення (час роботи алгоритму) дорівнює 24.5 секунди. Розглянемо експеримент під номером 7. При цьому кількість завдань становить 180, кількість кроків коригування , а час знаходження рішення дорівнює 19.457 сек. Зменшення часу роботи алгоритму при збільшенні кількості завдань пояснюється зменшенням кількості кроків коригування з двох до одного, що мають безпосередній вплив на час. Розглянемо експерименти під номерами 12 та 15. Зменшення часу знаходження рішення гібридним методом у 186 разів обумовлено зміненням значення параметру d з двох на одиницю, який безпосередньо впливає на оцінку складності методу і, звісно, на час роботи алгоритму.

11

а)

б)

Рис. 1. Залежність часу роботи гібридного алгоритму від кількості завдань (а) і кількості комп’ютерів (б)

Залежність часу роботи гібридного алгоритму від кількості завдань при п’яти комп’ютерах і кількості комп’ютерів при 200 завданнях представлено на рис. 1а і рис. 1б відповідно.

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

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

Теоретично обчислений час виконання алгоритму порядку . Параметр d може бути встановлений за бажанням, проте рекомендоване значення 1 або 2. У наведеному прикладі параметр d дорівнює двом.

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

12

Рис. 2. Структура диспетчера завдань

Структурно система диспетчеризації завдань містить такі модулі:

1. Модуль збору статистичної інформації. Надає відомості про доступні ресурси виконуючих комп’ютерів;

2. Модуль надання інформації про завдання. Являє собою файл оцінки завдань або ресурсний запит, що надають інформацію про необхідні для виконання завдання ресурси. Всі параметри встановлюються мінімально необхідними;

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

4. Основний модуль диспетчеризації завдань. Він безпосередньо проводить планування розподілення завдань серед комп’ютерів, спираючись на описані вище методи;

5. Клієнтський модуль диспетчеризації завдань:

запускає прийняте завдання на виконання;

пересилає отримані результати на серверну частину диспетчера по закінченню обчислень;

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

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

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

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

1. Завдання, які вимагають більших витрат оперативної пам’яті;

2. Завдання, які вимагають більших витрат процесорного часу;

13

3. Завдання, які вимагають високої пропускної спроможності мережі.

У табл. 2 наведено найбільш репрезентативні результати порівняння реалізованих програмно алгоритмів FCFS, Backfill і розробленого гібридного методу для однопроцесорних завдань.

Залежність продуктивності застосування гібридного методу від співвідношення кількості завдань до кількості комп’ютерів розподіленої комп’ютерної системи відображено на графіку (рис. 3).

На графіку пунктирною лінією позначено апроксимовані значення сумарного часу виконання завдань, нерозривною лінією – апроксимовані значення максимального часу виконання завдань на одному з комп’ютерів розподіленої системи.

Виходячи з результатів, наведених у табл. 2 та на рис. 3, можна зробити висновок, що найбільш ефективним є застосування гібридного методу для випадку, коли кількість завдань перевищує кількість комп’ютерів не більше, ніж у 20 разів.

Таблиця 2

Результати порівняння алгоритмів FCFS, Backfill та гібридного

Кіль-кість ком-п’юте-рів, n

Кіль-кість зав-дань, m

Сумарний час

Максимальний час

Гібридний алгоритм

FCFS, Backfill

Про-дуктив-ність, %

Гібрид-

ний алгоритм

FCFS, Backfill

Про-дуктив-ність, %

5

15

3

248.46

309.28

24.48

50.74

89.44

76.27

5

30

6

499.69

549.22

9.91

100.62

135.00

34.17

5

60

12

1002.15

1042.53

4.03

201.24

228.78

13.69

5

100

20

1640.11

1683.71

2.66

329.81

363.35

10.17

5

120

24

1999.57

2037.55

1.90

401.76

429.66

6.94

5

130

26

2137.84

2170.77

1.54

430.00

450.00

4.65

5

170

34

2802.09

2836.22

1.22

562.65

577.17

2.58

20

200

10

3275.42

3483.84

6.36

166.98

206.83

23.87

50

200

4

3269.63

3663.73

12.05

67.08

111.80

66.67

60

200

3.33

3272.96

3686.35

12.63

55.90

95.03

70.00

80

200

2,5

3090.53

3753.38

21.45

43.86

83.70

90.83

100

200

2

3109.88

3742.58

20.34

35.26

75.00

112.71

50

1000

20

16609.75

16998.06

2.34

335.00

373.86

11.60

50

100

2

1530.24

1893.86

23.76

35.26

65.00

84.34

50

400

8

6597.91

6999.87

6.09

134.31

167.70

24.86

100

2000

20

33287.73

33956.43

2.01

335.00

374.53

11.80

Рис. 3. Залежність продуктивності застосування гібридного методу від співвідношення кількості завдань до кількості комп’ютерів розподіленої комп’ютерної системи

14

З метою скорочення часу роботи гібридного алгоритму, що реалізує гібридний метод, було застосовано розпаралелювання этапу генерації рішень на двох процесорах. У середньому прискорення при використанні паралельного алгоритму на двох процесорах дорівнює 1.83, а продуктивність – 0.92, що говорить про ефективність використання паралельного ГА при реалізації гібридного методу для диспетчеризації завдань у розподілених комп'ютерних системах.

У даному розділі також наведено впровадження розроблених методів і алгоритмів у GRID-систему.

Розроблені математичні моделі, методи диспетчеризації і структура диспетчера завдань впроваджено у вигляді локального менеджера ресурсів дворівневого GRID на кластері Запорізького національного технічного університету (ЗНТУ), та апробовано на обчислювальних ресурсах ЗНТУ та ВАТ «Мотор Січ», що не входять до складу кластера, як на прикладі диспетчера однорівневого GRID.

ВИСНОВКИ

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

Зокрема, отримано такі теоретичні та практичні результати:

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

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

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

4. Розроблено гібридний метод для диспетчеризації завдань у розподілених комп’ютерних системах з кількістю завдань більшою за кількість комп’ютерів. Він базується на принципах жадібних алгоритмів і удосконаленому еволюційному методі. Використання гібридного методу скорочує максимальний час виконання завдань у середньому на 28.4%, а сумарний – на 6.5%, у порівнянні з алгоритмами FCFS і Backfill;

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

6. Для підвищення ефективності системи диспетчеризації завдань запропоновано використання фактора надійності. Це полягає у прогнозуванні працездатності вузла розподіленої комп’ютерної системи. Необхідність даного прогнозування базується на тому, що якщо при плануванні розподілення завдань буде враховано комп’ютер, який є не працездатним на момент дійсного розподілення завдань, то доведеться наново переплановувати розподілення завдань, що потребує додаткових витрат часу;

15

7. Розроблено структуру системи диспетчеризації завдань, що використовує розроблені методи диспетчеризації у розподілених комп’ютерних системах, основною особливістю якої є наявність модулю групування завдань і комп’ютерів.

Перелік опублікованих автором робіт за темою дисертації:

  1.  Юрич М.Ю. Подход к оптимальному распределению заданий в вычислительной системе /М.Ю. Юрич // Комп’ютинг, Тернопіль: «Економічна думка». – 2008. – Том 7. – Випуск 1. – С. 27–34.
  2.  Юрич М.Ю. Забезпечення ефективності розподілу завдань в обчислювальній системі за допомогою генетичного  алгоритму / М.Ю. Юрич // Вісник Житомирського державного технологічного університету. Серія: Технічні науки. – Житомир. – 2008. – №4 (47) – С. 190–195.
  3.  Yurich M.Yu. Sorting algorithms for distribution of tasks in the computer system / M.Yu. Yurich, D.S. Barsukov, R.K. Kudermetov // Радіоелектронні і комп’ютерні системи. – 2009. – №5 (39). – С. 20-24.
  4.  Юрич М.Ю. Разработка методики построения прогнозируемо надежной вычислительной системы /М.Ю. Юрич // Науковий вiсник Чернiвецького національного унiверситету. Серiя: Комп’ютернi системи та компоненти. – 2009. – Випуск 446. – С. 55-58.
  5.  Юрич М.Ю. Математическая модель системы диспетчеризации задач /М.Ю. Юрич // Науковий вiсник Чернiвецького національного унiверситету. Серiя: Комп’ютернi системи та компоненти. – 2009. – Випуск 479. – С. 134-138.
  6.  Юрич М.Ю. Анализ систем управления заданиями в рамках grid /М.Ю. Юрич // Радіоелектроніка, Інформатика, Управління. – 2010. – №1 (22). – С. 144–152.
  7.  Юрич М.Ю. Гибридный алгоритм распределения задач в вычислительной системе / М.Ю. Юрич // Сборник научных трудов Донецкого национального технического университета. Серия: Информатика, кибернетика и вычислительная техника. – 2010. – № 12 (165) – С. 66–71.
  8.  Юрич М.Ю. Анализ систем и методов балансировки нагрузки вычислительных систем /М.Ю. Юрич // Науковий вiсник Чернiвецького національного унiверситету. Комп’ютернi системи та компоненти. – Випуск 1. – Т. 1. – 2010. – С. 14-19.
  9.  Юрич М.Ю. Распределение заданий в компьютерной системе на базе нейронной сети / М.Ю. Юрич, Р.К. Кудерметов // Материалы Седьмой Международной конференции-семинара «Высокопроизводительные параллельные вычисления на кластерных системах», 26–30 нояб. 2007 г., Нижний Новгород. – 2007. – С. 347-353.
  10.  Yurich M. An Optimal Distribution of Tasks in Parallel Computing System / M. Yurich // Proceedings of the International Conference «Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET’2008)», 19–23 Febr. 2008, Lviv–Slavsko, Ukraine. – 2008. – рр. 585-587.
  11.  Юрич М.Ю. Выбор метода решения проблемы управления вычислительными ресурсами / М.Ю. Юрич, Р.К. Кудерметов // Материалы Девятой Международной научно-практической конференции «СИЕТ-2008», 19 – 23 мая 2008 г., Одесса. – 2008. – С. 128.
  12.  Юрич М.Ю. Использование сортировки в задачах планирования нагрузки компьютерных сетей / М.Ю. Юрич, Д.С. Барсуков, Р.К. Кудерметов // Тези доповідей IV Міжнародної науково-практичної конференції, 24–26 верес. 2008 р., Запоріжжя. – 2008. – С. 137-139.

16

  1.  Юрич М.Ю. Параллельные генетические алгоритмы в задачах оптимизации / М.Ю. Юрич, Р.К. Кудерметов // Материалы Восьмой Международной Конференции-семинара «Высокопроизводительные Параллельные Вычисления на Кластерных Системах»,
    17 -22 нояб. 2008 г., Казань. – 2008. – С. 281-282.
  2.  Юрич М.Ю. Основные параметры файлов оценки в GRID / М.Ю. Юрич // Збірник тез доповідей щорічної науково-технічної конференції серед студентів, викладачів, науковців, молодих учених і аспірантів «Тиждень науки», 13–17 квітня 2009 р., Запоріжжя. – 2009. – Т.1. – С. 293-294.
  3.  Юрич М.Ю. Концепция повышения надежности вычислительных систем / М.Ю. Юрич // Материалы Десятой  Международной научно-практической конференции «СИЕТ-2009», 18 – 22 мая 2009 г., Одесса. – 2009. – Т.1. – С. 116.
  4.  Юрич М.Ю. Нагрузочные модули для высокопроизводительных систем / М.Ю. Юрич, Р.К. Кудерметов // Материалы Девятой Международной Конференции-семинара «Высокопроизводительные Параллельные Вычисления на Кластерных Системах», 2 – 3 нояб. 2009 г., Владимир. – 2009. – С. 421-423.
  5.  Юрич М.Ю. Решение задачи оптимального распределения заданий в вычислительной системе / М.Ю. Юрич // Материалы Одиннадцатой  Международной научно-практической конференции «СИЕТ-2010», 24–28 мая 2010 г., Одесса. – 2010. – С. 185.

АНОТАЦІЯ

Тягунова М.Ю. Методи та алгоритми диспетчеризації завдань у розподілених комп’ютерних системах. – Рукопис.

Автореферат дисертації на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – Комп’ютерні системи та компоненти. Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Київ, 2010.

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

У роботі формалізовано проблему диспетчеризації завдань у розподілених комп’ютерних системах у вигляді модифікованої транспортної задачі; розроблено метод для розв’язання задачі диспетчеризації завдань з числом завдань меншим за число комп’ютерів у розподіленій комп’ютерній системі, який базується на застосуванні алгоритмів сортування даних. Для систем з кількістю завдань більшим, ніж число комп’ютерів розроблено гібридний метод. Розроблений метод є поєднанням методики знаходження рішення, що базується на принципах жадібних алгоритмів, і удосконаленого еволюційного методу, а саме модифікованого ГА. Максимальний час виконання завдань при застосуванні гібридного алгоритму у порівнянні з алгоритмами FCFS та Backfill скорочується у середньому на 28.4%, а сумарний – на 6.5%.

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

17

АННОТАЦИЯ

Тягунова М.Ю. Методы и алгоритмы диспетчеризации заданий в распределенных компьютерных системах – Рукопись.

Автореферат диссертации на соискание ученой степени кандидата технических наук по специальности 05.13.05 – Компьютерные системы и компоненты. Институт проблем моделирования в энергетике им. Г.Е. Пухова НАН Украины, Киев, 2010.

Диссертация посвящена разработке методов диспетчеризации заданий в распределенных компьютерных системах, в частности, как элемента системы управления заданиями в GRID-системах, с целью максимально эффективного использования вычислительных ресурсов.

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

Разработан метод диспетчеризации заданий, основанный на применении алгоритмов сортировки данных для решения задачи с числом заданий меньшим, чем число компьютеров в распределенной компьютерной системе.

Разработан гибридный метод, эффективный для систем с количеством заданий большим, чем количество компьютеров, который является сочетанием методики нахождения решения, основанной на принципах жадных алгоритмов, и усовершенствованного эволюционного метода. При этом использование гибридного метода сокращает максимальное время выполнения заданий в среднем на 28.4%, а суммарное – на 6.5%, по сравнению с алгоритмами FCFS и Backfill.

Усовершенствован эволюционный метод, который позволяет приблизить результаты диспетчеризации к оптимальным при использовании гибридного метода и, в отличие от существующих методов, уже на первоначальном этапе формирования популяций выделить лучшее решение и далее только улучшать это значение за счет иначе построенной последовательности выполнения операторов классического ГА.

Для повышения эффективности системы диспетчеризации заданий предложено использование фактора надежности. Данное применение заключается в прогнозировании работоспособности узла распределенной компьютерной системы. Необходимость данного прогнозирования основана на том, что если при планировании распределения заданий будет учтен компьютер, который будет не работоспособным на момент действительного распределения заданий, то придется заново перепланировать распределение заданий, на что потребуются дополнительные расходы времени.

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

Разработанные математические модели, методы диспетчеризации и структура диспетчера заданий внедрены на кластере Запорожского национального технического университета (ЗНТУ) в качестве локального менеджера ресурсов двухуровневого GRID, и апробированы на вычислительных ресурсах ЗНТУ и OАO «Мотор Сич», не входящих в состав кластера, как на примере одноуровневого GRID.

Материалы диссертационной работы используются в учебном процессе в лекционных курсах и лабораторных работах по дисциплинам «Основы теории интеллектуальных систем», «Компьютерные системы», «Параллельные и

18

распределенные системы», «Оптимизация в компьютерных системах и сетях» на кафедре компьютерных систем и сетей ЗНТУ.

Ключевые слова: диспетчеризация заданий, распределенные компьютерные системы, GRID-системы, генетический алгоритм, оптимизация времени выполнения заданий, гибридный метод.

ABSTRACT

Tyagunova M.Yu. Methods for scheduling problems in distributed computer systems. – Manuscript.

Thesis for candidate’s degree in technical science by speciality 05.13.05 – Computer systems and components. – Pukhov Institute for Modelling in Power Engineering, NAS of Ukraine, Kiev, 2010.

The dissertation is devoted to development of methods for scheduling problems in distributed computer systems, particularly as part of task management in GRID – systems to the most efficient use of computing resources environment.

The problem of scheduling tasks in distributed computer systems is formalized as a modified transportation problem. A method based on the use of sorting algorithms for problem scheduling tasks solving is proposed; the method is oriented   in case where number of tasks is less than the number of computers in the distributed computer system. For systems with many more tasks than the number of computers the hybrid method is developed. This method is a combination of techniques based on the principles of greedy algorithms, and improve evolution methods, namely the modified genetic algorithm. Maximum execution time of tasks in the application of hybrid algorithm reduced on average by 28.4% in comparison with algorithms FCFS and Backfill, and the total time – by 6.5%.

Keywords: task scheduling, distributed computer systems, GRID-system, genetic algorithm, optimization time tasks, a hybrid method.

Підписано до друку 12.10.2010 р. формат 60х84 1/16 0,9 д.а. Тираж 120 прим. Зам. № 1714

69063, м. Запоріжжя, ЗНТУ, Друкарня, вул. Жуковського, 64


 

А также другие работы, которые могут Вас заинтересовать

35790. Лялька - мотанка 3.57 MB
  Коли нам запропонували теми для творчого проекту, я вирішила обрати саме «Лялька - мотанка в українському стилі». Адже мотанка — прадавній оберіг українського народу. Вона несе в собі сонячну енергетику, тепло людських рук, любов і турботу, з якою створена. Головне призначення ляльки — берегти душу свого власника від зла й нечистих помислів.
35791. Творческий проект «Сорочка» 5.51 MB
  Расчет себестоимости изготовления изделия План Изготовления изделия Изготовления изделия и проверка качества Самооценка и оценка 1.Задачи Провести исследование и разработать эскиз моего проектного изделия. Изготовить выкройку швейного изделия. Подобрать ткань для изделия.
35792. Выбор профессии 168 KB
  Появление профессии Определение интересов и склонностей Обоснование выбора Алгоритм профессион. самопределения Формула профессии Выявление индивидуальных характер. Выбор профессии – это большая ответственность которую очень важно осознать как можно раньше.
35794. Кружка. Творческий проект 158.5 KB
  4 Технологическая карта № детали № операции Название операции Эскиз Инструмент и приспособления 1 1 Выбрать заготовку с учётом припуска на обработку Линейка 2 Прострогать базовую сторону Верстак рубанок 3 Разметить и прострогать заготовку по толщине Линейка рубанок карандаш 4 Разметить и прострогать по ширине Линейка рубанок карандаш 5 Отторцевать заготовку Угольник карандаш подкладка 6 Разметить и отпилить заготовку по длине Верстак линейка угольник карандаш ножовка 7 Разметить заготовку по чертежу Линейка угольник карандаш...
35795. Вышивка своими руками. Творческий проект 1.18 MB
  Вышивание крестом – один из самых распространенных видов народного искусства. История возникновения вышивки крестом уходит далеко в глубь веков когда появился первый стежок сделанный первобытными людьми при скреплении шкуры убитого мамонта. Материалом для вышивки крестом служили: жилы животных нити льна хлопка конопли шелка шерсти а так же применяли натуральный волос. Особой популярности вышивка крестом достигла в Западной Европе в XVI столетии.
35796. Метод проектів на уроках трудового навчання (обслуговуюча праця) 461 KB
  Проектна технологія — практика особистісно зорієнтованого трудового навчання в процесі конкретної навчально-трудової діяльності учня, на основі його вільного вибору та з урахуванням інтересів. У свідомості учня це має такий вигляд: «Я знаю, для чого мені потрібно все, що я пізнаю, і де я можу ці знання застосувати». Для педагога це прагнення знайти розумний баланс між академічними і прагматичними знаннями, уміннями та навичками.
35797. ”Садово-городній інвентар” Прилад для виготовлення живильних горщиків 565.5 KB
  КОНСТРУКТОРСЬКИЙ ЕТАП Розробка конструкції прилада для виготовлення живильних горщиків. 8 Технологія виготовлення виробу ТЕХНОЛОГІЧНИЙ ЕТАП ЗАКЛЮЧНИЙ ЕТАП. Метою проекту є створення приладу для виготовлення живильних горщиків який здатен задовольнити попит найвибагливіших споживачів.