Русский
Русский
English
Статистика
Реклама

Распределенные вычисления

Распределенное обучение и вычисления в сети. Доклад Яндекса

28.10.2020 14:12:50 | Автор: admin
Все эксперты по сетям знакомы с принципом end-to-end, когда специфичные для конкретной задачи фичи реализовываются на конечных нодах, а промежуточные ноды должны только передавать данные, не взаимодействуя с ними. Но есть случаи, когда полезны вычисления внутри сети с использованием устройств сети, занятых передачей трафика. Один из примеров таких задач распределенный ML. В докладе Дмитрий Афанасьев дал краткое введение в особенности вычислений для распределенного ML, паттерны обмена данными и коллективные операции. Вторая половина доклада о том, как редукция увеличивает производительность при обучении, и о некоторых реализациях.

Меня зовут Дмитрий Афанасьев, я сетевой архитектор Яндекса. И я сегодня расскажу про достаточно экзотические по крайней мере пока технологии. Но думаю, что они будут становиться менее экзотическими, и шансы с ними встретиться возрастают.


Итак, распределенное обучение для machine learning и вычисления в сети. Что я хочу рассказать? Сначала очень быстрое введение про то, что вообще такое нейросети, как они устроены, какие у них есть режимы функционирования и как они обучаются. Дальше специфика распределенного обучения, как устроен трафик при распределенном обучении и как он может ложиться на топологию сети Compute Implementations.

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

В пакетных и IP-сетях мы привыкли руководствоваться e2e-принципом. И говорим, что всю функциональность желательно реализовывать на endpoint, а сеть, которая посередине, должна быть быстрой, простой, дешевой и достаточно тупой, и заниматься только передачей данных, не вмешиваясь в процесс их обработки.

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

Дальше мы посмотрим, как устроены сами задачи и что в них такое происходит с вычислениями, что можно внести много пользы, добавив вычисления в сети.

Кратко о нейросетях


Итак, что такое нейросети? Слева на картинке у нас биологический нейрон с кучей своих запчастей. Справа у нас его математический аналог. Устроен просто. У него есть входы, на которые поступают какие-то сигналы. У этих входов есть веса. И еще есть смещение.

Ссылка со слайда

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

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

Ссылка со слайда

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


Из таких нейронов мы собираем собственно нейронную сеть. У нее есть входной уровень, который ничего не делает, это точки, в которые поступают какие-то входы. Дальше идут один или несколько слоев, которые производят обработку. Слои, которые не являются ни входными, ни выходными, мы называем скрытыми.


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

Ссылка со слайда

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

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

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

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

То есть мы прогоняем прямой путь, получаем результат. Смотрим на ошибку, на отклонение от того, что должно было получиться. И распространяем эту ошибку в обратном направлении по сети, чтобы скорректировать коэффициенты и уменьшить ошибку.


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


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

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

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

А когда мы проходим через весь набор входных семплов, это называется эпохой обучения, и дальше начинаем прогонять весь набор по новой.


Чтобы вычислить градиент после того, как мы прогнали вычисления в прямом направлении, мы идем обратно по сети. Не будем смотреть уравнения детально, но это действительно обратное распространение, то есть эффективный метод расчета учитывает структуру сети.



Этот эффективный метод расчета называется алгоритмом обратного распространения или backpropagation algorithm.


Он значительно эффективнее, чем если бы мы пытались считать градиент грубой силой за счет того, что он учитывает структуру сети и использует расчеты, которые были сделаны на разных этапах.


Процесс можно представить как состоящий из следующих потоков распространения данных и прохождения вычислений. Здесь прямое распространение вычислений через сеть.


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


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

Распределенное обучение глубоких сетей: структура вычислений и потоки трафика

Основано на туториале Fundamentals of Scaling Out DL Training Паулиуса Мицикевичуса (Nvidia) на симпозиуме HotChips

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


Мы стартуем со случайно инициализированными весами и итерируем наши данные по minibatch за проход в прямом направлении, затем в обратном направлении и апдейтим веса.

Как я уже говорил, сейчас нас интересует обучение, потому что inference более простая задача, в ней меньше вычислений, и не возникает таких больших объемов передачи данных.


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

Если minibatch имеет размер больше единицы, то входом становится уже не вектор, а матрица. И каждый промежуточный результат тоже является матрицей. На практике так обычно и происходит, и, более того, это эффективно, потому что GPU заточен на работу с матрицами.


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


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


Когда мы вычислили потери, то начинаем проходить в обратном направлении по сети, и задача этого прохода посчитать модификаторы, апдейт для весов и смещения всех нейронов сети.

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


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


Мы идем обратно по сети и вычисляем апдейты весов. Это шаг оптимизации. На входе у него текущие веса и градиенты весов. На выходе новые модифицированные веса. Операция состоит в том, что мы обновляем каждый вес с учетом соответствующего значения градиента. На практике вычисления могут быть несколько более сложными, но сама структура вычислений и структура обмена данными меняется не сильно.

Важно, что оптимизации могут использовать значительно больше памяти, чем сама модель. Особенно методы, которые хранят дополнительное состояние, например момент. Это связано с желанием улучшить входимость и уменьшить, например, застревание градиентного спуска на каких-то участках.


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

Наконец, мы берем матрицу весов, добавляем к ней матрицу апдейтов весов и получаем новые веса.

Важно, что эти вычисления можно распараллеливать, потому что, вообще говоря, вычислительная задача обучения нейросети сложная, в ней очень много вычислений. Один из способов как-то ускорить процесс распараллеливать, потому что иначе обучение некоторых сетей может занимать недели или месяцы, что очень печально. Хочется быстрее. Как можно параллелить? По-разному.


Один из методов Data Parallel, другой Model Parallel. Внутри модельного параллелизма можно еще делать параллелизм внутри уровней и между уровнями.

Data Parallel это когда мы разным нодам в сети отдаем вычисления на разных входных данных. То есть мы действительно разбиваем данные и считаем на разных нодах результат для разных сэмплов.

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

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


Что происходит при распараллеливании по данным? Каждый worker получает полную копию всей нейросети и отвечает за вычисления только на части данных. На прямом проходе он считает входные активации для своей части minibatch, и никаких коммуникаций не происходит.

А вот на обратном проходе появляются коммуникации, потому что мы считаем градиенты и активации для своей части minibatch, и мы считаем вклад для градиентов весов на основании своей порции minibatch, после чего все workers должны просуммировать свои вклады в апдейт весов. То есть каждый worker считает только свою долю. Чтобы посчитать истинную модификацию весов на этом minibatch, нужно просуммировать или редуцировать результат всех workers.


Как это будет выглядеть в разбивке на ноды по разным workers? Вот иллюстрация. Они все работают с одной и той же матрицей весов, но с разными входными данными.

На обратном проходе они тоже работают с разными данными, потом это все нужно собрать.


Здесь мы подходим к самому интересному к коммуникациям. Основная операция, которую мы здесь видим, так называемый Allreduce. Это очень типовая операция в суперкомпьютерных вычислениях. В мире суперкомпьютеров так называемые групповые или коллективные операции очень типовые, с ними все знакомы. Но за пределами этого мира они достаточно малоизвестны.

Allreduce одна из самых популярных из них. Ее смысл в том, что мы сначала редуцируем или собираем вместе, в данном случае суммируем промежуточные результаты с каждой ноды, а потом на все ноды распространяем получившийся результат.


Есть довольно много способов реализовать Allreduce. Эти способы имеют разные затраты по трафику, разные структуры обмена данными. Хуже всего наивный способ. Это когда каждый worker просто отдает свои результаты всем остальным, и каждый сам выполняет все суммирование. Никто так не делает.

К эффективным методам относятся кольцевые редукции чуть позже покажу, как они выглядят и так называемые One-shot reduction, то есть редукции за один проход, которые обычно используются в типологиях с коммутаторами, где все ноды видят других достижимых, хоть и не обязательно через один ход. Такие типы редукции могут использовать иерархические оптимизации.


Есть довольно большой коммуникационный overhead, который растет вместе со степенью параллелизма. И есть способы его оптимизации, на которые мы дальше посмотрим.


Что касается модельного параллелизма внутри уровня и между уровнями, я просто привожу картинки о том, как это устроено с точки зрения разделения задач. Но мы не будем в них углубляться.


Почему важно оптимизировать коммуникации между нодами? Это графики, снятые с тестового кластера с тестовой нагрузкой. Синее GPU power, то есть энергопотребление GPU, которое является довольно хорошим индикатором того, насколько занят GPU и насколько он активно считает.

Другой график обмен данными. Здесь видно, что наш дорогущий GPU простаивает, пока идет обмен и синхронизация данных. В жизни очень хотелось бы минимизировать этот простой.


Потоки трафика и интерконнекты


Как устроены потоки трафика и как они связаны с интерконнектами? Небольшое напоминание про коллективные или групповые операции, какие они бывают.

Ссылка со слайда

