Параллельные вычислительные системы

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

Для каждого процессора можно сказать, что он может выполнять только одну задачу за раз. Таким образом, система, которая зависит от небольшого количества таких процессоров, фактически выполняет почти все задачи последовательно. Однако параллелизм является очень распространенным явлением в нашем мире, и использование такой архитектуры для решения параллельных задач либо невозможно, либо крайне неэффективно.В противоположность последовательной архитектуре вычислительных систем находится параллельная вычислительная система [1], которую можно рассматривать как ещё не существующую в настоящий момент. Представим себе такую параллельную систему, которая больше не будет состоять из небольшого количества мощных процессоров и одного централизованного большого хранилища, но вместо этого будет состоять из огромного количества (миллионов, миллиардов) простых модулей. Каждый модуль будет представлять собой микроконтроллер со встроенными простыми вычислительными и хранящими функциями, при этом каждый модуль будет иметь высокотехнологичное взаимодействие друг с другом, что позволит быстро передавать данные. Когда выполняется какое-либо вычисление, программа передается одному вычислительному модулю, однако этот модуль не берёт на себя всю работу самостоятельно; напротив, он связывается с другими модулями, распределяет задачи между ними, и каждый модуль выполняет часть работы, обмениваясь результатами вычислений через коммуникацию. Конечный результат вычисления предоставляется одним или несколькими модулями. В отличие от системы с большим процессором и большой памятью, здесь вычисления действительно будут параллельными. Одна задача будет разделена на множество подзадач, каждая из которых будет обрабатываться отдельными модулями одновременно.Одним из ключевых факторов снижения эффективности вычислительной системы с большим процессором и большим объёмом памяти является разделение вычислений и хранения данных. В одном участке памяти хранятся данные для вычислений; ЦПУ должна сначала считывать эти данные из памяти, выполнять над ними какие-либо вычисления вместе с другими данными, а затем заново записывать результат обратно в память. Обычно вычисления выполняются не один раз, поэтому при необходимости использования этого результата ЦПУ снова должна его считать, выполнить вычисление и записать результат. .. Очевидно, этот процесс крайне затратен по времени. Основная причина заключается в том, что эта память может только хранить данные — когда вы сохраните данные, то через год они всё ещё будут такими же! Давайте теперь рассмотрим, как это будет выглядеть в параллельной системе. Здесь нет централизованной большой памяти, но для каждого модуля, который выполняет вычисления, остальные модули могут рассматриваться как "память", адрес модуля — как "адрес памяти". В отличие от обычной памяти, когда один модуль сохраняет данные в определённый "участок памяти", при следующей попытке получить эти данные происходит удивительное событие — данные уже были автоматически вычислены (конечно, фактически вычисления производил другой модуль)!Это я называю "хранение равно вычислению", когда каждый модуль параллельной системы делит задачи на такие мелкие части, что вычисления и хранение сливаются воедино! Это как если бы вы положили сахар и лёд рядом друг с другом — они разделены, но если вы растопите сахар и лёд до микроскопических частиц и поместите их вместе, они соединятся, образуя раствор, где невозможно различить сахар и воду. Симулирование параллельной вычислительной системы с помощью Erlang

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

"Параллельная вычислительная система" готова, но какой вопрос следует за этим? После создания "компьютера" нам нужна операционная система, которая будет работать на этой системе. schem.erl является такой операционной системой.Проектирование schem. erl

Из имени schem. erl можно понять, что он использует синтаксис Scheme, .erl указывает на то, что он работает на параллельной вычислительной системе, созданной с помощью Erlang (далее, когда говорится о модуле, имеется в виду процесс Erlang, а общение — это передача сообщений Erlang и так далее). Отныне мы переходим в параллельную систему, забываем, что это модель, забываем про Erlang! Обычный Scheme был спроектирован для работы на компьютерах с большим процессором и большим объёмом памяти, тогда как schem. erl был спроектирован для работы на параллельной вычислительной системе, что является главным различием между ними. Проектирование schem. erl должно полностью учитывать особенности параллельной вычислительной системы, где весь компьютер состоит из множества модулей, основные вычисления проводятся параллельно, а вычисления и хранение данных происходят одновременно. Структура файла schem. erl в целом схожа с обычным интерпретатором Scheme, основной задачей которого является рекурсивный анализ S-выражений, а также обработка различных базовых случаев. Выбор Scheme вместо других языков обусловлен его простотой, что позволяет легко видеть суть вещей, и достаточной мощностью для создания полнофункциональной системы.В интернете можно найти множество материалов по теме Scheme, однако это не является главной темой данной статьи, поэтому здесь мы не будем углубляться в подробности. Далее будут рассмотрены специфичные особенности schem. erl. Ключевой момент дизайна schem. erl заключается в решении задачи распределения задач. Когда задача требует выполнения определённым модулем, как он делит эту задачу и передаёт её другим модулям? В текущей реализации schem. erl, принцип такого решения следующий: когда модуль сталкивается с выражением, которое является процедурой (procedure), он полностью передаёт эту процедуру другому модулю и ставит маркёр там, где находится эта процедура, затем продолжает выполнять остальные вычисления. Когда необходимо получить значение этой процедуры, этот модуль использует маркёр для чтения значения процедуры. В этом случае либо процедура уже была рассчитана другим модулем, и тогда полученный результат используется для дальнейших вычислений, либо она ещё не была рассчитана, и тогда ждёт завершения расчёта этого модулем прежде чем продолжить вычисление.В приведённом выше тексте есть два ключевых слова: "маркер" и "необходимость". "Маркер" должен быть достаточно информативным, чтобы указывать, какой модуль получил данную процедуру. Это аналогично концепции переменной, которая указывает адрес памяти в обычной компьютерной системе; в реализации schem.erl мы используем pid процесса.

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

