Wikipedia:Tłumaczenie miesiąca/Obliczenia równoległe

Z Wikipedii

Ten artykuł jest obecnie tłumaczeniem miesiąca z języka angielskiego. Podstawę stanowi en:Parallel computing Z Twoją pomocą może się stać artykułem na medal!. Oddaj swój głos na kolejną propozycję artykułu do tłumaczenia

UWAGA! W celu nadania kontekstu, lub zaznaczenia fragmentu wątpliwego merytorycznie, tekst w języku en zaznaczamy kolorem zielonym:

<span style="color:green">tu zaznaczona treść</span>

Cray-2 był najszybszym komputerem na świecie między 1985 a 1989 rokiem.

Obliczenia równoległe – forma wykonywania obliczeń, gdzie wiele instrukcji jest wykonywanych jednocześnie^[1]. Taka forma przetwarzania danych była wykorzystywana przez wiele lat, głównie przy wykorzystaniu superkomputerów, lecz szczególne zainteresowanie zyskała w ostatnich latach, z uwagi na fizyczne ograniczenia uniemożliwiające dalsze zwiększanie częstotliwości taktowania procesorów. Obliczenia równoległe stały się dominującym wzorcem w architekturze komputerowej, głównie za sprawą upowszechnienia procesorów wielordzeniowych^[2].

