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

Во введении обосновывается актуальность темы диссертации,
выделяются и формулируются цели и задачи исследования, показана научная новизна, теоретическая и практическая значимость результатов, описывается
структура диссертационной работы. Изложены основные положения, выносимые на защиту, соответствие содержания диссертации паспорту научной специальности, степень достоверности и апробация результатов.
В первой главе содержит литературный обзор по теме диссертации. Представлены результаты анализа публикаций, касающихся особенностей формирования и обработки сообщений на основе входящих в их состав идентификаторов в современных информационно-вычислительных системах. Определена целевая характеристика устройств обработки данных – производительность – количество формируемых множеств сообщений в единицу времени:
ETNUT N U1 (1) eq  dec dec comp comp 
где: Tdec – длительность операции декодирования сообщения, Tcomp – длительность операций формирования и сравнения идентификаторов, Ndec(|U|) – число операций декодирования сообщений, являющееся функцией мощности множества сообщений U, поступающих в устройство в единицу времени, Ncomp(|U|) – число операций сравнения идентификаторов (функция от |U|).
Если определить число сообщений как произведение числа формируемых множеств K на число сообщений M, относящихся к каждому множеству, которые поступают в устройство в единицу времени, то для известных методов, ориентированных на обработку единичных сообщений, производительность определится как:
1
E1 T KMT KM. (2)
eq dec comp
Для методов, ориентированных на обработку групп сообщений:
 1
KM , (3)
eq eq обрабатывающих группы сообщений: уменьшение времени Tcomp выполнения операции формирования и сравнения идентификаторов, использование параллельно работающих модулей формирования множеств сообщений, использование алгоритмов сравнения идентификаторов, сложность которых
O(K·M) меньше сложности известных решений.
Вторая глава диссертации посвящена созданию метода и алгоритмов
обработки данных на основе идентификаторов ограниченной длины. Сообщения, относящиеся к множеству сообщений адресата, кодируются на основании некоторого идентификатора данного множества ΩA. Каждое сообщение Si содержит в себе поле идентификатора SiС, содержащее проверочные данные, по которым осуществляется проверка корректности обработки сообщения, а также определяется принадлежность сообщения конкретному множеству. Его содержимое есть функция следующих данных: ΩA – идентификатора множества сообщений, содержимого информационной
части Sinf предыдущего сообщения и некоторого идентификатора μ i
E2  T KT N 
comp

eq dec comp
Отсюда сформулированы основные подходы к повышению производительности (увеличению соотношения E2 / E1 ) приёмников,
i
сообщения, позволяющего его выделить среди всех сообщений целевого множества (определить его номер ip в анализируемой группе сообщений):
SC  F A,Sinf,ip |  F A,Sinf,ip |F A,ip   
(4) где F – функция формирования приёмником имитовставки из слов Sinf
i 1 i1 i 1 i1 2
и ΩA (необратимое преобразование); F2 – выполненное приёмником кодирование числа ip на основе слова ΩA (обратимое преобразование), | – операция конкатенации двух слов.
Полученное сообщение будет идентифицировано как ip–е сообщение источника, если будет истинным следующее логическое выражение:
 F1A,ip  SC / FA,Sinf,ip 2 i i i 1 i1 
слова
(5)
μ по
где F 1 – выполняемое приёмником декодирование 2
i идентификатору множества ΩA, ip – число полученных сообщений обрабатываемой группы, SiС / μi – результат отделения от слова SiС слова μi. Все полученные сообщения, для которых было выполнено условие (5), буферизируются в основной буферной памяти (ОБП) устройства, затем из них формируется последовательность (цепочка) сообщений фиксированной длины M, для каждого элемента которой верно условие (5). По факту формирования цепочки принимается решение о принадлежности всех её M сообщений
множеству с идентификатором ΩA.
В основе повышения производительности приёмников (см. формулу
(3)) лежит сокращение временных затрат при проверке условия (5). Для этого, вместо многократного чтения из ОБП содержимого информационной
части S inf сообщений и выполнения операций F 1 и F , с помощью
i2
быстродействующей регистровой памяти адресов сообщении (ПАС) устройства организуется хранение следующих слов:
 адреса сообщения в ОБП;
 результата вычисления выражения F A, Sinf , ip 1для данного со-
