новости
статьи
.software

QNX: многомашинные вычисления

общие соображения

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

Легко заметить, что все такие задачи занимают некоторую промежуточную позицию на шкале, на одном конце которой находятся циклические вычисления, а на другом — итерационные. Т.е. степень успешности распараллеливания обратно зависима от того, насколько исходные данные последующих циклов вычислений зависят от предыдущих.
За годы эволюции идеи распределенной обработки сложились и различные ее реализационные механизмы, все из которых находятся где-то между двумя крайними позициями: сильно связанные многопроцессорные системы, и системы со слабой связью. Классическое выражение 1-й позиции — симметричная многопроцессорная обработка (Symmetric MultiProcessor, SMP). Системы 2-го класса принято относить к кластерным системам.

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

общее описание проекта

В предложенном к рассмотрению проекте предложена иллюстрация реализации кластерных вычислений в системе из нескольких универсальных компьютеров, работающих в OS QNX и объединенных сетью QNET (для реализации QNET достаточно объединение хостов любого рода Ethernet-сетью). Полный текст работающей программной реализации проекта может быть взят на http://shelek.com/club/files/olej/cluster.1.12.tgz.
Идея того, что QNX-хосты, объединенные QNET-сетью, сами по себе уже являются полноценным многомашинным кластером, появилась у меня еще "сколько-то там..." лет назад, еще при начальном знакомстве с QNX, на то время еще то ли 2.ХХ, то ли 4.ХХ. И действительно:

  • каждый QNX-хост обладает собственным микроядром OS;

  • микроядро QNX с одинаковой легкостью обменивается сообщениями уровня микроядра (по схеме Send — Receive — Reply) как с процессами на своем собственном хосте, так и с процессами на удаленных хостах;

  • cтоит "нагрузить" сообщения уровня микроядра целевой информацией для взаимодействия разнесенных частей распределенного приложения ... и кластер готов. 

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

  • не хотелось "погрязнуть" в низкоуровневых механизмах схемы "Send — Receive — 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 параметра в командной строке, например, так:

#./codec s0.txt d0-2.txt key.2.1

где 1-й параметр — имя (текстового) исходного файла, 2-й параметр — имя файла, в который будет записана результирующая последовательность (той же длины), и 3-й параметр — имя файла, содержащего байтовую последовательность ключа. Длина ключа определяется непосредственно из длины файла ключа. Собственно, в тексте codc.cpp, кроме этой рутины (обработки параметров) нет значащих операторов, кроме 2-х строк, в которых и производится считывание ключа из файла в специальную структуру key и кодирование исходной текстовой последовательности inp:
key k( argv[ 3 ] );
char *out = k.code( inp, slen );
Все, что связано со структурой key и процессом шифрования-дешифрования записано в файле coder.h. Объект класса key — это байтовая последовательность ключа (_Uint8t*) и ее длина. Далее, в классе переопределены ряд традиционных операций (инициализация, присвоение, сравнения на "равенство-неравенство" и на "больше-меньше", вывод в поток и т.д.). Определена операция rshift — нахождение ключа "сдвинутого" относительно исходного в сторону увеличения (напомню, ключ может быть достаточно длинным, более того "произвольной" длины, и арифметические "+" и "-" к нему не применимы). 
Из целевых операций на классе key определена операция кодирования текстовой последовательности s длины n (вообще то говоря: байтовой, при декодировании, но здесь имеет место недосмотр):

char* key::code( char *s, unsigned long n ) {
char *r = new char [ n ];
if( r == NULL ) return NULL;
for( unsigned long i = 0; i < n; i++ ) r[ i ] = (char)( (_Uint8t)s[ i ] ^ *( p + i % k ) ); 
return r;
};

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

bool test( const char src[], unsigned long srclen ) {
const char *p = src;
for( unsigned long i = 0; i < srclen; i++, p++ ) { 
if( *p == 'n' || *p == 't' || *p == 'r' || ( *p >= ' ' && *p <= '~' ) ) continue;
return false;
};
return true;
};

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

#./codec s0.txt d0-2.txt key.2.1
#./codec d0-2.txt s0-2.txt key.2.1

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

#./single d0-2.txt 2

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

#time single d0-2.txt 2
#time master d0-2.txt 2

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

key bkey( keylen ), ckey( keylen );
while( ckey.next() != bkey ) {
char *out = ckey.code( inp, slen );
if( test( out, slen ) ) cout << ckey;
delete out;
};

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

1. Понятие критерия принадлежности декодированного результата к интересующему нас множеству (то, что делает функция test) — вообще, ключевое понятие всякого декодирования. Приведенная мной простейшая функция анализирует полученный результат по принципу: каждый байт результирующей последовательности должен принадлежать к множеству англоязычных "печатных" символов (латинские литеры, цифры, знаки препинания, символы пробела и табуляции, перевод и возврат каретки). Естественно, такая критериальная функция забракует русскоязычные тексты! Более того — она может признать приемлемыми несколько результатов: один для истинного ключа, и еще несколько — для ложных, возвращающих "белиберду", но "англоязычную" (это все можно наблюдать на примерах, находящихся в составе проекта). Такая, как показана у меня критериальная функция — это "байтовая" критериальная функция, которая принимает или забраковывает один очередной байт без учета какого либо его контекста. В реальном дешифровании, после побайтного применения такой критериальной функции, к ограниченному подмножеству отобранных кандидатов должна бы применятся "контекстная" критериальная функция (статистика знаков, длины слов и т.д.) ... но в данном проекте меня это уже не интересовало.

2. Уже раньше по тексту я употреблял термины "символьная последовательности" и "байтовая последовательности", и еще неоднократно они будут упоминаться по тексту. Чем они отличаются в этом проекте? Практически ничем (я работаю с байтовым представлением символа, unicode меня в этом проекте не занимает), кроме того, что к "байтовым" последовательностям нельзя применять ни одну из функций группы str... — внутри "байтовой" строки вполне допустим значащий символ ''!

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

bool test( _Uint8t b ) { return b == 'n' || b == 't' || b == 'r' || ( b >= ' ' && b <= '~' ); };
bool key::code( _Uint8t *s, unsigned long n, _Uint8t *d, bool (t*)( _Uint8t ) ) {
for( unsigned long i = 0; i < n; i++ ) if( ! *t( d[ i ] = ( s[ i ] ^ *( p + i % k ) ) ) ) return false; 
return true;
};

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

организация кластера

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

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

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

  • master должен синхронизироваться и дождаться завершения каждого из запущенных agent (почему разумно и "на самом себе" запустить agent — чего ж ждать попусту?);

  • далее он должен получить (собрать) результаты их работы;

  • и представить их на вывод ... так же как это делала программа single. 

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

  • операцию задания работы 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. Все программное обеспечение — в DiskOnChip. Вся взаимосвязь модуля с кластером осуществляется посредством гальванически развязанного Ethernet, т.е. модули могут произвольно "на ходу" как добавляться, так и изыматься из кластера. А программное обеспечение кластера достаточно быстро и легко адаптируется к числу имеющихся "по факту" хостов в системе.

Олег (Olej) Цилюрик
обсудить статью

© сетевые решения
.
.