автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методика и программные средства организации процесса обработки данных в многоканальной многопроцессорной системе цифровой обработки сигналов

На правах рукописи

00345В821

Стручков Игорь Вячеславович

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

Специальность

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

и

Санкт-Петербург - 2008

003458821

Работа выполнена на кафедре «Автоматики и вычислительной техники» государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный политехнический университет».

Научный руководитель:

доктор технических наук, профессор

Мелехин Виктор Федорович

Официальные оппоненты:

доктор технических наук, профессор

Устинов Сергей Михайлович

кандидат физико-математических наук Иванов Александр Николаевич

Ведущая организация

ФГУП «НПО Аврора»

Защита состоится «12» февраля 2009 г. в часов на заседании Диссертационного Совета Д 212.229.18 при ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, Санкт-Петербург, ул. Политехническая, д. 21, 9-й учебный корпус, ауд. 325.

С диссертацией можно ознакомиться в фундаментальной библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан «*©» декабря 2008 г.

Ученый секретарь

Диссертационного совета ----

кандидат технических наук, доцент /^Л сгс_\, Васильев А.Е.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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). Особенностью многопроцессорной системы является кластерная организация: цифровые сигнальные процессоры (ЦСП, DSP) размещены на платах, внутри которых обмен данными возможен через общую память. Обмен между процессорами на разных платах осуществляется посредством коммуникационных каналов.

Для автоматизации этапа распределения и планирования заданий необходимо формализовать исходные данные в виде модели системы параллельных заданий, отражающей параллелизм и количественные характеристики используемых алгоритмов. Известны теории и модели параллельных вычислений, предложенные Ч.Э.Р. Хоаром, Р. Милнером, P.M. Карпом, P.E. Миллером, Ж. Каном, Э. А. Ли, В. В. Воеводиным, Р. Л. Смелянским, Ю.Г. Карповым, A.A. Шалыто и др. Применительно к рассматриваемым задачам распределения и планирования заданий в системах ЦОС наиболее близкой является модель синхронных потоков данных Synchronous Data Flow (SDF) Э. A. Ли, которая, однако, не отражает многоканальный характер обработки данных и вычисления с накоплением, характерные для ММСЦОС. Для решения задач распределения и планирования заданий в ММСЦОС может быть предложена модель системы параллельных заданий, развивающая модель-прототип SDF за счет конструктивного представления параллелизма многоканальной обработки и более адекватного отраже-

ния алгоритмов обработки данных. В соответствии с принципами, изложенными в работах Р.Л. Смелянского, да1шая модель должна быть также дополнена моделью исполнителя — многопроцессорной вычислительной системы.

Хост-компьютер

Потребители

результатов

Многопроцессорная система

