Wyciek rejestrów

Ten artykuł od 2010-09 wymaga zweryfikowania podanych informacji.
Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Wyciek rejestrów – proces przydzielania dużej liczby zmiennych danego programu do małej liczby rejestrów procesora.

Wprowadzenie

W wielu językach programowania, programista pracuje na abstrakcji alokując wiele zmiennych. Jednakże podczas kompilacji, kompilator musi zdecydować w jaki sposób rozmieścić te zmienne w małej liczbie rejestrów. Nie wszystkie zmienne są w użyciu w każdym momencie wykonania programu, więc niektóre rejestry mogą być przypisane do więcej niż jednej zmiennej. Jednak dwie zmienne używane w tym samym czasie nie mogą być przypisane do tego samego rejestru. Zmienne które nie mogą być zapisane w rejestrze muszą być przechowywane w pamięci RAM. Alokacja rejestrów może przebiegać podczas:

Algorytmy przydziału rejestrów

Problem przydziału rejestrów można sprowadzić do problemu kolorowania grafu, w którym wierzchołkami są zmienne. Są one połączone krawędzią jeśli w danej chwili t są jednocześnie w użyciu. Kolorami są natomiast numery rejestrów. Jeśli teraz pokolorować taki graf to można z niego odczytać do jakiego rejestrów dana zmienna powinna być przypisana. Ponieważ liczba rejestrów jest stała problem tak naprawdę można sprowadzić do problemu K-kolorowoania grafu[1].

Rozlewanie rejestrów (spilling)

Przerzucanie zmiennych do stosu z powodu przewagi liczby zmiennych do liczby rejestrów. Pojawia się on w programach napisanych w języku wysokiego poziomu.

Kompilatory przetwarzają kod źródłowy na kod maszynowy zrozumiały dla procesora. Współczesne kompilatory wykonują optymalizację kodu wynikowego, a głównym kryterium optymalizacji jest szybkość działania skompilowanego programu. Procesory szybciej wykonują operacje na wewnętrznych rejestrach procesora niż na zewnętrznej (dla CPU) pamięci. Dlatego istotne jest, aby zmienne używane w programie były przechowywane w rejestrach. Procesory dają do dyspozycji oprogramowania określoną liczbę rejestrów, a w wielu procesorach (w technologii CISC) jest jeden wyróżniony rejestr, w którym umieszcza się wyniki działań; pozostałe mają różne przeznaczenia. W wielu architekturach procesorów liczba rejestrów jest niewielka i mniejsza niż zmiennych lokalnych używanych w typowych programach, dlatego konieczne staje się przerzucanie zmiennych pomiędzy rejestrami a pamięcią na czas, gdy zmienne nie są chwilowo potrzebne.

Obecnie większość oprogramowania pisana jest w językach wysokiego poziomu, z użyciem bardzo dużej ilości danych, programista zazwyczaj nie ma wpływu na optymalizację użycia rejestrów. Zakłada się, że optymalizacja kodu dokonywana przez kompilator jest dobra, szybkość procesora i jego wewnętrzna architektura, szczególnie pamięć podręczna, rekompensują tę niepożądaną sytuację. Jednak zjawisko to jest nadal istotne tam, gdzie wydajność działania aplikacji jest najważniejszym kryterium – w systemach czasu rzeczywistego i wbudowanych, w których montuje się procesory o niewielkiej wydajności. Wówczas oprogramowanie często tworzone jest w asemblerze, a programista, który dobrze zna architekturę i sposób działania procesora, może tworzyć algorytmy tak, by zjawisko wycieku rejestrów minimalizować.

W związku z problemami związanymi z optymalizacją pracy procesorów postanowiono zmienić koncepcję działania mikroprocesora, konstruując je w technologii RISC (np. PowerPC). Procesory te mają dużą liczbę rejestrów, wyniki obliczeń można umieszczać w każdym z rejestrów, uproszczono tryby adresowania pamięci, rozkazy mają określony format (np. wielokrotność 2 lub 4 bajtów). Struktura taka ułatwia optymalizację kodu dokonywaną przez kompilator.

Zobacz też

Przypisy

  1. ↑ Alex Aiken: Register Allocation-Compilers. 2012-06-22. [dostęp 2014-06-20].