Основи програмної інженерії

Вид материала

Документы

Содержание 5.2. Теоретичне програмування 5.3. Контрольні питання і завдання 6. Оптимізація програм 6.2. Призначення і цілі оптимізації 6.3. Проміжна мова 6.4. Елементи топології програми 6.4.2. Сильно зв'язана область 6.5. Способи оптимізації 6.5.1. Розвантаження ділянок повторюваності 6.5.2. Скорочення глибини операції 6.5.3. Спрощення дій 6.5.3.1. Видалення індуктивних змінних і виразів 6.5.3.2. Заміна складних операцій на більш прості 6.5.3.3 Виключення надлишкових виразів 6.5.3.4 Інші перетворення 6.5.4. Реалізація дій 6.5.5. Підстановка (згортання) 6.5.6. Чищення програми 6.5.6.1. Усунення ідентичних операторів 6.5.6.2. Заміна змінних в операторах умовного переходу і усунення невикористовуваних визначень. ... Полное содержание

Подобный материал:

• Назва модуля: Моделювання та аналіз програмного забезпечення Код модуля, 36.38kb.
• Емпіричні методи програмної інженерії, 10.35kb.
• Онтологічні моделі опису готових ресурсів у розробці програм, 202.38kb.
• Апаратна складова, 214.38kb.
• Назва модуля: Основи інженерії довкілля. Код модуля, 15.91kb.
• «Основи інформатики. 7 клас», 663.63kb.
• «Основи інформатики. 7 клас», 662.94kb.
• Виступ директора зош №44 Топорікової, 336.95kb.
• Основи навчальної програми враховують вимоги Ради з освіти Міжнародної Федерації бухгалтерів,, 143.95kb.
• Солтисік Роман Андрійович, доцент, к т. н. Федевич Олег Євгенійович, 7 Результати навчання:, 103.84kb.

5.2. Теоретичне програмування

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

Авторами української теоретичної школи програмування, створеної В.М. Глушковим, запропоновані нові парадигми, а саме:

- алгебраїчне та інсерційне програмування (А.А.Летичевський і ін.) [24-26];

- експлікативне та номінативне програмування (В.Н.Редько, М.С.Нікітченко), які використовують логічний і математичний апарат для абстрактного конструювання програм [27-29];

- алгебро-алгоритмічне програмування (Г.О. Цейтлін), що поєднує алгебраїчний апарат і теорію алгоритмів [30-31 ].

5.3. Контрольні питання і завдання

1. Охарактеризуйте структурні методи програмування.

2. Наведіть основні особливості і можливості об'єктно-орієнтованого програмування.

3. Які діаграми є в мові UML для візуального проектування програм?

4. Наведіть основні типи компонентів і шляхи їхнього використання.

5. Назвіть базові поняття в компонентному програмуванні.

6. Визначте основні поняття й етапи життєвого циклу у компонентному програмуванні.

7. Визначте основні елементи аспектно-орієнтованого програмування.

8. Визначте основні елементи агентного програмування.

9. Визначте об'єкти генерувального програмування і наведіть призначення.

10. Що таке простір проблем і простір рішень?

11. Наведіть теоретичні методи програмування.

12. Охарактеризуйте алгебраїчне програмування.

13. Що таке алгоритміка і її алгебра?

14. Покажіть сутність переходу до інших алгебр.

6. Оптимізація програм

6.1 Основні поняття.


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

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

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

Розрізняються дві основні категорії оптимізуючих перетворень:

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

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

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

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

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


6.2. Призначення і цілі оптимізації


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

У процесі оптимізації транслятор виконує наступні дії:

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

6.3. Проміжна мова

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

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

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

а) оператори мови не повинні бути занадто дрібними;

б) символи, ідентифікатори і константи повинні мати фіксований формат;

в) в усторої операторів бажана відсутність рекурсивності;

г) повинна зберігатися вся інформація у вхідній мові, що є необхідною для оптимізації;

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

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

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

