Specjalizacja algorytmu czasu wykonywania

W informatyce specjalizacja algorytmów czasu wykonywania to metodologia tworzenia wydajnych algorytmów dla kosztownych zadań obliczeniowych pewnego rodzaju. Metodologia wywodzi się z dziedziny automatycznego dowodzenia twierdzeń , a dokładniej z projektu dowodzenia twierdzeń o wampirach .

Pomysł jest inspirowany wykorzystaniem częściowej oceny w optymalizacji tłumaczenia programów. Wiele podstawowych operacji w dowodach twierdzeń ma następujący wzór. $, że$ wykonać jakiś algorytm $sytuacji$ , dla różne wartości ${\ displaystyle B}$ . Aby zrobić to skutecznie, możemy spróbować znaleźć $\$$_ {A}}$${$ Displaystyle \ mathit ${\ Displaystyle {\ mathit {alg}} _ {A} (B)}$ jest równoznaczne z wykonaniem ${\ Displaystyle {\ mathit {alg}} (A, B )}$ .

Algorytm wyspecjalizowany może być bardziej wydajny niż algorytm ogólny, ponieważ może wykorzystywać pewne szczególne właściwości stałej wartości ${\ displaystyle A}$ . Zazwyczaj ${\ Displaystyle {\ mathit {alg}} _ {A} (B)}$ można uniknąć niektórych operacji, które $\ Displaystyle {\ mathit {alg}} (A,B)}$ musiałyby działać, jeśli wiadomo, że są zbędne dla tego konkretnego parametru ${\ Displaystyle A}$ . W szczególności często możemy zidentyfikować niektóre testy, które są prawdziwe lub fałszywe dla rozwijania pętli i rekurencji itp. ${\ displaystyle A}$

Różnica w stosunku do oceny częściowej

$alg}}}$ polega na tym, że wartości, na których specjalizuje $się,$ nie są znane statycznie, więc specjalizacja ma miejsce za w czasie wykonywania .

Istnieje również istotna różnica techniczna. Częściowa ocena jest stosowana do algorytmów jawnie reprezentowanych jako kody w niektórych językach programowania. W czasie wykonywania nie potrzebujemy żadnej konkretnej reprezentacji za $displaystyle {\ mathit {alg}}}$ \ Musimy tylko $.$ sobie programujemy procedurę specjalizacji Wszystko, czego potrzebujemy, to konkretna reprezentacja specjalistycznej wersji ${\ Displaystyle {\ mathit {alg}} _ {A}}$ . Oznacza to również, że nie możemy stosować żadnych uniwersalnych metod specjalizacji algorytmów, jak to zwykle ma miejsce w przypadku oceny cząstkowej. Zamiast tego musimy zaprogramować procedurę specjalizacji dla każdego konkretnego algorytmu ${\ displaystyle {\ mathit {alg}}}$ . Ważną zaletą takiego postępowania jest to, że możemy użyć kilku potężnych ad hoc wykorzystujących osobliwości ${\ displaystyle$ reprezentację $}$ i $B}$ , które są poza zasięgiem jakichkolwiek uniwersalnych metod specjalizacyjnych.

Specjalizacja z kompilacją

Wyspecjalizowany algorytm musi być przedstawiony w postaci, która może być interpretowana. $obliczona$$wielu$ , zwykle gdy wielu wartościach rzędu zapisz $jest$ specjalnej maszyny abstrakcyjnej i często mówimy, że kompilowany ZA $A}$ . Wtedy sam kod można dodatkowo zoptymalizować poprzez transformacje zachowujące odpowiedzi, które opierają się wyłącznie na semantyce instrukcji maszyny abstrakcyjnej.

Instrukcje maszyny abstrakcyjnej można zwykle przedstawić jako rekordy. Jedno pole takiego rekordu zawiera znacznik typu integer, który identyfikuje typ instrukcji, inne pola mogą służyć do przechowywania dodatkowych parametrów instrukcji, np. wskaźnika do innej instrukcji reprezentującej etykietę, jeśli semantyka instrukcji wymaga skoku. Wszystkie instrukcje kodu mogą być przechowywane w tablicy, liście lub drzewie.

Interpretacja odbywa się poprzez pobieranie instrukcji w określonej kolejności, identyfikowanie ich typu i wykonywanie akcji związanych z tym typem. W C lub C++ możemy użyć instrukcji switch , aby powiązać niektóre akcje z różnymi znacznikami instrukcji. Współczesne kompilatory zwykle dość wydajnie kompilują switch z etykietami liczb całkowitych z wąskiego zakresu, przechowując adres instrukcji odpowiadający wartości $displaystyle$ ja $i}$ -ta komórka specjalnej tablicy. Można to wykorzystać, biorąc wartości dla znaczników instrukcji z małego przedziału liczb całkowitych.

Specjalizacja dane i algorytmy

Istnieją sytuacje, w których wiele wystąpień ${\ Displaystyle {\ mathit {alg}} (A, B$ przeznaczonych do długoterminowego przechowywania, a wywołania występują z $}$ różne w $nieprzewidywalnej$ . Na przykład być może będziemy musieli najpierw sprawdzić, a następnie za $\ Displaystyle {\ mathit {alg}} (A_ {1}, B_ {1})$${\ Displaystyle {\ mathit {alg}} (A_ {2}, B_ {2})}$ , a następnie ${\ Displaystyle {\ mathit { alg}}(A_{1},B_{3})}$ i tak dalej. W takich okolicznościach pełna specjalizacja z kompilacją może nie być odpowiednia ze względu na nadmierne wykorzystanie pamięci. Jednak czasami możemy znaleźć zwartą wyspecjalizowaną reprezentację dla każdego $pierwsza}}$${\ displaystyle A}$ , które mogą być przechowywane z lub zamiast. ${\ displaystyle A}$ . Definiujemy również wariant $\$$mathit {$ , jest zastępowane przez ${\ Displaystyle {\ mathit {alg}} ^ {\ pierwsza} (A ^ {\ pierwsza}, B)}$ , przeznaczone do szybszego wykonywania tej samej pracy.

Zobacz też

• Psyco , wyspecjalizowany kompilator czasu wykonywania dla Pythona
• programowanie wieloetapowe

• A. Voronkov, „The Anatomy of Vampire: Implementing Bottom-Up Procedures with Code Trees”, Journal of Automated Reasoning , 15(2), 1995 ( oryginalny pomysł )

Dalsza lektura

• A. Riazanov i A. Voronkov, „Efficient Checking of Term Ordering Constraints”, Proc. IJCAR 2004, Lecture Notes in Artificial Intelligence 3097, 2004 ( zwarta, ale samodzielna ilustracja metody )
• A. Riazanov i A. Voronkov, Efficient Instance Retrieval with Standard and Relational Path Indexing , Information and Computation, 199(1-2), 2005 ( zawiera kolejną ilustrację metody )
• A. Riazanov, „Implementing an Efficient Theorem Prover” , rozprawa doktorska, The University of Manchester, 2003 ( zawiera najobszerniejszy opis metody i wiele przykładów )