65443

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

Автореферат

Информатика, кибернетика и программирование

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

Украинкский

2014-07-30

922.5 KB

0 чел.

PAGE 2

Київський національний університет імені Тараса Шевченка

ШИНКАРЕНКО Віктор Іванович

УДК 510.5:004.05

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

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

автореферат

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

Київ-2010


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

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

Науковий консультант: 

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

Капустян Володимир Омелянович, Національний технічний університет України "КПІ", завідувач кафедри математичного моделювання економічних систем.

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

член-кореспондент Національної академії наук України, доктор фізико-математичних наук, професор

 Перевозчикова Ольга Леонідівна, Інститут кібернетики НАН України,  зав. відділом автоматизації програмування;

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

Симоненко Валерій Павлович, Національний технічний університет України "КПІ", професор кафедри обчислювальної техніки;

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

Цейтлін Георгій Овсійович, Інститут програмних систем НАН України, провідний науковий співробітник відділу теорії комп’ютерних обчислень.

Захист вiдбудеться 23 грудня 2010 р. о 14 год. 00 хв. на засiданнi спецiалiзованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка, Київ, пр. Глушкова, 4д, факультет кібернетики, ауд. 40.

Тел. 521-33-66. Факс 239-32-80, E-mail: rada@cyber.univ.kiev.ua

З дисертацiєю можна ознайомитися в науковій бiблiотецi ім. М. Максимовича Київського національного університету імені Тараса Шевченка, Київ, вул. Володимирська, 58

Автореферат розiсланий 22 листопада 2010 р.

Вчений секретар
спецiалiзованої вченої ради

____________________    В. П. Шевченко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Темпи розвитку обчислювальної техніки та відповідного системного та прикладного програмного забезпечення (ПЗ) постійно зростають. Якщо в 60-90 рр. минулого століття нові архітектури ЕОМ і операційні системи масового використання з’являлися з інтервалом 5...10 років, то зараз тільки фірма Intel забезпечує оновлення декількох серій процесорів щорічно, а Microsoft щорічне оновлення ОС Windows. Крім того, розвивається декілька принципово різних платформ процесорів RISC, Гарвардської, Берклійської архітектури, асоціативні, матричні, нейронні, проблемно-орієнтовані архітектури та інші. Вагому конкуренцію OC Windows складають Unix-подібні ОС, такі як Linux, QNX та інші.

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

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

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

Перший підхід базується на теорії ймовірностей і комбінаториці. Розробкою методології аналізу алгоритмів та її застосуванням до конкретних алгоритмів починаючи з 1950 р. інтенсивно займалися багато вчених. Розроблені методи й більшість результатів зарубіжних дослідників узагальнено у відомій роботі Д. Кнута. Сучасні дослідження представлені великою кількістю монографій і підручників, серед яких праці А. В. Аха, Д. Гріна, Дж. Хопкрофта, Дж. Ульмана, Дж. Макконнелла, С. Гудмана, С. Хідетніемі, Т. Кормена, Ч. Лейзерсон, Р. Ривеста та інших, а також вітчизняних учених і вчених країн СНД В. К. Задираки, А. В. Анісімова, О. А. Павлова, М. М. Глибовця, Л. П. Лісовика, В. П. Симоненка, О. Л. Семенова, В. А. Успенського, О. Є. Андрєєва, В. Б. Алексєєва, Г. П. Кожевнікової, С. А. Абрамова, В. А. Носова, В. В. Воєводіна та інших.

Формальному аналізу алгоритмів та їх перетворенням присвячені роботи на основі відомих моделей: алгебр Глушкова, машин Тьюрінга, Колмогорова, Шйонхаге, систем Поста, нормальних алгоритмів Маркова, схем програм Янова, граф-схем Калужніна і т. ін. (другий підхід). Завдяки роботам В. М. Глушкова, А. А. Летичевського, Є. Л. Ющенко, Ю. В. Капітонової, Г. О. Цейтліна, В. Н. Редька, П. І. Андона, М. С. Нікітченка, Д. Б. Буя, А. Ю. Дорошенка та інших підтримується пріоритетність вітчизняної науки в алгебраїчному підході до аналізу алгоритмів.

Основою третього підхіду є аналіз складових і конструкцій алгоритмів. Він представлений роботами таких вчених, як M. Halstead, T. McCabe, C. McClure, W. Harrison, S. Henry, D. Kafula, C. Myere, E. Chen та інших.

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

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

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

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