1. Когда вычисление доходит до процедуры, и оператор этой процедуры является примитивным оператором (например, +, -, *, / и так далее, встроенными в интерпретатор), то значение этих примитивных процедур (+ proc1 proc2 ...) является необходимым;
2. Когда вычисление доходит до условия if (if ...), его тестовое выражение () если является процедурой, то значение этой процедуры является необходимым;
3. Когда вычисление доходит до последовательности выражений begin (begin proc1 proc2 ...), каждое из которых является процедурой, то значение каждой такой процедуры (proc1, proc2 ...) является необходимым;
4. Когда весь программный код рассматривается как процедура ($schem.erl myapp), значение этой процедуры (myapp) является необходимым.Замечательно отметить, что при внимательном анализе можно заметить, что эти четыре момента являются единственными местами, где действительно требуется последовательность. Только здесь каждый последующий этап вычисления зависит от результата предыдущего этапа. Во всех других случаях вычисления могут и должны выполняться параллельно. Такую систему, которая выполняется последовательно только там, где это действительно необходимо, а во всех остальных случаях выполняется параллельно, называют полностью параллельной системой. Такое различие демонстрирует суть последовательности и параллелизма, находясь на таком низком уровне, мы можем четко различать их, как будто бы через микроскоп высокого разрешения отделяем вещества от примесей. В реализации schem. erl в целом придерживаются принципа полной параллелизации. Однако есть одно исключение: мы говорили, что один модуль будет распараллеливаться между другими модулями только тогда, когда он достигнет процесса. Поэтому если выражение полностью состоит из примитивных операторов, то его не будут распределять параллельно, например, такое выражение (+ (- 2 1) (* 3 4)). Хотя согласно четвертому пункту последовательности здесь (- 2 1) и (* 3 4) должны были бы вычисляться параллельно, но поскольку они являются примитивными выражениями, вычисление этих двух частей в schem.erl происходит последовательно как один модуль.Основная идея такого подхода заключается в том, чтобы учесть реальность: обычно выражения, состоящие исключительно из примитивных операторов, не слишком сложны, поэтому затраты на параллельное распределение могут превышать время самостоятельного вычисления. Но рациональность этого допущения ещё требует проверки.

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

Для наглядности рассмотрим пример параллелизации с использованием schem.erl:

>>> (define (slp) (sleep 1000)) ; для распределения нам нужна процедура

>>> (define (try a b)
        (if (= a 0) 1 b))

>>> (try 0 (slp))    ; немедленный возврат
1
>>> (try 1 (slp))    ; заснуть на 1 секунду
>>>
```Эта часть кода может выполняться на любом интерпретаторе Scheme, однако вы заметите, что в обычном интерпретаторе `(try 0 (slp))` будет спать 1 секунду перед тем, как вернуть значение, хотя условие `(= a 0)` истинно, следовательно, `(slp)` вообще не используется. Это потому, что Scheme вычисляет каждый параметр до того, как передать его в функцию; когда интерпретатор встречает `(slp)`, он просто застревает там, просыпается после 1 секунды и понимает, что заснул зря. В schem.erl же `(try 0 (slp))` сразу возвращает значение, потому что `(slp)` передаётся другому модулю для выполнения, текущий модуль продолжает работу и, встретив `(= a 0)`, возвращает значение немедленно.После просмотра данного примера можно сказать, что если Scheme был бы лениво вычисляемым, он также бы немедленно вернул значение. Какова же разница между schem.erl и ленивой вычислительностью? Посмотрите на следующий пример:

```scheme
>>> (+ (slp) (slp))  ; заснуть на 1 секунду
Конечно, тип данных здесь неверен, мы знаем об этом.
Мы игнорируем ошибку ради демонстрации!
Замените (slp) на (процедуры, которые возвращают число через 1 секунду), если вам неприятно это.

