Державний вищий навчальний заклад

«Донецький національний технічний університет»

ЩЕРБАКОВА МАРИНА ЄВГЕНІВНА

УДК 004.045

БАЛАНСУВАННЯ НАВАНТАЖЕННЯ І ПЛАНУВАННЯ ЗАДАЧ ДЛЯ ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ КЕРУЮЧИХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ

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

05.13.05 - Комп’ютерні системи та компоненти

Автореферат

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

кандидата технічних наук

Донецьк – 2008

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

Робота виконана в Технологічному інституті Східноукраїнського національного університету імені Володимира Даля (м. Сєвєродонецьк) Міністерства освіти і науки України

Науковий керівник: | кандидат технічних наук, доцент

Рязанцев Олександр Іванович,

Технологічний інститут Східноукраїнського національного університету імені Володимира Даля

(м. Сєвєродонецьк),

завідувач кафедри «Комп’ютерна інженерія».

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

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

Філатов Валентин Олександрович,

Харківський національний університет радіоелектроніки, м. Харків,

професор кафедри «Штучний інтелект»;

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

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

Державний вищий навчальний заклад «Донецький національний технічний університет», м. Донецьк,

завідувач кафедри «Автоматизовані системи управління».

Захист відбудеться «19» червня 2008 р. о 14 год. на засіданні спеціалізованої вченої ради Д 11.052.03 Державного вищого навчального закладу «Донецький національний технічний університет» за адресою: 83000, м. Донецьк, вул. Артема, 58, навч. корп. 8, ауд. 704.

З дисертацією можна ознайомитися в бібліотеці Державного вищого навчального закладу «Донецький національний технічний університет» за адресою: 83001, м. Донецьк, вул. Артема, 58, навч. корпус 2.

Автореферат розісланий «15» травня 2008 р.

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

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

Д 11.052.03, к.т.н., доц. |

Г.В. Мокрий

ЗАГАЛЬНА|спільна| ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в Технологічному інституті Східноукраінського національного університету ім. В. Даля (м. Сєвєродонецьк) в рамках госпдоговору № 161 від 22.10.2003 р. із ЗАТ „Сєвєродонецьке науково-виробниче об'єднання „Імпульс” „Розробка підсистеми ведення складу виробу і автоматизації випуску конструкторської документації”, а також в рамках держбюджетних тем „Розробка програмно-технічного комплексу хімічного виробництва” (ДР №0104U000391), керівник – доцент Рязанцев О. І. і „Проектування муніціпальної комп’ютерної системи з використанням сучасних інформаційних технологій” (ДР №0103U007993), керівник – доцент Рязанцев О. І. У вказаних роботах автор брав безпосередню участь як виконавець.

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

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

- розробити метод оптимального балансування навантаження між комп'ютерами в мережевій системі керування;

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

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

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

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

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

Наукова новизна отриманих результатів полягає в наступному:

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

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

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

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

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

Використання розробленого методу планування задач дає можливість скоротити втрати часу на виконання задач верхнього рівня керування приблизно на 9 – 11%. Це досягається за рахунок збалансованого використання ресурсів робочої станції, а також за рахунок зменшення непродуктивних простоїв задач в чергах очікування звільнення послідовно використовуваних ресурсів, таких, як загальні таблиці баз даних, загальні канали зв'язку і т. д.

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

Розроблені методи були використані в пакеті прикладних програм КВАРЦ і перевірені на практиці при експлуатації пакету на об'єктах багатьох підприємств, зокрема, в Дніпропетровському метрополітені, на Дніпропетровському лакофарбному заводі, Лисичанському желатиновому заводі, Самарській ТЕЦ, Юльївському нафтогазоконденсатному родовищі, Хоростковському сахарному заводі.

Результати дисертаційного дослідження використані в навчальних курсах „Системне програмування”, „Системи цифрової обробки інформації” для студентів спеціальностей 7.091501 та 7.091502 в Технологічному інституті (м. Сєвєродонецьк).

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

