Search academic texts

Registration Number

0823U101872, PhD dissertation

Status

Доктор філософії

Date

02-02-2024

popup.evolution

o

Title

Method and tools for packet parser design for FPGA

Author

Oleksii Molchanov,

popup.head Alexei M. Romankevich
popup.opponent Serhii Hilgurt
popup.opponent Volodymyr Opanasenko
popup.review Inna V. Stetsenko
popup.review Yaroslav Klyatchenko

Description

Поширення інформаційних технологій нерозривно пов’язане з розвитком комп’ютерних систем, елементної бази, на якій вони базуються, та удосконаленням підходів до вирішення задач в галузі інформаційних технологій (хмарні обчислення, Інтернет речей, системи супутникового зв’язку тощо). Від ефективності функціонування програмного та апаратного забезпечення комп’ютерних систем залежить і ефективність рішень таких задач. Однією з задач, що вирішують інформаційні системи, є обробка мережевих пакетів, під якою мається на увазі лексичний та синтаксичний аналізи мережевих пакетів, тобто, їх граматичний розбір, та отримання даних із них. В залежності від формату пакету та від сталості цього формату, розбір мережевих пакетів відбувається програмними, апаратними або комбінованими системами розбору. Наприклад, повідомлення у форматі XML, який є сталим і регламентується стандартизованими версіями, широко використовуються у вебсервісах. Проте, окрім коректності самого формату, XML-документи також мають відповідати деякій граматиці, визначеній певною мовою опису граматик XML. Набори граматик XML у вебсервісах, які можуть вміщувати тисячі екземплярів, часто змінюються, що призводить до обмеженості, або неможливості використання ефективних суто апаратних систем обробки XML-документів. Тому найчастіше розбір XML-документів відбувається програмно. У середовищі хмарних обчислень розбір XML-документів вимагає значних обчислювальних ресурсів. Деякий час тому він споживав майже 30% часу обробки запитів до серверів. Окрім того, кількість транзисторів у процесорах більше не змінюватиметься так швидко, як це було раніше згідно з законом Мура та законом Деннарда. Відповідно і продуктивність суто програмних систем не може в подальшому бути збільшена завдяки оновленню процесорів на серверах з тією ж швидкістю, яка була раніше, що може призвести до поступового збільшення часу затримки при обробці запитів до серверів. Об’єктом дослідження є процес граматичного розбору речень формальних мов. Предметом дослідження є методи, способи і засоби апаратного та програмно-апаратного граматичного розбору мережевих пакетів, а також методи і засоби проєктування таких засобів. Метою дисертаційної роботи є розширення можливостей з переналаштування апаратних засобів граматичного розбору мережевих пакетів на роботу за іншим алгоритмом розбору або підтримку іншого набору граматик з досягненням співмірних показників швидкодії та апаратних витрат у порівнянні з існуючими апаратними парсерами на прикладі розбору XML-документів. Наукова новизна дисертаційної роботи полягає в наступному: 1. Запропоновано вдосконалення методу проєктування апаратних засобів для розбору мережевих пакетів на основі стекових скінченних автоматів. Вдосконалений метод відрізняється від наявних використанням програмно-апаратного представлення скінченного автомату граматичного розбору, що дає змогу динамічно змінювати алгоритм або множину граматик, за якими відбувається розбір, протягом короткого терміну. 2. Вперше запропоновано спосіб проєктування стекових архітектур для програмно-апаратної реалізації граматичного розбору, який відрізняється тим, що до базової стекової архітектури процесора з двома стеками включаються додаткові стеки і спеціальні команди, завдяки чому досягається пришвидшення граматичного розбору у порівнянні з програмною реалізацією. 3. З використанням запропонованого методу проєктування вперше створено обчислювальну структуру парсера, яка на відміну від відомих структур крім компілятора граматик містить спеціалізований стековий процесор, що реалізує адаптований для програмно-апаратного виконання алгоритм граматичного розбору XML-документів для заданого набору граматик, за рахунок чого забезпечується можливість динамічної зміни алгоритму розбору або набору підтримуваних граматик. 4. Вперше отримано аналітичне представлення розрахунку швидкодії програмно-апаратного парсера, спроєктованого за запропонованим методом, яке дає змогу виконати оцінку кількості тактів виконання розбору, в залежності від набору підтримуваних граматик. Практична цінність результатів дисертації полягає в тому, що використання розробленого методу для проєктування спеціалізованих обчислювачів для програмно-апаратного граматичного розбору XML-документів на базі ПЛІС як на серверах, так на вузлових пристроях Інтернету речей, дасть змогу скоротити як час проєктування парсерів мережевих пакетів, так і обробку XML-документів, а також зменшити апаратні та енергетичні витрати, необхідні для обробки цих документів. Розроблена за новим способом стекова архітектура SM16 і однойменний стековий процесор разом з новими засобами автоматизованої розробки парсерів пакетів дають можливість ефективної реалізації процедур розбору і аналізу XML-пакетів та можуть бути застосовані у інших застосунках.

Registration Date

2023-12-18

popup.nrat_date

2024-02-06