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

• Автор: Чайников, Сергей Иванович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Харьков
• Количество страниц: 218 c. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

1. АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ И ПОСТАНОВКА ЗАДАЧИ

1.1. Методы оценки параметров последовательных вычислительных процессов в проблеме создания сложных систем.
1.2. Ретроспективный обзор методов моделирования и оценивания параметров последовательных вычислительных процессов

1.3. Постановка задачи и цели исследования .

2. СИНТЕЗ АЛГОРИТМОВ ТОПОЛОГИЧЕСКОГО АНАЛИЗА ГРАФМОДЕЛЕЙ ВП .

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

2.2. Алгоритм обнаружения топологических некорректностей .

2.3. Алгоритм топологической декомпозиции графмоделей большой размерности .

2.4. Алгоритм топологического анализа циклических графмоделей .

2.5. Выводы.
3. РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ОЦЕНКИ ПАРАМЕТРОВ НА ДЕТЕРМИНИРОВАННЫХ ГРАФМОДЕЛЯХ ВП.
3.1. Методика расчета экстремальных значений параметров на детерминированных графмоделях, содержащих циклические подграфы
3.2. Алгоритм приведения детерминированных графмоделей
к ациклическому зиду.
3.3. Критерий и алгоритм проверки целесообразности вероятностного моделирования ВП
3.4. Анализ чувствительности вероятностных графмоделей
ВП к вариациям вероятностей передач управления .
3.5. Выводы
. СИНТЕЗ МЕТОДОВ И АЛГОРИТМОВ ОЦЕНКИ ВЕРОЯТНОСТНЫХ ХАРАКТЕРИСТИК ПАРАМЕТРОВ ВП.
4.1. Вероятностные графмодели элементарного вычислительного процесса и вычислительного процесса в укрупненных состояниях .
4.2. Методы оценки вероятностных характеристик параметров вычислительных процессов
4.3. Метод укрупнения состоянии и алгоритм синтеза вероятностной графмодели вычислительного процесса
в укрупненных состояниях .
4.4. Алгоритм оценки стационарных вероятностей состояний ВП .
4.5. Выводы
5. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА МЕТОДОВ И АЛГОРИТМОВ АПРИОРНОЙ ОЦЕНКИ ПАРАМЕТРОВ ПОСЛЕДОВАТЕЛЬНЫХ ВП
5.1. Топологический анализ и оценка экстремальных значений времени реализации реального ВП . . . .
5.2. Анализ чувствительности и оценка вероятностных характеристик времени реализации реального ВП . .
5.3. Экспериментальная проверка работоспособности алгоритма топологической декомпозиции графмоделей большой размерности .
5.4. Программная реализация методов и алгоритмов априорной оценки параметров последовательных ВП .
5.5. Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Рост сложности объектов управления и повышение требований к эффективности их функционирования привели к необходимости использования вычислительной техники в управляющих подсистемах. ВС, распределенные микропроцессорные ВС и т. В настоящее время наблюдается тенденция резкого роста стоимости разработки и внедрения программного обеспечения вычислительных систем. Например, если в г. ВС в США было затрачено около млрд. Затраты же на аппаратуру при этом за тот же период возрастут с 5 млрд. Эта тенденция привела к возникновению ряда технологий программирования и связанных с ними направлений и подходов к созданию систем автоматизации программирования и отладки сложных комплексов программ . Технология программирования независимо от ее типа содержит три этапа проектирование алгоритма, кодирование алгоритма составление программы и отладка программы. Распределение затрат по этапам соответственно , 2С, от общей суммы затрат на получение готового программного продукта . Общая же сумма затрат на программирование во многом определяется количеством алгоритмических ошибок в программах. Алгоритмические ошибки характеризуются особой сложностью их обнаружения методами формального автоматического контроля. В работе отмечается, что трудности обнаружения ошибок этого типа определяются, в основном, некорректностью постановок задач управления, вызываемой отсутствием для большинства алгоритмов строго формализованных постановок, и значительной степенью неопределенности при проектировании алгоритмов. Значительную часть алгоритмических ошибок составляют просчеты в оценках использования алгоритмами ресурсов ВС. Основной причиной появления просчетов в оценках использования алгоритмами ресурсов ВС является субъективность таких оценок, обусловленная оцениванием по отдельным реализациям программ. Субъективность оценивания усугубляется еще и тем, что разработка алгоритмов и программ, реализующих эти алгоритмы зачастую ведется в различных организациях или в одной организации различными специалистами. Кроме того, отладка программ, реализующих алгоритмы управляющей подсистемы, в большинстве случаев производится на ВС, характеристики аппаратных средств и структура которой не совпадают с характеристиками аппаратных средств и структурой гипотетической ВС проектируемой сложной системы управления. К настоящему времени известен ряд методов оценивания ресурсов ВС, необходимых для реализации вычислительных процессов, порождаемых алгоритмами 6,8,9,,,,,,,,,,,,. Основу этих методов составляет вероятностное моделирование алгоритмов с учетом характеристик аппаратных средств и структуры гипотетической ВС. Вероятностный характер моделей алгоритмов объясняется тем, что программы, являющиеся закодированной формой представления алгоритма и порождающие вычислительный процесс в ВС, обычно содержат команды передачи управления по условию. Наличие таких команд в программе создает неопределенность в выборе направления развития вычислительного процесса, а так как ресурсы время, память, каналы,передачи данных и др. ВС являются случайными величинами. Класс вероятностной модели алгоритма определяется местом моделируемого вычислительного процесса в иерархической классиф1кашя вычислительных процессов и целями моделирования . Вычислительные процессы верхних уровней состоят из вычислительных процессов нижних уровней, т. ВС. Обобщенная схема взаимодействия программных средств ВС, являющейся подсистемой сложной системы управления , в которой показано взаимодействие алгоритмов, относящихся к уровням, приведена на рис. ПВ программа взаимодействия комплексированных ЭВМ и процессоров 3 программы решения функциональных задач ВС в системах управ
ления. В табл. Цели моделирования всегда определяются практическими задачами, возникающими в процессе проектирования сложной системы управления и, в частности, программных средств ВС. ВС, в реальном масштабе времени. Для решения этих задач всегда требуются хотя бы приближенные оценки параметров вычислительных процессов. Обобщенная x. Рис. Анализ многодоступных 2, 3, 4, , однопроцессорных ВС. Ап , риорное оценивание вероятностных характеристик времени выполнения микропрограмм. Оптимизация алгоритмов.