Title
Побољшање перформанси програма употребом делимично контекстно осетљивих профила
Creator
Vukasović, Maja, 1993-
CONOR:
71296009
Copyright date
2023
Object Links
Select license
Autorstvo-Nekomercijalno-Bez prerade 3.0 Srbija (CC BY-NC-ND 3.0)
License description
Dozvoljavate samo preuzimanje i distribuciju dela, ako/dok se pravilno naznačava ime autora, bez ikakvih promena dela i bez prava komercijalnog korišćenja dela. Ova licenca je najstroža CC licenca. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/deed.sr_LATN. Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc-nd/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Theses Type
Doktorska disertacija
description
Datum odbrane: 16.01.2024.
Other responsibilities
Academic Expertise
Tehničko-tehnološke nauke
University
Univerzitet u Beogradu
Faculty
Elektrotehnički fakultet
Alternative title
Improving program performance with partially context-sensitive profiles
Publisher
[М. Вукасовић]
Format
135 листова
description
Рачунарска техника и информатика - Софтверско инжењерство / Сomputer science and information technology -
Software engineering
Abstract (sr)
Велика предност компајлера који раде превођење у току извршавања програма
(JIT преводиоци) јесте доступност профила, који садрже информације о извршавању
програма, током превођења. Профили усмеравају поредак превођења и оптимизације,
које утичу на убрзавање извршавања програма. Превођење пре времена извршавања
(AOT превођење) такође може да користи профиле, али добијене засебним извршава-
њима програма, намењеним прикупљању профила. Профили садрже метричке податке
везане за програмски контекст. У зависности од дела програмског стека садржаног у
контекстима профила, они могу бити контекстно осетљиви или неосетљиви. Како би се
поједноставио процес прикупљања профила и смањила његова цена, уз очување преци-
зности, у многим системима се прикупљају делимично контекстно осетљиви профили,
који садрже само суфикс програмског стека. Иако је уложено доста истраживачких
напора у овој области, и даље постоји значајан потенцијал за унапређење перформанси
програма на основу делимично контекстно осетљивих профила.
У овој тези је описан нов алгоритам под називом PRINC за унапређење процеса
превођења и оптимизације инлајновања коришћењем делимично контекстно осетљивих
профила. На основу профила, алгоритам идентификује често извршаване секције кода
и преводи их са већим буџетом за оптимизације, притом не увећавајући значајно ве-
личину извршног кода. Ова техника је погодна за имплементацију у оквиру већине
AOT преводилаца, који могу да користе делимично контекстно осетљиве профиле. Ал-
горитам PRINC укључује компоненту за детекцију често извршаваног кода како би ре-
конструисао значајне целине кода, чијом агресивнијом оптимизацијом се постижу боље
перформансе целокупног програма. Распоред превођења и оптимизација инлајновања
су модификовани тако да користе информације о често извршаваном коду.
У тези је формално описан предложени алгоритам, укључујући његове компоненте
и хеуристике. Такође, алгоритам PRINC је имплементиран као саставни део савременог
AOT преводиоца GraalVM Native Image, а значајни делови имплементације су такође
приказани у раду. Исцрпном евалуацијом предложеног алгоритма над 16 бенчмарка из
скупова DaCapo, Scalabench и Renaissance показано је побољшање времена извршава-
ња програма између 22% и 40% за 4 бенчмарка и између 2.5% и 10% за 5 бенчмарка.
Увећање генерисаног кода варира између 0.8% и 9%, док је у случају 10 бенчмарка
оно испод 2.5%. На основу добијених резултата показан је значајан потенцијал за уна-
пређење перформанси, а у оквиру квалитативне евалуације показано је да алгоритам
може бити имплементиран и у другим оптимизационим компајлерима уз адекватно при-
лагођавање конкретном окружењу.
Abstract (en)
Availability of profiling information is a major advantage of just-in-time (JIT)
compilation. Profiles guide the compilation order and optimizations, thus substantially
improving program performance. Ahead-of-time (AOT) compilation can also utilize profiles,
obtained during separate profiling runs of the programs. Profiles can be context-sensitive, i.e.,
each profile entry is associated with a call-stack. To ease profile collection and reduce overheads,
many systems collect partially context-sensitive profiles, which record only a call-stack suffix.
Although there exists a significant portion of prior research work, there is still a lot of potential
for further program performance improvement using partially context-sensitive profiles.
This thesis describes a novel technique that exploits partially context-sensitive profiles
to determine which portions of code are hot, and compile them with additional compilation
budget. This technique is applicable to most AOT compilers that can access partially context-
sensitive profiles, and its goal is to improve program performance without significantly
increasing code size. The technique relies on a new hot-code-detection algorithm to reconstruct
hot regions based on the partial profiles. The compilation ordering and the inlining of the
compiler are modified to exploit the information about the hot code. Proposed algorithm,
named PRINC, is formally described, after which follows the description of the production-
ready implementation inside GraalVM Native Image, a state-of-the-art AOT compiler for
Java. Evaluation of the proposed technique on 16 benchmarks from DaCapo, Scalabench and
Renaissance suites shows a performance improvement between 22% and 40% on 4 benchmarks,
and between 2.5% and 10% on 5 benchmarks. Code-size increase ranges from 0.8 − 9%, where
10 benchmarks exhibit an increase of less than 2.5%. Based on the evaluation results it is
proven that there exists a great potential for performance improvement and that the algorithm
can be implemented in other modern compilers with respective algorithm adjustment.
Authors Key words
превођење, AOT преводиоци, распоред превођења, оптимизација инлај-
новања, профили, делимично контекстно осетљиви профили
Authors Key words
compilation, AOT compilers, compilation schedule, inlining optimization, profiles,
partially context-sensitive profiles
Classification
004.4`234:004.4`422:621.394.67(043.3)
Type
Tekst
Abstract (sr)
Велика предност компајлера који раде превођење у току извршавања програма
(JIT преводиоци) јесте доступност профила, који садрже информације о извршавању
програма, током превођења. Профили усмеравају поредак превођења и оптимизације,
које утичу на убрзавање извршавања програма. Превођење пре времена извршавања
(AOT превођење) такође може да користи профиле, али добијене засебним извршава-
њима програма, намењеним прикупљању профила. Профили садрже метричке податке
везане за програмски контекст. У зависности од дела програмског стека садржаног у
контекстима профила, они могу бити контекстно осетљиви или неосетљиви. Како би се
поједноставио процес прикупљања профила и смањила његова цена, уз очување преци-
зности, у многим системима се прикупљају делимично контекстно осетљиви профили,
који садрже само суфикс програмског стека. Иако је уложено доста истраживачких
напора у овој области, и даље постоји значајан потенцијал за унапређење перформанси
програма на основу делимично контекстно осетљивих профила.
У овој тези је описан нов алгоритам под називом PRINC за унапређење процеса
превођења и оптимизације инлајновања коришћењем делимично контекстно осетљивих
профила. На основу профила, алгоритам идентификује често извршаване секције кода
и преводи их са већим буџетом за оптимизације, притом не увећавајући значајно ве-
личину извршног кода. Ова техника је погодна за имплементацију у оквиру већине
AOT преводилаца, који могу да користе делимично контекстно осетљиве профиле. Ал-
горитам PRINC укључује компоненту за детекцију често извршаваног кода како би ре-
конструисао значајне целине кода, чијом агресивнијом оптимизацијом се постижу боље
перформансе целокупног програма. Распоред превођења и оптимизација инлајновања
су модификовани тако да користе информације о често извршаваном коду.
У тези је формално описан предложени алгоритам, укључујући његове компоненте
и хеуристике. Такође, алгоритам PRINC је имплементиран као саставни део савременог
AOT преводиоца GraalVM Native Image, а значајни делови имплементације су такође
приказани у раду. Исцрпном евалуацијом предложеног алгоритма над 16 бенчмарка из
скупова DaCapo, Scalabench и Renaissance показано је побољшање времена извршава-
ња програма између 22% и 40% за 4 бенчмарка и између 2.5% и 10% за 5 бенчмарка.
Увећање генерисаног кода варира између 0.8% и 9%, док је у случају 10 бенчмарка
оно испод 2.5%. На основу добијених резултата показан је значајан потенцијал за уна-
пређење перформанси, а у оквиру квалитативне евалуације показано је да алгоритам
може бити имплементиран и у другим оптимизационим компајлерима уз адекватно при-
лагођавање конкретном окружењу.
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.