Моделі, методи і засоби синтезу обчислювальних систем для обробки потоків даних
DSpace at NTB NTUU KPI
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Моделі, методи і засоби синтезу обчислювальних систем для обробки потоків даних
|
|
| Creator |
Сергієнко, Анатолій Михайлович
|
|
| Description |
Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.05 – Комп'ютерні системи та компоненти. Національний технічний університет України "Київський політехнічний інститут", м. Киів, 2011 р. Розроблено ряд методів синтезу конвеєрних обчислювальних систем (ОС) через відображення просторового графу синхронних потоків даних в структуру ОС та розклад виконання операцій в ній, який забезпечує при заданому періоді виконання алгоритму в L тактів мінімізацію тривалості тактового інтервалу, об'єму пам'яті, а також апаратних витрат, включаючи кількість процесорних елементів, їх регістрів, мультиплексорів, з'єднань. Розроблені методи синтезу конвеєрних ОС для програмованих логічних інтегральних схем (ПЛІС), проектування ОС з використанням мови VHDL, відображення алгоритмів обробки синхронних потоків даних з операторами керування, спосіб синтезу буферних схем. Методи перевірені при проектуванні ОС для цифрової обробки сигналів і вирішення задач лінійної алгебри, які реалізовані в ПЛІС, параметри яких переважають або не гірше параметрів кращих зразків. Розроблені також методи програмної конвеєризації і програмування багатопроцесорних ОС. Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.05 – Компьютерные системы и компоненты. Национальный технический университет Украины "Киевский политехнический институт", г. Киев, 2011г. Объектом исследований в диссертационной работе являются параллельные вычислительные системы (ВС) для обработки потоков данных и дискретных сигналов. Предметом исследований являются математические модели алгоритмов обработки потоков данных и методы их отображения в ВС с ориентацией на реализацию в программируемых логических интегральных схемах (ПЛИС). Целью работы является улучшение эффективности указанных методов отображения, в частности, минимизации аппаратурных затрат при заданном периоде выполнения алгоритма L тактов. Предложены классификация вычислительных моделей для задания и отображения итерационных алгоритмов и их представление на модели графа синхронных потоков данных (ГСПД) с помощью языка VHDL. Выработан критерий эффективности ВС, сконфигурированной в ПЛИС, учитывающий свойства как периодических алгоритмов, так и элементной базы. Предложена модель пространственного ГСПД, позволяющая улучшить оптимизацию ВС. Разработан ряд методов синтеза конвейерных ВС путем отображения пространственного ГСПД в структуру ВС и ее расписание, который обеспе чивает при заданном L минимизацию длительности тактового интервала, аппаратных затрат, включая количество процессорных элементов, их регистров, мультиплексоров, межсоединений, объем памяти а также энергопотре бление. Методы основаны на том, что ГСПД представляется в многомерном целочисленном пространстве в виде конфигурации алгоритма (КА), которая является пространственным ГСПД, состоящей из матрицы векторов-вершин K, соответствующих операторам алгоритма, матрицы векторов-дуг, отвечающих непосредственным информационным связям между операторами или переменным и матрицы инцидентности ГСПД. Поиск оптимального структурного решения ВС заключается в нахожде нии такой матрицы К, которая минимизирует заданный критерий качества и удовлетворяет ряд требований к КА, которые учитывают как временные ограничения, так и периодичность алгоритма с параметром L. На первом этапе синтеза ВС ГСПД размещается в многомерном пространстве по координатам которого отсчитываются номер процессорного элемента, где исполняется оператор, его тип и такт его исполнения с учетом определенных ограничений. При этом число вершин, отображаемых в один ПЭ должно стремиться к L, что обеспечивает минимизацию аппаратных затрат. На втором этапе КА уравновешивается вставкой в дуги ГСПД промежу точных вершин задержки, в результате чего вершины образуют ярусы, расстояние между которыми по координате времени равно 1. После уравновеши вания КА выполняется ее оптимизация путем взаимных перестановок вершин из одного яруса с минимизацией числа регистров и числа входов мультиплексоров в результирующей структуре. Полученная КА отображается в граф структуры ВС или описывается на VHDL как искомая модель ВС. Разработаны также метод синтеза конвейерных ВС для ПЛИС, включая метод проектирования с использованием языка VHDL, метод отображения алгоритмов с операторами управления, а также способы синтеза буферных схем, отображения иерархических условных алгоритмов. Методы адаптированы к синтезу ВС для цифровой обработки сигналов. При этом построены способ синтеза функциональных схем фильтров с конечной импульсной характеристикой, реализуемых в ПЛИС и программа генератора таких фильтров. Предложен способ структурного синтеза рекурсивных фильтров с кратными задержками. Методы проверены при синтезе ряда структурно-функциональных схем конвейерных ВС для цифровой обработки сигналов, таких как процессоры быстрого преобразования Фурье, дискретного косинусного преобразования, цифровые фильтры, параметры которых превосходят или не хуже параметров лучших образцов. Разработан метод проектирования параллельных ВС и ряд структур ВС, полученных с его помощью для решения задач линейной алгебры на основе комбинированного отображения пространственного ГСПД и решетчатого графа алгоритма. Предложено представление данных в виде рациональных дробей, благодаря чему осуществляется реализация ВС для решения задач линейной алгебры на базе ПЛИС с минимальными аппаратными затратами, высокой производительностью и требуемой точностью вычислений. Разработан метод программной конвейеризации на основе простран ственного ГСПД, который позволяет составлять эффективные программы обработки потоков данных в многопроцессорных ВС. Также предложен метод отображения пространственного ГСПД в структуру SIMD-процесора. Методы проектирования параллельных ВС обеспечивают возможности: снижение трудоемкости и сокращение сроков получения множества оптими зированных альтернативных структурных решений при проектировании конвейерных ВС, реализуемых как в ПЛИС, СБИС, так и в одно- и многопроцессорных ВС; повышение загруженности ресурсов и памяти ВС; разработка ВС цифровой обработки сигналов с заданными параметрами. Методы могут служить основой курса обучения проектированию специализированных ВС для студентов, аспирантов и специалистов. Thesis for a doctoral degree in engineering sciences, speciality: 05.13.05 – Computer systems and components. National Technical University of Ukraine "Kiev Polytechnic Institute", Kiev, 2011. A set of methods for pipelined computer systems is developed. The methods are based on mapping the spatial synchronous dataflow graph (SDF) into the computer structure, and its schedule. Methods provide minimizing clock period, hardware volume, register number, multiplexor complexity, and energy consumption by the fixed calculation period of L clock cycles. The methods for the pipelined datapath synthesis are developed, which are intended for FPGA, and widely use VHDL as the working language. The methods for mapping Boolean SDF, for buffer synthesis, for hierarchical SDF mapping are proposed as well. The methods are proven by the design of a set of IP core modules for digital signal processing and linear algebra problem solving, which are configured in FPGA. The module parameters are equal or higher than ones for the best analogous modules. Methods of the software pipelining and SIMD system programming are proposed too. |
|
| Publisher |
НТУУ "КПІ"
|
|
| Date |
2011-09-26T09:29:21Z
2011-09-26T09:29:21Z 2011 |
|
| Type |
Thesis
|
|
| Identifier |
http://library.kpi.ua:8080/handle/123456789/1124
|
|
| Language |
uk
|
|