Редакция 1.04 от 15.11.2002

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

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

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

• Криптоанализ. Для вскрытия криптографированного текста необходимо произвести его восстановление с помощью всех возможных ключей шифрования, и выбрать наилучший результат.
• Информационно поисковые системы - поиск в потоке запросов к больших объёмах данных, при поиске по ключам, или их сложной комбинации.
• Физика сплошных сред: прочностные расчёты и метод конечных элементов, гидро- и электродинамика сплошных сред.
• Радио- и гидролокация в пространственно разнесённых системах: проверка комбинаторно порождаемых гипотез и отождествление отметок целей, полученных на разнесённых в пространстве приёмных пунктах.
• Задачи баллистики.
• Разнообразные алгоритмы из области обработки изображений.
• Множественное вычисление целевой функции в процедурах многомерной нелинейной оптимизации.
• Любые поисковые задачи, особенно комбинаторного свойства, например, на деревьях вариантов. К этому классу принадлежат большинство задач поиска вариантов в пошаговых игровых программах, например, в шахматах.

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

За годы эволюции идеи распределенной обработки сложились и различные её реализационные механизмы, все из которых находятся где-то между двумя крайними позициями: сильно связанные многопроцессорные системы, и системы со "слабой" связью. Классическое выражение 1-й позиции - симметричная многопроцессорная обработка - SMP. Системы 2-го класса принято относить к "кластерным" системам.

В первых, SMP системах - N обрабатывающих процессоров разделяют общие поля внешних устройств, и, конечно и главным образом - поле оперативной памяти. Для реализации этой модели необходимо использование специализированных архитектур взаимодействия процессоров, и специальных chipset поддерживающей электроники. В таких архитектурах оптимальным механизмом разделения работы между параллельными ветвями представляется - разделение на уровне потоков (thread). Собственно, эти требования и привели к массовой реализации механизмов tread в аппаратных платформах (начало 90-х), поддержке абстракций thread в операционных системах (1994-1996), и отражение их в стандартах POSIX (конец 90-х).

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

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

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

Общее описание проекта. В предложенном к рассмотрению проекте предложена иллюстрация реализации кластерных вычислений в системе из нескольких универсальных компьютеров, работающих в OS QNX и объединённых сетью QNET (для реализации QNET достаточно объединение хостов любого рода Ethernet сетью). Полный текст работающей программной реализации проекта может быть взят на cluster.1.12.tgz.

Идея того, что QNX хосты, объединённые QNET сетью, сами по себе уже являются полноценным многомашинным кластером, появилась и меня ещё "сколько то там..." лет назад, ещё при начальном знакомстве с QNX, на то время ещё толи 2.ХХ, толи 4.ХХ. Действительно:

• Каждый QNX-хост обладает собственным микроядром OS;
• Микроядро QNX с одинаковой лёгкостью обменивается сообщениями уровня микроядра (по схеме Send - Reseive - Reply) как с процессами на своём собственном хосте, так и с процессами на удалённых хостах.
• Стоит "нагрузить" сообщения уровня микроядра целевой информацией для взаимодействия разнесённых частей распределённого приложения ... и кластер готов.

Сравните простоту изложенной модели с необходимостью реализации взаимодействия (скажем через TCP/IP) между составными частями кластерного приложения в "традиционных" OS! Забегая вперёд, скажу, что представленный ниже проект по трудоёмкости (объёму) реализации оказывается на 1 или 2 порядка ниже, чем можно спрогнозировать такой же проект, скажем, в Linux. То же, что и в Linux, собственно, и в Windows, с той лишь разницей, что Windows-проект после реализации, в отличии от Linux, скорее всего тут же "зависнет"...

Сдерживало реализацию подобного проекта (помимо всегдашней нехватки времени) следующие соображения:

• Не хотелось "погрязнуть" в низкоуровневых механизмах схемы "Send - Reseive - Reply" обмена сообщениями микроядра. А более высокоуровневый и единообразный механизм был формализован и предложен, начиная с QNX RTP 6.0, в виде технологии "менеджера ресурса".
• В ранних реализациях QNX 6.Х возможности команды удалённого запуска процессов "on" были реализованы с ошибками. Только начиная с QNX Momentics 6.2 команда "on" работает в достаточном соответствии со своими спецификациями.

(В связи с последним пунктом интересно отметить: когда я реально выполнял уже построенный проект в QNET сети, в которой присутствовал один хост с "залежалой" QNX 6.1, то описываемый кластер в ходе запуска определил в качестве доступных к использованию хостов только N-1.)

В том проекте, который представлен на рассмотрение, содержится, собственно, 2 задачи:

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

 Рассмотрим их по порядку.