Розглянута проблематика є предметом вивчення як програмної інженерії, так і інженерії якості програмного забезпечення. Одним з ключових елементів програмної інженерії є розробка алгоритмів та їх аналіз. Рекомендації об’єднаної комісії ACM та IEEE з викладання програмної інженерії (Software Engineering) та інформатики (Computer Science) включають аналіз алгоритмів у ядро знань та пропонують обов’язковим до вивчення студентами університетів.

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

Значний внесок у дослідження задач інженерії якості як найважливішої складової програмної інженерії зробили П. І. Андон, Є. М. Лавріщева, В. В. Ліпаєв, S. H. Kan, J. Tian та інші.

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, що ведуться на кафедрі "Комп’ютерні інформаційні технології" Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна. Результати роботи різною мірою використані у госпдоговірних науково-дослідних роботах, що виконувались відповідно до планів науково-дослідних робіт Міністерства транспорту та зв’язку України, Укрзалізниці та Придніпровської залізниці. У семи з них дисертант є науковим керівником та співавтором звітів:

  •  „Розробка програмного забезпечення для виконання робіт по збору, обробці та аналізу інформації щодо діяльності закладів освіти”, ДР № 107U004387. Робота виконана згідно з планом науково-дослідних та конструкторських робіт (НДКР) Міністерства транспорту України на 2004 р.;
  •  „Розвиток системи багатокритеріального аналізу діяльності закладів освіти”, ДР № 0107U006737. Робота виконана згідно з планами НДКР Міністерства транспорту України на 2006 та 2007 р.;
  •  „Розробка АРС для працівників управління ЦКадри для збору інформації та формування звітності за сучасними інформаційними технологіями”, ДР № 0103U007779. Робота виконана згідно з планами НДКР Укрзалізниці на 2002 та 2003 р.;
  •  „Розробка автоматизованого робочого місця з аналізу діяльності вищих навчальних закладів”, ДР № 0106U011750. Робота виконана згідно з планом НДКР Укрзалізниці на 2006 р.;
  •  „Формування поточних та довгострокових планів підвищення кваліфікації керівників та фахівців Придніпровської залізниці”, ДР № 0103U007780. Робота виконана згідно з планами НДКР Придніпровської залізниці на 2003 та 2004 р.;
  •  „Впровадження системи навчання та контролю знань кадровиків структурних підрозділів на робочих місцях”, ДР № 0107U004386. Робота виконана згідно з планом НДКР Придніпровської залізниці на 2004 р.
  •  „Розробка методів та засобів розшифровки швидкостемірних стрічок для вантажного, пасажирського та приміського руху”, ДР № 0107U006736. Робота виконана згідно з планами НДКР Придніпровської залізниці на 2007 та 2008 р.

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

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

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

  •  розробити методи виконання комп’ютерних експериментів для оцінки ефективності алгоритмів, а також відповідне алгоритмічне та програмне забезпечення;
  •  виділити найбільш суттєві експлуатаційні характеристики обчислювальних алгоритмів, визначити відповідні показники ефективності, розробити методики розрахунку їх достовірних оцінок на основі комп’ютерних експериментів;
  •  дослідити вплив архітектури сучасних ЕОМ і її модифікацій на ефективність алгоритмів і запропонувати методику оцінки впливу окремих елементів архітектури;
  •  запропонувати методи оцінки ефективності алгоритмів для вкрай великих (106...1010 операторів у представленні алгоритму) і вкрай малих алгоритмів (1…5 операцій);
  •  розробити методи та засоби адаптації алгоритмів, що функціонують у реальних програмно-апаратних середовищах, на основі вибору алгоритмів або їх частин із застосуванням розроблених показників та методів оцінки ефективності алгоритмів. Підготувати алгоритмічне і програмне забезпечення;
  •  розробити формальні засоби моделювання алгоритмів, які дозволяють встановити зв’язок між різними представленнями алгоритмів та їх виконанням, а також автоматизувати процеси синтезу адаптивних алгоритмів.

Об’єкт дослідження: процес виконання алгоритмів у програмно-апаратних середовищах.

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

До таких середовищ належать сучасні програмно-апаратні середовища масового використання: ПЕОМ на основі процесорів Intel і їх аналогів під управлінням багатопотокових ОС різних версій Windows і Unix при спільному виконанні системних і прикладних програм.

Методи дослідження. Результати дослідження отримані на основі відомих та апробованих методів.

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

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

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

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

Наукова новизна отриманих результатів. У роботі вперше отримані такі результати:

  •  встановлена наявність суттєвих розбіжностей оцінок часових характеристик алгоритмів за традиційними показниками обчислювальної або часової складності алгоритмів з експериментальними даними, отриманими при виконанні алгоритмів у програмно-апаратних середовищах з неявним розпаралелюванням обчислень і кешуванням даних;
  •  розроблені методи обґрунтування, підготовки, виконання, обробки та аналізу результатів комп’ютерних експериментів з дослідження ефективності алгоритмів;
  •  запропоновані статистичні показники й розроблені методи оцінки часової ефективності алгоритмів. На відміну від існуючих, вони дозволяють виконувати оцінку ефективності алгоритмів при функціонуванні в сучасних програмних і апаратних середовищах;
  •  запропоновані показники оцінки впливу кешування даних на часову ефективність алгоритмів, розроблена методика їх визначення. Це дозволяє вирішувати завдання підвищення ефективності алгоритмів у програмно-апаратному середовищі шляхом підбору відповідної апаратної складової;
  •  розроблена методика вибору структур даних на основі експериментальних досліджень мікроалгорітмов обміну даними, що дає можливість конструювати структури даних з урахуванням особливостей використання кеш-пам’яті;
  •  розроблена методика статистичної оцінки середнього часу конвеєрного виконання команд процесора, що дозволяє враховувати особливості виконавчого пристрою при низькорівневому програмуванні;
  •  розроблені методи оцінки часової ефективності великих програмних систем (106...1010 операторів). Вони можуть бути використані під час вибору програмних засобів з функціонально еквівалентних, а також для контролю часової ефективності в процесі розробки та супроводу ПЗ;
  •  сформульовані поняття нечітко специфікованих алгоритмів і функціональної ефективності, запропоновані статистичні показники й розроблені методи оцінки функціональної ефективності алгоритмів. Виконані дослідження функціональної ефективності деяких класів алгоритмів;
  •  розроблена метрична модель функціонально еквівалентних алгоритмів, що дозволило застосувати методи кластеризації та структурної адаптації алгоритмів.

Отримали подальший розвиток:

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

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

Обґрунтованість наукових положень і достовірність отриманих результатів підтверджується:

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

Достовірність оцінок ефективності алгоритмів забезпечується:

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

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

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

Розроблені методи:

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

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

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

Особистий внесок здобувача. Основні результати дисертаційної роботи отримані автором особисто.

У наукових працях, виданих у співавторстві, дисертанту належать: [, ] – апробація запропонованих методів та алгоритмів, [] – постановка задачі відновлення граматик засобами формальних структур, [] – формальні засоби перетворення ієрархічних структур у реляційні, методологія підвищення функціональної ефективності автоматизованої системи, [] – методологія адаптації алгоритмів навчання нейромереж, [] – граматико-алгоритмічна модель множини алгоритмів сортування, [] – постановка задачі, концепція розробки автоматизованої системи, [] – показники якості моделей робочого навантаження СКБД, [] – оцінка ефективності організації обчислень, [] – постановка задачі, метод структурної адаптації алгоритмів стискання даних, оцінка функціональної ефективності адаптованого алгоритму, [] – концепція формальних алгоритмічних структур та структурні моделі алгоритмів, [] – формальні зв’язки між алгоритмами та представлення процесу розробки ПЗ як послідовності реструктуризацій алгоритмів, [, ] – постановка задачі, [] – виокремлення єдиних властивостей процедур, алгоритмів, модулів, класів. У спільній монографії [1] матеріали всіх глав написані за участю дисертанта, а глави 5, 6 – в основному дисертантом.

