Umieszczam tu dwie strony jedna org i moje tlumaczenie ...czy ktos moglby sprawdzic czy dobrze to zrobilem bo mam watpliwosci a tekst nie jest latwy..A mam go o wiele wiecej do tlumaczenia:-(
Eliminating Dependent Computations
Compiler can reduce the impact of dependent computations so as achieve more ILP. The key technique is to eliminate or reduce a dependent computation by back substitution, which increases the amount of parallelism and sometimes increases the amount of computation required. These techniques can be applied both within a basic block and within loops, and we describe them differently. Within a basic block, algebraic simplifications of expressions and an optimization called “copy propagation”, which eliminates operations that copy values, can be used to simplify sequences like the fallowing:
RYS:
Assuming this is the only use of R1. In fact, the techniques we used to reduce multiple increments of array indices during loop unrolling and to move the increments across memory addresses in Section 4.1 are examples of this type of optimization.
In these examples, computations are actually eliminated, but it also possible that we may want to increase the parallelism of the code, possibly even increasing the number of operations. Such optimizations are called “tree height reduction”, since the reduce of height of the tree structure representing computation, making it wider but shorter. Consider the fallowing code sequence:
..
.
Notice that this sequence requires at least three execution cycles, since all the instructions depend on the immediate predecessor. By taking advantage of associativity, we can transform the code and rewrite it as:
….
This sequence can be computed in two execution cycles. When loop unrolling is used, opportunities of these types of optimizations occur frequently.
Although arithmetic with unlimited range and precision is associative, computer arithmetic is not associative, for either integer arithmetic, because of limited range, or floating-point arithmetic, because of both range and precision. Thus using these restructuring techniques can sometimes lead to erroneous behavior, although such occurrences are rare. For this reason, most compilers require that optimization that rely on associativity be explicitly enabled.
When loops are unrolled, this sort of algebraic optimization is important to reduce the impact of dependences arising from recurrences. “Recurrences” are expression whose value on one iteration is given by function that depends on the previous iterations. When a loop with a recurrence is unrolled, we may be able to algebraically optimize the unrolled loop, so that the recurrence need only be evaluated once per unrolled iteration. One common type of recurrence arises from an explicit program statement, such as:..
A teraz tlumaczenie ...:
Eliminacja zależ
ności obliczen?
Kompilator moż
e zredukowac wpływ zaleznych obliczen tak by osciagnac wiecej ILP.Kluczowa metoda jest to by wyeliminowac lub zredukowac zależ
ność obliczen poprzez wtorne podstawianie, ktore zwieksza ilość równoległości??? I czasami zwieksza liczbe wymaganych obliczen. Te techniki mogę być stosowane wewnatrz bazowego bloku i wewnatrz petli, opiszemy je inaczej.
Wewnątrz bazowego bloku , algebraiczne uproszczenie wyraż
enia i optymalizacja zwana „copy propagation” , która eliminuje operacje kopiowania wartości, moż
e być uzywana do
Upraszczania sekwencji jak następujące.:
DADDUI ……itd.
Zakładając ze jest tylko uzywana przez R1. W rzeczywistości techniki które uzywamy do zredukowania wielokrotności inkrementacji szeregu indeksow ?? podczas rozwijania petli i przenoszenia inkrementacji poprzez adresy pamieci w Sekcji 4.1 znajduja się przykłady tego typu optymalizacji.
W tych przykładach , obliczenia są juz wyeliminowane, ale takż
e moż
liwe jest ze będziemy chcieli zwiększyć równoległość kodu, moż
liwe ze nawet zwiększyć liczbe operacji.Tak optymalizacja zostala nazwana „Tree height reduction(redukcja wysokości drzew)”,odkad redukowala wzrost struktury drzewa reprezentującej obliczenia, tworząc je szerszymi ale krótszymi.Rozwazmy nastepujaca sekwencje kodu.
ADD…..
Zauważ
my ze ta sekwencja wymaga przynajmniej trzech wykonanych cykli , dopuki wszystkie instrukcje zalezą od najbliż
szego??? poprzednika. Poprzez korzystanie z „associativity”-asocjacji?, moż
emy zmienic kod i przerobic go tak :
ADD
Ta sekwencja moż
e być wyliczona w dwoch wykonawczych cyklach. Kiedy rozwijanie petli jest uzywane, moż
liwości dla tych rodzajow optymizacji pojawia się często.
Chociaz artmetyka z nieograniczonym zasiegiem i precyzja asocjacyjna, arytmetyka komputera nie jest asocjacyjna, dla każ
dej całkowitej liczby arytmetycznej , z powodu ograniczonego zasiegu, lub zmienno-przecinkowych punktow arytmetycznych??, z powodu obu zakresu i precyzji. Tak wiec, uzycie tych „restructuring” technik moż
e czasami prowadzic do blednych zachowan, chociaz takie wypadki SA rzadkie.
Z tego powodu , większość kompilatorow wymaga by optymizacja ta polegajaca na asocjacji była stanowczo uaktywniona.
Kiedy petle zostana rozwinięte, wazne jest by ten rodzaj algebraicznej optymizacji redukowal wpływ zależ
ności bedących wynikiem powtórzeń. „Recurrences” sa wyraż
eniem których wartość w jednej iteracji jest podawana przez funkcje w zależ
ności???? od wcześniejszej iteracji. Kiedy petla z rekurencją jest rozwinięta, moż
emy byc w stanie dokonac algebraicznej optymizacji rozwiniętej petli, wiec rekurencja wymaga tylko „oszacowania”??(evaluated) raz na rozwinieta iteracje.
Jeden wspolny typ rekurencji jest wynikiem „explicite program statement”??, such as: