Содержание к диссертации
Введение
1 Проблемы обработки данных на основе идентификаторов в современных информационных системах . 14
1.1 Особенности формирования и обработки информации на основе идентификаторов 14
1.2 Математическое и алгоритмическое обеспечение систем обработки сообщений 16
1.3 Известные технические решения, направленные на сокращение затрат при обработке сообщений и их идентификаторов 19
1.4 Особенности реализации процедур обработки данных на основе идентификаторов в условиях ограниченного размера единичного сообщения 27
1.5 Анализ подходов к повышению производительности устройств обработки данных на основе идентификаторов 33
1.6 Выводы по разделу 35
2 Разработка методов и алгоритмов обработки сообщений ограниченного размера 37
2.1 Формальное представление процедуры определения источника сообщений на основе ограниченного размера служебных данных. 37
2.1.1 Организация взаимодействия двух устройств, обменивающихся сообщениями ограниченной длины 37
2.1.2 Влияние ошибок на особенности буферизации памяти и на скорость обработки сообщений 41
2.1.3 Особенности буферизации сообщений 43
2.2 Особенности реализации аппаратной обработки данных на основе идентификаторов 44
2.2.1 Формирование цепочек сообщений одного множества в приёмнике 44
2.2.2 Организация буферной памяти приёмника, обеспечивающая повышение скорости построения цепочек сообщений 45
2.2.3 Ограничение числа вычислительных модулей и блоков памяти при множеств сообщений 48
2.2.4 Формализация метода обработки данных на основе идентификаторов 49
2.3 Синтез алгоритма управления статусами множеств сообщений. 50
2.3.1 Описание алгоритма управления статусами множеств сообщений. 50
2.3.2 Описание алгоритма обработки входящих сообщений 52
2.3.2.1 Варианты реализации алгоритма обработки сообщений 52
2.3.2.2 Итерационный алгоритм формирования цепочек сообщений 53
2.3.2.3 Рекурсивный алгоритм формирования цепочек сообщений 55
2.4 Описание алгоритма кодирования данных сообщения короткой длины 57
2.4.1 Общие принципы обработки сообщений 57
2.4.2 Основные этапы кодирования сообщений 58
2.4.3 Алгоритм необратимого преобразования 58
2.4.4 Используемый алгоритм обратимого преобразования данных 60
2.5 Выводы по разделу 61
3 Исследование характеристик алгоритма обработки данных на основе идентификаторов 63
3.1 Постановка задачи. 63
3.2 Исследование вероятности ошибки определения принадлежности сообщения целевому множеству 64
3.3 Исследование затрат памяти для реализации метода определения источника сообщений 71
3.4 Влияние типа алгоритма для формирования цепочек сообщений на требуемый размер памяти приёмника 74
3.5 Исследование вычислительной сложности алгоритма формирования цепочек сообщений 78
3.6 Выводы по разделу 84
4 Разработка структурно-функциональной организации специализированного устройства обработки данных на основе идентификаторов 86
4.1 Основные функции устройства обработки данных на основе идентификаторов и принципы его структурной организации 86
4.2 Структурная организация специализированного устройства управления обработки данных на основе идентификаторов 87
4.3 Описание функциональных схем отдельных блоков специализированного устройства управления обработки данных на основе идентификаторов 90
4.3.1 Функциональная схема блока предобработки сообщений 90
4.3.2 Функциональная схема блока буферизации сообщений 92
4.3.3 Описание организации памяти адресов сообщений 94
4.3.4 Описание блока анализа сообщений 96
4.3.5 Описание микропрограммного устройства управления 99
4.4 Оценка характеристик разработанного специализированного устройства управления обработки данных на основе идентификаторов 102
4.4.1 Реализация специализированного устройства управления обработки данных на основе идентификаторов с помощью системы автоматического проектирования 102
4.4.2 Оценка быстродействия разработанного специализированного устройства обработки данных на основе идентификаторов 104
4.5 Выводы по разделу 107
Основные результаты работы 109
Список литературы 111
Приложение А 128
Приложение Б 130
- Известные технические решения, направленные на сокращение затрат при обработке сообщений и их идентификаторов
- Организация буферной памяти приёмника, обеспечивающая повышение скорости построения цепочек сообщений
- Исследование вычислительной сложности алгоритма формирования цепочек сообщений
- Оценка быстродействия разработанного специализированного устройства обработки данных на основе идентификаторов
Известные технические решения, направленные на сокращение затрат при обработке сообщений и их идентификаторов
Если рассмотреть класс информационных систем с ограниченным размером передаваемого сообщения, то размер полей служебной информации должен быть минимальным, чтобы сократить информационную избыточность и повысить пропускную способность канала связи [27, 28]. В таких системах все затраты, связанные с необходимостью хранения и обработки дополнительного объёма служебных данных должны быть сокращены, особенно для систем с большим числом взаимодействующих между собой источников и приемников информации.
Известно решение для организации схем сетевого обмена данными между произвольным количеством устройств, взаимодействующих по протоколам с невысокой пропускной способностью, например, устройств интернета вещей [29]. Отнесение каждого обрабатываемого сообщения к определённому множеству происходит за счёт кодирования каждого пакета в паре взаимодействующих устройств на основе некоторой ключевой последовательности, ассоциированной с данной парой. Техническим результатом является возможность достоверного разделения сообщений на непересекающиеся множества в каждом устройстве за счёт применения кодирования, которое обеспечивает также невозможность обработки неправильно декодированных сообщений устройствами. В то же время основным его недостатком является то, что достоверность зависит от размера H дополнительных служебных полей (идентификатора взаимодействующей пары устройств). При этом вероятность совпадения двух идентификаторов определится как:
Кроме того, кодирование, используемое для изоляции множеств сообщений, само по себе не повышает указанную достоверность их разделения. В отличие от изобретения для управления обработкой данных в полосе телевизионного сигнала [30]. В нём контроль блоков обрабатываемой в приёмнике информации осуществляется по результатам кодирования данных кодами с низкой плотностью и контролем чётности. Достигаемая при этом достоверность разделения кадров информации приближается к теоретически определённой границе Шенона для каналов связи с помехами [31]. Но при этом множественность источников данных при высокой сложности кодирования [32] требует высокой аппаратной сложности кодеров и декодеров [33], что для рассматриваемых классов систем, подразумевающих использование энергоэффективных и относительно несложных по схемотехнической реализации приёмников, оказывается затруднено.
Известны способ и техническое устройство для обмена управляющими данными при использовании в информационной системе множества каналов связи [34]. Для того, чтобы не передавать управляющую информацию с помощью дополнительного канала управления, так как это требует использования дополнительных ресурсов (дополнительных преобразований, дополнительных алгоритмов кодирования для расширения спектра сигнала) используется разделение во времени передачи основных данных и дополнительной информации с их последующим мультиплексированием. При небольшом соотношении между размером полезной и служебной информации данный метод позволяет с достаточно высокой производительностью предобрабатывать сообщения, разделяя их на множества с различными правилами дальнейшей обработки. В то же время реализация дополнительных логических каналов передачи данных и дополнительной служебной информации потребует усложнения организации приёмников в части модуля сопряжения с интерфейсом.
Аналогичные операции кодирования используются и в изобретении [35] для придания передаваемых сообщений идентификационной информации. Переменное число циклов операции скремблирования позволяет кодировать сообщения разных источников. Но для высокой скорости выполнения операций декодирования целесообразно использовать комбинационные схемы, а не кодирующие автоматы [36, 37], так как первые позволяют сформировать контрольные последовательности за один так работы кодера. То есть при синтезе схем предобработки данных на основе идентификаторов для обеспечения требуемой производительности выбор функций кодирования может играть существенную роль. При этом если мы говорим об обработке сообщений небольшой длины, требуемые свойства кодов (равномерности частоты встречи выходных слов) [38, 39] могут быть обеспечены использованием достаточно простых наборов арифметико-логических операций.
В разработке [40], предназначенной для использования в системах связи между абонентами и базовыми станциями в режиме множества входов и множества выходов. В основе способа лежит декодирование последовательности сообщений с последующей отправкой подтверждения приема в передающее устройство при успешной передаче. При приёме следующего сообщения и при его декодировании комбинируют его как изолированно, так и с содержимым одного или нескольких предыдущих сообщений. После этого определяют, соответствует ли вся передаваемая группа сообщений последнему декодированному, причем повторное декодирование выполняют, даже если ранее принятые передачи данных уже были успешно декодированы. Если результирующая комбинация успешно повторно декодирована, то формируют сигнал успешной передачи в передающее устройство, и назначают упомянутую следующую передачу данных следующему сообщению, если результирующая комбинация не была успешно повторно декодирована. При подобной организации снижается необходимый объём служебной информации в каждом сообщении, что повышает пропускную способность канала связи. При этом, за счёт снижения объёма дополнительной служебной информации, на основании которой проходит декодирование сообщений, при невысокой пропускной способности канала связи снижает длительность полного цикла «передача – приём - обработка» для каждого сообщения.
В то же время несмотря на то, что система и ориентирована на работу приёмника сообщений с множеством источников, в разработке не уделено внимание росту непроизводительных затрат, связанных с перебором предыдущих сообщений для декодирования очередного сообщения. Кроме того, растёт аппаратная сложность реализующего способ приёмного модуля в части организации мультиплексирования и числа используемых буферов сообщений.
В изобретениях [41, 42] использован схожий с [43] подход формирования для каждого обрабатываемого блока некой метрики. В первом изобретении она рассчитывается с помощью механизма трассировки на основании идентификаторов промежуточных узлов, во втором - путём кодирования данных поступающего пакета на основе некоторой информации, атрибутирующей его источник и содержимого дополнительного служебного поля. В первом способе осуществляют проверку принятого набора сообщений P в блоке анализа на разрешение запрашиваемого взаимодействия с узлом сети РИС согласно таблицы коммутации. Разделение набора сообщений осуществляется в соответствии с содержимым данной таблицы. Далее на узле сети РИС в узле дополнительного анализа осуществляют формирование текущих файлов трассировки на основе выполнения программ при доступе пользователей к информационным ресурсам и сервисам РИС и передача их на блок анализа. На основе имеющихся эталонных файлов трассировки принимается решение о необходимости внесения изменений в таблицу коммутации M. Кроме того при несовпадении эталонных и текущих файлов трассировки осуществляется блокирование обработки сообщений как несанкционированных. В случае же их совпадения сообщения считаются санкционированными и их передача в соответствующее устройство информационной системы продолжается.
Организация буферной памяти приёмника, обеспечивающая повышение скорости построения цепочек сообщений
Результатом вышеприведённых рассуждений является необходимость организации буферной памяти таким образом, чтобы обеспечить повышение скорости выполнения операций анализа сообщений при умеренных затратах оперативной памяти [80]. Как было отмечено выше, для этого необходима косвенная адресация буферизируемых сообщений: все поступающие сообщения хранятся в произвольном порядке в основной буферной памяти (ОБП), а их адреса - в отдельной памяти адресов сообщений (ПАС) [81]. При этом для повышения скорости выбора адресов из ПАС предлагается организовывать её в виде матрицы, когда адрес сообщения представляет из себя две независимые части: порядковый номер ip сообщения в пуле и порядковый номер сообщения в множестве U p (рис. 2.4).
Так как обращение к памяти по времени значительно превышает скорость выбора данных из внутренних регистров современных микроэлектронных устройств [82, 83, 84, 85], то ПАС целесообразно реализовывать в виде набора внутренних регистров. Но подобная организация ограничивает размер ПАС, прежде всего, в максимальном размере множества и.р . Пусть N - максимальный размер множества сообщений с одинаковым порядковым номером: N = max(\Щ), j = 1...М . Размер ОБП в таком случае равен MxNxLs, где Ls - размер сообщения в битах, а размер ПАС MxNx [log2(M N)].
Для сокращения временных затрат, помимо адреса сообщения в ОБП, для каждого сообщения с номером целесообразно хранить два слов:
-результат исчисления выражения FAQA, S1 ,ір) для данного сообщения для сравнения с результатом S - ц , а также для сравнения с содержимым поля S сообщения, у которого F l (Q.A, jLl;.) = iv +1.
- слово sf - ц., для сравнения с содержимым поля Sc сообщения, у которого F l (С1А, ыг.) = ip -1.
Таким образом для хранения описателя одного сообщения требуется количество битов, равное сумме максимальной длины поля Sc и значения [log2(M N)]. Отрицательным последствием внедрения технического решения является возможность переполнения ПАС «по ширине», когда в приёмник в течение передачи одного пула сообщений поступило сообщений с одинаковым номером больше, чем максимальная ширина ПАС N:
Введение подобного ограничения, с одной стороны, увеличивает вероятность возникновения ошибки игнорирования сообщения целевого источника, а с другой - уменьшает вероятность формирования посторонних цепочек о возникновения ошибки определения цепочки целевого источника при получении проверочного сообщения. Целесообразный диапазон параметра N, при котором сумма вероятностей данных ошибок минимальна, может быть установлен в результате математического моделирования процесса получения приёмником сообщений.
При формировании цепочек в качестве описателей сообщений, их составляющих, целесообразно не копировать значения ПАС, а использовать индексы соответствующей позиции адреса в ПАС. Таким образом вместо числа битов, равного произведению М, на сумму длины поля Sc и значения [log2(MN)], мы будем задействовать только M([log2(M)]+ [log2(N)]) битов регистровой памяти.
Исследование вычислительной сложности алгоритма формирования цепочек сообщений
В соответствии с рассматриваемыми методом обработки сообщений, вариантом его аппаратной реализации и алгоритмом обработки сообщений, основные временные задержки будут приходиться на операции сравнения содержимого слов Sf - \ii и Sp - \± , хранящихся в ПАС в соседних столбцах и являющихся частью описателя буферизированных сообщений. Поэтому именно число таких операций сравнения мы выберем в качестве меры сложности реализации алгоритма обработки сообщений.
Сравнение описателей сообщений при формировании цепочек схематично представлено на рисунке 3.9, на котором: w\ - wM+u множества описателей сообщений с одинаковым порядковым номером , щ - uv (см. п. 2.3.2), множества описателей, формирующих цепочку сообщений, v -максимальное число цепочек сообщений в приёмнике. Описатели подмножества wt, сравниваются с описателями множества w;.b которые включены в посторонние цепочки
Эти цепочки формируются от элементов 0… (І–2) цепочки сообщений, которая обозначена нами как часть целевого множества сообщений (эта цепочка отмечена на рисунке увеличенной толщиной линии) и имеют длину (г–1) … 1 соответственно. Их последние элементы, которые и сравниваются, образуют подмножества g0, –i - g –д. Алгоритм формирования цепочек допускает, что множества общем случае пересекаться [125, 126]. Оценку числа выполняемых операций сравнений описателей сообщений будем вести через оценку математического ожидания M[g0,i і] - M[g г–1;1] мощностей множеств g0,i і - g г ід
Пусть от некоторой позиции і= 1 … М цепочки целевого множества сообщений было сформировано \giJ\ дополнительных цепочек длиной j. В этом случае плотность распределения вероятностей случайного числа htj различных кодовых слов, являющихся описателями gi;i конечных сообщений этих цепочек, определится по формуле: где: pg(gi,j) – плотность распределения вероятностей мощности множества gi,j, h – разрядность описателя сообщения, определяющая вероятность выполнения условия (2.3), U – мощность множества анализируемых сообщений, К этим hi,j различным описателям сообщений в следующую позицию цепочек будет добавлено gi,j +1 сообщений из множества wi+1. Плотность распределения этого числа выводится из вероятности совпадения описателей (см. п. 3.2). При этом, для простоты расчетов, мы также как и ранее предположили, что биномиальное распределение числа совпадений описателей выродится при большом числе сравнений gi,j +1 wi+1 в распределение Пуассона [123]: плотность распределения вероятностей случайной величины – мощности множества wi+1.
Так как множество сообщений U представляет из себя совокупность сообщений различных независимых множеств, сформиованных произвольным числом источников, считаем, что случайные величины мощностей множеств wt, i = 1 … п подчинены распределению Пуассона с интенсивностью (U-n)/n:
Рекуррентные выражения (3.9) и (3.10) позволяют получить плотность распределения вероятностей чисел g0,j-1 -#«-1,1. Из плотностей распределения вероятностей получаем выражение для их математических ожиданий:
Общее число сравнений описателей будет равно сумме произведений мощностей множеств wi, i = 1 … n и мощностей объединений множеств g0, i–1 – g i–1,1, i = 1 … n. При этом каждое множество будет дополнено одним сообщением, являющимся частью целевого информационного множества:
Определим математическое ожидание мощности объединения множеств по формуле [124]:
Исходя их рассуждений о том, что множество g W,1 Ug І_2,2 образовано сообщениями, которые принадлежат как g, 1,1, так и g г-_2,2, определим вероятность того, что элемент множества Wi принадлежит множеству gt_1,1 как отношение M[gj_1,1]/M[wj]. По аналогии: для множества g; 2,2 - отношение M[gj_2,2]/M[wj], двум множествам одновременно - M[gj_1,1]M[gj_ 2,2]/(M[w;])2. В этом случае получаем формулу: (3.15)
Применяя её к частям выражения (3.13) и вычисляя значения мощностей множеств, получим итоговое значения математического ожидания числа сравнений хеша h.
График зависимости этого числа (его отношение к длине пула сообщений) от разрядности служебного поля sC и параметра К (который использовался для нахождения мощности множества U) - числа множеств, формируемых устройством, приведён на рисунке 3.10. Анализ полученных зависимостей показал, что в установленном ранее (см. п. 3.3) диапазоне для параметра К: K 2h+1 - отношение Т/М имеет линейную зависимость от К. Для получения численных значений можно использовать коэффициент пропорциональности 1,5…2.0. Как и в случае с числом формируемых приёмником цепочек сообщений, при таком соотношении между параметрами модели мощность множества gi–1,1 … п g0u–1 незначительна, . Основную долю от число операций сравнения описателей составляют операции сравнения с описателями сообщений целевого множества.
С помощью описанной в п. 3.4 имитационной модели было исследовано влияние типа используемого алгоритма формирования цепочек на число выполняемых операций (рис. 3.11). Анализ показал, что тип алгоритма незначительно влияет на вычислительную сложность процедуры формирования цепочки сообщений: выигрыш в пользу рекурсивного составляет менее 10% в области высоких значений ошибки обработки данных. Поэтому в качестве числа операций сравнения мы будем использовать число операций сравнения, выполняемых при использовании простого итерационного алгоритма.
Оценка быстродействия разработанного специализированного устройства обработки данных на основе идентификаторов
На основании полученных выше временных характеристик работы различных частей устройства мы можем получить временные характеристики работы самого СУОДОИ, а также сравнить их с характеристиками известных решений. Как показали результаты исследований, описанных в разделе 3, число типовых операций сравнения при реализации алгоритмов формирования цепочек сообщений зависят от длины цепочки M сообщений, числа множеств K и длины поля служебной информации h. Схемой блока анализа сообщений предусмотрено выполнение одной операции сравнения за 3 такта : такт на чтение одного элемента для сравнения, так на чтение второго элемента и выработку информационного сигнала, один такт на выполнение условного перехода в микропрограмме. Описанная в третьем разделе имитационная модель позволила произвести экспериментальную проверку полученных теоретически зависимостей между трудоёмкостью процедуры формирования цепочки. Результаты трудоёмкости по итогам 1000 экспериментов для каждого набора данных приведены в таблице 4.1.
Поступление каждого сообщения в СУОДОИ сопровождается операцией декодирования, выполняемой блоком предобработки сообщения. Для отправки данных в ПАС проходит два такта: на первом выполняется декодирование данных сообщения в соответствии с текущим идентификатором множества сообщений, на втором – определение содержимого буферизируемых в ПАС слов и передача данных в соответствующий блок устройства. Среднее число сравнений, выполняемых приёмником, будет равно половине числа K множеств сообщений, формируемых СУОДОИ. Таким образом, после получения последнего сообщения в пуле в среднем проходит время, равное сумме времени предобработки, равное 95K нс, и времени, определённому как произведение числа операции сравнения в блоке анализа сообщений на 48 нс – длительность 3 тактов работы БАС.
Для оценки производительности аналогов разрабатываемого СУОДОИ мы считали, что при реализации метода [43] требуется один цикл на декодирование полученного сообщений (95 нс) и один цикл (16 нс) на сравнение полученного результата с целевым значением. Длительности аналогичных циклом мы брали такими же, как и в разрабатываемом устройстве, предполагая, для чистоты эксперимента, использование одинаковых алгоритмов кодирования данных. И это несмотря на то, что авторами в исходных разработках предлагаются более сложные с точки зрения числа выполняемых операций, алгоритмы кодирования сообщений [139]. Число таких операций будет равно половине произведения числа формируемых множеств сообщений K на число сообщений в пуле M (см. формулу (1.4)). Для известных методов мы предполагали определение помимо множества сообщений ещё и позицию каждого сообщения в нём, так как без этого достоверность операции определения принадлежности сообщения у сравниваемых методов значительно отличалась (отличался бы размер дополнительного служебного поля). При этом мы предполагали полный перебор всего набора формируемых множеств и позиций сообщения в нём, а не до первого совпадения (в среднем это уменьшило бы число операций в два раза), так как каждое сообщение должно пройти проверку на принадлежность всем множествам, для более высокой точности выполнения операций обработки данных, так же как это реализовано в нашем устройстве. Приведённые выше рассуждения позволяют получить следующие зависимости между количеством выполненных операций обработки сообщений Eeq, K с-1 в единицу времени для разрабатываемого СУОДОИ и у известных решений, числом формируемых множествах, числом сообщений, для которых принимается решение о принадлежности множеству (рис. 4.7).
Для более наглядного сравнения производительностей разработанного устройства и аналога приведём график отношения производительностью разрабатываемого СУОДОИ Ee2q и производительностью известных решений Ee1 q (рис. 4.8), рассчитанный для определённого числа множеств сообщений. Исследования показали, что число обрабатываемых множеств слабо влияет на указанное отношение производительностей, поэтому график приведён для значения K = 10.
Из анализа графика можно сделать вывод о том, что использование предложенного метода обработки данных на основе идентификаторов ограниченного размера при его аппаратной реализации в разработанном СУОДОИ, позволяет повысить число операций обработки сообщений и выработки решений об их принадлежности его множества на 15 – 35 %. Указанное повышение производительности обеспечено тем, что в диапазонах параметров работы приёмника, при которых частота ошибок формирования множеств сообщенийне превышает 5%, структурно-функциональная организация СУОДОИ предполагает выполнение меньшего числа трудоёмких операций декодирования данных, выполняя вместо этого большее число менее длительных операций сравнения содержимого дополнительных служебных полей.