Метод і засоби проєктування парсерів пакетів для ПЛІС
| dc.contributor.advisor | Романкевич, Олексій Михайлович | |
| dc.contributor.author | Молчанов, Олексій Андрійович | |
| dc.date.accessioned | 2024-01-22T10:42:06Z | |
| dc.date.available | 2024-01-22T10:42:06Z | |
| dc.date.issued | 2023 | |
| dc.description.abstract | Молчанов О. А. Метод і засоби проєктування парсерів пакетів для ПЛІС. — Кваліфікаційна праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії з галузі знань 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 публікації у матеріалах науково-технічних конференцій. | uk |
| dc.description.abstractother | Molchanov O. Method and tools for packet parser design for FPGA. — Qualifying scientific work, the manuscript. Ph.D. thesis in the field of knowledge 12 Information technologies in a specialty 123 Computer engineering. — National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, 2023. The spread of information technology is inextricably linked with the development of computer systems, the elemental basis on which they are based, and the improvement of approaches to solving problems in the field of information technologies (cloud computing, the Internet of Things, satellite communication systems, etc.). The effectiveness of the solution to such problems also depends on the efficiency of the software and hardware of computer systems. One of the tasks solved by information systems is the processing of network packets which includes lexical and syntactic analysis of network packets (their grammatical parsing) and obtaining data from them. Depending on the packets format and the constancy of this format, network packets are parsed by software, hardware, or combined parsing systems. For example, XML messages are widely used in web services. The XML format is stable and regulated by standardized versions. However, in addition to the correctness of the XML format itself, XML documents must also conform to some grammar defined by a specific XML grammar description language. The sets of XML grammars in web services, which can hold thousands of instances, change frequently, leading to limited or impossible use of efficient pure hardware XML document processing systems. Therefore, most XML documents parsing is done by software parsing systems. In a cloud computing environment, parsing XML documents requires great amount of computing resources. Some time ago it consumed almost 30% of the time processing requests to servers. In addition, due to the termination of Moore's Law and Dennard's Law, the number of transistors in processors will no longer change as quickly as before. Accordingly, the performance of purely software systems cannot be further increased by updating the processors on the servers at the same speed as before, which can lead to a gradual increase in latency when processing requests in XML format to the servers. The object of research is the process of grammatical analysis of sentences of formal languages. The subject of the study is the methods, approaches and means of hardware and software-hardware grammar parsing of network packets, as well as methods and means of designing such means. The dissertation aimsto expand the possibilities of reconfiguring the hardware means of grammatical parsing of network packets to work according to a different parsing algorithm or to support another set of grammars with the achievement of comparable indicators of speed and hardware costs in comparison with existing hardware parsers using the example of parsing XML documents. To achieve the set goal, the following tasks are solved in the dissertation. 1. To analyze the known approaches and element base for the grammatical parsing of network packets implementation. 2. Classify methods for solving the problem of parsing XML documents, depending on the equipment and approaches used in these methods. 3. To improve the method of designing hardware parsers of network packets based on finite state machines and to evaluate effectiveness of the improved method. 4. Analyze existing processor architectures. Based on the analysis results, propose an architecture that will enable the most efficient implementation of the parsing by the chosen parsing algorithm. Develop a hardware accelerator according to the proposed processor architecture. 5. To develop tools for the automated development of packet parsers based on the proposed method of designing hardware accelerators for parsing network packets. 6. To test the performance of the hardware accelerator developed according to the new method for different XML grammars and to conduct a comparative analysis of it with existing solutions. The scientific novelty of the dissertation work is next: 1. An improvement of the method of designing hardware for parsing network packets based on stack finite-state machine is proposed. Improved method differs from the existing ones by usage a software-hardware representation of a finite-state machine of grammar parsing, which makes it possible to dynamically change the algorithm or the set of grammars by which the parsing takes place within a short period of time. 2. For the first time, a way of designing stack architectures for software/hardware implementation of grammatical parsing is proposed, which differs in that additional stacks and special commands are added to the basic stack processor architecture with two stacks, thanks to which grammatical parsing acceleration is achieved compared to software implementation. 3. Using the proposed design method, a computing structure of a parser was created for the first time, which, unlike known structures, contains, in addition to a grammar compiler, a specialized stack processor that implements an algorithm for grammatical parsing of XML documents adapted for software and hardware execution for a given set of grammars, due to which the possibility of dynamic changes to the parsing algorithm or the set of supported grammars is achieved. 4. For the first time, an analytical representation of the calculation of the speed of the software-hardware parser, designed according to a new method, was obtained, which makes it possible to evaluate the parsing speed depending on the set of supported grammars. The practical value of the results of the dissertation is that the use of the developed method for designing specialized computers for software/hardware grammar parsing of XML documents based on FPGAs both on servers and on node devices of the Internet of Things will make it possible to speed up both the design time of network packet parsers and processing of XML documents, as well as reduce the energy costs required to process these documents. The newly developed SM16 stack architecture and the stack processor of the same name, together with new means of automated development of packet parsers, enable more efficient implementation of XML packet parsing and analysis procedures and can be used in other applications. The results of the dissertation are implemented in the educational process of the System Programming and Specialized Computer Systems Department of National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» during the preparation and teaching of the course of lectures «Computer Architecture. Microarchitecture», as well as in the laboratory work of the same course. Based on the dissertation, 8 scientific works were published: 4 scientific articles, 2 articles of which were published in foreign professional publications, which are referenced by Scopus, and 2 articles were published in a scientific publications included in scientific professional publications of Ukraine, and 4 publications were published in the materials of scientific and technical conferences. | |
| dc.format.extent | 225 с. | uk |
| dc.identifier.citation | Молчанов, О. А. Метод і засоби проєктування парсерів пакетів для ПЛІС : дис. … д-ра філософії : 123 Комп’ютерна інженерія / Молчанов Олексій Андрійович. – Київ, 2023. – 225 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/63944 | |
| dc.language.iso | uk | uk |
| dc.publisher | КПІ ім.Ігоря Сікорського | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | розбір мережевих пакетів | uk |
| dc.subject | програмно--апаратний граматичний розбір | uk |
| dc.subject | ПЛІС | uk |
| dc.subject | проєктування парсерів | uk |
| dc.subject | граматичний розбір | uk |
| dc.subject | система на кристалі | uk |
| dc.subject | формальна граматика | uk |
| dc.subject | Java | uk |
| dc.subject | спеціалізована архітектура | uk |
| dc.subject | розподілена пам’ять | uk |
| dc.subject | обробка даних | uk |
| dc.subject | продуктивність | uk |
| dc.subject | network packets parsing | uk |
| dc.subject | FPGA | uk |
| dc.subject | XML | uk |
| dc.subject | designing of parsers | uk |
| dc.subject | stack processor | uk |
| dc.subject | software/hardware grammatical parsing | uk |
| dc.subject | system on a chip | uk |
| dc.subject | algorithm | uk |
| dc.subject | formal grammar | uk |
| dc.subject | specialized architecture | uk |
| dc.subject | distributed memory | uk |
| dc.subject | data processing | uk |
| dc.subject | performance | uk |
| dc.subject.udc | 004.27 : 004.31 : 004.62 : 004.71 | uk |
| dc.title | Метод і засоби проєктування парсерів пакетів для ПЛІС | uk |
| dc.type | Thesis Doctoral | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Molchanov_dys.pdf
- Розмір:
- 3.77 MB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.01 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: