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

Область застосування таких оцінок, в основному, збігається з областю дослідження, а саме: архітектурами та модифікаціями ЕОМ, на яких проводилися дослідження, ОС і програмних середовищ, під управлінням яких працює досліджуване ПЗ, різноманітністю та обсягами вхідних даних. Рекомендується застосування методу для порівняння багатофункціональних ПС одного призначення (наприклад, СУБД) за відомих умов застосування та нечітких вхідних даних.

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

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

Цей метод є спеціалізацію S- оцінок часової ефективності алгоритмів.

Для оцінки ймовірностей появи команд у ПЗ виконується розбір всіх виконавчих модулів. В експерименті 19 визначена частота використання усіх команд обробки даних процесора Intel у виконавчих модулях ОС Windows 95, 98 і 2000. Встановлено, що з 680 команд та їх модифікацій сумарну ймовірність 0,9 дають близько 90 найбільш ймовірних команд.

Далі проводиться оцінка часу виконання команд у випадковим чином сформованих сумішах команд, характерних для даного ПЗ. В експерименті 20 на комп'ютерах експериментальної бази з процесорами Intel і AMD встановлено поліпшення використання конвеєрних обчислень при розвитку версійністі ОС Windows.

Непрямою оцінкою ефективності конвеєризації є характеристики довжини лінійних ділянок і глибини коротких та довгих переходів, що позначається на можливих затримках конвеєра та кешуванні команд. Розроблено необхідне інструментальне ПЗ та експериментально (експеримент 21) отримані середні оцінки та їх дисперсії глибини переходів у виконавчих модулях ОС Windows 95, 98, 2000 і XP.

Розподіл часу виконання сумішей команд відображає вплив програмно-апаратних засобів на часову ефективність ПЗ. Виконаний експеримент 22 показав більшу ефективність Photoshop 6.0 під керуванням Windows 2000, ніж під Windows 98.

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

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

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

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

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



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

1

Рис. 3. Схема формування структурно адаптивного алгоритму

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

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

Система аналізу ґрунтується на припущенні, що чим більше використовується реалізація АО в найбільш ефективному алгоритмі, тим вона ефективніша і її частіше треба використовувати.

Визначається кількість включень у кожен -й виконаний алгоритм кожної -ї реалізації-го АО -го рівня деталізації .

Усі нормалізуються:

.	(20)

Образ алгоритму у визначається у вигляді вектора

, де - кількість усіх реалізацій усіх АО у метаалгоритмі.

Відстань між образами алгоритмів і визначається як

.	(21)

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

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

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

В експерименті 23 виконана структурна адаптація алгоритмів сортування до потоків вхідних даних з усталеними особливостями. Результати показують, що адаптивний алгоритм не гірше швидкого сортування, а в ряді випадків (масив розсортований на 0,1...0,2 %, масив відсортований до країв) на 1-3 порядки перевершує алгоритм швидкого сортування (табл. 2).

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

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

Ідея альтернативної адаптації алгоритмів відображена в такому адаптивному алгоритмі:

.	(22)

Алгоритм розбиває область визначення алгоритму, що адаптується, на підмножини, такі що

, и ,	(23)

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

Таблиця 2 Результати адаптації алгоритму сортування

Особливості сортованого масиву (множина вхідних даних)	Кількість ітерацій (загальна кількість синтезованих алгоритмів)	Кількість різних алгоритмів	Час виконання адаптивного алгоритму, 107 тактів	Порівняльний час сортування, 107 тактів
				«бульбашкою»	швидким сортуванням
Заповнений випадковими числами	157…159	91…104	4,2 …5,3	1229…1320	4,2…4,9
Масив відсортований	344…372	132…157	0,20 …0,22	0.15…0.20	2,0…3,1
Відсортований у зворотному порядку	161…455	90…149	0,48…1,2	1380…1685	2,0…2,4
Відсортований до середини масиву	158…175	88…110	5,08…5,97	1018…1113	282…290
Відсортований до кінців масиву	157…159	91…108	4,9…5,7	854…943	17,1…18,4
Розсортований на 0,1 %	210…359	98…167	0,71…2,26	407…669	1,9…2,0
Розсортований на 0,2 %	158…458	93…186	0,92…2,10	557…719	1,9…2,3

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