Бывают операции broadcast, когда один набор данных раздается всем. Бывает scatter, когда есть набор данных, и мы по кусочку раздаем его остальным нодам. Gather строго обратное, собираем данные вместе по кусочкам.

И reduction, когда мы собираем куски и вычисляем из них что-то новое. Например, суммируем. Хотя редукция не обязана быть суммированием, в случае нейросети она является суммированием. Важная свойство редукции то, что размер блока данных после редукции не меняется. То есть мы собрали по вектору какой-то размерности с каждой ноды, просуммировали, получилось не в n раз больше, а столько же данных, но в которых уже учтены промежуточных результаты.

Ссылка со слайда

Как я уже говорил, наивная реализация One-shot reduction за один проход не эффективна.

Ссылка со слайда

Есть другие реализации, например так называемый кольцевой Allreduce.


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


В итоге каждая нода получает свою завершенную часть результата.


И потом реплицирует на все остальные.

Ссылка со слайда

Если представить, что кольца могут быть ориентированы по разным осям, то этот способ также может быть иерархическим. И такая конструкция очень хорошо ложится на типологию классических интерконнектов.


Потому что с чем мы обычно сталкиваемся в IP-сетях? IP сети, которые мы строим, всё это коммутируемые или indirect-сети. Ноды в них подключены не напрямую к другим нодам, если мы говорим про вычислительные ноды, а к коммутаторам. И только через них видят другие ноды.

А есть еще интерконнекты/сети, которые называются прямыми, direct, или же point-to-point. Это когда в одной ноде совмещены и линки для коммуникации с соседями, и вычислительные элементы. Многие суперкомпьютерные сети и многие кластеры для high performance-компьютинга исторически так и выглядят. Это неспроста.

Ссылка со слайда

Дело в том, что многие коллективные операции очень хорошо ложатся на такую топологию интерконнекта. Если мы говорим конкретно про машинное обучение, то например, Google, как известно, делает свои тензорные процессоры для машинного обучения. А еще он делает на них кластеры. И в этих кластерах топология как раз 2-D torus, что позволяет кольцевой Allreduce непосредственно отобразить на топологию этого кластера.

Ссылка со слайда

Но конечно, не все могут делать свои акселераторы и специализированные интерконнекты для них. Что же можно сделать? А если бы свитчи тоже умели что-то считать?

Реализация вычислений внутри сетей


Итак, вычисление в сетях на сетевых элементах.

Ссылка со слайда

Мы посмотрим на две реализации. Первая SHARP, Scalable Hierarchical Aggregation and Reduction Protocol. Это реализация вычислений в сети от компании Mellanox, теперь Nvidia.


И это production ready-реализация. Она оптимизирует все ту же задачу расчета редукций. Один из способов такого расчета построение дерева, по которому могут идти редукции. Это логическое дерево. Оно отображается на топологию сети. Если мы говорим про индиректную или switched-сеть, то отображаться оно может довольно неудачно. Например, вызывая перегрузку на определенных линках.


Пример одной из реализации Allreduce Recursive Doubling. Он происходит в несколько этапов.


Что делает SHARP? Во-первых, SHARP основан на том, что внутри коммутаторов, в данном случае это InfiniBand-коммутаторы, реально есть логические устройства, которые могут что-то считать. Считать им нужно не так много, в данном случае достаточно суммировать. Но они могут работать со всеми популярными типами данных, которые нужны в HPC и в машинном обучении.

В случае с SHARP у нас также строится дерево агрегации, это логическое дерево, наложенное на физическую топологию сети.


Что происходит? У нод появляются промежуточные расчеты данных. Они отсылают эти данные по дереву, и при распространении вверх по этому дереву происходит редукция. У нас есть switch снизу. Ему несколько нод присылают свои данные для редукции. Он редуцирует эти наборы данных до одного.

Мы получили пачку векторов от разных нод, например, при расчетах для машинного обучения. Просуммировали эти вектора, наверх ушел один вектор. То есть данные уменьшились в размере.

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

И поскольку здесь речь идет об InfiniBand, у которого надежный транспорт, и есть реализация надежного мультикаста, это очень эффективная операция. Этот номер не прошел бы так легко в произвольной пакетной сети, где есть потери. Нам пришлось бы подставлять некоторое количество подпорок. Но в случае с InfiniBand это работает очень неплохо.


Дело даже не в том, что свитчи очень эффективно считают. Они делают простую операцию суммируют, просто находятся в правильном месте, чтобы это считать, потому что раз мы просуммировали векторы внутри свитча, дальше уходит меньше данных.

То есть мы не просто сделали полезную работу, выполнив операцию редукции. Мы еще и значительно уменьшили объем передаваемых дальше данных.


На графике видно, как использование SHARP влияет на использование операции Allreduce. Влияет не только на полосу, а еще и на Latency. Видно, что Latency остается примерно постоянной. Конечно, на самом деле нет. Latency является логарифмической. Потому что если посмотреть на то, что было здесь, это на самом деле подмножество внутри сети. И Latency при использовании SHARP зависит в основном от количества уровней сети, а не от количества нод, принимающих участие в вычислениях.

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


Но улучшается не только полоса и задержка.

Есть данные тестов с обучением различных нейросетей. В зависимости от того, какие модели мы обучаем, сколько нод в кластере, и от другой специфики, есть выигрыш от единиц процентов до весьма заметных 10-16% на некоторых моделях.

Это очень много с учетом того, какими цифровыми молотилками являются современные GPU и как соотносится стоимость самой вычислительной части нод GPU со стоимостью интерконнекта. 10% роста производительности могут пару раз окупить весь интерконнект.

SwitchML

sands.kaust.edu.sa/project/switchml

И еще одна реализация. Она не production ready, но куда более доступна, потому что подразумевает менее экзотическое оборудование.

То есть в исследовательских целях она более доступна, и, вообще, больше шансов до нее добраться, даже если у вас нет большого кластера. Это SwitchML.


Та же проблема распределенное обучение, Data Parallel, worker посчитали свои промежуточные результаты.


Их нужно собрать вместе, и мы хотим сделать это эффективнее.


И хотим сделать это на switch.


На чем это можно было бы сделать? Тут мы вспоминаем, что у нас есть программируемые чипы от компании Barefoot, теперь Intel. У них нет поддержки операций с плавающей запятой и продвинутой арифметики, но в целом с числами они работать умеют. Выясняется, что на этом тоже можно собрать конструкцию для редукции в сети.


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

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


Подробно вдаваться не будем. У нас есть данные с плавающей точкой. У них разные порядки. Мы хотим это все привести к целочисленному представлению, и желательно, чтобы они по масштабу были более-менее вместе, чтобы не было сильно различающихся масштабов данных. Это делается на worker.


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

Switch при помощи bitmap отслеживают, какие worker уже прислали свои данные для данного слота вычислений.


Собрана вся эта конструкция с использованием такого знатного зоопарка технологий. Но в то же время реализована поддержка для различных фреймворков машинного обучения.



Это тестовый кластер, на котором производились эксперименты.


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


Из экспериментов видно, что производительность не очень зависит от количества workers, в отличие от реализаций, не использующих вычисления на switch.


SwithML достаточно неплохо себя ведет при разумных значениях количества потерь. 1% для типовой сети это уже как-то очень много. Меньше 0,1% это то, на что можно ориентироваться. Даже 0,1% много в контролируемой среде.


И, наконец, чуть подробнее о том, как реализована устойчивость относительно потерь пакетов. На этапе агрегации мы игнорируем дублирующиеся данные, ждем того, что не пришло. И на этапе распространения результатов мы отсылаем результат. Если worker не получил результат, он его перезапрашивает. Система устойчива к потерям в обоих направлениях.

Ссылка со слайда

И про SHARP, и про SwitchML есть статьи и презентации. Они в открытом доступе, их можно посмотреть.
Подробнее..

Неочевидные сложности CRDT

12.05.2021 16:20:09 | Автор: admin


Мы все так привыкли к облачной синхронизации Dropbox и совместному редактированию в Google Docs, что объединение результатов действий разных пользователей может казаться давно решённой проблемой. Но на самом деле в этом вопросе остаётся множество подводных камней, а работа над алгоритмами CRDT вовсю продолжается.


Один из людей, ведущих эту работу Мартин Клеппманн (Martin Kleppmann): исследователь в Кембриджском университете и создатель популярной библиотеки Automerge. И на конференции Hydra он рассказывал о нескольких вещах, которые исследовал буквально в последнюю пару лет. Какие действия пользователя могут заставить Google Drive выдать unknown error? Почему в CRDT метаданные о работе над документов могут занимать в сто раз больше места, чем сам документ, и как с этим бороться? А у какой проблемы сейчас даже не существует известного решения?


Обо всём этом он поведал в докладе, а теперь мы сделали для Хабра текстовый перевод. Видео и перевод под катом, далее повествование будет от лица спикера.



Содержание доклада



