Strona główna

A white paper 9 Grudzień 2008


Pobieranie 52.66 Kb.
Data19.06.2016
Rozmiar52.66 Kb.
AQUA@home
A white paper

9 Grudzień 2008

Dr. Geordie Rose

Fundator i Chief Technology Officer

D-Wave Systems Inc.

rose@dwavesys.com






D-Wave opracowuje system przetwarzania danych wysokiej wydajności nowej klasy, by rozwiązywać skomplikowane problemy optymalizacji, z naciskiem na aplikacje uczenia maszynowego.


Systemy D-Wave bazują na innowacyjnym procesorze który używa modelu obliczeniowego znanego jako Adiabatyczne Przetwarzanie Kwantowe (AQC). Procesory te wykorzystują efekty kwantowe by rozwiązywać problemy optymalizacji w nowy sposób. Procesory te są wykonane z użyciem metali nadprzewodzących zamiast półprzewodników i pracują w ultra niskich temperaturach w próżni magnetycznej.

www.dwavesys.com




WPROWADZENIE
Algorytm to seria kroków służąca do rozwiązania problemu. 1 Przykład jest podany na wpisie w wikipedii o algorytmach, gdzie problemem do rozwiązania jest naprawa uszkodzonej lampy (zobacz rys1). W tym przypadku podążamy sekwencją kroków, z taktyką rozwiązywania problemu opisaną w każdym kroku przedstawionym na schemacie.
Zazwyczaj można w prosty sposób sprawdzić jak dobrze działa zaproponowany algorytm. Jednym ze sposobów jest policzenie kroków potrzebnych do rozwiązania problemu danego typu.
Jedne algorytmy są lepsze od innych. W przykładzie z lampą, całkowicie poprawny algorytm mógłby wymagać podróży na Syberię, pomiędzy sprawdzeniem czy lampa jest podłączona, a sprawdzeniem czy żarówka jest spalona. Dodanie opóźnienia związanego z podróżą na Syberię nie ma wpływu na wynik algorytmu, lampa zostanie naprawiona. Ten zmodyfikowany algorytm naprawy lampy wciąż byłby postrzegany jako mniej sprawny od oryginału.
Czasami nowo odkryty algorytm jest w oczywisty sposób sprawniejszy od wszystkich poprzednich. Gdy tak jest, stosowane dotychczas podejścia są często porzucane i wszyscy którzy borykają się z podobnymi problemami do rozwiązania mogą osiągnąć natychmiastowy i czasem spektakularny przyrost wydajności. 2 W scenariuszu z lampą, wyobraźmy sobie że wszyscy używają wersji algorytmu z podróżą na Syberię, dopóki jakiś genialny naukowiec komputerowy nie wykaże że można ominąć ten krok i wciąż skutecznie naprawić lampę. Większość natychmiast przerzuciłaby się na lepszy algorytm.
Czasem jest bardzo trudno powiedzieć czy dany algorytm może zostać ulepszony. Prze ostatnie dwa dziesięciolecia, dokonano wielkiego postępu w rozumieniu jednego typu ograniczeń skuteczności algorytmów. Okazuje się że prawa fizyki wytyczają granice skuteczności rozwiązywania problemów.

Tak jak fizyka wytycza granice szybkości podróży (prędkość światła), wyznacza ona fundamentalne ograniczenia co do tego jakie jest minimum kroków (lub bitów pamięci) wymaganych do rozwiązania danego problemu. Te ograniczenia są niezależne od inteligencji programisty lub dostępnego sprzętu.


Zasadniczo, powodem tego że prawa fizyki mają znaczenie dla przetwarzania danych jest to że komputery są budowane z materiałów, które oczywiście podlegają prawom fizyki. Informacja która jest przechowywana i przetwarzana w komputerze, również podlega tym regułom, i dlatego podlega wszystkim ograniczeniom wynikającym z tych reguł.
Rysunek 1. Z wpisu na wikipedii o algorytmach. Ten konkretny algorytm został zaprojektowany by z zepsutej lampy uzyskać działającą lampę.

