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

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

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

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

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

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

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

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

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

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

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

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

Документы

1. Домашняя страница аморфных вычислений

   Сборник статей и ссылок в лаборатории искусственного интеллекта Массачусетского технологического института.

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

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

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

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

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

   Обзор идей и предложений по реализации

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

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

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

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

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

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

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

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

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

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

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

    Схема аналогична предыдущей статье

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

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

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

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

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

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

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

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

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

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