Obliczenia amorficzne - Amorphous computing

Obliczenia amorficzne odnoszą się do systemów obliczeniowych, które wykorzystują bardzo dużą liczbę identycznych, równoległych procesorów, z których każdy ma ograniczoną zdolność obliczeniową i lokalne interakcje. Termin Amorphous Computing został ukuty na MIT w 1996 roku w artykule zatytułowanym „Amorphous Computing Manifesto” autorstwa Abelsona, Knighta, Sussmana i in.

Przykłady naturalnie występujących obliczeń amorficznych można znaleźć w wielu dziedzinach, takich jak: biologia rozwoju (rozwój organizmów wielokomórkowych z pojedynczej komórki), biologia molekularna (organizacja przedziałów subkomórkowych i sygnalizacja wewnątrzkomórkowa), sieci neuronowe , i inżynieria chemiczna (układy nierównowagowe), żeby wymienić tylko kilka. Badanie obliczeń amorficznych jest agnostyczne względem sprzętu — nie dotyczy podłoża fizycznego (biologicznego, elektronicznego, nanotechnologicznego itp.), ale raczej charakteryzacji algorytmów amorficznych jako abstrakcji w celu zarówno zrozumienia istniejących naturalnych przykładów, jak i nowych systemów inżynieryjnych .

Komputery amorficzne mają zwykle wiele z następujących właściwości:

• Zaimplementowane przez nadmiarowe, potencjalnie wadliwe, masowo równoległe urządzenia.
• Urządzenia o ograniczonej pamięci i możliwościach obliczeniowych.
• Urządzenia są asynchroniczne.
• Urządzenia nie mające a priori wiedzy o swojej lokalizacji.
• Urządzenia komunikujące się tylko lokalnie.
• Wykazuj zachowania wyłaniające się lub samoorganizujące (wzorce lub stany większe niż pojedyncze urządzenie).
• Odporny na uszkodzenia, szczególnie w przypadku sporadycznie zniekształconych urządzeń lub zaburzeń stanu.

Algorytmy, narzędzia i wzorce

(Niektóre z tych algorytmów nie mają znanych nazw. Tam, gdzie nazwa nie jest znana, podaje się opisową.)

• „Komunikacja ficka” . Urządzenia komunikują się poprzez generowanie komunikatów, które rozchodzą się przez medium, w którym przebywają urządzenia. Siła wiadomości będzie zgodna z prawem odwrotnego kwadratu, opisanym przez prawo dyfuzji Ficka . Przykłady takiej komunikacji są powszechne w systemach biologicznych i chemicznych.
• „Połącz komunikację dyfuzyjną” . Urządzenia komunikują się poprzez propagację komunikatów w dół łączami przewodowymi z urządzenia do urządzenia. W przeciwieństwie do „komunikacji Ficka” niekoniecznie istnieje medium dyfuzyjne, w którym przebywają urządzenia, a zatem wymiar przestrzenny jest nieistotny, a prawo Ficka nie ma zastosowania. Przykłady można znaleźć w algorytmach routingu internetowego, takich jak algorytm Diffusing Update Algorithm . Większość algorytmów opisanych w literaturze amorficznej zakłada ten rodzaj komunikacji.
• „Propagacja fali” . (Odn. 1) Urządzenie emituje komunikat z zakodowaną liczbą przeskoków. Urządzenia, które wcześniej nie widziały komunikatu, zwiększają liczbę przeskoków i ponownie rozsyłają. Fala rozchodzi się w medium, a liczba przeskoków w medium skutecznie zakoduje gradient odległości od źródła.
• „Losowy identyfikator” . Każde urządzenie nadaje sobie losowy identyfikator, przy czym losowa przestrzeń jest wystarczająco duża, aby wykluczyć duplikaty.
• "Program punktu wzrostu" . (Coore). Procesy, które poruszają się między urządzeniami zgodnie z „tropizmem” (ruch organizmu pod wpływem bodźców zewnętrznych).
• "Współrzędne fali" . Prowadnice DARPA PPT . Do napisania.
• „Zapytanie o sąsiedztwo” . (Nagpal) Urządzenie próbkuje stan swoich sąsiadów za pomocą mechanizmu pchania lub ciągnięcia.
• „Nacisk rówieśników” . Każde urządzenie utrzymuje stan i przekazuje ten stan swoim sąsiadom. Każde urządzenie wykorzystuje pewien schemat głosowania, aby określić, czy zmienić stan na stan sąsiada. Algorytm dzieli przestrzeń zgodnie z rozkładami początkowymi i jest przykładem algorytmu grupowania.
• "Linia samoutrzymująca się" . ( Laura Lauren, Klemens ). Gradient jest tworzony z jednego punktu końcowego na płaszczyźnie pokrytej urządzeniami za pomocą Link Diffusive Communication. Każde urządzenie jest świadome swojej wartości w gradiencie oraz identyfikatora swojego sąsiada, który jest bliżej początku gradientu. Przeciwległy punkt końcowy wykrywa gradient i informuje swojego bliższego sąsiada, że ​​jest częścią linii. Powoduje to propagację gradientu, tworząc linię, która jest odporna na zakłócenia w polu. (Wymagana ilustracja).
• „Tworzenie klubu” . ( Coore, Coore, Nagpal, Weiss ). Lokalne klastry procesorów wybierają lidera, który służy jako lokalny węzeł komunikacyjny.
• „Tworzenie współrzędnych” ( Nagpal ). Tworzone są wielokrotne gradienty, które są wykorzystywane do tworzenia układu współrzędnych poprzez triangulację.