i
общения для сравнения его за один такт (без предобработки и дополнитель- ных преобразований) с результатом S C   , а также для сравнения с со-
ip 1 ip 1
держимым поля SC сообщения, у которого F -1(ΩA , μ ) = ip +1;
2i
 слова SiС / μi , для сравнения его за один такт с содержимым поля SC
сообщения, у которого F -1(ΩA , μ ) = ip –1. 2i
Для уменьшения вычислительных затрат при обработке сообщений, создан алгоритм управления статусами обрабатываемых специализированным вычислительным устройством множеств сообщений (рис. 1).
p
i 1
Рисунок 1. Алгоритм управления статусами множеств сообщений.
На основании всего сказанного выше можно описать основные этапы разрабатываемого метода обработки данных на основе идентификаторов.
1. Каждому множеству сообщений присваивают статус «анализируемое» или «неактивное». Сообщения проверяются на принадлежность только к множествам со статусом «анализируемое».
2. Для каждого поступающего в устройство сообщения производится операция его декодирования с использованием множества идентификаторов.
3. Результат проверки содержимого сообщения по условию (5) относит его к определённой цепочке каждого множества со статусом «анализируемое». 4. Результат проверки декодированного номера сообщения переводит
множество из состояния «неактивное» в состояние «анализируемое».
5.Если для некоторого множества из состояния «анализируемое» получено граничное сообщение и сформирована единственная цепочка сообщений, то вся такая цепочка относится к данному множеству, а множеству присваивают статус «неактивное», что исключает его из анализа при предобработке данных и позволяет снизить число операций
декодирования поступающих сообщений.
Новизна метода обработки данных заключается в управлении набором
множеств, на принадлежность к которым проверяется каждое поступающее сообщение, что уменьшает аппаратную сложность операционной части устройства за счёт сокращения числа параллельно работающих блоков, выполняющих процедуры анализа принадлежности групп сообщений множествам, и обеспечивает повышение его производительности.
Процедура формирования цепочек сообщений включает отнесение каждого обрабатываемого сообщения к одной из групп w1 – wM сообщений с одинаковым порядковым номером i в цепочке и размещающихся в соответствующем столбце ПАС. После чего цепочки могут формироваться двумя способами:
 параллельным формированием всех цепочек путём выполнения итераций по добавлению во все цепочки элементов из групп w1 – wM;
 формированием каждой цепочки до конца и лишь затем переходом к формированию следующей.
Соответственно, разработаны два алгоритма формирования цепочек сообщений: итерационный, на основе перебора всех сообщений из ПАС, и рекурсивный алгоритма, в котором содержимое столбцов ПАС передаётся в качестве параметров в соответствующую процедуру. На начальном этапе Nchain =1, ichain = 1, iind = 1, k = 1 u1 = {sstart}, где sstart – последнее сообщение предыдущей цепочки множеств (рис. 2).
Рисунок 2. Блок-схема рекурсивного алгоритма формирования цепочек сообщений.
Рекурсивный алгоритм отличается последовательным формированием цепочек сообщений и проверкой условия возникновения ошибки после каждой сформированной цепочки и позволяет при обнаружении более чем одной цепочки длиной M завершить работу, прекратив заполнение регистровой памяти устройства описателями сформированных цепочек. Это позволяет снизить требуемый объём такой памяти.
Третья глава посвящена оценке с помощью математического и имитационного моделирования вычислительной сложности разработанных алгоритмов и ресурсных затрат для их реализации. Исследуемыми параметрами были: размер матрицы регистров ПАС N и M (M определяется как максимальная длина формируемой приёмником цепочки сообщений), разрядность h поля идентификатора сообщения и K – число формируемых множеств сообщений. В основе математической модели процедуры обработки

сообщений было положено представление получения сообщений приёмником в виде пуассоновского процесса. Получена рекуррентная формула для среднего числа сформированных цепочек сообщений при длине цепочки r:
Nr 
pn1,r,r  p n1,r1 

2h k 12h Nk . (6)

i0  k1 k!
N KkeK 
ch
ch
Ck N1

  
При r = M получим функцию плотности вероятности сформированных цепочек. Итоговая формула для вероятности возникновения ошибки pfl(M) отнесения цепочки сообщений к множеству получена, исходя из вероятности выполнения условия (5) для хотя бы одной
числа из n1,M–1 цепочек. Она является вероятностью совместного наступления
ch
независимых событий:
ch
Вероятность powfl(M) ошибки нехватки размеров ПАС, при которой
число сообщений с одинаковым значением μi превышает число N строк в матрице регистров ПАС, определится как:
  M m
fl
ch

 1,M 

 n1,M 1
1,M  h ch
pM pn 112n .
 (7) 
p M,N1 1  pn ,M . (8)
 owfl  

ind n1,MN

ch
Общая же вероятность возникновения ошибки perr(M, N) определится
как вероятность наступления хотя бы одного из описанных выше событий.
perr M,N11 pfl M1 powfl M,N. (9)
Полученное соотношение позволяет определить зависимость между количеством столбцов M и строк N в ПАС при требуемых значениях вероятности ошибки perr (рис. 3).
Рисунок 3. Зависимость между количеством столбцов M и строк N в матрице ПАС A) perr = 0.25 B) perr = 0.15 C) perr = 0.1.
Исходя из данных графиков, можно утверждать, что целесообразное соотношение между количеством строк N и столбцов M регистровой памяти ПАС лежит в диапазоне 1.5 … 2.0. Большее соотношение нецелесообразно,