Независимо от того, запускаете ли вы этот выражение в схеме объяснителя с ленивым или нет, перед тем как вернуть ошибку, будет пауза в течение двух секунд. Однако в schem.erl эта пауза составляет всего одну секунду. Теперь вы знаете, что такое параллелизм? Ленивая вычисляемость просто откладывает вычисление, но рано или поздно это должно произойти самому, тогда как параллелизм откладывает вычисление и вообще не требует его выполнения!Если будет создана полностью параллельная нижняя "операционная система", то это означает, что все приложения высшего уровня, написанные на этой "операционной системе", будут автоматически полностью параллелизоваться? Если бы это было так, это было бы замечательно, поскольку можно было бы свободно писать эти приложения, а затем они автоматически становились бы полностью параллельными. К сожалению, это не так. В чем проблема? Она заключается во вторых пунктах из четырёх пунктов последовательности. Эти два пункта конкретизируют содержание, которое определяется человеком, который пишет приложение высшего уровня, а не schem.erl. Например, третий пункт говорит, что schem.erl получает последовательность выражений, таких как (begin (proc1) (proc2) (proc3)), и выполняет их последовательно. Однако конкретное содержание (proc*) определяется пользователем. Поэтому, если пользователь помещает две процедуры, которые могут быть выполнены параллельно, между собой, schem.erl выполнит их последовательно. Таким образом, schem.erl не может автоматически параллелизовать приложения высшего уровня.Что касается четвертого пункта, там тоже есть аналогичная проблема. Нужно просто заменить (процесс1, процесс2, процесс3) на (программа1, программа2, программа3). Здесь различные пользователи одной команды не могут гарантировать наличие последовательности между их программами.

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

int i = 1 + 1;
int j = 2 + 2;
...

Или в Scheme:```scheme (define i (+ 1 1)) (define j (+ 2 2)) ...

Однако обратите внимание: последовательное написание не означает, что это должно выполняться последовательно! Например, две строки выше могут быть вычислены параллельно. В рамках последовательной вычислительной модели сделать такую запись проблематично не является, поскольку эта модель не предоставляет возможность параллельного выполнения и может выполнять только последовательно, как будет написано. Однако в `schem. erl`, если вы запишете это таким образом, `schem. erl` будет считать, что пользователь намеренно указывает на необходимость последовательного выполнения двух процессов, что явно не соответствует намерению пользователя. В последовательной вычислительной модели можно не беспокоиться об этом (ваше беспокойство бесполезно, так как параллелизм недоступен), но в параллельной модели вам следует об этом подумать, так как ваше мышление определяет конечную степень параллелизма вашего приложения. Например, для двух строк кода выше, в `schem. erl` вы не должны писать их последовательно, потому что последовательное написание будет интерпретировано как `(begin (define i (+ 1 1)) (define j (+ 2 2)))`, что представляет собой последовательность, где процессы будут выполняться последовательно. Напротив, вы должны записать его как `(parallel (define i (+ 1 1)) (define j (+ 2 2)))`, чтобы `schem. erl` мог выполнять эти операции параллельно.Таким образом, параллельные нижние уровли системы, такие как `schem.erl`, не могут автоматически параллелировать высокие уровни приложений от имени пользователя, но они предоставляют примитивы, которые побуждают пользователя думать и дают ему свободу выбора реализации. Переход от последовательной обработки к параллельной требует изменения многих устоявшихся взглядов; когда эти изменения произойдут, вы поймете, что это всего лишь один из способов выполнения задачи, а не единственный.---

[1]: Основные характеристики последовательного компьютера включают небольшое количество процессоров и большой объём централизованной памяти; характеристики параллельного компьютера — множество процессоров и распределённой памяти. Для системы компьютеров мы определяем **степень параллелизма как отношение общего количества процессоров к общему размеру памяти (в байтах)**. Это значение находится в диапазоне от 0 до 1, где большее значение указывает на более высокую степень параллелизма системы. Когда степень параллелизма равна 0, система считается полностью последовательной, а при значении 1 — полностью параллельной. Конечно, это крайние случаи, а в реальности переход через определённый порог уже позволяет рассматривать систему как параллельную.

[2]: В современных системах компьютеров такой параллелизм моделируется с помощью временной многопользовательской среды, но на уровне Erlang мы можем рассматривать его как истинный параллелизм.\[3]: Когда вы открываете файл и записываете строки последовательно `(process1)\n(process2)\n(process3)...`, модуль `schem.erl` анализирует этот файл как `(start (process1) (process2) (process3) ...)`, что приводит к последовательному выполнению процессов. Как же следует записывать данные, чтобы `schem.erl` интерпретировал их как `(parallel (process1) (process2) (process3) ...)`? Это требует тщательного дизайна, например, можно заставить `schem.erl` интерпретировать процессы из разных файлов как параллельные; данный дизайн ещё находится в разработке, если у вас есть хорошие идеи, не стесняйтесь делиться ими со мной!