Naukowcy i laboratoria

• Hal Abelson , MIT
• Jacob Beal , doktorant MIT (języki wysokiego poziomu dla komputerów amorficznych)
• Daniel Coore , University of West Indies (język punktu wzrostu, tropizm, seria inwerterów uprawianych)
• Nikolaus Correll , University of Colorado ( materiały zrobotyzowane )
• Tom Knight , MIT (obliczenia z biologią syntetyczną)
• Radhika Nagpal , Harvard (systemy samoorganizujące się)
• Zack Booth Simpson , Ellington Lab, Univ. z Teksasu w Austin. (Bateryjny detektor krawędzi)
• Gerry Sussman , MIT AI Lab
• Ron Weiss , MIT (wyzwalanie reguł, język kolonii drobnoustrojów, tworzenie wzorców coli)

Dokumenty

1. Strona główna obliczeń amorficznych

   Zbiór artykułów i linków w laboratorium MIT AI

2. Obliczenia amorficzne (Komunikaty ACM, maj 2000)

   Artykuł przeglądowy pokazujący przykłady z języka Coore'a Growing Point Language, a także wzorce stworzone z języka wyzwalającego reguły Weissa.

3. „Obliczenia amorficzne w obecności zaburzeń stochastycznych”

   Artykuł badający zdolność komputerów amorficznych do radzenia sobie z uszkodzonymi komponentami.

4. Amorficzne slajdy komputerowe z wykładu DARPA w 1998 r.

   Przegląd pomysłów i propozycji wdrożeń

5. Obliczenia amorficzne i komórkowe PPT z 2002 r. Wykład NASA

   Prawie tak samo jak powyżej, w formacie PPT

6. Infrastruktura dla inżynierii pojawiania się w sieciach czujników/elementów wykonawczych , Beal i Bachrach, 2006.

   Amorficzny język obliczeniowy o nazwie „Proto”.

7. Samonaprawiające się wzorce topologiczne Clement, Nagpal.

   Algorytmy do samodzielnej naprawy i samoobsługi linii.

8. Solidne metody amorficznej synchronizacji , Joshua Grochow

   Metody wywoływania globalnej synchronizacji czasowej.

9. Programowalna samoorganizacja: konstruowanie globalnego kształtu za pomocą inspirowanych biologicznie lokalnych interakcji i matematyki origami i powiązanych slajdów Praca doktorska Nagpal

   Język do kompilowania instrukcji interakcji lokalnych z opisu wysokiego poziomu złożonej struktury przypominającej origami.

10. W kierunku materiału programowalnego , slajdy powiązane z Nagpal

    Podobny zarys do poprzedniego artykułu

11. Struktury samonaprawiające się w obliczeniach amorficznych Zucker

    Metody wykrywania i utrzymywania topologii inspirowanych odnową biologiczną.

12. Odporne seryjne wykonanie na maszynach amorficznych , Praca magisterska Sutherland

    Język do uruchamiania procesów szeregowych na komputerach amorficznych

13. Paradygmaty struktury w amorficznym komputerze , 1997 Coore, Nagpal, Weiss

    Techniki tworzenia porządku hierarchicznego w komputerach amorficznych.

14. Organizowanie globalnego układu współrzędnych na podstawie informacji lokalnych na komputerze amorficznym , 1999 Nagpal.

    Techniki tworzenia układów współrzędnych poprzez tworzenie gradientów i analizy granic dokładności.

15. Obliczenia amorficzne: przykłady, matematyka i teoria , 2013 W Richard Stark.

    W artykule przedstawiono prawie 20 przykładów, od prostych do złożonych, standardowe narzędzia matematyczne są używane do udowodnienia twierdzeń i obliczenia oczekiwanego zachowania, zidentyfikowano i zbadano cztery style programowania, udowodniono trzy wyniki nieobliczalności oraz podstawy obliczeniowe złożonego, dynamicznego systemu inteligencji są naszkicowane.