(mi) код операції аргументи оператора,

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

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

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

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

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

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

1. Таблиці ідентифікаторів і констант зі звичайною інформацією про змінні і константах.

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

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


6.4. Елементи топології програми


6.4.1. Блок (лінійна ділянка)


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

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

Блок моделює частина програми проміжною мовою, яка містить оператори присвоювання.

Формально модель лінійної ділянки може бути представлена в такий спосіб:

блок B - це трійка виду (P,I,U), де

(1) P - список операторів S1,S2,...Sn (n>=0),

(2) I - множина вхідних змінних,

(3) U - множина вихідних змінних.

При цьому оператором називається ланцюжок (у загальному випадку) виду

A <- Q B1...Br,

де A, B1,..., Br - змінні, а Q - операція.

Тут оператор привласнює значення змінній А та посилається на B1,...,Br.

Якщо оператор Sj посилається на А, то або А є вхідною змінною, або здійснене присвоювання їй значення деяким оператором до Sj, (тобто деяким оператором Si, (і
Оператор S у програмі називається входом у лінійну ділянку, якщо він або є першим оператором у програмі, або позначений ідентифікатором, що з'являється в операторі переходу, або безпосередньо йде за умовним оператором.

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


6.4.2. Сильно зв'язана область


Для кожного блоку B=(P,I,U) можна знайти орієнтований ациклічний граф , що представляє цей блок. При цьому кожен лист графа (кінцева вершина) відповідає одній вхідний змінній у I, а кожна його внутрішня вершина - оператору з P. Граф відбиває порядок виконання операторів програми і дає більш наочне представлення, ніж лінійна послідовність операторів.

Якщо вершини і та j графа відповідають ділянкам і та j програми, то дуга йде з і в j, якщо

1) останній оператор ділянки і не є ні оператором переходу, ні оператором зупинки, а ділянка j йде в програмі за ділянкою і чи

2) останній оператор ділянки і є оператором переходу на мітку L, що позначений перший оператор ділянки j.

Сильно зв'язаною областю орієнтованого графа називається така множина його вершин, що для будь-яких двох вершин x і y (x != y) існує шлях з x у y.

Будемо розглядати сильно зв'язані області Ri, що володіють наступними властивостями:

1) Ri є сильно зв'язаною областю, що складається з множини блоків, кожний з яких передує сам собі і йде сам за собою усередині цієї множини;

2) Ri != Rj;

3) для кожного і

6.5. Способи оптимізації


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

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

- розвантаження ділянок повторюваності;

- спрощення дій;

- реалізація дій;

- чищення програми;

- економія пам'яті;

- скорочення програми.


6.5.1. Розвантаження ділянок повторюваності


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

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

попередні результати лінійні чи компоненти групи лінійних

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

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

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

Приклади.

а) Чищення вниз перетворить цикл

for K:=1 to 100 do

begin

X:=X*K;

if Z>0 then Y:=sin(X)

else A[I]:=X+2;

end

до виду:

for K:=1 to 100 do X:=X*K;

if Z>0 then Y:=sin(X);

else A[I]:=X+2;


б) Чищення нагору перетворить цикл

for K:=1 to 100 do

begin

if Z>0 then Y:=1

else Y:=Z+2;

X[K]:=X[K]-Y;

end

до виду

if Z>0 then Y:=1

else Y:=Z+2;

for K:=1 to 100 do X[K]:=X[K]-Y;


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

тіло рекурсивної функції

ціла функція Ф(N)

begin

цілі Z,W;

W:=1;

if X>0 then W:=Y;

if N<=0 then Ф:=1

else

begin

Z:=N-W; Ф:=Z*Ф(Z)

end

end

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

ціла функція Ф(N)

begin

var N:integer;

ціла функція F(M)

begin

var Z:integer;

if M<=0 then F:=1;

else

begin

Z:=M-W;

F:=Z*F(Z)

end

end

W:=1;