Розроблений адаптивний алгоритм стискання даних у будь-яких випадках і варіантах виконання має перевагу над відомими архіваторами. При цьому для суміші файлів різної структури це перевага досить невелика, близько 5...10 %. При гомогонізаціі суміші, у разі невдало обраного архіватора, ступінь переваги адаптивного алгоритму може доходити до 20 % і більше.

У додатку А наведено експериментальні дослідження адаптивного синтезу та навчання нейромереж на основі генетичного алгоритму, використані в ході проектування й розробки "Автоматизованої системи управління вантажними перевезеннями Укрзалізниці". Показано застосування методів оцінки ефективності алгоритмів для вирішення практичних завдань на сучасних алгоритмах штучного інтелекту. Розроблені в дисертаційній роботі показники функціональної ефективності застосовані для досягнення необхідного рівня якості системи моделювання робочого навантаження СКБД, а саме для оцінки ефективності моделювання робочого навантаження СКБД, компромісного критерію часової та функціональної ефективності - процесу навчання нейромереж, а також часової ефективності алгоритмів - для оцінки ефективності алгоритмів організації обчислювального процесу.

У додатку В показано застосування запропонованих підходів і методів оцінки функціональної ефективності до нечітко специфікованих алгоритмів багатокритеріального аналізу діяльності вищих навчальних закладів, підпорядкованих Міністерству транспорту та зв'язку України.

У додатку С подані акти впровадження результатів дисертаційної роботи в Міністерстві транспорту та зв'язку України, Укрзалізниці та в навчальному процесі.

На закінчення зауважимо, що для всіх комп'ютерних експериментів розроблене методичне та програмне забезпечення. Результати експериментів через обмеженість обсягу відсутні у авторефераті, але повністю наведені в дисертації. Результати роботи становлять цінність для алгоритмів, що функціонують у програмно-апаратних середовищах з неявним розпаралелюванням обчислень і кешуванням даних. Характерні представники таких середовищ - програмно-апаратні комплекси масового використання на базі процесорів Intel, AMD і їх аналогів під управлінням операційних систем Windows, Unix.

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

Основні результати та висновки

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

Розроблена сукупність показників ефективності алгоритмів (рис. 4).

Основні наукові результати дисертації такі:

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

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

3. Запропоновані універсальні S-R-L- показники часової ефективності алгоритмів: ступеня, області переваги та переваги за межами досліджень. Вони можуть бути застосовані в різних програмно-апаратних середовищах функціонування, що дозволяє вирішувати задачі вибору, адаптації, спеціалізації та оптимізації алгоритмів, призначених для виконання на сучасних ПЕОМ із засобами неявного розгалуження обчислень та кешування даних.

Виконані дослідження та отримані оцінки часової ефективності для алгоритмів сортування даних.

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

1

Рис. 4. Призначення та апробація S-R-L- показників ефективності алгоритмів

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

Виконані дослідження функціональної ефективності архіваторів даних. Встановлена перевага архіватора 7-Zip за S- показником на 10-20 %, та за R- показником на 95-98 % у представницькій області дослідження.

5. Розроблені методи визначення часу виконання операції доступу до даних, що є суттєвим для логічного й фізичного рівня проектування структур даних. На їх основі базується метод вибору структури даних з урахуванням операцій доступу. Запропоновані показники впливу кешування даних на часову ефективність алгоритмів, розроблена методика їх визначення. Встановлено, що час виконання операцій доступу до даних може бути на два порядки більшим за час виконання операцій обробки даних; у деяких випадках збільшення розміру кешу у 2 рази може зменшити час виконання алгоритму щонайменше у 4-4,5 рази.

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

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

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

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

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

Розроблено модифікований метод структурної адаптації, який передбачає одночасний синтез прямого та зворотного алгоритмів.

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

10. Розроблений метод формування альтернативно адаптивного алгоритму, що дозволяє підвищити ефективність множини функціонально еквівалентних алгоритмів. Розроблений альтернативно адаптивний алгоритм стискання даних, який за S- показником на 5-20 % краще архіваторів, що є його альтернативними складовими.

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

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

Основні положення дисертації опубліковані в таких роботах

1. Ільман В. М. Формальні структури та їх застосування : монографія / В. М. Ільман, В. В. Скалозуб, В. І. Шинкаренко. - Д.: Вид-во Дніпропетр. нац. ун-ту залізн. трансп. ім. акад. В. Лазаряна, 2009. - 205 с.

2. Шинкаренко В. И. Экспериментальные исследования алгоритмов в программно-аппаратных средах : монография / В. И. Шинкаренко. - Д.: Изд-во Днепропетр. нац. ун-та ж.-д. трансп. им. акад. В. Лазаряна, 2009. - 279 с.

3. Ільман В. М. Відтворення графів за технологічними шляхами / В. М. Ільман, В. В. Скалозуб, В. І. Шинкаренко // Вісн. Дніпропетр. нац. ун-ту залізн. трансп. ім. акад. В. Лазаряна. -2007. - Вип. 18. - С. 85-94.

4. Ільман В. М. Структурний підхід до проблеми відтворення граматик / В. М. Ільман, В. І. Шинкаренко // Проблеми програмування. -2007. - № 1. - С. 5-16.

5. Ільман В. М. Утворюючі системи графів / В. М. Ільман, В. В. Скалозуб, В. І. Шинкаренко // Вісн. Дніпропетр. нац. ун-ту залізн. трансп. ім. акад. В. Лазаряна. -2007. - Вип. 17. - С. 127-133.

6. Капустян В. О. Система аналізу діяльності вищих навчальних закладів та її функціональна ефективність / В. О. Капустян, В. І. Шинкаренко, Д. В. Олійник, О. П. Іванов // Наукові вісті НТТУ КПІ. -2007. - № 2. - С. 12-21.

7. Олейник Д. В. Мультиагентная адаптация гибридного генетического алгоритма для обучения нейросетей / Д. В. Олейник, В. И. Шинкаренко // Искусственный интеллект. - 2008. - № 4. - C. 463-470.

8. Шинкаренко В. И. Временная оценка операций обработки структурированных данных с учетом конвейеризации и кэширования / В. И. Шинкаренко // Проблеми програмування. -2006. - № 2-3. - С. 43-52.

9. Шинкаренко В. И. Выбор программных средств по критерию временной эффективности / В. И. Шинкаренко // Проблемы программирования. - 2002. - № 1-2. - С. 175-181.

10. Шинкаренко В. И. Грамматико-алгоритмические структурные модели метаалгоритмов / В. И. Шинкаренко, В. М. Ильман, Г. Г. Кроль // Математичні машини та системи. -2010. - № 1. - С. 3-16.

11. Шинкаренко В. И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования / В. И. Шинкаренко // Математичні машини та системи. -2007. - № 2. - С. 43-55.

12. Шинкаренко В. И. Зависимость временной эффективности вычислительных программ от архитектуры cуперскалярных процессоров / В. И. Шинкаренко // Проблемы программирования. - 2004. - № 2-3. - С. 267-273.

13. Шинкаренко В. И. Знание-ориентированный подход к адаптации алгоритмов / В. И. Шинкаренко // Искусственный интеллект. - 2008. - №3. - С. 388-397.

14. Шинкаренко В. И. Методы и средства структурной адаптации алгоритмов на метаалгоритмической основе / В. И. Шинкаренко, Г. Г. Кроль, И. В. Литвин, Е. Г. Васецкий // Искусственный интеллект. - 2009. - № 3. - С. 105-113.

15. Шинкаренко В. И. Нейросетевое моделирование рабочей нагрузки СУБД / В. И. Шинкаренко, Д. В. Олейник // Искусственный интеллект. -2007. - № 4. - С. 657-664.

16. Шинкаренко В. И. Особенности оценки эффективности вычислительных алгоритмов / В. И. Шинкаренко // Проблемы программирования. - 2001. - № 1-2. - С. 23-29.

17. Шинкаренко В. І. Особливості практичного застосування показників обчислювальної складності алгоритмів / В. І. Шинкаренко // Проблеми програмування. -2008. - № 2-3. - С 57-63.

18. Шинкаренко В. И. Программные агенты в организации распределенных вычислений адаптивного синтеза и обучения нейросетей / В. И. Шинкаренко, Д. В. Олейник // Проблеми програмування. - 2009. - № 1. - С. 60-72.

19. Шинкаренко В. И. Сравнительный анализ временной эффективности функционально эквивалентных алгоритмов / В. И. Шинкаренко // Проблемы программирования. - 2001. - № 3-4. - С. 31-39.

