Балансування навантаження і планування задач для підвищення ефективності керуючих обчислювальних систем

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

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

Спеціальність 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), що дорівнює витратам часу контролера на взаємодію між відповідними програмними модулями за умови, що один з них виконується робочою станцією, інший - контролером

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

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

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

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

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

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

	(3)

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

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

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

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

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

	(4)

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

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

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

	(5)

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

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

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

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

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

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

	(6)

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

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

В розробленому методі для кожної задачі значення всіх її характеристик записуються в спеціальну структуру - блок керування задачею (tcb). При цьому перелік всіх задач що обробляються алгоритмом планування, представляється масивом структур розмірності N (tcb[N]), де N - число всіх задач

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

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

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

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

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

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

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

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

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

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

0, інакше.

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

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

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

При використанні методу за рахунок збалансованого використання ресурсів робочої станції збільшується завантаження процесора, підвищується її продуктивність, збільшується пропускна спроможність. В середньому по всіх тестах розроблений диспетчер показав кращі результати приблизно на 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

Такі самі дії над елементами масиву в скалярному варіанті обробки виконуються простим циклом з операторами 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>) при кожній ітерації замінюють поточний вектор індексів новим, куди записуються номери елементів, що задовольняють умові виконання циклу. Всі операції в циклі проводяться тільки для елементів з останнього вектора індексів; а оскільки|тому що| цикл виконується, поки умова виконується хоча б для одного елементу, значить, це те ж саме, що й виконання циклу для кожного елементу вектора окремо.

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

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

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

Шаблон класів 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. Щербакова М.Е. Пакет программ „КВАРЦ” для автоматизированных систем управления / Щербаков Е.В., Охрамович В.К., Щербакова М.Е. // Збірник наукових праць Східноукраїнського національного університету імені Володимира Даля (на підставі матеріалів IХ Міжнародної науково-практичної конференції „Університет і регіон”). - Луганськ, 2003. - С. 103

11. Щербакова М.Е. Управление выборочной векторной обработкой с помощью векторов ветвления / Щербакова М.Е. // Збірник (частина 2) тез доповідей науково-технічної конференції студентів, аспірантів та молодих вчених "Технологія - 2004". - Сєвєродонецьк, 2004. - С. 24 - 25

12. Щербакова М.Е. Оптимизация вычислений в высокопроизводительных информационно-вычислительных системах / Щербакова М.Е. // Сборник докладов Международной научно-практической конференции „Единое информационное пространство 2004”. - Днепропетровск, 2004. - С. 205 - 208

13. Щербакова М.Е. Диспетчеризация задач по структурному критерию / Щербакова М.Е. // Материалы 9-го Международного молодежного форума "Радиоэлектроника и молодежь в 21 веке". - Харьков, 2005. - С. 398

14. Щербакова М.Е. Пакет программ АСУТП КВАРЦ / Щербакова М.Е. // Тезисы докладов международной научно-методической конференции „Математические методы и информационные технологии в управлении, образовании, науке и производстве”. - Мариуполь: ПГТУ, 2005. - 242 с. - С. 120 - 121

15. Щербакова М.Є. Розподіл програм між вузлами мережі в комп'ютерних системах керування / Щербакова М.Е. // Інформаційні технології в наукових дослідженнях і навчальному процесі: Матеріали Міжнародної науково-практичної конференції, 21 - 23 листопада 2005. - Луганськ, 2005. - 219 с. - С. 215 - 219

16. Shcherbakova M.E. Methods of computing optimization used in program package Kvarts /Shcherbakova M.E. // Материалы десятого Юбилейного Международного молодежного форума "Радиоэлектроника и молодежь в 21 веке". - Харьков 2006. - С. 569

17. Щербакова М.Е. Программные средства, использующие векторную обработку данных / Щербакова М.Е.// Інформаційні технології в наукових дослідженнях і навчальному процесі: Матеріали 2-го Міжнар. наук.-практ. конф., м. Луганськ, 14-16 листоп. 2006 р. Т. 2. - Луганськ, 2006. - 216 с. - С. 213 - 215

18. Щербакова М.Е. Программные средства, использующие векторную обработку данных / Щербаков Е.В., Горбатюк А.Ф., Щербакова М.Е. // Сборник научных трудов Донбасского государственного технического университета: Спецвыпуск: Информационные технологии в научных исследованиях и учебном процессе: Мат-лы 2-й Международ. научн.-практ. конференц.(14 - 16 ноября 2006 г., г.Луганск). - Алчевск: ДонГТУ; Луганск: ЛНПУ, 2006 - 248 с. - С. 238 - 244

19. Щербакова М.Е. Использование моделирования при балансировке нагрузки в компьютерной сети управления / Щербакова М.Е. // Моделирование и компьютерная графика : Материалы 2-й международной научно -технической конференции, г. Донецк, 10-12 октября 2007 г . -- Донецк , ДонНТУ , Министерство образования и науки Украины, 2007. -- 358 с. - С. 291 - 294

20. Щербакова М.Е. Методы балансирования нагрузки в управляющих вычислительных системах / Рязанцев А.И., Щербакова М.Е. // Інформатика та комп'ютерні технології - 2007 / Матеріали третьої науково-технічної конференції молодих учених та студентів. - Донецьк, ДонНТУ - 2007. - 580 с. - С. 231 - 233.

