Методика и программные средства организации процесса обработки данных в многоканальной многопроцессорной системе цифровой обработки сигналов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Стручков, Игорь Вячеславович

• Стручков, Игорь Вячеславович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Стручков, Игорь Вячеславович

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

ВВЕДЕНИЕ.

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

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

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

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

1.3.1.Особенности системного программного обеспечения систем ЦОС.

1.3.2.Прикладное программное обеспечение.

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

1.5.Анализ моделей параллельных вычислительных процессов.

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.Определение длительности вычислений и характеристик потоков данных.

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.0беспечение адекватности имитационной модели.

4.2.3.Архитектура имитационной модели.

4.2.4.Выбор средства имитационного моделирования.

4.3.Прототип многопроцессорной операционной системы реального времени

4.3.1.Цель разработки прототипа и требования.

4.3.2.Архитектура прототипа операционной системы реального времени

4.4.Экспериментальные исследования корректности и применимости разработанных программных средств.

4.4.1.Экспериментальное исследование адекватности имитационной модели.

4.4.2.Экспериментальное подтверждение достоверности теоретических результатов.

4.4.3.Экспериментальное исследование области применимости методики на имитационной модели.

4.4.4. Сравнительное исследование характеристик предлагаемых систем с существующим аналогом.'.

4.4.5. Исследование эффекта от применения методики в реальной задаче проектирования многоканальной системы цифровой обработки сигналов.

4.5.Пути дальнейшего развития и совершенствования разработанной методики.

4.6.Вывод ы.

Введение диссертации (часть автореферата) на тему «Методика и программные средства организации процесса обработки данных в многоканальной многопроцессорной системе цифровой обработки сигналов»

Актуальность темы. Многоканальные многопроцессорные системы цифровой обработки сигналов (ММСЦОС) используются в гидроакустике и радиолокации - для обнаружения и идентификации объектов по отраженному сигналу или шуму, сопровождения обнаруженных объектов, прогнозирования местоположения и скорости движения объектов, классификации объектов; в астрофизике и ядерной физике - для спекгрометрии заряженных частиц; в телекоммуникациях — для обработки сигналов радиосвязи и кодирования звуковой и видеоинформации и других областях. Эти системы обработки данных имеют следующие особенности: поступление данных в реальном времени с высокой интенсивностью; большое количество параллельных каналов ввода; последовательные многоэтапные вычислительные процедуры обработки данных; однотипная вычислительная обработка данных от разных каналов; периодичность поступления порций входных данных с фиксированным периодом.

Рост требований к производительности и пропускной способности указанных систем, связанный с ростом объемов обрабатываемой информации, требует повышения эффективности использования вычислительных ресурсов. При этом реализация сложных алгоритмов ЦОС на многопроцессорных платформах требует эффективной организации взаимодействия компонентов системы, а смена аппаратных платформ требует переработки сложных программных систем. Решение данных задач вручную даже опытными проектировщиками становится все более длительным и трудоемким, а результаты проектирования становятся недостаточно эффективными.

Ресурсы современных процессоров ЦОС позволяют использовать операционные системы реального времени (ОСРВ) для управления вычислительным процессом и обменом данными между процессорами в многопроцессорной системе. Такими специализированными ОСРВ являются: DSP/BIOS, OSE, ThreadX, а также разрабатываемые в лаборатории программно-аппаратных разработок кафедры АиВТ СПбГПУ ОС для процессоров SHARC и TigerSHARC. Использование ОСРВ в системах ЦОС позволяет сделать прикладное ПО менее зависимым от аппаратной платформы. При этом вычислительный процесс разбивается на множество заданий, число которых, как правило, превышает число процессоров. Задания могут исполняться параллельно на отдельных процессорах или на одном процессоре в режиме разделения времени. Инструментальные средства разработки ПО ЦОС включают средства для создания, отладки,и моделирования систем. Однако, остается неавтоматизированной актуальная задача эффективной организации процесса обработки данных за счет рационального распределения заданий по процессорам и планирования заданий с учетом требуемых временных характеристик выполнения.

