 Komputery kantowe
„Liczba tranzystorów w układzie scalonym (procesorze) zwiększa się w kolejnych latach zgodnie z trendem wykładniczym – podwaja się w dwunastomiesięcznych okresach.” Tak mówi Prawo Moore’a. Czytelnicy jednak wielokrotnie pisali, że „co to za prawo, które przestało się sprawdzać”.
Ograniczenia współczesnej technologii
Chcąc zrozumieć problem rozwoju procesorów i nagłego zatrzymania wzrostu mocy obliczeniowej, trzeba uświadomić sobie, że „Prawo Moore’a” wynika z obserwacji, jest prawem empirycznym, a nie uniwersalnym. Gordon Moore, jeden z założycieli Intela, w 1965 roku zauważył tą prawidłowość, która utrzymywała się przez kolejne dziesiątki lat. Z czasem jednak okresy, w których moc podwajała się wydłużyły się do 24 miesięcy. Dzięki czemu taki szybki rozwój był w ogóle możliwy? Jednym z głównych powodów jest stosowanie coraz mniejszych elementów w procesie produkcyjnym procesorów. W latach 90-tych używano technologii o litografii 500 nanometrów, podczas gdy współcześnie przeważają technologie 45 nm, 32 nm (Sandy Bridge), 22 nm (Haswell) i już wkrótce 14 nm (Broadwell).
Trzeba jednak zdawać sobie sprawę, że rozmiary te nie mogą zmniejszać się bez końca z uwagi na twarde ograniczenia fizyki klasycznej. Wartością graniczną będzie oczywiście rozmiar atomów (dla przykładu – atom krzemu ma średnicę 0,24 nm), a przejście z krzemu na grafen czy german również nie pozwoli na minimalizowanie litografii w nieskończoność – nawet w przypadku, gdyby pojedyncza ścieżka procesora miała grubość jednego atomu. Kolejnym ograniczeniem jest też prędkość światła, która wraz z fizycznymi rozmiarami płytki warunkuje maksymalną możliwą szybkość przesyłania informacji.
Od wielu lat zapowiada się, że Prawo Moore’a przestanie (przestało?) obowiązywać. Sam Gordon Moore, w roku 2006 powiedział, że za kilka lat jego „prawo” nie będzie miało zastosowania właśnie z uwagi na ograniczenia fizyki klasycznej. Producenci pokonują jednak kolejne granice i już teraz wiemy, że w 2016-2017 najprawdopodobniej uda się zejść poniżej 10 nm. Nie rozwiązuje to jednak problemu, a jedynie go odracza. Wkrótce i tak napotkamy ścianę limitów fizycznych i co wtedy? Możliwości producentów nie kończą się tak szybko. Pozostaje jeszcze optymalizacja programowa i zmiana architektury. Nie zmienia to „czystej” mocy obliczeniowej, ale pomaga oszukać ograniczenia i zwiększyć realną wydajność w praktycznych zastosowaniach. Dodawanie kolejnych rdzeni pomaga, ale też nie jest optymalnym rozwiązaniem – nie wszystkie procesy i zadania da się zrównoleglać (na poziomie bitów, rozkazów, danych i zadań), a całą wojnę na rdzenie czasami można ironicznie sprowadzić do pytania: „Wolałbyś osiem Fiatów czy jednego Bentleya?”.
Problematyczne jest też zjawisko wycieku (prąd upływu, „leakage”), które wzmaga się wraz z wzrostem częstotliwości procesora. Jest to niepożądany efekt kwantowy, polegający na tunelowaniu elektronów przez warstwę izolatora. Duże prądy upływu zwiększają pobór energii i mogą doprowadzić nawet do całkowitego uszkodzenia układu. Zjawisko wycieku jest obecnie jednym z głównych czynników limitujących maksymalne częstotliwości pracy procesorów. Na chwilę obecna wygląda na to, że nawet jeśli zmienimy architekturę i będziemy używać innych materiałów, problemu tego nie przeskoczymy.
Zacznijmy od optymalizacji programowej czyli software’u. Dopracowanie wykonywania rozkazów, zrównoleglania i sterowników może przełożyć się na wzrost odczuwalnej mocy obliczeniowej. Doskonałym przykładem zastosowania tych rozwiązań jest architektura Haswell, która opiera się na tym samym procesie litograficznym (22 nm) co poprzednia generacja Ivy Bridge. Mimo tej samej wielkości ścieżek, udało się podwyższyć moc obliczeniową o 10-20% redukując przy tym pobór prądu o 30-40%. Jednym z trików było zbalansowanie obciążenia CPU i układanie rozkazów w grupy odpalane synchronicznie w równych odstępach czasu, w opozycji do asynchronicznego wykonywania rozkazów niezależnie, po otrzymaniu sygnałów z wybranych peryferiów. Do tego jednak nie wystarczy technologia procesora – potrzebny będzie kompatybilny system operacyjny. Intel pracował blisko z Microsoftem i Apple, żeby ich OS-y w pełni wykorzystywały możliwości CPU i GPU w sposób optymalny. W przyszłości pojawią się kolejne rozwiązania związane między innymi z Panel Self Refresh, czyli odświeżaniem obrazu monitora. Firmy pracują nad tym, żeby w sytuacjach „statycznych” (czytanie tekstu, oglądanie zdjęcia) nie odświeżać go 60 razy na sekundę. Wszystkie te drobne kroczki składają się na jedną całość, ale dalej nie rozwiązują problemu ściany, z którą wkrótce musimy się zderzyć.
A może zmienić architekturę współczesnych komputerów zachowując paradygmat obliczeniowy maszyny Turinga (bo każdy współczesny komputer to maszyna Turinga)? Jest to bardzo ciekawa koncepcja i to nie tylko teoretyczna. W HP Labs, laboratorium badawczym Hewlett Packarda, od jakiegoś czasu pracuje się nad komputerem „The Machine”, który zmienia podejście do projektowania maszyn liczących. Współcześnie przetwarzanie danych w komputerach i innych urządzeniach polega na wykonywaniu prostych operacji binarnych oraz przenoszenia bloków danych między poszczególnymi rodzajami pamięci – od L1 i L2 w procesorze, poprzez pamięć RAM, aż do pamięci wewnętrznej urządzeń czy zewnętrznych nośników danych. Dlaczego aż tyle rodzajów pamięci? W telegraficznym skrócie – duża pamięć jest wolna, szybka pamięć jest mała. A do tego: szybka-duża pamięć jest potwornie droga i trudna do produkowania na masową skalę. W związku z tym pamięć w komputerach jest hierarchizowana – tam gdzie potrzeba dużej szybkości (blisko procesora) używa się superszybkiej pamięci rzędu pojedynczych megabajtów, potem mamy dość szybki RAM (rzędu kilku GB), dyski SSD zwykle (do ok. 1 TB) i dyski HDD i nośniki zewnętrzne o pojemności wielu terabajtów.
Segmentacja ta ma oczywisty sens z przyczyn ekonomicznych i technologicznych, ale w ogromnym stopniu spowalnia działanie komputerów. Szacuje się, że 90% czasu procesora wykorzystuje się nie na znaczące zadania obliczeniowe, a na przenoszenie bloków danych z jednej pamięci do drugiej. Czy jest na to jakiś sposób? The Machine od HP ma wykorzystywać pamięć bazującą na memrystorach, czyli rezystorach z pamięcią, które mogą przechowywać jeden bit informacji i pozwalają na budowę procesorów znacznie mniejszych niż obecnie. Użyte zostaną też bardzo szybkie fotoniczne łącza systemowe, zarówno dla podzespołów wewnętrznych, jak i urządzeń zewnętrznych. Całość ma korzystać z szybkiej pamięci uniwersalnej, bez podziału na RAM czy przestrzeń dyskową. Takie rozwiązanie mogłoby znacznie zoptymalizować i przyspieszyć działanie urządzeń opartych na takiej architekturze i odroczyć zderzenie ze ścianą na kolejne kilka lat, jednak problem ograniczeń fizyki klasycznej dalej pozostaje. Czy istnieje jakieś wyjście z tej sytuacji?
Przewrót kopernikański – fizyka kwantowa przychodzi z pomocą
Oczekujemy przewrotu kopernikańskiego w informatyce. Zmiany podejścia. Wyjścia poza uznane standardy i status quo. Thomas Kuhn w książce The Structure of Scientific Revolutions opisał to zjawisko nazwane przez niego „paradigm shift”, czyli w wolnym tłumaczeniu właśnie zmiana podejścia.
Polecam wszystkim tę książkę, która mimo tego, że powstała w 1962 roku opisuje zjawiska, które obowiązują w nauce i technologii po dziś dzień. Jedną z jego obserwacji było właśnie „paradigm shift”. Według autora, przełomy w tych dziedzinach zwykle nie odbywają się stopniowo, krok po kroku, a gwałtownie, szybko i spektakularnie. Tak było po wymyśleniu silnika parowego, tranzystora czy technologii cyfrowej. Całkowita zmiana sposobu myślenia.
Procesory krzemowe wykonujące liniowe rozkazy na zerach i jedynkach mają swoje ograniczenia i prędzej czy później ich wydajność niemalże się zatrzyma. Ale nie jest to jedynie melodia przyszłości. Już teraz klasyczne komputery nie radzą sobie z wieloma zagadnieniami. Istnieje cała klasa problemów zbyt złożonych obliczeniowo dla współczesnych maszyn liczących. Klasę tę nazwano NP (w tym problemy NP-zupełne i NP-trudne). NP, czyli problemy niedeterministycznie wielomianowe. Brzmi strasznie, prawda? Nie zagłębiając się jednak w matematyczne podstawy, jest to problem decyzyjny, dla którego rozwiązania nie można zweryfikować w czasie wielomianowym (czytaj: jego rozwiązanie będzie trwać baaaaaaardzo długo). Wraz ze wzrostem wymiarowości (skali) problemu czas potrzebny na rozwiązanie gwałtownie rośnie i może wielokrotnie przekroczyć… wiek wszechświata.
Dalej nie brzmi to zbyt jasno. Posłużmy się zatem przykładem. Jednym z najpopularniejszych problemów NP jest tak zwany problem komiwojażera. Jeśli sięgniemy do definicji, znowu natkniemy się na matematyczną nowomowę – „jest to zadanie optymalizacyjne polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym”. Nazwa pochodzi od zobrazowania tego zagadnienia, przedstawiającego problem z punktu widzenia wędrownego sprzedawcy – wyznaczone jest „n” miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast (graf ważony). Rozwiązaniem problemu komiwojażera jest znalezienie najkrótszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.
Brzmi banalnie, prawda? Poza tym, po co komuś takie czysto teoretyczne rozważania? No ok, przypomina to trochę znajdowanie najkrótszej drogi przez aplikacje nawigacji, z których korzystamy na co dzień. Zajmuje to zaledwie kilka sekund, w czym zatem problem? W tym, że algorytmy zakodowane w naszych nawigacjach nie znajdują trasy optymalnej. A mówiąc bardziej precyzyjnie: trasa którą wyznaczają NIE MUSI być optymalna. Korzystają one z tzw. algorytmów zachłannych („greedy”), czyli takich które w celu wyznaczenia rozwiązania w każdym kroku dokonują „zachłannego” (najlepiej rokującego w danym momencie) wyboru rozwiązania częściowego. Mówiąc prościej – algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie w skali globalnej, a dokonuje on wyboru WYDAJĄCEGO się w danej chwili najlepszym. Przykład? Wyznaczając trasę Warszawa – Paryż, algorytm zachłanny nie analizuje wszystkich możliwych tras (jest to problem NP, którego analiza zajęłaby miliardy lat), a jedynie kolejne pozornie optymalne kroki. I tak pierwszym krokiem byłoby na przykład przeanalizowanie czy opłaca się jechać przez Poznań, Kraków czy Gdańsk. Lokalnie optymalnym rozwiązaniem będzie Poznań. Dzięki temu problem sprowadza się do znalezienia (krótszej) trasy Poznań – Paryż. I tak w kilku (kilkudziesięciu? kilkuset?) krokach otrzymujemy rozwiązanie. Nie mamy jednak pewności, że jest to trasa optymalna, gdyż algorytm nie przeanalizował wszystkich możliwych tras. Podsumowując – dla zadań dużej skali (wymiarowości) nie jest możliwe przeanalizowanie w sensownym czasie wszystkich kombinacji rozwiązań (problem NP), stosuje się zatem algorytmy „zachłanne” które mniej lub bardziej skutecznie potrafią zbliżyć się do rozwiązania optymalnego. Ale nie zawsze je znajdują.
Kolejnym praktycznym zastosowaniem problemów NP i ograniczeń klasycznych komputerów jest szyfrowanie oparte na faktoryzacji liczb będących iloczynem dwóch liczb pierwszych. Faktoryzacja to po prostu rozkład na czynniki. Chcąc rozłożyć na czynniki liczbę 6, otrzymamy 3 i 2 (parę liczb pierwszych). Każda liczba, która nie jest liczbą pierwszą składa się z iloczynu co najmniej dwóch liczb pierwszych. RSA to jeden z pionierskich asymetrycznych (z kluczem publicznym i prywatnym) algorytmów kryptograficznych. Jego siła szyfrowania opiera się właśnie na trudności faktoryzacji dużych liczb złożonych (pary losowo wybranych dużych liczb pierwszych). Po informacje czym jest klucz publiczny i prywatny i jak się je generuje odsyłam do Wikipedii, ale wróćmy do zagadnienia rozkładu liczby na czynniki i trudności z tym związanych. W Internecie znajdziemy prosty przykład: mając dwie liczby 65537 i 65539, można szybko je pomnożyć przez siebie i w ułamkach sekund otrzymać wynik: 4295229443. Jednak rozłożenie 4295229443 na czynniki jest trudne – rozłożenie czyli znalezienie tych dwóch liczb będących dwoma czynnikami działania mnożenia. Faktoryzacja odpowiednio długiej liczby zajmie współczesnym komputerom miliony lub miliardy lat (w zależności od długości wybranej liczby).
Ale jaki to ma związek ze zmianą paradygmatu? Zasadniczy. Jeśli nie zmienimy podejścia, współczesne komputery, mimo ciągłego zwiększania mocy obliczeniowej i tak nigdy nie poradzą sobie ze złożonymi problemami klasy NP. Z pomocą mogą nam przyjść… komputery kwantowe, które jeszcze niedawno były tylko abstrakcyjnym tworem w głowach fizyków. Musimy zacząć od definicji. Wikipedia podaje, że komputer kwantowy to układ fizyczny, do opisu którego wymagana jest mechanika kwantowa, zaprojektowany tak, aby wynik ewolucji tego układu reprezentował rozwiązanie określonego problemu obliczeniowego. Ciężko wyobrazić sobie gorszą definicję.
Zacznijmy zatem od początku. W klasycznych komputerach dane są jednoznacznie reprezentowane przez zera lub jedynki w kolejnych bitach pamięci. Na tych danych procesory wykonują operacje arytmetyczno-logiczne. Dane w komputerach kwantowych z kolei, reprezentowane są przez aktualny „stan kwantowy” komputera. Zmiany tego stanu odpowiadają procesowi obliczeniowemu. Najważniejsze jest to, że odpowiednie zaplanowanie tych zmian, czyli stworzenie celowego algorytmu kwantowego pozwalałoby na osiągnięcie wyników obliczeń w znacznie szybszy i wydajniejszy sposób, niż za pomocą komputerów klasycznych. Nadal jednak nie wiemy o co tak naprawdę chodzi.
Najważniejszymi elementami kwantowego komputera są kwantowe bramki logiczne. Kwantowy bit (kubit, qbit), zgodnie fizyką kwantową nie będzie miał ustalonej jednoznacznej wartości 1 lub 0. W trakcie wykonywania obliczeń będzie się znajdował w stanie pośrednim – kubit jest zatem kwantową superpozycją zera i jedynki. Pojedynczy wynik obliczeń komputera kwantowego będzie w związku z tym obarczony niepewnością. Istotne staje się więc wykonanie całej serii obliczeń i dopiero ich uśredniona wartość określi wynik (tym dokładniejszy, im więcej komputer dokona obliczeń).
Na temat podstaw teoretycznych można by napisać wiele więcej i poprzednie akapity jedynie w bardzo ogólny sposób objaśniają ten trudny temat. Posłużmy się jednak przykładem i wróćmy do problemu komiwojażera. Chcąc sprawdzić wszystkie możliwe drogi i wybrać najkrótszą, klasyczny komputer musiałby zapisać każdą z nich (z dróg) w postaci ciągu zer i jedynek (ciągu o tej samej długości dla każdej z tras), a potem na tej podstawie dla każdego ciągu dokonać obliczeń długości trasy. Liczba tych ciągów jest jednak tak ogromna, że nie starczyłoby ani pamięci ani mocy obliczeniowej, żeby wyliczyć to w skończonym (rozsądnym) czasie. Komputer kwantowy natomiast, zamiast kwantyliona różnych ciągów zer i jedynek (bitów) reprezentujących wszystkie możliwe trasy posłużyłby się jednym ciągiem kubitów i znalazł optymalny wynik w mgnieniu oka. Oczywiście przykład ten to duże uproszczenie, ale pozwala wyobrazić sobie dlaczego komputery kwantowe budzą tak wiele emocji i nadziei.
Kwantowy komputer w praktyce
Sama idea komputera kwantowego jest genialna i przełomowa. Jak zwykle w takim przypadku, problemy pojawiają się podczas praktycznej realizacji fizycznej takiego urządzenia. Wynika to głównie z niestabilności stanów kwantowych, które mogą być zakłócone przez najdrobniejsze wahania parametrów fizycznych, takich jak pole magnetyczne, temperatura czy ruch.
Nie oznacza to jednak, że od lat 90-tych nic nie udało się osiągnąć w tej dziedzinie. Kubitami są „zwykłe” cząstki elementarne takie jak fotony czy elektrony. Pierwsze praktyczne konstrukcje do kontrolowanych obliczeń kwantowych zaprezentowano już w 1995 roku, kiedy to udało się skonstruować kwantowe bramki, które przetwarzały kubity. Grupa z Instytutu Technologii w Pasadenie posłużyła się do tego atomem cezu, który został pochwycony w optyczną pułapkę pomiędzy lustrami, a rolę kubitów grały fotony o różnej polaryzacji. A co z zastosowaniami praktycznymi i mocą obliczeniową? Na razie skala jest bardzo mała, mimo dużych rozmiarów samych urządzeń, które muszą być ściśle izolowane od zakłóceń świata zewnętrznego. W tej dziedzinie wiele zawdzięczmy koncernowi IBM, który w 2001 roku stworzył 7-kubitowy komputer kwantowy i za pomocą algorytmu Shora dokonał faktoryzacji liczby 15 (na 5 i 3). W 2011 roku inny zespół na czynniki pierwsze rozbił liczbę 21 (7 x 3). Wydać dziesiątki milionów dolarów na obliczenie, które dzieci wykonują w szkole podstawowej? Spokojnie, to dopiero nieśmiałe początki…
Głośno jest też o firmie D-Wave Systems projektującej komputery kwantowe, szczególnie po ogłoszeniu, że niektóre egzemplarze testowe trafiły do Google i NASA. W 2007 roku zaprezentowano układ oparty na 128 kubitach, ale niestety architektura tego komputera jest tajemnicą i nie do końca można zweryfikować zapewnienia twórców i producenta. W roku 2012 użyto 84-kubitowego komputera tej firmy do obliczenia liczb Ramseya (kolejny problem klasy NP) na małą skalę. Maszyny wykorzystywane przez Google i NASA to w teorii jednostki 128-kubitowe, ale para naukowców John Smolin i Graeme Smith (ale nie TEN Lee Smolin) na łamach Nature opublikowali pracę, która kwestionuje pełną kwantowość rozwiązania od D-Wave. Sceptycznie podchodzi do tego też sam IBM. Przedstawiciele D-Wave argumentują jednak, że definicja komputera kwantowego jest szeroka, a ich komputer wykorzystuje prostsze do opanowania zjawiska kwantowego wyżarzania. Na niekorzyść D-Wave zadziałała też publikacja testów algorytmów, które wykazały, że komputer ten nie wykazał żadnej przewagi obliczeniowej nad klasycznymi rozwiązaniami. Komputerami kwantowymi zainteresowana jest też Agencja Bezpieczeństwa Wewnętrznego Stanów Zjednoczonych (NSA). Przyczyny są oczywiste – łamiąc szyfry oparte o faktoryzację dużych liczb, szpiegowanie użytkowników i łamanie zabezpieczeń stałoby się dziecinnie proste.
IBM podchodzi do prognoz bardzo ostrożnie. Zdaje sobie sprawę, że obecna technologia nie jest w stanie pozwolić na tworzenie małych i rozwojowych procesorów kwantowych, a stabilność obecnych rozwiązań pozostawia wiele do życzenia. W tym momencie dochodzimy do bardzo ważnego pytania – który kierunek wybrać? Czy rozwiązania praktyczne z mniejszym potencjałem (jak D-Wave) czy mocno problematyczne rozwiązania teoretyczne, których realizacja umożliwiłaby tworzenie przenośnych i przede wszystkim skalowalnych rozwiązań? Tą drugą drogą od ponad dekady podąża Microsoft. Michael Freedman, matematyk (nagrodzony Medalem Fieldsa – odpowiednik Nobla w matematyce) i fizyk, prawie 15 lat temu został zatrudniony w firmie z Redmond do pracy nad projektem komputera kwantowego. Jednym z jego podstawowych warunków była pełna autonomia działań i otwartość wyników.
Dzięki temu, w uniwersytecie Santa Barbara w Kalifornii, powstała Stacja Q – oddział badawczy zrzeszający matematyków, fizyków i informatyków, wspólnie pracujących nad teoretycznymi i praktycznymi aspektami projektowania komputerów kwantowych. Pomijając ogromnie skomplikowane szczegóły techniczno-fizyczne, z których zrozumieniem problem ma sam szef Microsoft Research doktor Peter Lee, można powiedzieć, że prace w Station Q zaowocowały odkryciem nowej kwazicząstki (fermion Majorany) i postawieniem na podejście topologicznie (kubity chronione topologicznie oparte na fermionie egzystującym w dwuwymiarowym tunelu złożonym z gazu elektronowego umieszczonego w silnym polu magnetycznym). Mimo tego, że fizyką teoretyczną i kwantową interesuję się od prawie 15 lat, czytając opracowania tego zespołu wielokrotnie traciłem wątek. I nie ma co się dziwić. Niels Bohr, jeden z ojców fizyki kwantowej twierdził, że jeśli ktoś mówi, że rozumie mechanikę kwantową, to… nie rozumie fizyki kwantowej. Ja nie rozumiem.
Co zatem wynika z tego dla nas, zwykłych śmiertelników, nie będących laureatami nagród Nobla czy Fieldsa? Mówiąc najogólniej, chodzi o stabilność, skalowalność i małe rozmiary. Cały zespół podkreśla, że nie ma pojęcia dokąd zaprowadzą ich te badania i czy uda się na ich podstawie zrobić działający komputer kwantowy z praktycznymi zastosowaniami. Jeśli to by się udało, możemy mieć do czynienia z końcem tranzystorowo-silikonowej ery cyfrowej, a implikacje płynące ze zwiększonych możliwości obliczeniowej mogą zmienić nasze życie w wielu dziedzinach. Od szyfrowania, bezpieczeństwa danych, do sekwencjonowania DNA, zwrotów w dziedzinie inżynierii materiałowej czy nowych leków na nieuleczalne choroby. Czy przełom taki jest możliwy i czy urzeczywistni się jeszcze za naszego życia? Pytania te wciąż pozostają otwarte.
©® GRUPA MEDIA INFORMACYJNE & ADAM NAWARA
|