if X>0 then W:=Y;

Ф:=F(N);

end;

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

Наприклад, за допомогою цих перетворень фрагмент

for K:=1 then

begin

if N>0 то перехід на L;

N:=N*N;

L: if Z=0 then write(N);

end

N:=100;


може бути перетворений до виду:

for K:=1 to 100 do

if Z=0 then

begin

N:=A[K];

if N>0 then goto L;

N:=N*N;

L: write(N);

end;

N:=100;

6.5.2. Скорочення глибини операції


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

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

Наведемо приклад скорочення глибини операції стосовно оператора t4:=K*10+I з n-го блоку :


n-й блок

L:t4:=K*10+I

t5:=t6+K

z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1

перехід на L


у результаті виконання цієї операції оператор t4:=K*10+I

зсувається в (n-1)-й блок, а в n-му блоці він заміняється оператором t4:=t4+10:

(n-1)-й блок

. . .

t4:=K*10+I

n-й блок

L: z(t2):=z(t2)+x(t4)+y(t5)

K:=K+1

t4:=t4+10

t5:=t6+K

перехід на L


6.5.3. Спрощення дій


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


6.5.3.1. Видалення індуктивних змінних і виразів


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

Наприклад, застосування зазначених перетворень перетворить фрагмент

for I:=1 to 99 do

begin

K:=I+J;

A[K]:= A[K]+1

end;

K:=10;

у фрагмент

I:=1;

for K:=I+J to 99+J do

begin

A[K]:= A[K]+1

end;

K:=10;

Тут I,K - індуктивні змінні. У даному випадку з циклу видалений індуктивний вираз K:=I+J.


6.5.3.2. Заміна складних операцій на більш прості


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

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

for K:=1 to 100 do

V:=(K-1)*N+I

до більш ефективно працюючого фрагмента:

V:=I;

for K:=1 to 100 do

begin

A[V]:=A[V]+1;

V:=V+N

end

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


6.5.3.3 Виключення надлишкових виразів


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

Наприклад, ця операція здійснює перехід від фрагмента

if B>0 then

begin

A:=A+2;

X:=A*B+C

end

else Y:=A*B+D;

Z:= A*B;

до фрагмента

if B>0 then

begin

A:=A+2;

W:=A*B;

X:=W+C

end

else

begin

W:=A*B;

Y:=W+D

end;

Z=W;


6.5.3.4 Інші перетворення


У цю же групу входить економія загальних підвиразів, що заміняє, наприклад, оператор:

X:=(A+B)*(A+B+C)/(A+B+E)

на фрагмент Y:=A+B; X:=Y*(Y+C)/(Y+E),

а також такі перетворення, як втягування обчислення параметрів у процедуру, спрощення підстановки параметра-масиву, перебудови умовних операторів (типу заміни оператора, якщо X>0 && Y<2 то Z:=1 на оператор, якщо X>0 то початок якщо Y<2 то Z:=1 кінець), видалення копіювань (зокрема, тих, що заміняють пересилання значень масиву на пересилання його вказівника), інші різні способи перебудови структури інформаційних об'єктів у залежності від характеру їх використання і з метою скорочення часу роботи з об'єктами; різні способи реалізації змінних через швидкі регістри, заміна рекурсії на цикли

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


6.5.4. Реалізація дій


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

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

Реалізація дій здійснюється також при:

• утягуванні констант, коли вирази, що мають тотожно константні значення, заміняються на ці значення;
  
• при аналітичних перетвореннях (наприклад, що заміняють Е*1 на Е чи 0*Е на 0, де Е - довільне підвираз);
  
• ототожненні ( чи втягуванні унікальних), що видаляє з програми оператор-пересилання виду X:=Y, де X і Y - змінні, заміняючи або входження X на Y
  