Апробація результатів дисертації. Основні результати роботи обговорювалися на конференціях „Технологія 2002” (18-19 квітня 2002 р.), „Технологія 2003” (24-25 квітня 2003 р.), „Технологія 2004” (15-16 квітня 2004 р.), „Технологія 2006” (19 – 20 квітня 2006 р.), СТІ, м. Сєвєродонецьк; на 10 міжнародному молодіжному форумі „Радіоелектроніка і молодь у 21 столітті”, ХНУРЕ (20 – 21 квітня 2006 р., м. Харків); на 8 і 9 міжнародних науково-практичних конференціях „Університет і регіон”, СНУ ім. В.Даля (25-26 грудня 2002 р. і 24-25 грудня 2003 р., відповідно, м. Луганськ); на міжнародній науково-практичній конференції „Єдиний інформаційний простір 2004”, УГХТУ (2-3 грудня 2004 р., м. Дніпропетровськ); на 2 міжнародній науково-методичній конференції „Інформаційні технології в наукових дослідженнях і в навчальному процесі”, ЛНПУ (14-16 листопада 2006 р., м. Луганськ); на 2 міжнародній науково-технічній конференції „Моделювання і комп’ютерна графіка”, ДонНТУ (10-12 жовтня 2007 р., м. Донецьк).

Публікації. Основні результати дисертаційної роботи опубліковані в 20 друкованих роботах, з них: 4 статті у фахових виданнях ВАК України, 1 стаття в російському журналі; була взята участь у написанні 1 монографії та 1 навчального посібника; 11 тез доповідей опубліковано у виданнях міжнародних наукових конференцій, 2 - у збірках доповідей вітчизняних конференцій, 13 наукових робіт написані без співавторів.

Структура і об'єм дисертаційної роботи. Дисертаційна робота обсягом 153 сторінки складається із вступу, чотирьох розділів, висновків, списку використаних джерел із 133 найменувань на 11 сторінках, 1 додатку обсягом 5 сторінок. Дисертація містить 44 рисунка і 20 таблиць.

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

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

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

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

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

(1)

де Tij – час взаємодії програми j з програмою i; m – число програм, що виконуються робочою станцією, n – число програм, що виконуються контролером.

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

(2)

де Vi – об'єми пакетів даних, що передаються; Nj – число передач кожного з них.

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

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

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

Крок 1. Зобразимо комплекс програм у вигляді неорієнтованого зв'язного графа G = (U, V) з множиною вузлів V = {v1, v2, ... vn}, кожний з яких відповідає окремій програмі, і множиною ребер U = {u1, u2, ... um}, що відповідають зв'язкам між програмами. Кожному ребру [vi, vj] припишемо вагу c(i, j), що дорівнює витратам часу контролера на взаємодію між відповідними програмними модулями за умови, що один з них виконується робочою станцією, інший – контролером (рис. 1).

Рис. 1. Граф взаємозв’язків між програмами для мінімізації часу взаємодії програмних модулів

В графі на рис. 1 програмні модулі зі складу пакету програм АСКТП КВАРЦ представлені їхніми абревіатурами.

Крок 2. Додамо до графа ще два вузли: K і РС, що формально представляють контролер і робочу станцію відповідно. З вузлом К (контролер) з'єднаємо тільки ті вузли графа, які представляють програми, що використовують спеціальне обладнання контролера або ж виконують специфічні функції, які повинні завжди виконуватися контролером. Вагу таких ребер встановимо рівною нескінченності: c(К, j) = ?. Аналогічно, з вузлом РС (робоча станція) з'єднаємо ребрами тільки ті вузли графа, які мають обов'язково виконуватися робочою станцією, якщо такі є. Вага таких ребер c(i, РС) = ?.