20. Шинкаренко В. И. Статистические показатели зависимости временной эффективности алгоритмов от кэширования данных / В. И. Шинкаренко // Математичні машини та системи. -2007. - № 3-4. - С. 150-161.

21. Шинкаренко В. И. Структурная адаптация алгоритмов на основе полиморфизма / В. И. Шинкаренко // Математичні машини та системи. - 2009. - № 2. - С. 28-44.

22. Шинкаренко В. И. Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе / В. И. Шинкаренко, Г. Г. Кроль, Е. Г. Васецкий, Т. Н. Мажара // Искусственный интеллект. - 2009. - № 4. - С. 104-111.

23. Шинкаренко В. И. Структурные модели алгоритмов в задачах прикладного программирования Часть I. Формальные алгоритмические структуры / В. И. Шинкаренко, В. М. Ильман, В. В. Скалозуб // Кибернетика и системный анализ. - 2009. - № 3. - С. 3-14.

24. Шинкаренко В. И. Структурные модели алгоритмов в задачах прикладного программирования Часть II. Структурно-алгоритмический подход к моделированию программного обеспечения / В. И. Шинкаренко, В. М. Ильман, В. В. Скалозуб // Кибернетика и системный анализ. - 2009. - № 4. - С. 49-56.

25. Шинкаренко В. И. Функциональная эффективность нечетко специфицированных алгоритмов / В. И. Шинкаренко // Проблеми програмування. - 2006. - № 1. - С. 24-33.

26. Шинкаренко В. И. Алгоритмический подход к управлению предприятием, отраслью / В. И. Шинкаренко // Современные информационные технологии на транспорте, в промышленности и образовании : междунар. науч.-практ. конф., 15-16 мая 2008 г. : тезисы докл. - Д.: ДНУЖТ, 2008. - С. 79-80.

27. Шинкаренко В. И. Методология измерения временной эффективности программных средств / В. И. Шинкаренко // Теоретические и прикладные аспекты разработки программных систем (TAAPSD'2005): междунар. конф., 7-9 дек. 2005 г. : тезисы докл. - К.: КНУ, 2005. - С. 61-65.

28. Шинкаренко В. И. Об оценке эффективности алгоритмов с учетом архитектуры ЭВМ / В. И. Шинкаренко // Компьютерное моделирование : междунар. науч.-метод. конф., 29 июня - 1 июля 2000 г.: тезисы докл. - Днепродзержинск: ДГТУ, 2000. - С. 268-269.

29. Шинкаренко В. И. Оценка влияния кэширования данных на временную эффективность алгоритмов / В. И. Шинкаренко // Теоретические и прикладные аспекты разработки программных систем (TAAPSD'2006) : междунар. конф., 5-8 дек. 2006 г. : тезисы докл. - К., 2006. - С. 38-42.

30. Шинкаренко В. И. Оценка влияния операционной системы и технических средств на временную эффективность программ / В. И. Шинкаренко // Проблемы математического моделирования : междунар. науч.-метод. конф., 28-30 мая 2003 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2003. - С. 190.

31. Шинкаренко В. И. Оценка эффективности алгоритмов при больших объемах данных / В. И. Шинкаренко // Проблемы математического моделирования : междунар. науч.-метод. конф., 29-31 мая 2002 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2002. - С. 177.

32. Шинкаренко В. И. Оценка эффективности использования структур данных в вычислительных программах / В. И. Шинкаренко // Проблемы математического моделирования : междунар. науч.-метод. конф., 25-27 мая 2005 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2005. - С. 183-184.

33. Шинкаренко В. И. Повышение временной и функциональной эффективности алгоритмов посредством адаптации / В. И. Шинкаренко // Теоретические и прикладные аспекты разработки программных систем (TAAPSD'2008) : междунар. конф., 22-26 сент. 2008 г. : тезисы докл. - К., Чернигов, 2008. - С. 200-204.

34. Шинкаренко В. И. Показатели временной эффективности вычислительных алгоритмов - программ / В. И. Шинкаренко // Компьютерное моделирование : междунар. науч.-метод. конф., 25-27 апреля 2001 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2001. - С. 183-184.