Апробація результатів дисертації. Результати дисертаційної роботи представлені на міжнародних наукових і науково-практичних конференціях: УкрПРОГ (Київ, 2002, 2004, 2006, 2008), "Теоретичні та прикладні аспекти розробки програмних систем" (TAAPSD, Київ, 2004, 2005, 2006; Бердянськ, 2007; Київ - Тернопіль, 2008; Київ, 2009), "Комп’ютерні науки та інформаційні технології" (CSIT, Уфа, 2001; Патрас (Греція), 2002), "Інформаційні технології в освіті" (ІTO, Москва, 2001, 2002), "Проблеми і прийняття рішень в умовах невизначеності" (PDMU, Київ, 2001; Київ - Канів, 2002; Тернопіль, 2004; Бердянськ, 2005), "Штучний інтелект" (Кацивелі (Крим), 2002, 2008; Дивногорське (Росія), 2007, 2009), "Комп’ютерне моделювання" (Дніпродзержинськ, 2000, 2001), "Проблеми математичного моделювання" (Дніпродзержинськ, 2002, 2003, 2004, 2005, 2006, 2007), "Автоматика" (Одеса, 2001; Донецьк, 2002), "Теоретичні та прикладні питання сучасних інформаційних технологій" (Улан-Уде, 2001, 2002), "Інтернет наука освіта" (Вінниця, 2000), "Інформаційна техніка і електромеханіка на рубежі XXI століття" (Луганськ, 2001), "Інформаційні технології на виробництві та в освіті" (Хмельницький, 2002), "Комп’ютерне моделювання та інформаційні технології в науці, економіці та освіті" (Кривий Ріг, 2002; Черкаси, 2003), "Проблеми економіки транспорту" (Дніпропетровськ, 2002, 2003, 2005, 2009), "Сучасні інформаційні та електронні технології" (Одеса, 2002), "Проблеми та перспективи розвитку залізничного транспорту" (Дніпропетровськ, 2005), "Сучасні інформаційні технології на транспорті, в промисловості та освіті" (Дніпропетровськ, 2007, 2008, 2009), "Комп’ютерне моделювання та інтелектуальні системи" (Запоріжжя, 2007).

Результати роботи доповідались також на наукових семінарах "Проблеми управління та інформатики" (ДДТУЗТ, Дніпропетровськ, 2000; ДНТУЗТ, Дніпропетровськ, 2006), "Інформаційні технології та автоматизовані системи на транспорті" (Транспортна академія України, Дніпропетровськ, 2005) і науковому семінарі інституту програмних систем (Київ, 2001).

У повному обсязі матеріали дисертаційного дослідження доповідалися на республіканському семінарі "Програмологія та її застосування" на базі кафедри "Теорії та технології програмування" Київського національного університету імені Тараса Шевченка, науковому семінарі відділу теорії комп’ютерних обчислень Інституту програмних систем НАН України, міжкафедральному семінарі факультету "Технічна кібернетика" Дніпропетровського національного університету залізничного транспорту імені академіка В. Лазаряна, науковому семінарі відділу автоматизації програмування Інституту кібернетики НАН України, науково-методичному семінарі факультету кібернетики Київського національного університету імені Тараса Шевченка, науково-методичному семінарі кафедри "Програмне забезпечення ЕОМ" Харківського національного університету радіоелектроніки та міжкафедральному семінарі факультету кібернетики Київського національного університету імені Тараса Шевченка.

Публікації. За темою дисертації видано дві монографії. У журналах, рекомендованих ВАК для публікації результатів дисертацій, опубліковано 23 статті: «Проблеми програмування» – 9, «Штучний інтелект» – 5, «Математичні машини і системи» – 4, «Кібернетика і системний аналіз» – 2, «Наукові вісті КПІ» – 1, «Вісник Дніпропетровського національного університету залізничного транспорту» – 2, з них 11 одноосібно. Праць і тез доповідей наукових конференцій – 41.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, семи розділів, висновків, трьох додатків і списку використаної літератури з 261 найменувань. Загальний обсяг роботи – 357 сторінка, 49 рисунків (1 на окремій сторінці), 35 таблиць (2 з них на 5 окремих сторінках), основний текст роботи викладено на 275 сторінках.

ЗМІСТ РОБОТИ

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

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

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

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

З метою виявлення суттєвої залежності часу виконання алгоритмів від архітектури ЕОМ було проведено комп’ютерний експеримент 1. На двох ПЕОМ з різними процесорами Intel виконувалися алгоритми сортування. На вхід подавалися однакові масиви випадкових чисел, що містилися в оперативній пам’яті. Виконання здійснювалося під управлінням ОС Windows, усі системні й прикладні процеси, крім життєво необхідних для ОС, були зупинені.