так как влечёт лишь увеличение объёма ПАС без уменьшения вероятности возникновения ошибок при обработке сообщений и их идентификаторов.
Затраты внутренней регистровой памяти устройства возникают, во- первых, из-за необходимости хранить адреса сообщений в ПАС, а во-вторых, из-за необходимости для каждой сформированной цепочки хранить номера регистров ПАС, её составляющих. Размеры ПАС выбираются исходя из требуемой протоколом передачи данных достоверности (perr) и полученных выше соотношений. На основе формулы (6) определяется число регистров, требуемых для хранения сформированных цепочек. Проведённые серии математических экспериментов позволили определить целесообразный диапазон для данной характеристики как 20 … 100 (рис. 4).
Рисунок 4. Зависимость числа сформированных цепочек сообщений Nchain от числа строк ПАС N и K=30. 1) M = 10, 2) M = 15, 3) M = 20.
Для оценки влияния типа алгоритма формирования цепочек сообщений на число необходимых регистров внутренней памяти устройства и число операций, выполняемых таким устройством, оба алгоритма были реализованы с помощью имитационной модели. Получена зависимость Nchain среднего числа формируемых устройством цепочек для каждого алгоритма от числа анализируемых сообщений |U| и размера поля служебных данных h (рис. 5). Установлено, что тип алгоритма незначительно влияет на вычислительную сложность процедуры формирования цепочки сообщений: выигрыш в пользу рекурсивного составляет менее 10%.
Рисунок 5. Зависимость Nchain среднего числа цепочек от числа анализируемых сообщений |U| при h = 5.
Числа цепочек, формируемых при использовании рекурсивного алгоритма, снижается на величину до 30% (при вероятности возникновения ошибок perr>0,15) от числа цепочек, формируемых при использовании итерационного, что определяет выбор рекурсивного алгоритма в качестве основного алгоритма обработки данных на основе идентификаторов.
Создана математическая модель оценки числа операций проверки условия (5) при использовании рекурсивного алгоритма обработки данных и получена зависимость отношения T/M числа сравнений к длине цепочки сообщений от числа формируемых множеств сообщений K . Установлено, что данная зависимость является линейной: T/M = 1,5…2.0 ×K.
Четвёртая глава посвящена разработке специализированного вычислительного устройства обработки данных на основе идентификаторов (СВУОДОИ). Структурная схема СВУОДОИ приведена на рис. 6, где сплошной линией показаны направления передачи данных, пунктирной – управляющих и информационных сигналов. Блоки устройства обмениваются данными по двум внутренним шинам: данных сообщения и адреса сообщения в ОБП.
Рисунок 6. Структурная схема специализированного вычислительного устройства обработки данных на основе идентификаторов (СВУОДОИ).
Микропрограммное устройство управления (МПУУ) управляет взаимодействием всех блоков устройства через внутренние шины, вместе с блоком предобработки сообщений осуществляет управление работой блоков анализа сообщений, закрепляя за ними функции определения принадлежности сообщений конкретному множеству. Также МПУУ обеспечивает синхронизацию работы независимых модулей СВУОДОИ.
Блок сопряжения с интерфейсом обеспечивает преобразование сигнала из канала связи в параллельный код сообщения, пригодный для обработки узлами СВУОДОИ. Блок буферизации сообщений состоит из ОЗУ ОБП и схемы управления адресами, которая обеспечивает формирование адреса для очередного записываемого в буфер сообщения, а также поддержание битовой карты занятых областей ОБП.
Несколько независимых блоков анализа сообщений, подключаемых к общей шине, обеспечивают формирование содержимого регистровой памяти адресов сообщений (ПАС) для нескольких множеств. После формирования цепочки сообщений, их адреса передаются на шину адреса, и производится их обработка в соответствии с определёнными для множества правилами.
Функциональная схема одного блока памяти адресов сообщений, работающего в связке с блоком анализа сообщений, приведена на рисунке 7. Она представляет собой матрицу регистров M на N , в которые записывается
i
адрес сообщения в ОБП (с шины адреса), а также слова F A, Sinf , ip 1 и
p
S C   (с шины данных). Выбор регистра хранения происходит по сигналу
ii
от дешифраторов DC 1 – DC M, на которые поступает двоичный номер регистра либо из блока анализа сообщений (при анализе сообщений), либо со считающих регистров CRg 1 – CRg M (при заполнении ПАС).
Рисунок 7. Функциональная схема памяти адресов сообщений.
Для оценки характеристик СВУОДОИ и сравнения их с аналогами, оно было реализовано в системе синтеза и анализа схем Vivado фирмы Xilinx как проект программируемой логической интегральной схемы (ПЛИС). Реализовывалось устройство в виде двух независимых модулей. Первый модуль состоит из блока предобработки сообщений, блока буферизации сообщений и МПУУ. Второй модуль включает в себя блок ПАС, блок анализа сообщений и их независимый блок управления. В одном СВУОДОИ через общую шину объединяются один первый модуль и несколько вторых.
Реализация первого модуля показала, что его схемотехническая сложность составила 3456 логических блоков (LUT Elements) и 114 задействованных блоков ввода – вывода (IOBs). При этом максимальное время распространения сигнала между ножками составило 95 нс. Это время, определяющее длительность такта работы соответствующих частей СВУОДОИ, необходимого для выполнения операции декодирования содержимого поля служебных данных. Сложность второго модуля 4125 логических блоков и 52 задействованных блока ввода – вывода при минимальной длительности такта работы в 16 нс. Более высокая скорость работы схем второго модуля объясняется невысокой сложностью выполняемых им операций сравнения и записи данных в регистры.
Исходя из полученных данных, пригодной для реализации СВУОДОИ
является микросхема xc7s75fgga484-1 фирмы Xilinx. На основании
полученных временных характеристик работы различных частей устройства
получены временные характеристики работы самого СВУОДОИ, которые
сравнивались с аналогичными характеристиками для известных решений. В
соответствии с полученным средним числом тактов работы каждого модуля
и длительностью соответствующих тактов были получены зависимости
между производительностью разрабатываемого СВУОДОИ E2 и eq
производительностью известных решений E1 (рис. 8). eq
Рисунок 8 – График зависимости отношения производительности разрабо- танного СВУОДОИ к производительности устройства, обрабатывающих от- дельные сообщений, от длины цепочек сообщений M.
Реализация метода обработки данных на основе идентификаторов ограниченного размера в разработанном СВУОДОИ, позволяет повысить

