Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



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

Скачати 287.67 Kb.

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




Скачати 287.67 Kb.
Сторінка1/3
Дата конвертації13.04.2017
Розмір287.67 Kb.
ТипАвтореферат
  1   2   3


Національний університет “Львівська політехніка”

Тичковський Роман Олександрович

УДК 004.75




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

Спеціальність 01.05.

Програ́мне забезпе́чення (програ́мні за́соби) (ПЗ; англ. software) - сукупність програм системи обробки інформації і програмних документів, необхідних для експлуатації цих програм.

03 – математичне та програмне



забезпечення обчислювальних машин і систем

Автореферат

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

кандидата технічних наук
Львів – 2010

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


Робота виконана у Львівському національному університеті імені Івана Франка

Міністерства освіти і науки України



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

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



Цегелик Григорій Григорович,

Львівський національний університет імені Івана Франка, завідувач кафедри математичного моделювання соціально-економічних процесів



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

доктор технічних наук, доцент



Пелещишин Андрій Миколайович,

Національний університет “Львівська політехніка”,

проф.

Математи́чне моделюва́ння (рос. моделирование математическое; англ. mathematical simulation, нім. mathematische Modellierung f) - метод дослідження процесів або явищ шляхом створення їхніх математичних моделей і дослідження цих моделей.

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

Технічні науки - науки, що вивчають закономірності розвитку техніки і визначають способи найкращого її використання.

кафедри інформаційних систем та мереж

кандидат технічних наук, доцент



Томашевський Олег Михайлович,

Львівська філія Європейського університету,

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

Захист відбудеться “17” червня 2010р.

Інформацíйна систéма (англ. Information system) - сукупність організаційних і технічних засобів для збереження та обробки інформації з метою забезпечення інформаційних потреб користувачів.

Європе́йський університе́т - недержавний приватний вищий навчальний заклад IV рівня акредитації в Україні. Заснований в 1991 р. родиною вчених - Тимошенком Іваном Івановичем, його дружиною Зоєю Іванівною та їх донькою Оленою Іванівною.

о 1400 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, м. Львів, вул. С. Бандери, 12).


З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська політехніка” (79013, м. Львів, вул. Професорська, 1)
Автореферат розісланий “ ” __________ 2010 р.

Вчений секретар

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

доктор технічних наук, професор Р. А. Бунь


Загальна характеристика роботи

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

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