У ряді випадків стійко повторювалася ситуація, коли один алгоритм виконувався швидше за інший на одному комп’ютері й повільніше на іншому. Також виявлені випадки, коли на одній ПЕОМ алгоритми з більшою кількістю команд виконувалися швидше, ніж з меншою за однакових вхідних даних і однакових інших умов.

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

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

У другому розділі описані розроблені формальні моделі алгоритмів. На основі формальних структур, які задаються впорядкованою трійкою з множиною сигнатурою  та аксіоматикою :

,

(1)

запропоновані моделі алгоритмічних структур (АС):

,

(2)

де  – скінченна множина утворюючих алгоритмів, які задані на носії, у загальному випадку неоднорідній множині , X(A), Y(A) – множини визначень та значень алгоритму A.

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

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

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

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

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

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

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

Часова ефективність алгоритму визначається функцією

(3)

де обсяг, t тип, значення вхідних даних відповідно, програмне середовище створення та функціонування *. exe файла,  – архітектура ЕОМ.

За наявності декількох функціонально еквівалентних алгоритмів слід порівняти функції

(4)

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

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

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

  •  ступінь переваги одного (i-го) алгоритму над іншим (j-м) на обмежених множинах, що є підмножинами зазначених вище множин     як функціонал:

(5)

де N – загальна кількість доданків,  – ступінь переваги i-го алгоритму над j-м в точці, яка визначається як

,

(6)

де  – час виконання i-го алгоритму;

  •  область переваги:

(7)

де ознака переваги i-го алгоритму над j-м у точці

(8)

  •  перевагу за межами:

.

(9)

Вважаючи, що множини дискретні й обмежені, їх можна відобразити на множину натуральних чисел = {1,2, ... }, ...  ={1,2, ... } відповідно, при цьому:

.

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

В області =[1…+1][1…+1][1…+1] визначимо:

,

(10)

де , і замінимо суму інтегралом:

(11)

Якщо  або  є безперервними, відповідні суми в (5), (7) і (9) спочатку замінюються інтегралами і відпадає необхідність у переході до (10).

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

Як відомо, оцінкою математичного сподівання є величина

.

(12)

S- оцінку ступеня переваги i-го алгоритму над j-м (5) визначимо як

.

(13)

Проводиться оцінка довірчих інтервалів:

.

(14)

Значення  визначаються експериментально.

Оцінка R- показника розраховується аналогічно оцінці S- показника. Для оцінки L- показника застосовуються методи регресійного аналізу.

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

В експерименті 2 дослідження виконувалося на восьми відомих алгоритмах сортування, які наведені в роботі Н. Вірта "Алгоритми + структури даних = програма". На одній ПЕОМ в однаковому і стабільному програмному середовищі виконано 44-54 реалізації кожного алгоритму з  елементами масивів та 12 різними типами даних. Результати показали значну перевагу алгоритмів швидкого і пірамідального сортування над іншими алгоритмами (значення всіх S-R-L- показників близько 100 %), що повністю узгоджується з відомими даними.Водночас відзначено незначну перевагу швидкого сортування над пірамідальним () майже в усій області дослідження ().

В експерименті 3 ці самі алгоритми досліджувалися при  , експериментальній базі з чотирьох ПЕОМ різних модифікацій і двома модифікаціями середовища формування і виконання *.exe файла. В експерименті 4, на відміну від попереднього, при однаковому програмному середовищі досліджувалося 12 модифікацій комп’ютерів з процесорами Intel. Визначені S-R-L- показники часової ефективності алгоритмів частково наведені у табл. 1. Результати експериментів 2, 3 та 4 досить добре узгоджуються між собою відповідні показники в основному не виходять за довірчі інтервали і практично не розходяться більше, ніж на 10 %.

Таблиця 1

S-R-L- показники часової ефективності алгоритмів сортування

Алгоритми сортування

Швидке сортування 

Х

-9

100

100

100

100

100

100

Пірамідальне сортування 

9

Х

100

100

100

100

100

100

Прямим включенням 

0,0

-100

0,0

-100

Х

33

22

Шейкер -
сортування
 

0,0

-100

0,0

-100

-33

Х

-11

Простим вибором 

0,0

-100

0,0

-100

-22

11

Х

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