число операций обработки сообщений и выработки решений о принадлежности их множествам на 15 – 35 %. Указанное повышение производительности обеспечивается ускорением выполнения операций сравнения содержимого служебных полей и снижением числа трудоёмких операций декодирования данных сообщения.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
Диссертация посвящена решению актуальной научно–технической задачи разработки метода и алгоритмов определения принадлежности групп сообщений адресатам, ориентированных на высокую скорость выполнения при их аппаратной реализации на микроконтроллерах и ПЛИС. Получены следующие результаты:
1. Проведен сравнительный обзор известных методов, алгоритмов и технических средств обработки данных и определения принадлежности сооб- щений конкретному множеству. Показано, что из-за ограниченной пропускной способности каналов связи в некоторых классах современных информацион- но-вычислительных систем накладываются существенные ограничения на размер дополнительных служебных полей сообщений. Это требует при обра- ботке данных использования специализированных методов и средств обработ- ки групп сообщений, повышающих достоверность такой обработки.
2. Разработан метод обработки данных на основе идентификаторов огра- ниченной длины, предполагающий формирование из сообщений логически связанных структур на основе содержимого нескольких битов их служебных полей. Для повышения скорости обработки сообщений метод предусматри- вается сокращение числа множеств, к которым может быть отнесено каждое поступающее сообщение. При этом процедуры обработки данных реализуются в независимых вычислительных блоках устройства, и число таких блоков меньше числа формируемых устройством множеств сообщений.
3. Разработан алгоритм обработки сообщений на основе идентификато- ров и отнесения их к определённым множествам, отличающийся проверкой условия возникновения ошибки после каждой сформированной цепочки со- общений. Это позволяет при формировании цепочек сообщений уменьшить объём задействованной памяти устройства и реализовать память в виде мат- рицы регистров, повысив тем самым скорость выполнения процедур обработ- ки сообщений.
4. Создана математическая модель размещения описателей сообщений во внутренней регистровой памяти специализированного вычислительного устройства обработки данных на основе идентификаторов ограниченной длины, основанная на теории вероятностей и теории случайных процессов, отличающаяся представлением процедур формирования и анализа логически связанных структур сообщений в виде случайного процесса, позволившая оценить требуемый объём регистровой памяти одного вычислительного бло- ка для реализации метода обработки данных. Соотношение между числом строк и числом столбцов матрицы регистров определено как 2:1, что обеспечи-
вает линейную зависимость вычислительной сложности алгоритма от числа формируемых множеств сообщений при вероятности ошибки определения принадлежности сообщения множеству, не превышающей 0,15.
5. На основании созданной имитационной модели реализации метода обработки данных на основе идентификаторов произведена оценка влияния типа алгоритма формирования цепочки сообщений на требуемый объём ре- гистровой памяти устройства. Это позволило за счёт использования рекур- сивного алгоритма формирования цепочек сократить на 30% число регистров в каждом вычислительном блоке устройства.
6. Реализована структурно-функциональная схема специализированно- го вычислительного устройства данных на основе идентификаторов ограни- ченной длины, отличающаяся выполнением длительных по времени опера- ций декодирования сообщений и коротких операций сравнения содержимого дополнительных полей в независимых параллельно работающих модулях. Такое распараллеливание повышает производительность устройства, выра- женную в числе операций обработки сообщений в единицу времени, на 15 – 35 % в сравнении с аналогами, реализующими обработку на основе сравне- ний, выполняемых непосредственно после декодирования сообщений.