Целевая задача. В качестве целевой задачи следовало выбрать задачу одного из классов, которые хорошо распараллеливаются, и которые перечислены выше. Я выбрал для демонстрации кластерной обработки задачу криптоанализа - поиск ключа шифрования, которым криптографирован неизвестный текст, образец которого мы имеем. В целом, вся затея очень напоминает то, что делается в хорошо известном проекте Distributed.net, с той лишь разницей, что они анализируют криптостойкость известных и хорошо себя зарекомендовавших алгоритмов, а я использую простейший алгоритм криптографирования: XOR-свёртку с неизвестным ключом.

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


- где 1-й параметр - имя (текстового) исходного файла, 2-й параметр - имя файла, в который будет записана результирующая последовательность (той же длины), и 3-й параметр - имя файла, содержащего байтовую последовательность ключа. Длина ключа определяется непосредственно из длины файла ключа. Собственно, в тексте codc.cpp, кроме этой рутины (обработки параметров) нет значащих операторов, кроме 2-х строк, в которых и производится считывание ключа из файла в специальную структуру key и кодирование исходной текстовой последовательности inp:

Всё, что связано со структурой key и процессом шифрования - дешифрования записано в файле coder.h - именно так, без .cpp - да простят меня блюстители нравов и стиля программирования - всё, что касается целевой задачи написано inline-включением. Объект класса key - это байтовая последовательность ключа (_Uint8t*) и её длина. Далее, в классе переопределены ряд традиционных операций (инициализация, присвоение, сравнения на "равенство-неравенство" и на "больше-меньше", вывод в поток и т.д.). Определена операция rshift - нахождение ключа "сдвинутого" относительно исходного в сторону увеличения (напомню, ключ может быть достаточно длинным, более того "произвольной" длины, и арифметические "+" и "-" к нему не применимы).

Из целевых операций на классе key определена операция кодирования текстовой последовательности  s длины n (вообще то говоря: байтовой, при декодировании, но здесь имеет место недосмотр):

Кроме класса key в coder.h определена только единственная операция - тестирование полученной декодированием байтовой последовательности на принадлежность к "текстовым строкам":

Для упрощения отработки выбран именно симметричный алгоритм шифрования - дешифрования: двукратное применение программы codec должно возвращать нас к исходному виду шифруемого файла:


После таких манипуляций файлы s0.txt и s0-2.txt должны оказаться абсолютно идентичными.

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


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


Целесообразно заглянуть в текст программы single.cpp, чтобы позже к этому не возвращаться в более сложном многопроцессорном исполнении. Собственно, в содержательной части, представляет интерес только вот это "ядро" программы:

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

Некоторые заключительные комментарии, чтобы нам больше не приходилось дальше вообще возвращаться к рассмотрению целевой задачи:

• Понятие критерия принадлежности декодированного результата к интересующему нас множеству (то, что делает функция test) - вообще, ключевое понятие всякого декодирования. Приведенная мной простейшая функция анализирует полученный результат по принципу: каждый байт результирующей последовательности должен принадлежать к множеству англоязычных "печатных" символов (латинские литеры, цифры, знаки препинания, символы пробела и табуляции, перевод и возврат каретки). Естественно, такая критериальная функция забракует русскоязычные тексты! Более того - она может "признать приемлемыми" несколько результатов: один для истинного ключа, и ещё несколько - для ложных, возвращающих "белиберду", но "англоязычную" (это всё можно наблюдать на примерах, находящихся в составе проекта). Такая, как показана у меня критериальная функция - это "байтовая" критериальная функция, которая принимает или забраковывает один очередной байт без учёта какого либо его контекста. В реальном дешифровании, после побайтного применения такой критериальной функции, к ограниченному подмножеству отобранных кандидатов должна бы применятся "контекстная" критериальная функция (статистика знаков, длины слов и т.д.) ... но в данном проекте меня это уже не интересовало.
• Уже раньше по тексту я употреблял термины "символьная последовательности" и "байтовая последовательности", и ещё неоднократно они будут упоминаться по тексту. Чем они отличаются в этом проекте? Практически ничем (я работаю с байтовым представлением символа, unicode меня в этом проекте не занимает), кроме того, что к "байтовым" последовательностям нельзя применять ни одну из функций группы str... - внутри "байтовой" строки вполне допустим значащий символ ''!
• Сразу хочу подчеркнуть, что функции code() & test() сделаны наихудшими с точки зрения эффективности: code для каждой операции динамически выделяет буфер результата, кроме того, для любого значения ключа code сначала делает полную дешифрацию, и только после этого - результат передаётся критериальной функции test. Если кого-то заинтересует эффективная реализация, то это должно было бы быть нечто такое:

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


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

