Solid Optimizer Project

Цели

Да се изградят различни представяния (модели) със съответни междумоделни трансформации, които да бъдат интегрирани в SolidOpt. Предназначението им е да предоставят подходяща структура от данни за разработване оптимизационни методи.

Описание

Това е работно заглавие на тема, подходяща за дипломна работа във ФМИ на ПУ “Паисий Хилендарски”.

В заданието се предвиждат следните представяния: Control Flow Graph (CFG), Three Address Code (TAC) и Static Single Assignment (SSA).

CFG представя програмата като свързани помежду си блокове. Блокът представлява съвкупност от инструкции, които се изпълняват една след друга и евентуално завършват с инструкция за преход или възврат.

В три-адресното представяне се съдържат следните оператори:

x = y op z

където x, y, z са променливи, константи или временни променливи, а op представлява оператор (например, аритметичен оператор).

Аналогично се представят и условните преходи:

Пример на C
Три-адресно представяне

int main(void) {

    int i;

    int b[10];

    for (i = 0; i < 10; ++i) {

    b[i] = i*i;

    }

 }

   i = 0

L1: if i >= 10 goto L2

   t0 = i * i

   t1 = &b

   t2 := t1 + I

   *t2 := t0

   i := i + 1

   goto L1

L2:

Единичното статично присвояване се различава от три-адресното представяне основно в две направления. Първото е, че присвояванията са на две различни променливи. Например:

Три-адресно представяне
SSA

p = a + b

q = p – c

p = q * d

p = e – p

q = p + q

p<sub>1</sub> = a + b

q<sub>1</sub> = p<sub>1</sub> – c

p<sub>2</sub> = q<sub>1</sub> * d

p<sub>3</sub> = e – p<sub>2</sub>

q<sub>2</sub> = p<sub>3</sub> - q<sub>1</sub>

Обаче една и съща променлива би могла да бъде дефинирана в различен път от последователността на изпълнение. Например:

if (flag) x = -1; else x = 1;

	y = x * a;

има две различни последователности на изпълнение, при които x ще получи различна стойност. При това положение, ако използваме различни имена на x няма да бъде ясно коя стойност ще бъде присвоена на y.

Втората отличителна черта на SSA идва на помощ. SSA използва конвенция за отбелязване наречена ϕ-функция, която комбинира двете дефиниции на x:

  if (flag) x<sub>1</sub> = -1; else x<sub>2</sub> = 1;

	x<sub>3</sub> = ϕ (x1, x2);

Трябва да се разработят и съответните междумоделни трансформации (компилация и декомпилация) от и към известните представяния в инструментариума.

Областта на дипломната работа е интересна, като има добра основа за развитие. Дипломантите ще придобият по-широки познания по програмиране, оптимизирането на приложения и разработката междинни представяния за транслатори.

Разяснения

Програмният език е нотация, чрез която хората описват изчисленията, които трябва да бъдат изпълнени от машина. Целият софтуер за всички компютри е написан на някакъв програмен език. Следователно софтуерът може да се разглежда като предписание, решаващо конкретна задача от реалния свят. А всяко предписание или алгоритъм, описващ част от реалния свят е модел (представяне). Може да се направи заключението, че софтуерната програма е модел на изпълнение за намиране на решение на даден проблем. Моделират се последователността от стъпки, които трябва да се извършат за достигане на задоволително решение.

Програмните езици непрекъснато се променят, като се стремят да се доближат максимално до естествения език. Създават се различни семантично-еквивалентни конструкции (понякога и синтактична захар), които предоставят удобство и лекота при програмиране. С други думи основната цел на тези изменения е да се улесни максимално разработчика на софтуер.

С течение на времето и моделът на програмата би трябвало да става все по-абстрактен и все по-близък до естествения език, т.е. да се превръща в модел, по-ясен за разработчика. Това води до необходимостта от приложения, свеждащи до модел от ниско ниво, изпълним от конкретна виртуално-изчислителна машина (ВИМ или абстрактен изпълнител). Този процес (познат като транслация) води до загуба на информация за модела от високо ниво и в частност до създаване на неоптимален код за изпълнение. Неоптималната транслация е следствие на три основни причини:

• Липса или недостатъчно добре реализирани оптимизиращи модули в транслатора;
• Неизползване на пълните възможности на ВИМ;
• Неизползване на знания за приложната област на модела;
• Неизползване на пълната информация налична в модела от високо ниво.

Софтуерните приложения могат да се разглеждат като модел, от който да се получават оптимално работещи системи (приложения). Изходният код остава непроменен, като за оптималността на модела се грижи специализирана софтуерна подсистема (SolidOpt). Едно от важните предимства на подхода е, че могат да бъдат прилагани концептуално различни софтуерни трансформации в зависимост от зададените цели. Освен това, от основния алгоритъм могат да се изнесат всички техники, които служат за постигане на оптималната му работа. С други думи в модела трябва да остане единствено моделираното решение на проблема от реалния свят без допълнителни техники за оптимизиране на изпълнението му.

Наличието на специализирана софтуерна подсистема позволява разделение между модела, генериран от разработчика и модела (за изпълнение), генериран от транслатора. Следователно за получаването на оптимални приложения не се изискват промени в модела на разработчика. Основно изискване остава моделите да бъдат семантично еквивалентни.

При транслация до изпълним модел се използват множество представяния (модели). Преминаването от един модел в друг не е новост при разработката на софтуер. Много от използваните модели са качествено различни, т.е. разликата в нивото им на абстракция е голяма. Поради това много от трансформациите от един модел в друг са неясни и често необратими.

Използването на множество модели с ясни и обозрими механизми за трансформация би позволило много по-фино транслиране и оптимизиране на компютърните програми. Тази идея е основополагаща за разработвания от нас инструментариум SolidOpt.

Създаването на една такава многомоделна архитектура, каквато е показана на Фигура 2-1. обобщава трансформирането на софтуерния модел от високо ниво до модел, изпълним от ВИМ. В зависимост от целите, етапите (междинните модели) през които преминава трансформацията може да са произволен брой.

Transformation optimization method (hereinafter optimization method or just optimization) in terms of the framework SolidOpt is a module that converts the software program so that it satisfies some conditions. Most often, these conditions represent a kind of metrics by which to evaluate a quality system. For example, performance metrics, metrics for energy consumption, etc.

Оne of the objectives of SolidOpt is to propose enough models for performing optimization transformations.

The following scheme is basis of the framework

Figure 2-1: Interactions between the models

On figure 2-1 used the following names:

• M_i - a level of abstraction of the model where i ∈ [0,n]. M₀ is target model i.e. M₀is the executable program;
• T_Mi,T^-1_Mi - transformation of the model wherei ∈ [0,n]. Keep the level of abstractionof the model;
• T_i,T^-1_i - transformation between the models where i ∈ [0,n-1]. Change the level of abstraction.

The scheme describes the relationship between models and ways of lowering and raising the level of abstraction. Also shows the mechanism of transformation of the model.

Using thus determined methodology would facilitate the establishment of optimization methods, operating at different levels. This provides flexibility in the development of sophisticated optimizations such as merging of classes, the restructuring of ABB and others. To achieve better results, you may need some optimization to work on several levels of abstraction of the model.

Required knowledge

it is appropriate to have knowledge in the following technologies:

• C#
• .NET/Mono/CIL/CLI