Сегодня я хотел бы рассказать вам о CRDT (Conflict-free Replicated Data Types, бесконфликтные реплицированные типы данных). Вначале мы вкратце выясним, что же это такое и зачем они нам нужны, но в основном будет новый материал на основе исследований, которые мы проводили последний год или два. Возможно, вы читали мою книгу. Но сегодня речь пойдёт о ПО для совместной работы (collaborative software).


ПО для совместной работы


С помощью такого ПО несколько пользователей могут участвовать в редактировании и обновлении общего документа, файла, базы данных или какого-либо другого состояния. Примеров такого ПО много. С помощью Google Docs или Office 365 можно совместно редактировать текстовые документы. Среди графических приложений ту же функциональность даёт Figma. Trello позволяет пользователям давать друг другу задания, комментировать их и тому подобное. Общим у всех этих приложений является то, что в них пользователи могут параллельно обновлять данные.


В качестве примера рассмотрю редактирование текста (но те же механизмы работают для довольно широкого спектра приложений).


В редакторе текста для совместной работы два пользователя могут почти одновременно внести изменения в документ, при этом не видя изменений друг друга. Предположим, есть документ, состоящий из слова Hello!. Красный пользователь добавляет перед восклицательным знаком слово World, а параллельно с ним синий пользователь добавляет после восклицательного знака смайлик:



Необходимо обеспечить, чтобы при подключении к сети документ обоих пользователей пришёл к одинаковому состоянию, отражающему все внесённые изменения. В нашем случае документ будет выглядеть так: Hello World! :-).


Алгоритмы для параллельного редактирования документов


Для обеспечения подобного параллельного редактирования было разработано множество алгоритмов. Расхождения между версиями документа могут возникнуть, даже когда оба пользователя в онлайне, если они редактируют документ одновременно. А когда работа идёт в офлайне, расхождений будет ещё больше. Представьте, сколько изменений накапливается после нескольких часов редактирования текста. При такой работе постоянно происходят ветвления и слияния вариантов документа, как в системе контроля версий вроде Git. Как правило, системы для совместной работы должны выполнять разрешение конфликтов автоматически, чтобы это не приходилось делать вручную.


На самом общем уровне можно различить два вида алгоритмов, обеспечивающих параллельное редактирование документов:


  • Давно существует семейство алгоритмов операционального преобразования (operational transformation, OT), используемых в Google Docs и многих других современных приложениях.
  • А примерно 15 лет назад появился более новый вид: CRDT.

Оба вида алгоритмов решают примерно одну и ту же проблему, но существенно разными способами.


Рассмотрим вкратце механизм работы операционального преобразования. Предположим, существует документ, состоящий из букв Helo, к которому есть доступ у двух пользователей. Один пользователь добавляет в документ вторую букву l, а другой восклицательный знак. Теперь необходимо объединить эти версии документа:



При операциональном преобразовании каждое изменение записывается как операция. Операция это добавление или удаление символа в документе. Поэтому необходим способ указать, где именно произошло это изменение. В операциональном преобразовании для этого используется индекс символа. В случае нашего документа индекс новой l 3, а восклицательного знака 4.


В какой-то момент пользователи обмениваются изменениями через сервер. Второй пользователь узнаёт, что по индексу 3 необходимо вставить букву l, и получает необходимый результат. Но в случае с первым пользователем всё несколько менее очевидно. Если просто добавить восклицательный знак по индексу 4, то получится Hell!o, поскольку первый пользователь до этого добавил новый символ по индексу 3, и из-за этого индексы всех последующих символов увеличились на единицу. Поэтому индекс 4 необходимо преобразовать в индекс 5. Отсюда название алгоритма операциональное преобразование. И отсюда же главная сложность с ним.


Большинство алгоритмов операционального преобразования исходят из предположения о том, что все взаимодействия выполняются через единый сервер. Даже если пользователи сидят в одной комнате и могли бы передать друг другу свои версии по Bluetooth, им всё равно нужно связаться с сервером (который в случае Google Docs предоставляет им Google). Этот алгоритм правилен только в том случае, если все изменения упорядочены одним сервером. А следовательно, любые другие каналы обмена информацией не допускаются, даже если технически доступны будь то Bluetooth, P2P или банальная флешка.



В алгоритмах CRDT не делается подобных предположений о топологии сети. Для них не требуется, чтобы вся связь шла через единый центр. Как следствие, такие алгоритмы более надёжные, и они работают для большего числа систем. Многие приложения, которые нельзя было реализовать с операциональным преобразованием, оказываются возможными с CRDT.


Сходимость


Алгоритмы CRDT и операционального преобразования гарантируют сходимость. Это означает, что если два пользователя видели один и тот же набор операций, то их документы должны быть в одном состоянии, даже если они получили эти операции в разном порядке. Это обязательное требование для согласованности; если оно не выполнено, версии пользователей не окажутся согласованы.


Но одной только сходимости недостаточно. Она лишь гарантирует, что состояние у пользователей одинаковое, но каким именно будет это состояние неизвестно. Ниже мы с вами рассмотрим несколько примеров, когда состояние у пользователей одинаковое, причем одинаково неправильное.


Помимо сходимости, нужны способы убедиться, что наше итоговое состояние именно то, которое нужно. Определить их бывает непросто, поскольку они зависят от нашего интуитивного представления о том, что именно будет желаемым результатом, а что нет. Мы ещё увидим это на примерах. В общем, поработав несколько лет с CRDT, я пришёл к выводу, что базовую реализацию такого алгоритма сделать легко, но наломать дров в реализации ещё проще. Мы с вами рассмотрим способы обойти эти проблемы и реализовать CRDT лучше привычных подходов.


Хочу привести четыре примера конкретных проблем. Первый:


Аномалии чередования в текстовых редакторах для совместной работы


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


Я уже говорил, что алгоритмы операционального преобразования используют индекс символа. Алгоритмы CRDT же индексами не пользуются; вместо этого они присваивают каждому символу документа уникальный идентификатор. Механизмы генерации таких идентификаторов используются разные. Часто это делают с помощью дробей. Предположим, каждый символ у нас представлен числом от 0 до 1, где 0 начало документа, а 1 окончание. В примере с документом Helo позицию первого символа будет представлять число 0.2, второго 0.4, третьего 0.6, четвёртого 0.8.


Тогда при добавлении второй буквы l между первой l и o этому новому символу будет присвоено значение от 0.6 до 0.8 например, 0.7. Подобным же образом восклицательному знаку присваивается значение 0.9.



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


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


Звучит разумно. К сожалению, у этого подхода есть существенный недостаток. Рассмотрим пример на слайде.



У нас есть документ Hello!. Один пользователь добавил Alice перед восклицательным знаком, второй пользователь добавил Charlie. Но в результате слияния этих изменений мы получили нечто совершенно непонятное. Почему это произошло? Чтобы разобраться, взглянем на схему, представленную на следующем слайде.



В первоначальном документе символу o соответствует цифра 0.64, а восклицательному знаку 0.95. Первый пользователь добавил несколько символов между этими двумя, и новым символам были присвоены значения от 0.64 и до 0.95. Параллельно этому второй пользователь добавил свои символы на той же позиции, и им были присвоены цифры в том же диапазоне.


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


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


Мы рассмотрели несколько существующих алгоритмов CRDT для текста на предмет чередования, результаты этого сравнения представлены на следующем слайде.



Проблему чередования мы нашли как минимум в двух алгоритмах Logoot и LSEQ. Из-за особенностей этих алгоритмов простого способа решить эту проблему для них нет. Нам не удалось улучшить их в этом отношении, не изменив при этом фундаментально самих алгоритмов. В Treedoc и WOOT мы этой проблемы не нашли, но, к сожалению, эти алгоритмы наименее эффективные. Собственно говоря, главной причиной, по которой был создан LSEQ, было достижение большей производительности по сравнению с Treedoc и WOOT. Возвращаться к этим неэффективным алгоритмам не хотелось бы. Далее, Astrong не алгоритм, а спецификация, формализующая требования к алгоритмам редактирования текста. К сожалению, она также допускает чередование.


RGA


Отдельный случай алгоритм RGA. Непосредственно той проблемы, о которой я сейчас говорил, там нет, зато есть другая, правда, менее существенная. Попробуем вкратце её рассмотреть.



На слайде представлен пример, в котором один пользователь добавляет слово reader между Hello и !, затем возвращает курсор к позиции непосредственно перед reader и добавляет dear. Здесь очень важно именно перемещение курсора. Второй пользователь только добавляет Alice между Hello и !. При действии алгоритма RGA возможным результатом этих операций будет чередование слов: Hello dear Alice reader!. Это тоже нежелательно, хоть и лучше, чем чередование символов.


Давайте разберёмся, почему это происходит. RGA использует структуру, показанную на слайде.



В ней текст представлен в виде очень глубокого дерева, в котором родителем каждого символа является предшествующий на момент добавления символ. Счёт идёт от положения курсора на момент ввода символа. Исходный текст Hello!. Затем у нас есть три случая перемещения курсора перед написанием reader, Alice и dear. В такой ситуации алгоритм RDA генерирует один из трёх возможных результатов, перечисленных на слайде. Из них второй, на мой взгляд, является нежелательным, поскольку в нём происходит чередование слов разных пользователей. Другие два результата вполне допустимы.


