Аморфные вычисления

Аморфные вычисления относятся к вычислительным системам, которые используют очень большое количество идентичных параллельных процессоров, каждый из которых имеет ограниченную вычислительную способность и локальные взаимодействия. Термин аморфные вычисления был придуман в MIT в 1996 году в статье под названием «Манифест аморфных вычислений» Абельсона, Найта, Сассмана и др.

Примеры естественных аморфных вычислений можно найти во многих областях, таких как биология развития (развитие многоклеточных организмов из одной клетки), молекулярная биология (организация субклеточных компартментов и внутриклеточная сигнализация), нейронные сети и химическая инженерия (неравновесные системы). Изучение аморфных вычислений не зависит от оборудования — оно не связано с физическим субстратом (биологическим, электронным, нанотехнологическим и т. д.), а скорее с характеристикой аморфных алгоритмов как абстракций с целью как понимания существующих природных примеров, так и проектирования новых систем.

Аморфные компьютеры, как правило, обладают многими из следующих свойств:

• Реализовано с помощью избыточных, потенциально неисправных, массивно-параллельных устройств.
• Устройства с ограниченной памятью и вычислительными возможностями.
• Устройства асинхронные.
• Устройства, не имеющие априорных сведений о своем местоположении.
• Устройства взаимодействуют только локально.
• Демонстрируют эмерджентное или самоорганизующееся поведение (шаблоны или состояния, выходящие за рамки отдельного устройства).
• Устойчивость к отказам, особенно к случайным неисправностям устройства или нарушениям состояния.

Алгоритмы, инструменты и шаблоны

(Некоторые из этих алгоритмов не имеют известных названий. Если название неизвестно, дается описательное название.)

• "Фикианская коммуникация" . Устройства общаются, генерируя сообщения, которые распространяются через среду, в которой находятся устройства. Сила сообщения будет следовать закону обратных квадратов, как описано в законе диффузии Фика . Примеры такой коммуникации распространены в биологических и химических системах.
• "Link diffusive communication" (диффузионная связь по каналам связи) . Устройства взаимодействуют, распространяя сообщения по проводным линиям связи от устройства к устройству. В отличие от "фиковской связи", не обязательно существует диффузионная среда, в которой находятся устройства, и, таким образом, пространственное измерение не имеет значения, а закон Фика неприменим. Примеры можно найти в алгоритмах маршрутизации Интернета, таких как алгоритм диффузионного обновления . Большинство алгоритмов, описанных в литературе по аморфным вычислениям, предполагают этот тип связи.
• "Распространение волн" . (Ссылка 1) Устройство передает сообщение с закодированным числом переходов. Устройства, которые ранее не видели сообщение, увеличивают число переходов и повторно передают. Волна распространяется через среду, и число переходов через среду будет эффективно кодировать градиент расстояния от источника.
• «Случайный идентификатор» . Каждое устройство присваивает себе случайный идентификатор, причем случайное пространство должно быть достаточно большим, чтобы исключить дубликаты.
• «Программа точки роста» . (Кур). Процессы, которые перемещаются между устройствами в соответствии с «тропизмом» (перемещение организма под действием внешних раздражителей).
• "Волновые координаты" . Слайды DARPA PPT. Будет написано.
• «Запрос соседей» . (Nagpal) Устройство проверяет состояние своих соседей с помощью механизма push или pull.
• "Peer-pressure" (давление со стороны окружающих) . Каждое устройство поддерживает состояние и сообщает это состояние своим соседям. Каждое устройство использует некоторую схему голосования, чтобы определить, следует ли менять состояние на состояние соседа. Алгоритм разделяет пространство в соответствии с начальными распределениями и является примером алгоритма кластеризации. ^{[ необходима цитата ]}
• «Самоподдерживающаяся линия» . (Лорен Лорен, Клемент). Градиент создается из одной конечной точки на плоскости, покрытой устройствами, посредством Link Diffusive Communication. Каждое устройство знает свое значение в градиенте и идентификатор своего соседа, который находится ближе к началу градиента. Противоположная конечная точка обнаруживает градиент и сообщает своему ближайшему соседу, что он является частью линии. Это распространяется вверх по градиенту, образуя линию, которая устойчива к сбоям в поле. (Необходима иллюстрация).
• «Формирование клуба» . (Кур, Кур, Нагпал, Вайс). Локальные кластеры процессоров выбирают лидера, который будет служить локальным коммуникационным узлом.
• «Формирование координат» (Nagpal). Формируются множественные градиенты, которые используются для формирования системы координат посредством триангуляции.

Исследователи и лаборатории

• Хэл Абельсон , Массачусетский технологический институт
• Джейкоб Бил, аспирант Массачусетского технологического института (языки высокого уровня для аморфных вычислений)
• Дэниел Кур, Университет Вест-Индии (язык точек роста, тропизм, серия выращенных инверторов)
• Николаус Коррелл , Университет Колорадо ( робототехнические материалы )
• Том Найт , Массачусетский технологический институт (вычисления с использованием синтетической биологии)
• Радхика Нагпал, Гарвард (самоорганизующиеся системы)
• Зак Бут Симпсон, лаборатория Эллингтона, Техасский университет в Остине (детектор бактериальных краев)
• Джерри Сассман , Лаборатория искусственного интеллекта Массачусетского технологического института
• Рон Вайс, Массачусетский технологический институт (запуск правил, язык микробных колоний, формирование паттернов кишечной палочки)

Смотрите также

• Нетрадиционные вычисления

Документы

1. Домашняя страница Amorphous Computing

   Коллекция статей и ссылок в лаборатории ИИ Массачусетского технологического института

2. Аморфные вычисления (Сообщения ACM, май 2000 г.)

   Обзорная статья, демонстрирующая примеры из языка точек роста Кура, а также шаблоны, созданные на основе языка запуска правил Вайса.

3. «Аморфные вычисления при наличии стохастических возмущений»

   Статья, посвященная исследованию способности аморфных компьютеров справляться с отказавшими компонентами.

4. Аморфные вычисления. Слайды с выступления DARPA в 1998 году.

   Обзор идей и предложений по внедрению

5. Аморфные и клеточные вычисления PPT из лекции NASA 2002 года

   Почти то же самое, что и выше, в формате PPT

6. Инфраструктура для инженерных аварийных ситуаций на сетях датчиков/исполнительных механизмов, Бил и Бахрах, 2006.

   Аморфный язык вычислений под названием «Прото».

7. Самовосстанавливающиеся топологические паттерны Клемент, Нагпал.

   Алгоритмы самовосстановления и самообслуживания линии.

8. Надежные методы аморфной синхронизации, Джошуа Грохоу

   Методы индукции глобальной временной синхронизации.

9. Программируемая самосборка: построение глобальной формы с использованием биологически вдохновленных локальных взаимодействий и математики оригами и связанных слайдов. Кандидатская диссертация Нагпала

   Язык для составления инструкций локального взаимодействия из высокоуровневого описания складчатой ​​структуры, напоминающей оригами.

10. На пути к программируемому материалу, связанные слайды Nagpal

    Похожий план предыдущей статьи

11. Самовосстанавливающиеся структуры в аморфных вычислениях Цукер

    Методы обнаружения и поддержания топологий, вдохновленные биологической регенерацией.

12. Устойчивое последовательное выполнение на аморфных машинах ^{[ постоянная мертвая ссылка ]} , магистерская диссертация Сазерленда

    Язык для запуска последовательных процессов на аморфных компьютерах.

13. Парадигмы для структуры в аморфном компьютере, 1997 Кур, Нагпал, Вайс

    Методы создания иерархического порядка в аморфных компьютерах.

14. Организация глобальной системы координат на основе локальной информации на аморфном компьютере, 1999 Нагпал.

    Методы создания систем координат путем формирования градиента и анализа пределов точности.

15. Аморфные вычисления: примеры, математика и теория, 2013 г. В. Ричард Старк.

    В статье представлено около 20 примеров, варьирующихся от простых до сложных, для доказательства теорем и вычисления ожидаемого поведения используются стандартные математические инструменты, определяются и исследуются четыре стиля программирования, доказываются три результата о невычислимости и обрисовываются вычислительные основы сложной динамической интеллектуальной системы.