Методика и программные средства организации процесса обработки данных в многоканальной многопроцессорной системе цифровой обработки сигналов

• Автор: Стручков, Игорь Вячеславович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Санкт-Петербург
• Количество страниц: 224 с. : ил.

ОГЛАВЛЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ,

ВВЕДЕНИЕ.
1. АНАЛИЗ МЕТОДОВ И СРЕДСТВ ОРГАНИЗАЦИИ ПРОЦЕССА ОБРАБОТКИ ДАННЫХ В МНОГОКАНАЛЬНЫХ МНОГОПРОЦЕССОРНЫХ СИСЛЕМАХ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ. ЗАДАЧИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБРАБОТКИ ЗА СЧЕТ РАСПРЕДЕЛЕНИЯ И ПЛАНИРОВАНИЯ ЗАДАНИЙ

Е1.Класс многоканальных многопроцессорных систем цифровой обработки

сигналов

1.2.Анализ аппаратных средств многопроцессорных систем цифровой

обработки сигналов

ЕЗ.Анализ программного обеспечения систем цифровой обработки сигналов

1.3.1.Особенности системного программного обеспечения систем ЦОС
1.3.2.Прикладное программное обеспечение
1.4.Анализ процесса проектирования программного обеспечения
многоканальной многопроцессорной системы цифровой обработки сигналов
ЕЗ.Анализ моделей параллельных вычислительных процессов
1.6.Анализ методов распределения и планирования заданий в
многопроцессорных системах
1.7 .Постановка задач повышения эффективности обработки данных за счет-
распределения и планирования заданий
1.8.Выводы
2. МОДЕЛИ СИСТЕМЫ ПАРАЛЛЕЛЬНЫХ ЗАДАНИЙ И СТРУКТУРЫ
АППАРАТНОГО
МНОГОПРОЦЕССОРНОЙ СИСТЕМЕ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
2.1.Модель системы параллельных заданий
2.1.1.Цель построения модели. Требования
2.1.2.Принципы построения модели
2.1.3. Формализация класса систем ММСЦОС
2.1.4. Элементарные модели заданий
2.1.5. Граф генераторов и преобразователей данных
2.1.6. Перемещаемость и расщепление заданий
2.1.7. Взаимосвязь модели генераторов и преобразователей данных и модели синхронных потоков данных
2.1.8. Условия корректности графа генераторов и преобразователей данных
2.1.9. Анализ соответствия модели параллельных заданий поставленным требованиям
2.2. Граф соединений процессоров
2.3. Маршрутизация данных в ММСЦОС
2.4. Выводы
3. МЕТОДИКА ОРГАНИЗАЦИИ ПРОЦЕССА ОБРАБОТКИ ДАННЫХ В
МНОГОКАНАЛЬНОЙ МНОГОПРОЦЕССОРНОЙ СИСТЕМЕ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
3.1.Формальная постановка задачи оптимальной организации вычислительного процесса в ММСЦОС
3.2.Формирование модели системы параллельных заданий
3.2.1.Идентификация параллельных заданий
3.2.2.0пределение длительности вычислений и характеристик потоков
данных
3.2.3.Расчет вычислительных весов заданий и интенсивностей потоков
данных
3.2.4.0бобщения алгоритма расчета
3.2.5. Учет расщепления заданий
3.3. Распределение параллельных заданий в многоканальной многопроцессорной вычислительной системе цифровой обработки сигналов
3.3.1. Основные принципы
3.3.2. Оптимизация распределения заданий методом имитации отжига
3.4. Планирование заданий реального времени в многоканальной многопроцессорной системе цифровой обработки сигналов
3.4.1. Обоснование подхода
3.4.2. Динамическое планирование периодических операций реального времени
3.4.3. Планирование операций реального времени с зависимостями по данным
3.4.4. Метод планирования с динамическими приоритетами для смещенных периодических операций
3.4.5. Накладные расходы на передачу данных
3.4.6. Расчет размеров буферов данных
3.4.7. Расчет значений частных целевых функций оптимизации
3.4.8. Расчет ограничений оптимизации
3.4.9. Отсутствие полиномиального алгоритма оптимизации
3.4.10. Временная сложность одного шага алгоритма оптимизации
3.5. Методика организации процесса обработки данных
3.6. Экспериментальные исследования
3.6.1. Исследование сходимости алгоритма оптимизации
3.6.2. Сравнительное исследование разработанной методики с известным подходом
3.7. Выводы
4. ПРОГРАММНЫЕ СРЕДСТВА ОРГАНИЗАЦИИ ПРОЦЕССА ОБРАБОТКИ
ДАННЫХ В МНОГОКАНАЛЬНОЙ МНОГОПРОЦЕССОРНОЙ СИСТЕМЕ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ
4.1.Инструментальное средство распределения и планирования заданий в ММСЦОС
4.1.1.Цель разработки инструментального средства, требования
4.1.2.Архитектура инструментального средства
4.2.Подсистема имитационного моделирования вычислительного процесса в ММСЦОС
4.2.1 Цели имитационного моделирования
4.2.2.Обеспечение адекватности имитационной модели
4.2.3 .Архитектура имитационной модели
4.2.4.Выбор средства имитационного моделирования

проверяющего наличие текущих непериодических заданий и выполняющего их; выполнение апериодических заданий в фоновом режиме.
В работе [39] применен подход, основанный на альтернативном варианте определения условий реального времени при помощи понятия пропорциональной справедливости, являющегося более сильным условием, чем выполнение всех директивных сроков. Базовым алгоритмом составления пропорционально справедливого расписания реального времени является алгоритм PF. Этот алгоритм можно рассматривать, как обобщение алгоритма на основе сроков выполнения (EDF). В работе [85] рассматривается простая схема со статическими приоритетами, которая также позволяет создавать пропорционально справедливые периодические расписания. Алгоритм получил название монотонного, относительно веса (Weight-Mono tonic, WM).
Основным недостатком всех ранее рассмотренных подходов к дипамичеекому планированию заданий реального времени является условие независимости выполнения заданий. В [45] предложена модификация алгоритма EDF для зависимых по данным заданий, заданных моделью SDF. Метод имеет ряд существенных ограничений. Во-первых, принцип расчета модифицированных времен старта и сроков выполнения предполагает отсутствие контуров в графе заданий. Во-вторых, не учитывается кратность дуг графа, типичная для графов SDF. В-третьих, не учитывается возможность одновременного планирования нескольких заданий на одном процессоре. В этом случае использование времени выполнения задания без прерываний как оценки его фактического времени завершения некорректно. В работе [113] метод модификации директивных сроков выполнения расширяется на случай многочастотного графа SDF с контурами, однако, проблема вытесняющей многозадачности остается незатронутой.
По результатам анализа методов распределения и планирования заданий в многопроцессорных системах можно сделать следующие выводы:
• Балансировка загрузки не во всех случаях ведет к оптимальной эффективности программного обеспечения многопроцессорной вычислительной системы. В частности, методы балансировки загрузки неприменимы для гетерогенных вычислительных систем. Кроме того, балансировка загрузки не позволяет учитывать требования реального времени (директивные сроки операций).