Порівнюючи ступінь переваги алгоритму швидкого сортування над алгоритмами з обчислювальною складністю  в досліджуваній області, яка склала 98...99,9 %, і ступінь переваги паралельно виконуваних алгоритмів у кращому випадку над послідовно виконуваними, що для 30 ЕОМ (процесорів) становить 96 %, черговий раз переконуємося в пріоритетній необхідності якісної алгоритмізації. Це, у свою чергу, передбачає наявність відповідних критеріїв, показників і оцінок ефективності, чому і присвячений даний розділ.

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

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

У роботі проаналізовано два класи алгоритмів: стиснення даних та кластеризації. На основі аналізу виділено основні джерела нечіткості:

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

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

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

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

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

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

  •  ступінь переваги одного (i-го) алгоритму над іншим (j-м) на обмеженій множині :

,

(15)

де N загальна кількість доданків,   оцінка якості отриманих алгоритмом результатів,  – функція, яка реалізує i-й алгоритм, наприклад розмір стисненого файла;

  •  область переваги:

.

(16)

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

З метою дослідження можливості застосування показників функціональної ефективності алгоритмів у задачах вибору з ряду альтернативних для вирішення конкретних завдань виконано експеримент 6. На вибірці з 14 000 файлів загальним обсягом 4Гб форматів *.doc, *.xls, *.bmp, *.tif досліджувалася функціональна ефективність архіваторів. Встановлено, що при стисненні файлів формату *.doc і *.xls явну перевагу має архіватор 7-Zip (стискає файли *.doc на 10 ... 20 % краще за інших, файли *.xls  на 7 ... 13 %), для файлів * .bmp архіватори WinRAR, WinACE, 7-Zip приблизно рівноцінні й кращі за інших на 5...10 %, файли *.tif всі архіватори стискають приблизно однаково.

Для оцінки можливостей вибору алгоритмів на основі показників функціональної ефективності з урахуванням структури та обсягу даних виконано експеримент 7. Його можна вважати уточненням попереднього. Доповнюючи методику попереднього експерименту, під час стиснення файлів формату MS Word враховувався різний ступінь заповнення файлів такими складовими, як текст, вставлені об’єкти, таблиці, рисунки та рисунки, створені засобами MS Word. Встановлено, що архіватор 7-Zip 3.12 має перевагу над іншими архіваторами за S-оцінкою. При цьому вміст файлів майже не позначається на його перевазі. Лише наявність таблиць та рисунків MS Word деякою мірою знижує цю перевагу, однак у межах довірчих інтервалів.

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

У п’ятому розділі подані дослідження часової ефективності алгоритмів. Мова йде про спеціалізацію оцінок часової ефективності алгоритмів при всіх фіксованих чинниках впливу на час виконання алгоритмів (3), за винятком одного з елементів архітектури ЕОМ  кеш-пам’яті.

Час виконання операції обробки даних мов програмування визначається таким чином:

(17)

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

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

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

Метою експерименту 8 була оцінка часу доступу до позиції та до даних. Різниця в часі виконання циклу з оператором присвоювання структурованих даних (елемента масиву) і неструктурованих дозволяє визначити час доступу до позиції.

Слід очікувати, що час доступу до даних буде значно відрізнятися, залежно від кількості промахів у кеші. Тому для оцінки часу доступу до даних експеримент виконувався таким чином.

У циклі перебувала лише одна операція для дослідження, а саме: i:= x [i]. При цьому по-різному формувався масив х. У першому випадку . При цьому в циклі постійно йшло звернення до одного елемента масиву, який після перших проходів циклу вже потрапляв у кеш. Можна вважати, що перший випадок відповідає ситуації, коли структуровані дані постійно містяться в кеші. Виміряний час виконання циклу позначимо .

У другому випадку . При цьому в циклі виконувалася послідовна вибірка елементів масиву. Якщо час виконання цього циклу позначити , то  – мінімальний час доступу до елементів масиву.

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

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

Експеримент виконувався на восьми комп’ютерах з процесорами Intel і AMD різних модифікацій.

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

Для оцінки часу доступу до динамічних даних виконано експеримент 9. На тій самій експериментальній базі визначений час доступу до елемента даних становить 0...325 тактів при чотирибайтових адресах. Для доступу до елемента в динамічному ланцюжку потрібно багаторазове виконання операції доступу до даних для всіх проміжних елементів. У найгіршому випадку час доступу до даних може на декілька порядків перевищувати час обробки даних.

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

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

У прямому комп’ютерному експерименті 11 показано, що прискорення часу виконання алгоритмів сортування зі зростанням обсягу даних значно збільшується, коли обсяг даних перевищує розмір кеша. Встановлено, що загальноприйняті ймовірнісні методи оцінки часу виконання алгоритмів не узгоджуються з експериментальними даними при існуючому кешуванні даних. Для прикладу на рис. 1 наведені залежності часу сортування прямим включенням від кількості елементів масиву. Маркерами помічені експериментальні дані, середні із дев’яти вимірювань. Крива 1 відображає залежність  з визначеними за експерементальними даними методом найменших квадратів коефіцієнтами; крива 2 – з урахуванням визначених Д. Кнутом залежностей кількості порівнянь та пересилок від кількості елементів при сортуванні масиву за цим алгоритмом та експериментально визначеними методом найменших квадратів значеннями часу операцій пересилки та порівняння; крива 3 – запропоновані залежності у вигляді:

,

з визначеними коефіцієнтами та  тим самим способом.

Рис. 1. Залежність часу сортування від кількості елементів масиву

Для оцінки чутливості алгоритмів до кешування даних (ефект нестатку кешу) запропоновано два показники: 

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

Показано, що ці показники є спеціалізацією запропонованого в третьому розділі S-показника часової ефективності алгоритмів.

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

Висунуто гіпотезу про те, що в разі збільшенні тривалості операцій обробки даних та збереження порядку доступу до даних слід очікувати зниження показників  і , та навпаки: зі збільшенням розмірів елементарних даних (підвищення частки операцій доступу до даних) показники  і  повинні збільшуватися. Ця гіпотеза підтверджена теоретичними дослідженнями й експериментально (експерименти 13 та 14). Таким чином показано, що в деяких випадках для визначення граничних статистичних оцінок не обов’язково проводити комп’ютерні експерименти, а можна скористатися результатами раніше проведених.

Усі експерименти дисертаційного дослідження виконані у багатозадачній ОС Windows різних версій. Тільки експерименти 12-14 – у MS DOS. Передбачалося, що в багатозадачній ОС кеш різною мірою використовується всіма задачами і прикладному алгоритму (реалізованому в деякій програмі-процесі) буде виділятися лише частка кешу даних, розмір якої буде динамічно змінюватися. Нестаток кешу буде посилюватися, і тим більше, чим вище показники  і . Показники, отримані за результатами експериментів у однозадачній ОС, можна розглядати як нижню границю відповідних оцінок.

Для оцінки ступеня впливу багатозадачних ОС на показники  і  виконаний експеримент 15. Порівняння залежностей часу виконання алгоритмів сортування від обсягів даних в ОС Windows і MS DOS показало, що при достатньому розмірі кешу залежності завжди практично збігаються. У разі нестачі кешу час сортування в ОС Windows завжди більше, ніж в MS DOS і залежності в ОС Windows можуть мати суттєві спотворення. Отже, показники  і  доцільно визначати в однозадачних ОС.

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

Якщо обчислення на одному ядрі (при другому незавантаженому) тривало 67 годин, то при одночасному виконанні – на одному ядрі 89 годин, на другому – 247 годин. Зниження ефективності алгоритмів пояснюється конкуренцією за кеш-пам’ять, необхідністю додаткових завантажень даних, витіснених конкуруючим процесом, у кеш. Попутно експериментально встановлено нерівноправне обслуговування ядер процесора кеш-пам’яттю.

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

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

Для оцінки часу виконання команд обробки даних процесора Intel з урахуванням конвеєризації проведений експеримент 17. Методика експерименту близька до експерименту 8. Вимірювався час виконання циклу, у який по черзі вставлялося 30...80 повторень досліджуваної команди. Результати експерименту свідчать про те, що збільшення кількості команд у циклі не завжди приводить до збільшення часу його виконання. Для деяких команд збільшення кількості на 3-6 не змінює час виконання циклу, наступна додана команда цей час стрімко збільшує. У окремих випадках додавання однієї команди призводить до зниження часу виконання циклу, однак завжди спостерігається певна циклічність. Типові приклади наведені на рис. 2.

Рис. 2. Залежність часу виконання циклу від кратності досліджуваних команд

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

(18)

де кількість проходів циклу, – на скільки змінена кількість команд за період, тактова частота процесора, – середні зміни за період  по осях  (кількість повторень команд) та  (час виконання циклу) при  випробуваннях:

