Дунець, Роман БогдановичТкачук, Тарас Ігорович2018-08-312018-08-312018Ткачук Т. І. Характеристики складності SH-моделей спеціальних функцій і їх застосування для оптимізації спецпроцесорів : дисертація на здобуття наукового ступеня кандидата технічних наук (доктора філософії) : 05.13.05 – комп’ютерні системи та компоненти / Тарас Ігорович Ткачук ; Міністерство освіти і науки України, Національний університет “Львівська політехніка”. – Львів, 2018. – 163 с. – Бібліографія: с. 137–149 (119 назв).https://ena.lpnu.ua/handle/ntb/42548Роботу присвячено розв’язанню актуального науково-прикладного завдання створення ефективних структурних побудов спеціальних функцій спецпроцесора опрацювання сигналів, методом побудови відповідних SH-моделей та оптимізації значень їх характеристик складності. Проведено оптимізацію характеристик складності арифметичних пристроїв та пристроїв спеціальних функцій спецпроцесора опрацювання сигналів. Проаналізовані шляхи вдосконалення відомого методу обчислення структурної характеристики складності для структур спеціальних функцій та вдосконалено його за рахунок виявлення та об’єднання у групи однотипних елементів схеми, що дало змогу отримувати матриці інциденцій значно меншого розміру без регулярно розташованих елементів а в результаті спростило обчислення й скоротило час на проектування системи. Розроблено структуру конвеєрного пристрою множення, із затримкою сходинки конвеєра не більшою, ніж затримка на одному багаторозрядному суматорі, та відсутністю залежності від розмірності вхідних даних. Розроблено SН-моделі пристроїв спеціальних функцій опрацювання сигналів, а саме згортки та швидкого перетворення Фур’є, із оптимізованими значеннями характеристик складності. Отримано RH-модель із суміщенням алгоритмів згортки та метелика швидкого перетворення Фур’є, яка має оптимальні значення часової та структурної характеристик складності. Реалізовано VHDL-моделі модифікованих у роботі пристроїв: оптимізованого двосходинкового конвеєрного матричного пристрою множення, оптимізованого пристрою згортки, пристрою швидкого перетворення Фур’є та реконфігурованого пристрою, що реалізує алгоритми згортки та метелика швидкого перетворення Фур’є. Показано, що оптимізація характеристик складності пристроїв дала змогу покращити значення структурної та часової складності та реалізувати конвеєр обробки даних із затримкою сходинки конвеєра 8,1 нс. Работа посвящена решению актуального научно-прикладного задания создания эффективных структурных построений специальных функций спецпроцессора обработки сигналов, методом построения соответствующих SH-моделей и оптимизации значений их характеристик сложности. Проведена оптимизация характеристик сложности арифметических устройств и устройств специальных функций спецпроцессора обработки сигналов. Проанализированы пути совершенствования известного метода вычисления структурной характеристики сложности для структур специальных функций и усовершенствовано его за счет выявления и объединения в группы однотипных элементов схемы, что позволило получать матрицы инциденций значительно меньшего размера без регулярно расположенных элементов, а в результате упростило вычисления и сократило время на проектирование системы. Разработана структура конвейерного устройства умножения, с задержкой ступени конвейера не более, чем задержка на одном многоразрядные сумматоре и отсутствием зависимости от размерности входных данных. Разработан SН-модели устройств специальных функций обработки сигналов, а именно свертки и быстрого преобразования Фурье, с оптимизированными значениями характеристик сложности. Получено RH-модель с совмещением алгоритмов свертки и бабочки быстрого преобразования Фурье, которая имеет оптимальные значения временной и структурной характеристик сложности. Реализовано VHDL-модели модифицированных в работе устройств: оптимизированного конвейерного матричного устройства умножения, оптимизированного устройства свертки, устройства быстрого преобразования Фурье и реконфигурируемого устройства, реализующего алгоритмы свертки и бабочки быстрого преобразования Фурье. Показано, что оптимизация характеристик сложности устройств позволила улучшить значение структурной и временной сложности и реализовать конвейер обработки данных с задержкой ступени конвейера 8,1 нс. The dissertation is devoted to the solution of an actual scientific and applied task – creating effective structural constructions of special functions of digital signal processing by constructing the corresponding SH-models and optimizing the values of their characteristics of complexity. A comparative analysis of the basic models of formal algorithmic systems, models of hardware of special processors and models of hardware and software of specialized computer systems has been carried out. It has been shown that hardware and software models allow best optimization of specialized computer systems that implement special functions, taking into account hardware, time, software and structural characteristics of complexity. A well-known method for calculating the structural complexity of SH-models has been improved by detecting and integrating into a group of similar-type elements of the scheme, which made it possible to receive matrices of incidents of a much smaller size without regularly located elements, and as a result simplified the calculation and reduced the time for designing the system. The characteristics of the complexity of the SH-models of multiplication devices on the multi-bit aggregator and the conveying device of multiplication are obtained and it is shown that it is not expedient to use them for the realization of special functions, since they do not have the optimal values of the complexity characteristics. The optimization of the matrix multiplication device with horizontal transfer has been carried out and the H-model of the device has been obtained, which has, in comparison with the known device, lesser values of the hardware and time characteristics of complexity. The optimization of the matrix multiplication device with a diagonal transport has been optimized and the H-model of a two-link conveyor multiplication device has been obtained, which has a higher value of hardware complexity and less time complexity compared to a known device. The characteristics of the complexity of the SH-models of the convolution algorithm implemented on the basis of the systolic structure and the mixed structure are obtained and it is shown that the device with mixed structure is best used for implementation in special processors, because it has high speed and low hardware complexity and is best suited for combining with other algorithms. The characteristics of the complexity of the SH models of a fast Fourier transform butterfly on one multiplier and two multipliers are obtained and it is shown that it is not expedient to use them for implementation in special processors, since such devices have high values of time and software characteristics of complexity. The optimization of the complexity of the SH-model of the Fourier Fast Fourier transform butterfly on four multipliers has been performed and the SH-model of the device is divided into four parallel branches, which has, in comparison with the known device, a smaller structural complexity of one branch, which greatly simplifies the design process, and also best suited for combining on one structure with a convolution algorithm. An RH model is obtained combining the convolution algorithms and the Fourier fast butterfly, which has optimal values of time and structural characteristics of complexity.ukSH-модельH-модельхарактеристики складностіспецпроцесор опрацювання сигналівструктурний синтезпараметрична оптимізаціяFPGAVHDL-модельSH-модельH-модельхарактеристики сложностиспецпроцессор обработки сигналовструктурный синтезпараметрическая оптимизацияFPGAVHDL-модельSH-modelH-modelcomplexity characteristicsdigital signal processorstructural synthesisparametric optimizationFPGAVHDL-modelDissertation Abstract163004.31