Для автоматизации этапа распределения-и планирования заданий необходимо формализовать исходные данные о задаче обработки данных в виде модели, отражающей параллелизм и количественные характеристики заданий, а также особенности их исполнения в системах класса ММСЦОС. Разработкой моделей параллельной обработки данных занимались многие исследователи. Модели Ч.Э.Р. Хоара [59], Р. Милнера [74], P.M. Карпа, P.E. Миллера, Ю.Г. Карпова [9] и др. создавались прежде всего с целью построения^ математического аппарата для спецификации поведения программ, верификации и исследований^их эквивалентных преобразований. Методика разработки программ логического управления на основе систем связанных автоматов, предложенная A.A. Шалыто [34], позволяет строить формально верифицируемые программы соответствующего класса, однако, не содержит способов спецификации временных характеристик алгоритмов. Для задач количественного и алгоритмического анализа P.' JI. Смелянским была предложена" модель функционирования распределенных систем [29], охватывающая не только поведение программ, но и характеристики аппаратуры, и программного окружения, обеспечивающих выполнение программы. Данный подход весьма полезен в задачах распределения и планирования заданий в многопроцессорных системах, что подтверждается в ряде работ [3, 13, 14]. В то же время, одно из ограничений подхода, а именно, конечность числа шагов в истории процесса, существенно для рассматриваемого класса задач, в которых большинство процессов являются бесконечными и периодическими.

Непосредственно для задач ЦОС чрезвычайно полезны модели вычислений, управляемых потоком данных (data flow). Среди таких моделей применительно к рассматриваемым задачам распределения и планирования вычислений в системах ЦОС наиболее близкой является модель синхронных потоков данных (Synchronous Data Flow, SDF) (Э. А. Ли и Д. Г. Мессершмитг) [71], однако, данная модель недостаточно отражает многоканальный характер обработки данных и вычисления с накоплением, характерные для ММСЦОС.

Представление параллелизма вычислений является важнейшим требованием к модели системы параллельных заданий. В зависимости от соотношения производительности вычислителя и требуемой интенсивности обработки информации выделяются случаи, когда вычислитель способен обрабатывать несколько потоков данных в режиме разделения' времени, один поток данных и случай, когда* для обработки потока данных требуется параллельная работа нескольких вычислителей [19]. В этом смысле современные многоканальные системы ЦОС представляют собой комбинированный случай: обработка каждого отдельно взятого канала (или группы каналов) на одном этапе может выполняться одним процессором, однако число каналов в системе превышает возможности одного процессора. Параллельная обработка отдельных этапов вычислений, связанных только по данным, осуществляется« за счет конвейеризации процессоров (макроконвейер). Однако, наиболее существенной степенью параллелизма является параллелизм многоканальной обработки. Характерной особенностью такого параллелизма является возможность гибко перераспределять нагрузку между процессорами, назначая отдельным процессорам группы независимых каналов для обработки. Подобный параллелизм может быть представлен расщеплением вычислительных заданий на независимые параллельные подзадания (экземпляры).

Таким» образом, для решения задач распределения и планирования вычислений в ММСЦОС может быть предложена модель системы параллельных заданий, развивающая модель-прототип ЗОБ за счет конструктивного представления параллелизма многоканальной обработки и более полного отражения алгоритмов обработки данных. В соответствии с принципами, изложенными в работах Р.Л. Смелянского, данная модель должна быть также дополнена моделью исполнителя — многопроцессорной вычислительной системы.

Распределению и планированию вычислений в многопроцессорных системах посвящены работы И. Оха [75], А. Бёрчарда [49], С. К. Баруа [38, 39], Г. К. Сиха [92, 93], К. К. Пархи [78, 79], Э. А. Ли, Д. Г. Мессершмитга [69, 70], Р. Л. Смелянского [29]. Однако, эти методы ориентированы, главным образом, на статическое планирование программ. Методы статического планирования, как правило, либо не учитывают периодический характер вычислений, либо рассматривают только ограниченное число периодов, что снижает показатели получаемых расписаний. В то же время, использование ОСРВ в качестве системного слоя ПО ММСЦОС предполагает динамическое планирование заданий на каждом процессоре. Основы динамического планирования заданий реального времени заложены в работе Ч. Лиу, Дж. Лейланда [73], где не допускаются взаимозависимости заданий. Возможность учета зависимостей заданий в директивных сроках предусмотрена в работе Я. Блазевица [45], но предложенный подход не подходит в случае вытесняющей многозадачности, характерной для ОСРВ. Кроме того, планирование должно учитывать коммуникационные затраты в многопроцессорной системе со сложными маршрутами потоков данных, вопросы многоканальной обработки и использования параллелизма внутри заданий, ограниченность ресурсов оперативной памяти, являющиеся важными для ММСЦОС. Рассмотрению именно этих вопросов посвящена данная работа.

В связи с вышесказанным актуальной является задача разработки методики и соответствующих программных средств автоматизированного распределения и планирования заданий реального времени в ММСЦОС с учетом коммуникационных затрат и параллелизма многоканальной обработки, в условиях ограниченности вычислительных ресурсов с целью повышения эффективности программного обеспечения. В настоящей работе проводится теоретическое и экспериментальное исследование в области программных средств организации (распределение заданий и расчет ресурсов) и управления (планирование и диспетчеризация) обработкой данных в ММСЦОС. При постановке рассматриваемых задач предполагается, что аппаратное обеспечение вычислительной системы к началу разработки ПО ММСЦОС предопределено. Тем не менее, предлагаемая методика может быть использована для определения минимально необходимого числа процессоров, при котором удовлетворяются условия реального времени, с целью выработки рекомендаций для разработчиков вычислительной системы.

