Ім'я файлу: пз.docx
Розширення: docx
Розмір: 1133кб.
Дата: 26.05.2023
скачати
Пов'язані файли:
16. 04. лекція Тригери на БТ.docx
Методичні вказівки до практичних занять з дисципліни «Комп’ютерн
Методичні вказівки до практичних занять з дисципліни «Комп’ютерн
Розширення: docx
Розмір: 1133кб.
Дата: 26.05.2023
скачати
Пов'язані файли:
16. 04. лекція Тригери на БТ.docx
Методичні вказівки до практичних занять з дисципліни «Комп’ютерн
Методичні вказівки до практичних занять з дисципліни «Комп’ютерн
3 ПРОГРАМНО ТЕХНІЧНЕ РІШЕННЯ ДЛЯ ВИРІШЕННЯ ЗАДАЧІ ПОШУКУ РАЦІОНАЛЬНОГО ВАРІАНТУ ПЕРЕВІРКИ ОБ’ЄКТІВ КОМП’ЮТЕРНОЇ МЕРЕЖІ
3.1 Структурна схема та призначення основних функціональних блоків
Для підвищення ефективності обчислювального процесу крім вибору оптимального алгоритму пошуку раціонального шляху також була розроблена система розподіленої обробки даних яка підвищує швидкість обчислювального процесу та зменшує вартість системи в цілому оскільки відпадає необхідність у придбанні багатопроцесорних систем обробки даних. Використання такої системи вимагає наявність певної кількості ЕОМ з’єднаних між собою високошвидкісним середовищем передачі даних та встановлених на ці ЕОМ спеціальних програмних модулів управління обчисленням які б перетворювали цю систему на обчислювальний кластер (Додаток Б).
До таких модулів відноситься:
модуль завантаження виконуваних завдань;
модуль балансування навантаження;
виконавчий модуль.
Модуль завантаження виконуваних завдань призначений для обробки клієнтських запитів, та завантаження об’єктів що призначений для запуску у кластері. Процес передачі об’єктів що призначені для запуску на виконання можливий завдяки використанні механізму серіалізації – перетворенні об’єкту у потік байтів. Оскільки основою паралельного виконаня є багатопотоковість задачі то і об’єкт що транслюється до кластеру повинен являти собою сконструйований, серіалізований потік. Оскільки дана система була побудована для використання у програмах розроблених на мові програмування JAVA то таким об’єктом являється клас що реалізує інтерфейс «Callable<T>», де «Т» це тип повертаємого значення.
Серіалізація об’єкту відбувається на клієнтській ЕОМ за допомогою спеціально розробленої бібліотеки. Таким чином усе що необхідно для того щоб ваш додаток виконував свій код у заздалегідь побудованому кластері це створювати програмні потоки за допомогою спеціально розробленої бібліотеки і не потребує вивчення додаткового синтаксису для розпаралелювання задачі. Звісно лише передати готовий об’єкт недостатньо щоб відновити його на сервері, оскільки відновлення об’єкту з потоку байтів неможливе без наявності вихідного байт коду на основі якого був створений об’єкт, тому для вирішення цієї проблеми був розроблений спеціальний модуль для завантаження байт коду з клієнтських ЕОМ. Даний модуль являєьбся об’єктом що наслідує системний клас «ClassLoader» та перевизначає його методи таким чином що під час відновлення об’єкту модулем завантаження виконуваних завдань даний клас звертається до клієнтської ЕОМ за вихідним байт кодом виконуваного об’єкту. Завантажений байт код зберігається у файлі у директорії що має ім’я відповідно до IP адресси клієнтської ЕОМ, це робится для того щоб байт коди з однаковим ім’ям не змішувались на стороні сервера.
Модуль балансування навантаження відповідає за рівномірне завантаження всіх ЕОМ на яких запущена виконавча частина. Кожна виконавча частина одразу після старту встановлює зв'язок з модулем балансування навантаження та через встановлені проміжки часу перадає інформацію про завантаженя власного процесора. Під час обробки клієнтського запиту модуль завантаження виконуваних завдань звертається до модуля балансування навантаження шоб отримати адресу найменш завантаженого виконавчого серверу.
Після отримання адреси модуль завантаження виконуваних завдань передає об’єкт що призначений на виконання до виконавчої частини де він безпосередньо виконується та повертає результат до клієнтської ЕОМ (рисунок 3.1).
Рис.3.1- Структурна схема організації управління
3.2 Програмний модуль управління обчисленням
Велика обчислювальна складність задачі що вирішується зумовлює певні складності для побудови обчислювального середовища. Також необхідно враховувати що Мурашиний алгоритм що був вибраний як оптимальний передбачає створення великої кількості потоків в системі які повинні мати можливість використовувати спільні вхідні дані та володіти результатами виконання один одного. Для побудови системи, що б задовольнила усім цим вимогам була вибрана мова програмування JAVA, та операційна система Linux(Додаток А).
Оскільки елементарною одиницею споживання процесорного часу є потік то для розпаралелювання вихідної задачі для її роботи у обчслювальному кластері був розроблений протокол що дозволяє передавати через середовище передачі потоки з клієнтських ЕОМ. Дана можливість реалізована за допомогою технології серіалізації об’єктів. Серіалізация це процес збереження стану об'єкта в послідовність байт; десеріалізациі це процес відновлення об'єкта, з цих байт. Java Serialization API надає стандартний механізм для створення серіалізуемим об'єктів. Також додатки створені на мові програмування Java не залежать від операційних систем, тобто одного разу написаний додаток має змогу виконуватись як на ОС UNIX, APLE так і Windows. Мова програмування Java в порівнянні з іншими мовами програмування ( С та С++) має деякі додаткові переваги, наприклад динамічне зв’язування коду та параметризацію методів та класів. Також в мові програмування Java розроблений зручний для програміста програмний інтерфейс створення та керування потоками введення виведення. Усі розроблені додатки виконуються не безпосередньо на процесорі а у віртуальній машині, тобто віртуальна машина зчитує скомпільований байт код, аналізує його та посилає певні інструкції процесору. Також мова програмування Java надає програмісту можливість зміни стандартного способу завантаження вихідного коду під час створення нового об’єкту, що вкрай корисно при створенні об’єктів що завантажені з посторонньго джерела.
В якості базової операційної системи було використано ОС Linux. Вибір оснований на відмінній стабільності даної операційної системи, широкими можливостями щодо забезпечення безпеки інформації та наявністю мережевих служб для створення спільних мережевих тек що важливо для забезпечення спільної пам’яті обчислювального кластеру.
Для управління обчислювальним процесом був розроблений графічний додток, який має усі необхідні інструменти для побудови графів та має можливість зберігати побудований користувачем граф у вигляді файлу для його подальшої обробки за допомогою необхідного алгоритму. Також мається можливість виконувати обчислення на побудованому графі безпосередньо в створеному додатку за допомогою алгоритму повного перебору. Результат що буде виданий алгоритмом відображається на побудованому користувачем графі, що спрощує роботу користувача по обробці результатів. Для демонстрації роботи алгоритмів також був розроблений модуль випадкової генерації вхідних даних для обрахунків.
3.3 Опис алгоритмів обробки даних
Мурашиний алгоритм (алгоритм оптимізації мурашиної колонії, англ. ant colony optimization, ACO) — один з ефективних поліноміальних алгоритмів для знаходження наближених рішень задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах. Підхід запропонований бельгійським дослідником Марко Доріго (англ. Marco Dorigo). Суть підходу полягає в аналізі та використанні моделі поведінки мурах, що шукають дороги від колонії до їжі. В природі, мурахи (початково) блукають довільним чином, і по знаходженні їжі повертаються до колонії, залишаючи по собі феромоновий слід. Якщо інші мурахи знаходять такий шлях, вони схильні припинити свої блукання, натомість слідувати позначеним шляхом, посилюючи його під час повернення у разі знайдення їжі.
В природі, мурахи (початково) блукають довільним чином, і по знаходженні їжі повертаються до колонії, залишаючи по собі феромоновий слід. Якщо інші мурахи знаходять такий шлях, вони схильні припинити свої блукання, натомість слідувати позначеним шляхом, посилюючи його під час повернення у разі знайдення їжі (рисунок 3.2).
Однак, з часом, феромонові шляхи випаровуються, тоді привабливість шляхів зменшується. Чим більше часу потрібно мурасі, щоб подолати дорогу, тим більше часу мають феромони, щоб випаруватись. Натомість, короткий шлях проходиться частіше, отже щільність феромонів стає більшою на короткому шляху. Випаровування феромонів також надає перевагу уникнення локально найкращих шляхів. Якби випаровування не відбувалось взагалі, шляхи обрані першим мурахою тяжіли б стати вкрай привабливими для наступних. В цьому разі, розвідка можливих шляхів була б обмежена.
Рисунок. 3.2 - Природні спостереження за рухом мурах
Таким чином, коли мураха знаходить вдалий (тобто короткий) шлях з колонії до джерела їжі, інші мурахи швидше слідуватимуть йому, і позитивний зворотний зв'язок зрештою призведе до обрання цього шляху всіма мурахами. Ідея мурашиного алгоритму полягає в наслідуванні поведінки з «симулятором мурахи», що прогулюється графом, який представляє проблему, що треба розв'язати.
Первісна ідея прийшла зі спостереження за використанням харчових ресурсів серед мурах, де мурахи, окремо обмежені в своїх пізнавальних можливостях, колективно здатні знайти найкоротший шлях між джерелом їжі і гніздом.
Перша мураха знаходить джерело їжі, через якийсь шлях, тоді повертається до гнізда, залишивши позаду слід з феромонів
Мурахи без розбору обирають всі чотири шляхи, але підсилення основної стежки робить її привабливішою як найкоротший шлях.
Мурахи обирають коротшій шлях, довгі відтинки втрачають щільність феромонового сліду. В серії дослідів на колонії мурах з вибором між двома різно довгими шляхами до джерела їжі, біологи спостерігали, що мурахи тяжіють до використання найкоротшого шляху. Модель, що пояснює таку поведінку така:
мураха (звана «бліц») рухається більш-менш випадково по колонії;
якщо вона знаходить джерело їжі, вона повертається прямо до гнізда, залишаючи по собі феромоновий слід;
ці феромони заманливі, ближні мурахи схилятимуться до слідування, більш чи менш точно, цим шляхом;
повертаючись до колонії, мурахи підсилюватимуть маршрут;
якщо наявні два шляхи до одного й того самого джерела їжі тоді, за певний час, коротшій шлях пройде більше мурах ніж довшій;
короткий шлях все більш посилюватиметься, і таким чином ставатиме привабливішим;
довгий шлях з часом зникне, бо феромони вивітряться;
зрештою, всі мурахи визначатимуть і через це обиратимуть найкоротшій шлях.
Мурахи використовують навколишнє середовище як посередник для зв'язку. Вони обмінюються інформацією не прямо, а через відкладання феромонів, які уточнюють статус їхньої роботи. Інформація розповсюджувана через феромони має місцеву дію, лише мурахи розташовані поруч із відкладеними феромонами помічають їх. Таку систему називають «Стіґмерґі» (англ. stigmergy) і вона трапляється в багатьох спільнотах соціальних тварин (її вивчали на прикладі розбудови стовпів у гніздах термітів). Спільне розв'язання проблем занадто складних для одного мурахи є хорошим прикладом самоорганізованої системи. Система покладається на позитивний зворотній зв'язок (відкладення феромонів приваблюють інших мурах, які підсилять їх у свою чергу) і негативний (зникнення маршруту через випаровування забезпечує оптимальність роботи системи). Теоретично, якщо щільність феромонів залишатиметься постійною на всіх відтинках, жоден із шляхів не стане головним. Однак, через зворотній зв'язок, малі відмінності на підмаршрутах підсилюватимуться і дозволятимуть зробити вибір. Алгоритм зсуватиметься з нестабільного стану, де жоден з підмаршрутів не привабливіший за інші, у бік стабільного стану, де маршрут утворений з найсильніших підмаршрутів.
Ідея мурашиного алгоритму - моделювання поведінки мурах, пов'язаного з їх здатністю швидко знаходити найкоротший шлях від мурашника до джерела їжі і адаптуватися до мінливих умов,знаходячи новий найкоротший шлях. При своєму русі мураха мітить шлях феромоном, і ця інформація використовується іншими мурашками для вибору шляху. Це елементарне правило поведінки і визначає здатність мурашок знаходити новий шлях, якщо старий виявляється недоступним. Розглянемо випадок, показаний на малюнку, коли на оптимальному досі шляху виникає перешкода. В цьому випадку необхідно визначення нового оптимального шляху. Дійшовши до перепони, мурахи з рівною ймовірністю будуть обходити її справа і зліва. Те ж саме буде відбуватися і на зворотному боці перепони. Однак, ті мурахи, які випадково виберуть найкоротший шлях, будуть швидше його проходити, і за кілька пересувань він буде більш збагачений феромоном. Оскільки рух мурах визначається концентрацією феромону, то наступні будуть віддавати перевагу саме цей шлях, продовжуючи збагачувати його феромоном до тих пір, поки цей шлях з якої-небудь причини не стане недоступний.
Формалізація руху мурах у вигляді алгоритму виконується наступним чином. У основі алгоритму лежить маркування вдалих доріг великою кількістю феромону. Робота починається з розміщення мурашок у вершинах графа (містах), потім починається рух мурашок — напрям визначається імовірнісним методом, на підставі формули:
(3.1)— ймовірність переходу по дорозі,
— довжина і-ого переходу,
— кількість феромонів на -ому переході,
— величина, яка визначає «жадібність» алгоритму,
— показник , яка визначає «стадність» алгоритму .
Результат не є точним і навіть може бути одним з гірших, проте, в силу імовірності рішення, повторення алгоритму може видавати (досить) точний результат.
Мурашиний алгоритм найефективніше підходить для вирішення задачі коммівояжера. Завдання формулюється як задача пошуку мінімального за вартістю замкнутого маршруту до всіх вершин без повторень на повному зваженому графі з n вершинами. Змістовно вершини графа є місцями, які має відвідати комівояжер, а ваги ребер відображають відстані (довжини) або вартості проїзду. Ця задача є NP-важкою, і точний переборний алгоритм її вирішення має факторіальних складність. Моделювання поведінки мурах пов'язано з розподілом феромона на стежці - ребрі графа в задачі комівояжера. При цьому ймовірність включення ребра в маршрут окремого мурашки пропорційна кількості феромону на цьому ребрі, а кількість відкладали феромона пропорційно довжині маршруту. Чим коротше маршрут, тим більше феромона буде відкладено на його ребрах, отже, більшу кількість мурах буде включати його в синтез власних маршрутів.
В математичній моделі після досягнення мурахою місця призначення відбувається онвленя феромону у всіх елементах графу які мураха використовувала за час свого прямування.
Моделювання такого підходу, використовує тільки позитивний зворотний зв'язок, призводить до передчасної збіжності - більшість мурашок рухається по локально оптимальному маршруту. Уникнути цього можна, моделюючи негативний зворотний зв'язок у вигляді випаровування феромону. При цьому якщо феромон випаровується швидко, то це призводить до втрати пам'яті колонії і забування хороших рішень, з іншого боку, великий час випаровування може привести до отримання стійкого локального оптимального рішення. Якість одержуваних рішень багато в чому залежить від настроювальних параметрів в ймовірнісно-пропорційному правилі вибору шляху на основі поточної кількості феромону і від параметрів правил відкладання і випаровування феромону. Можливо, що динамічна адаптаційна настройка цих параметрів може сприяти отриманню найкращих рішень. Важливу роль відіграє і початковий розподіл феромонів, а також вибір умовно оптимального рішення на кроці ініціалізації. Перспективними шляхами покращення мурашиних алгоритмів є різні адаптації параметрів з використанням бази нечітких правил та їх гібридизація, наприклад, з генетичними алгоритмами. Як варіант, така гібридизація може полягати в обміні через певні проміжки часу поточними найкращими рішеннями.вапрврв
Велика обчилювальна складність задачі що вирішується зумовлює певні складності для побудови обчислювального середовища. Також необхідно враховувати що Мурашиний алгоритм передбачає створення великої кількості потоків що повинні мати механізм обміну даними. Для побудови системи що б задовольнила усім цим вимогам була вибрана мова програмування JAVA, та операційна система Linux. Для управління побудованим середовищем обробки даних були розроблені спеціальні додатки які винують обчилення в окремих потоках та синхронізують результати.
Мурашиний алгоритм (алгоритм оптимізації мурашиної колонії, англ. ant colony optimization, ACO) — один з ефективних поліноміальних алгоритмів для знаходження наближених рішень задачі комівояжера, а також аналогічних завдань пошуку маршрутів на графах.
У основі алгоритму лежить поведінка мурашиної колонії — маркування вдалих доріг великою кількістю феромону, який буде приваблювати інших мурах що будуть проходити сусідніми шляхами.
4 ОЦІНКА ЕФЕКТИВНОСТІ ВИБОРУ РАЦІОНАЛЬНОГО ВАРІАНТУ ПОСЛІДОВНОСТІ ПЕРЕВІРКИ ОБ’ЄКТІВ КОМП’ЮТЕРНОЇ МЕРЕЖІ
4.1 Опис випробування та порівняльний аналіз результатів
В умовах реального часу досить часто доводиться швидко приймати рішення та діяти але вирішити задачі подібні до задач коммивояжера досить швидко шляхом повного перебору не є можливим. При вирішенні задачі коммівояжера шляхом повного перебору кількість можливих варіантів дорівнює факторіалу кількості вузлів що надто багато для вирішення на звичайних персональних комп’ютерах. На практиці можливості повного перебору закінчуються при кількості вузлів бльзькій до 60. Розроблена система вирішення задач комівояжера вирішує задачі з кількістю вузлів рівною декілька сотень за відносно прийнятні часові відрізки (1-2хв), а при збільшення вузлів обчилювального кластеру до десяти кількість вузлів у графі може бути рівною декільком тисячам. Виходячи з практичних випробувань які проводились з різною кількістю вузлів системи (10,30,50,100,300,400) можна сказати що використовувати метод повного перебору доцільно у тому випадку коли необхідне точне рішення задачі з невеликою кількістю вузлів графу (0-50). Також з результатів експерименту можна зробити висновок що відносна похибка при застосуванні мурашиного алгоритму на задачах невеликої розмірності має досить велике значення, тому застосовувати його до подібних задач нераціонально. При збільшенні кількості вузлів до 60 і загальної кількості зв’язків між вузлами близькій до 120 час очікування на знаходження відповіді шляхом повного перебору близький до нескінченності, чого неможна сказати про мурашиний алгоритм – при кількості вузлів рівній 600 і загальній кількості зв’язків між вузлами рівній 1200, тобто кожний елемент графу має приблизно 2 звязки з іншими вузлами, рішення видається за 0,2-1сек. Звісно мурашиний алгоритм не гарантує точності розвязку але при дотриманні всіх правил запуску мурах та правильного вибору налаштовуваних параметрів точність розвязку наближається до 98% (рисунок 4.1).
Рисунок 4.1 - Залежність часу виконання задачі від кількості вузлів:
Ох – кількість вузлів у графі
Оу – наближений час виконання (сек)
Виходячи з графіку на рисунку 4.1 можна сказати, що практична доцільність використання методу повного перебору вичерпується при кількості вузлів рівній 60.
4.2 Напрямки удосконалення прототипу системи
Для удосконалення розробленої платформи розподілених обчислень може бути розроблений WEB – інтерфейс управління обчилювальним кластером. Даний модуль надавав би додаткові можливості адміністратору по керуванню навантаженням на вузли кластеру та спрощував процес виявлення неполадок у системі. Також до напрямків подальшої роботи над удосконаленням системи можна віднести розробку WEB – сервісу який надавав би користувачам можливість будувати та вирішувати задачі на графах без необхідності встановлення будь-яких інших утиліт.
Для удосконалення роботи обчислювального кластеру в подальшому необхідно розробити процес забезпечення міграції виконуваних завдань між вузлами обчислювального кластеру. Дана можливість могла б забезпечити високий рівень надійності обчилень, оскільки при раптовому відключенні одного з вузлів виконувані на ньому завдання не припиняли б свою роботу.
При вирішенні задачі коммівояжера шляхом повного перебору кількість можливих варіантів дорівнює факторіалу кількості вузлів що надто багато для вирішення на звичайних персональних комп’ютерах. Розроблена система вирішує задачі з кількістю вузлів рівною декілька сотень за відносно прийнятні часові відрізки (1-2хв), а при збільшення вузлів обчилювального кластеру до десяти кількість вузлів у графі може бути рівною декільком тисячам. Виходячи з практичних випробувань які проводились з різною кількістю вузлів системи (10,30,50,100,300,400) можна сказати що використовувати метод повного перебору доцільно у тому випадку коли необхідне точне рішення задачі з невеликою кількістю вузлів графу (0-50). Для удосконалення роботи обчислювального кластеру в подальшому необхідно розробити процес забезпечення міграції виконуваних завдань між вузлами обчислювального компютерної мережі. Дана можливість могла б забезпечити високий рівень надійності обчилень, оскільки при раптовому відключенні одного з вузлів виконувані на ньому завдання не припиняли б свою роботу.
5 ЕКОНОМІЧНА ЧАСТИНА
Розробка нового програмно-технічного рішення передбачає розрахунок економічного ефекту від реалізації програмного продукту. Нова розробка повинна бути вигідною не тільки для розробника, а й для споживачів, підприємств, так як придбавши її, покупець сподівається зменшити витрати часу, ресурсів тощо. Отже необхідно оцінити економічний ефект для всіх сторін.
В економічній частині необхідно розрахувати:
- кошторис витрат на розробку нового програмно-технічного рішення ;
- експлуатаційні витрати, пов’язані з використанням нового програмно-технічного рішення ;
- обсяг роботи, яка може бути виконана з застосуванням нового програмно-технічного рішення;
- річний економічний ефект від впровадження нового програмно-технічного рішення;
- термін окупності витрат.
5.1 Розрахунок витрат на розробку програмно-технічного рішення
Собівартість продукції - це виражені в грошовій формі поточні витрати підприємства на її виробництво та реалізацію. Розрахунок собівартості проводиться прямим підрахунком по статтям калькуляції, так як цей метод дозволяє з достатнім ступенем точності оцінити витрати на розробку даного програмно-технічного рішення. Розрахуємо витрати на розробку по таких статтях витрат:
5.1.1 Основна заробітна плата розробників
Основна заробітна плата розробників розраховується за формулою:
(5.1)
=
де: М - місячний посадовий оклад конкретного розробника, грн.,
Тр - число робочих днів в місяці (Тр = 21-22)
t - число днів роботи розробника (дослідника).
Відомості про витрати на заробітну плату представлені в таблиці 5.1.
Таблиця 5.1 - Розрахунок заробітної плати
| № | Найменування посади | Місячний посадовий оклад, грн. | Оплата за робочий день, грн. | Число днів роботи | Витрати на заробітну плату, грн. |
| 1 | Спеціаліст з радіотехніки | 7450 | 413,89 | 18 | 7450,02 |
| 2 | Керівник | 7880 | 437,78 | 8 | 3502,24 |
| | Всього | | | | 10952,26 |
1 2 3 4 5 6 7 8