Крок 3. Одержаний в результаті розширення модифікований граф взаємозв'язків між програмами можна розглядати як транспортну мережу з джерелом К і стоком РС. Завдання зводиться до знаходження мінімального розрізу побудованої таким чином мережі, приклад якої представлений на рис. 1.

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

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

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

(3)

де n і m – число програм, що виконуються контролером і робочою станцією відповідно; Pi – час виконання i-го програмного модулю контролером; Tij – час взаємодії i-го програмного модулю з контролера з j-м програмним модулем з робочої станції.

Як і в попередньому варіанті методу, відомо, які програмні модулі мають обов'язково виконуватися контролером, а які - робочою станцією.

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

Рис. 2. Граф взаємозв’язків між програмами для мінімізації часу виконання програм контролером

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

A – мінімальний розріз такої транспортної мережі (рис. 2), UA – множина ребер, які входять до мінімального розрізу. Тоді сума вагів ребер розрізу має бути мінімальною: |

(4)

При використанні другого варіанту методу в програмі установки пакету програм АСКТП КВАРЦ час виконання програм контролерами в середньому зменшився на 26%, що означає, що число контролерів можна зменшити на ј (рис. 3).

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

В середньому завантаження робочої станції виросло лише на 11%.

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

(5)

Pi , Fj– час виконання програмних модулів контролером і РС; Tij – час взаємодії двох програмних модулів з різних вузлів.

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

Рис. 4. Граф взаємозв’язків між програмами для мінімізації часу виконання програм робочою станцією і контролером

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

Три вищеописані варіанти методу призначені для використання в програмах установки і балансування навантаження програмних пакетів систем керування. Зокрема, в підсистемі установки пакету КВАРЦ добре зарекомендував себе метод розподілу програмних модулів, що мінімізує час виконання програм робочою станцією і контролером. Він дав можливість поліпшити одну з найважливіших характеристик систем реального масштабу часу – гарантований час відповіді на 16% у порівнянні з базовим варіантом програми розподілу модулів (рис. 5) і на 23% у порівнянні з першим варіантом методу.

Рис. 5. Час реакції комплексу на зовнішні події при використанні ручного розподілу програм і трьох варіантів розробленого методу

Перша оцінка на гістограмі (рис. 5) – базовий (ручний) варіант, за яким ідуть слідом результати по трьох варіантах розробленого методу.

У третьому розділі „Планування задач за структурним критерієм” досліджені існуючі методи планування задач в обчислювальних системах; пропонується метод планування задач по структурному критерію. Цей метод може підвищити продуктивність робочої станції за рахунок мінімізації часу очікування задачами звільнення послідовно використовуваних ресурсів: |

(6)

де Ti – час очікування|чекання| i-ю задачею звільнення|визволення| ресурсу.

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

В розробленому методі для кожної задачі|задачі| значення всіх її характеристик записуються в спеціальну структуру - блок керування задачею|задачею| (tcb). При цьому перелік всіх задач|задач|, що обробляються алгоритмом планування, представляється масивом структур розмірності N (tcb[N]), де N – число всіх задач|задач|. Вважається|лічитимемо|, що задачі|задача| tcb[i] слід віддати перевагу перед задачею|задачі| tcb[k], якщо задача|задача| tcb[i] перевершує задачу|задачу| tcb[k] хоча б|хоча би| за однією характеристикою (tcb[i].j > tcb[k].j), а по всіх інших характеристиках не гірша за неї. І нехай|нехай| задачі|задачі| tcb[i] та tcb[k] вважаються непорівнюваними|незрівнянні| між собою, якщо задача|задача| tcb[i] перевершує задачу|задачу| tcb[k] за значеннями одних характеристик, а задача|задача| tcb[k] перевершує задачу|задачу| tcb[i] за значеннями інших. Групі непорівнюваних|незрівнянні| та еквівалентних задач|задачі| присвоюється номер (ранг), що визначає порядок|лад| виконання: чим менше номер, тим вище ранг групи задач|задач|.

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

Крок 1. Вибирається перша задача з першої черги.

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

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

