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

• Автор: Шепеток, Богдан Дмитриевич
• Шифр специальности: 05.13.06
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Киев
• Количество страниц: 209 c. : ил

СОДЕРЖАНИЕ
Введение .
1 Исследование процесса распределения программного обеспечения в многомашинных и мультипроцессорных вычислительных комплексах АСУ

1.1. Организация параллельного вычислительного процесса .

1.2. Определение графовых мделей программного обеспечения о.

1.3. Задачи рациональной организации вычислительного процесса в вычислительных системах АСУ

1.4. Задачи разбиения на билогических двухграфовых моделях программного обеспечения

2. Методы построения расписаний на графах управления

2.1 Определение оптимального расписания для двухцепного гамака

2.2. Определение оптимального расписания для п цепного гамака .

3. Алгоритмы построения распределенного программного обеспечения АСУ .

3.1. Определение временных характеристик программного обеспечения .
3.2. Прямая и обратная задачи распределения программного обеспечения
4. Распределение задач в двухмашинном вычислительном комплексе АСУ на стане Новолипецкого металлургического завода ИЗ
4.1. Применение УВМ для управления процессом прокатки . ИЗ
4.2. Структура автоматизированной системы регулирования толщиной полосы
4.3. Решение задачи распределения программного обеспечения автоматизированной системы регулирования толщиной полосы
4.4. Синхронизация вычислительного процесса в распределенных системах.
Заключение
Литература


В качестве моделей программ для построения расписаний наибольшее распространение получили графы: в простейшем случае -это ациклические графы без условных ветвлений, в более сложных случаях - графы с циклами и (или) с условными ветвлениями. Наиболее известными ранними работами в этой области являются [, Юь] . Основные концепции планирования вычислительных процессов в многопроцессорных системах изложены в [8] . Получение аналитических оценок характеристик расписаний затруднительно. Как правило, данные оценки оказываются слишком осторожными, поэтому большое значение имеют экспериментальные исследования расписаний. Результаты моделирования разнообразных расписаний и анализ их эффективности изложены в [7,,, ,,,3,2,4,3,4,6] . Учитывая тот факт, что простые расписания не являются оптимальными и отличаются от последних по длине (времени испол -нения) незначительно, а также занимают для своего построения незначительное время, для универсальных вычислительных систем можно рекомендовать эвристические, приоритетные [П8,2,4], локально-оптимальные и подобные им расписания, как правило, динамического типа. Для специализированных систем с фиксиро -ванными комплексами программ и систем реального времени могут оказаться целесообразными также и глобальные статические расписания, поскольку их построение осуществляется заранее на этапе проектирования и поэтому не занимает машинное время в про -цессе эксплуатации. Соответствующие вопросы рассмотрены в [, ,] и других работах. В целях упрощения решения задач построения оптимальных расписаний и с учетом их специфики разработан ряд специальных методов оптимизации. На практике оптимальные расписания построены только для простых типов и сравнительно небольших размеров моделей параллельных программ. По мере увеличения сложности и размеров моделей трудности построения оптимальных расписаний резко возрастают. Кроме того, временные характеристики программного обеспечения определяются преимущественно прибли -женно из-за невозможности точного определения данных величин , зависящих от многих факторов: входных данных, структуры построения, языка программирования. Поэтому точные решения задач расписания в этом случае обесцениваются из-за недостоверности ис -ходной информации. Указанные выше обстоятельства стимулировали разработку большого числа достаточно простых методов построения приближенных расписаний, близких к оптимальным, среди которых можно вы -делить локально-оптимальные, обеспечивающие оптимальность на отдельных этапах вычислений и не гарантирующие оптимальности в целом, и эвристические расписания. Граница между двумя последними типами расписаний является достаточно условной, поскольку, например, при определенных условиях эвристические расписания могут оказаться локально-оптимальными и, более того, эвристические и локально-оптимальные расписания могут оказаться оптимальными. В настоящей работе рассмотрены методы построения локальнооптимальных и эвристических расписаний для различных заданных граф-моделей программного обеспечения, описаны условия получения оптимальных расписаний. Пусть программное обеспечение реализуется некоторым набором программ. Для решения задачи оптимального быстродействия исходный граф управления преобразуется в граф ярусно-параллельного вида [ ]. Данную процедуру можно выполнить с помощью определения порядковой функции графа без контуров [бз]* Таким образом, для графа Г(Е, Г) определяем подмножества N0, N4,. М = [ Хсхі ? Е -Мо. ГЛ/г = ф. Иначе говоря, предлагается разбить множество вершин графа без контуров на непересекагощиеся подмножества так, что если вершина принадлежит подмножеству с номером К , то следующая за ней вершина входит в подмножество с номером, большим К . При "ИЛИ" - выходной логике после завершения операции вершины Хс возможно включение любой последующей вершины* При "И" - выходной логике все последующие вершины должны обязательно включаться. М.*)', *к€Г *? Ъу * 6 М°) . Расчет "Ьц должен производиться последовательно по уровням, от первого к последнему. Гх? Ли Г'4хгиг'жх? Щ = 0 (Ух? Сх«в] и №.