35. Шинкаренко В. И. Статистическая оценка временной эффективности алгоритмов / В. И. Шинкаренко // Информационные технологии в образовании : междунар. конф.-выставка, 5-9 сент. 2001 г. : труды. - М.: МИФИ, 2001. - ч. 3. - С. 149-151.

36. Шинкаренко В. И. Статистический анализ PE-модулей / В. И. Шинкаренко // Проблемы математического моделирования : междунар. науч.-метод. конф., 26-28 апр. 2004 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2004.- С. 192.

37. Шинкаренко В. И. Структурная адаптация алгоритмов / В. И. Шинкаренко // Проблемы математического моделирования: междунар. науч.-метод. конф., 24-26 мая 2006 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2006. - С. 210-211.

38. Шинкаренко В. И. Формализация алгоритмов и их преобразований в процессе разработки программного обеспечения / В. И. Шинкаренко // Теоретические и прикладные аспекты разработки программных систем (TAAPSD'2007) : междунар. конф., 4-9 сент. 2007 г. : тезисы докл. - Бердянск, 2007. - С. 30-34.

39. Шинкаренко В. И. Характеристики, показатели и метрики качества алгоритмов / В. И. Шинкаренко // Современные информационные технологии на транспорте, в промышленности и образовании : междунар. науч.-практ. конф., 14-15 мая 2007 г. : тезисы докл. - Д.: ДНУЖТ, 2007. - С. 82-83.

40. Шинкаренко В. И. Экспериментальные исследования алгоритмов / В. И. Шинкаренко // Проблемы математического моделирования : междунар. науч.-метод. конф., 23-25 мая 2007 г. : тезисы докл. - Днепродзержинск: ДГТУ, 2007. - С. 217-218.

41. Shinkarenko V. I. Preprocessing of image befor handwriting recognition / V. I. Shinkarenko // Internet - education - science. New informational and computer technologies in education and science : the second International Conf., 10-12 oct. 2000 y. : abstracts. - Vinnytsia: VSTU, 2000. - P. 294-296.

42. Shinkarenko V. I. Case Tool for Program Measurement / V. I. Shinkarenko, E. V. Shamaev // Copmputer Science and Information Technologies : International Scientific Conf. 21-26 sept. 2001 y. : proceedings - Ufa: USATU. - 2001. - Vol 3. - P. 39-42.

43. Shinkarenko V. I. Characteristics of Quality of UML-project / V. I. Shinkarenko, E. V. Shamaev // Computer Science and Information Technologies : the 4th International Workshop, 18-20 sept. 2002 y. : abstracts + CD ROM - Patras:University of Patras, 2002. - P. 26.

44. Shynkarenko V. I. Statistics for modeling of program's run on different processors / V. I. Shynkarenko, D. V. Oleinic // Prediction and decision making under uncertainties : International Workshop, 25-30 may 2004 y. : abstracts. - T.: KNU, 2004. - P. 54-56.

Анотація

Шинкаренко В. І. Експериментальні методи оцінки часової та функціональної ефективності алгоритмів у програмно-апаратних середовищах. - Рукопис.

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

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

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

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

Аннотация

Шинкаренко В. И. Экспериментальные методы оценки временной и функциональной эффективности алгоритмов в программно-аппаратных средах. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. Киевский национальный университет имени Тараса Шевченко, Киев, 2010.

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

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

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

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

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

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

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

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

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

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

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

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

Abstract

Shynkarenko V.I. Experimental methods for evaluating time and functional efficiency of algorithms in hardware and software environments. - Manuscript.

Dissertation for a scientific degree of the Doctor`s of technical sciences on speciality 01.05.03 - mathematical support and software for computers and systems. Taras Shevchenko National University of Kyiv, Kyiv, 2010.

Important scientific and practical problem of development the basis of algorithms` experimental research, efficiency of processes of forming algorithms for software that runs on modern hardware and software environments with implicit parallelization of computation and caching data has been solved.

The indicators of time efficiency and functional efficiency of algorithms were proposed. They are used to study extremely small and large algorithms and for realization of alternative and structural adaptation of algorithms.

Key words: the time efficiency of algorithms, functional efficiency of algorithms, indicator of efficiency of algorithms, a computer experiment, hardware and software environments, cache memory, algorithmic structure, grammar-algorithmic structure, the adaptation of algorithms.

Размещено на Allbest.ru

...