Крок 4. Кроки 2, 3 повторюються до тих пір, поки знаходяться нові задачі в чергах, що позначають наступні характеристики.

Крок 5. Коли в поточній черзі розширився набір задач конкретного рангу, необхідно передивлятися всі попередні черги і знаходити найгірше положення кожної задачі поточного рангу.

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

1, якщо i-та задача|задача| сумісна по ресурсам,

що використовуються, з j-ю задачею|задачею|;

tcb[i].r[j] = (7)

0, інакше.

Перший раз для виконання вибираються задачі|задачі| з|із| найвищим рангом. Далі перебираються рядки матриці сумісності задач|задач|, помічені|позначені| номерами задач, що виконуються. Відмічаються всі стовпці матриці, в яких у виділених рядках знаходяться|перебувають| одиничні|поодинокі| значення. Номери цих стовпців визначають задачі|задачі|, сумісні з виконуваними. Серед них і вибираються задачі|задачі| з|із| найбільш високим рангом для виконання. При завершенні виконання будь-якої задачі|задачі| з|із| матриці сумісності задач|задач| видаляються відповідні рядок і стовпець, і для вільних процесорів вибираються задачі|задачі| відповідно до відкорегованої|відкоригованої| матриці. Обрані задачі запускаються на виконання за допомогою API функцій базової операційної системи (ОС).

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

Був написаний диспетчер задач для пакету програм АСКТП КВАРЦ, що використовує розроблений метод планування. Час виконання набору задач порівнювався з його ж часом виконання під управлінням диспетчерів ОС Windows і QNX. На рис. 6 наведені результати для 5 наборів задач, за якими проводилося тестування.

Рис. 6. Час виконання п’яти наборів задач різними диспетчерами

При використанні методу за рахунок збалансованого використання ресурсів робочої станції збільшується завантаження процесора, підвищується її продуктивність, збільшується пропускна спроможність. В середньому по всіх тестах розроблений диспетчер показав кращі результати приблизно на 11%. (від -4% до +10% у порівнянні з диспетчером ОС QNX та від +10% до +32% у порівнянні з диспетчером ОС Windows).

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

Стандартним засобом векторної обробки масивів даних є|з'являється,являється| шаблон класів valarray з|із| бібліотеки STL мови|язика| програмування C++. Цей шаблон класів разом із допоміжними механізмами, такими як зрізи, узагальнені зрізи, маски або непрямі масиви, дозволяє виконувати операції над підмножинами елементів векторів. Але|та| використання цих механізмів утруднюється із-за їх нетрадиційного синтаксису. Їх практично неможливо використовувати для регулярної вибіркової векторної обробки |галузяться|.

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

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

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

Шаблон класів vcarray побудований|споруджений| таким чином, що всі арифметичні операції виконуються над|із| елементами, які входять в поточний вектор галуження. Спочатку до вектора галуження входять всі елементи послідовності. Умовні оператори - VcarrayIf(vcarray<bool>), VcarrayElse, оператори повторення - VcarrayWhile(vcarray<bool>) – EndVcarrayWhile, VcarrayDo - VcarrayDoWhile(vcarray<bool>) формують новий вектор галуження, і всередині них обробляються лише елементи послідовності, що задовольняють умові (входять до vcarray<bool>). Інструкція EndVcarrayIf, а також інструкції завершення циклів видаляють|знищують,віддаляють| останній вектор галуження, і відбувається|походить| повернення до попереднього вектора галуження, з|із| яким працювали до циклу (умовного оператора). Таким чином можна будувати обробку будь-якого ступеня|міри| вкладеності – кожен цикл і умовний оператор додає|добавлятиме| в спеціальний стек новий вектор галуження, а після його завершення цей вектор галуження видаляється. Стандартний шаблон valarray взагалі не дозволяє робити|чинити| вкладену вибіркову обробку.

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

Лема 1. Для шаблону vcarray можливості|спроможності| векторних операторів присвоювання з|із| арифметичними і логічними векторними виразами, віднесені до одного індексу елементів оброблюваних векторів, повністю відповідають їх скалярним аналогам – оператору присвоювання і виразам мови|язика| програмування C++.

Лема 2. Для шаблону vcarray галуження векторної обробки за індивідуальними умовами для кожного з індексів елементів оброблюваних векторів виконується так, начебто елементи векторів обробляються скалярним алгоритмом з використанням інструкцій “if () {} else {}” (рис. 7).

Рис. 7. Векторне програмування інструкції вибору if () else{}

Дійсно, простий блок галуження, представлений|уявлений| графічно зліва|ліворуч| на рис. 7, у векторному варіанті обробки з використанням шаблону vcarray програмується послідовністю інструкцій, представленою|уявленою| на цьому ж рисунку в центрі.

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

Лема 3. Для шаблону vcarray цикли VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo-VcarrayDoWhile(vcarray<bool>) виконуються так само, як і при обробці кожного елементу вектора в окремому циклі while() або do – while(), де умовою виконання циклу є перевірка, чи задовольняє елемент вектора якійсь логічній умові.

Дійсно|дійсно|, цикли VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo-VcarrayDoWhile(vcarray<bool>) при кожній ітерації замінюють поточний вектор індексів новим, куди записуються|занотовуються| номери елементів, що задовольняють умові виконання циклу. Всі операції в циклі проводяться тільки|лише| для елементів з|із| останнього вектора індексів; а оскільки|тому що| цикл виконується, поки|доки| умова виконується хоча б|хоча би| для одного елементу, значить, це те ж саме, що й виконання циклу для кожного елементу вектора окремо. Приклади|зразки| векторної і звичайної|звичній|, скалярної, обробки послідовностей чисел в циклі наведені на рис. 8.

Рис. 8. Векторне програмування циклу while() {}

Лема 4. Приведених інструкцій прямування |дотримання|, вибору і повторення достатньо|досить|, щоб виконувати вибіркову векторну обробку будь-якого ступеня|міри| вкладеності.

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

Основне твердження. Шаблону класів vcarray, структури для організації галужень і набору макросів для галуження обробки VcarrayIf(vcarray<bool>), VcarrayElse, EndVcarrayIf, макросів повторення VcarrayWhile(vcarray<bool>) - EndVcarrayWhile; VcarrayDo - VcarrayDoWhile(vcarray<bool>) і інструкцій слідування|дотримання| достатньо|досить| для побудови|шикування| програм вибіркової векторної обробки будь-якого ступеня|міри| складності |галузиться|.

Дійсно, відповідно до правил структурного програмування, для створення|створіння| програми будь-якого рівня складності достатньо|досить| інструкцій прямування|дотримання|, галуження і повторення. Шаблон vcarray надає ці 3 види інструкцій, ідентичних тим, що є в мові|язиці| програмування С++, що доведено в лемах; отже, за допомогою цих макросів теж|також| можна написати програму будь-якого ступеня|міри| складності.

Як показали експериментальні дослідження, розроблені засоби векторної обробки, а саме шаблон класів vcarray, значно перевищують за швидкістю виконання майже всіх операцій стандартний шаблон класів valarray в його реалізації в рамках Microsoft Visual Studio.NET 7.1. На гістограмі, представленій на рис. 9, показано час виконання різних операцій шаблонами vcarray і valarray.

Рис. 9. Час виконання операцій різними засобами обробки векторів

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

ВИСНОВКИ

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

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

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

3. Експериментальні дослідження розробленої програми розподілу програмних модулів між комп'ютерними вузлами на тестових наборах показали: для першого варіанту методу час взаємодії програм з різних вузлів мережі скоротився на 19%; для другого - час виконання програм контролерами скоротився на 26% з незначним зростанням завантаженості робочої станції; для третього - час гарантованої відповіді системи на зовнішні події зменшився на 16%.

