Amorfní výpočty - Amorphous computing

Amorfní výpočty označuje výpočetní systémy, které používají velmi velké množství identických paralelních procesorů, z nichž každý má omezené výpočetní schopnosti a místní interakce. Termín Amorphous Computing byl vytvořen na MIT v roce 1996 v příspěvku nazvaném „Amorfní výpočetní manifest“ Abelson, Knight, Sussman a kol.

Příklady přirozeně se vyskytujících amorfních výpočtů lze nalézt v mnoha oblastech, například: vývojová biologie (vývoj mnohobuněčných organismů z jedné buňky), molekulární biologie (organizace subcelulárních kompartmentů a intracelulární signalizace), neuronové sítě, a chemické inženýrství (nerovnovážné systémy), abychom jmenovali alespoň některé. Studium amorfního výpočtu je hardware agnostik—Nezajímá se o fyzický substrát (biologický, elektronický, nanotechnický atd.), Ale spíše o charakterizaci amorfních algoritmů jako abstrakcí s cílem jak porozumět existujícím přírodním příkladům, tak vytvářet nové systémy.

Amorfní počítače mívají mnoho z následujících vlastností:

  • Implementováno nadbytečnými, potenciálně vadnými, masivně paralelní zařízení.
  • Zařízení s omezenou pamětí a výpočetními schopnostmi.
  • Zařízení jsou asynchronní.
  • Zařízení s číslem a priori znalost jejich polohy.
  • Zařízení komunikující pouze lokálně.
  • Vykazují vznikající nebo samoorganizační chování (vzorce nebo stavy větší než u jednotlivých zařízení).
  • Odolný vůči chybám, zejména k příležitostně poškozenému zařízení nebo poruchám stavu.

Algoritmy, nástroje a vzory

(Některé z těchto algoritmů nemají žádná známá jména. Pokud název není znám, je uveden popisný název.)

  • „Fickianova komunikace“. Zařízení komunikují generováním zpráv, které difundují médiem, ve kterém zařízení sídlí. Síla zprávy se bude řídit zákonem inverzních čtverců, jak je popsáno v Fickův zákon difúze. Příklady takové komunikace jsou běžné v biologických a chemických systémech.
  • „Link diffusive communication“. Zařízení komunikují šířením zpráv dolů odkazy připojenými ze zařízení k zařízení. Na rozdíl od „Fickianovy komunikace“ nemusí nutně existovat difuzní médium, ve kterém zařízení přebývají, a tedy prostorová dimenze je irelevantní a Fickův zákon není použitelné. Příklady lze nalézt v internetových směrovacích algoritmech, jako je Difúzní aktualizační algoritmus. Většina algoritmů popsaných v amorfní počítačové literatuře předpokládá tento druh komunikace.
  • „Wave Propagation“. (Odkaz 1) Zařízení vydává zprávu s kódovaným počtem hopů. Zařízení, která předtím zprávu neviděla, zvyšují počet hopů a znovu vysílají. Vlna se šíří médiem a počet hopů v médiu bude účinně kódovat gradient vzdálenosti od zdroje.
  • „Náhodné ID“. Každé zařízení si dává náhodné ID, přičemž náhodný prostor je dostatečně velký, aby zabránil duplikátům.
  • „Program rostoucího bodu“. (Coore). Procesy, které se pohybují mezi zařízeními podle „tropismu“ (pohyb organismu v důsledku vnějších podnětů).
  • "Vlnové souřadnice". DARPA PPT diapozitivy. Bude napsáno.
  • „Sousední dotaz“. (Nagpal) Zařízení vzorkuje stav svých sousedů mechanismem push nebo pull.
  • „Vzájemný tlak“. Každé zařízení udržuje stav a komunikuje tento stav se svými sousedy. Každé zařízení používá určité hlasovací schéma k určení, zda se má změnit stav na stav souseda. Algoritmus rozděluje prostor podle počátečních distribucí a je příkladem shlukovacího algoritmu.[Citace je zapotřebí ]
  • "Samoúdržbová linka". (Lauren Lauren, Clement ). Přechod je vytvořen z jednoho koncového bodu v rovině pokryté zařízeními prostřednictvím Link Difúzní komunikace. Každé zařízení si je vědomo své hodnoty v přechodu a ID svého souseda, který je blíže počátku přechodu. Opačný koncový bod detekuje gradient a informuje svého bližšího souseda, že je součástí přímky. To se šíří nahoru gradientem a vytváří čáru, která je odolná proti přerušení v poli. (Ilustrace nutná).
  • "Klubová formace". (Coore, Coore, Nagpal, Weiss ). Místní klastry procesorů volí vedoucího, který bude sloužit jako místní komunikační uzel.
  • "Tvorba souřadnic" (Nagpal ). Vytvoří se více přechodů a použije se k vytvoření souřadného systému pomocí triangulace.

Výzkumníci a laboratoře

Dokumenty

  1. Domovská stránka Amorphous Computing
    Sbírka papírů a odkazů v laboratoři MIT AI
  2. Amorphous Computing (sdělení ACM, květen 2000)
    Přehledový článek ukazující příklady z Coore's Growing Point Language a vzory vytvořené z Weissova pravidla spouštějícího jazyk.
  3. „Amorfní výpočty za přítomnosti stochastických poruch“
    Článek zkoumající schopnost amorfních počítačů vypořádat se s vadnými součástmi.
  4. Amorphous Computing Slides z diskuse DARPA v roce 1998
    Přehled nápadů a návrhů na implementace
  5. Amorphous and Cellular Computing PPT z roku 2002 Přednáška NASA
    Téměř stejné jako výše, ve formátu PPT
  6. Infrastruktura pro technický vznik v sítích senzorů / akčních členů, Beal a Bachrach, 2006.
    Amorfní výpočetní jazyk zvaný „Proto“.
  7. Samopravné topologické vzory Clement, Nagpal.
    Algoritmy pro samoopravné a samoudržovací vedení.
  8. Robustní metody amorfní synchronizace Joshua Grochow
    Metody vyvolání globální časové synchronizace.
  9. Programovatelné samosestavování: Konstrukce globálního tvaru pomocí biologicky inspirovaných místních interakcí a matematiky Origami a Přidružené snímky Nagpal disertační práce
    Jazyk pro sestavení pokynů pro místní interakci z popisu na vysoké úrovni skládané struktury podobné origami.
  10. Směrem k programovatelnému materiálu Nagpal Přidružené snímky
    Obrys podobný předchozímu článku
  11. Samoléčivé struktury v amorfním výpočtu Zucker
    Metody detekce a udržování topologií inspirovaných biologickou regenerací.
  12. Odolné sériové provedení na amorfních strojích[trvalý mrtvý odkaz ], Sutherlandova diplomová práce
    Jazyk pro spouštění sériových procesů na amorfních počítačích
  13. Paradigmata pro strukturu v amorfním počítači 1997 Coore, Nagpal, Weiss
    Techniky pro vytváření hierarchického pořadí v amorfních počítačích.
  14. Organizace globálního souřadnicového systému z místních informací na amorfním počítači, 1999 Nagpal.
    Techniky vytváření souřadnicových systémů tvorbou gradientů a analýza přesných limitů.
  15. Amorfní výpočty: příklady, matematika a teorie, 2013 W Richard Stark.
    Tento článek představuje téměř 20 příkladů od jednoduchých po složité, standardní matematické nástroje se používají k prokázání vět a výpočtu očekávaného chování, jsou identifikovány a prozkoumány čtyři programovací styly, jsou prokázány tři výsledky nepočitatelnosti a výpočetní základy komplexního systému dynamické inteligence jsou načrtnuty.