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

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

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

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

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

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

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

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

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

Документы

  1. Домашняя страница Amorphous Computing
    Коллекция статей и ссылок в лаборатории искусственного интеллекта Массачусетского технологического института
  2. Аморфные вычисления (сообщения ACM, май 2000 г.)
    Обзорная статья, показывающая примеры из языка точки роста Кура, а также шаблоны, созданные из языка запуска правил Вайса.
  3. «Аморфные вычисления при наличии стохастических возмущений»
    Статья, посвященная исследованию способности компьютеров Amorphous справляться с неисправными компонентами.
  4. Слайды об аморфных вычислениях из доклада DARPA в 1998 г.
    Обзор идей и предложений по реализации
  5. Аморфные и сотовые вычисления PPT из лекции НАСА 2002 г.
    Практически то же, что и выше, в формате PPT
  6. Инфраструктура для инженерных разработок в сетях датчиков / исполнительных механизмов, Бил и Бахрах, 2006.
    Аморфный компьютерный язык под названием «Proto».
  7. Самовосстанавливающиеся топологические шаблоны Клемент, Нагпал.
    Алгоритмы самовосстановления и самоподдержания линии.
  8. Надежные методы аморфной синхронизации, Джошуа Грохов
    Способы индукции глобальной временной синхронизации.
  9. Программируемая самосборка: построение глобальной формы с использованием биологически вдохновленных локальных взаимодействий и математики оригами и Связанные слайды Нагпал докторская диссертация
    Язык для компиляции инструкций локального взаимодействия из высокоуровневого описания сложенной структуры, похожей на оригами.
  10. К программируемому материалу, Нагпал Связанные слайды
    Схема, аналогичная предыдущей статье
  11. Самовосстанавливающиеся структуры в аморфных вычислениях Цукер
    Методы обнаружения и поддержки топологий, вдохновленных биологической регенерацией.
  12. Устойчивое серийное исполнение на аморфных машинах[постоянная мертвая ссылка ], Магистерская работа Сазерленда
    Язык для запуска последовательных процессов на аморфных компьютерах
  13. Парадигмы структуры в аморфном компьютере, 1997 Coore, Nagpal, Weiss
    Приемы создания иерархического порядка в аморфных компьютерах.
  14. Организация глобальной системы координат из локальной информации на аморфном компьютере, 1999 Nagpal.
    Методы создания систем координат путем формирования градиента и анализа пределов точности.
  15. Аморфные вычисления: примеры, математика и теория, 2013 г. Ричард Старк.
    В этой статье представлено около 20 примеров, варьирующихся от простых до сложных, стандартные математические инструменты используются для доказательства теорем и вычисления ожидаемого поведения, определены и исследованы четыре стиля программирования, доказаны три результата невычислимости и вычислительные основы сложной динамической интеллектуальной системы. набросаны.