Содержание к диссертации
Введение
1. Анализ методов и средств организации процесса обработки данных в многоканальных многопроцессорных системах цифровой обработки сигналов. задачи повышения эффективности обработки за счет распределения и планирования заданий 14
1.1.Класс многоканальных многопроцессорных систем цифровой обработки сигналов 14
1.2. Анализ аппаратных средств многопроцессорных систем цифровой обработки сигналов 17
1.3.Анализ программного обеспечения систем цифровой обработки сигналов 19
1.3.1.Особенности системного программного обеспечения систем ЦОС. 19
1.3.2.Прикладное программное обеспечение 20
1.4 .Анализ процесса проектирования программного обеспечения
многоканальной многопроцессорной системы цифровой обработки сигналов 22
1.5.Анализ моделей параллельных вычислительных процессов 24
1.6.Анализ методов распределения и планирования заданий в
многопроцессорных системах 29
1.7.Постановка задач повышения эффективности обработки данных за счет
распределения и планирования заданий 37
1.8.Выводы 39
2. Модели системы параллельных заданий и структуры аппаратного обеспечения ногоканальной многопроцессорной системе цифровой обработки сигналов 40
2.1.Модель системы параллельных заданий 41
2.1 Л.Цель построения модели. Требования 41
2.1.2.Принципы построения модели 42
2.1.3. Формализация класса систем ММСЦОС 43
2.1.4. Элементарные модели заданий 45
2.1.5. Граф генераторов и преобразователей данных 46
2.1.6. Перемещаемость и расщепление заданий 48
2.1.7. Взаимосвязь модели генераторов и преобразователей данных и модели синхронных потоков данных 50
2.1.8. Условия корректности графа генераторов и преобразователей данных 52
2.1.9. Анализ соответствия модели параллельных заданий поставленным требованиям 53
2.2. Граф соединений процессоров 55
2.3. Маршрутизация данных в ММСЦОС 57
2.4. Выводы 58
3. Методика организации процесса обработки даьшых в многоканальной многопроцессорной системе цифровой обработки сигналов 59
3.1.Формальная постановка задачи оптимальной организации вычислительного процесса в ММСЦОС 60
3.2.Формирование модели системы параллельных заданий 62
3.2.1.Идентификация параллельных заданий 62
3.2.2. Определение длительности вычислений и характеристик потоков данных 64
3.2.3.Расчет вычислительных весов заданий и интенсивностей потоков данных 65
3.2.4.0бобщения алгоритма расчета 67
3.2.5. Учет расщепления заданий 69
3.3. Распределение параллельных заданий в многоканальной
многопроцессорной вычислительной системе цифровой обработки сигналов 72
3.3.1. Основные принципы 72
3.3.2. Оптимизация распределения заданий методом имитации отжига 73
3.4. Планирование заданий реального времени в многоканальной
многопроцессорной системе цифровой обработки сигналов 77
3.4.1. Обоснование подхода 77
3.4.2. Динамическое планирование периодических операций реального времени 79
3.4.3. Планирование операций реального времени с зависимостями по данным 81
3.4.4. Метод планирования с динамическими приоритетами для смещенных периодических операций 84
3.4.5. Накладные расходы на передачу данных 90
3.4.6. Расчет размеров буферов данных 92
3.4.7. Расчет значений частных целевых функций оптимизации 97
3.4.8. Расчет ограничений оптимизации 100
3.4.9. Отсутствие полиномиального алгоритма оптимизации 103
3.4.10. Временная сложность одного шага алгоритма оптимизации 105
3.5. Методика организации процесса обработки данных 107
3.6. Экспериментальные исследования 109
3.6.1. Исследование сходимости алгоритма оптимизации 109
3.6.2. Сравнительное исследование разработанной методики с известным подходом 113
3.7. Выводы 115
4. Программные средства организации процесса обработки данных в многоканальной многопроцессорной системе цифровой обработки сигналов 116
4.1.Инструментальное средство распределения и планирования заданий в ММСЦОС 117
4.1.1.Цель разработки инструментального средства, требования 117
4.1.2. Архитектура инструментального средства 118
4.2.Подсистема имитационного моделирования вычислительного процесса в ММСЦОС 120
4.2.1.Цели имитационного моделирования 120
4.2.2.0беспечение адекватности имитационной модели... 122
4.2.3.Архитектура имитационной модели 124
4.2.4.Выбор средства имитационного моделирования 132
4.3.Прототип многопроцессорной операционной системы реального времени 132
4.3.1.Цель разработки прототипа и требования 132
4.3.2.Архитектура прототипа операционной системы реального времени134 4.4.Экспериментальные исследования корректности и применимости разработанных программных средств 138
4.4.1.Экспериментальное исследование адекватности имитационной модели 138
4.4.2.Экспериментальное подтверждение достоверности теоретических результатов 142
4.4.3.Экспериментальное исследование области применимости методики на имитационной модели 144
4.4.4. Сравнительное исследование характеристик предлагаемых систем с существующим аналогом .'.148
4.4.5. Исследование эффекта от применения методики в реальной задаче проектирования многоканальной системы цифровой обработки сигналов 150
4.5.Пути дальнейшего развития и совершенствования разработанной методики 154
4.6.Выводы 156
Заключение 157
Список использованных источников
- Анализ аппаратных средств многопроцессорных систем цифровой обработки сигналов
- Формализация класса систем ММСЦОС
- Определение длительности вычислений и характеристик потоков данных
- Архитектура инструментального средства
Введение к работе
Актуальность темы. Многоканальные многопроцессорные системы цифровой обработки сигналов (ММСЦОС) используются в гидроакустике и радиолокации - для обнаружения и идентификации объектов по отраженному сигналу или шуму, сопровождения обнаруженных объектов, прогнозирования местоположения и скорости движения объектов, классификации объектов; в астрофизике и ядерной физике - для спектрометрии заряженных частиц; в телекоммуникациях — для обработки сигналов радиосвязи и кодирования звуковой и видеоинформации и других областях. Эти системы обработки данных имеют следующие особенности: поступление данных в реальном времени с высокой интенсивностью; большое количество параллельных каналов ввода; последовательные многоэтапные вычислительные процедуры обработки данных; однотипная вычислительная обработка данных от разных каналов; периодичность поступления порций входных данных с фиксированным периодом.
Рост требований к производительности и пропускной способности указанных систем, связанный с ростом объемов обрабатываемой информации, требует повышения эффективности использования вычислительных ресурсов. При этом реализация сложных алгоритмов ЦОС на многопроцессорных платформах требует эффективной организации взаимодействия компонентов системы, а смена аппаратных платформ требует переработки сложных программных систем. Решение данных задач вручную даже опытными проектировщиками становится все более длительным и трудоемким, а результаты проектирования становятся недостаточно эффективными.
Ресурсы современных процессоров ЦОС позволяют использовать операционные системы реального времени (ОСРВ) для управления вычислительным процессом и обменом данными между процессорами в многопроцессорной системе. Такими специализированными ОСРВ являются: DSP/BIOS, OSE, ThreadX, а также разрабатываемые в лаборатории программно-аппаратных разработок кафедры АиВТ СПбГПУ ОС для процессоров SHARC и TigerSHARC. Использование ОСРВ в системах ЦОС позволяет сделать прикладное ПО менее зависимым от аппаратной платформы. При этом вычислительный процесс разбивается на множество заданий, число которых, как правило, превышает число процессоров. Задания могут
исполняться параллельно на отдельных процессорах или на одном процессоре в режиме разделения времени. Инструментальные средства разработки ПО ЦОС включают средства для создания, отладки,и моделирования систем. Однако, остается неавтоматизированной актуальная задача эффективной организации процесса обработки данных за счет рационального распределения заданий по процессорам и планирования заданий с учетом требуемых временных характеристик выполнения.
Для автоматизации этапа распределения-и планирования заданий необходимо формализовать исходные данные о задаче обработки данных в виде модели, отражающей параллелизм и количественные характеристики заданий, а также особенности их исполнения в системах класса ММСЦОС. Разработкой моделей параллельной обработки данных занимались многие исследователи. Модели Ч.Э.Р. Хоара [59], Р. Милнера [74], P.M. Карпа, Р.Е. Миллера, Ю.Г. Карпова [9] и др. создавались прежде всего с целью построения^ математического аппарата для спецификации поведения программ, верификации и исследований*их эквивалентных преобразований. Методика разработки программ логического управления на основе систем связанных автоматов, предложенная А.А. Шалыто [34], позволяет строить формально верифицируемые программы соответствующего класса, однако, не содержит способов спецификации временных характеристик алгоритмов. Для задач количественного и алгоритмического анализа Р.' Л. Смелянским была предложена" модель функционирования распределенных систем [29], охватывающая не только поведение программ, но и характеристики аппаратуры, и программного окружения, обеспечивающих выполнение программы. Данный подход весьма полезен в задачах распределения и планирования заданий в многопроцессорных системах, что подтверждается в ряде работ [3, 13, 14]. В то же время, одно из ограничений подхода, а именно, конечность числа шагов в истории процесса, существенно для рассматриваемого класса задач, в которых большинство процессов являются бесконечными и периодическими.
Непосредственно для задач ЦОС чрезвычайно полезны модели вычислений, управляемых потоком данных (data flow). Среди таких моделей применительно к рассматриваемым задачам распределения и планирования вычислений в системах ЦОС наиболее близкой является модель синхронных потоков данных (Synchronous Data Flow, SDF) (Э. А. Ли и Д. Г. Мессершмитт) [71], однако, данная модель
недостаточно отражает многоканальный характер обработки данных и вычисления с накоплением, характерные для ММСЦОС.
Представление параллелизма вычислений является важнейшим требованием к модели системы параллельных заданий. В зависимости от соотношения производительности вычислителя и требуемой интенсивности обработки информации выделяются случаи, когда вычислитель способен обрабатывать несколько потоков данных в режиме разделения' времени, один поток данных и случай, когда- для обработки потока данных требуется параллельная работа нескольких вычислителей [19]. В этом смысле современные многоканальные системы ЦОС представляют собой комбинированный случай: обработка каждого отдельно взятого канала (или группы каналов) на одном этапе может выполняться одним процессором, однако число каналов в системе превышает возможности одного процессора. Параллельная обработка отдельных этапов вычислений, связанных только по данным, осуществляется* за счет конвейеризации процессоров (макроконвейер). Однако, наиболее существенной степенью параллелизма является параллелизм многоканальной обработки. Характерной особенностью такого параллелизма является возможность гибко перераспределять нагрузку между процессорами, назначая отдельным процессорам группы независимых каналов для обработки. Подобный параллелизм может быть представлен расщеплением вычислительных заданий на независимые параллельные подзадания (экземпляры).
Таким» образом, для решения задач распределения и планирования вычислений в ММСЦОС может быть предложена модель системы параллельных заданий, развивающая модель-прототип SDF за счет конструктивного представления параллелизма многоканальной обработки и более полного отражения алгоритмов обработки данных. В соответствии с принципами, изложенными в работах Р.Л. Смелянского, данная модель должна быть также дополнена моделью исполнителя — многопроцессорной вычислительной системы.
Распределению и планированию вычислений в многопроцессорных системах посвящены работы И. Оха [75], А. Бёрчарда [49], С. К. Баруа [38, 39], Г. К. Сиха [92, 93], К. К. Пархи [78, 79], Э. А. Ли, Д. Г. Мессершмитта [69, 70], Р. Л. Смелянского [29]. Однако, эти методы ориентированы, главным образом, на статическое планирование программ. Методы статического планирования, как правило, либо не
учитывают периодический характер вычислений, либо рассматривают только ограниченное число периодов, что снижает показатели получаемых расписаний. В то же время, использование ОСРВ в качестве системного слоя ПО ММСЦОС предполагает динамическое планирование заданий на каждом процессоре. Основы динамического планирования заданий реального времени заложены в работе Ч. Лиу, Дж. Лейланда [73], где не допускаются взаимозависимости заданий. Возможность учета зависимостей заданий в директивных сроках предусмотрена в работе Я. Блазевица [45], но предложенный подход не подходит в случае вытесняющей многозадачности, характерной для ОСРВ. Кроме того, планирование должно учитывать коммуникационные затраты в многопроцессорной системе со сложными маршрутами потоков данных, вопросы многоканальной обработки и использования параллелизма внутри заданий, ограниченность ресурсов оперативной памяти, являющиеся важными для ММСЦОС. Рассмотрению именно этих вопросов посвящена данная работа.
В связи с вышесказанным актуальной является задача разработки методики и соответствующих программных средств автоматизированного распределения и планирования заданий реального времени в ММСЦОС с учетом коммуникационных затрат и параллелизма многоканальной обработки, в условиях ограниченности вычислительных ресурсов с целью повышения эффективности программного обеспечения. В настоящей работе проводится теоретическое и экспериментальное исследование в области программных средств организации (распределение заданий и расчет ресурсов) и управления (планирование и диспетчеризация) обработкой данных в ММСЦОС. При постановке рассматриваемых задач предполагается, что аппаратное обеспечение вычислительной системы к началу разработки ПО ММСЦОС предопределено. Тем не менее, предлагаемая методика может быть использована для определения минимально необходимого числа процессоров, при котором удовлетворяются условия реального времени, с целью выработки рекомендаций для разработчиков вычислительной системы.
Цель работы - разработка методики и программных средств автоматизации распределения и планирования процесса обработки данных в ММСЦОС, обеспечивающих повышение эффективности обработки данных и сокращение длительности проектирования ПО.
Задачи исследования. х
Модель системы параллельных заданий в ММСЦОС, представляющая характеристики алгоритмов цифровой обработки сигналов и параллелизм многоканальной обработки данных.
Оптимизация распределения заданий в многопроцессорной системе.
Планирование заданий и расчет характеристик вычислительного процесса.
Разработка инструментального ПО для автоматизации распределения и планирования заданий.
Методы исследования. В теоретических исследованиях применяются методы теории графов, системного анализа, теории расписаний, теории принятия решений, имитационного моделирования. При разработке программных средств используются методы теории и технологии объектно-ориентированного программирования. Для экспериментальных исследований на имитационных моделях и прототипе и анализа результатов используются методы математической статистики и теории планирования эксперимента.
Научная новизна работы.
Предложена модель системы параллельных периодических заданий - граф генераторов и преобразователей данных, развивающая известную в области проектирования систем ЦОС модель синхронных потоков данных (SDF), позволяя адекватно представить алгоритмы цифровой обработки сигналов, в том числе, вычисления с накоплением, и раскрыть параллелизм многоканальной обработки за счет расщепления заданий. Расщепление заданий дает возможность гибко использовать внутренний параллелизм алгоритмов многоканальной обработки сигналов с независимой обработкой каналов при распределении заданий в многопроцессорной системе.
Предложена методика организации процесса обработки данных, которая позволила осуществить оптимальное распределение и планирование связанных по данным периодических заданий в многопроцессорной системе со сложной кластерной топологией при ограничениях на сроки выполнения заданий и объем доступной оперативной памяти. В отличие от существующих подходов методика использует расщепление заданий для оптимального распараллеливания алгоритмов многоканальной обработки и динамическое планирование заданий и
потоков данных во время функционирования системы, что позволяет управлять бесконечным периодическим процессом обработки данных с использованием операционной системы реального времени. Методика, позволяет аналитически рассчитывать показатели эффективности,программного обеспечения, основываясь на теоретически обоснованных границах времени выполнения заданий, и обеспечивает улучшение показателей эффективности: времени отклика, пропускной способности и коэффициента использования памяти. 3. Расширена область применения известного алгоритма динамического планирования EDF (Earliest Deadline First) на смещенные периодические операции, которые не относятся к известным классам строго периодических и спорадических операций. В работе показано, что смещенные периодические операции возникают вследствие динамического планирования связанных по данным операций в многопроцессорной системе.
Достоверность, результатов. Достоверность теоретических выводов подтверждается доказательствами утверждений, реальностью- исходных данных и их представительностью для класса ММСЦОС. Все теоретические результаты, проверены с использованием специально» разработанных имитационных моделей, а также на реальном прототипе вычислительной системы. Достоверность результатов экспериментальных исследований* подтверждается планированием экспериментов, указанием доверительных интервалов и доверительных вероятностей, корректной статистической обработкой результатов имитационного моделирования.
Практическая, значимость работы. Полученные в диссертационной работе модели и алгоритмы могут быть использованы для автоматизации* процесса проектирования, программного обеспечения ММСЦОС. Использование предложенной методики позволяет сократить сроки проектирования, гарантировать работоспособность проектируемых систем, в условиях реального времени, повысить эффективность использования вычислительных ресурсов. Применение разработанного инструментального средства позволяет выполнить автоматическую генерацию шаблонов- программного кода программ, исполняемых как под управлением специализированной операционной системы, прототип которой также разработан в данной работе, так и под управлением операционной системы RTLinux. Возможность автоматической генерации имитационных моделей позволяет путем
имитационного моделирования уточнить принятые решения и обнаружить ошибки на ранних этапах проектирования. Принципы, сформулированные в диссертационной работе, являются основой для разработки ОСРВ для ММСЦОС.
Реализация результатов работы. По результатам исследований разработаны: пакет инструментального программного обеспечения для поддержки проектирования ПО ММСЦОС, библиотека программ имитационного моделирования, прототип операционной системы реального времени. Результаты использовались в процессе проектирования программного обеспечения многоканальных вычислительных комплексов для обработки гидроакустических сигналов, разрабатываемых ФГУП «Камчатский гидрофизический институт», акт о внедрении приложен к диссертации.
Апробация работы. Основные идеи и результаты работы докладывались на конференциях «VII Всероссийская конференция по проблемам науки и высшей школы» (2003 год), «VIII Всероссийская конференция по проблемам науки и высшей школы» (2004 год), «Молодые ученые - промышленности Северо-Западного региона» (2004 год) и «38-я международная научная конференция аспирантов и студентов «Процессы управления и устойчивость»» (2007 год).
Публикации. По результатам диссертационной работы опубликовано десять печатных работ, в том числе в журнале «Системы управления и информационные технологии» (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»). Всего опубликовано пять журнальных статей и пять тезисов конференций. Работа поддержана грантами: для поддержки научно-исследовательской работы аспирантов вузов Федерального агентства по образованию 2004 года № А04-3.16-482 и грантом правительства Санкт-Петербурга 2003 года (диплом АСП № 303406).
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников. Общий объем работы составляет 168 печатных страниц, работа включает 26 рисунков, список источников из 113 наименований, четыре приложения, в которые вынесены численные результаты экспериментов, описания программ, обзор и сравнение известных методов распределения и планирования вычислений, обзор и выбор средств имитационного моделирования.
Анализ аппаратных средств многопроцессорных систем цифровой обработки сигналов
Системы ЦОС относятся к классу встраиваемых вычислительных систем (embedded systems). Встраиваемой системой называется система, управляемаяг вычислителем, являющимся неотъемлемой составной частью этой системы [1]. Особенности аппаратного обеспечения, специфические требования к условиям функционирования и характеристикам вычислительных систем такого класса определяют использование специализированного программного обеспечения.
С развитием возможностей встраиваемых вычислительных систем становится целесообразным выделить системный слой программного обеспечения операционную систему для встраиваемых вычислительных систем. Большинство операционных систем для встраиваемых вычислительных систем в той или иной форме реализуют требования реального времени. Операционная система реального времени (ОСРВ) - это многозадачная операционная система, обеспечивающая работу приложений, выполняющихся в условиях определенных ограничений на временные характеристики отклика. Ключевой особенностью операционной системы реального времени являются предсказуемые характеристики времени выполнения заданий. В связи с этим важнейшей функцией операционной системы реального времени является реализация дисциплины планирования заданий.
Среди операционных систем реального времени можно выделить ОСРВ общего назначения, такие как QNX, VxWorks, LynxOS и операционные системы, ориентированные на ЦСП: DSP/BIOS, OSE, ThreadX, VSPWorks, Trident. К последнему типу ОС относятся также SharcOS и TigerSharcOS — операционные системы для семейств процессоров SHARC и TigerSHARC соответственно, разрабатываемые в лаборатории программно-аппаратных разработок кафедры автоматики и вычислительной техники СПбГПУ [8]. В настоящее время данным операционным системам недостает поддержки планирования заданий жесткого реального времени. Данная работа посвящена развитию принципов построения систем реального времени для многопроцессорных систем ЦОС, которые могут быть непосредственно воплощены на практике в рамках работы над совершенствованием систем SharcOS/TigerSharcOS.
Большинство вычислительных алгоритмов из предметной области, описанной в п. 1.1, относится к классу задач цифровой обработки сигналов. В связи с этим особенности данного класса задач определяют свойства и характеристики разрабатываемых вычислительных систем. К задачам цифровой обработки сигналов, в первую очередь, относятся: дискретная фильтрация, дискретное преобразование Фурье (ДПФ), спектральный и корреляционный анализ сигналов [27].
Некоторые характерные особенности алгоритмов цифровой обработки сигналов могут быть сформулированы в виде следующих тезисов:
Время выполнения вычислительных процедур не зависит от фактических данных на входе. Большинство алгоритмов цифровой обработки сигналов сводится к множеству операций умножения и сложения комплексных чисел. Число таких операций зависит от размерности входных данных, но не от их значений. В современных ЦСП время выполнения операций умножения и сложения также не зависит от значений операндов.
Параллелизм вычислений заложен в основе алгоритмов. Большинство процедур выполняются над массивами отсчетов сигналов, что естественным образом, вносит параллелизм в алгоритмы обработки. В частности, быстрое преобразование Фурье может быть реализовано параллельно. Кроме того, в ряде современных ЦСП параллелизм обработки массивов данных реализуется с помощью SIMD-расширений. Однако, в, условиях множества каналов входной информации, по каждому из которых необходимо выполнять однотипные операции, появляется, еще одна; более существенная, степень параллелизма — параллелизм1 многоканальной обработки. Если число каналов велико, то именно эта степень параллелизма может быть наиболее эффективно использована в многопроцессорной вычислительной- системе. При этом параллелизм алгоритмов может быть реализован внутри одного процессора посредством VLIW и SIMD команд.
Периодичность выполнения процедур. Входные данные поступают на вход вычислительной системы в виде непрерывных аналоговых сигналов. Однако, алгоритмы цифровой обработки сигналов требуют массивы отсчетов, которые должны быть полностью готовы к моменту начала вычислений. Таким образом, входящие отсчеты подвергаются предварительному накоплению в промежуточных буферах. Учитывая постоянство частоты дискретизации и размерности обрабатываемых массивов, такое накопление порождает детерминированный периодический процесс поступления входных данных.
Вычисления с накоплением. Ряд алгоритмов ЦОС (в частности, корреляционный и спектральный анализ) требуют усреднения- по ансамблю реализаций случайного сигнала. Результат таких вычислений может быть сформирован не после каждого поступления массива отсчетов, а после накопления результатов вычислений над множеством таких массивов.
В настоящее время становится- очевидным, что достижение высокой производительности вычислений, невозможно без использования параллелизма. Существует две основные парадигмы параллельного программирования, используемые наиболее часто: параллелизм данных и параллелизм заданий. В [24] и ряде других работ последняя- парадигма именуется «параллелизм задач», поэтому для дальнейшего использования в тексте работы, следует уточнить терминологию. В литературе встречается различный перевод на русский язык английского слова task: «задание» либо «задача».
Формализация класса систем ММСЦОС
Из рассмотренных известных моделей параллельных вычислений модель синхронных потоков данных (SDF) наиболее близка рассматриваемому классу вычислительных систем. В связи с этим целесообразно использовать данную модель в качестве прототипа, расширив ее за счет более полного представления потоков данных и учета параллелизма многоканальной обработки. Следующие свойства модели SDF соответствуют классу ММСЦОС и должны быть унаследованы в разрабатываемой модели: Представление параллельной программы в виде ориентированного графа, вершины которого соответствуют заданиям, а дуги — путям передачи данных. Сопоставление с каждой вершиной графа детерминированного времени обработки одной порции данных, не зависящего от самих данных. Сопоставление с каждой дугой чисел производимых и потребляемых фрагментов данных (токенов). Соотношения данных чисел определяют периоды срабатывания вершин графа.
Для более полного удовлетворения требованиям исходная модель SDF должна быть доработана в следующих направлениях:
Представление параллелизма многоканальной обработки. Многие алгоритмы позволяют независимо обрабатывать данные по отдельным каналам. Подобные свойства алгоритмов должны компактно и конструктивно представляться в модели.
Адекватное представление динамики потоков данных. Исходная модель, в которой каждая вершина графа формирует заданное количество данных при каждом срабатывании, может быть усовершенствована, в частности, для адекватного описания процессов с накоплением данных, часто встречающихся на практике. В модели с накоплением данных токены могут формироваться не при каждом срабатывании вершины, а один раз в несколько срабатываний.
Анализ функционирования реальных систем обработки гидроакустической информации [31], как представителей класса ММСЦОС, позволяет выделить характерные особенности этого класса систем. С точки зрения общей теории систем [23] ММСЦОС представляет собой детерминированную временную систему S czXxY,X AT,YQBT , где А — алфавит входных символов, В — алфавит выходных символов, Т— множество моментов времени, Ат и Вт — множества всевозможных отображений из Т в А и В соответственно. Входной- объект X формируется блоком аналого-цифрового преобразования (АЦП), который осуществляет квантование входных аналоговых сигналов C,(t), в результате которого формируются последовательности дискретных отсчетов Z,(k), и буферизацию отсчетов (рис. 2.1).
Таким образом, исходные данные поступают периодическими одинаковыми порциями {всплесками) с постоянным периодом. Размер порции, являющийся параметром, задаваемым при проектировании, в дальнейшем называется величина всплеска. Алгоритмы промежуточной обработки получают данные также определенными порциями (возможно, ожидая накопления до размера порции) и, после обработки, выдают данные также всплесками определенного размера. При постоянном периоде поступления входных данных период выдачи результатов также является постоянным (это допущение справедливо, учитывая свойство независимости времени обработки от значений данных).
Таким образом, можно сделать вывод о том, что потоки данных в рассматриваемой системе принадлежат к определенному классу. Общий вид потока данного класса представлен на рис. 2.2. Поток состоит из периодических порций данных (всплесков) величины NB с постоянным периодом всплесков Гв. Введя счетчик периодов р = 0, 1, ... и задав время передачи фрагмента данных по коммуникационному каналу т, получим следующее выражение для компоненты вектора входного объекта X
Детерминированный периодический поток
Следует отметить, что реальные потоки данных в многопроцессорной вычислительной системе с распределенной памятью могут отличаться от модели детерминированного периодического потока. В частности, конфликты, доступа к ресурсам и ожидания в очередях могут внести случайные вариации промежутков времени между поступлением всплесков данных. Однако, данная модель подходит для описания абстрактного поведения параллельной программы, не привязанного к конкретному исполнителю. Фактические временные характеристики, связанные с интерпретацией поведения программы на конкретном исполнителе, определяются далее на этапе планирования вычислений (см. главу 3). Собственно система ММСЦОС является функциональным преобразователем X— - Y, где выходной объект Y является вектором выходных отсчетов і \к) = КУ №), У Л )) функции преобразования представлены композициями составляющих функций этапов вычислений Ф J \—J,rг Ддд вычислений с накоплением (например, спектральный и корреляционный анализ) частота выходных отсчетов уменьшается пропорционально коэффициенту накопления (делителю) М: /, ) = F(Z(k),...,Z(k-M + \),F(k-l),. F(k-M)),k = Mq
Определение длительности вычислений и характеристик потоков данных
Формализованное описание системы параллельных заданий осуществляется на основе модели графа генераторов и преобразователей данных (ГГПД). Исходной информацией для формализованного описания является спецификация программного проекта по результатам этапа анализа проекта с указанием набора выделенных параллельных заданий, измеренных (или оцененных) времен выполнения заданий, характеристик потоков данных. Ниже приводится способ расчета базовых характеристик - вычислительных весов и интенсивностей потоков данных для случая, когда модель вычислительного процесса представляет собой ГГПД в форме дерева с расщеплением. Возможные расширения на более общие виды графов обсуждаются далее.
Рассмотрим систему параллельных заданий, описываемую графом генераторов и преобразователей данных в виде дерева с расщеплением. Поскольку данный граф является бесконтурным, то все его вершины могут быть упорядочены таким образом, что любая дуга начинается в вершине с меньшим номером и заканчивается в вершине с большим номером. Пусть i=L.т - номера вершин в соответствии с введенным порядком, от - число вершин в графе.
Вычислительным весом преобразователя называется отношение времени обработки одной активизации задания к периоду активизации: с = oi; Тої/ (3.3) X где Тої — время обработки /-ого преобразователя, Tt период активизации /-го преобразователя.
Вычислительный вес генераторов и терминаторов принимается равным 0. Средней интенсивностью потока данных от генератора или преобразователя называется отношение величины всплеска потока к периоду всплесков: где / - индекс задания, j - индекс потока для данного задания.
Для генераторов величины NBy и Тцц каждого генерируемого потока данных являются заданными в модели ГГПД. Для потоков данных, генерируемых преобразователями, величины NBlJ заданы в модели ГТПД, а период потока вычисляется на основе периода активизации задания с учетом делителя.
Период активизации преобразователя в модели ГГПД определяется интенсивностью входных потоков данных и числом активизации. Для ГТПД в виде дерева с расщеплением справедливо следующее соотношение: Т = А /є V (3-5) Ас/() где I(i) - множество входящих потоков преобразователя /, 0 - множество преобразователей, NA, — количество данных для активизации 1-го преобразователя.
Тогда период /-го потока данных, генерируемого преобразователем /, определяется выражением: TBlJ=MvT,= f-,i Q, (3.6) где Му — делительj-ro потока преобразователя і.
Таким образом, период потоков, генерируемых преобразователем, зависит от интенсивностей входящих потоков данного преобразователя.
Исходя из вышесказанного, можно предложить следующий алгоритм расчета интенсивностей потоков данных между заданиями в ГТПД:
1. Для всех генераторов рассчитываются интенсивности генерируемых потоков данных на основе параметров модели ГГПД по формуле (3.4).
2. Для всех преобразователей рассчитываются периоды всплесков по формуле (3.6) и интенсивности генерируемых потоков по формуле (3.4). При этом перебор заданий осуществляется в порядке возрастания индекса /. Поскольку все задания упорядочены в соответствии с потоками данных, то при переходе к следующему заданию интенсивности всех входящих потоков данных известны.
Интенсивности потоков данных Xsa между всеми парами заданий (s, d) формируют матрицу интенсивностей потоков данных Л размера mxm, где m — число заданий в системе. Согласно приведенному алгоритму расчет матрицы интенсивностей осуществляется построчно, начиная с первой строки. Если в исходном ГГПД отсутствует дуга между парой заданий, то интенсивность потока данных между этими заданиями принимается равной 0.
Одновременно с вычислением матрицы интенсивностеи Л может быть получен также вектор вычислительных весов заданий С по формуле (3.3).
Предложенный алгоритм расчета вычислительных весов заданий и
интенсивностеи потоков данных справедлив для систем параллельных заданий из класса ГГПД-деревьев с расщеплением. Однако, данный метод может быть обобщен на случай ГГПД-сети с небольшими ограничениями.
Рассмотрим обобщение на случай бесконтурной ГГПД-сети. В формуле (3.5) использовано допущение, что период преобразователя зависит от суммы интенсивностеи потоков данных на входе. Это допущение справедливо для ГГПД-дерева с расщеплением, так как все потоки на входе одного преобразователя в таком графе однородны и имеют один и тот же период. В случае графа более общего вида допустимы неоднородные потоки данных на входе одного преобразователя с, потенциально, различными периодами. При этом для каждого класса входных потоков в спецификации преобразователя указывается отдельное число активизации NA/C- Однако, необходимо учесть, что условие согласованности ГГПД требует, чтобы вычислительная система могла функционировать постоянно без бесконечного накопления данных в буферах передачи. Поскольку модель вычислений предполагает, что преобразователь при каждой активизации потребляет данные от всех источников, то из этого очевидно следует, что периоды активизации преобразователя, рассчитанные по каждому входящему потоку должны быть равны. Таким образом, формула (3.5) может быть использована для расчета периода активизации преобразователя от каждого из неоднородных потоков на входе. При этом дополнительно может быть проверено условие равенства периодов по всем неоднородным потокам.
Архитектура инструментального средства
На основе анализа требований, перечисленных в п. 4.1.1, было принято решение использовать для разработки инструментального программного средства язык программирования и платформу Java, разработанную корпорацией Sun Microsystems. Такой выбор обеспечивает требуемую переносимость разрабатываемого программного средства. Кроме того, язык программирования Java является современным объектно-ориентированным языком, имеющим основательную поддержку в виде удобных средств разработки. Таким образом, выбор данного языка программирования способствует эффективной и качественной разработке программного кода.
В качестве формата данных для хранения входной и выходной информации выбран язык XML. XML является стандартным метаязыком разметки, позволяющим создавать конкретные форматы хранения данных (языки разметки) в форме схем XML. Документы XML могут быть при необходимости прочитаны человеком или обработаны стандартным анализатором XML во внешней программе. Таким образом, выбор указанного формата хранения данных отвечает предъявленным требованиям.
Для поддержки различных типов обрабатываемых данных были разработаны следующие схемы XML: XML-формат для хранения графов генераторов и преобразователей данных; XML-формат для хранения графов соединений процессоров; XML-формат для хранения таблиц маршрутизации данных; XML-формат для хранения распределений заданий по процессорам.
Обобщенная функциональная схема инструментального программного средства приведена на рис. 4.1. Исходные данные для инструментального средства представлены файлами описания параллельных заданий (ГТПД), описания целевой многопроцессорной системы (граф соединений процессоров), описания таблицы маршрутизации. Таблица маршрутизации может быть как входной, так и выходной информацией. В последнем случае инструментальное средство автоматически выполняет расчет таблицы маршрутизации по заданному графу соединений процессоров по алгоритму Дейкстры и сохраняет результат в соответствующем XML-файле.
. Обобщенная функциональная схема инструментального средства Реализацию алгоритмов распределения и планирования заданий выполняет программа TaskMappingConsole. Данная программа имеет графический пользовательский интерфейс и состоит из следующих основных модулей:
Анализаторы (парсеры) XML-форматов входных данных. Данные модули используют стандартную модель XML-napcepa DOM (Document Object Model). Анализаторы выполняют непосредственное считывание входных файлов и формирования соответствующих структур данных в памяти.
Модуль планирования вычислений и потоков данных (MultiprocessorScheduler).
Данный модуль выполняет расчет параметрического расписания заданий и потоков данных для всех процессоров и коммуникационных каналов в вычислительной системе.
Модуль оптимизации распределения заданий по методу сверхбыстрого отжига (FastSimulatedAnnealing). Различные целевые функции оптимизации задаются классами CriticalPathOptimizer, ThroughputOptimizer, RelativeBuffersOptimizer, ProcessorCountOptimizer. Ограничения оптимизации задаются классом MappingConstraints.
Модуль формирования выходных результатов для имитационного моделирования и шаблонов программного кода ММСЦОС (ModelConstructor).
Основной результат работы инструментального средства сохраняется в выходном файле распределения заданий. Данный файл содержит информацию о размещении заданий (возможно, расщепленных) на процессорах многопроцессорной вычислительной системы. Данная информация может быть проанализирована пользователем или использована внешним программным средством.
Для поддержки имитационных и экспериментальных исследований инструментальное средство способно автоматически генерировать имитационные модели для среды OMNet++ (на языке NED) или шаблоны программного кода для целевой многопроцессорной вычислительной системы (на языке С).
Некоторые харакгеристики разрабатываемой системы требуют подтверждения на этапе проектирования, поскольку неправильные решения на этом этапе могут привести к существенным затратам впоследствии, связанным с изменением архитектуры системы. Необходимость подтверждения возникает вследствие следующих причин: 1. наличие неучтенных в теоретической модели аспектов функционирования реальной системы; 2. потребность в получении характеристик вычислительной системы не для наихудшего случая, а для реальных условий; 3. поиск ошибок в расчете или формализации.
Верификация характеристик параллельной вычислительной системы может быть выполнена аналитически, однако, множество анализируемых состояний исследуемой системы существенно зависит от размерности и структуры системы. В [9] показано, что задача построения дерева историй параллельных процессов в общем случае не менее сложна, чем любая NP-полная задача. Однако, данная задача может быть упрощена и решена за полиномиальное время для частных случаев, например, для процессов с графом связности типа дерево.
При исследовании процессов в реальной вычислительной системе необходимо учитывать неявные взаимодействия процессов, которые не учитываются в графе параллельных заданий. К таким взаимодействиям относятся: переключение контекстов заданий, взаимное влияние потоков данных, передаваемых по одному коммуникационному каналу, совместный доступ к памяти и прочим ресурсам. В результате, даже для систем параллельных заданий с графом типа дерево реальная структура взаимодействий будет более сложной, а следовательно, непросто предложить эффективный алгоритм для аналитического решения задачи верификации такой системы.