4. Для робочих станцій систем управління розроблено метод планування задач по багатьох характеристиках, що забезпечує рівномірне використання обчислювальних ресурсів. У розробленому методі однаковий ранг присвоюється групі задач, що збалансовано завантажують обчислювальні ресурси робочої станції, за рахунок чого збільшується завантаження процесора робочої станції, підвищується її продуктивність, збільшується пропускна спроможність. В результаті час виконання типових задач верхнього рівня автоматизованої системи управління технологічним процесом зменшується приблизно на 9 – 11%. Цей метод був застосований і перевірений на ефективність в диспетчері задач реального часу пакету програм КВАРЦ.

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

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

7. Розроблені програмні методи і засоби були апробовані на практиці і довели свою працездатність і ефективність у складі пакету програм АСКТП КВАРЦ на об'єктах багатьох підприємств, зокрема, в Дніпропетровському метрополітені, на Дніпропетровському лакофарбному заводі, Лисичанському желатиновому заводі, Самарській ТЕЦ, Юльївському нафтогазоконденсатному родовищі, Хоростковському цукровому заводі.

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

1. Щербакова М.Е. Автоматизированное проектирование ППО КСУ на базе пакета программ "КВАРЦ" : монография [под ред. д.т.н., проф. А.Г. Руденко] / Щербаков Е.В., Щербакова М.Е., Охрамович В.К. - Луганск: Издательство Восточноукраинского национального университета имени В.Даля, 2003. - 200 с.

2. Щербакова М.Є. Мовні засоби системного програмування / Щербаков Є.В., Щербакова М.Є. – Луганськ: Вид-во Східноукр. Нац. Ун-ту, 2005. – 387 с.

3. Щербакова М.Е. Особенности SCADA-системы пакета "КВАРЦ" / Щербаков Е.В., Щербакова М.Е., Рязанцев А.И. // Вестник ХГТУ. Херсон. – 2003. - № 2 (18). - С. 188 - 192

4. Щербакова М.Е. Система SCADA на базе пакета КВАРЦ / Щербакова М.Е. // Промышленные контроллеры АСУ. – Москва, 2004. - № 10. - С. 30 - 32

5. Щербакова М.Є. Диспетчеризація задач за структурним критерієм / Щербакова М.Е. // Сборник научных трудов: Спецвыпуск: Информационные технологии в научных исследованиях и в учебном процессе (международ. научн. – практ. конф., Луганск – Алчевск, 21 – 24 ноября 2005 г.). – Алчевск: ДонГТУ, 2005. – 204 с. - С. 178 - 186

6. Щербакова М.Е. Оптимизация распределения программных модулей между узлами сети в компьютерных системах управления / Щербакова М.Е. // Материалы 7-го Международного молодежного форума "Радиоэлектроника и молодежь в 21 веке". - Харьков, 2003. - С. 479

7. Щербакова М.Е. Методика диспетчеризации задач реального масштаба времени / Щербакова М.Е., Гудкович Н.В. // Збірник наукових праць Східноукраїнського національного університету імені Володимира Даля (на підставі матеріалів VIII Міжнародної науково-практичної конференції „Університет і регіон”). - Луганськ, 2002. - С. 205

8. Щербакова М.Е. Распределение программных модулей между узлами сети в компьютерных системах управления / Щербакова М.Е. // Збірник тез доповідей науково-технічної конференції студентів, аспірантів та молодих вчених "Технологія – 2003". - Сєвєродонецьк, 2003. - С. 99 - 100

9. Щербакова М.Е. Управление выборочной векторной обработкой с помощью массива индексов / Щербакова М.Е. // Материалы 8-го Международного молодежного форума "Радиоэлектроника и молодежь в 21 веке". - Харьков, 2004. - С. 267

10. Щербакова М.Е. Пакет программ „КВАРЦ” для автоматизированных систем управления / Щербаков Е.В., Охрамович