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

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

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

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

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

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

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

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

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

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

См. также

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

Документы

Домашняя страница аморфных вычислений
Сборник статей и ссылок в лаборатории искусственного интеллекта Массачусетского технологического института.
Аморфные вычисления (сообщения ACM, май 2000 г.)
Обзорная статья, показывающая примеры языка точки роста Кура, а также шаблоны, созданные на основе языка запуска правил Вайса.
«Аморфные вычисления при наличии стохастических возмущений»
Статья, исследующая способность аморфных компьютеров справляться с неисправными компонентами.
Слайды «Аморфные вычисления» из выступления DARPA в 1998 году
Обзор идей и предложений по реализации
PPT по аморфным и клеточным вычислениям из лекции НАСА 2002 г.
Почти то же самое, что и выше, в формате PPT.
Инфраструктура для инженерных сетей датчиков и исполнительных механизмов , Бил и Бахрах, 2006.
Аморфный компьютерный язык под названием «Прото».
Самовосстанавливающиеся топологические паттерны Клемент, Нагпал.
Алгоритмы самовосстанавливающейся и самообслуживающейся линии.
Робастные методы аморфной синхронизации , Джошуа Грочоу
Методы обеспечения глобальной временной синхронизации.
Программируемая самосборка: построение глобальной формы с использованием биологически обусловленных локальных взаимодействий, математики оригами и связанных с ней слайдов. Нагпал Кандидатская диссертация
Язык для компиляции инструкций локального взаимодействия на основе высокоуровневого описания сложенной структуры, похожей на оригами.
На пути к программируемому материалу , слайды, связанные с Нагпалом
Схема аналогична предыдущей статье
Самовосстанавливающиеся структуры в аморфных вычислениях Цукер
Методы обнаружения и поддержания топологий, основанных на биологической регенерации.
Устойчивое серийное исполнение на аморфных машинах ^{[ постоянная мертвая ссылка ]}, магистерская диссертация Сазерленда
Язык для запуска последовательных процессов на аморфных компьютерах.
Парадигмы структуры аморфного компьютера , 1997 Кур, Нагпал, Вайс
Методы создания иерархического порядка в аморфных компьютерах.
Организация глобальной системы координат на основе локальной информации на аморфном компьютере , 1999 г., Нагпал.
Методы создания систем координат путем формирования градиента и анализ пределов точности.
Аморфные вычисления: примеры, математика и теория , 2013 Ричард Старк.
В этой статье представлено около 20 примеров, от простых до сложных, для доказательства теорем и расчета ожидаемого поведения используются стандартные математические инструменты, идентифицируются и исследуются четыре стиля программирования, доказываются три результата невычислимости, а также вычислительные основы сложной динамической интеллектуальной системы. зарисованы.