• с помощью инициирующей программы master на каждом хосте сети (включая и тот, на котором выполняется master) запустить другую автономную программу agent но передать ей только часть работы: диапазон ключей ("от и до") которые должен отработать этот хост;
• хорошо бы ещё, чтоб master выделял диапазон обработки ключей каждому хосту не "поровну", а предварительно "попросив" этот хост сообщить производительность своего процессора, и раздать работу пропорционально производительности каждого;
• master должен синхронизироваться и дождаться завершения каждого из запущенных agent (почему разумно и "на самом себе" запустить agent - чего ж ждать попусту?);
• далее он должен получить (собрать) результаты их работы;
• и представить их на вывод ... так же как это делала программа single.

Из этой постановки уже видно, что программы master и agent должны достаточно плотно кооперироваться, и пересылать друг другу данные в обоих направлениях, пользуясь транспортным механизмом сообщений уровня микроядра. Какой самый простой, отработанный и высокоуровневый механизм обработки сообщений микроядра? Конечно же - менеджер ресурса! Т.е. в качестве agent мы пишем менеджер ресурса, причём - это тот не столь частый случай в практике, когда нам абсолютно не нужен многопотоковый менеджер, и нас вполне устроит однопотоковый.

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

• операцию задания работы master будет осуществлять операцией write(), причём, в качестве буфера данных он будет передавать agent-у последовательности 2-х ключей (начального и конечного), т.е. если работа идёт с ключами длины keylen, то write() будет осуществлять передачу буфера длины 2*keylen;
• ожидать получения результата от agent master будет на обычной блокирующей операции read(), а agent возвратит буфер длины N*keylen, где N - может быть и 0;
• поскольку master должен ожидать read() от многих хостов, то последовательность write() - read() для каждого доступного хоста должна быть выполнена в отдельном потоке (thread - забегая вперёд отмечу, что синхронизация thread далее будет сделана на барьере pthread_barrier_t);
• master-у нужны ещё некоторые вспомогательные операции приёма-передачи информации agent, все они сделаны на devctl() (все эти команды определены в comand.h):
  
  • DCMD_CLUST_STS - по этой команде master передаёт agent-ам сетевое (т.е. в форме /net/host/...) имя файла-источника для декодирования, получив эту команду agent средствами QNET загружает содержимое источника к себе в буфер, и далее в источнике не нуждается (направление передачи данных - к agent);
  • DCMD_CLUST_STK - команда, которой master передаёт текущую использующуюся длину ключа (направление передачи данных - к agent);
  • DCMD_CLUST_GTF - команда запроса частоты процессора, на котором работает agent (направление передачи данных - от agent);

Всё, с процедурами взаимодействия - всё ясно, строим менеджер. Менеджер находится в файле agent.cpp, и в нём нет совершенно ничего интересного (ну, типовой такой dispatch-менеджер, скопированный из HELP QNX), за исключением нескольких деталей:

• менеджер agent регистрирует префикс пути /dev/agent на своём хосте;
• программа agent является не только менеджером ресурса, это fork-ающая программа, которая своим дочерним процессом создаёт менеджер, и остаётся активным, а родительский процесс благополучно завершается;
• как уже понятно, в менеджере устанавливается 3 обработчика для операций read(), write(), devctl() - все обработчики сообщений находятся не в основном файле (agent.cpp), а в отдельном файле обработчиков (agefun.h - agefun.cpp);

Всё остальное уже предельно просто. Некоторых минимальных комментариев заслуживает только текст запускающей программы master (master.cpp):

• начиная работу master читает QNET каталог /net (это - значение по умолчанию, если вы используете другой - вам придётся несколько исхитриться). Если он не находит /net, то это означает, что npm-qnet.so просто не подмонтирован к io-net и мой master пытается подправить ситуацию (но это - дело вкуса).
• далее программа перечитывает содержимое /net, для определённости описания будем считать, что она там находит имена хостов: alpha, beta, gamma, при чём будем считать, что alpha соответствует имени локального хоста, на котором и запущена программа master.
• программа строит односвязный список хостов (class SutList), в котором каждый доступный хост будет представлен элементом списка (class Sutelite). В этом есть достаточно глубокий смысл! Первоначально я (пересчитав хосты в /net) создавал динамический массив хостов, но динамический список - гораздо глубже, и вот почему. QNET - "устойчивая" сеть (в отличие, скажем, от IP), в которой крайне просто сигнализируется потеря канала (по коду возврата read(): кто пытался обрабатывать разнообразные ошибки канала в TCP - меня поймёт, об UDP - я просто не хочу говорить...). Последующие open() позволяют восстановить трафик сразу же по восстановлению канала (это - очень важно, и все эти свойства QNET я перепроверял и тестировал сам). А значит - при использовании динамического списка, master может поддерживать в нём только "актуальные" хосты: вы можете добавлять или убирать хосты "на ходу" работы кластера, но он будет распределять работы только на те хосты, которые ему реально сейчас доступны.
• далее master выполняет команду "on" для каждого имени хоста в его связном списке с целью запустить менеджер ресурса agent на этом хосте. Здесь есть одна тонкость: первоначально я хотел "заставить" master выполнить "дословно": on -f[host] agent ... но! Эта команда благополучно выполняется на всех хостах, кроме ... собственного, локального (в нашем случае - alpha). Достаточно продолжительные эксперименты меня ни к чему не привели, и эту особенность "on" я пока могу относить только к "артефактам"... Поэтому, перебирая хосты, master анализирует их "локальность", и для своего хоста выполняет: on -n[host] agent (ключиком отличается ...).  Конечно, я мог бы просто для локального хоста выполнять просто ./agent , но меня всегда привлекает симметричность
  оно всегда потом где-то скажется. (Я действительно в моём master использую операторы типа: system "on -nalpha agent", а не spawn() - это сделано сознательно: для простоты и наглядности. Как от system "on ..." перейти к spawn() - дело техники, и прекрасно описано в статье Дмитрия Алексеева на qnx.org.ru).
• после предыдущего пункта на каждом хосте в списке master появляется "драйвер" /dev/agent.
• master выполняет open() поочерёдно ко всем именам /net/[host]/dev/agent и сохраняет файловые дескрипторы в соответствующих элементах Sutelite. Всё! Связь установлена, и я могу делать с хостами всё, что вздумается!
• master запрашивает "по списку" devctl( DCMD_CLUST_GTF, ... ) - тактовую частоту процессоров,на которых работают хосты, agent-ы отвечают ему, выполнив на своих процессорах: SYSPAGE_ENTRY( qtime )-]cycles_per_sec ...
• далее master выполняет для всех поочерёдно devctl( DCMD_CLUST_STS, ... ) и devctl( DCMD_CLUST_STK, ... ), сообщая всем хостам: "работаем" файл такой-то, с такой-то длиной ключа.
• после этого, в цикле, запускаются thread-ы для каждого из хостов выполняющие write( ... ) - диаппазон ключей поиска согласно производительности хоста, и ожидают read( ... ) - результатов этого поиска.
• master, присинхронизировавшись на барьере barrier с завершением работы всех хостов, собирает результаты "в кучу", и представляет их на вывод.

Всё, проще не бывает. Весь текст многомашинного кластера - порядка 300 строк кода (agefun.cpp + master.cpp, всё остальное - либо целевая задача coder.h, либо типовой менеджер ресурса из HELP - agent.cpp).

Кластер и "живучесть" системы.

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

В чём "тонкое" место приведенного в проекте кластера? В программе master - синхронизаторе работы системы (заметьте ещё раз - во время активной работы хостов сам синхронизатор - пассивен, и на его хосте работает agent, как и на всех других хостах).

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

• только один master из всех был активен. Какой из них - это должно определяться в результате некоторой состязательной процедуры, которая должна проводиться:
  
  • при начальной загрузке системы
  • при обнаружении (по тайм-ауту), что последний активный master - "мёртв".
  Например, каждый из master на различных хостах может уведомлять прочие хосты о своей готовности, хорошо бы, если временные задержки "оживания" хостов - были заведомо различающимися. Здесь я мог бы предложить рассмотреть очень "смешной" способ: поскольку кластер - сугубо сетевое творение, использовать в качестве задержки "оживания" хоста ... MAC-адрес его сетевого адаптера (вот уж точно не совпадут!).
• каждый не активный master - пассивно выполняет прослушивание команд "активного" master с целью кратчайшей реакции на обнаружение работоспособного master в системе.

Такая динамическая кластерная система могла бы стать особенно интересной именно в QNX-исполнении, учитывая embedded-возможности этой OS. Каждый модуль кластера вполне мог бы реализовываться на каком либо умеренно мощном PC, скажем AMD 5x86 форм-фактора PC/104. Всё программное обеспечение как QNX, так и целевого кластера - в DiskOnChip. Вся  взаимосвязь модуля с кластером - осуществляется посредством гальванически развязанного Ethernet, т.е. модули могут произвольно "на ходу" как добавляться, так и изыматься из кластера. А программное обеспечение кластера достаточно быстро и легко адаптируется к числу имеющихся "по факту" хостов в системе.

Источники дополнительной информации:
[1] - "Writing Resource Manager" в HELP подсистеме операционной системы QNX Momentics 6.2.
[2] - Дмитрий Алексеев "Утилита on" - http://qnx.org.ru/docs-devel/on.html
[3] - Дмитрий Алексеев "Получение системной информации" - http://qnx.org.ru/docs-devel/sysinfo.html