Наихудший сценарий при алгоритме RGA если пользователь напишет весь документ символ за символом от конца к началу. В этом случае возможно произвольное посимвольное чередование, поскольку перед каждым символом курсор перемещается в начало документа. Учитывая, что большинство пользователей пишут документы всё-таки от начала к концу и более-менее линейно, проблема чередования у RGA значительно менее серьёзная, чем у других алгоритмов. Поэтому в нашей работе мы предпочитаем RGA другим алгоритмам.


В Logoot и LSEQ проблема чередования, как мне кажется, нерешаема, и, к сожалению, использовать их из-за этого нельзя. Мы разработали алгоритм для RGA, который позволяет избавиться даже от этого варианта проблемы чередования, но сейчас у меня нет времени на нём останавливаться. При желании с ним можно ознакомиться в нашей статье об аномалиях чередования, представленной на семинаре PaPoC в 2019 году. Там подробно описан этот алгоритм.


Перемещение элементов в списке


Мы опубликовали статью на эту тему всего несколько месяцев назад (PaPoC 2020). На слайде проблема представлена на примере списка задач.



При составлении списков задач пользователям часто бывает необходимо изменить порядок элементов. В нашем случае пользователь вначале написал, что ему нужно купить молоко, полить цветы и позвонить Джо, а потом решил, что позвонить Джо нужно в первую очередь, и переместил этот элемент в начало списка.


Такую структуру данных можно представить с помощью CRDT-списка. В сущности, это то же самое, что CRDT для редактирования текста. Ни в одном из имеющихся алгоритмов CRDT нет встроенной операции перемещения элемента в списке. Вместо неё есть операции удаления элемента и добавления элемента. Казалось бы, операцию перемещения легко представить как операцию удаления с последующей операцией добавления на необходимой позиции в списке.


Давайте посмотрим, что произойдёт при таком подходе в ситуации, когда два пользователя осуществляют перемещение параллельно как это происходит на слайде.



Оба пользователя одновременно выполняют одну и ту же операцию: перемещают операцию phone joe с последней позиции в списке на первую. Операция перемещения реализована как удаление с последующим добавлением, поэтому вначале необходимый элемент дважды удаляется на старой позиции. Здесь разницы с тем, чтобы удалить его один раз, нет. А вот если добавить элемент дважды, то на новой позиции появится два элемента phone joe вместо одного. Ясно, что такой вариант нам не подходит.


Давайте спросим себя: что именно должно было произойти в этой ситуации?



На слайде представлен другой пример, в котором всё тот же элемент пользователи переместили на разные итоговые позиции в списке. Первый пользователь переместил элемент phone joe в начало списка, второй на позицию после buy milk. К какому именно результату должен прийти алгоритм? Он может, как и в прошлом примере, дублировать элемент phone joe, чтобы в итоге этот элемент оказался и в начале списка, и после buy milk. Но это нежелательный вариант. Перемещаемый элемент должен оказаться лишь на одной из этих двух позиций. Чтобы этого достичь, необходимо выбрать одну из двух конфликтующих версий, причём выбрать произвольно, но детерминистично. В нашем примере выбрана версия, в которой phone joe оказывается в начале списка.


Как реализовать такой вариант? Если вы знакомы с существующими работами в области CRDT, это может выглядеть знакомо. Мы тут смотрим на ситуацию, в которой произвольно, но детерминистически выбираем одно из нескольких параллельно записываемых значений. Такое происходит к last writer wins register. Там, если значение могут обновлять несколько пользователей, при параллельной записи нескольких значений выбирается одно на основе произвольного критерия вроде метки времени.


Дальше это значение становится общим, а остальные значения удаляются. В нашем примере со списком необходимо именно такое поведение. Мы можем представить позицию каждого элемента в списке как last writer wins register, а значение, находящееся в регистре как описание позиции данного элемента. Когда первый пользователь указывает для позиции phone joe начало списка, а второй перемещает этот элемент на позицию после buy milk, нам необходимо, чтобы одно из этих значений стало общим для обоих пользователей. Таким итоговым значением может быть начало списка.


То есть для операции перемещения мы можем использовать существующий CRDT (last writer wins register). Чтобы реализовать такую операцию, необходимы две вещи. Во-первых, сам регистр, и, во-вторых, способ описать положение некоторого элемента в списке (это и будет значением, содержащимся в регистре). Но если подумать, то такой способ уже есть.


Вспомните, что я уже говорил выше. Все CRDT присваивают каждому элементу списка или символу в тексте уникальный идентификатор. Каким именно будет этот идентификатор, зависит от того, какой используется алгоритм CRDT. Например, в Treedoc применяется путь через бинарное дерево, в Logoot путь через более сложное дерево с большим фактором ветвления, в RGA метка времени и так далее. Во всех этих CRDT есть работающий механизм обращения к определённой позиции в списке. Так что позиции можно сгенерировать с помощью существующих алгоритмов. А при перемещении элемента на новую позицию можно создать новый идентификатор для позиции, на которую мы хотим переместить элемент, после чего записать этот идентификатор в наш last writer wins register.


Помимо этого, нам необходим отдельный регистр last writer wins для каждого элемента в списке. Но здесь тоже есть простое решение: это набор CRDT add-wins set (AWSet на слайде):



Можно создать add-wins set, в котором каждый элемент набора является пунктом нашего списка и состоит из пары, а именно, значения элемента (например, описание пункта списка) и регистра last writer wins с положением этого пункта. Регистр last writer wins можно поместить в набор AWSet, а идентификаторы позиции из CRDT списка можно поместить в регистр last writer wins register. Итак, мы объединили три CRDT и создали новый CRDT, а именно CRDT списка с операцией перемещения. Он позволяет атомарно переместить элемент с одной позиции в списке на другую что, согласитесь, весьма неплохо. Заметьте, что этот подход работает с любым из существующих алгоритмов CRDT списка. То есть любой существующий CRDT можно дополнить операцией перемещения.


До сих пор мы рассматривали только перемещение отдельных элементов в списке. В списке задач перемещать несколько задач одновременно, как правило, не нужно, в крайнем случае их нетрудно переместить по одной. Но при редактировании текста нужна более общая операция перемещения, которая может работать с последовательностями символов. Давайте попробуем представить список в качестве текста. Здесь каждый элемент списка начинается с символа маркера и заканчивается символом новой строки:



Предположим, второй пользователь хочет переместить элемент Milk со второго места в списке на первое, то есть одновременно переместить последовательность символов. Параллельно этому первый пользователь изменяет Milk на Soy milk. Для этого он вначале удаляет первый символ слова Milk, а затем добавляет все остальные символы. В итоге возникло два отличающихся документа, которые теперь необходимо привести к одному состоянию. Каким должно быть это состояние? Интуитивно ожидаемый вариант переместить Milk в начало списка и изменить текст на Soy milk. К сожалению, если мы применим описанную мной выше операцию перемещения, то получим результат, показанный на следующем слайде.



Не знаю как вам, а мне на него смотреть грустно. Элемент Milk был перенесён на первую позицию в списке, но все изменения в этом элементе остались на старой позиции этого элемента. В результате документ заканчивается символами Soy m. Это произошло потому, что позиция, на которой было выполнено добавление этих символов, не изменилась. Я не думаю, что эта проблема нерешаемая, но пока что нам не удалось найти адекватного способа её преодолеть. Я буду очень рад, если кто-то из вас захочет над ней подумать.


Перемещение деревьев


Вообще деревья крайне полезная структура данных. Файловая система вашего компьютера, документ JSON или XML всё это примеры деревьев. Предположим, у вас есть приложение, которое использует то или иное дерево например, распределённую файловую систему или документ JSON с возможностью перемещать поддерева документа. Такому приложению необходима операция перемещения. И здесь сразу возникает проблема, целиком аналогичной той, с которой мы уже встречались в контексте списков: что происходит, когда несколько пользователей параллельно перемещают один и тот же узел на разные позиции?



В примере на слайде первый пользователь перемещает узел А (со всеми дочерними узлами) так, что тот становится дочерним узлом B. Одновременно второй пользователь делает узел А дочерним узлом C. При таком конфликте возможны четыре итоговых дерева, которые представлены в правой части слайда. Во-первых, узел А может быть дублирован это не лучшее решение проблемы. В новом дереве один узел А окажется дочерним для B, а другой для C. Но помимо самого узла A нужно также скопировать все его дочерние узлы. В большинстве приложений такой итог нежелателен.


Второй вариант сделать узел A одновременно дочерним и для B, и для C. Такая структура данных уже не дерево, а ориентированный ациклический граф (DAG), или граф более общего типа. На мой взгляд, этот вариант тоже неудачный. Следует выбирать между третьим и четвёртым вариантами, где A является либо дочерним для B, либо дочерним для C. Здесь, как и в ситуации с перемещением в списке, одна версия становится общей, а вторая удаляется.