• утягування нагору (назад) - наприклад, фрагмент Y:=F(W); X:=Y; заміняється на X:=F(W), або входження Y на X - утягування вниз (уперед) - наприклад, X:=Y; якщо Z>0 те W:=Y+1 інакше W:=Y+2 заміняється на фрагмент якщо Z>0 те W:=X+1 інакше W:=X+2.
  

6.5.5. Підстановка (згортання)


Операції, операнди яких відомі під час компіляції, немає необхідності виконувати під час обрахунку.

Підстановка (згортання) - це заміна змінної або mi-ідентифікатора результату заданою чи обчисленою константою, причому ця заміна провадиться під час трансляції, а не в процесі розв'язання.

Згортання головним чином застосовуються до арифметичних операторів +,-,*,/, тому що вони найбільше часто використовуються у вихідній програмі


6.5.6. Чищення програми


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

Набір перетворень цього типу містить у собі наступні оптимізації:

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

6.5.6.1. Усунення ідентичних операторів


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

Оператор F вважається ідентичним і може бути усунутий із програми, якщо існують інші оператори G1,G2,...Gn, такі, що

1) оператор F і всі оператори G1, G2, ... Gn виконують ту саму операцію над тими самими операндами;

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


6.5.6.2. Заміна змінних в операторах умовного переходу і усунення невикористовуваних визначень.


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

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

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

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

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

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


6.5.6.3. Усунення марних операторів і змінних


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

Змінна А називається активною після виконання оператора Si, якщо

- їй привласнене значення оператором Si;

- їй не привласнені значення операторами Si+1,...Sj;

- на неї посилається оператор Sj+1.

if оператор Si привласнює значення змінній А і вона неактивна після моменту i, то

- при i>0 можна видалити Si з P

- при i=0 можна видалити A з I

Наприклад, нехай B=(P,I,U), де I={ A,B,C }, U={ F,C } і P складається з

F:=A+A

G:=F*C

F:=A+B

G:=A*B

Другий оператор марний, тому що його область дії порожня. Таким чином, одне застосування перетворення усунення марних операторів відображає B у B1=(P1,I,U), де P1 складається з

F:=A+A

F:=A+B

G:=A*B

Тепер у B1 марна вхідна змінна C і перший оператор. Застосувавши те ж перетворення, можна одержати B2=(P2,{A,B},U), де P2 складається з

F:=A+B

G:=A*B


6.5.7. Економія пам'яті


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

У відповідну групу оптимізацій входять наступні перетворення:

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

Прикладом виконання цього перетворення є заміна функції

ціла функція F(N,M)

begin

ціле K;

if N=M then F:=1

else

begin

K:=M+1;

F:=F(N,K)*K

end

end

на функцію

ціла функція F(N,M)

begin

цила функція G(Z);

begin

ціле K

if N=Z then F:=1

else

begin

K:=Z+1;

F:=F(K)*K

end

end

F:=G(N)

end;

 

6.5.8. Скорочення програми


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

if A>0 then

begin

X:=X+3;

Z:=2

end

else

begin

X:=X+3;

W:=X+4

end

перетвориться до виду

X:=X+3;

if A>0 then Z:=2

else W:=X+4

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

6.5.9. Вставка псевдоблоку


У процесі оптимізації оператори, що зсовуються з блоків, збираються в псевдоблок. Після оптимізації області Rk оператори псевдоблоку повинні бути вставлені в програму так, щоб вони виконувалися до (після) виконання операторів області Ri. Для того, щоб оператори псевдоблоку виконувалися на усіх вхідним (вихідних) шляхах області Rk, вони повинні вставлятися в усі блоки, безпосередньо попередні (наступні) області або з псевдоблоку повинен бути сформований блок, що буде вставлений на усі вхідні (вихідні) шляхи області Rk.

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

1) оператори уставляються в усі блоки, що безпосередньо передують області, що мають тільки один безпосередньо наступний блок. Оператори, що вставляються, записуються перед оператором переходу

2) із псевдоблока створюється формальний блок, що вставляється на усіх вхідних шляхах, що йдуть від безпосередньо попередніх блоків, що мають кілька спадкоємців

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