____________________________

1 Interesujący artykuł o algorytmach: http://www.crmbuyer.com/story/33488.html

2 Słynny przykład obejmuje algorytmy dla faktoringu; zobacz



http://dwave.wordpress.com/2007/08/27/algorithms-vs-hardware-the-throwdown/ dla porównania.


INFORMACJA KWANTOWA I ALGORYTMY
Postęp w rozumieniu relacji pomiędzy fizyką i naukami komputerowymi, doprowadziła do stworzenia nowej kategorii naukowych badań, gdzie studiowane są ostateczne granice przetwarzania. Ta kategoria nazywa się nauką o informacji kwantowej. Gruntownym założeniem jest to, że prawa fizyki, nie koniecznie związanymi z dzisiejszymi procesorami i zestawami przetwarzającymi, ustalają ostateczne granice sprawności algorytmów. Trzydzieści lat temu ta gałąź nauki nie istniała. Dziś mielibyśmy problem ze znalezieniem choćby jednego uniwersytetu który nie posiadałby wydziału zajmującego się fascynującymi problemami w tej dziedzinie.
Jednym z najbardziej prowokacyjnych odkryć dokonanych w toku tych badań jest to, że istnieją algorytmy możliwe z punktu widzenia natury, lecz nie umiemy ich uruchomić na komputerach dostępnych dziś. 3 Te kwantowe algorytmy wymagają operacji możliwych w mechanice kwantowej lecz nie w fizyce klasycznej. 4 Uruchomienie ich wymaga specjalistycznego sprzętu (zwykle komputerów kwantowych) zaprojektowanych z myślą o wykonywaniu operacji kwantowych wymaganych przez algorytmy kwantowe. Niektóre z tych algorytmów są znacznie lepsze niż najlepsze znane algorytmy klasyczne. Niektóre z nich będą miały ogromne znaczenie dla problemów które będą rozwiązywać.
Dobrze znanym przykładem jest algorytm Shor'a, który jest algorytmem kwantowym dla faktoringu. 5 Faktoring jest ciężkim problemem używanym jako podstawa dla pewnych kryptosystemów, zdolnych do wyliczenia dużej ilości liczb pierwszych, które szybko pozwolą łamać pewne powszechnie używane kody. Algorytm Shor'a znacznie redukuje liczbę kroków wymaganych do takiego działania. Jesli współczesny komputer mógł uruchomić algorytm Shor'a, mógłby złamać kod, chroniący twój zakup online przy pomocy karty kredytowej, w około sekundę, podczas gdy używając najlepszego znanego klasycznego algorytmu faktoringowego, to samo zadanie zajęłoby największemu na świecie superkomputerowi więcej niż dzień. 6
ADIABATYCZNE ALGORYTMY KWANTOWE
Jedną z ważnych dziedzin algorytmów kwantowych są adiabatyczne algorytmy kwantowe. 7 Pierwotnie odkryte w 2000 roku przez grupę naukowców na MIT (Massachussets Institute of Technology). Te algorytmy rozwiązują ważną pulę ciężkich problemów obliczeniowych w nowatorski sposób. 8 Algorytmy te wywołały wielkie kontrowersje w środowiskach naukowców z dziedziny fizyki i nauk komputerowych, ponieważ nie ma prostego sposobu analizy, czasu rozwiązywania problemu do którego zostały zaprojektowane.

________________________

3 Zoo algorytmów kwantowych http://www.its.caltech.edu/~sjordan/zoo.html lista wszystkich znanych algorytmów tego typu.

4 Mechanika kwantowa w zarysie na podstawie którego zbudowane jest całe współczesne rozumienie materii i energii.



http://en.wikipedia.org/wiki/Quantum_physics posiada referencje do dobrych instrukcji na temat mechaniki kwantowej.

5 http://en.wikipedia.org/wiki/Shor%27s_algorithm

6 http://en.wikipedia.org/wiki/Key_size