.

(19)

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

Для оцінки впливу багатозадачності ОС на чистоту експерименту виконано подібний експеримент 18 у MS DOS. Аналіз результатів показує, що отримані значення експериментів 17 та 18 добре корелюють між собою, що свідчить про можливість отримання вказаних оцінок у більш доступних середовищах багатозадачних ОС.

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

Запропоновано такі методи оцінки часової ефективності ПС.

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

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

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

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

Цей метод є спеціалізацію 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 останніх алгоритмів співпадають.

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

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

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

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В

ТАКИХ РОБОТАХ:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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.

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.

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.

Шинкаренко Віктор Іванович

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

автореферат

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

Надруковано згідно з оригіналом автора

Підписано до друку 19.11.10 р.Формат .

Ум. друк. арк. 1,9. Обл.-вид. арк. 1,95.

Замовлення №       . Наклад 100.

Видавництво Дніпропетровського національного університету

залізничного транспорту імені академіка В. Лазаряна

Свідоцтво суб’єкта видавничої діяльності ДК № 1315 від 31.03.2003.

Адреса видавництва та дільниці оперативної поліграфії:

49010, м. Дніпропетровськ, вул. Лазаряна, 2.

www.diitrvv.dp.ua

 


 

А также другие работы, которые могут Вас заинтересовать

57857. Значення сенсорних систем в психології та медицині 93.5 KB
  Цілі та завдання: узагальнити знання про будову сенсорних систем принцип структури та функції аналізаторів; з‘ясувати значення органів чуття для психології та медицини формувати науковий світогляд виховувати в учнів культуру здоров‘я як складову загальної культури людини.
57858. Дослідження різних видів пам’яті 121 KB
  Мета: ознайомити з основними видами пам’яті; розкрити фізіологічний механізм пам’яті; поглибити знання учнів про шкідливий вплив алкоголю, нікотину, наркотичних речовин на пам’ять; усвідомити можливість розвитку пам’яті.
57859. Різноманітність грибів, їх роль у природі, житті та господарській діяльності людини 183.5 KB
  Мета уроку: познайомити учнів з різноманітністю грибів показати їх роль в природі житті та господарській діяльності людини; вчити дітей розпізнавати різні гриби розвивати навички роботи з додатковою літературою...
57860. Характеристика класу Однодольні. Рослини родини Злакові 161 KB
  Мета. Охарактеризувати рослини класу Однодольні продовжити формування в учнів навичок складання порівняльної характеристики спрямувати пізнавальну активність учнів на вивчення рослин родини Злакові з’ясувати їх практичне використання людиною.
57861. Відкриття європейців 44.5 KB
  Кого з Великих мореплавців ви пам’ятаєте ІІІ. Мотивація навчальної діяльності Сьогодні на уроці ми починаємо вивчати нову тему Слайд 1 Великі географічні відкриття дізнаємося про основний перебіг Великих географічних відкриттів і подорожей ХV – ХVІ століття.
57862. Революція у Франції. Бонопартистський переворот 1851р. і Встановлення імперії 85 KB
  Задачі уроку: Сприяти тому, щоб учні могли грамотно характеризувати причини, хід та рушійні сили революції у Франції, виділяти головні революційні події та оцінювати зміст Конституційних процесів, усвідомили поняття «республіка», «бонапартизм», «монархія».
57863. Географічне середовище як сфера взаємодії суспільства і природи. Природокористування. Ресурсозабезпеченість 37.5 KB
  Мета: розглянути географічне середовище як сферу взаємодії суспільства і природи сформувати поняття ресурсозабезпеченість природокористування; розвивати економічне мислення уміння аналізувати ступені впливу людини на природу...
57864. Енергетика України і проблеми енергозбереження 104.5 KB
  Мета уроку: узагальнити й систематизувати знання учнів про виробництво електроенергії на електростанціях різних типів; показати учням зв’язок енергетики та екологiї їхню взаємодiю шляхи полiпшенню стану енергетики на глобальному та мiсцевому рівнях...
57865. Трудові ресурси і зайнятість населення України 228.5 KB
  Мета: вивчити поняття трудові ресурси економічно активне населення зайнятість населення безробіття; визначити географію трудових ресурсів України; зясувати в чому полягає проблема зайнятості населення...