Perforacja pętli przyśpiesza programy
Komputery powstały po to, by dać odpowiedzi na trudne logiczne pytania. I przez dziesięciolecia służyły właśnie temu celowi - precyzyjnemu rozwiązywaniu zadań. W ostatnim czasie sytuacja się jednak zmienia i coraz częściej jesteśmy skłonni poświęcić precyzję na rzecz prędkości.
Przykładem niech będzie sposób działania wyszukiwarek. Rezultaty uzyskane z Google'a czy Yahoo! nie są najbardziej precyzyjne z możliwych, jednak internauci wolą szybko uzyskać nieco mniej dokładną odpowiedź, niż dłużej czekać na najlepszą z możliwych. Stąd też np. dokładna kolejność pierwszych kilku czy kilkunastu wyników wyszukiwania nie jest ważna.
Grupa badaczy z MIT-u pracująca pod kierunkiem profesora Martina Rinarda postanowiła wykorzystać takie podejście i stworzyła system automatycznie wyszukujący w kodzie komputerowym miejsc, w których nieco dokładności może zostać poświęconej na rzecz znacznego przyspieszenia pracy programu.
Udało im się osiągnąć zadziwiające rezultaty. Podczas testów skrócili o połowę czas potrzebny do zakodowania transmisji wideo w celu przesłania jej przez sieć. Jakość obrazu pozostała przy tym niezmieniona. Takie samo podejście może zostać wykorzystane wszędzie tam, gdzie konieczne jest przetwarzanie danych w czasie rzeczywistym, a więc np. w oprogramowaniu do analiz giełdowych czy systemach śledzenia i monitorowania wykorzystujących sieci czujników.
Opracowany przez zespół Rinarda system może działać dwojako. Potrafi wskazać programiście te miejsca kodu, w których możliwe jest poświęcenie precyzji na rzecz prędkości. Jest też w stanie samodzielnie dokonać odpowiednich zmian. Przykładem takiego zastosowania niech będzie wideokonferencja przeprowadzana z użyciem laptopa. Gdy program do konferencji jest jedynym uruchomionym na maszynie, kodowanie sygnału wideo może odbywać się tradycyjnymi metodami. Jeśli jednak komputer wykonuje jednocześnie inne zadania, mógłby automatycznie przełączać kodowanie w tryb wymagający zużycia mniej mocy procesora.
Uczeni z MIT-u wykorzystali bardzo prosty trick. Rozbudowane programy komputerowe wykorzystują liczne pętle, czyli wielokrotnie powtarzane procesy. Rinard oraz współpracujący z nim naukowcy Stelios Sidiroglou-Douskos, Hank Hoffman i Sasa Misailovic nazwali swoją technikę "perforacją pętli". Polega ona na "wybijaniu dziur" w pętlach, co po prostu polega na pomijaniu pewnych kroków w pętli. System automatycznie ocenia, ile takich kroków można pominąć by znacząco przyspieszyć pracę programu, a jednocześnie nie poświęcić zbyt wiele z precyzji jego działania.
Sam system opracowany przez grupę Rinarda jest pętlą - przeszukuje on program, "wybija" w nim dziury, a następnie uruchamia program i wylicza, jak jego działanie wpłynęło na wydajność programu. Następnie oceniane jet, która z "perforacji" najlepiej wpływa na zwiększenie wydajności, a jednocześnie oznacza najmniejsze straty w precyzji.
Pomysł uczonych z MIT-u jest niezwykle prosty, a jednocześnie zapewnia olbrzymi wzrost wydajności. Jednocześnie jest sprzeczny z intuicją programistów, którzy starają się udoskonalać swój kod, a teraz słyszą, że mogą część swojej pracy wyrzucić do kosza, a jednocześnie nie poświęcą zbyt dużo z precyzji działania programu.
Komentarze (14)
kocurxtr, 14 maja 2010, 20:55
niebezpieczna zabawa. w odpowiedzialnym sofcie, np. medycznym może to narobić sporo problemów; absolutnie nie do zastosowania w poważnych projektach. co z tego, że mi szybciej policzy dynamikę przepływu krwi w modelowanej sztuczej komorze serca, jeżeli zrobi to z błędem? to już wolę, by mi ansys liczył 3 dni ale poprawnie.... pomysł ciekawy, ale... prowadzi do bylejakości wyników na których niw można polegać. wyłącznie do zabawy.
wilk, 14 maja 2010, 21:13
Pomysł dość niecodzienny, choć zrozumiały w przypadku transmisji A/V, gdzie i tak dokonywana jest stratna kompresja. Aczkolwiek co do poniższego przykładu byłbym ostrożny:
Coś takiego może doprowadzić do narastających błędów. Kompletnie odpada też w obliczeniach matematycznych.
thikim, 15 maja 2010, 08:40
Nie zgodzę się. Tak by było gdybyśmy zakładali że system medyczny jest bezbłędny. Niestety elementem systemu medycznego są ludzie, przykładowo lekarze, mylący się bardzo często. Na wynik leczenia ma dużo większy wpływ błąd lekarza, dużo osób ginie przez błąd lekarza. Tak więc wprowadzenie drobnych niedokładności w sofcie nic nie zmieni. To będzie jak dodanie do załóżmy 10 % błędów ludzkich 0,01 % błędu maszyny. Pomijalne. A o takie błędy w stosunku do całości tu chodzi.
Absolutnie nie odpada. Sieci neuronowe, logika rozmyta, rachunek zaburzony. To są przecież już od wielu lat rozwijane dziedziny matematyki i informatyki gdzie właśnie wprowadza się celowo pewną niedokładność.
Dlatego dziwi mnie trochę że tak późno tym się zajęto jeśli zajmowano się tym już od 20 lat. W sumie wspomnieli google, te systemy działają już od dawna. Różnica jest taka że stworzono system do wyszukiwania i automatycznego korygowania innych systemów.
To jest właśnie to nowatorstwo a nie poświęcanie dokładności na rzecz szybkości co robi się już od wielu lat.
wilk, 15 maja 2010, 12:07
OK, tylko, że to się wprowadza z poziomu algorytmu/formuły matematycznej, która przewiduje te (zaplanowane) czynniki niepewności, a nie poprzez psucie już gotowego modelu obliczeń. Aczkolwiek pomysł ciekawy, wart śledzenia jego rozwoju.
Gość shadowmajk, 15 maja 2010, 12:55
Hmm... a ja czasem łowię ryby
kocurxtr, 15 maja 2010, 13:30
często w wyniku źle postawionej diagnozy - uzyskanej np. na skutek obrazów z rezonansu magnetycznego... chciałbyś być źle zdiagnozowany ? ale zostawmy konowałów w spokoju gdyż...
... ja mówiłem o innym zagadnieniu - o konkretnym przykładzie - załóżmy że z błędnych oblizeń wynika, że skrzydełko sztucznej zastawki może mieć grubość 0.2mm (zamiast 0.4) i ... nie wytrzymuje ciśnienia; zastawka ulega zniszczeniu, pacjent umiera. czy dla ciebie taki błąd jest pomijalny/dopuszczalny ? a gdybyś to Ty wylądował na stole i miał dostać sztuczną zastawkę/komorę ? chciałbyć mieć świadomość że soft użyty do zaprojektowania dopuszcza błędy obliczeniowe ? to są poważne zastosowania o których mówiłem. błędy lekarskie nie mają nic do tego i nie są przdmiotem tej dyskusji. przedmiotem jest świadome dopuszczenie do powstania niedokładnych obliczeń - i to że są obszary w których jest to niedopuszczalne. pozdro.
kocurxtr, 15 maja 2010, 13:32
ja też. można w spokoju podumać i odpocząć od zawiłości tego świata
shaker, 15 maja 2010, 20:36
Szkoda, że nie ma podanych szczegółów działania algorytmu.
Na pierwszy rzut oka nie wygląda to na nic rewolucyjnego, po prostu kolejny algorytm, który ma za zadanie optymalizować kod.
Trzeba zdać sobie sprawę z tego, że obecnie programiści nie zawsze piszą optymalny kod, zdając się na optymalizację wykonywaną przez kompilatory.
Przeglądając różne kody, można zauważyć wiele sytuacji, w których pewne operacje mogą być realizowane przed pętlą. Dobrym przykładem jest deklarowanie zmiennych wewnątrz pętli zamiast jednorazowej deklaracji i nadpisywania wartości w każdej iteracji. Warto też zauważyć, że w niektórych przypadkach takie działanie jest pożądane - głównie w celu zwiększenia czytelności kodu.
Możliwe, że naukowcy opracowali algorytm wykrywania tych operacji, które mogą być bez problemu realizowane przed pętlą. Drugą rzeczą, jaka przychodzi mi na myśl jest zmniejszenie ilości bitów przeznaczonych na reprezentację danych w przypadku zmiennych, które nie są używane w celu osiągnięcia wyniku, czyli tego, co jest przekazywane gdzieś dalej lub wyświetlane użytkownikowi.
Nie wiecie czy można gdzieś zapoznać się z tą pracą?
KONTO USUNIĘTE, 16 maja 2010, 14:19
kocurxtr,wilk
zespół Rinarda świadom ograniczeń swojego triku od razu zaznaczył gdzie go można zastosować:transmisja wideo,bieżąca analiza giełdy,itp. Ale faktycznie,monitorowanie sieci czujników to za odważne stwierdzenie,bo czujniki są w różnych,mniej lub bardziej ważnych miejscach
A dlatego ,bo gdzieś było doświadczenie o ludzkich gazach jelitowych,które czujnik wykrywał.
thikim, 16 maja 2010, 15:26
Gdzieś też były wyniki diagnostyki chorób przez lekarzy i program. Program wygrywał...
Czy jak badanie prowadzi lekarz to jego błąd przestaje być krytyczny?
Dziwi mnie że program żeby być akcpetowanym musi mieć błąd <0,00001 %
podczas gdy lekarz stawiający tę samą i w tej samej sytuacji diagnozę może mieć błąd na poziomie 50 % i wszystko jest ok.
Moją siostrę leczyło 4 różnych lekarzy. 3 diagnozy były nieprawidłowe, omal nie doprowadziły ją poprzez złe leczenie do śmierci. Jaka był błąd stawiania diagnozy? 75 % I wiecie co? Wszystko było w porządku, a jak moja mama wyprosiła wreszcie zgodę na wyjazd siostry do USA na leczenie to jeszcze ją objechał jeden polski ordynator szpitala że pacjenta zabiera.
KONTO USUNIĘTE, 16 maja 2010, 16:04
Bo lobby lekarskie rządzi.W lotnictwie zresztą też jest podobnie.10.04 w Smoleńsku, komputer by nie lądował.
kocurxtr, 16 maja 2010, 20:22
w46, 17 maja 2010, 13:13
Co do dokładności obliczeniowej są sytuacje/algorytmy w których utrata dokładności nie spowoduje katastrofy są też takie dla których dane są nieliniowe do tego stopnia że niedokładność rzędu ułamka procenta może nie mieć żadnego wpływu na wynik ale może też spowodować gigantyczne różnice od rzeczywistego.
Tej sytuacji bym nie mieszał szczególnie że nie wiemy co tak naprawdę się stało ... i pewnie nigdy się już nie dowiemy.
pio, 17 maja 2010, 20:47
gwoli scislosci.. predkosc jest przypisana raczej do obiektow materialnych. w tym przypadku chodzi o szybkosc (dzialania).