Распределенные сети взаимодействия
Feb. 8th, 2014 10:46 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
codedotТак называемые жесткие комбинаторы принадлежат более узкому классу graph relabeling systems, чем graph rewriting systems, к которым относятся сети взаимодействия в общем случае. По научным меркам, они введены буквально вчера - в нулевых. По их поводу написано полторы статьи, а наивная реализация в современных FPGA/ASIC и для жестких комбинаторов не очень многообещающая, так как агенты одновременно служат и для вычисления и для хранения данных, что слишком затратно для FPGA/ASIC, где суммарный объем памяти регистров всегда на порядок, если не на два, меньше доступной на той же доске встроенной RAM. У последнего неизбежно оказывается бутылочное горлышко.
В определенной перспективе жесткие сети взаимодействия - логичное продолжение развития процессоров. Но на данном этапе этот подход кажется слишком далеким от практики, - возможно, им потребуется еще несколько лет побыть в академических кругах. Впрочем, коммерческие компании типа ARM и сами метят в ту же сторону. К сожалению, пока это только пресс-релизы и провалившиеся проекты, тем не менее, ключевые слова правильные - "clockless computation".
С точки зрения исследований, сети взаимодействия - гораздо более зрелое направление. Первые работы в эту стороны были в конце 80-ых, а первая система взаимодействия (Lamping) решала задачу оптимальной по Levy редукции, даже не называясь собственно системой взаимодействия (Lafont формализовал и обобщил такие системы уже пост-фактум). По данной теме доступны сотни статей, учебник (см. черновой перевод на русский язык соответствующей главы), монография, а также десятки различных программных реализаций, хотя большинство из них представляет собой лишь приложения к публикациям.
В отличие от жестких комбинаторов, сети взаимодействия в чистом виде неприменимы для архитектуры процессоров из-за необходимой перезаписи графов. Однако, возможен совсем другой подход.
Интернет позволяет передавать петабайты данных одновременно по тысячам разных каналов, когда как ни один из существующих суперкомпьютеров не может в одиночку добиться той же суммарной скорости в RAM. Можно посмотреть на интернет как на распределенную RAM. В связи с этим интересно было бы рассмотреть произвольные вычисления с использованием этой памяти.
Если пойти этим путем, естественным образом возникает проблема синхронизации. В случае BOINC она решается наличием серверов, проверяющих корректность работы. В случае Bitcoin проверка работы тривиальна и не отнимает у всех нод никакого существенного времени ценой дублирования десятков гигабайт информации на всех нодах. Заметим, что в обоих упомянутых случаях работа заранее выбрана так, что ее можно легко проверить, а также строго выполняется единая последовательность событий.
Если же мы хотели бы иметь децентрализованную вычислительную сеть для произвольной работы без требования единого timeline, то неизбежно возникают проблемы локальности и конфлюэнтости. К счастью, системы взаимодействия как раз и обладают последними двумя свойствами, давая возможность продолжать вычисления оптимальным образом без необходимости немедленной синхронизации.
В определенной перспективе жесткие сети взаимодействия - логичное продолжение развития процессоров. Но на данном этапе этот подход кажется слишком далеким от практики, - возможно, им потребуется еще несколько лет побыть в академических кругах. Впрочем, коммерческие компании типа ARM и сами метят в ту же сторону. К сожалению, пока это только пресс-релизы и провалившиеся проекты, тем не менее, ключевые слова правильные - "clockless computation".
С точки зрения исследований, сети взаимодействия - гораздо более зрелое направление. Первые работы в эту стороны были в конце 80-ых, а первая система взаимодействия (Lamping) решала задачу оптимальной по Levy редукции, даже не называясь собственно системой взаимодействия (Lafont формализовал и обобщил такие системы уже пост-фактум). По данной теме доступны сотни статей, учебник (см. черновой перевод на русский язык соответствующей главы), монография, а также десятки различных программных реализаций, хотя большинство из них представляет собой лишь приложения к публикациям.
В отличие от жестких комбинаторов, сети взаимодействия в чистом виде неприменимы для архитектуры процессоров из-за необходимой перезаписи графов. Однако, возможен совсем другой подход.
Интернет позволяет передавать петабайты данных одновременно по тысячам разных каналов, когда как ни один из существующих суперкомпьютеров не может в одиночку добиться той же суммарной скорости в RAM. Можно посмотреть на интернет как на распределенную RAM. В связи с этим интересно было бы рассмотреть произвольные вычисления с использованием этой памяти.
Если пойти этим путем, естественным образом возникает проблема синхронизации. В случае BOINC она решается наличием серверов, проверяющих корректность работы. В случае Bitcoin проверка работы тривиальна и не отнимает у всех нод никакого существенного времени ценой дублирования десятков гигабайт информации на всех нодах. Заметим, что в обоих упомянутых случаях работа заранее выбрана так, что ее можно легко проверить, а также строго выполняется единая последовательность событий.
Если же мы хотели бы иметь децентрализованную вычислительную сеть для произвольной работы без требования единого timeline, то неизбежно возникают проблемы локальности и конфлюэнтости. К счастью, системы взаимодействия как раз и обладают последними двумя свойствами, давая возможность продолжать вычисления оптимальным образом без необходимости немедленной синхронизации.
