Методи і засоби проєктування спеціалізованих конвеєрних обчислювачів на базі ПЛІС для обробки сигналів
Вантажиться...
Дата
2023
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім.Ігоря Сікорського
Анотація
Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 123 — Комп’ютерна інженерія. — Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, 2023.
Тема дисертації пов’язана з автоматизацією проєктування обчислювальних засобів на базі інтегральних схем надвисокої інтеграції (НВІС) та програмовних логічних інтегральних схем. В даний час складність проєктів обчислювальних систем для НВІС та програмовних логічних інтегральних схем досягла десятків мільйонів вентилів. Причому досі вирішальну роль грає технологія, яка основана на описі проєктів на рівні регістрових передач, продуктивність якої є обмеженою. Розвивається галузь високорівневого синтезу, який ґрунтується на трансляції опису алгоритму в опис на рівні регістрових передач і на порядок прискорює проєктування. Але в наявних засобах такого синтезу необхідно вручну задавати паралелізм алгоритму та особливості відображення в опис обчислювальної системи на рівні регістрових передач, яка часто одержує надмірні апаратні витрати чи продуктивність, що не відповідає заданій.
Невідповідність ефективності наявних засобів високорівневого синтезу складності та продуктивності обчислювальних систем, що проєктуються, представляє актуальну технічну проблему. Обчислювальні системи для цифрової обробки сигналів є такими системами, які вимагають для своєї реалізації проєктування НВІС та програмовних логічних інтегральних схем найбільшої складності і для них ця проблема стає актуальнішою.
Об’єктом дослідження є процес розроблення високопродуктивних паралельних обчислювальних засобів. Предметом дослідження є методи та засоби проєктування спеціалізованих обчислювальних систем конвеєрного типу для цифрової обробки сигналів на базі програмовних логічних інтегральних схем (ПЛІС).
Метою дисертації є підвищення ефективності проєктування конвеєрних обчислювальних систем на основі програмовних логічних інтегральних схем на базі запропонованого методу проєктування спеціалізованих конвеєрних структур на основі генетичного програмування, який дає змогу прискорити проєктування конвеєрних обчислювальних систем і підвищити відношення продуктивність — апаратні витрати завдяки формалізації проєктування і новим алгоритмам пошуку апаратних рішень із мінімізованими апаратними витратами при заданому періоді обчислень.
Для досягнення мети в дисертації виконуються завдання: проаналізувати алгоритми і пристрої цифрової обробки сигналів і сформулювати вимоги до елементної бази й засобів проєктування обчислювальних систем для цифрової обробки сигналів, проаналізувати алгоритмічні моделі та мови опису алгоритмів цифрової обробки сигналів, методи і засоби їхнього відображення в паралельні обчислювальні системи, вибрати найбільш придатні модель та метод відображення, теоретично обґрунтувати та розробити новий метод відображення алгоритму цифрової обробки сигналів у апаратні засоби, які конфігуруються в програмовну логічну інтегральну схему, на основі запропонованого методу розробити засоби автоматизації відображення алгоритмів цифрової обробки сигналів в обчислювальні системи на основі програмовних логічних інтегральних схем, перевірити ефективність розробленого методу під час проєктування низки спеціалізованих обчислювальних систем для вирішення завдань цифрової обробки сигналів.
Під час аналізу алгоритмічних моделей вибрана модель просторового графа синхронних потоків даних (ГСПД) та його відображення у структуру обчислювальної системи і розклад виконання алгоритму як найбільш придатні модель та метод відображення. Просторовий граф синхронних потоків даних представляє собою граф, операторні вершини якого розміщується у просторі з координатами місця, такту виконання і типу оператора таким чином, щоби шуканий розклад виконання алгоритму був коректним. Відображення просторового графа синхронних потоків даних є афінним відображенням у підпростір структур обчислювальних систем та підпростір розкладів.
Наукова новизна роботи. Вперше запропоновано метод проєктування спеціалізованих конвеєрних структур на основі генетичного програмування, який відрізняється тим, що алгоритм цифрової обробки сигналів, який відображається в структуру, задається просторовим ГСПД, задача мінімізації апаратних витрат вирішується із заданими часовими обмеженнями за допомогою еволюційного підходу, який ґрунтується на поданні хромосоми як закодованого ГСПД та відповідних функціях її зміни, а також двохетапному алгоритмі оптимізації. Запропонований метод дає змогу формалізовано вирішувати задачу синтезу обчислювальних систем для цифрової обробки сигналів і завдяки регулюванню ступеня розпаралелювання алгоритму та мінімізації апаратних витрат одержані структури мають високе співвідношення продуктивність — вартість.
Вперше запропоновано спосіб проєктування рекурсивних фільтрів на ПЛІС, який відрізняється тим, що завдяки застосуванню методу відображення просторового ГСПД, використання схем без блоків множення, а також пошуку коефіцієнтів фільтра методом модельованого відпалювання та застосування мови VHDL (VHSICVHSIC (vveryery highhigh speedspeed integratedintegrated circuitscircuits) hhardwareardware ddescriptionescription llanguageanguage), забезпечується одержання фільтрів з мінімізованими апаратними витратами та високою тактовою частотою.
Практична цінність результатів дисертаційної роботи полягає в тому, що використання нового методу проєктування обчислювальних систем забезпечує зниження трудомісткості і скорочення термінів одержання множини альтернативних оптимізованих структурних рішень, мінімізація використання обчислювальних ресурсів, зокрема пам’яті обчислювальних систем, розроблення високоефективних конвеєрних обчислювальних систем обробки сигналів із мінімізованими апаратними витратами за заданих пропускної спроможності й порядку подання даних у вхідному та вихідному потоках даних.
Розроблено програмний застосунок SDFCAD (synchronoussynchronous datadata flowflow computercomputer-aidedaided designdesign), у якому впроваджений запропонований метод. Цей застосунок дає змогу проєктувальнику описувати за допомогою графа синхронних потоків даних алгоритм цифрової обробки сигналів, моделювати алгоритм з різними степенями паралелізму, забезпечує автоматизований синтез обчислювальної системи із заданими властивостями, яка придатна для подальшої компіляції та конфігурування в програмовну логічну інтегральну схему довільної серії, а також впровадження в замовлену НВІС.
Розроблені з використанням нового методу проєкти обчислювальних систем, такі як процесор дискретного косинусного перетворення, процесор для швидкого перетворення Фур’є, рекурсивні фільтри, модулі обчислення синусоїдальних функцій у програмовних логічних інтегральних схемах, є налаштовуваними обчислювальними модулями, які описані на VHDL, мають високе відношення продуктивність — апаратні витрати та можуть бути впроваджені в нових розробках із мінімальними додатковими часовими і фінансовими витратами. Запропонований спосіб проєктування рекурсивних цифрових фільтрів впроваджено у вебзастосунку, який може бути вільно використаний у практиці проєктування пристроїв цифрової обробки сигналів.
Результати роботи впроваджені у двох НДР, що проводяться в Національному технічному університеті України «Київський політехнічний інститут імені Ігоря Сікорського» на кафедрі обчислювальної техніки, які присвячені проєктуванню високопродуктивних апаратних і програмних засобів.
Матеріали дисертації є корисними для викладачів і спеціалістів у галузях проєктування апаратних засобів обчислювальної техніки, систем телекомунікацій, зв’язку, вимірювання, радіолокації, штучного інтелекту, засобів мікроелектроніки.
Molchanova A. A. Methods and tools of designing the application specific pipelined processors for signal processing based on FPGA. — Qualification scientific work on the rights of the manuscript. Dissertation for the degree of Philosophy Doctor in speciality 123 — Computer Engineering. — National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, 2023. The topic of the dissertation is related to the computer-aided design of very large scale integration (VLSI) application specific integral circuits (ASICs) and field programmable gate arrays (FPGAs). Currently, the complexity of the processing systems in ASIC and FPGA has reached tens of millions of gates. And still the design technology based on the register transfer level (RTL) description of projects plays the main role. But its productivity is limited. The field of high-level synthesis (HLS) is spreading. It is based on the translation of the algorithm description into the RTL description and speeds up the design by an order of magnitude. However, in the existing HLS tools, it is necessary to control manually the algorithm parallelism and the constraints of mapping the processing system structure to the RTL-description. Such a synthesis often leads to excessive hardware costs or performance that does not meet the limitations. The discrepancy between the inefficiency of the existing HLS tools and needed hardware volume and performance of the designed system is an urgent technical problem. The digital signal processing (DSP) system is a system that requires the most complex implementation in ASIC and FPGA, and this technical problem becomes even more relevant now. The object of the research is the design of the high-performance parallel processors. The subject of the research are the methods and tools for the design of the application-specific pipelined DSP processors based on FPGA. The goal of the dissertation is to increase the efficiency of mapping DSP algorithms into parallel computational systems based on FPGA. The efficiency is increased by the proposed application-specific pipelined structures design method based on the genetic programming. This method helps to accelerate the design of a pipelined processing system and to improve its quality through formalization and automation of the design, and use of new hardware optimization algorithms. To achieve the goal of the dissertation, the following tasks are performed. The dissertation analyzes the algorithms and devices for DSP, and formulates the requirements to element base and tools for designing DSP processing systems. It analyzes the algorithmic models and DSP algorithm description languages, methods and tools of mapping them to parallel processing systems, chooses the most suitable model and method of mapping. It substantiates theoretically and developes a new method of mapping DSP algorithms into hardware configured in FPGA as well. The development of tools for mapping the DSP algorithms into processing systems based on FPGA, and testing the effectiveness of the developed method when designing a number of application-specific computing systems for the DSP problem solving are performed. During the analysis of algorithmic models, the model of the spatial synchronous data flow (SDF) and its mapping into the structure of a processing system and the schedule of the algorithm are chosen. It is proven as the most suitable model and method of mapping. Spatial SDF is a graph whose operator nodes are placed in 3D space. The coordinates of this space are the location, execution time and operator type, so that the resulting schedule of the algorithm execution is correct. The mapping of the spatial SDF is an affine mapping into the subspace of computing system structures and the subspace of schedules. The scientific novelty of the work. A method for application-specific pipelined structures design based on the genetic programming is proposed. The method differs in that the DSP algorithm, which is mapped into a structure, is given by a spatial SDF, the hardware minimization problem is solved with the given time constraints using an evolutionary approach based on the representation of a chromosome as an encoded SDF and the corresponding functions of its change, as well as a two-stage optimization algorithm. A method of the IIR filter design based on FPGA is proposed. The method differs in that the use of the spatial SDF mapping method, and the multiplier-free circuits, as well as the filter coefficient search using the simulating annealing method, and the use of VHDL language provide the deriving of the filters with minimal hardware costs and high throughput. The practical value of the dissertation results is that the use of a new method of the processing system design provides a reduction of both complexity and time of obtaining a variety of alternative optimized structural solutions. It improves the resource utilization effectiveness and processing system memory volume, provides the development of highly pipelined DSP processing systems with minimized hardware costs for a given bandwidth. Besides, it provides the natural order of data in input and output data streams. The developed SDFCAD software framework implements the proposed method. This application allows the designer to describe the DSP algorithm using the SDF model providing the different degrees of parallelism, automated synthesis of processing systems with specified properties. The resulting processing system description is suitable for further compilation and configuration in FPGA of any series, as well as for implementation in ASIC. Newly developed processing system projects, such as DCT processor, FFT processor, recursive filters, sine wave generating modules configured in FPGA, are customizable IP cores that are described in VHDL and have a high performancehardware cost ratio. They can be built in the new projects with minimal additional time and financial costs. The proposed method of designing the recursive digital filters is implemented in a Web application that can be freely used in the practice of designing the DSP devices. The results of the work have been implemented in two scientific research works held at the National Technical University of Ukraine “Ihor Sikorsky Kyiv Polytechnic Institute” at the Computer Engineering Department, which are dedicated to the high-performance hardware and software design. The materials of the dissertation are useful for the lecturers and specialists in the fields of computer hardware design, telecommunication systems, communication, measurement, radar, artificial intelligence, microelectronics.
Molchanova A. A. Methods and tools of designing the application specific pipelined processors for signal processing based on FPGA. — Qualification scientific work on the rights of the manuscript. Dissertation for the degree of Philosophy Doctor in speciality 123 — Computer Engineering. — National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, 2023. The topic of the dissertation is related to the computer-aided design of very large scale integration (VLSI) application specific integral circuits (ASICs) and field programmable gate arrays (FPGAs). Currently, the complexity of the processing systems in ASIC and FPGA has reached tens of millions of gates. And still the design technology based on the register transfer level (RTL) description of projects plays the main role. But its productivity is limited. The field of high-level synthesis (HLS) is spreading. It is based on the translation of the algorithm description into the RTL description and speeds up the design by an order of magnitude. However, in the existing HLS tools, it is necessary to control manually the algorithm parallelism and the constraints of mapping the processing system structure to the RTL-description. Such a synthesis often leads to excessive hardware costs or performance that does not meet the limitations. The discrepancy between the inefficiency of the existing HLS tools and needed hardware volume and performance of the designed system is an urgent technical problem. The digital signal processing (DSP) system is a system that requires the most complex implementation in ASIC and FPGA, and this technical problem becomes even more relevant now. The object of the research is the design of the high-performance parallel processors. The subject of the research are the methods and tools for the design of the application-specific pipelined DSP processors based on FPGA. The goal of the dissertation is to increase the efficiency of mapping DSP algorithms into parallel computational systems based on FPGA. The efficiency is increased by the proposed application-specific pipelined structures design method based on the genetic programming. This method helps to accelerate the design of a pipelined processing system and to improve its quality through formalization and automation of the design, and use of new hardware optimization algorithms. To achieve the goal of the dissertation, the following tasks are performed. The dissertation analyzes the algorithms and devices for DSP, and formulates the requirements to element base and tools for designing DSP processing systems. It analyzes the algorithmic models and DSP algorithm description languages, methods and tools of mapping them to parallel processing systems, chooses the most suitable model and method of mapping. It substantiates theoretically and developes a new method of mapping DSP algorithms into hardware configured in FPGA as well. The development of tools for mapping the DSP algorithms into processing systems based on FPGA, and testing the effectiveness of the developed method when designing a number of application-specific computing systems for the DSP problem solving are performed. During the analysis of algorithmic models, the model of the spatial synchronous data flow (SDF) and its mapping into the structure of a processing system and the schedule of the algorithm are chosen. It is proven as the most suitable model and method of mapping. Spatial SDF is a graph whose operator nodes are placed in 3D space. The coordinates of this space are the location, execution time and operator type, so that the resulting schedule of the algorithm execution is correct. The mapping of the spatial SDF is an affine mapping into the subspace of computing system structures and the subspace of schedules. The scientific novelty of the work. A method for application-specific pipelined structures design based on the genetic programming is proposed. The method differs in that the DSP algorithm, which is mapped into a structure, is given by a spatial SDF, the hardware minimization problem is solved with the given time constraints using an evolutionary approach based on the representation of a chromosome as an encoded SDF and the corresponding functions of its change, as well as a two-stage optimization algorithm. A method of the IIR filter design based on FPGA is proposed. The method differs in that the use of the spatial SDF mapping method, and the multiplier-free circuits, as well as the filter coefficient search using the simulating annealing method, and the use of VHDL language provide the deriving of the filters with minimal hardware costs and high throughput. The practical value of the dissertation results is that the use of a new method of the processing system design provides a reduction of both complexity and time of obtaining a variety of alternative optimized structural solutions. It improves the resource utilization effectiveness and processing system memory volume, provides the development of highly pipelined DSP processing systems with minimized hardware costs for a given bandwidth. Besides, it provides the natural order of data in input and output data streams. The developed SDFCAD software framework implements the proposed method. This application allows the designer to describe the DSP algorithm using the SDF model providing the different degrees of parallelism, automated synthesis of processing systems with specified properties. The resulting processing system description is suitable for further compilation and configuration in FPGA of any series, as well as for implementation in ASIC. Newly developed processing system projects, such as DCT processor, FFT processor, recursive filters, sine wave generating modules configured in FPGA, are customizable IP cores that are described in VHDL and have a high performancehardware cost ratio. They can be built in the new projects with minimal additional time and financial costs. The proposed method of designing the recursive digital filters is implemented in a Web application that can be freely used in the practice of designing the DSP devices. The results of the work have been implemented in two scientific research works held at the National Technical University of Ukraine “Ihor Sikorsky Kyiv Polytechnic Institute” at the Computer Engineering Department, which are dedicated to the high-performance hardware and software design. The materials of the dissertation are useful for the lecturers and specialists in the fields of computer hardware design, telecommunication systems, communication, measurement, radar, artificial intelligence, microelectronics.
Опис
Ключові слова
генетичне програмування, ПЛІС, цифрова обробка сигналів, структурний синтез, граф, граф потоків даних, system on a chip, speedup, graph encoding, scaling, artificial intelligence, performance, resource allocation, genetic programming, FPGA, digital signal processing, structural synthesis, graph, data flow graph, SDF, system on a chip, speedup, graph encoding, scaling, artificial intelligence, performance, resource allocatio
Бібліографічний опис
Молчанова, А. А. Методи і засоби проєктування спеціалізованих конвеєрних обчислювачів на базі ПЛІС для обробки сигналів : дис. … д-ра філософії : 123 Комп’ютерна інженерія / Молчанова Анастасія Анатоліївна. – Київ, 2023. – 243 с.