Інформаці́йні техноло́гії, ІТ (використовується також загальніший / вищий за ієрархією термін інформаційно-комунікаційні технології (Information and Communication Technologies, ICT) - сукупність методів, виробничих процесів і програмно-технічних засобів, інтегрованих з метою збирання, опрацювання, зберігання, розповсюдження, показу і використання інформації в інтересах її користувачів.

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

Обчи́слювальні ресу́рси - можливості, забезпечувані компонентами обчислювальної системи, що витрачаються (зайняті) в процесі її роботи.

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

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

Розподі́лені обчи́слення (розподілена обробка даних) - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу.

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

Розроблені математичні моделі є задачами математичного програмування, які належать до класу NP-повних і для яких не існує ефективних алгоритмів розв’язування.

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

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

Глобальна система Інтернет є унікальним інформаційним ресурсом, який об’єднує величезні обсяги інформації. Основними складовими цього ресурсу є сторінки – атомарні одиниці інформації з унікальним наповненням, об’єднані між собою логічними зв’язками. Найпопулярнішим методом навігації користувача по системі Інтернет є використання пошукових серверів (пошукових систем). Однак ефективність пошуку потрібної інформації користувачем в значній мірі залежить від вибраної стратегії пошуку. Можна послідовно переглядати сторінки, а можна певним чином прискорити пошук, розбивши сторінки на блоки або організувавши спеціальний каталог. Тому актуальною є проблема оптимальної організації доступу до інформації інтернет-серверів з боку користувачів.

Теоретичною та методологічною основою дослідження стали праці таких вчених, як Р. Касі, В. Чу, Д. Кнута, Дж. Мартіна, Г. Г. Цегелика, О.В. Деми­довича, Я. Фостера, К. Кессельмана, А.М. Пелещишина та ін., а також аналіз існуючих систем опрацювання інформації, в основі яких лежить концепція розподілених баз даних та розподілених обчислень. При проведенні дослідження використано підхід, запропонований керівником дисертаційної роботи Г. Г. Цегеликом.

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася у рамках науково-дослідних тем кафедри математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка:


  1. “Побудова та аналіз математичних моделей оптимальної організації та доступу до інформації баз даних для однопроцесорних та багатопроцесорних ЕОМ”, № держ.

    Льві́вський націона́льний університе́т і́мені Іва́на Франка́ (у 1918-1939 - Університет Яна Казимира) - один із найстаріших університетів України та Східної Європи та найпрестижніших в Україні. Заснований у 1784 імператором Йосифом ІІ з латинською мовою викладання.

    реєстрації 0103U001083 (1999 – 2005рр.). Автором проаналізовано деякі математичні моделі оптимального розподілу файлів розподіленої бази даних серед вузлів обчислювальних мереж та розроблено евристичний метод реалізації однієї з моделей, досліджена ефективність використання евристичного і генетичного алгоритмів для розв’язування задачі оптимального розподілу інформаційних ресурсів серед вузлів комп’ютерних мереж.

    Інформаці́йні ресу́рси (Information resources) - документи і масиви документів в інформаційних системах (бібліотеках, архівах, фондах, банках даних, депозитаріях, музейних сховищах і т.і.). Розрізняють інформаційні ресурси державні та недержавні.



  2. “Математичне моделювання природничих, інформаційних та соціально-економічних процесів”, № держ. реєстрації 0106U005905 (2006-2008рр.). Автором досліджена ефективність доступу користувачів до інформації інтернет-серверів для різних законів розподілу ймовірностей звертання до сторінок.

  3. “Математичне та комп’ютерне моделювання природничих, інформаційних та соціально-економічних процесів. Розробка інтелектуальних систем підтримки прийняття рішень”, № держ. реєстрації 0109U004325 (2009 – 2011рр.). Автором проведено дослідження ефективності еволюційних алгоритмів при розв’язуванні задач дискретної оптимізації.

    Комбінаторна оптимізація (англ. Combinatorial optimization) - розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної.

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



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

Мета дисертаційної роботи визначає необхідність розв’язання таких завдань:



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

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

    Генети́чний алгори́тм (англ. genetic algorithm) - це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.



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

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

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

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

    Інформаці́йний по́шук (ІП) (англ. Information retrieval) - наука про пошук неструктурованої документальної інформації. Особливо це відноситься до пошуку інформації в документах, пошук самих документів, добуття метаданих з документів, пошуку тексту, зображень, відео та звуку у локальних реляційних базах даних, у гіпертекстових базах даних таких, як Інтернет та локальні інтранет.



Об’єктом дослідження є розподіл ресурсів серед вузлів комп’ютерних мереж.

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

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

Тео́рія організа́ції - є системою знань про закономірності функціонування та розвитку організаційних відносин в природі та суспільстві.

Чи́сельні ме́тоди - методи наближеного або точного розв'язування задач чистої або прикладної математики, які ґрунтуються на побудові послідовності дій над скінченною множиною чисел. Основні вимоги до чисельних методів, щоб вони були стійкими та збіжними.

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

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

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

Експериме́нт (англ. experiment) - сукупність дослідів, об’єднаних однією системою їх постановки, взаємозв’язком результатів і способом їх обробки. В результаті експерименту отримують сукупність результатів, які допускають їхню сумісну обробку і зіставлення.



Наукова новизна одержаних результатів. В результаті проведених досліджень в дисертації отримано такі нові наукові результати:

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

    Зада́ча оптиміза́ції - задача знаходження точки (точок) мінімуму, або декількох мінімумів заданої функції.



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

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

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

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

    Крите́рій оптима́льності (рос. критерий оптимальности; англ. optimum criterion; нім. Optimalitätskriterium n) - основний показник якості роботи системи.



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

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

Основні результати, отримані при виконанні дисертаційної роботи, використано для розробки програмного комплексу оптимального навантаження вузлів кластера Львівської філії відкритого акціонерного товариства “Укртелеком” (м. Львів), оптимального розподілу файлів серед вузлів комп’ютерної мережі закритого акціонерного товариства “УВТК” (м.

Робоча станція (англ. workstation) - комплекс апаратних і програмних засобів, призначених для вирішення певного кола завдань.

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

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

Закрите акціонерне товариство (ЗАТ) - організаційно-правова форма юридичної особи, в якій в Україні створювались приватні акціонерні товариства в період з 1 жовтня 1991 р. до 30 квітня 2009 р. Протягом двох років (з 30 квітня 2009 р. до 30 квітня 2011 р.)

 Львів), Львівської філії “Промінвестбанку” (м. Львів), використані у НДР, виконаних на кафедрі математичного моделювання соціально-економічних процесів Львівського національного університету імені Івана Франка, а також впроваджені у навчальний процес на факультеті прикладної математики та інформатики Львівського національного університету імені Івана Франка: вони використовуються при читанні курсів “Основи інформаційних технологій” та “Сучасні інформаційні технології”, при написанні курсових та дипломних робіт.

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



Особистий внесок здобувача. Усі наукові результати, подані у дисертації, одержані здобувачем особисто. У друкованих працях, опублікованих у співавторстві, здобувачу належать: [1, 10] – евристичний алгоритм реалізації матема­тичних моделей визначення оптимальної кількості копій кожного файлу та їх розподілу серед вузлів комп’ютерних мереж; [2, 11] – розробка матем­атичних моделей використання процесорних потужностей вузлів комп’ютерних мереж; [3, 12] – знаходження оптимальних значень параметрів моделі оптимального доступу до інформації інтернет-серверів; [4] – опис запропо­нованого підходу до розробки математичних моделей оптимального розподілу ресурсів серед вузлів комп’ютерних мереж; [5, 21] – розробка математичної моделі оптимального доступу до інформації інтернет-серверів; [6, 25] – проаналізовано ефективність двох математичних моделей оптимального доступу до інформації серверів з боку користувача; [7, 14] – запропоноване кодування у генетичному алгоритмі, яке враховує структуру розв’язків задачі оптимізації розподілу копій файлів; [8, 15, 26] – евристичний метод знаходження оптимального розподілу задач серед вузлів кластера; [16, 19] – адаптація генетичного алгоритму до розв’язування узагальненої задачі про призначення; [18, 23] – порівняльний аналіз ефективності еврис­тичного і генетичного алгоритмів; [27] – реалізація мурашиного алгоритму розв’язування задачі оптимізації розподілу копій файлів; [13, 20] – використання методики штрафних функцій для врахування структури розв’язків задачі оптимізації розподілу копій файлів; [17, 24] – виведення співвідношень для визначення значень параметрів, за яких математичне сподівання досягає мінімуму.
  1   2   3


Скачати 287.67 Kb.

  • Науковий керівник
  • Пелещишин Андрій Миколайович
  • Загальна характеристика роботи Актуальність теми.
  • Зв’язок роботи з науковими програмами, планами, темами .
  • Львівського національного університету
  • Мета і завдання дослідження.
  • Наукова новизна одержаних результатів.
  • Практичне значення одержаних результатів.
  • Особистий внесок здобувача.