Це відповідає створенню нового блоку

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

Можна дати деякі приватні рекомендації з оптимізації циклів і лінійних ділянок

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

1) аналіз циклів - виявлення циклів, що підлягають оптимізації й одержання потрібної для оптимізації інформації;

2) винесення за кордон циклів інваріантних операцій;

3) заміна складних операцій

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

7. Навчально-методичні рекомендації до вивчення дисцілини «Основи програмної інженерії.»


7.1. Анотація навчальної дісциплини.

Галузь знань – 0501 «Інформатика та обчислювальна техника»

Напрям підготовки - 6.050103 «Програмна інженерія»

Обсяг курсу 180 год., у тому числі: лекцій 70 год., лабораторних занять 52 год., практичних робіт 18 год, самостійної роботи 40 год, залік 3 сем., іспит 4 сем.

Програмна Інженерія (Software Engineer ing) - наука побудови комп'ютерних програмних систем (ПС), що містить у собі теоретичні концепції, методи і засоби програмування, технологію програмування, системи та інструменти їхньої підтримки, сучасні стандарти, зокрема, процеси життєвого циклу (ЖЦ), вимірювання, оцінювання якості розробки ПС. Головне призначення програмної інженерії - побудова ПС, починаючи з аналізу предметної області (ПрО) і закінчуючи виготовленням вихідного коду для виконання на комп'ютері. Фундаментальну основу побудови ПС становлять: теорія алгоритмів, математична логіка, теорія обчислень, теорія керування й ін.

Колективне розроблення великих проектів ПС обумовило розвиток інженерних, технологічних методів і засобів регламентованого проектування ПС із урахуванням організаційних процесів ЖЦ: інженерія вимог, керування ризиком і якістю, планування і регулювання ресурсів, оцінювання процесів ЖЦ та показників якості, вартості і строків виготовлення програмного продукту.

Ціль даної дисципліни - представити методи і засоби програмної інженерії в структурованому і систематизованому вигляді для теоретичного й практичного навчання процесам проектування, тестування і оцінювання якості програмних систем. У дисципліні відображено зміст програмної інженерії з урахуванням базового ядра знань SWEBOK (k.org) та програми навчання Computing Curricula - 2001, 2004, що застосовується на факультетах інформатики в міжнародних навчальних закладах понад 20 років. Навчання програмній інженерії є запорукою успішного освоєння накопичених міжнародною спільнотою знань з інженерії побудови програмних продуктів.

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


7.2. Необхідність та задачі навчальної дісциплини. Ії місце в учбовому процесі.


Дисципліна «Основи програмної інженерії» входить до «Обов’язкового переліку навчальних дисциплін і практик» циклу професійно-орієнтованої та практичної підготовки згідно Освітньо-професійної програми підготовки бакалавра за фаховим спрямуванням 6.050103 «Програмна інженерія»

Згідно додатку Б до пункту 6 Освітньо-професійної програми підготовки бакалавра за фаховим спрямуванням 6.050103 «Програмна інженерія» дисципліна включає наступні блоки:

3.01	Основи програмної інженерії	Інженерні основи програмного забезпечення	1.ПФ.Е.03.01.01
		Основи моделювання	1.ПФ.Е.02.02.01
		Технології розробки ПЗ	1.ПФ.Е.03.01.02
		Основи інженерії вимог до ПЗ	1.ПФ.Е.02.01.02
		Письмова комунікація	4.ПФ.С.02.01.02

Система змістових модулів дисципліни, щодо складових узагальнених структур діяльності, згідно додатку А до пункту 5 Освітньо-професійної програми підготовки бакалавра за фаховим спрямуванням 6.050103 «Програмна інженерія», наступна:

Зміст уміння, що забезпечується	Шифр уміння	Назва змістового модуля	Шифр змістового модуля
Здійснювати аналіз вимог, розробляти специфікацію програмних вимог, виконувати їхню верифікацію та атестацію	1.ПФ.Е.02.01	Типи вимог, функціональні, не функціональні, атрибути якості	1.ПФ.Е.02.01.01
		Основи інженерії вимог до ПЗ	1.ПФ.Е.02.01.02
		Узгодження вимог і управління ризиками	1.ПФ.Е.02.01.03
Моделювати різні аспекти системи, для якої створюється ПЗ	1.ПФ.Е.02.02	Основи моделювання	1.ПФ.Е.02.02.01
		Типи моделей	1.ПФ.Е.02.02.02
		Основні концепції уніфікованої мови моделювання UML	1.ПФ.Е.02.02.03
Проектувати компоненти архітектурного рішення	1.ПФ.Е.03.01	Інженерні основи програмного забезпечення	1.ПФ.Е.03.01.01
		Технології розробки ПЗ	1.ПФ.Е.03.01.02
		Структура та архітектура ПЗ	1.ПФ.Е.03.01.03
		Стратегії і методи проектування ПЗ	1.ПФ.Е.03.01.04
		Аналіз якості та оцінка програмного дизайну	1.ПФ.Е.03.01.05
		Нотації та засоби підтримки проектування	1.ПФ.Е.03.01.06
Створювати чітку, стислу та точну технічну документацію у відповідності до діючих стандартів	4.ПФ.С.02.01	Рецензувати письмову технічну документацію з метою виявлення різного роду проблем	4.ПФ.С.02.01.01
		Письмова комунікація	4.ПФ.С.02.01.02

У дисципліні відображено зміст програмної інженерії з урахуванням базового ядра знань SWEBOK (k.org) та програми навчання Computing Curricula

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

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

Зміст дисципліни розкривається в темах:

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

2. Стандарт і моделі життєвого циклу. Характеристики базових моделей ЖЦ, що використовуються на практиці. Основні положення стандарту 1SO/IEC 12207 і підходи до формування на його основі робочих моделей ЖЦ.

3. Аналіз та визначення вимог до програмних систем. Загальні підходи, методи аналізу предметної області та формування вимог до ПС.

4. Методи об'єктного аналізу і моделювання. Огляд методів об'єктного аналізу, побудови моделей предметних областей та проектування архітектури системи.

5. Прикладні і теоретичні методи програмування. Аналіз прикладних, теоретичних і формальних методів програмування, а також огляд їхніх засобів щодо подання та розробки ПС.

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

7. Інтерфейс, взаємодія, еволюція програм та даних. Методи інтеграції, проблеми взаємодії різномовних програм і даних у сучасних середовищах, а також методи еволюційної зміни компонентів і систем, характеристика стандарту ISO/IEC 11404-96 з опису даних, незалежних мов програмування.

8. Інженерія виробництва програмних продуктів. Базові характеристики інженерії виробництва компонентів, предметної області готових компонентів та лінії виробництва програмних продуктів, особливості сучасних середовищ для колективного виробництва ПС.

9. Моделі якості та надійності програмних систем. Моделі якості, метрики і методи виміру показників якості ПС. Класифікація математичних моделей надійності та підходи до оцінки надійності програмного продукту за деякими моделями.

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

У результаті вивчання даної дисципліни студенти повинні:

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

Дисціплина підтримується курсами Основи програмування, Об’єктно-орієнтоване програмування.

Форма контролю.

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

Співвідношення оцінок за національною шкалою (чотирибальною), шкалою ECTS (семибальною) та шкалою навчального закладу (стобальною) наступне:

За національною шкалою	За шкалою навчального закладу		Шкалою ECTS
Відмінно	90-100	90-100	А
Добре	75-89	85-89	В
		75-84	С
Задовільно	60-74	67-74	D
		60-66	E
Незадовільно ( з можливістю повторного складання)	35-59	35-59	FX
Незадовільно ( з обов’язковим повторним курсом)	1-34	1-34	F