Цель работы - разработка методики и программных средств автоматизации распределения и планирования процесса обработки данных в ММСЦОС, обеспечивающих повышение эффективности обработки данных и сокращение длительности проектирования ПО.

Задачи исследования. х

1. Модель системы параллельных заданий в ММСЦОС, представляющая характеристики алгоритмов цифровой обработки сигналов и параллелизм многоканальной обработки данных.

2. Оптимизация распределения заданий в многопроцессорной системе.

3. Планирование заданий и расчет характеристик вычислительного процесса.

4. Разработка инструментального ПО для автоматизации распределения и планирования заданий.

Методы исследования. В теоретических исследованиях применяются методы теории графов, системного анализа, теории расписаний, теории принятия решений, имитационного моделирования. При разработке программных средств используются методы теории и технологии объектио-ориентированного программирования. Для экспериментальных исследований на имитационных моделях и прототипе и анализа результатов используются методы математической статистики и теории планирования эксперимента.

Научная новизна работы.

1. Предложена модель системы параллельных периодических заданий - граф генераторов и преобразователей данных, развивающая известную в области проектирования систем ЦОС модель синхронных потоков данных (ЗОБ), позволяя адекватно представить алгоритмы цифровой обработки сигналов, в том числе, вычисления с накоплением, и раскрыть параллелизм многоканальной обработки за счет расщепления заданий. Расщепление заданий дает возможность гибко использовать внутренний параллелизм алгоритмов многоканальной обработки сигналов с независимой обработкой каналов при распределении заданий в многопроцессорной системе.

2. Предложена методика организации процесса обработки данных, которая позволила осуществить оптимальное распределение и планирование связанных по данным периодических заданий в многопроцессорной системе со сложной кластерной топологией при ограничениях на сроки выполнения заданий и объем доступной оперативной памяти. В отличие от существующих подходов методика использует расщепление заданий для оптимального распараллеливания алгоритмов многоканальной обработки и динамическое планирование заданий и потоков данных во время функционирования системы, что позволяет управлять бесконечнььм периодическим процессом обработки данных с использованием операционной системы реального времени. Методика, позволяет аналитически рассчитывать показатели эффективности,программного обеспечения, основываясь на теоретически обоснованных границах времени выполнения заданий, и обеспечивает улучшение показателей эффективности: времени отклика, пропускной способности и коэффициента использования памяти. 3. Расширена область применения известного алгоритма динамического планирования EDF (Earliest Deadline First) на смещенные периодические операции, которые не относятся к известным классам строго периодических и спорадических операций. В работе показано, что смещенные периодические операции возникают вследствие динамического планирования связанных по данным операций в многопроцессорной системе.

Достоверность, результатов. Достоверность теоретических выводов подтверждается доказательствами утверждений, реальностью- исходных данных и их представительностью для класса ММСЦОС. Все теоретические результаты, проверены с использованием специально» разработанных имитационных моделей, а также на реальном прототипе вычислительной системы. Достоверность результатов экспериментальных исследований* подтверждается планированием экспериментов, указанием доверительных интервалов и доверительных вероятностей, корректной статистической обработкой результатов имитационного моделирования.

Практическая, значимость работы. Полученные в диссертационной работе модели и алгоритмы могут быть использованы для автоматизации- процесса проектирования, программного обеспечения ММСЦОС. Использование предложенной методики позволяет сократить сроки проектирования, гарантировать работоспособность проектируемых систем, в условиях реального времени, повысить эффективность использования вычислительных ресурсов. Применение разработанного инструментального средства позволяет выполнить автоматическую генерацию шаблонов- программного кода программ, исполняемых как под управлением специализированной операционной системы, прототип которой также разработан в данной работе, так и под управлением операционной системы RTLinux. Возможность автоматической генерации имитационных моделей позволяет путем имитационного моделирования уточнить принятые решения и обнаружить ошибки на ранних этапах проектирования. Принципы, сформулированные в диссертационной работе, являются основой для разработки ОСРВ для ММСЦОС.

Реализация результатов работы. По результатам исследований разработаны: пакет инструментального программного обеспечения для поддержки проектирования ПО ММСЦОС, библиотека программ имитационного моделирования, прототип операционной системы реального времени. Результаты использовались в процессе проектирования программного обеспечения многоканальных вычислительных комплексов для обработки гидроакустических сигналов, разрабатываемых ФГУП «Камчатский гидрофизический институт», акт о внедрении приложен к диссертации.