Но сейчас перед нами встаёт дополнительное затруднение. Вы можете поставить эксперимент у себя на компьютере. Создайте каталог a, затем в нём создайте другой каталог b, а потом попробуйте переместить a в b. То есть попробуйте сделать a подкаталогом самого себя. Как вы думаете, что произойдёт? По идее, в результате должен возникнуть цикл. Я попробовал в macOS и получил сообщение об ошибке Invalid argument. Подозреваю, что большинство операционных систем, в которых файловая система является деревом, реагируют подобным образом, потому что если разрешить такую операцию, то система уже не будет деревом.


Но обнаружить ситуацию, когда пользователь пытается сделать директорию дочерней для себя самой, довольно просто. А вот в случае с CRDT всё сложнее. Взглянем на пример на слайде.



Первый пользователь сделал узел B дочерним для A. Второй пользователь одновременно с этим сделал узел A дочерним для B. По отдельности эти операции вполне допустимы и безопасны. Но если их выполнить одновременно, возникнет только что описанная проблема циклических связей. Возможные результаты таких операций представлены в правой части слайда.


Первый вариант содержит циклические связи, то есть эта структура данных уже не дерево. Второй вариант решения дублирование. Можно скопировать A и B, так, чтобы в одном случае один узел являлся дочерним, а во втором другой. Формально это допустимый вариант, но всё-таки нежелательный. Я полагаю, что здесь, как и в прошлом примере, нам следует выбрать одну из конфликтующих операций и удалить вторую. То есть либо A должна быть родителем B, либо наоборот, но не то и другое одновременно.


А как ведут себя существующие программы в таком случае? Я поставил эксперимент с Google Drive, результат которого виден на слайде.



На одном компьютере я переместил A в B, на другом B в A, затем дал им синхронизироваться. Google Drive вернул сообщение о неизвестной ошибке. Так что как видим, даже Google не удалось найти удовлетворительное решение этой проблемы. Но для CRDT правильное решение всё-таки необходимо. С этой целью мы разработали алгоритм, который позволяет безопасно выполнять такого рода операции для деревьев, не приводя к возникновению циклических связей. О нём я сейчас и расскажу.


Схематично этот алгоритм представлен на следующем слайде:



Первый пользователь здесь выполнил операции op1, op3, mv A B и op5. Каждой операции присвоена метка времени t. Для соответствующих операций значения этих меток 1, 3, 4 и 5. У второго пользователя есть операция mv B A с меткой времени 6. Как уже говорилось, сами по себе эти операции перемещения безопасны. Сложности начинаются, когда мы пытаемся синхронизировать эти операции, как это показано на следующем слайде.



Самый простой способ выполнить синхронизацию это объединить все операции в один список, расположив их в порядке возрастания метки времени. В этом случае первая операция перемещения всё ещё безопасная, а вторая уже может вызвать цикл. Поэтому нам необходим способ пропустить эту операцию.


Давайте взглянем теперь на ситуацию с точки зрения первого пользователя. В его версии уже выполнены операции с метками времени от 1 до 5. С ними теперь нужно синхронизировать операцию op2, выполненную вторым пользователем. Поскольку значение её метки времени 2, она должна оказаться между двумя операциями первого пользователя, как это показано на следующем слайде.



Мы не можем просто добавить op2 в конец списка, потому что тогда они не будут упорядочены по метке времени. Чтобы определить, какие операции безопасные, а какие нет, важно знать порядок, в котором операции выполняются.


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



Для реализации этого алгоритма необходима возможность отмены операций. Как видим, первому пользователю нужно добавить новую операцию с меткой времени 2, в то время как у него уже есть операция с меткой времени 5. Поэтому ему необходимо отменить все операции с меткой времени больше 2, то есть операции op5, mv A B и op3. Теперь можно добавить операцию op2, а затем повторно применить все отменённые операции. При условии, что все операции полностью отменяемые, этот алгоритм генерирует список операций, применённых в порядке возрастания метки времени.


Все эти преобразования могут показаться ресурсозатратными. Какие-то издержки здесь, конечно, неизбежны. Чтобы определить их размер, мы поставили эксперимент с тремя репликами, которые мы развернули на трёх разных континентах, чтобы коммуникация происходила с большой задержкой. Затем мы запустили генерацию операций перемещения на этих репликах. Чем быстрее эти операции генерируются, тем больше отмен и повторов необходимо выполнять. Мы обнаружили, что время выполнения отдельной операции растёт линейно в зависимости от скорости применения операций, поскольку количество отмен и повторов растёт линейно в зависимости от числа операций. Тем не менее, в нашей довольно простой программе обрабатывалось около 600 операций в секунду. Это существенно меньше показателей, скажем, системы работы с большими данными, но значительно больше того, что необходимо приложению, запущенному одним пользователем в своей локальной системе для отдельного дерева. Так что для большого диапазона приложений такая производительность вполне допустима.


Теперь я хотел бы в общих чертах описать структуры данных, используемые в этом алгоритме (см. слайд).



В сокращённом виде операция перемещения описывается структурой MoveOp. В каждой операции есть метка времени Timestamp. Такая метка должна быть уникальной для всего приложения; этого легко добиться с помощью, например, меток времени Лэмпорта. Далее, для операции необходим идентификатор, по которому можно обращаться к узлам дерева. Здесь child это идентификатор перемещаемого узла, а parent идентификатор узла назначения. Metadata meta это метаданные отношения родительского и дочернего узла. Например, если мы работаем с файловой системой, в качестве meta может выступать имя файла. Обратите внимание, что здесь нигде не записано старое местоположение дочернего узла. Операция просто переносит узел со старого местоположения на новое.


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


Теперь мы можем описать алгоритм перемещения. Вначале нужно определить, что значит, что a является родительским узлом b. Формально это сделано на слайде.



a является родителем b в том случае, если (a, m, b) дереву, то есть если a является прямым родителем b в дереве, или если есть узел c, такой, что a является родителем c, а c является родителем b. При таком определении операцию перемещения можно определить следующим образом. Вначале нужно проверить, не является ли перемещаемый узел родителем по отношению к своему родительскому узлу. Если да, то операция не выполняется, потому что она привела бы к возникновению цикла. То же самое в ситуации, когда дочерний узел идентичен родительскому. Если эти проверки успешно пройдены, то ситуация безопасна. Старое отношение можно удалить, а затем вставить новое отношение из дерева с новыми метаданными.


Мы доказали правильность этого алгоритма. А именно, мы показали, что для каждого дерева, с которым выполняется операция, сохраняется свойство дерева. Структура данных является деревом в случае, если у каждого узла есть уникальный родитель и если в дереве нет циклов. Выше мы показали, что операция перемещения не нарушает этих свойств. Кроме того, мы доказали, что эта операция является CRDT. То есть не важно, в каком порядке применяются операции если два пользователя применяют один и тот же набор операций, то итоговое состояние одинаковое. Иначе говоря, мы доказали, что операции коммутативны.


Сокращение издержек метаданных


CRDT с самого их появления преследовали проблемы с издержками метаданных. Для свойств CRDT всегда требовалось много места и сетевых ресурсов. Как вы помните, при редактировании текста мы присваивали уникальный идентификатор каждому символу в текстовом документе.



На следующем слайде показан текст, в котором использован такой алгоритм. Если работа идёт с английским текстом, то в кодировке UTF-8 один символ занимает один байт; для текста на русском языке каждый символ, скорее всего, будет занимать два байта. Это не так много; но в дополнение к этому необходим идентификатор позиции. Чаще всего в качестве него используется какой-нибудь путь в дереве, размер которого зависит от длины пути. Он с лёгкостью может занимать несколько десятков байт, если не сотню. Помимо него необходим идентификатор узла, то есть пользователя, который добавил данный символ. В итоге для символа, занимающего один байт, необходимо 100 байт метаданных, или даже больше. Согласитесь, ситуация крайне печальная.


Хочу поговорить об экспериментах, которые мы проводили в проекте Automerge, специальной реализации CRDT. За последние несколько месяцев я посвятил довольно много усилий тому, чтобы сократить издержки CRDT. Результаты вкратце представлены на следующем слайде.



Давайте обсудим их по порядку. Набор данных, на который мы тут смотрим история редактирования одной статьи в академическом издании. Мы написали исследовательскую статью (в формате plain text-файла в формате LaTeX размером около 100 килобайт) с помощью текстового редактора собственной разработки, записав каждое нажатие клавиши во время этой работы. В общей сложности зафиксировано около 300 000 изменений: это включает все добавления и удаления символов, а также перемещения курсора. Мы хотели сохранить всю эту историю изменений, чтобы иметь возможность наблюдать за эволюцией документа (так же, как в системе контроля версий сохраняют прошлые версии проекта).


