Содержание к диссертации
Введение
1. Анализ методов моделирования и оптимизации многопроцессорных систем 10
1.1. Классификация многопроцессорных вычислительных систем 10
1.2. Методы, используемые при планировании программного обеспечения многопроцессорных систем 19
1.3. Анализ и синтез параллельного программного обеспечения. Преимущества графового метода и метода «ветвей и границ» 36
1.4. Выводы 39
2. Модель параллельного вычислительного процесса 40
2.1. Представление вычислительного алгоритма в виде решетчатого орграфа 40
2.2. Модель параллельного вычислительного процесса 51
2.3. Определение временных характеристик исследуемого алгоритма 64
2.4. Формализация оптимизационных критериев 69
2.5. Выводы 73
3. Методика оптимального распараллеливания алгоритма функционирования вычислительной системы 74
3.1. Сегментация алгоритма 74
3.2. Распараллеливание алгоритма на основе системы ордеров 82
3.3. Распараллеливание линейных алгоритмов на основе целочисленного линейного программирования 89
3.4. Получение исходных данных о структуре и основных параметрах алгоритма 97
3.5. Исследование точности получаемых результатов 108
3.6. Выводы ПО
4. Экспериментальные исследования методик анализа и синтеза программного обеспечения многопроцессорной системы 112
4.1. Программный комплекс для автоматического распараллеливания алгоритмов 112
4.2. Пример синтеза программного обеспечения спецвычислителя .118
4.3. Исследование точности полученных результатов и проведение практического эксперимента 127
4.4. Исследование времени поиска оптимального решения 132
4.5. Исследование эффективности распараллеливания при использовании разработанного подхода 137
Заключение 144
Литература
- Методы, используемые при планировании программного обеспечения многопроцессорных систем
- Модель параллельного вычислительного процесса
- Распараллеливание алгоритма на основе системы ордеров
- Пример синтеза программного обеспечения спецвычислителя
Введение к работе
Актуальность темы. На современном этапе развития электронно-вычислительной техники системы, предназначенные для цифровой обработки данных, характеризуются значительным увеличением объемов обрабатываемой информации. Это связано с расширением области применения данных систем, а также с постоянным совершенствованием алгоритмов обработки, их усложнением, появлением новых технических задач.
Увеличение сложности вычислительных алгоритмов обусловлено постоянным стремлением разработчиков к усовершенствованию проектируемых систем, повышению эффективности их функционирования, качества и точности обработки [90], что имеет большое значение в различных областях цифровой обработки сигналов: обработке изображений [71], звукозаписывающих и звуковоспроизводящих устройствах, цифровом телевидении, интеллектуальных робототехнических системах, в системах распознавания и обнаружения.
В настоящее время наблюдается расширение и совершенствование элементной базы, что выражается в появлении многоядерных универсальных микропроцессоров и специализированных сигнальных процессоров, обладающих повышенной вычислительной мощностью, а также широкими возможностями для их использования в качестве параллельных вычислительных структур. Применение параллельной обработки существенно увеличивает производительность вычислительной системы, что, в свою очередь, позволяет использовать более сложные алгоритмы обработки информации и большие объемы входных данных, а также повышать точность вычислений [73, 78].
Избранный в соответствии с указанными обстоятельствами объект диссертационного исследования может быть охарактеризован как много-
ядерная или многопроцессорная вычислительная система, предназначенная для цифровой обработки сигналов.
Эффективность параллельной обработки существенно зависит от правильности распараллеливания операций между исполнительными устройствами [7,10, 11, 41]. Основное противоречие, которое должно быть преодолено в процессе решения задачи распараллеливания, заключается в том, что, с одной стороны, к разрабатываемой вычислительной системе предъявляются требования повышенного быстродействия, с другой - ставятся жесткие ограничения на объем используемых аппаратных ресурсов. Разрешение данного противоречия представляет собой сложную оптимизационную задачу большой размерности [7,10, 31].
В настоящее время увеличивается доля выпуска многоядерных микропроцессоров с упрощенной системой управления, для которых необходимо производить распараллеливание алгоритма в статическом режиме на этапе построения программы. Если учесть, что данный тип микропроцессоров используется при проектировании систем цифровой обработки сигналов с жесткими алгоритмами функционирования, то можно сделать вывод об актуальности задачи распараллеливания алгоритмов функционирования вычислительных систем на этапе их разработки. Однако, методологическое обеспечение программирования мультипроцессорных систем на их основе практически отсутствует. Существующие методы построения параллельных программ, ориентированных на различные алгоритмические конструкции, налагают существенные ограничения на логическую и информационную структуру алгоритма, не учитывают всех параметров алгоритма и зачастую являются эвристическими, не дающими оптимального решения задачи распараллеливания.
Указанное обстоятельство обусловило выбор предмета исследования, который может быть охарактеризован как автоматическое формирование па-
раллельного программного обеспечения для многопроцессорных систем исследуемых классов.
Цель и задачи диссертации. Цель диссертационной работы состоит в повышении быстродействия вычислительных систем путем эффективного распараллеливания алгоритмов их функционирования.
В соответствии с указанной целью были поставлены и решены следующие задачи:
Формализация модели параллельных вычислений.
Разработка системы сегментации множества операторов алгоритма с целью сокращения размерности задачи распараллеливания.
Выбор и формализация методов оптимизации, обеспечивающих наиболее эффективное решение задачи распараллеливания.
Разработка методики получения исходных данных о временных характеристиках вычислительных операций, входящих в исследуемый алгоритм.
Разработка методики исследования информационных зависимостей между отдельными вычислительными операциями распараллеливаемого алгоритма.
Методы исследования. В качестве основного инструмента теоретического исследования использовались методы теории алгоритмов, теории множеств и графов, теории вероятностей и математической статистики, методы дискретной оптимизации.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:
Разработана методика распараллеливания алгоритмов на основе системы ордеров, отличающаяся формой представления различных вариантов распараллеливания алгоритма в виде набора целых чисел.
Разработана модель многопроцессорной системы на основе случайного решетчатого графа, дающая возможность вычислять временные харак-
теристики системы, функционирующей по разветвляющимся и циклическим алгоритмам со случайным временем выполнения операторов, для их использования в качестве оптимизационного критерия.
Предложена методика группировки операторов алгоритма, позволяющая уменьшить сложность задачи распараллеливания и реализации системы.
Разработана методика получения исходной информации о временных характеристиках операций, входящих в алгоритм, с помощью экспериментального стенда и активного измерительного монитора.
Достоверность полученных результатов подтверждена экспериментальными исследованиями с применением разработанного программного инструментального средства.
Практическая ценность работы заключается в применении теоретических положений и выводов диссертации для решения практических задач распараллеливания алгоритмов функционирования систем цифровой обработки данных, в частности:
Разработано программное обеспечение, позволяющее производить распараллеливание алгоритмов функционирования вычислительной системы на основе полученных исходных данных.
Создана библиотека классов, применяемых для анализа информационных зависимостей в программах на языке Си++, позволяющих проводить анализ используя стандартные компиляторы языка Си++.
2. Разработаны экспериментальный стенд и измерительный монитор, дающие возможность анализировать временные характеристики реализаций операторов алгоритма на микропроцессорах любых типов.
Реализация и внедрение результатов работы. Прикладные результаты диссертационной работы были внедрены: 1) ООО «Научно-производственная фирма ОВЕН-К», г. Москва. 2) компания «Трейд-М», г. Тула.
Теоретические результаты работы были внедрены в учебном курсе «Проектирование процессоров для цифровой обработки сигналов» на кафедре ЭВМ Тульского государственного университета, а также в дипломном проектировании бакалавров и инженеров по специальности «Вычислительные машины, комплексы, системы и сети».
Апробация работы. Основные положения диссертационной работы легли в основу докладов на следующих конференциях: 1. Международная молодежная научная конференция «Гагаринские чтения» (Москва, МАТИ, 2002, 2003, 2004, 2005, 2006 гг.) 2. Межрегиональная научно-техническая конференция «Интеллектуальные и информационные системы» (Тула, Тул-ГУ, 2003, 2004, 2005). 3. 7-я всероссийская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и в образовании» (Рязань, РГРТА, 2002). 4. 1 -я Всероссийская научно-техническая конференция студентов и аспирантов «Идеи молодых - новой России» (Тула, ТулГУ, 2004). 5. IV Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии» (Томск, ТПУ, 2006). 6. Международная научно-методическая конференция «Информатизация образования - 2006» (Тула, 2006). 7. Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации» (Новосибирск, НГТУ, 2006). 8. IV Международная научно-техническая конференция «Искусственный интеллект в XXI веке. Решения в условиях неопределенности» (Пенза, 2006). 9. I молодежная научно-практическая конференция Тульского государственного университета «Молодежные инновации» (Тула, ТулГУ, 2006).
Публикации. По результатам исследований опубликовано 20 печатных работ.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 142 страницах маши-
нописного текста, содержит 54 рисунка, 10 таблиц, список использованной литературы из 96 наименований и приложения.
В первом разделе рассматривается классификация многопроцессорных вычислительных систем, методы, применяемые для анализа многопроцессорных систем, методы дискретной оптимизации; обоснованы постановленные цель и задачи исследования.
Во втором разделе описывается графовый метод анализа многопроцессорных систем со стохастическими временными характеристиками, позволяющий учитывать межпроцессорный обмен, сформулированы оптимизационные критерии.
В третьем разделе описаны алгоритм поиска оптимального варианта распараллеливания на основе метода «ветвей и границ» и методика получения исходных данных о временных характеристиках блоков распараллеливаемого алгоритма.
В четвертом разделе проведены экспериментальные исследования, подтверждающие адекватность построенной модели и преимущества разработанного метода перед существующими методами по эффективности распараллеливания.
В заключении приведены основные выводы по работе.
В приложении 1 приведен пример решения задачи оптимального распараллеливания алгоритма методом линейного программирования.
В приложении 2 приведены экспериментальные исследования модели общей шины с помощью имитационного моделирования.
В приложении 3 приводятся акты о внедрении теоретических и прикладных результатов диссертации.
Методы, используемые при планировании программного обеспечения многопроцессорных систем
Задача планирования программного обеспечения многопроцессорной системы [3, 14, 62] представляет собой совокупность двух составляющих. Во-первых, необходимо построить модель объекта исследования с целью определения характеристик разрабатываемой системы [69], для чего следует применить соответствующие методы анализа многопроцессорных вычислительных систем. Во-вторых, данная модель должна быть подвергнута процедуре оптимизации [1, 31, 42], для чего она должна иметь возможности для построения различных вариантов проектируемого программного обеспечения.
Если определена структура системы и ее математическая модель, то можно определить параметры данной системы, которые имеют численное выражение. Задача в такой постановке сводится к поиску решений для удовлетворения требований к системе: х = argmin f(x), либо JC = argmax f(x). хєХ хеХ
Здесь множество X подразумевает множество всех возможных вариантов решения задачи. Целевая функция Дх) может быть линейной либо нелинейной, что определяется условиями задачи. Поиск решения производится с учетом системы ограничений: ymin упол ушах ymin упол ушах ymin - упол ушах .и — я — я Задача планирования параллельных вычислительных процессов сводится к решению двух вопросов: 1. Назначение каждой операции одному из имеющихся исполнительных устройств. 2. Определение очередности выполнения операций, назначенных одному исполнительному устройству, последовательность выполнения которых не является жестко заданной.
Задача в такой постановке сводится к методам дискретной оптимизации.
Методы анализа временных характеристик многопроцессорных систем. Временные характеристики многопроцессорной системы могут являться как детерминированными, так и случайными величинами. Алгоритмы функционирования вычислительной системы [43] можно классифицировать по типу характеризующих величин: Класс 1. С детерминированными временными характеристиками отдельных блоков. Класс 2. Со случайными временными характеристиками отдельных блоков (при условии взаимной независимости случайных величин). Класс 3. Со случайными временными характеристиками отдельных блоков (без наложения условий взаимной независимости случайных величин). Модели, используемые при анализе многопроцессорных систем представлены на рис. 1.7. Модели и методы анализа многопроцессорных систем
Для анализа параллельных вычислительных систем может быть использована модель системы массового обслуживания (СМО) [32, 33, 66]. В работе [35] рассматривается модель вычислительного ядра микропроцессорной системы, в соответствии с которой вычислительное ядро состоит из ограниченного величиной N числа процессоров. На вход ядра от активного источника информации по общему каналу связи поступает множество сигналов - заявок на обработку поступающей информации.
Принимается, что информация подается в виде множества независимых потоков заявок, как правило, регулярных, либо простейших с интенсивностью их поступления 1{.
Обслуживание заявки продолжается в течение случайного времени, распределенного по показательному закону с параметром //: p(t) = jue , t 0. Интенсивность обслуживания ц характеризует среднее число обслуженных заявок в единицу времени в стационарном режиме работы вычислительного ядра и определяется равенством /л = Е\ Тобр " . Рассматриваемая СМО имеет следующие состояния: So - канал свободен; S\ - канал занят, очереди нет; & - канал занят, одна заявка стоит в очереди;.. . Sz+i - канал занят, Z заявок стоит в очереди.
Граф состояний описываемой СМО показан на рис. 1.8. Для анализа данной СМО пользуются общим решением схемы гибели и размножения.
По данной схеме можно вычислить время пребывания заявки в системе, что характеризует производительность исследуемого устройства.
Метод анализа временных характеристик многопроцессорных систем на основе сетей массового обслуживания приведен также в [40].
Существенным недостатком данного метода является то, что заявка представляет собой операцию, не подвергающуюся распараллеливанию. При этом заявки поступают разрозненно, независимо друг от друга. Современные сложные алгоритмы состоят из большого количества подзадач, неким обра зом зависящих друг от друга, причем время их выполнения которых не всегда распределено по экспоненциальному закону, поэтому данный метод имеет существенные ограничения по области применения.
Данный метод может быть применен, если в качестве обслуживающего канала рассматривается не процессор, а модуль памяти или канал ввода-вывода. Тогда метод можно применить для анализа конфликтных ситуаций при обращении к памяти и определения времени простоя процессоров в случае подобных конфликтов.
Кроме того, для определения характеристик систем, рассматриваемых как системы массового обслуживания, может быть применено имитационное моделирование [66, 75, 85]. Для имитационного моделирования реализующий модель алгоритм воспроизводит процесс работы системы во времени, причем с помощью датчиков случайных чисел [58] имитируются элементарные явления, составляющие процесс, с сохранением их логической структуры и последовательности протекания во времени, что позволяет по исходным данным получить сведения о состояниях процесса в определенные моменты времени, дающие возможность оценить характеристики системы.
Имитационная модель может быть реализована на ЭВМ программно с помощью одного из универсальных языков программирования высокого уровня (Си, Паскаль, Бейсик и т.п.), однако для анализа систем массового обслуживания более удобным является язык GPSS [87].
Достоинством данного метода является то, что он позволяет моделировать системы с любыми характеристиками (то есть интервал между заявками и время обслуживания может быть распределено по любому закону). Кроме того, с помощью этого метода можно моделировать более сложные системы, чем те, которые доступны аналитическим методам. Недостатком метода имитационного моделирования является зависимость точности результата от времени моделирования, то есть для получения высокой точности необходимо длительное время.
Модель параллельного вычислительного процесса
Если вычислительная система реализуется на нескольких исполнительных устройствах, то каждая вычислительная операция алгоритма может выполняться на одном из этих устройств. В общем случае распараллеливание предполагает назначение вычислительных операций алгоритма одному из нескольких исполнительных устройств.
Пусть С={с\, Сі,... Сдс} - множество исполнительных устройств (процессоров), включенных в состав вычислительной системы, bf" - общее число исполнительных устройств.
Тогда назначение операции и, исполнительному устройству Си может быть обозначено следующим образом: ck=C(vt). (2.2)
Операция может быть назначена только одному исполнительному устройству, то есть функциональная зависимость (2.2) является однозначной. Операции у,- и Vj называются однородными, если они принадлежат множеству вычислительных операций одного блока, т. е. 3k\D,eVkbAVjeVkb, из чего следует, что
Определение 2.4. Циклическим сегментом алгоритма называется множество S однородных вычислительных операций, которые могут алгоритмически быть представленными в виде цикла с параметрами. Операторы, входящие в один сегмент должны выполняться на одном вычислителе последовательно друг за другом. Для каждого сегмента S задается последовательность Jf векторов индексов операций, входящих в состав сегмента S.
Предложено несколько возможных форм задания последовательностей Jf, отличающихся реализацией и областью применения: 1. Алгоритмическая форма, в соответствии с которой сегмент S пред ставляет собой вложенный цикл, каждое 1-е вложение которого характеризу ется следующими функциями: / (Js) - нижняя граница изменения пере менной цикла jf; /, (Js) - верхняя граница изменения переменной цикла jf fiS(JS) модификатор переменной цикла jf. В данном случае последовательность Jf формируется в процессе выполнения цикла. 2. Аналитическая форма, в соответствии с которой последовательность выполнения вычислительных операций определяется рекуррентной функци ей 3S,=VS(JL), (2-3) а также вектором индексов Jf начальной операции и числом операций в сегменте. Данная форма записи применима при реализации вычислительной системы на основе жесткой логики. 3. Эмпирическая форма, при которой последовательность Jf задается в явном виде. Данная форма применима для систем, не имеющих ограничений на память программ.
Все операции из одного сегмента должны быть реализованы на одном исполнительном устройстве, т. е. С(ц.) = С( ),еслицє5,і;;.є5.
Сегментацией алгоритма называется разделение множества V операций алгоритма на конечное число подмножеств Sl,S1,...,SN , где Ns - число сегментов. На данное множество сегментов накладываются следующие условии: 1. Циклические сегменты Sl,S2,,..,S/l! составляют полное множество операций алгоритма, т. е. 1=1 2. Циклические сегменты SuS2,...fSN не пересекаются, т. е. 1=1 В противном случае некоторые вычислительные операции, будут выполняться более одного раза. Пример сегментации цикла, изображенного на рис. 2.5. показан на рис. 2.9.
Распараллеливание алгоритма на основе системы ордеров
В процессе распараллеливания некоторые аппаратные дуги будут удалены из графа Г, остальные дуги либо останутся неизменными, либо поменяют направление на обратное. Граф Г отражает структуру вычислительного процесса следующим образом: если аппаратная дуга / = (и,-, vj) присутствует в графе, то операторы и,- и Vj будут выполнены на одном вычислителе в порядке, указываемом направлением дуги; если дуга Гк удалена из графа, то операторы о, и Vj будут выполнены на разных вычислителях.
2. Различные варианты распараллеливания удобнее задавать в числовом виде. Поэтому каждой аппаратной дуге / = (У,, vj) ставится в соответствие ордер h, который может принимать одно из трех значений {1; 0; -1}. Ка ждому ордеру задается начальное значение, равное 1. Значения ордера 4 имеют следующий смысл: h = 1, если гк имеет прямое направление, -1, если гк имеет обратное направление, О, если гк отсутствует. 3. Вводится переменная, обозначающая номер аппаратной дуги и соответствующего ей ордера, рассматриваемых на текущем шаге алгоритма. Изначально принимается / = 0. Кроме того, задается начальное значение критерия оптимизации Гтіп = оо. 4. Необходимо принять / = /+1, перейдя таким образом к рассмотрению следующего ордера и аппаратной дуги. 5. Ордеры 1\... 1[. могут противоречить друг другу в случаях, когда одна часть ордеров предписывает выполнять два оператора алгоритма на одном вычислителе, а другая часть ордеров предписывает выполнять эти два оператора на разных вычислителях, либо, когда ордеры предписывают порядок выполнения операторов, приводящий к зацикливанию алгоритма. В обоих случаях для предупреждения подобных противоречий необходимо наложить следующие ограничения на структуру графа Г: если из вершины и, в вершину Vj существует цепь, состоящая из аппаратных дуг, то должна существовать аппаратная дуга, идущая из и,- в o;- или из и,- в и,-, причем если данная цепь является путем, то дуга может быть направлена только из У, В VJ В случае несоответствия графа.указанным условиям перейти на п. 9. 6. Определить, на скольких вычислителях может быть реализована вычислительная схема, задаваемая ордерами І\... її. Для этого следует заменить матрицу смежности графа Г на матрицу достижимости и определить для данного графа число независимости а [3]. Если a N, то п. 9. 7. Если / L, то необходимо вычислить прогрессивную (заведомо меньшую) оценку времени выполнения алгоритма 7\ вычислив критический путь графа Г через вершины, временно удалив из него дуги п+\--- Гь- Если T Tmin, то перейти к п. 10, иначе к п. 4. Вычисление прогрессивной оценки позволяет исключить перебор возможных значений ордеров с номерами, большими чем /. 8. Если / = L, то определить время выполнения Тщ алгоритма в соответствии с выбранным критерием. Если Ткр Тща, то запомнить значения /] = 1\, ... її = 4 и граф Г = Г. 9. Перейти к новому значению текущего ордера по следующему правилу: если 1/ = 1, то изменить направление дуги г і, принять 1/ = -1 и перейти на п. 4., если 1/ = -1, то удалить дугу г/, принять I/ = 0 и перейти на п. 4., если I/ = 0, то вернуть в граф дугу Г/, принять 1/=1,/ = /-1. 10. Если/ . 0, перейти к п. 9. 11. Построить неориентированный граф U, в котором ребра строятся по следующему правилу: если / = (vh vj) и Ik = 0, то вершины и,-, Vj соединяются ребром. 12. Для полученного графа t/решается задача о раскраске неориентированного графа [3], при которой вершины, соединяемые ребром, раскрашиваются в различные цвета. В результате номер цвета, в который раскрашена вершина, соответствует номеру вычислителя, на котором следует выполнить оператор алгоритма, соответствующий данной вершине.
Вершины, раскрашенные в один цвет, сортируются по следующему правилу: если в графе Г существует путь из и,- В и;, то в отсортированном ряде вершина Vj должна предшествовать вершине Vj. Таким образом осуществляется определение последовательности выполнения операций на каждом из вычислителей.
Важным достоинством предложенной методики является ее четкая формализация, что позволяет реализовать ее в виде компьютерной программы.
Пример синтеза программного обеспечения спецвычислителя
Определение второй составляющей погрешности Аг можно произвести следующим образом.
Пусть время выполнения оператора задается как 7) ± А,.. Разумеется, что при различных значениях 7] оцениваемый параметр taver будет принимать различные значения tawr(Jt). Тогда погрешность Аг вычисляется как А2 = тах{/_(7;)aver(Tt - А ауег(1] + А,)aver{Tt)}. Тогда значение погрешности может быть вычислено как А = А,+А2. (3.7)
Если полученное значение превышает предельно допустимую погрешность, то необходимо продолжить сбора исходных данных с помощью измерительного монитора, увеличивая тем самым объем выборки исходных данных, что приводит к уменьшению погрешности оценки исследуемого параметра.
1. Разработана методика группировки операторов алгоритма, позволяющий уменьшить сложность задачи распараллеливания и реализации системы.
2. Задача построения оптимального программного обеспечения сведена к нахождению множества дуг ориентированного графа, описывающего процесс функционирования многопроцессорной системы, что позволяет распределять операции между процессорами и находить последовательность их выполнения в рамках одной оптимизационной задачи.
3. Осуществлено представление вариантов решения задачи в виде системы ордеров, отвечающих за положение аппаратных дуг. Осуществлено решение задачи методом «ветвей и границ», для чего найдена формула прогрессивной оценки оптимизационного критерия, а также методом целочисленного линейного программирования.
4. Разработана методика получения исходной информации о временных характеристиках операций, входящих в алгоритм, с помощью экспериментального стенда и активного измерительного монитора, предназначенная для испытания алгоритма на реальных входных данных и дальнейшего использования полученной информации в задаче синтеза оптимального параллельного программного обеспечения.
5. Разработана методика автоматического анализа информационной структуры алгоритма на основе технологии объектно-ориентированного программирования, позволяющая использовать для анализа традиционные компиляторы объектно-ориентированных языков.
Как указывалось ранее, задача распараллеливания имеет высокую вычислительную сложность. В связи с этим предложенные в работе методики реализованы в виде программного комплекса. Программный комплекс состоит из трех модулей: модуль визуального редактирования информационного графа, модуль синтеза параллельной программы, модуль измерительного монитора, а также содержит библиотеку анализа информационной структуры алгоритмов, записанных на языке программирования Си.
Разработанный программный комплекс позволяет: - задавать информационную структуру исследуемого алгоритма путем задания информационного графа в ручном и автоматическом режиме (с использованием данных, полученных с помощью модуля анализа информационных зависимостей); - осуществлять определение временных параметров алгоритма на экспериментальном стенде; - осуществлять построение программного обеспечения многопроцессорной системы с учетом заданных требований и ограничений.
Модуль визуального синтеза структуры алгоритма (рис. 4.1) позво ляет производить построение в визуальном режиме информационной структуры алгоритма в виде ориентированного графа, вершинами которого являются операторы (команды, подпрограммы), дуги - информационные связи между операторами (информационные дуги).
Этот модуль позволяет наглядно добавлять, удалять, редактировать вершины и ребра графа, то есть производить визуальный синтез ориентированных графов. Имеется возможность задавать названия вершин, веса вершин и их шестнадцатеричные идентификаторы.
Модуль синтеза параллельной программы (рис. 4.2) позволяет распараллеливать заданный алгоритм для многопроцессорной системы. Имеется возможность задавать максимальное число процессоров, параметры информационного обмена.
Модуль осуществляет построение программного обеспечения для системы, реализующей данный алгоритм. Результат выдается по каждому процессору в виде последовательности операций (вершин заданного графа).
Исходными данными к построению программы могут служить веса вершин заданного графа, представляющие собой времена выполнения соответствующих операций, либо файл, имеющий специальный формат и содержащий данные о времени выполнения операций, полученные измерительным монитором, либо симулятором исследуемого микропроцессора.
Кроме того имеется возможность редактировать полученную программу вычислений и определять временные характеристики системы, работающие по этой программе.