Апробация работы. Основные идеи и результаты работы докладывались на конференциях «VII Всероссийская конференция по проблемам науки и высшей школы» (2003 год), «VIII Всероссийская конференция по проблемам науки и высшей школы» (2004 год), «Молодые ученые - промышленности Северо-Западного региона» (2004 год) и «38-я международная научная конференция аспирантов и студентов «Процессы управления и устойчивость»» (2007 год).

Публикации. По результатам диссертационной работы опубликовано десять печатных работ, в том числе в журнале «Системы управления и информационные технологии» (входит в «Перечень ведущих рецензируемых научных журналов и изданий, выпускаемых в Российской Федерации»). Всего опубликовано пять журнальных статей и пять тезисов конференций. Работа поддержана грантами: для поддержки научно-исследовательской работы аспирантов вузов Федерального агентства по образованию 2004 года № А04-3.16-482 и грантом правительства Санкт-Петербурга 2003 года (диплом АСП № 303406).

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников. Общий объем работы составляет 168 печатных страниц, работа включает 26 рисунков, список источников из 113 наименований, четыре приложения, в которые вынесены численные результаты экспериментов, описания программ, обзор и сравнение известных методов распределения и планирования вычислений, обзор и выбор средств имитационного моделирования.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Стручков, Игорь Вячеславович

Основные результаты работы заключаются в следующем:

1. Предложена модель системы параллельных периодических заданий в ММСЦОС -граф генераторов и преобразователей данных (ГГПД), представляющая особенности используемых алгоритмов и параллелизм многоканальной обработки за счет расщепления заданий (раздел 2.1).

2. Разработана методика организации процесса обработки данных в ММСЦОС (раздел 3.5), включающая оптимизацию распределения заданий в многопроцессорной системе (раздел 3.3) и способ динамического планирования операций реального времени с зависимостями по данным (раздел 3.4). Эффективность разработанной методики доказана теоретически и подтверждена экспериментально (раздел 3.6). Применение методики позволяет получить существенное улучшение времени отклика по сравнению с алгоритмом

3. Разработано инструментальное средство для автоматизации распределения и планирования заданий в ММСЦОС (раздел 4.1).

4. Разработана подсистема имитационного моделирования вычислительного процесса в ММСЦОС, позволяющая моделировать вычислительный процесс с учетом конфликтов доступа к общей памяти и измерять показатели эффективности программного обеспечения (раздел 4.2).

5. Разработан прототип операционной системы для ММСЦОС (раздел 4.3). Прототип исследован на реальной многопроцессорной вычислительной системе.

6. Разработанная методика применена с целыо оптимизации показателей эффективности ПО реальной системы обработки гидроакустических сигналов (раздел 4.4.5). Эффект от применения методики заключается в многократном снижении сроков разработки в сочетании с повышением показателей эффективности ПО до 31%.

Разработанная методика использована в процессе проектирования многопроцессорных комплексов обработки гидроакустических сигналов (акт о внедрении приложен к диссертации).

В ходе разработки и опытного применения методики организации процесса обработки данных в ММСЦОС были сформулированы следующие возможные направления для дальнейшего совершенствования:

1. Развитие методов планирования заданий и потоков данных с целью явного учета взаимодействий с общей внешней памятью.

2. Учет непостоянных и непериодических заданий.

3. Экспериментальное исследование применимости методики для более широкого класса графов заданий.

ЗАКЛЮЧЕНИЕ

В результате проведенных теоретических и экспериментальных исследований методов и средств распределения и планирования заданий разработана методика организации процесса обработки данных в ММСЦОС, созданы системные и инструментальные средства, позволяющие повысить эффективность обработки данных (уменьшить время обработки и затраты оперативной памяти, увеличить пропускную способность системы), сократить длительность проектирования ПО, повысить качество программных продуктов, упростить переход на новые платформы.

Список литературы диссертационного исследования кандидат технических наук Стручков, Игорь Вячеславович, 2008 год

1. Баррет С. Ф., Пак Д. Дж. Встраиваемые системы. Проектирование приложений на микроконтроллерах семейства 68НС12 / HCS12 с применением языка С. М.: Издательский дом «ДМК-пресс», 2007. - 640 с.

2. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. - 367 с.

3. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2004. - 599 с.

4. Гончаров Ю. Технология разработки eXpressDSP // Chip News. 2001. - №2. -Режим доступа: http://www.chip-nevvs.ru/archive/chipnews/200102/5.html