Проще всего этого добиться, если хранить журнал операций CRDT. Если записать такой журнал в формате JSON, он займёт около 150 мегабайт. С помощью gzip его можно сжать до примерно 6 мегабайт, но по сравнению со 100 килобайтами исходного текста без метаданных это всё равно огромный размер. Нам удалось, более эффективно закодировать данные и сократить размер файла метаданных до 700 килобайт (то есть где-то в 200 раз), при этом сохранив полную историю изменений. Если же отказаться от хранения перемещений курсора, размер можно сократить ещё на 22%. Далее, если убрать историю редактирования CRDT и оставить только метаданнные, необходимые для слияния текущей версии документа, размер сокращается до 228 килобайт. Это всего лишь в два раза больше размера исходного текста без метаданных. Если эти данные ещё и сжать в gzip, то мы получим чуть больше 100 килобайт. Далее, если избавиться от отметок полного удаления (tombstones), то мы получим 50 килобайт. Это то, что нужно для хранения уникальных идентификаторов для каждого символа. Но без отметок полного удаления мы уже не можем обеспечить слияния параллельно добавленных изменений.


Даже сохраняя целиком историю редактирования и отметки полного удаления, мы всё равно можем добиться весьма компактного размера итогового файла. Сейчас я постараюсь кратко объяснить, как это сделать. Мы храним информацию о всех выполненных операциях, и каждой операции присваивается уникальный идентификатор. В нашем случае таким идентификатором является метка времени Лэмпорта, это пара из счётчика и идентификатора узла. Как и в RGA, в нашем алгоритме для определения местоположения символа используется ссылка на идентификатор предшествующего символа. Далее все операции сохраняются в порядке, в котором они появляются в тексте. В итоге получается таблица вроде той, которая показана на следующем слайде.



В первых двух столбцах слайда хранятся метки времени Лэмпорта для каждой операции. Каждая строка здесь операция вставки. Как видим, в третьем и четвёртом столбце указаны идентификаторы предшествующих символов. Здесь второй символ добавляется после первого, третий после второго и так далее. В следующих двух столбцах указаны вставляемые символы в кодировке UTF-8, и количество байт, которое занимает каждый символ. Наконец, в последних двух столбцах записано, был ли символ удалён.


Эти данные можно сжать с помощью нескольких довольно простых приёмов. Каждый столбец этой таблицы можно закодировать отдельно. Первый столбец содержит числа 1, 2, 3, 4, 5, 6. К ним можно применить дельта-кодирование, то есть вычислить для каждого числа разницу между ним и предшествующим числом. Тогда мы получим 1, 1, 1, 1, 1, 1. К этому ряду можно применить кодирование длин серий, то есть сказать, что мы храним 6 повторений числа 1. Если к этому применить кодировку переменной длины для целых чисел, результат займёт всего два байта. Эта кодировка записывает самые короткие числа одним байтом, которые подлиннее двумя, трёмя и тому подобное. Итак, для записи первого столбца нам потребовалось всего два байта, то есть байта на операцию. Для второго столбца нужно создать таблицу подстановки, в которой идентификаторам пользователей присваиваются короткие числа. Тогда второй столбец можно представить как 0, 0, 0, 0, 0, 0. Дальше опять-таки можно применить кодирование длин серий, а затем кодировку переменной длины для целых чисел, и, как и в первом случае, результат будет занимать два байта.


Взглянем на столбец с символами UTF-8. Обратите внимание, что у нас есть отдельный столбец, в котором указана длина символа в байтах. Сам этот столбец легко закодировать только что описанным способом. А символы UTF-8 можно просто объединить в строку UTF-8 размером в 6 байт. Наконец, в последних двух столбцах мы записываем только тот факт, что мы удалили один символ. В дополнение ко всему этому нам необходимо совсем немного метаданных с информацией о том, когда произошло каждое изменение, какой диапазон идентификаторов операций, какие значения счетчиков для каждого изменения. В результате можно реконструировать состояние документа в любой момент времени в прошлом. Итак, мы сохранили целиком историю документа, но сжали её так, что она занимает совсем немного места.


На этом я хотел бы перейти к заключению. Как я уже сказал вначале, в работе с CRDT много трудностей. Сделать хорошую реализацию непросто, а плохую легче лёгкого. Мы рассмотрели четыре проблемы, которые давно преследуют CRDT: чередование, операции перемещения в списках и деревьях, а также проблему издержек. Если вы хотите ознакомиться с дополнительной литературой по теме, вот список статей, в которых описан целый ряд CRDT для редактирования текста.


Научные статьи по теме

Logoot: Stephane Weiss, Pascal Urso, and Pascal Molli: Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks, ICDCS 2009.


LSEQ: Brice Nedelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils: LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing, DocEng 2013.


RGA: Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee: Replicated abstract data types: Building blocks for collaborative applications, Journal of Parallel and Distributed Computing, 71(3):354368, 2011.


Treedoc: Nuno Preguica, Joan Manuel Marques, Marc Shapiro, and Mihai Letia: A Commutative Replicated Data Type for Cooperative Editing, ICDCS 2009.


WOOT: Gerald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine: Data consistency for P2P collaborative editing, CSCW 2006.


Astrong: Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, and Marek Zawirski: Specification and Complexity of Collaborative Text Editing, PODC 2016.


Наконец, вот список наших работ по темам, которые мы сейчас обсуждали.


Interleaving anomaly: Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford: Interleaving anomalies in collaborative text editors. PaPoC 2019.


Proof of no interleaving in RGA: Martin Kleppmann, Victor B F Gomes, Dominic P Mulligan, and Alastair R Beresford: OpSets: Sequential Specifications for Replicated Datatypes, May 2018.


Moving list items: Martin Kleppmann: Moving Elements in List CRDTs. PaPoC 2020.


Move operation in CRDT trees: Martin Kleppmann, Dominic P. Mulligan, Victor B. F. Gomes, and Alastair R. Beresford: A highly-available move operation for replicated trees and distributed filesystems. Preprint


Reducing metadata overhead: Martin Kleppmann: Experiment: columnar data encoding for Automerge, 2019.


Local-first software: Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan: Local-first software: You own your data, in spite of the cloud. Onward! 2019.


Все слайды доступны в электронном виде. Спасибо большое за внимание!


Если вы дочитали этот доклад с Hydra 2020 до конца, похоже, что вы интересуетесь распределёнными вычислениями. В таком случае вам будет интересно и на Hydra 2021, которая пройдёт с 15 по 18 июня. Там будут как доклады от академиков, так и выступления людей из индустрии, которые имеют дело с параллельными и распределёнными системами в продакшне на сайте уже анонсирован ряд докладов.
Подробнее..

Реализация распределённых вычислений на языке python с использованием технологии docker

13.01.2021 12:17:24 | Автор: admin

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

Одно из первых упоминаний распределенных вычислений относится к 1973 году. Сотрудники научно-исследовательского центра Xerox PARC Джон Шох и Джон Хапп написали программу, которая рассылала себя по другим работающими компьютерам через локальную сеть PARC.

Впоследствии, в связи с развитием и ростом количества персональных компьютеров, распределённые вычисления стали использоваться всё более и более широко. Так, в конце 1980- х годов Арьен Ленстра и Марк Менес написали программу для факторизации длинных чисел. Она рассылала задания на компьютеры участников по электронной почте и таким же образом принимала ответы.

Ещё одним значимым событием было создание проекта SETI@Home (Search for Extra-Terrestrial Intelligence at Home) для поиска внеземного разума путём анализа данных с радиотелескопов, в том числе на домашних компьютерах участников. Данный проект был запущен в 1999 году и оста новлен в 2020-м. Эта распределенная система была построена на платформе BOINC, созданной в университете Беркли.

В дальнейшем разработки по созданию различных распределённых систем активно продолжались, и в настоящее время они применяются в самых различных областях. В частности, распределённые вычисления широко используются для математических задач. Типичным примером является факторизация чисел (разложение их на произведение простых множителей).

Ещё одной важной областью применения распределённых вычислений является обработка больших данных с использованием методов машинного обучения и Data Mining. В качестве языка программирования для этой цели в последние годы на лидирующие позиции выходит язык Python. По состоянию на март 2020 года, согласно рейтингу TIOBE, Python находится на третьем месте, хотя ещё в 2015 году занимал лишь седьмое.

Одной из известных проблем языка Python является относительно низкая производительность в сравнении с компилируемыми языками такими как C++. Данный недостаток является дополнительным поводом применять параллельное и распределённое программирование в процессе разработки.

Также во второй половине второй декады 21 века стали набирать популярность такие технологии, как контейнеризация и микросервисы. Благодаря программному обеспечению Docker и изолированным пространствам исполнения стало возможным относительно легко запускать на одном сервере несколько приложений полностью изолированно друг от друга и с собственными настройками среды выполнения. В настоящее время технология Docker используется всё более широко и для самых разных целей, в том числе при разработке программного обеспечения: она позволяет проводить различные эксперименты с зависимостями ПО, не засоряя основную систему.

Основной инструмент кластеризации для Docker носит название Docker Swarm. Он позволяет объединять узлы в единое кластерное пространство и распространять контейнеры по этому кластеру. Представленная в данной статье разработка основывается на изолированных Docker-контейнерах исполнителях.

