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

• Автор: Труб, Илья Иосифович
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1994
• Место защиты: Донецк
• Количество страниц: 203 с.

СОДЕРЖАНИЕ
Введение

ГЛАВА 1. Методы оценки быстродействия диалоговых вычислительных систем с циклической

дисциплиной обслуживание

1.1 Распределение времени ожидания в открытой

вычислительной системе.

1.1.1. Аналитические результаты.

1.1.2. Результаты численных экспериментов.

1.2. Анализ неоднородной вычислительной системы

коллективного пользования.

ГЛАВА 2. Аналитические модели функционирования

оперативной памяти модульной структуры
2.1. Обзор основных методов исследования
2.2. Модель функционирования модульной
с равновероятными обращениями к каждому модулю
2.2.1. Постановка задачи.
2.2.2. Определение множеств состояния и событий.
2.2.3. Построение системы уравнений.
2.2.4. Сведение к системе линейных уравнений
2.2.5. Анализ основных характеристик системы
2.3. Исследование функционирования модульной
памяти с неравновсроятными обращениями.
2.3.1. Постановка задачи.
2.3.2. Анализ особенностей системы. Определение
множества состояний.
2.3.3. Построение системы уравнений для
вероятностей состояний
2.3.4. Вывод уравнения для г.
2.3.5. Критерий эффективности.
ГЛАВА 3. Анализ производительности ЭВМ.
управляемой потоком операндов
3.1. Введение и обзор литературы
3.2. Анализ стационарного режима в вычислительной
системе, управляемой потоком операндов
3.2.1. Постановка задачи.
3.2.2. Математическая модель для случая Хр
3.2.3. Случай различного быстродействия.
процессоров
3.2.4. Учет быстродействия блоков памяти
3.2.5. Анализ средних.
3.2.6. Численные эксперименты
3.3.Анализ нестационарного режима в вычислительной
системе, управляемой потоком операндов.
3.3.1. Постановка задачи.
3.3.2. Математическая модель.
3.3.3. Численные эксперименты
ГЛАВА 4. Вычислительная система, управляемая потоком .
запросов редукция к задаче на графе, алгоритмы анализа и оптимизации
4.1. Введение и обзор литературы
4.2. Математическая модель. Основные определения
4.3. Режимы обслуживания запросов
4.4. Расчет времени работы для режима 1
Дисциплина РСРБ
4.5. Расписания на графах потоков данных.
4.6. Стратегия оптимизации
4.7. Моделирование обслуживания запросов в режиме 2 .
4.8. Дальнейшие направления изучения графов.
потоков данных
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


Может оказаться желательно решать задачу в такой первоначальной постановке: вероятность ухода пользователя из системы после первого сеанса обдумывания (точнее, после первоначального обустройства на рабочем месте) равна нулю, после любого другого сеанса - й. Однако, специальное выделение первого сеанса обдумывания усложняет анализ. Следует задаться новым значением 1Ы, которое распространялось бы на все сеансы обдумывания, в том числе и на первый. Выбрать наиболее естественно из условия сохранения р. Ьх= ^г- . Распределение для Ук ищется в терминах преобразования Лапласа-Стил-тьеса. Для использования этого метода введем в рассматриваемой нами задаче одно дополнительное ограничение, выполнимость которого достаточно очевидна. Пусть в момент начала кванта обслуживания на процессоре некоторого требования какой-либо терминал пуст. Ограничение заключается в следупцем: если новый пользователь в течение этого кванта займет терминал, то до окончания кванта он не посылает своей задачи на обслуживание. Иными словами, во время кванта послать свои задачи в пультовую фазу могут лишь те пользователи, которые уже обдумывали их к началу кванта. Так как время кванта обслуживания, по-видимому, намного меньше среднего времени обдумывания, то такое ограничение можно принять без сколько-нибудь серьезного нарушения общности. Основная идея анализа такова. Случайная величина Ук складывается из квантов обслуживания тех требований, которые хотя бы раз оказывались впереди помеченного к-требования. Пусть в момент поступления в очередь к-требования в системной фазе находятся Ь требований. С каждым из них связываются ветвящиеся процессы порождения потомков. Каждое из этих I требований считаем предком; требования, приходящие в системную фазу за время очередного кванта обслуживания предка, считаем его потомками первого поколения, требования, поступающие за кванты обслу-жвания этих потомков - потомками второго поколения. Величина Ук представляется в виде суммы элементов задержки помеченного требования от различных этапов обслуживания требований и их потомков. Фкт - элемент суммарной задержки помеченного требования из-за го-го по счету предка (го= Т) и всех его потомков. Это суммарный интервал занятости прибора, составленный из отдельных квантов обслуживания соответствующего предка и его потомков. Аналогичную величину вклада в от собственно помеченного требования и его потомков обозначим Бк. Фкш независимы и при т одинаково распределены. Фк> <^(3) - ПЛС от 0к. Эта теорема остается справедливой и для рассматриваемой сети, но формулы ДЛЯ фк(3), Ф*(Э> И бк(8> будут уже иные. Мы ограничимся здесь выводом формулы для фк (з) и ее моментов, т. Обозначим ПЛС короткого кванта я4(в), длинного -Ч (в). Фкт (гг&2) и Фк1. Ч4(з) = -, ч(з) = е‘ва. Оно справедливо при условии, что квант обслуживания предка короткий, и этот предок не является требованием, находящимся на обслуживании в момент поступления помеченного требования в системную фазу. N - число поступлений в системную фазу за время . N=0,3, где 3 - число задач, находящихся в пультовой фазе к моменту начала кванта (в определении верхней границы для N использовано введенное выше ограничение). Найден Е[е-к|0х, в пультовой фазе 3 заявок ). Для этого применим ПЛС к обеим частям (1. Выражение, стоящее под знаком суммы, за исключением последнего сомножителя - вероятность того, что из 3 обдумываодих пользователей ровно ш заверяет обдумывание в течение времени х; ф7. Фк _ х. Г е~вхд4(х) у С" (1-Ь)т(1-е~*А*х)"’(ф (ЭМ)" бх. Таким образом, Е(е-зфк | С^. Е С? И(фк_4(8)-1)т ? НМ*(цг + з). Пусть теперь квант начальной задержки - длинный. Равенство (1. Формула (1. Вероятность длинного кванта равна е * короткого - 1-е ^2 . У р Г(1-е-М)А; + е'М А2 3, (1. Фк-д<3>. Здесь учтено то, что у К-требования коротким является лишь последний квант, остальные кванты - длинные. Вычислим первый и второй моменты Для А', А4, а затем и для фк(8). Продифференцируем А4 и подставим э=0, поменяв знак получившегося выражения. Ненулевой вклад дают лишь слагаемые, соответствующие т=0 и 1. Получим С4 = Я+3(1-Ь)Фк. Ъ= Ч1+3(1-Ь)Фк_1,1(1-Я*(»А1))+Фк. Р]((1-е'^а)сЧ е“М О* 3.