5. Данилов А. Современные цифровые процессоры обработки сигналов. // Электронные компоненты. 2003. - Вып. 4. - С. 23 - 30.

6. Карпов Ю.Г. Анализ и синтез параллельных информационных процессов на основе свойства когерентности : Автореф. дис. д-ра. техн. наук: 05.13.13 .— Санкт-Петербург, 1990 .— 33 с .— Библиогр.: с. 31-33.

7. Касьянов В.И., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 с.

8. Клаус Г. Кибернетика и философия. М.: ИЛ, 1963. - 529 с.

9. Конвей Р.В., Максвелл B.JL, Миллер JT.B. Теория расписаний. — М.: Главная редакция физико-математической литературы изд-ва «Наука», 1975. 359 с.

10. Костенко В.А. Крупноблочный параллелизм в задачах обработки сигналов // Программирование. 1997. - №2. - С. 67-75.

11. Костенко В.А., Смелянский PJL, Трекин А.Г. Синтез структур вычислительных систем, реального времени с использованием генетических алгоритмов // Программирование. 2000. - №5. - С. 63-72.

12. Куприянов М.С., Матюшкин Б. Д. Цифровая обработка сигналов: процессоры, алгоритмы, средства проектирования. СПб.: Политехника, 2002. - 592 с.

13. Липаев В.В. Методы обеспечения качества крупномасштабных программных средств: М.: СИНТЕГ, 2003. - 520 с.

14. Литюк В.И., Литюк Л.В. Методы цифровой многопроцессорной обработки ансамблей радиосигналов. М.: СОЛОН-ПРЕСС, 2007. - 592 с.

15. Ломазова И.А. Вложенные сети Петри: моделирование и анализ распределенных систем с объектной структурой. М.: Научный мир, 2004. - 207 с.

16. Лопатин A.C. Метод отжига // Межвузовский сборник «Стохастическая оптимизация в информатике» / ред. Граничин О.Н. СПб.: Изд-во СПбГУ, 2005. - С. 133- 149.

17. Мелехин В. Ф. Вычислительные машины, системы и сети : учебник для вузов / В. Ф. Мелехин, Е. Г. Павловский. М.: Академия, 2006. - 555 с.

18. Месарович М., ТакахараЯ. Общая теория систем: математические основы. -М.: Мир, 1978. -312 с.

19. Немнюгин С.А., Стесик O.JÏ. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ-Петербург, 2002. - 400 с.

20. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. -СПб.: КОРОНА принт; М.: Альтекс-А, 2004. 384 с.

21. Саати Т. Принятие решений. Метод анализа иерархий / Саати Т.; пер. с англ. Р. Г. Вачнадзе. М.: Радио и связь, 1993. - 315с.

22. Сергиенко А.Б. Цифровая обработка сигналов СПб.: Питер, 2003. - 603 с.

23. Сирота А.А. Компьютерное моделирование и оценка эффективности сложных систем. М.: Техносфера, 2006. - 280 с.

24. Смелянский P.JI. Модель функционирования распределенных вычислительных систем // Вестн. Моск. Ун-та. Сер. 15, Вычислительная математика и кибернетика. 1990. -№3. - С. 3-18.

25. Хьюз К., Хьюз Т. Параллельное и распределенное программирование на С+ +.: Пер. с англ. -М.: Издательский дом «Вильяме», 2004. 672 с.

26. Черноруцкий И.Г. Методы принятия решений. СПб.: БХВ-Петербург, 2005.-416 с.

27. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000. - 780 с.

28. Штофф В.А. Моделирование и философия. М., Л.: Наука, 1966. - 301 с.

29. Amoroso A., Marzullo К. Multiple Job Scheduling in a Connection-Limited Data Parallel System // IEEE Transactions on Parallel and Distributed Systems. February 2006. -Vol. 17, No. 2.-P. 125-134.

30. Bar-Noy A., Dreizin V., Patt-Shamir B. Efficient periodic scheduling by trees //

31. FOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings / IEEE. June 2002. - Vol. 2, 23-27. - P. 791-800.

32. Baruah S., Fisher N. The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems // IEEE Transactions on Computers. July 2006. - Vol. 55, No. 7.- P. 918-923.

33. Baruah S.K., Gehrke J.E., Plaxton C.G. Fast scheduling of periodic tasks on multiple resources // Proceedings., 9th International Parallel Processing Symposium, 1995. -April 1995. No. 25-28. - P. 280-288.

34. Beaumont O., Legrand A., Robert Y. Static scheduling strategies for heterogeneous systems. Technical Report 2002-29 / Ecole Normale Superieure de Lyon. July 2002. -Mode of access: http://citeseer.ist.psu.edu/beaumont02static.html.

35. Berman F. High-performance schedulers // The Grid: Blueprint for a New Computing Infrastructure / Foster I., Kesselman C. MorganKaufmann, 1998. - P. 279-309. - Mode of access: http://citeseer.ist.psu.edu/54356.html.

36. Berten V., Goossens J., Jeannot E. On the Distribution of Sequential Jobs in Random Brokering for Heterogeneous Computational Grids // IEEE Transactions on Parallel and Distributed Systems. February 2006. - Vol. 17, No. 2. - P. 113-124.

37. Bilsen G., Engels M., Lauwereins R., Peperstraete J.A. Cyclo-static data flow // International Conference on Acoustics, Speech, and Signal Processing, 1995; ICASSP-95. -May 1995. Vol. 5, 9-12. - P. 3255 - 3258.

38. Bilsen G., Engels M., Lauwereins R., Peperstraete J.A. Static scheduling of multi-rate and cyclo-static DSP-applications // VLSI Signal Processing, VII, 1994. 26-28 Oct. 1994.-P. 137-146.

39. Blazewicz J. Modeling and Performance Evaluation of Computer Systems. -North-Holland, Amsterdam, 1976.

40. Blazewicz J., Kovalyov M. Y., Machowiak M., Trystram D., Weglarz J. Preemptable Malleable Task Scheduling Problem // IEEE Transactions on Computers. -April 2006. Vol. 55, No. 4. - P. 486-490.

41. Boussemart F., Cavory G., Lecoutre C. Solving the cyclic job shop scheduling problem with linear precedence constraints using CP techniques // IEEE International Conference on Systems, Man and Cybernetics, 2002. 6-9 Oct. 2002. - Vol. 7. - P. 6.

42. Budenske J.R., Ramanujan R.S., Siegel H.J. On-line use of off-line derivedmappings for iterative automatic target recognition tasks and a particular class of hardware platforms // Proc. Sixth Heterogeneous Computing Workshop. 1 April 1997. - P. 96-110.

43. Burchard A., Liebeherr J., Oh Y., Son S.H. New strategies for assigning real-time tasks to multiprocessor systems // IEEE Transactions on Computers. Dec 1995. - Vol. 44, No. 12.-P. 1429-1442.

44. Casavant T. L., Kuhl J. G. A taxonomy of scheduling in general-purpose distributed computing systems // IEEE Trans. Softw. Eng. Feb. 1988. - Vol. 14, No. 2. - P. 141-154.

45. Geilen M., Basten T., Stuijk S. Minimising buffer requirements of synchronous dataflow graphs with model checking // Proceedings of the 42nd Design Automation Conference, 2005. 13-17 June 2005. - P. 819-824.

46. Gelabert P.R., Barnwell, T.P., III. Optimal automatic periodic multiprocessor scheduler for fully specified flow graphs // IEEE Transactions on Signal Processing. Feb 1993. - Vol. 41, No. 2. - P. 858-888.

47. Goddard S., Jeffay K. Managing Memory Requirements in the Synthesis of RealTime Systems from Processing Graphs // Proceedings of the Fourth IEEE Real-Time Technology and Applications Symposium. 1998. - P. 59-70.

48. Hluchy L., Dobrovodsky M., Dobrucky M. Static Mapping Methods for Processor Networks. Mode of access: http://citeseer.ist.psu.edu/472693.html

49. Hluchy L., Dobrovodsky D., Dobrucky M. Automatic Configuration of Parallel Programs for Processor Networks. Mode of access: http://citeseer.ist.psu.edu/783.html

50. Hluchy L., Dobrucky M., Dobrovodsky D. Distributed Static Mapping and Dynamic Load Balancing Tools under PVM. Mode of access: http://citeseer.ist.psu.edu/465012.html

51. Hoar C. A. R. Communicating Sequential Processes. Prentice Hall International, 1985.-238 p.

52. Horstmannshoff J., Meyr H. Optimized System Synthesis of Complex RT Level Building Blocks from Multirate Dataflow Graphs // Proceedings of 12th International Symposium on System Synthesis, 1999. 10-12 Nov. 1999. - P. 38-43.

53. Hu Y., Blake R. An optimal dynamic load balancing algorithm. Technical Report DL-P95-011 / Daresbury Laboratory, Warrington, UK. 1995. - Mode of access: http://citeseer.ist.psu.edu/hu95optimal.html

54. Hu Y. H., Wang D. J. Clustering approach for mapping recursive DSP algorithms to multiprocessor with fixed IPC delays // VLSI Signal Processing V / Ed. K. Yao, R. Jain, W. Przytula, J. Rabaey. IEEE Press, Piscataway, NJ, 1992. - P. 365-374.