Каждый исполнитель представляет из себя асинхронный TCP-сервер, работающий следующим образом. На первом шаге он десериализует полученные данные и получает объект задания. Каждый такой объект содержит код функции, которую необходимо выполнить, а также значения её входных данных. Исполнитель запускает заданную функцию, используя определённую стратегию исполнения, после чего сериализует результат её работы и возвращает полученный результат.

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

Здесь стоит учитывать, что потоки в Python по умолчанию являются не совсем полноценными в отличие, например, от потоков в языке C++. Дело в том, что интерпретатор Python (CPython) написан на языке C с использованием некоторых библиотек, не являющихся потокобезопасными. Из-за этого используемый в CPython механизм GIL (Global Interpreter Lock) не позволяет потокам исполняться по-настоящему параллельно даже на многоядерных процессорах. Вместо этого интерпретатор постоянно переключается между потоками с интервалом примерно 5 миллисекунд. В связи с этим, на современных компьютерах в большинстве случаев более эффективным вариантом будет использование стратегии множественных процессов.

Разрабатываемая библиотека имеет следующую архитектурную особенность. В ней применён механизм Docker Swarm, позволяющий организовать единый вход и выполнять балансировку нагрузки между исполнителями. Наличие единой точки входа для клиентов позволяет разработчикам не заботиться о настройке множественных подключений и конфигурации каждого исполнителя в отдельности.

Кроме того, Docker Swarm позволяет после создания контейнера реплицировать его на доступные узлы. Также он позволяет легко увеличивать количество репликаций исполнителя, способен балансировать нагрузку между исполнителями, автоматически перезапускает исполнителей при их отключении, автоматически подключает компьютеры, которые ранее были отключены от кластера.

Дополнительно отметим, что в представленной библиотеке оставлена возможность работы и без использования Docker Swarm, так как в некоторых случаях его применение будет избыточным. Примером может быть ситуация, когда у нас имеется ограниченное количество слабых машин, имеющих одноядерный процессор и ограниченный объём оперативной памяти.

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

Тестирование проводилось на двух объединённых в локальную сеть компьютерах (6 ядер на первом и 2 на втором) с суммарным объёмом ОЗУ 20 ГБ, под управлением ОС Linux.

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

Результаты выполнения представлены в следующей таблице.

Стратегия/Задача

Расчет факториала

Вычисление про- стых чисел

Множественные процессы (8 процессов)

7.3525 с

39.3731 c

Многопоточный (8 потоков)

54.3255 c

42.0415 с

Последовательная

43.4656 c

41.4426 c

Асинхронная

43.5361 с

43.9102 c

Исходя из данных результатов, можно сделать вывод, что запуск функций в отдельных процессах позволяет максимально загрузить процессор и достичь наибольшей скорости выполнения задач. Многопоточный вариант уступает даже последовательному исполнению из-за особенностей реализации многопоточности в языке Python. Асинхронный вариант показал результаты, не слишком сильно отличающиеся от последовательного. Но, в целом, это хороший показатель для математических задач, так как в этих функциях отсутствует, например, ожидание ответа базы данных. Также благодаря асинхронному серверу в основе каждого исполнителя, можно запускать эти задачи совместно, не блокируя запуск других функций.

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

Одним из возможных применений разработки является организация распределённой проверки решений при проведении соревнований по программированию.

Подробнее..

Вычислительная система пятого поколения

12.02.2021 14:21:36 | Автор: admin

В 80 годы прошлого века правительство Японии совершило попытку создать распределенную вычислительную систему следующего поколения с элементами ИИ. Проект закончился достаточно закономерным провалом. Причина провала достаточно проста, почему то посчитали, что простого наличия технологии производства больших интегральных схем хватит для качественного "скачка" в вычислительных технологиях (своеобразный переход количества в качество). Да, история повторилась, после изобретения компьютера, тоже присутствовала необоснованная уверенность в скором появлении ИИ и тоже провалилась.

Сейчас ИИ в основном рассматривается как совокупность нейронов, объединенных в сеть. В свою очередь я попытался посмотреть на человеческий мозг, как на вычислительную систему. При этом не акцентируя внимание на элементах какого типа он базируется.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Современное состояние вычислительной техники

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

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


Внимание:

Все идеи и алгоритмы, описываемые в данной статье, являются результатом моей независимой и полностью самостоятельной интеллектуальной деятельности. Как автор, разрешаю свободно использовать, изменять, дополнять все идеи и алгоритмы любому человеку или организации в любых типах проектов при обязательном указании моего авторства (Балыбердин Андрей Леонидович Rutel@Mail.ru).


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

Примерное описание идеи в статье : Цифровое бессмертие Инженерный подход.


Определим основные термины


Объект

Определение понятия объекта (правильнее сказать виртуальный объект), поведение которого и будет моделировать новая вычислительная система.

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


Данные

Данные это иерархическая информационная конструкция, состоящая из совокупности символов. Данная структура, описывает физические параметры объекта в настоящем времени и изменяется согласно законам функционирования при взаимодействии с другими объектами.


Символ

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


Взаимодействие объектов

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


Время

Моделируемые объекты изменяют свое состояние во времени. Время в физическом мире не имеет носителя и является просто отношением скорости течения различных процессов. Единственно, что можно сказать о времени определенно, оно направлено из прошлого, через настоящее, в будущее и нереверсивно. Текущее состояние данных объекта это и есть его настоящее. Время, для вычислительной системы, логичнее определить через количество взаимодействий между объектами. Нет взаимодействий, нет времени. Если произошло взаимодействие (приняты данные взаимодействия), то оно мгновенно изменяет объект (его состояние). Если требуется привязать объект к реальному (модельному или физическому времени), то достаточно путем взаимодействия с объектом таймер добавить в его данные (состояние) значение времени.


Вычисление

Новая вычислительная парадигма в значительной степени (с вычислительной точки зрения) базируется на идеях DataFlow (вычисления возможны только после готовности всех исходных данных). В момент когда происходит взаимодействие (получены данные взаимодействия от другого объекта), выполняются все возможные преобразования для данного объекта, для которых присутствуют необходимые данные. В отличии от канонического DataFlow, где проверяется только готовность исходных данных, необходимо проверить еще наличие возможности записать результат преобразования. Такие проверки позволяют осуществлять координацию работы нескольких объектов, притормаживая объекты имеющие возможность создать много данных сразу (не считаясь с возможностью другого объекта их обработать). В результате получается сбалансированная система, где невозможно начать вычисления раньше готовности данных и производить вычисление слишком быстро по причине отсутствия места для сохранения данных. Можно добавить, что существенным отличием от вычислительной парадигмы фон-неймана, является возможность получить больше одного легитимного результата. Поскольку исходными данными для создания ПО являются законы, а не отдельные команды (фон-нейман). Применение законов отделяет множество легитимных решений из множества возможных, их может быть больше одного, а может и не быть вообще. В парадигме фон-неймана происходит простое вычисление математического выражения, с одним результатом в итоге.

Физическая реализация вычислителя может любой (программа для обычного фон-неймановского процессора, FPGA, обычная логика, нейронные технологии и тд). Каналы переноса данных взаимодействия, по своим свойствам являются обычными каналами связи (точка-точка) с произвольно распределенным по их протяженности FIFO (канал имеет некую информационную емкость). Регулируя скорость передачи символов в отдельных каналах, можно регулировать скорость работы различного ПО, иначе говоря это более эффективный аналог системы приоритетов из парадигмы фон-неймана.


Итог

Отдельные объекты могут располагаться (исполняться) на различных кристаллах, которые соединяются каналами связи (для переноса данных взаимодействия). Нет границ между различными компонентами суммарной вычислительной системы. Состояние объекта в будущем зависит только от данных взаимодействия, плюс данные текущего состояния объекта, значит может быть вычислено полностью параллельно. Кроме того можно представить вычисление виде направленного ациклического графа, что позволит организовать вычислительный процесс по готовности данных с одновременным использованием большого числа вычислительных ядер. Такой подход дополнительно распараллеливает вычислительный процесс. Получается максимально параллельная и распределенная вычислительная система.

Программирование в новой парадигме превращается из составления списка исполняемых команд (фон-нейман) в описании иерархии законов (свойств), которым должен подчиняться виртуальный объект (или их совокупность). Такой подход открывает очень большие перспективы, например избавляет от неэффективного посредника (программиста) при взаимодействии с вычислительной системой. Разрушает барьер максимальной сложности создаваемой программы. Человек может одновременно оперировать не более чем 5-7 информационными сущностями, что приводит к ошибкам логической связности больших объектов. Программирование в новой парадигме становится инкрементальным, можно постепенно добавлять (редактировать) законы (свойства), до тех пор пока весь объект не станет соответствовать потребностям пользователя. В парадигме фон-неймана такой подход невозможен из-за того что программирование представляет собой создание (редактирование) последовательности действий, которая может полностью измениться при внесении даже небольших изменений в законы функционирования математической модели объекта. Замечу, что нигде не говорится о необходимости изначально понимать устройство создаваемого объекта, можно просто формировать список требований (законов). Произойдет постепенное формирование множества объектов подходящих для решения поставленной задачи. Объекты будут немного отличаться друг от друга, но только в части не значимой для решаемой задачи. Если замкнуть обратную связь с объектом существующим в физической реальности, то можно создать автоматическую исследовательскую систему, которая будет без участия оператора строить виртуальные модели физических объектов. Самое главное, такой подход позволит решить проблему написания адаптивно изменяющегося ПО, предназначенного для работы в не контролируемой среде (в изменяющемся реальном мире).

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

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