Ze względu na skalę możemy wyróżnić obliczenia równoległe: na poziomie bitów, instrukcji, danych oraz zadań. Przetwarzanie równoległe da się sklasyfikować na podstawie poziomu, na którym sprzęt wspomaga operacje równoległe. Możemy wyróżnić komputery: wielordzeniowe (zawierające jeden procesor wielordzeniowy, symetryczne wieloprocesorowe (zawierające kilka identycznych, równorzędnych procesorów) oraz systemy składające się z wielu maszyn: klastry, systemy MPP, czy Gridy. w poprzednim zdaniu pisownia i terminologia wątpliwa

Algorytmy równoległe są trudniejsze w implementacji niż sekwencyjne^[3], ponieważ współbieżność wprowadza dodatkowe możliwości popełnienia błędu, spośród których wyścigi (ang. race conditions) są najczęściej spotykanym. Natomiast nakłady na komunikację i konieczność synchronizacji obliczeń są największymi problemami w uzyskaniu wysokiej wydajności w obliczeniach równoległych.

[edytuj] Background

W przeszłości, (traditionally) oprogramowanie komputerowe było pisane dla przetwarzania sekwencyjnego. Aby rozwiązać problem tworzony jest algorytm, który składa się z ciągu instrukcji. Instrukcje te są wykonywane na procesorze, w ustalonej kolejności, na jednym komputerze. Nie można wykonywać więcej niż jednej instrukcji jednocześnie - po ukończeniu jednej instrukcji, wykonywana jest kolejna^[4].

W przetwarzaniu równoległym, inaczej niż w przypadku przetwarzania sekwencyjnego, aby rozwiązać dany problem wykorzystuje się wiele jednostek obliczeniowych jednocześnie. Można tak postąpić dzieląc problem na mniejsze, niezależne części, z których jedna może być wykonywana niezależnie od pozostałych. Jeśli uda się przeprowadzić taki podział, każda z części może być wykonana na innej jednostce obliczeniowej w tym samym czasie co pozostałe. Jednostki obliczeniowe nie muszą być takie same i mogą zawierać takie zasoby jak pojedynczy komputer z wieloma procesorami, wiele komputerów połączonych siecią, specjalistyczne urządzenia (specialized hardware) lub kombinację powyższych (gdzie to jest w cytowanym materiale?)^[4].

Skalowanie częstotliwości było dominującym czynnikiem w zwiększaniu szybkości działania komputerów od połowy lat 80. do 2004 roku. Czas wykonywania programu jest równy liczbie instrukcji pomnożonej przez średni czas wykonywania instrukcji. Zachowując stałość reszty parametrów (Maintaining everything else constant (styl?)), zwiększanie częstotliwości zegara zmniejsza średni czas jaki potrzebny jest na wykonanie instrukcji. Wzrost częstotliwości zmniejsza zatem czas wykonywania wszystkich programów, w których prędkość procesora ma dominujący wpływ na szybkość ich wykonania (zob. CPU bound) computation-bounded programs.^[5]

Moc power consumption (pobór mocy?) danego układu scalonego (chip) określa się wzorem P = C × V² × F, gdzie P oznacza moc (power), C pojemność elektryczną przełączaną (zmienianą?) przy każdym cyklu zegara (capacitance being switched per clock cycle) (proporcjonalna do ilości tranzystorów, których dane wejściowe się zmieniają), V napięciem i F częstotliwością procesora (liczba cykli zegara na sekundę).^[6] Wzrosty częstotliwości zwiększają ilość pobieranej energii przez procesor. Powiększający się pobór energii procesorów skłonił firmę Intel ku decyzji podjętej w maju 2004 dotyczącej zamknięcia projektu tworzenia procesorów Tejas i Jayhawk. Decyzja ta jest często jest cytowana jako koniec dominacji skalowania częstotliwości w architekturze komputerowej.^[7]

Prawo Moore'a jest empiryczną obserwacją mówiącą, iż liczba tranzystorów w układzie scalonym podwaja się co 18 - 24 miesiące. Mimo problemów z poborem energii i częstych zapowiedzi jego końca, prawo Moore'a jest nadal aktualne. W związku z końcem skalowania częstotliwości, dodatkowe tranzystory (które nie są już używane dla skalowania częstotliwości) mogą być używane aby dodać extra hardware for parallel computing.

[edytuj] Prawa Amdahla i Gustafsona

Czas wykonania przykładowego programu (na niebiesko) i jego przyspieszenie (na czerwono) z suboptymalnym suboptimal zrównolegleniem. Przerywane linie pokazują optymalny liniowy wzrost przyspieszenie i and linear decrease in runtime - niezupełnie, rysunek trzeba poprawić. Dla pewnej wartości czas wykonania przestaje maleć mimo zwiększania liczby procesorów (podobnie przyspieszenie zaczyna maleć), zjawisko to nazywamy parallel slowdown.

Teoretycznie, przyspieszenie spowodowane zrównolegleniem powinno być liniowe – podwojenie liczby jednostek obliczeniowych powinno zmniejszyć czas obliczeń o połowę, jednak bardzo mało algorytmów równoległych osiąga optymalne przyspieszenie. Większość z nich osiąga przyspieszenie bliskie optymalnemu dla małej liczby jednostek obliczeniowych ale następnie dąży do stałej wartości dla większej liczby jednostek.

Potencjalne przyspieszenie algorytmu na platformie korzystającej z obliczeń równoległych jest określone przez prawo Amdahla, które Gene Amdahl sformułował w latach 60-tych XX wieku^[8]. Duży matematyczny czy inżynierski problem typowo składa się z takich części, które udaje się zrównoleglić i z takich, dla których nie jest to możliwe. Prawo Amdahla stanowi iż fragmenty programu które nie mogą być zrównoleglone ograniczają możliwe do osiągnięcia przyspieszenie całego procesu. Ten związek jest definiowany przez następujące równanie:

gdzie S jest maksymalnym, możliwym do osiągnięcia przyspieszeniem programu (jako ułamek swojej pierwotnej prędkości w przypadku wykonywania sekwencyjnego) a P jest ułamkiem który określa jaką część obliczeń można "zrównoleglić". Na przykład, jeśli sekwencyjna część programu stanowi 10% całkowitego czasu potrzebnego na jego wykonanie (1 − P = 0,1), to można osiągnąć nie więcej niż 10-krotne przyspieszenie, niezależnie od ilości procesorów jakie zostaną dodane. Tworzy to odgórny limit przydatności dodawania większej ilości jednostek obliczeniowych. "Jeśli zadanie nie może być podzielone z uwagi na ograniczenia wynikające z sekwencyjności problemu, dodane mocy przetwarzania nie wpłynie na czas jego wykonania. Ciąża u ludzi trwa dziewięć miesięcy, obojętnie, ile kobiet uczestniczy w jej utrzymaniu".^[9]

Prawo Gustafsona (ang. Gustafson's law) jest kolejnym prawem w inżynierii komputerowej, blisko spokrewnionym z prawem Amdahla. Może być one zdefiniowane następująco:

Graficzna reprezentacja prawa Amdahla. Jeśli zadanie składa się z dwóch niezależnych części A i B oraz część B stanowi około 25% czasu potrzebnego na wykonanie całego zadania, to pięciokrotne przyspieszenie wykonania części B skutkuje znacznie mniejszym przyspieszeniem wykonania całości zadania niż zaledwie dwukrotne przyspieszenie wykonania części A.

gdzie P jest liczbą procesorów, S przyspieszeniem a α częścią procesu, która nie może być wykonywana równolegle.^[10] Prawo Amdahla, w przeciwieństwie do prawa Gustafsona, zakłada iż problem ma stałą wielkość (assumes a fixed-problem size) oraz, że wielkość części, którą można wykonać równolegle jest niezależna od liczby procesorów.

[edytuj] Zależności

Zrozumienie zależności danych jest kluczowe w implementacji algorytmów równoległych. Żaden program nie może być wykonany szybciej niż najdłuższy łańcuch zależnych od siebie obliczeń (znanych jako ścieżka krytyczna), ponieważ obliczenia, które są zależne od poprzednich obliczeń w łańcuchu muszą być wykonywane po sobie. Jednak większość algorytmów nie składa się tylko z długich łańcuchów zależnych od siebie obliczeń; najczęściej pojawia się możliwość wykonania dwóch niezależnych obliczeń równolegle.

Niech P_i i P_j będą dwoma fragmentami programu. Warunki Bernsteina^[11] opisują kiedy dwa fragmenty są niezależne od siebie i mogą być wykonane równolegle. Niech I_i będzie zbiorem wszystkich zmiennych wejściowych dla P_i, a O_i zbiorem zmiennych wyjściowych, and likewise for P_j (tak samo I_ji O_i dla P_j? (styl)). P _i i P_j są niezależne, jeśli spełniają następujące warunki:

Naruszenie pierwszego warunku wprowadza zależność przepływu, odpowiadającą sytuacji, w której wynikiem działania pierwszego wyrażenia jest wartość wykorzystywana przez następne wyrażenie. Drugi warunek przedstawia antyzależność, w której pierwsze wyrażenie nadpisuje wartość wymaganą przez kolejny element programu. Trzeci warunek to zależność wejścia. W sytuacji, gdy dwie zmienne zapisują swoje wartości w jednym miejscu, stan tej wartości może być wynikiem działania drugiej procedury.^[12]

Następujące funkcje pokazują kilka rodzajów zależności:

1: function Zależne(a, b)
2:    c := a·b
3:    d := 2·c
4: end function

Operacja 3 w Zależne(a, b) nie może być wykonana przed (czy nawet równolegle z) operacją 2, ponieważ operacja 3 wykorzystuje wynik z operacji 2. Narusza warunek 1 i w konsekwencji tworzy flow dependency (zależność strumieniową? (język)).

1: function Niezależne(a, b)
2:      c := a·b
3:      d := 2·b
4:      e := a+b
5: end function

W tym przykładzie nie ma żadnych zależności pomiędzy operacjami, a więc mogą one być wykonane równolegle.

Warunki Bernsteina nie zezwalają na współdzielenie pamięci pomiędzy różnymi procesami. W konsekwencji, potrzebne jest ustalanie kolejności między dostępami do pamięci, korzystając z takich technik jak semafory, bariery czy inne techniki synchronizacji.

[edytuj] Sytuacje wyścigu, wzajemne wykluczanie, synchronizacja i spowolnienie równoległe

Zadania składowe programu realizowanego równolegle często noszą nazwę wątków. Niektóre równolegle pracujące komputery zaprojektowane są tak, by wykorzystywać lżejsze odmiany wątków - włókna - podczas, gdy niektóre maszyny korzystają z procesów. Najczęściej jednak ogólnie przyjmuje się do oznaczania zadań składowych słowa "wątek". Podczas wykonywania programu, poszczególne wątki często muszą uaktualniać szereg współdzielonych zmiennych. Polecenia pomiędzy wątkami mogą się przeplatać w dowolny sposób. Weźmy jako przykład następujący program:

Jeśli instrukcja 1B zostanie wykonana pomiędzy 1A i 3A, lub jeśli instrukcja 1A zostanie wykonana pomiędzy 1B i 3B, to wynik działania programu będzie nieprawidłowy. Zjawisko to jest znane jako wyścigi (ang. race conditions), a fragment programu, który nie powinien być wykonywany przez kilka wątków jednocześnie, nazywamy sekcją krytyczną. W takim przypadku jak powyżej programista powinien zapewnić wzajemne wykluczanie pomiędzy wątkami w dostępie do zmiennej V. Można to osiągnąć stosując blokady – konstrukcje programistyczne, dzięki którym tylko jeden wątek ma dostęp do określonego zasobu. Powyższy fragment programu przepisany z użyciem blokad mógłby zostać przepisany w następujący sposób:

Tylko jeden z wątków z sukcesem zablokuje zmienną V i uzyska do niej wyłączny dostęp, podczas gdy drugi będzie musiał czekać na jej odblokowanie. Zastosowanie powyższej konstrukcji daje gwarancję poprawnego wykonania programu, kosztem jest jednak jego spowolnienie, które może być znaczne.

Blokowanie wielu zmiennych przy użyciu nieatomowych blokad może spowodować zakleszczenie. Atomowość blokady to własność, która gwarantuje, że wszystkie zmienne blokowane są razem, to znaczy jeśli dwa wątki próbują zablokować kilka zmiennych, to uda się to tylko jednemu z nich i blokada powstanie na wszystkich zmiennych. Jeśli natomiast blokady nie są atomowe, to może się zdarzyć, że jeśli dwa wątki próbują zablokować te same dwie zmienne, to jeden z nich zablokuje jedną a drugi drugą. W powstałej sytuacji oba wątki czekają na siebie nawzajem i żaden z nich nie może zakończyć działania. Taką sytuację nazywamy zakleszczeniem.

Wiele programów równoległych wymaga by ich podzadania były dodatkowo synchronizowane. Taką możliwość daje użycie bariery. Bariery są zwykle implementowane za pomocą blokad. Klasa algorytmów, w których nie używa się blokad i barier nazywa się lock-free and wait-free algorithms. Jednak stosowanie tego podejścia napotyka spore trudności.

Nie każda próba zrównoleglenia daje efekt w postaci przyspieszenia obliczeń. W ogólności, jeśli zadanie jest dzielone na coraz więcej i więcej wątków, to w pewnym momencie narzuty związane z komunikacją zaczynają przeważać nad zyskiem ze zrównoleglenia obliczeń i pomimo zwiększania teoretycznej mocy obliczeniowej mamy do czynienia ze spowolnieniem obliczeń. Zjawisko to nazywane jest spowolnieniem równoległym (ang. parallel slowdown).

[edytuj] Fine-grained, coarse-grained, and embarrassing parallelism

Aplikacje są często klasyfikowane pod względem tego jak często podzadania wymagają synchronizacji lub komunikują się ze sobą. Mówimy wtedy o równoległości drobnoziarnistej (ang. fine-grained), jeśli komunikacja następuje wielokrotnie w ciągu sekundy, lub gruboziarnistej (ang. coarse-grained). Jeśli komunkacja nie występuje w ogóle lub sporadycznie mówimy o embarrassingly parallel?. Ostatni typ jest najłatwiejszy do zrównoleglania.

[edytuj] Modele spójności

Zobacz więcej w osobnym artykule: Model spójności.

Leslie Lamport jako pierwszy zdefiniował koncepcję spójności sekwencyjnej. Jest również znany za swoją pracę w tworzeniu oprogramowania LaTeX.

W systemach przetwarzania równoległego w celu przyspieszenia wykonywania operacji na pamięci współdzielonej stosuje się lokalne pamięci podręczne i buforowanie operacji zapisu. Istnienie tych mechanizmów może prowadzić do niespójności (dla różnych procesów te same, wspólne dane mogą przez pewien mieć różne wartości). Jako przykład można podać następującą sekwencję instrukcji (x i y są zmiennymi współdzielonymi, początkowo obie są równe 0):

Realizacja wspomnianych mechanizmów może dopuścić sytuację, gdy aktualizacja zmiennych x i y jest dostarczana so wątku A w zmienionej kolejności, a więc mogłoby się zdarzyć, że wynik porównania w 3A byłby fałszywy. W związku z tym języki programowania równoległego i komputery równoległe muszą posiadać model spójności (ang. consistency model), który definiuje zasady wykonywania operacji na zmiennych współdzielonych w pamięci komputera oraz w jaki sposób powstają wyniki tych operacji.

Jednym z pierwszych modeli spójności był model spójności sekwencyjnej Lesliego Lamporta. Spójność sekwencyjna oznacza, że wyniki każdego możliwego działania programu równoległego są takie same jak wynik działania dla pewnego ustalonego sekwencyjnego wykonania tych operacji, przy czym kolejność wykonywania operacji przez każdy pojedynczy procesor zgadza się z kolejnością wykonania zapisaną w jego programie^[13].

Powszechnym modelem spójności pamięci jest STM (ang. en:software transactional memory, w którym używa się koncepcji atomowych transakcji zapożyczonej z teorii baz danych.

Modele spójności pamięci mogą być przedstawiane formalnie na wiele sposobów. Wczesnym matematycznym modelem dla dyskretnych systemów rozproszonych są sieci Petriego, które Carl Adam Petri zdefiniował w swojej rozprawie doktorskiej w 1962 roku. Dataflow theory later built upon these, and Dataflow architectures were created to physically implement the ideas of dataflow theory. Beginning in the late 1970s, process calculi such as calculus of communicating systems and communicating sequential processes were developed to permit algebraic reasoning about systems composed of interacting components. More recent additions to the process calculus family, such as the π-calculus, have added the capability for reasoning about dynamic topologies. Logics such as Lamport's TLA+, and mathematical models such as traces and Actor event diagrams, have also been developed to describe the behavior of concurrent systems.

[edytuj] Taksonomia Flynna

Michael J. Flynn stworzył jedną z najwcześniejszych klasyfikacji systemów dla równoległych (i sekwencyjnych) komputerów i programów, znaną jako taksonomia Flynna. Flynn zaklasyfikował programy i komputery według tego czy dany program lub komputer korzysta z jednego, czy z wielu zbiorów instrukcji oraz czy te instrukcje korzystają z jednego, czy z wielu zbiorów danych.

W obrębie podziału Flynn wyróżnił cztery klasy: SISD (ang. single-instruction-single-data) równoważną przetwarzaniu całkowicie sekwencyjnemu; SIMD (ang. single-instruction-multiple-data), gdzie wykonuje się te same operacje na różnych zbiorach danych − jak to ma często miescje przy przetwarzaniu sygnałów; MISD (ang multiple-instruction-single-data) to rzadko używana klasa, w ktorej wykonujemy te same operacje na różnych danych (zob. systolic arrays); i w końcu MIMD (ang. Multiple-instruction-multiple-data), gdzie różne operacje wykonywane są na różnych zbiorach danych − jest to najczęstszy przypadek w przetwarzaniu równoległym.

Według Davida Pattersona i Johna Hennesy'a, "Niektóre maszyny są oczywiście hybrydami tych kategorii, jednak ten klasyczny model przetrwał ponieważ jest prosty, łatwy do zrozumienia i daje dobry pierwszy ogląd zagadnienia? (and gives a good first approximation). Jest również − prawdopodobnie dzięki swojej zrozumiałości − najbardziej powszechnym schematem"^[14].

[edytuj] Typy równoległości

[edytuj] Równoległość na poziomie bitów

Zobacz więcej w osobnym artykule: Bit-level parallelism.

Poczynając od powszechnego zastosowania technologii VLSI (produkcji układów scalonych o wielkiej skali integracji) w latach siedemdziesiątych aż do roku około 1986 przyspieszenie działania komputerów było uzyskiwane poprzez podwajanie długości słowa maszynowego (czyli podstawowej jednostki informacji przetwarzanej przez procesor w jednym cyklu, w uproszczeniu jest to liczba bitów będąca rozmiarem szyny danych oraz rejestrów procesora) ^[15]. Zwiększenie rozmiaru słowa maszynowego zmniejsza liczbę instrukcji jaką procesor musi wykonać realizując operację na zmiennych, których rozmiar jest większy niż długość słowa maszynowego. Na przykład jesli 8-bitowy procesor realizuje dodawanie dwóch 16-bitowych liczb całkowitych, to trzeba oddzielnie wykonać działanie na młodszych i, z uwzględnieniem przeniesienia (ang. carry bit), starszych bajtach obu liczb. Tak więc w tym przypadku konieczne było wykonanie dwóch dodawań 8-bitowych, podczas gdy 16-bitowy procesor mógłby wykonać tę operację jako jedną instrukcję.

Historycznie, 4-bitowe procesory zostały zastąpione 8-bitowymi, te z kolei 16-bitowymi, a następnie 32-bitowymi. Ten trend nieco się zatrzymał, gdyż procesory 32-bitowe stały się standardem aż do lat 2003-2004, gdy na rynku upowszechniły się procesory z architekturą 64-bitową.

[edytuj] Równoległosć na poziomie instrukcji

Zobacz więcej w osobnym artykule: Instruction level parallelism.

Klasyczny pięciostopniowy potok w maszynie typu RISC (IF = Pobranie instrukcji, ID = Zdekodowanie instrukcji, EX = Wykonanie instrukcji, MEM = Dostęp do pamięci, WB = Zapisanie wyników działania instrukcji)

Program komputerowy, technicznie rzecz biorąc, jest ciągiem instrukcji wykonywanym przez procesor. Instrukcje te mogą być grupowane, a kolejność ich wykonania zmieniana w taki sposób, aby można było wykonać je równolegle bez zmiany wyniku programu. Technika ta nazywana jest zrównoleglaniem na poziomie instrukcji, postęp w jej stosowaniu zdominował rozwój architektury komputerów od połowy lat osiemdziesiątych do połowy lat dziewięćdziesiątych XX wieku^[16].

Współczesne procesory posiadają wielostopniowe potoki instrukcji. Każdy stopień potoku odpowiada za inną czynność jaką procesor wykonuje na danej instrukcji w danym etapie; innymi słowy, proces z N-stopniowym potokiem może posiadać do N różnych instrukcji na różnym etapie wykonywania. Klasycznym przykładem potokowego procesora jest procesor RISC z pięciostopniowym potokiem: pobranie instrukcji, zdekodowanie instrukcji, wykonanie instrukcji, dostęp do pamięci oraz zapisanie wyników działania instrukcji do rejestru. Procesor Pentium 4 ma 35-stopniowy potok.^[17]

Pięciostopniowy potok w superskalarnym procesorze, który może wykonywać dwie instrukcje podczas jednego cyklu zegara. Na każdym etapie potoku mogą się znajdować dwie instrukcje co daje jednoczesne wykonywanie 10 instrukcji.

Niektóre procesory mogą wykonywać więcej niż jedną instrukcję w ciągu cyklu, stosując inne techniki niż przetwarzanie potokowe opisane powyżej. Procesory te, nazywane superskalarnymi, grupują, przestawiają instrukcje nie powiązane zależnością danych i wykonują je jednocześnie. Dwie najczęściej stosowane w tym celu techniki to scoreboarding (technika notowania?) i i podobna, nazywana algorytmem Tomasulo, w której stosuje się przemianowanie rejestrów (ang. register renaming). Możliwe jest również wykonywanie instrukcji, co do których nie ma jeszcze pewności, czy powinny być wykonane, aby ostatecznie przyjąć lub odrzucić wyniki ich działania. Jest to tak zwane spekulatywne wykonywanie instrukcji.

[edytuj] Równoległość danych

Zobacz więcej w osobnym artykule: Data parallelism.

Równoległość danych jest właściwa iteracyjnemu ich przetwarzaniu i skupia się na rozdzielaniu danych pomiędzy różne jednostki obliczeniowe w taki sposób aby zminimalizować ich wzajemne zależności. Na pozomie kodu źródłowego mówi się o zrównoleglaniu pętli (ang. parallelization of loops), gdzie często wykonuje się podobne (niekoniecznie identyczne) ciągi operacji na elementach dużej struktury danych."^[18]. Tego typu równoległość wykorzystuje wiele naukowych i inżynierskich aplikacji.

Rozdzielenie danych nie zawsze jest możliwe. Jeśli przykładowo działania w każdej kolejnej iteracji zależą od wyników poprzedniej, to zrównoleglenie pętli nie jest możliwe. Taka zależność ma miejsce w poniższym przykładzie obliczającym pierwsze kilka liczb z ciągu Fibonacciego:

1:    prev2 := 0
2:    prev1 := 1
3:    cur := 1
4:    do:
5:       CUR := PREV1 + PREV2
6:       PREV2 := PREV1
7:       PREV1 := CUR
8:    while (CUR < 10) 

Pętla ta nie może zostać zrównoleglona, ponieważ zmienne (PREV1) i PREV2 użyte do obliczenia CUR są na nowo obliczane w każdym obiegu pętli. kolejne zdanie jakoś słabo się klei do reszty, a zwłaszcza do przykładu powyżej, zatem może je po prostu usunąć? Wraz ze wzrostem rozmiaru problemu, ilość danych, które można zrównoleglić zazwyczaj również wzrasta^[19].

[edytuj] Równoległość zadań

Zobacz więcej w osobnym artykule: Równoległość zadań.

Równoległość zadań jest cechą charakterystyczną programu, w którym "zupełnie różniące się obliczenie mogą być wykonywane na tych samych lub innych zbiorach danych".^[18] Różni się ono od równoległości danych, gdzie te same obliczenia wykonywane są na tych samych lub innych zbiorach danych. Task parallelism does not usually scale with the size of a problem.^[19]

[edytuj] Hardware

[edytuj] Pamięć i komunikacja

Pamięć operacyjna w komputerze równoległym jest pamięcią współdzieloną przez wszystkie jednostki w jednej przestrzeni adresowej, lub pamięcią rozproszoną, w której każda jednostka prowadzi obliczenia we własnej przestrzenie adresowej^[20]. Pojęcie pamięci rozproszonej oznacza logiczny podział przestrzeni adresowych (fizycznie mogą one należeć do tej samej maszyny), choć zwykle oznacza to również rozproszenie fizyczne. Rozproszona pamięć dzielona odnosi się do połączenia powyższych koncepcji, gdzie logicznie pamięć jest współdzielona chociaż fizycznie mamy do czynienia z pamięcią rozproszoną (każda jednostka ma swoją fizyczną pamięć lokalną, ale na poziomie logicznym/programowym ma dostęp do pamięci innych jednostek). Rozproszona pamięć dzielona jest więc symulacją pamięci współdzielonej, co ułatwia tworzenie oprogramowania, a jednocześnie może powodować opóźnienia (dostęp do pamięci lokalnej jest typowo znacznie szybszy niż dostęp do pamięci zdalnej).

Diagram przedstawiający strukturę logiczną architektury NUMA. Procesory z in one directory mają dostęp do pamięci ze swojego directory's memory z mniejszym opóźnieniem niż z pamięci należącej do innych directory's memory.

Architektury komputerowe, w których cała pamięć operacyjna jest dostępna z takim samym opóźnieniem i częstotliwością są nazywane UMA (ang. Uniform Memory Access). Tę cechę mogą mieć właściwie tylko sytemy z pamięcią dzieloną. Pozostałe systemy określamy mianem NUMA (ang. Non-Uniform Memory Access) – do tej kategorii zaliczamy systemy z pamięcią rozproszoną.

W celu poprawy wydajności systemu komputerowego stosuje się niewielkie, ale szybkie pamięci podręczne (ang. cache memory), które mogą przechowywać tymczasowe dane. Stosowanie ich w architekturach równoległych nastręcza problemy związane z zachowaniem spójności danych (zob. cache coherency), gdyż te same dane mogą być przechowywane w pamięciach podręcznych różnych procesorów. Zapewnienie poprawności obliczeń wymusza stosowanie dodatkowych technik, z których najpopularniejsza to bus snooping. Mimo ich istnienia projektowanie wydajnych pamięci podręcznych przysparza wiele trudności, dlatego architektury oparte na pamięci dzielonej należą do trudniej skalowalnych niż te oparte na pamięci rozproszonej^[20].

Komunikcja pomiędzy dwoma procesorami oraz procesorem i pamięcią może zostać zrealizowana sprzętowo na kilka sposobów: poprzez wieloportową (ang. multiported) lub multipleksowaną pamięć dzieloną, przełącznik krzyżowy (ang. crossbar switch), wspólną magistralę (ang. shared bus) lub sieć o jednej z wielu topologii (gwiazdy, pierścienia, drzewa, hiperkostki i innych). Komputery równoległe zbudowane w oparciu o sieć (ang. interconnect network) wymagają jakiejś formy wyboru tras połączeń (ang. routing) dla procesorów, które nie są bezpośrednio połączone. Medium użyte do komunikacji pomiędzy procesorami zwykle ma strukturę hierarchiczną, zwłaszcza w przypadku dużej liczby procesorów.

[edytuj] Typy komputerów równoległych

Komputery równoległe można podzielić ze względu na poziom, na jakim sprzęt zrównolegla operacje. Klasyfikacja w dużym stopniu odpowiada temu, jak bardzo są fizycznie oddalone od siebie poszczególne jednostki obliczeniowe. Przynależność do jednej z grup nie wyklucza jednak przynależności do pozostałych. Do często spotykanych kombinacji należą na przykład klastry wieloprocesorów symetrycznych.

[edytuj] Procesory wielordzeniowe

Procesor wielordzeniowy to procesor z kilkoma jednostkami wykonawczymi ("rdzeniami"). Procesory te różnią się od procesorów superskalarnych, gdyż mogą wykonywać jednocześnie instrukcje pochodzące z różnych ciągów instrukcji; w przeciwieństwie do tych drugich, które co prawda również mogą w pewnych warunkach wykonywać kilka instrukcji jednocześnie, ale pochodzących z jednego ciągu intrukcji (w danej chwili wykonują tylko jeden wątek). Potencjalnie każdy z rdzeni może być jednostką superskalarną.

Wczesną formą procesorów wielordzeniowych była technologia SMT (ang. simultaneous multithreading), którą zastosowano na przykład w procesorach i Pentium 4 (zob. HyperThreading). Procesor z technologią SMT ma tylko jeden rdzeń, ale kiedy jest bezczynny (ang. idle), na przykład z powodu konieczności odwołania poza pamięć podręczną (ang. cache miss), może go wykorzystać do wykonywania kolejnego wątku. Jako faktycznie wielordzeniowe procesory można wymienić architektury Core oraz Cell.

[edytuj] Symetryczne systemy wieloprocesorowe

Zobacz więcej w osobnym artykule: Wieloprocesorowość symetryczna.

Wieloprocesor symetryczny (SMP - ang. symmetric multiprocessor) to system komuterowy z wieloma identycznymi procesorami, które operują na wspólnej pamięci poprzez magistralę (ang. bus)^[21]. Z powodu zastosowania magistrali rozwiązanie to jest jednak słabo skalowalne, dlatego zwykle maszyny SMP posiadają nie więcej niż 32 procesory^[22]. Stosowanie dużych pamięci podręcznych, co ogranicza wykorzystanie magistrali, i niewielkich rozmiarów procesorów powduje, że wieloprocesory symetryczne są, przy założeniu o dostatecznie szybkim dostępie do pamięci, bardzo wydajne przy stosunkowo niewielkich kosztach ("Because of the small size of the processors and the significant reduction in the requirements for bus bandwidth achieved by large caches, such symmetric multiprocessors are extremely cost-effective, provided that a sufficient amount of memory bandwidth exists."^[21]).

[edytuj] Przetwarzanie rozproszone

Zobacz więcej w osobnym artykule: Przetwarzanie rozproszone.

Przetwarzanie rozproszone (znane też jako wieloprocesor o rozproszonej pamięci) jest systemem komputerowym o rozproszonej pamięci, w którym elementy przetwarzające połączone są przez sieć komputerową. Komputery rozproszone są wysoce skalowalne^{[potrzebne źródło]}.

[edytuj] Przetwarzanie klastrowe

Zobacz więcej w osobnym artykule: Klaster komputerowy.

Klaster Beowulf

Klaster jest grupą komputerów, które w pewnych aspektach mogą być traktowane jako pojedynczy komputer^[23]. Klastry składają się z wielu niezależnych komputerów połączonych siecią. Podczas gdy maszyny w klastrze nie muszą być symetryczne, równoważenie obciążenia jest trudniejsze jeśli nie są. Najbardziej popularny typ klastra to Beowulf^{[potrzebne źródło]}, który jest klastrem zaimplementowanym na wielu identycznych komputerach połączonych siecią lokalną Ethernet opartą o protokół TCP/IP^[24]. Technologia Beowulf została stworzona przez Thomasa Sterlinga i Donalda Beckera. Znaczna część superkomputerów z listy TOP500 to klastry^[25].

[edytuj] Komputery masowo równoległe

Zobacz więcej w osobnym artykule: Komputery masowo równoległe.

Masowo równoległy komputer (ang. Massively Parallel Processor) jest jednym komputerem z wieloma połączonymi ze sobą procesorami. Komputer ten posiada wiele podobnych cech do klastrów, jednak jest on zazwyczaj większy i posiada o wiele więcej niż 100 procesorów.^[26] W komputerze masowo równoległym, "każdy procesor posiada swoją własna pamięć oraz kopię systemu operacyjnego i aplikacji. Każdy podsystem komunikuje się z innymi poprzez szybkie łącza."^[27]

A cabinet from Blue Gene/L, ranked as the fastest supercomputer in the world according to the TOP500 rankings. Blue Gene/L is a massively parallel processor.

Blue Gene/L, najszybszy superkomputer na świecie, wg. rankingu TOP500, jest komputerem masowo równoległym.^{[potrzebne źródło]}.

[edytuj] Grid computing

Zobacz więcej w osobnym artykule: Grid.

Grid computing jest najbardziej rozproszoną formą obliczeń równoległych. Mamy tu do czynienia z komputerami połączonymi siecią Internet, których zasoby używane są do rozwiązania danego problemu. Ze względu na niewielką przepustowość i duże opóźnienia łączy, zwykle tylko embarrassingly parallel problems są roziązywane w ten spoób. Wśród realizacji obliczeń gridowych można wymienić SETI@home i Folding@Home jako szerzej znane.

Większość aplikacji korzysta z warstwy pośredniej (ang. middleware) - oprogramowania, które, działając na poziomie pomiędzy system operacyjnym a aplikacjami, dostarcza usług związanych z wykorzystaniem zasobów sieciowych. Jako przykład można wymienić system BOINC (ang. Berkeley Open Infrastructure for Network Computing), który pierwotnie powstał dla potrzeb projektu SETI@home.

[edytuj] Dedykowane komputery równoległe

Within parallel computing, there are specialized parallel devices that remain niche areas of interest. While not domain-specific, they tend to be applicable to only a few classes of parallel problems.

Rekonfigurowalne Systemy Obliczeniowe

System rekonfigurowalny składa się z procesora ogólnego przeznaczenia oraz programowalnych układów logicznych FPGA (ang. field-programmable gate array).

Układy FPGA programuje się przy użyciu języków HDL (ang. Hardware Description Language) takich jak VHDL czy Verilog. Programowanie w tych językach może być jednak monotonne i męczące, dlatego powstało kilka narzędzi, które próbują emulować elementy składni i semantyki języka C, znanego większości programistów, tłumacząc je na język typu HDL. Jako przykłady takich rozwiązań można podać: Mitrion-C, Impulse C, DIME-C oraz Handel-C.

Upublicznienie specyfikacji technologii HyperTransport przez AMD umożliwiło dostęp do wysoko wydajnych, rekonfigurowalnych obliczeń stronom trzecim^[28].

GPGPU with graphics processing units

Zobacz więcej w osobnym artykule: GPGPU.

General-purpose computing on graphics processing units (GPGPU) is a fairly recent trend in computer engineering research. GPUs are co-processors that have been heavily optimized for computer graphics processing.^[29] Computer graphics processing is a field dominated by data parallel operations—particularly linear algebra matrix operations.

In the early days, GPGPU programs used the normal graphics APIs for executing programs. However, recently several new programming languages and platforms have been built to do general purpose computation on GPUs with both Nvidia and AMD releasing programming environments with CUDA and CTM respectively. Other GPU programming languages are BrookGPU, PeakStream, and RapidMind. Nvidia has also released specific products for computation in their Tesla series.

Application-specific integrated circuits

Zobacz więcej w osobnym artykule: Application-specific integrated circuit.

Several Application-specific integrated circuit (ASIC) approaches have been devised for dealing with parallel applications.^[30][31][32]

Because an ASIC is (by definition) specific to a given application, it can be fully optimized for that application. As a result, for a given application, an ASIC tends to outperform a general-purpose computer. However, ASICs are created by X-ray lithography. This process requires a mask, which can be extremely expensive. A single mask can cost over a million US dollars.^[33] (The smaller the transistors required for the chip, the more expensive the mask will be.) Meanwhile, performance increases in general-purpose computing over time (as described by Moore's Law) tend to wipe out these gains in only one or two chip generations.^[28] High initial cost, and the tendency to be overtaken by Moore's-law-driven general-purpose computing, has rendered ASICs unfeasible for most parallel computing applications. However, some have been built. One example is the peta-flop RIKEN MDGRAPE-3 machine which uses custom ASICs for molecular dynamics simulation.

Procesory wektorowe

Zobacz więcej w osobnym artykule: Procesor wektorowy.

Cray-1 jest najbardziej znanym procesorem wektorowym.

Procesor wektorowy jest procesorem lub systemem komputerowym, który wykonuje te same instrukcje na dużych zbiorach danych. "Procesory wektorowe posiadają operacje wysokiego poziomu, które działają na liniowych tablicach składających się z liczb lub wektorów. Przykładem operacji wektorowej jest gdzie A, B i C są 64-elementowymi wektorami złożonymi z 64-bitowych liczb zmiennoprzecinkowych"^[34] Są blisko spokrewniony z klasyfikacją SIMD Flynna. They are closely related to Flynn's SIMD classification.^[34].

Cray computers became famous for their vector-processing computers in the 1970s and 1980s. However, vector processors—both as CPUs and as full computer systems—have generally disappeared. Modern processor instruction sets do include some vector processing instructions, such as with AltiVec and Streaming SIMD Extensions (SSE).

[edytuj] Oprogramowanie

Concurrent programming languages, libraries, APIs, and parallel programming models have been created for programming parallel computers. These can generally be divided into classes based on the assumptions they make about the underlying memory architecture—shared memory, distributed memory, or shared distributed memory. Shared memory programming languages communicate by manipulating shared memory variables. Distributed memory uses message passing. POSIX Threads and OpenMP are two of most widely used shared memory APIs, whereas Message Passing Interface (MPI) is the most widely used message-passing system API. One concept used in programming parallel programs is the future concept, where one part of a program promises to deliver a required datum to another part of a program at some future time.

[edytuj] Zrównoleglanie Automatyczne

Zobacz więcej w osobnym artykule: Automatic parallelization.

Automatyczne zrównoleglanie sekwencyjnego programu przez kompilator jest "świętym graalem" obliczeń równoległych. Mimo wieloletniej pracy dokonanej przez twórców kompilatorów (compiler researchers), zrównoleglanie automatyczne osiągnęło jedynie ograniczony sukces.^[35]

Mainstream parallel programming languages remain either explicitly parallel or (at best) partially implicit, in which a programmer gives the compiler directives for parallelization. A few fully implicit parallel programming languages exist—SISAL, Parallel Haskell, and (for FPGAs) Mitrion-C—but these are niche languages that are not widely used.

[edytuj] Application checkpointing

Wraz ze wzrostem stopnia skomplikowania komputerów rośnie również liczba występujących błędów i zmniejsza się średni bezawaryjny czas ich pracy. Jedną z technik zapewniania poprawności obliczeń jest zapamiętywanie, w czasie działania aplikacji, tak zwanych punktów kontrolnych (ang. application checkpointing). Innymi słowy, system co jakiś czas zapamiętuje stan działania aplikacji wraz ze wszystkimi wykorzystywanymi zasobami (zobacz też ang. core dump), aby w razie wystąpienia błędu wznowić obliczenia od ostatniego punktu kontrolnego, zamiast wykonywać je wszystkie od początku. Technika ta może również ułatwić migrację procesów.

[edytuj] Zastosowania

Wraz z postępem w szybkości działania komputerów równoległych coraz więcej problemów, których rozwiązanie wcześniej nie było możliwe, jest w zasięgu dostępnych mocy obliczeniowych. Zastosowanie obliczeń równoległych obejmuje szerokie spektrum dziedzin nauki od bioinformatyki (zob. zwijanie białka) do ekonomii (symulacje w matematyce finansowej).

Typowe problemy, gdzie może być wykorzystane przetwarzanie równoległe obejmują^[36]:

• gęstą algebrę liniowa – metody numeryczne w algebrze liniowej, gdzie dane są macierzami lub wektorami gęstymi,
• rzadką algebrę liniową – metody numeryczne w algebrze liniowej, gdzie dane są macierzami lub wektorami rzadkimi,
• metody spektralne – dane są w dziedzinie częstotliwości (ang. Frequency domain) w odróżnieniu do dziedziny czasu i przestrzeni,
• symulacje zachowania układu ciał pod wpływem oddziaływań fizycznych (ang. N-body simulation), na przykład symulacja Barnesa-Huta (ang. Barnes-Hut simulation),
• obliczenia z rozmieszczeniem węzłów w siatce prostokątnej (ang. regular grid problems) takich jak metoda kratowa Boltzmanna (ang. Lattice Boltzmann methods) stosowana w mechanice płynów,
• obliczenia z nieregularnym rozmieszczeniem węzłów (ang. unstructured grid problems) tak jak w analizie metodą elementów skończonych,
• symulacje metodą Monte Carlo,
• zagadnienia związane z układami kombinacyjnymi takie jak atak typu brute force,
• problemy, w których występuje przeszukiwanie grafu
• programowanie dynamiczne,
• algorytmy typu branch and bound,
• obliczenia w modelach grafowych (ang. graphical models) takie jak wykrywanie ukrytych modeli Markowa lub konstruowanie sieci bayesowskich),
• symulacja działania automatu skończonego.

[edytuj] Historia

ILLIAC IV, "perhaps the most infamous of Supercomputers"

The origins of true (MIMD) parallelism go back to Federico Luigi, Conte Menabrea and his "Sketch of the Analytic Engine Invented by Charles Babbage."^[37][38] IBM introduced the 704 in 1954, through a project in which Gene Amdahl was one of the principal architects. It became the first commercially available computer to use fully automatic floating point arithmetic commands.^[39] In 1958, IBM researchers John Cocke and Daniel Slotnick discussed the use of parallelism in numerical calculations for the first time.^[40] Burroughs Corporation introduced the D825 in 1962, a four-processor computer that accessed up to 16 memory modules through a crossbar switch.^[41] In 1967, Amdahl and Slotnick published a debate about the feasibility of parallel processing at American Federation of Information Processing Societies Conference.^[40] It was during this debate that Amdahl's Law was coined to define the limit of speed-up due to parallelism.

In 1969, US company Honeywell introduced its first Multics system, a symmetric multiprocessor system capable of running up to eight processors in parallel.^[40] C.mmp, a 1970s multi-processor project at Carnegie Mellon University, was "among the first multiprocessors with more than a few processors".^[38] "The first bus-connected multi-processor with snooping caches was the Synapse N+1 in 1984."^[38]

SIMD parallel computers can be traced back to the 1970s. The motivation behind early SIMD computers was to amortize the gate delay of the processor's control unit over multiple instructions.^[42] In 1964, Slotnick had proposed building a massively parallel computer for the Lawrence Livermore National Laboratory.^[40] His design was funded by the US Air Force, which was the earliest SIMD parallel-computing effort, ILLIAC IV.^[40] The key to its design was a fairly high parallelism, with up to 256 processors, which allowed the machine to work on large datasets in what would later be known as vector processing. However, ILLIAC IV was called "the most infamous of Supercomputers", because the project was only one fourth completed, but took 11 years and cost almost four times the original estimate.^[43] When it was finally ready to run its first real application in 1976, it was outperformed by existing commercial supercomputers such as the Cray-1.

[edytuj] Przypisy

1. ↑ G.S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin-Cummings publishers, Redwood city, CA, 1989.
2. ↑ Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. December 18, 2006: "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
3. ↑ David A. Patterson and John L. Hennessy. Computer Organization and Design (Second Edition) Morgan Kaufmann Publishers, 1998. ISBN 1558604286, p. 715.
4. ↑ ^{4,0 4,1} Blaise Barney: Introduction to Parallel Computing. Lawrence Livermore National Laboratory. [dostęp 2007-11-09].
5. ↑ John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, ISBN 1558607242, p. 43.
6. ↑ J.M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996. ISBN 0131786091, p. 235.
7. ↑ Laurie J. Flynn. Intel Halts Development of 2 New Microprocessors. The New York Times, May 8, 2004. Retrieved on April 22, 2008.
8. ↑ G. Amdahl. The validity of the single processor approach to achieving large-scale computing capabilities. In Proceedings of AFIPS Spring Joint Computer Conference, pp. 483–85, Atlantic City, N.J., April 1967. AFIPS Press.
9. ↑ The Mythical Man-Month: Essays on Software Engineering. Frederick P. Brooks Jr.. rozdział 2 - The Mythical Man Month. ISBN 0201835959
10. ↑ Reevaluating Amdahl's Law Communications of the ACM 31(5), 1988. pp. 532–33.
11. ↑ A.J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, October 1966, pp. 757–62.
12. ↑ Roosta, Seyed H. Parallel processing and parallel algorithms: theory and computation. 2000. Springer, ISBN 0387987169, str. 114.
13. ↑ Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9 (September 1979), pp. 690–91.
14. ↑ Patterson and Hennessy, p. 748.
15. ↑ David E. Culler, Jaswinder Pal Singh, Anoop Gupta. Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, 1999. ISBN 1558603433, p. 15.
16. ↑ Culler et al. p. 15.
17. ↑ Yale Patt. "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). Distinguished Lecturer talk at Carnegie Mellon University, April 2004. Retrieved on November 7, 2007.
18. ↑ ^{18,0 18,1} Culler et al. p. 124
19. ↑ ^{19,0 19,1} Culler et al. p. 125.
20. ↑ ^{20,0 20,1} Patterson and Hennessy, p. 713.
21. ↑ ^{21,0 21,1} Hennessy and Patterson, p. 549.
22. ↑ Patterson and Hennessy, p. 714.
23. ↑ What is clustering? (en). [dostęp 16 maja 2008].
24. ↑ Beowulf definition (en). [dostęp 16 maja 2008].
25. ↑ Architecture share for 11/2007 (en). [dostęp 16 maja 2008].
26. ↑ Hennessy and Patterson, p. 537.
27. ↑ MPP Definition. PC Magazine. Dostęp 2 czerwca 2008.
28. ↑ ^{28,0 28,1} Michael R. D'Amour, CEO DRC Computer Corporation. "Standard Reconfigurable Computing". Invited speaker at the University of Delaware, 28 lutego 2007.
29. ↑ Sha'Kia Boggan and Daniel M. Pressel. GPUs: An Emerging Platform for General-Purpose Computation (PDF). ARL-SR-154, U.S. Army Research Lab. August 2007. Retrieved on 7 listopada 2007.
30. ↑ Oleg Maslennikov (2002). Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units. Lecture Notes in Computer Science, 2328/2002: p. 272.
31. ↑ Y. Shimokawa, Y. Fuwa, N. Aramaki. A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed. IEEE International Joint Conference on Neural Networks, 18–21 Listopada 1991. 3: pp. 2162–67.
32. ↑ K.P. Acken, M.J. Irwin, R.M. Owens. A Parallel ASIC Architecture for Efficient Fractal Image Coding. The Journal of VLSI Signal Processing, Lipiec 1998, 19(2):97–113(17)
33. ↑ Andrew B. Kahng. "Scoping the Problem of DFM in the Semiconductor Industry." University of California, San Diego. 21 czerwca 2004: "Future design for manufacturing (DFM) technology must reduce design [non-recoverable expenditure] cost and directly address manufacturing [non-recoverable expenditures] – the cost of a mask set and probe card – which is well over $1 million at the 90 nm technology node and creates a significant damper on semiconductor-based innovation."
34. ↑ ^{34,0 34,1} Patterson and Hennessy, p. 751.
35. ↑ Modern Processor Design: Fundamentals of Superscalar Processors. John Paul Shen, Mikko H. Lipasti. McGraw-Hill Professional, 2005. ISBN 0070570647. pp. 561: "However, the holy grail of such research - automated parallelization of serial programs - has yet to materialize. While automated parallelization of certain classes of algorithms has been demonstrated, such success has largely been limited to scientific and numeric applications with predictable flow control (e.g., nested loop structures with statically determined iteration counts) and statically analyzable memory access patterns. (e.g., walks over large multidimensional arrays of float-point data)."
36. ↑ Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. December 18, 2006. See table on pages 17-19
37. ↑ L.F. Menabrea, Sketch of the Analytic Engine Invented by Charles Babbage. Bibliothèque Universelle de Genève, 1842. Retrieved on November 7, 2007.
38. ↑ ^{38,0 38,1 38,2} Patterson and Hennessy, p. 753.
39. ↑ Frank da Cruz: Columbia University Computing History: The IBM 704. Columbia University, 2003. [dostęp 2008-01-08].
40. ↑ ^{40,0 40,1 40,2 40,3 40,4} The History of the Development of Parallel Computing. Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science, 1994. [dostęp 2008-01-08].
41. ↑ Gary Anthes: The Power of Parallelism. Computerworld, 2001-11-19. [dostęp 2008-01-08].
42. ↑ Patterson and Hennessy, p. 749.
43. ↑ Patterson and Hennessy, pp. 749–50: "Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the $8 million estimated in 1966 to $31 million by 1972, despite the construction of only a quarter of the planned machine ... It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976."

[edytuj] External links

• Szablon:Dmoz
• Lawrence Livermore National Laboratory: Introduction to Parallel Computing
• Designing and Building Parallel Programs, by Ian Foster
• Internet Parallel Computing Archive
• Parallel processing topic area at IEEE Distributed Computing Online
• Parallel Computing Works Free On-line Book
• Frontiers of Supercomputing Free On-line Book Covering topics like algorithms and industrial applications