55. Ingber L. Very fast simulated re-annealing // Mathematical and Computer Modelling. 1989. - No. 12. - P. 967-973.

56. Jacob J.C., Soo-Young Lee. Task spreading and shrinking on multiprocessor systems and networks of workstations // IEEE Transactions on Parallel and Distributed Systems. Oct. 1999. - Vol. 10, No. 10. - P. 1082-1101.

57. Kahn G. The semantics of a simple language for parallel programming // Info. Proc. Stockholm, Aug. 1974. - P. 471-475.

58. Kirkpatrick S. Optimization by Simulated Annealing: Quantitative Studies // Journal of Statistical Physics. 1984. - Vol. 34, No. 5/6. - P. 975-986.

59. Kruatrachue B., Lewis T. Grain size determination for parallel processing // IEEE Software. Jan. 1988. - Vol. 5, No. 1. - P. 23-32.

60. Lamport L. Time, clocks and the ordering of events in a distributed system // Communications of the ACM: July 1978. - No. 21(7). - P. 558-565.

61. Lee D:Y., DiCesare F. Petri nets and heuristic search for periodic scheduling // IEEE International Conference on Systems, Man and Cybernetics, 1992. 18-21 Oct. 1992. -Vol.2.-P. 998-1003.

62. Lee E.A., Messerschmitt D.G. Pipeline Interleaved Programable DSP's: Synchronous Data Flow Programming // IEEE Transactions on Acoustics, Speech, and Signal Processing. September 1987. - Vol. ASP-35, No. 9. - P. 1334-1345.

63. Lee E.A., Messerschmitt D.G. Synchronous Data Flow // Proceedings of the IEEE. September 1987. - Vol. 75, No. 9. - P. 1235-1245.

64. Lin H.-D., Messerschmitt D.G. Transforming arbitrary data flow graphs to synchronous data flow graphs // IEEE International Symposium on Circuits and Systems, 1989.-8-11 May 1989. Vol. 1. - P. 319-322.

65. Liu C., Layland J. Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment // Journal of the ACM. Jan. 1973. - No. 20(1). - P. 46-61.

66. Milner R. A Calculus of Communicating Systems. Springer-Verlag New York, Inc., 1982. - 260 p.

67. Oh Y., Son S. H. Tight Performance Bounds of Heuristics for a Real-Time Scheduling Problem. Mode of access: http://citeseer.ist.psu.edu/613343.html

68. O'Neil T. W., Sha E. H.-M. Retiming Synchronous Data-Flow Graphs to Rcduce Execution Time // IEEE Transactions on Signal Processing. October 2001. - Vol. 49, No. 10. - P. 2397-2407.

69. Parhi K.K. Algorithm transformation techniques for concurrent processors // Proceedings of the IEEE. Dec. 1989. - Vol: 77, No. 12. - P. 1879-1895.

70. Parhi K.K., Messerschmitt D.G. Static rate-optimal scheduling of iterative dataflow programs via optimum unfolding // IEEE Transactions on Computers. Feb 1991. -Vol. 40, No. 2. - P. 178-195.

71. Park H.-J., Kim B.K. An efficient optimal task allocation and scheduling algorithm for cyclic synchronous applications // Sixth International Conference on RealTime Computing Systems and Applications, 1999; RTCSA '99. 13-15 Dec. 1999. - P. 78 -85.

72. Plotkin G. D. A Structural Approach to Operational Semantics. DAIMI-FN19, Aarhus University, 1981. - 132 p.

73. Polychronopoulos C.D. Compiler optimizations for enhancing parallelism andtheir impact on architecture design // IEEE Trans, on Computers. 1988. - Vol. 37, No. 8. -P. 991-1004.

74. Qi Z., Hui L., Baifeng W. Co-optimization of buffer requirement and response time for SDF graph // Proceedings of The 8th International Conference on Computer Supported Cooperative Work in Design, 2004. 26-28 May 2004. - Vol. 2. - P. 333 - 336.

75. Ramamurthy S., Moir M. Static-priority periodic scheduling on multiprocessors // The 21st IEEE Real-Time Systems Symposium, 2000. Proceedings. 27-30 Nov. 2000. - P. 69-78.

76. Rutten E., Martinez F. SIGNAL GTi: implementing task preemption and time intervals in the synchronous data flow language SIGNAL // Proceedings of the Seventh Euromicro Workshop on Real-Time Systems, 1995. 14-16 June 1995. - P. 176-183.

77. Saez S., Vila J., Crespo A. Firm Aperiodic Task Scheduling in Hard Real-Time Multiprocessor Systems. Mode of access: http://citeseer.ist.psu.edu/730432.html

