Метод і засоби проєктування парсерів пакетів для ПЛІС
Вантажиться...
Дата
2023
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім.Ігоря Сікорського
Анотація
Молчанов О. А. Метод і засоби проєктування парсерів пакетів для ПЛІС. — Кваліфікаційна праця на правах рукопису.
Дисертація на здобуття наукового ступеня доктора філософії з галузі знань 12 Інформаційні технології за спеціальністю 123 Комп’ютерна інженерія. Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2023.
Поширення інформаційних технологій нерозривно пов’язане з розвитком комп’ютерних систем, елементної бази, на якій вони базуються, та удосконаленням підходів до вирішення задач в галузі інформаційних технологій (хмарні обчислення, Інтернет речей, системи супутникового зв’язку тощо). Від ефективності функціонування програмного та апаратного забезпечення комп’ютерних систем залежить і ефективність рішень таких задач. Однією з задач, що вирішують інформаційні системи, є обробка мережевих пакетів, під якою мається на увазі лексичний та синтаксичний аналізи мережевих пакетів, тобто, їх граматичний розбір, та отримання даних із них. В залежності від формату пакету та від сталості цього формату, розбір мережевих пакетів відбувається програмними, апаратними або комбінованими системами розбору. Наприклад, повідомлення у форматі XML, який є сталим і регламентується стандартизованими версіями, широко використовуються у вебсервісах. Проте, окрім коректності самого формату, XML-документи також мають відповідати деякій граматиці, визначеній певною мовою опису граматик XML. Набори граматик XML у вебсервісах, які можуть вміщувати тисячі екземплярів, часто змінюються, що призводить до обмеженості, або неможливості використання ефективних суто апаратних систем обробки XMLдокументів. Тому найчастіше розбір XML-документів відбувається програмно. У середовищі хмарних обчислень розбір XML-документів вимагає значних обчислювальних ресурсів. Деякий час тому він споживав майже 30% часу обробки запитів до серверів. Окрім того, кількість транзисторів у процесорах більше не змінюватиметься так швидко, як це було раніше згідно з законом Мура та законом Деннарда. Відповідно і продуктивність суто програмних систем не може в подальшому бути збільшена завдяки оновленню процесорів на серверах з тією ж швидкістю, яка була раніше, що може призвести до поступового збільшення часу затримки при обробці запитів до серверів. Об’єктом дослідження є процес граматичного розбору речень формальних мов. Предметом дослідження є методи, способи і засоби апаратного та програмно-апаратного граматичного розбору мережевих пакетів, а також методи і засоби проєктування таких засобів. Метою дисертаційної роботи є розширення можливостей з переналаштування апаратних засобів граматичного розбору мережевих пакетів на роботу за іншим алгоритмом розбору або підтримку іншого набору граматик з досягненням співмірних показників швидкодії та апаратних витрат у порівнянні з існуючими апаратними парсерами на прикладі розбору XMLдокументів. Для досягнення поставленої мети в дисертації вирішуються такі задачі. 1. Проаналізувати відомі підходи та елементну базу для реалізації граматичного розбору мережевих пакетів. 2. Класифікувати методи вирішення задачі розбору XML-документів, залежно від апаратури та підходів, які використовуються в цих методах. 3. Удосконалити метод проєктування апаратних парсерів мережевих пакетів на основі скінченних автоматів та оцінити його ефективність. 4. Проаналізувати наявні архітектури процесорів. За результатами аналізу запропонувати архітектуру, яка дасть змогу найефективніше реалізувати розбір обраним алгоритмом. Розробити апаратний прискорювач за запропонованою архітектурою. 5. Розробити засоби автоматизованої розробки парсерів пакетів за розробленим методом проєктування апаратних прискорювачів розбору мережевих пакетів. 6. Перевірити ефективність апаратного прискорювача, розробленого за запропонованим методом, для різних граматик XML та провести його порівняльний аналіз із наявними рішеннями. Наукова новизна дисертаційної роботи полягає в наступному: 1. Запропоновано вдосконалення методу проєктування апаратних засобів для розбору мережевих пакетів на основі стекових скінченних автоматів. Вдосконалений метод відрізняється від наявних використанням програмно-апаратного представлення скінченного автомату граматичного розбору, що дає змогу динамічно змінювати алгоритм або множину граматик, за якими відбувається розбір, протягом короткого терміну. 2. Вперше запропоновано спосіб проєктування стекових архітектур для програмно-апаратної реалізації граматичного розбору, який відрізняється тим, що до базової стекової архітектури процесора з двома стеками включаються додаткові стеки і спеціальні команди, завдяки чому досягається пришвидшення граматичного розбору у порівнянні з програмною реалізацією. 3. З використанням запропонованого методу проєктування вперше створено обчислювальну структуру парсера, яка на відміну від відомих структур крім компілятора граматик містить спеціалізований стековий процесор, що реалізує адаптований для програмно-апаратного виконання алгоритм граматичного розбору XML-документів для заданого набору граматик, за рахунок чого забезпечується можливість динамічної зміни алгоритму розбору або набору підтримуваних граматик. 4. Вперше отримано аналітичне представлення розрахунку швидкодії програмно-апаратного парсера, спроєктованого за запропонованим методом, яке дає змогу виконати оцінку кількості тактів виконання розбору, в залежності від набору підтримуваних граматик. Практична цінність результатів дисертації полягає в тому, що використання розробленого методу для проєктування спеціалізованих обчислювачів для програмно-апаратного граматичного розбору XMLдокументів на базі ПЛІС як на серверах, так на вузлових пристроях Інтернету речей, дасть змогу скоротити як час проєктування парсерів мережевих пакетів, так і обробку XML-документів, а також зменшити апаратні та енергетичні витрати, необхідні для обробки цих документів. Розроблена за новим способом стекова архітектура SM16 і однойменний стековий процесор разом з новими засобами автоматизованої розробки парсерів пакетів дають можливість ефективної реалізації процедур розбору і аналізу XML-пакетів та можуть бути застосовані у інших застосунках. Результати дисертації впроваджені в освітній процес кафедри системного програмування і спеціалізованих комп’ютерних систем Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» при підготовці та викладанні курсу лекцій «Архітектура комп’ютерів. Мікроархітектура», а також в лабораторній роботі цього ж курсу. За матеріалами дисертації опубліковано 8 наукових праць, зокрема, 4 наукових статті, з яких 2 статті опубліковано у закордонних фахових виданнях, які реферуються базою Scopus, та 2 статті опубліковано у наукових виданнях, що входить до наукових фахових видань України, і 4 публікації у матеріалах науково-технічних конференцій.
Опис
Ключові слова
розбір мережевих пакетів, програмно--апаратний граматичний розбір, ПЛІС, проєктування парсерів, граматичний розбір, система на кристалі, формальна граматика, Java, спеціалізована архітектура, розподілена пам’ять, обробка даних, продуктивність, network packets parsing, FPGA, XML, designing of parsers, stack processor, software/hardware grammatical parsing, system on a chip, algorithm, formal grammar, specialized architecture, distributed memory, data processing, performance
Бібліографічний опис
Молчанов, О. А. Метод і засоби проєктування парсерів пакетів для ПЛІС : дис. … д-ра філософії : 123 Комп’ютерна інженерія / Молчанов Олексій Андрійович. – Київ, 2023. – 225 с.