[ Р2Р|[ ргр"]

[р5Р |[О5Р"|

[ Р8Р|| ОЭр] [ ОЭР | [ Р5Р~]

[ Р5Р |["5Р| | РЭР | |"р5р"|

НН ¡ви

[ 0$Р ] [ РЭР ] [ Р8Р |[ 0$р]

лип

¡Б,ХР |

АЦП

[ ! . ]

лип

| Ьуфв 1

. ь-зд. ] , АЦП

Рис. 1. Структурная схема системы обработки гидроакустических сигналов

Распределению и планированию вычислений в многопроцессорных системах посвящены работы И. Оха, А. Берчарда, С. К. Баруа, Г. К. Сиха, К. К. Пархи, Э. А. Ли, Д. Г. Мессершмитта, Р. Л. Смелянского. Однако, эти работы ориентированы на статическое планирование вычислений. Методы статического планирования, как правило, либо не учитывают периодический характер вычислений, либо рассматривают только ограниченное число периодов, что снижает показатели получаемых расписаний. В то же время, использование ОСРВ в качестве системного слоя ПО ММСЦОС предполагает динамическое планирование заданий на каждом процессоре. Основы динамического планирования периодических заданий реального времени заложены в работах Ч. Лиу, Дж. Лейланда, где не допускаются взаимозависимости заданий. Кроме того, планирование должно учитывать коммуникационные затраты в многопроцессорной системе со сложными маршрутами потоков данных, вопросы многоканальной обработки и использования параллелизма внутри заданий, ограниченность ресурсов оперативной памяти, являющиеся важными для ММСЦОС. Исследованию именно этих вопросов посвящена данная работа.

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

В качестве основного результата представлена новая модель системы параллельных периодических заданий, являющаяся развитием модели ЭОР, - граф генераторов и преобразователей данных (ГГПД). В модели ГГПД выделяется три типа заданий: генератор, преобразователь и терминатор. Генератор периодически формирует всплески данных и характеризуется параметрами: период всплесков (7*,,), количество фрагментов во всплеске (М,). Преобразователь активизируется после получения заданного количества входных данных и характеризуется параметрами: количество входных фрагментов для активизации (К), время обработки (Т„), для каждого получателя: количество фрагментов во всплеске (ДО,), для каждого получателя: делитель, то есть количество активизаций, после которого генерируется всплеск (М), требуемый

объем оперативной памяти (V). Терминатор не имеет выходов и параметров и обозначает конец вычислений.

Определение. Графом генераторов и преобразователей данных (рис. 2) называется ориентированный граф с вершинами трех типов, задаваемый четверкой (Г, в, О, Ф), где Г = {у,(Т„, И.,)} - множество вершин-генераторов, в = {в,(Т„„ Ма„ {К,}, {М,;}, V,)} -множество вершин-преобразователей, О - множество вершин-терминаторов, Ф — отношение потоковой зависимости по данным ФсГх0иГхйи0х0и0хй,

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

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

Аппаратное обеспечение многопроцессорной системы представляется графом соединений процессоров - взвешенным ориентированным графом Н=(¥, Е, к1), где V = РиВиМ, Р — множество процессоров, В — множество плат, М — множество модулей памяти; Е = ЬиТ, где ЬсРхР — множество дуг-межпроцессорных связей (коммуникационных каналов), (ЭсРхВиМхВ — отношение размещения на платах; 14/ — веса вершин из множества М (объем модулей памяти), н' - веса дуг из

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

В третьей главе решается задача разработки методики организации процесса обработки данных в ММСЦОС. Формально ставится многокритериальная задача оптимального выбора с множеством альтернатив X, множеством исходов Y, детерминистской функцией отображения множества альтернатив во множество исходов <р: Х-^У и множеством показателей эффективности fk: Г-^R, к = 1,2,3, R - множество вещественных чисел. Используются показатели в соответствии с ГОСТ Р ИСО/МЭК 9126-93 (ISO 9126:1991): длительность обработки, пропускная способность, коэффициент использования оперативной памяти.

Исходные данные задаются в виде модели системы параллельных заданий (ГГПД) и графа соединений процессоров. Модель ГГПД определяет множество заданий Т = ГиОиП, а граф соединений процессоров определяет множество процессоров Р. Множество альтернатив X определяется декартовым произведением X - Zx S. Каждый элемент zs Z представляет собой функцию отображения заданий на процессоры z: Т-^Р. Каждый элемент s е S представляет собой функцию планирования s: Т-^{[/„, //„]}, ставящую в соответствие каждому заданию последовательность промежутков времени, в течение которых данное задание выполняется на некотором процессоре (под выполнением задания понимается выполнение всех его периодических повторений).

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

Для системы с п процессорами и т заданиями вектором состояния является вектор размерности т, где значение каждой координаты - номер процессора из диапазона [1, и]. Для того, чтобы обеспечить автоматическое расщепление/слияние заданий при оптимизации, каждый диапазон значений координаты вектора состояний между ближайшими целыми числами [к, к+I] разбивается на три зоны. При попадании значения координаты в диапазон [к, к + 0,25) считается, что задание распределено на процессор к. При попадании значения координаты в диапазон (к + 0,75, к+1] считается, что задание распределено на процессор к+1. При попадании значения координаты в диапазон [к + 0,25, к + 0,75] считается, что данный экземпляр задания отсутствует.

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

Расчет характеристик вычислительного процесса, на основе которых вычисляются показатели эффективности, осуществляется аналитически на этапе планирования вычислительного процесса. Основной особенностью процессов, задаваемых моделью ГГПД, является периодичность. Расчет периода задания-преобразователя для ГГПД-дерева с расщеплением:

Чк

где src(i,k) - индекс к-й операции-источника для преобразователя i.

В системе реального времени каждому повторению j каждого задания-преобразователя i назначается директивный срок выполнения D,,.

Определение. Допустимым называется такой план seS, при котором на каждом процессоре в один момент времени выполняется не более одного задания и каждое повторение j каждого задания i заканчивается до истечения соответствующего директивного срока D,,.

Для учета коммуникационных затрат в многопроцессорной системе осуществляется планирование не только выполнения заданий на процессорах, но и передач данных по коммуникационным каналам. С этой целью задания и передачи данных объединяются понятием операции, а процессоры и коммуникационные каналы - понятием исполнительные устройства. Длительность выполнения передачи всплеска данных потока i по каналу / равна Ne\v¡. При этом при планировании рассматривается множество операций 0= 6 и f , где 0 — множество заданий-преобразователей, ¥ -множество операций передачи данных. Тогда для любой пары (у„сол), у,е Г, со,е Í2 существует множество путей п = {**= j)\y,<o[k^ rof\ 0}, где ■<- отао-

шение непосредственного предшествования операции в пути данных.

Директивные сроки выполнения Д; для каждого повторения j каждой операции /' соответствуют окончанию периода:

Dg = t„+ jT„j=l..«, (2)

где t„ - момент старта первого повторения операции.

Как доказано Ч. Лиу и Дж. Лейландом, для независимых периодических заданий реального времени алгоритм динамического планирования, основанный на сроках выполнения, Earliest Deadline First (EDF) - «задание с ближайшим сроком выполнения -раньше» обеспечивает выполнение директивных сроков при загрузке процессора, не превышающей 1. Данный алгоритм неприменим напрямую для планирования операций в ММСЦОС, так как задания имеют зависимости по данным, в результате которых запросы к промежуточным операциям теряют строго периодический характер. Однако, если на входе каждой операции в каждом исполнительном устройстве поместить буфер, то, искусственно задерживая поступление запросов в данном буфере, можно обеспечить строгую периодичность поступления запросов и, таким образом, выполнить условия применимости алгоритма EDF. Начальные времена старта операций для такого периодического расписания с искусственными задержками могут быть рассчитаны по формуле:

tsl = max D ,. (3)

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

подхода, состоит в том, что при использовании алгоритма ЕБР искусственные задержки операций используются при расчете параметрического расписания, но игнорируются при диспетчеризации во время работы системы. При условии соблюдения директивного срока выполнения операции-источника запрос на выполнение операции-приемника может поступить раньше планового времени старта операции (с искусственной задержкой), но не позже.

Определение. Смещенными периодическими операциями называются операции, для которых существуют плановые периодические времена старта с детерминированным периодом, однако запрос на выполнение может поступить раньше планового времени старта (но не позлее).

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

Теорема 1. Пусть 5 — план выполнения множества периодических операций I на исполнительном устройстве р с использованием искусственных задержек на основе алгоритма ЕОР и директивных сроков выполнения Бу, д* — модифицированный таи выполнения на основе в с исключением искусственных задержек.

Тогда, если план у допустим, то план $* также допустим.

Доказательство теоремы 1 приводится в диссертации. Доказательство основано на рассмотрении кусочно-линейных функций запланированной работы \¥(1) и затраченной работы Т;^). Доказывается, что перенос части запланированной работы на более позднее время может только уменьшить мгновенное значение Т^) (этот факт доказывается во вспомогательной лемме).

Таким образом, алгоритм ЕБР применим для планирования смещенных периодических операций, и решение задачи планирования при заданном распределении заданий сводится к нахождению параметров /„ и ¿), операций на каждом исполнительном устройстве с помощью промежуточного параметрического расписания с искусственными задержками. При этом коэффициенты загрузки процессоров 11р и коммуникационных каналов 1/1 не должны превышать 1.

Для определения показателей эффективности используются фактические сроки выполнения операций (5,), являющиеся оценками длительности выполнения операций для наихудшего случая с учетом загрузки исполнительного устройства. На основании фактических сроков выполнения могут быть рассчитаны предельные размеры буферов передачи данных. Самый поздний момент удаления запроса из входного буфера преобразователя Ь, определяется выражением:

и = + (7)

Е,:

Самый ранний момент поступления запроса во входной буфер преобразователя

4 ] = згс(1,к),Е. = тах£,1. со-»

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

■Кк, (9)

В,у

где Т,,к - период потока данных, входящего в буфер к преобразователя г, Л^ -

размер всплеска потока данных, входящего в буфер к преобразователя /. Аналогично рассчитываются предельные размеры входного буфера промежуточной операции передачи данных В'; с учетом того, что прием и передача данных на промежуточном узле могут накладываться во времени.

На основе фактических сроков выполнения S, рассчитываются показатели эффективности:

Время отклика:

Пропускная способность:

Коэффициент использования оперативной памяти на плате:

У/еГ.аей ггеП (.Г.")01сщ

с„

S,

Rr -- maх^,Т5а

о (е О I.

RTToci3

T6g,N6a3~- N6g,g:rgz Г (п)

Vn

Уп~- IV,+ I в^ I В\,Р(Ь)= {р\(р,Ь)ъ Q)

г(/>Р(й). г(|>Р(А). (12)

9,6 е е е, у ,е т

Схематическое изображение разработанной методики приведено на рис. 3.

Требования

Проектирование

аппаратной платформы

Математическая формулировка задачи

ГГПД

Граф соединений процессоров

I Уточнение \ 1 требований \

Разработка алгоритмов ЦОС

Оценка или измерение вычислительной сложности алгоритмов и

затрат оперативной памяти

|

Распределение и планирование заданий

Генерация . имитационных моделей

Подсистема имитационного моделирования

Инструментальное средство

Генерация шаблонов кода

Параметры ... диспетчеризации заданий

Разработка программного кода

Готовая система I

Рис. 3. Методика организации процесса обработки данных в ММСЦОС

Исследование сходимости алгоритма оптимизации выполнено экспериментально. Для случайно сгенерированных графов заданий и различных топологий многопроцессорных систем определяется зависимость математического ожидания целевой функции (коэффициента использования памяти) М[СР] от числа шагов оптимизации N.ш с учетом доверительного интервала с доверительной вероятностью а=0,95. Оценка глобального минимума осуществляется путем поиска минимального значения СР по всем повторениям в данном эксперименте. На рис. 4 приведены полученные зависимости и доверительные интервалы для различных топологий. Экспериментально установлено, что зависимость достигнутого субоптимального решения от числа шагов алгоритма является убывающей, что позволяет говорить о наблюдаемой тенденции к

нахождению некоторого асимптотического значения при стремлении числа шагов к бесконечности. Тот факт, что это асимптотическое значение совпадает с глобальным минимумом доказан Л. Ингбером в форме статистической гарантии сходимости. Для всех исследованных систем достичь 20% окрестности оценки глобального минимума возможно за 2000-8000 шагов алгоритма.

5-ыерный гиперкуб (32 процессора)

S.65

O.fiG

£ 0.55 £

0.53 Q.*5 5,43

# f ^ / ^ # / / /

Цепная топология (16 проц.)

Кластерная топология (18 г

O.SO -

o.es о,го

0,75 0.70 0.65 0.6Q

# ,f

Рис. 4. Сходимость алгоритма оптимизации для различных топологий систем

Для оценки эффективности методики экспериментально проведено ее сравнение с известным алгоритмом DLS для модели вычислений SDF, реализованным в среде моделирования и программирования встраиваемых систем Ptolemy. Исследовались случайно сгенерированные графы из 20-30 заданий, на полносвязной 8-процессорной системе. По результатам экспериментов исследуемая методика позволила в среднем обеспечить на (13±3)% меньшее время отклика-получения результатов, чем алгоритм DLS. При этом существенным преимуществом предлагаемой методики является возможность оптимизации также пропускной способности или используемости ресурсов.

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

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

ционной системы реального времени для ММСЦОС), а также для имитационного моделирования. Имитационное моделирование позволяет уточнить расчетные характеристики с учетом конфликтов доступа к внешней памяти. В качестве средства моделирования используется пакет ОМЫе1++ - система моделирования с открытыми исходными кодами.

Вероятность отсутствия переполнений буферов

1 100%

□ 30% -100%

пп Менее 80%

+ Реальная система

И2 3.5 0.7 0,3

Загрузка комм, каналов

Рис. 5. Экспериментальная область применимости методики

Корректность и применимость разработанных программных средств были исследованы, как с помощью имитационного моделирования, так и на реальной многопроцессорной вычислительной системе. Адекватность имитационной модели подтверждена сравнением результатов моделирования с результатами, полученными на реальной системе. С помощью имитационного моделирования определена область применимости методики, внутри которой конфликты доступа к общей памяти могут быть адекватно представлены компенсирующими добавками к времени выполнения операций (рис. 5), маркером отмечена реальная исследованная система.

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

Таблица 2 Показатели эффективности ПО при ручном и автоматизированном проектировании____

Показатель Ручной способ Автомат. Отн. выигрыш

Время отклика (сек) 14,5 14,1 3%

Пропускная способность (млн. слов/сек) 2,39 3,13 31%

Коэф. использования опер, памяти 0,15 0,11 27%

В заключении приводятся основные результаты, делается вывод о целесообразности внедрения разработанной методики в процесс проектирования, рассматриваются возможные пути дальнейшего совершенствования и развития результатов работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Научные:

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

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

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

Практические:

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

2. Прототип операционной системы реального времени для процессоров БНАЯС, позволивший подтвердить применимость методики и адекватность имитационной модели на реальной многопроцессорной вычислительной системе.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Стручков И.В. Распределение и планирование вычислений в многоканальной многопроцессорной системе цифровой обработки сигналов // Системное программирование. Вып. 3: Сб. статей / Под ред. А.Н. Терехова, Д.Ю. Булычева. - Спб.: Изд-во С.-Петерб. Ун-та, 2008. - С. 33-53.

2. Стручков И.В. Распределение вычислений с расщеплением задач в многопроцессорной системе обработки сигналов // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов. Россия, СПб., 9-12 апреля 2007 г. / Под ред. А.В. Платонова, Н.В. Смирнова. - СПб.: Изд-во СПбГУ, 2007. - С. 457 - 462.

3. Стручков И.В. Распределение и планирование периодических задач и потоков данных в многопроцессорной вычислительной системе // Системы управления и информационные технологии. - Воронеж, 2006. - Вып. 4.2(26). - С. 271 -276.

4. Struchkov I.V. Real-time periodic multiprocessor scheduling of data-dependent tasks // Информационные технологии моделирования и управления. - 2006. - № 9(34). - С. 1182-1191.

5. Стручков И.В. Двухэтапный метод распределения периодических задач реального времени в многопроцессорной системе // Информационные технологии моделирования и управления. - 2006. - № 6(31). - С. 744-753.

6. Стручков И.В. Формализм для описания программных систем и вычислительных процессов циклической параллельной обработки данных реального времени / Стручков И.В., Ицыксон В.М. // Информационно-управляющие системы. - 2006. -№2.-С. 8-13.

7. Стручков И.В. Многоуровневый подход к разработке программного обеспечения для параллельных вычислений с прогнозируемой производительностью // Молодые ученые - промышленности Северо-Западного региона: Материалы семинаров политехнического симпозиума 2004. - СПб.: Изд-во СПбГПУ, 2004. - С. 22-23.

8. Стручков И.В. Сравнительное исследование способов управления потоком данных в мультипроцессоре с распределенной памятью методом имитационного моделирования / Стручков И.В., Ицыксон В.М., Мелехин В.Ф. // Фундаментальные исследования в технических университетах: Материалы VIII Всероссийской конференции по проблемам науки и высшей школы. - СПб.: СПбГПУ, 2004. - С. 99-100.

9. Стручков И.В. Исследование эффективности коммуникационных систем для многопроцессорного комплекса с распределенной памятью / Стручков И.В., Ицыксон В.М., Мелехин В.Ф. // XXXII Неделя науки СПбГПУ: Материалы межвузовской научно-технической конференции. Ч. V. - СПб.: Изд-во СПбГПУ, 2004. -С. 87-89.

10. Стручков И.В. Исследование параллельного многоканального комплекса обработки гидроакустических сигналов / Стручков И.В., Ицыксон В.М., Мелехин В.Ф. // Труды СПбГПУ. Фундаментальные исследования в технических университетах: Материалы VII Всероссийской конференции по проблемам науки и высшей школы. - СПб.: СПбГПУ, 2003. - С. 163-164.

Лицензия ЛР № 020593 от 07.08 97

Подписано в печать 25.12 2008 Формат 60x84/16. Усл. печ. л 1,0 Уч -изд л. 1,0. Тираж 100. Заказ 0280.

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства Политехнического университета. 195251, Санкт-Петербург, Политехническая ул., 29.

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

ВВЕДЕНИЕ.

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. Экспериментальное исследование применимости методики для более широкого класса графов заданий.

ЗАКЛЮЧЕНИЕ

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

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. Б. С. Аршанский