78. Scheurer C., Scheurer H., Kropf P. Load balancing driven process migration. Tech. Rep. / University of Berne. June 1995. - Mode of access: http://citeseer.ist.psu.edu/scheurer951oad.html

79. Shao Z., Zhuge Q., Xue C., Sha E.H.-M. Efficient Assignment and Scheduling for Heterogeneous DSP Systems // IEEE Transactions on Parallel and Distributed Systems. -June 2005. Vol.16, No. 6. - P. 516-525.

80. Shin K.G., Chang Y.-C. A reservation-based algorithm for scheduling both periodic and aperiodic real-time tasks // IEEE Transactions on Computers. Dec 1995. -Vol. 44, No. 12. - P. 1405-1419.

81. Sih G.C., Lee E.A. A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures // IEEE Transactions on Parallel and Distributed Systems. February 1993. - Vol. 4, No. 2. - P. 175-187.

82. Sih G.C., Lee E.A. Declustering: A New Multiprocessor Scheduling Technique // IEEE Transactions on Parallel and Distributed Systems. June 1993. - Vol. 4, No. 6. - P. 625-637.

83. Sinnen O., Sousa L.A. Communication Contention in Task Scheduling // IEEE Transactions on Parallel and Distributed Systems. June 2005. - Vol.16, No.6. - P. 503-515.

84. Sinnen O., Sousa L. Scheduling Task Graphs on Arbitrary Processor Architectures Considering Contention // High Performance Computing and Networking. -Springer-Verlag LNCS 2110, 2001. P. 373-382.

85. Sinnen O., Sousa L.A., Sandnes F.E. Toward a Realistic Task Scheduling Model // IEEE Transactions on Parallel and Distributed Systems. March 2006. - Vol. 17, No. 3. - P. 263-275.

86. Sohn J., Robertazzi T. G., Luryi S. Optimizing Computing Costs Using Divisible Load Analysis // IEEE Trans. Parallel Distrib. Syst. Mar. 1998. - Vol. 9, No. 3. - P. 225234.

87. Spooner D. P., Nudd G. R. Allocating Non-Real-Time and Soft Real-Time Jobs in Multiclusters // IEEE Trans. Parallel Distrib. Syst. Feb. 2006. - Vol. 17, No. 2. - P. 99112.

88. Swiecicka A., Seredynski F. Multiprocessor Scheduling and Rescheduling with Use of Cellular Automata and Artificial Immune System Support // IEEE Trans. Parallel Distrib. Syst. Mar. 2006. - Vol. 17, No. 3. - P. 253-262.

89. Tao Y., Cong F. Heuristic algorithms for scheduling iterative task computations on distributed memory machines // IEEE Transactions on Parallel and Distributed Systems. June 1997. - Vol. 8, No. 6. - P. 608-622.

90. Tao Y., Gerasoulis A. DSC: scheduling parallel tasks on an unbounded number of processors // IEEE Transactions on Parallel and Distributed Systems. Sep 1994. - Vol. 5,No. 9.-P. 951-967.

91. Tate D.M., Smith A.E. A Genetic Approach to the Quadratic Assignment Problem // Computers & Operations Research. 1995. - No. 22(1). - P. 73-83.

92. Tsuchiya T., Osada T., Kikuno T. A new heuristic algorithm based on GAs for multiprocessor scheduling with task duplication // 3rd International Conference on

93. Algorithms and Architectures for Parallel Processing, 1997; ICAPP 97. 10-12 Dec. 1997. -P. 295-308.

94. Wang D.-J., Hu Y.H. Fully static multiprocessor array realizability criteria for real-time recurrent DSP applications // IEEE Transactions on Signal Processing. May1994. Vol. 42, No. 5. - P. 1288-1292.

95. Wang D.-J., Hu Y.H. Multiprocessor implementation of real-time DSP algorithms // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. Sept.1995. Vol. 3, No. 3. - P. 393-403.

96. Wang C.M., Wang S.D. Efficient Processor Assignment Algorithms and Loop Transformations for Executing Nested Parallel Loops on Multiprocessors // IEEE Trans. Parallel Distrib. Syst. Jan. 1992. - Vol. 3, No. 1. - P. 71-82.

97. Wu M.-Y., Gajski D.D. Ilypertool: a programming aid for message-passing systems // IEEE Transactions on Parallel and Distributed Systems. Jul 1990. - Vol. 1, No. 3.-P.330-343.

98. Zhiwei X. Executing Synchronous Data Flow Graphs on Multicomputer // Proceedings of The Sixth Distributed Memory Computing Conference, 1991. April 28-May 1, 1991.-P. 214-217.

99. Гл. специалист ФГУП «КГФИ»1. Б. С. Аршанский