7 Sprzęt wymagany do uruchomienia tych algorytmów jest zazwyczaj nazywany Adiabatycznym Komputerem Kwantowym, zobacz przykład http://arxiv.org/abs/quant-ph/0211152

8 http://www.sciencemag.org/cgi/content/abstract/292/5516/472

Pewni naukowcy teoretycy z zakresu nauk komputerowych wierzą że te algorytmy nie dadzą spodziewanych przyrostów wydajności, podczas gdy wielu naukowców, studiujących te zagadnienia rozwiązywania problemów, wierzy że mogą dać gwałtowną redukcję czasu potrzebnego na rozwiązanie pewnych problemów, w stosunku do najlepszych znanych algorytmów klasycznych. 9


Odpowiedź na pytanie, jak długo zajmie adiabatycznemu algorytmowi kwantowemu znalezienie rozwiązania problemu, jest bardzo ważnym zagadnieniem naukowym powiązanym z niektórymi z największych otwartych problemów nauk komputerowych. Oprócz tego że jest to ważny problem akademicki, ma to również wyjątkową wagę praktyczną dla starań w firmie D-Wave, która skupia się na stworzeniu sprzętu do uruchamiania tych algorytmów. 10
UŻYCIE METOD QUANTUM MONTE CARLO DO OBLICZANIA CZASU PRZETWARZANIA
Ostatnimi czasy została opracowana technika służąca do obliczania czasów których potrzebują Adiabatyczne Algorytmy Kwantowe do rozwiązania relatywnie małych problemów, poprzez symulację komputera kwantowego przetwarzającego te algorytmy.
Podczas gdy to podejście, niestety nie da nam odpowiedzi na pytanie, jak te algorytmy dadzą sobie radę z dużymi problemami, jest ono wystarczające do przewidywania oczekiwanej wydajności adiabatycznych komputerów kwantowych do wielkości 128 qubitów.
To podejście symulacyjne jest oparte na technice zwanej Quantum Monte Carlo (QMC). Podejście to jest "żenująco" równoległe i może efektywnie wykorzystywać dużą liczbę niezależnych procesorów.
D-Wave oraz Dr. Peter Young 11 ( współautor dokumentu QMC do którego odnosiliśmy się wcześniej, oraz profesor na UCSC), zbudowali rozproszoną platformę QMC do obliczania czasu przetwarzania adiabatycznego algorytmu kwantowego który będzie uruchomiony na eksperymentalnym sprzęcie w D-Wave. Projekt nazywa się AQUA (Adiabatyczne Algorytmy Kwantowe), Z wersją rozproszoną nazywaną Aqua@home.
Technologia przetwarzania rozproszonego jest oparta na platformie BOINC, Ta sama technologia która wspiera SETI@home oraz inne wielkoskalowe naukowe obliczenia rozproszone. 12 AQUA@Home daziała na serwerze http://aqua.dwavesys.com/ który został skonfigurowany tak by przyjmować wyniki obliczeń ochotników którzy chcą zasilić zasoby przetwarzania projektu.

___________________________________

9 Jedną z organizacji wiodących na świecie w badaniu tego problemu jest MIT; zobacz http://www.rle.mit.edu/xqit/research_01.htm

10 http://arxiv.org/abs/0803.3971

11 http://physics.ucsc.edu/~peter/

12 http://boinc.berkeley.edu/




SYMULOWANY SPRZĘT
Procesory symulowane w projekcie AQUA@home są aktualnie budowane w D-Wave i mają nazwę kodową Rainier. Są formowane przy użyciu technologii litogrfii obwodów metalowych. Użytym metalem jest Niob, który staje się nadprzewodnikiem w bardzo niskich temperaturach. Nadprzewodniki mają wiele egzotycznych właściwości które czynią z je szczególnie przydatnymi w pewnych typach projektów procesorów wysokiej wydajności. Szczegółowy przegląd technologii procesorów nadprzewodzących można znaleźć w tym odnośniku. 13


Procesor symulowany zawiera 128 Qubitów. To sprawia, że jest wystarczająco mały by móc być studiowanym przy użyciu techniki QMC w AQUA@home. Szczegółowe opisy Systemu i procesora można znaleźć na http://dwave.wordpress.com.


Rysunek 2. 128Qubitowy procesor używany w D-Wave/ Google Supercomputing 2007 demonstracja porównywania obrazów.


PROBLEM ROZWIĄZYWANY PRZEZ ADIABATYCZNY ALGORYTM KWANTOWY
Procesor Rainier został specjalnie zaprojektowany to rozwiązania szczególnie trudnego problemu zwanego Kwadratową Optymalizacją Binarną Bez Ograniczeń, lub QUBO.14 Rozwiązanie problemu QUBO wymaga znalezienia zestawu N binarnych zmiennych {xi} które minimalizują funkvję obektową równania.

Gdzie Q jest wyrażoną w wartościach rzeczywistych górną triangularną macierzą. Każda konkretna macierz Q jest nazywana instancją problemu. Generalnie macierz Q powstaje w wyniku działania aplikacji wymagającej rozwiązania QUBO. Przykładem takiej aplikacji jest uczenie maszynowe, na którym skupia się drużyna programistów D-Wave. 15


________________________________

13 http://www.nitrd.gov/pubs/nsa/sta.pdf

14 http://www.springerlink.com/content/n4372840250660v3/

15 http://arxiv.org/abs/0811.0416


CO LICZY AQUA@home?
AQUA@home oblicza czas przebiegu zestawu instancji problemu typu, który został podany wcześniej, dla problemów o rozmiarach od 8 do 128 zmiennych. Generujemy 50 instancji problemu dla każdego z następujących rozmiarów: 8, 16, 32, 48, 72, 96, 128 zmiennych, co daje 350 instancji problemu. Używamy AQUA@home do obliczenia czasu rozwiązania dla każdej instancji. To jest zamierzony efekt obliczeń.
Ta informacja może zostać użyta do dwóch istotnych celów. Po pierwsze, mówi nam jak szybko symulowany sprzęt może pracować i wciąż rozwiązywać problem. Po drugie, mówi nam jak czasy przebiegu zmieniają się wraz ze wzrostem rozmiaru problemu. Wiedząc jak zmienia się rozmiar problemu, daje nam ważną informację co do tego czy problem jest dobrze dostosowany do podejścia adiabatycznego. Na przykład gdy czasy przebiegi gwałtownie rosną wraz ze wzrostem rozmiaru problemu, mówi to nam, że badane instancje problemu nie pasują dobrze do sprzętu.
CO SIĘ STANIE Z DANYMI WYGENEROWANYMI PRZEZ AQUA@home?
Dane będące wynikiem AQUA@home zostaną upublicznione w formie wykresu mediany czasów przebiegu w odniesieniu do rozmiaru problemu dla wszystkich typów sprzętu. Algorytmy kwantowe i klasy instancii problemów zostaną przetwarzane przez AQUA@home zostaną udostępnione. Ponadto opublikujemy pełne opisy nauki dotyczącej obliczeń w dokumentach naukowych na serwerze preprint arxiv.org, i te spośród rezultatów które są pewne zostaną przekazane do przeglądu w wiodących czasopismach naukowych, takich jak Physical Review Letters.
GDZIE MOGĘ SIĘ DOWIEDZIEC O D-WAVE I NAUCE AQUA@home?
zegląd nauki stojącej za AQAU@home:

http://arxiv.org/abs/0803.3971

Wprowadzenie do Adiabatycznych Algorytmów Kwantowych:



http://arxiv.org/abs/quant-ph/0104129

Wprowadzenie do Nadprzewodzących Adiabatycznych Kwantowych Komputerów:



http://arxiv.org/abs/quant-ph/0403090

Informacje o D-Wave:



http://dwave.wordpress.com/



©snauka.pl 2016
wyślij wiadomość