Физическая реализация вычислительной системы


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

Сетевая парадигма

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

В новой вычислительной системе за счет революционного увеличения эффективности сетевой подсистемы данная проблема должна быть решена. Необходимо получить скорости до 10Е14 бит в секунду для каждого отдельного кристалла, при стабильных задержках задержках передачи, на 90% определяемых скоростью распространения электромагнитной волны в среде передачи. (Подробное описание устройства коммуникационной парадигмы в статье: Синхронный интернет: Синхронная символьная иерархия). Получить такую производительность при использовании медных линий связи практически невозможно, соответственно необходимо полностью изменить подход к проектированию меж-соединений. В настоящее время все компоненты устанавливаются на печатную плату и соединяются медными проводниками. В качестве альтернативы такому подходу, предлагаю в текстолите прокладывать оптические волокна и выводить их с торцов ПП или вырезов в ней для устанавливаемых микросхем. Если сейчас микросхемы распаиваются, то в новом подходе кристаллы могут устанавливаться в прорези в печатной плате. Оптические интерфейсы микросхем должны располагаться с торцов и сопрягаться с оптическими интерфейсами ПП, различные ПП соединять разъемами устанавливаемыми на внешние края плат. Такой подход позволит максимально плотно (значит с минимальными задержками) и надежно строить систему оптических соединений.

Теплоотвод

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

Структура вычислительной системы

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

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

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

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Вопросы безопасности

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

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


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

Границы вычислительной системы

Следующий вопрос: Если вычислительная система распределенная и в ней нет явных границ, то где конкретный пользователь имеет право монопольно распоряжаться аппаратурой(где граница частных владений)? Наиболее оптимальным будет создание физически существующего объекта ключ, который подключается к специальным административным каналам, только с использованием этих каналов, можно инициализировать управляющее ПО коммутаторов. Все что удастся инициализировать с использованием такого ключа и есть границы личного пространства (собственная вычислительная система), все остальное это пространство с делегированными полномочиями (разрешением ограниченного использования, выданного владельцем другой вычислительной системы). Такая инициализация может быть коллективной, различные пользователи получают различные типы (правила) доступа. Различать пользователя опять же по ключу, при этом если вынуть ключ, то настройки сохраняются и запущенное ПО продолжает работать.

Ограничивать доступ можно не только по пользователю, но и по степени доверенности исполняемого ПО.


Энерго-эффективность

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

Вычислитель

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


Далее будет описываться построение вычислителя, с принципами функционирования родственными DataFlow системам, но вычисления объекта возможны и другими вариантами (процессор на принципах фон-неймана, ПЛИС, нейронные сети и др.).

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

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


Вычислитель оперирует (обрабатывает) символы типа данные процессора ХХХ, как их интерпретировать личное дело этого вычислителя (никак не влияет на результат).


Пример структуры данных :

[EXE][READY][KEY][DATA]

EXE данные принадлежат к активному (вычисляемому) пути графа

READY данные вычислены и готовы к дальнейшему использованию (0 нет данных)

KEY уникальный ключ для поиска данных в ассоциативном ЗУ

DATA данные для обработки


Вершина графа вычисляется, только если все входящие ребра имеют значение отличное от нет данных.Если вершины такого графа рассортировать по слоям, таким образом что бы все входящие ребра принадлежали вершинам предыдущих слоев (были вычислены) или были данными состояния объекта. Результатом будет некоторое число групп вершин (слоев), вычислять значения вершин внутри такой группы можно в любом порядке. Но и тут можно немного оптимизировать вычислительный процесс, большинство преобразований (так эффективней для реального АЛУ) имеет один либо два операнда и выдает один результат, все остальные приводят нескольким таким преобразованиям. Максимальная эффективность вычислительного процесса получается когда результат предыдущего преобразования используется как один из операндов в следующем, приходится читать только один операнд и результат не всегда сохранять (он расходуется в следующем преобразовании). Если сделать вторую, уже вертикальную сортировку по этому критерию, то получим набор коротких последовательностей преобразований (нитей). Такие нити могут начинаться и заканчиваться на любом слое.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Определим механизм чтения второго операнда.

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Появляется задача распределения отсортированного графа по отдельным вычислительным ядрам, имеющим некоторый объем памяти, интерфейс связи с соседними ячейками и возможность доступа к каналам связи. Назначим каждому ребру графа уникальный идентификатор, возможно уникальный даже в пределах нескольких объектов. С большой вероятностью число уникальных идентификаторов будет много больше суммарной памяти всех вычислительных ячеек и максимального числа одновременно передаваемых между слоями данных. Поэтому использовать обычную память (данные выбираются по адресу) невыгодно, в новой парадигме в вычислительных ядрах должна использоваться ассоциативная память (замена регистровой и КЭШ памяти в парадигме фон-неймана). АЗУ будет хранить данные до момента их использования и предоставлять их, как своему АЛУ, так некоторому числу соседних, но не всем одинаково быстро (ближайшим соседям быстро за один такт) и это нужно учитывать при размещении нитей по различным ядрам. Получается, что каждое ядро имеет многоканальное АЗУ, число каналов чтения равно числу соседей, которым предоставлен быстрый доступ к данным (остальные медленнее и другим механизмом). Для вычисления объекта необходимо распределить граф по отдельным вычислительным ядрам так, что бы хранимых на каждой ступени (несколько слоев) вычисления данных было не больше числа ячеек АЗУ и список вычисляемых вершин (команд) мог поместиться в память генератора команд (control unit). По вертикали (между слоями) ядра соединяются через основную коммуникационную среду вычислительной системы (обычные каналы передачи данных). Данные из АЗУ, а в ней кроме промежуточных данных хранятся еще и данные состояния объекта, также могут быть коллективно выгружены в оперативную память. Такой механизм можно сравнить с виртуальной памятью в современных процессорах, только здесь это будет механизм виртуального вычислительного пространства. Физически реализованных вычислительных ячеек может быть многократно меньше, чем использовано для исполнения конкретного набора ПО.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Сколько физически существующих ядер необходимо для вычисления конкретного объекта?

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


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

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


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


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

Проведите мысленный эксперимент:

  • Возьмем любую функцию (Изначально созданную на языке высокого уровня).

  • Выполним ее и запишем последовательность исполненных ассемблерных команд.

  • Для простоты понимания выделим из этих команд только те, которые производят изменения данных, их будет примерно 20% от общего количества.

  • Построим граф где вершиной будет команда, ребра будут результатами исполнения или данными имеющимися на момент начала вычисления

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

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


В новой парадигме нет понятие цикла (есть понятие спираль).

Вопрос: Как примирить сегодняшнее представление о программировании, где практически постоянно встречаются различные циклы?

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

Считаем, что цикл имеет бесконечное число повторений. Для того что бы в результате компиляции не получить бесконечного размера граф (программу), необходимо записывать ее в сжатом виде (добавить служебные символы указывающие на бесконечное число повторений) и в момент исполнения распаковывать (control unit) уже в вычислительном ядре. В момент завершения цикла, необходимо отправить сообщение (записать данные в регистр управления) модулю генерирующему последовательность команд сигнал завершающий генерацию повторов тела цикла. В процессе компиляции никто не запрещает выполнить несколько логических итераций цикла за одну физическую, что позволит дополнительно ускорить вычисление. Примерно по той же схеме можно организовывать вызовы функций (процедур), подмену частей графа на оптимизированные варианты (где исключены не использованные пути).


Память в новой парадигме.

Понятие адресного пространства отсутствует и обращение к данным идет по уникальному идентификатору. Никаких ограничений на размер и структуру уникального идентификатора нет, в него можно вложить путь до конкретного запоминающего устройства, тип памяти, параметры доступа и многое другое. Все уникальные идентификаторы могут выглядеть как адрес в сети и при построении маршрута он будет постепенно использоваться промежуточными объектами для маршрутизации, настроек доступа (пароли и др), адреса в физической памяти, размера в битах и многое другое. По существу в процессе доступа к данным уникальный идентификатор является данными взаимодействия. Кроме того большинство обращений к памяти являются коллективными (чтение массивов данных), все отдельные переменные (данные состояния или промежуточные данные) хранятся в АЗУ вычислительного ядра и загружаются (сохраняются) коллективно в момент инициализации вычислительного процесса.


Подробно процесс создания ПО, описание операционной системы и алгоритма решения произвольной задачи, будет описан в следующей статье.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru