무정형 컴퓨팅

아모르퍼스 컴퓨팅은 각각 제한된 연산 능력과 국소적 상호작용을 가진 매우 많은 수의 동일한 병렬 프로세서를 사용하는 연산 시스템을 말한다. 아모르퍼스 컴퓨팅(Amorphous Computing)이라는 용어는 1996년 MIT에서 아벨슨, 나이트, 서스만 등이 쓴 '아모르퍼스 컴퓨팅 매니페스토(Amorphous Computing Manifesto)'라는 제목의 논문에서 만들어졌다.

자연적으로 발생하는 비정형 연산의 예는 개발 생물학(단일 세포로부터 다세포 유기체의 개발), 분자 생물학(하위 세포 구획과 세포 내 신호의 조직), 신경 네트워크, 그리고 a의 이름을 붙이는 화학 공학(비균형 시스템)과 같은 여러 분야에서 찾아볼 수 있다. 거의. 비정형 연산에 대한 연구는 하드웨어 불가지론적이다. 물리적 기질(생물학, 전자, 나노테크 등)보다는 기존의 자연 사례와 공학적인 새로운 시스템을 이해하는 것을 목표로 추상화로서의 비정형 알고리즘의 특성화와 관련이 있다.

비정형 컴퓨터는 다음과 같은 속성을 많이 갖는 경향이 있다.

• 이중화, 잠재적으로 결함이 있는 대규모 병렬 장치에 의해 구현됨.
• 메모리 및 계산 능력이 제한된 장치.
• 비동기 장치.
• 위치에 대한 사전 지식이 없는 장치.
• 로컬로만 통신하는 장치.
• 비상 또는 자기 조직적 행동(개별 장치보다 큰 패턴 또는 상태)을 나타낸다.
• 특히 간헐적인 기형 장치 또는 상태 동요에 대한 내결함성.

알고리즘, 도구 및 패턴

(이러한 알고리즘 중 일부는 알려진 이름이 없다. 이름을 알 수 없는 경우에는 서술적인 이름이 주어진다.)

• "피키안 통신" 장치는 장치가 있는 매체를 통해 확산되는 메시지를 생성하여 통신한다. 메시지 강도는 Fick의 확산 법칙에 의해 설명되는 역제곱 법칙을 따를 것이다. 그러한 의사소통의 예는 생물학적, 화학적 시스템에서 흔히 볼 수 있다.
• "링크 분산 통신". 장치는 메시지를 장치에서 장치로 유선 연결로 전파하여 통신한다. '픽키안 통신'과 달리 장치가 상주하는 확산 매체가 반드시 있는 것은 아니므로 공간적 차원과 무관하며 픽의 법칙은 적용되지 않는다. 업데이트 알고리즘 확산과 같은 인터넷 라우팅 알고리즘에서 예를 찾아볼 수 있다. 비정형 컴퓨팅 문헌에 기술된 대부분의 알고리즘은 이러한 종류의 통신을 가정한다.
• "파형 전파"(참조 1) 장치는 암호화된 홉 카운트로 메시지를 방출한다. 이전에 메시지를 보지 못한 장치, 홉 수를 증가시키고 다시 브로드캐스트하는 장치. 파동은 매체를 통해 전파되며 매체를 가로지르는 홉 카운트는 효과적으로 소스로부터의 거리 구배를 인코딩할 것이다.
• "랜덤 ID". 각 장치는 무작위 ID를 부여하며, 무작위 공간은 중복되는 것을 방지하기에 충분하다.
• "성장 포인트 프로그램" (코어) '트로피즘'(외부 자극에 의한 유기체의 이동)에 따라 기기 사이에서 이동하는 과정.
• "파형 좌표" DARPA PPT 슬라이드. 쓸 것.
• "이웃의 문의"(Nagpal) 장치는 밀거나 당기는 메커니즘으로 이웃의 상태를 샘플링한다.
• "피어-압력" 각 장치는 상태를 유지하고 이 상태를 이웃에게 전달한다. 각 기기는 상태를 이웃의 상태로 변경할지 여부를 결정하기 위해 일부 투표 방식을 사용한다. 알고리즘은 초기 분포에 따라 공간을 분할하며 클러스터링 알고리즘의 예다.^{[citation needed]}
• "자신 유지 라인" (로렌 로렌, 클레멘트) 경사도는 Link Difflictive Communication을 통해 장치로 덮인 평면의 한 끝점에서 생성된다. 각 기기는 경사로의 값과 경사로의 원점에 더 가까운 이웃의 ID를 알고 있다. 반대쪽 끝점은 구배를 감지하고 더 가까운 이웃에게 선의 일부임을 알려준다. 이것은 현장의 붕괴에 강한 선을 형성하는 경사로를 상승시킨다. (경사로가 필요함).
• "Club Formation". (Coore, Coore ,Nagpal, Weiss). Local clusters of processors elect a leader to serve as a local communication hub.
• "Coordinate formation" (Nagpal). Multiple gradients are formed and used to form a coordinate system via triangulation.

Researchers and labs

• Hal Abelson, MIT
• Jacob Beal, graduate student MIT (high level languages for amorphous computing)
• Daniel Coore, University of West Indies (growing point language, tropism, grown inverter series)
• Nikolaus Correll, University of Colorado (robotic materials)
• Tom Knight, MIT (computation with synthetic biology)
• Radhika Nagpal, Harvard (self-organizing systems)
• Zack Booth Simpson, Ellington Lab, Univ. of Texas at Austin. (Bacterial edge detector)
• Gerry Sussman, MIT AI Lab
• Ron Weiss, MIT (rule triggering, microbial colony language, coli pattern formation)

Documents

1. The Amorphous Computing Home Page

   A collection of papers and links at the MIT AI lab

2. Amorphous Computing (Communications of the ACM, May 2000)

   A review article showing examples from Coore's Growing Point Language as well as patterns created from Weiss's rule triggering language.

3. "Amorphous computing in the presence of stochastic disturbances"

   A paper investigating the ability of Amorphous computers to deal with failing components.

4. Amorphous Computing Slides from DARPA talk in 1998

   An overview of ideas and proposals for implementations

5. Amorphous and Cellular Computing PPT from 2002 NASA Lecture

   Almost the same as above, in PPT format

6. Infrastructure for Engineered Emergence on Sensor/Actuator Networks, Beal and Bachrach, 2006.

   An amorphous computing language called "Proto".

7. Self-repairing Topological Patterns Clement, Nagpal.

   Algorithms for self-repairing and self-maintaining line.

8. Robust Methods of Amorphous Synchronization, Joshua Grochow

   Methods for inducing global temporal synchronization.

9. Programmable Self-Assembly: Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics and Associated Slides Nagpal PhD Thesis

   A language to compile local-interaction instructions from a high-level description of an origami-like folded structure.

10. Nagpal Associated 슬라이드, 프로그램 가능한 재료로 이동

    이전 논문과 유사한 개요

11. 비정형 컴퓨팅 주커의 자가 치유 구조

    생물학적 재생에서 영감을 받은 토폴로지를 탐지하고 유지하는 방법.

12. 서덜랜드 마스터스 논문, 비정형 기계에서의^{[permanent dead link]} 복원력 있는 직렬 실행

    비정형 컴퓨터에서 직렬 프로세스를 실행하는 언어

13. 비정형 컴퓨터의 구조 패러다임, 1997 Coore, Nagpal, Weiss

    비정형 컴퓨터에서 계층적 순서를 만드는 기술.

14. 무정형 컴퓨터에 대한 지역 정보로부터 글로벌 좌표계를 조직한 1999년 나팔.

    구배 형성에 의한 좌표계 생성 기법 및 정밀 한계 분석.

15. 무정형 컴퓨팅: 예시, 수학 및 이론, 2013 W 리처드 스타크.

    이 논문은 단순함에서 복잡함까지 다양한 20가지 예를 제시하며, 표준 수학 도구를 사용하여 이론과 예상된 행동을 계산하고, 4가지 프로그래밍 스타일을 식별하여 탐구하고, 3가지 비적합성 결과를 입증하며, 복잡하고 역동적인 지능 시스템의 연산 기반을 스케치한다.