АНОТАЦІЯ

Щербакова М.Є. „Балансування навантаження та планування задач для підвищення ефективності керуючих обчислювальних систем”.- Рукопис.

Дисертація на здобуття|конкурс| наукового|ученого| ступеня|міри| кандидата технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. - Державний вищий навчальний заклад «Донецький національний технічний університет», м. Донецьк, 2008.

Дисертація присвячена питанням балансування обчислювального навантаження в системах керування технологічними процесами |.

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

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

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

АННОТАЦИЯ

Щербакова М.Е. „Балансирование нагрузки и планирование задач для повышения эффективности управляющих вычислительных систем”.- Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. - Государственное высшее учебное заведение «Донецкий национальный технический университет», г. Донецк, 2008.

Диссертация посвящена вопросам балансирования нагрузки и планирования задач в системах управления.

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

Для балансировки размещения программ между узлами сети в распределенных компьютерных системах были разработаны три варианта метода распределения. Первый находит такую конфигурацию программного комплекса, при которой время взаимодействия программ по сети является минимальным. Второй вариант минимизирует время выполнения программ контроллером за счет переноса части программных модулей для выполнения из контроллеров в рабочие станции. В третьем варианте метода минимизируется время гарантированного ответа сетевой вычислительной системы. Метод минимизации времени выполнения программ контроллерами и рабочими станциями был использован в подсистеме установки пакета программ АСУТП КВАРЦ и дал возможность улучшить одну из важнейших характеристик систем реального масштаба времени - гарантированное время ответа на 15 - 19%.

Серьезной проблемой в управляющих вычислительных системах является выбор задач на выполнение процессорами. При выборе задач нужно учитывать, что одновременная работа нескольких задач с общими ресурсами системы, такими, как каналы ввода-вывода или линии связи, может привести к значительному снижению производительности. Был разработан метод планирования задач, обеспечивающий равномерное использование вычислительных ресурсов. В разработанном методе одинаковый приоритет присваивается группе задач, сбалансированно загружающей вычислительные ресурсы рабочей станции. Задачи с одинаковым приоритетом выполняются в режиме квантования. За счет сбалансированного использования ресурсов рабочей станции увеличивается загрузка процессора рабочей станции, повышается ее производительность, увеличивается пропускная способность. За счет этого время выполнения типичных задач верхнего уровня автоматизированной системы управления технологическим процессом уменьшается примерно на 9 - 11%. Этот метод был применен и проверен на эффективность в диспетчере задач реального времени пакета программ АСУТП КВАРЦ.

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

Разработаны средства управления выборочной (условной) обработкой больших массивов данных, обеспечивающие практически полную загрузку конвейера центрального процессора на ветвящихся участках векторной обработки произвольной сложности и участках с последовательностями зависимых по операндам векторных операций. Доказано, что разработанные средства выборочной векторной обработки дают возможность обрабатывать массивы данных по алгоритмам любой степени сложности. За счет оптимальной загрузки конвейера центрального микропроцессора скорость выполнения математических операций при использовании разработанных средств управления векторной обработкой превосходит больше чем в 2 раза скорость выполнения тех же операций подобными средствами, обладающими меньшими возможностями.

Диссертационная работа выполнялась в Северодонецком технологическом институте в рамках хоздоговора № 161 от 22.10.2003 г. с ЗАО «Северодонецкое научно-производственное объединение «Импульс» «Разработка подсистемы ведения состава изделия и автоматизации выпуска конструкторской документации», а также в рамках госбюджетных тем «Разработка программно-технического комплекса химического производства» (ГР №0104U000391) и «Проектирование муниципальной компьютерной системы с использованием современных информационных технологий» (ГР №0103U007993). В указанных роботах автор принимал непосредственное участие как исполнитель.

Разработанные методы были использованы в пакете прикладных программ КВАРЦ и проверены на практике при эксплуатации пакета на объектах многих предприятий, в частности, в Днепропетровском метрополитене, на Днепропетровском лакокрасочном заводе, Лисичанском желатиновом заводе, Самарской ТЭЦ, Юльевском нефтегазоконденсатном месторождении, Хоростковском сахарном заводе.

Результаты диссертационного исследования использованы в учебных курсах «Системное программирование», «Системы цифровой обработки информации» для студентов специальностей 7.091501 и 7.091502 в Технологическом институте (г. Северодонецк).

ABSTRACT

Shcherbakova M.Y. “Load balancing and job planning for increasing efficiency of computer control systems”. - Manuscript.

Thesis on competition for the candidate of technical sciences degree - speciality 05.13.05 - “Computing systems and components”. - The state higher educational institution “Donetsk National Technical University”, Donetsk, 2008.

The thesis is concerned with questions of computer control systems functioning. For optimization of the task distribution in the network the special method was developed. The score of its development was to minimize workstation time costs for programs' execution. Also the method of task supervising by structural criterion was developed. In accordance with it task priority is assign to groups of tasks. Each group consists of noncomparable and equivalent tasks and has a number, denotative service procedure. For simultaneous execution is selects tasks, compatible by used resources. Use of developed method decrease time loss by 9 - 11 % due to reduction of tasks timeout in the queues of sequentially used resources waiting.

...