Лабораторные работы по информатике

Гуманитарные науки

У нас студенты зарабатывают деньги

 Дипломы, работы на заказ, недорого

 Контрольные работы

Контрольные работы

 Репетиторы онлайн по английскому

Репетиторы онлайн по английскому

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Приглашаем авторов для работы

Авторам заработок

Решение задач по математике

Закажите реферат

Закажите реферат

Практикум по физике Лабораторные работы по информатике Microsoft Visio Алгоритмические основы машинной графики AutoCAD
Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №6. Определение ранних и поздних сроков окончания выполнения операторов и оценка снизу требуемого количества процессоров и времени решения задачи на ВС

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

Теоретическая часть

Рассмотрим алгоритм, представляемый информационным графом (без связей по управлению), не имеющим контуров. Тогда очевидно, что момент окончания выполнения любого из операторов не может быть меньше максимальной из длин всех путей, заканчивающихся вершиной, соответствующей этому оператору. Таким образом, для каждого оператора, j = 1, …, m алгоритма можно найти ранний срок  окончания его выполнения.

Если окончание выполнения алгоритма ограничено временем T ≥ Tкр, то для каждого оператора можно найти и поздний срок окончания его выполнения . Здесь Tкр (критическое) – максимальная характеристика пути в графе со скалярными весами, и определяет минимальное время, за которое может быть решена данная задача.

Окончание выполнения любого оператора позже этого позднего срока приводит к тому, что все последующие за ним операторы не смогут быть выполнены в заданный срок Т, поэтому без задания Т определение поздних сроков не имеет смысла. При Т = Ткр ранние и поздние сроки выполнения операторов, входящие в критический путь, совпадают.

Далее приводятся алгоритмы нахождения ранних  и поздних  сроков окончания выполнения операторов алгоритма, заданного матрицей следования S, где j = 1, …, RS.

Алгоритм 6.1. Нахождение ранних сроков окончания выполнения операторов.

Положим , где j = 1, …, RS.

Просматриваются строки матрицы S сверху вниз, выбирается первая необработанная строка матрицы и осуществляется переход к следующему шагу. Если обработаны все строки, то – конец алгоритма.

Пусть выбрана j-я строка, не содержащая единичных элементов, далее вычисляется , где Pj – вес j-го оператора, затем выполняется переход на шаг 5.

Если j-я строка содержит единичные элементы, то вычисляется , где  есть множество времен, которым соответствует единица в данной строке, и выполняется переход на шаг 5. Если во множестве  есть нулевые элементы, то выполняется шаг 6.

Обработанная j-я строка исключается из рассмотрения и осуществляется переход на шаг 2.

Если найдена строка jν, для которой , то вычисляется строка j = jν, и осуществляется переход на шаг 3.

Конец алгоритма.

Примечание: пункт 6 используется для нетреугольной матрицы S.

Алгоритм 6.2. Получение поздних сроков окончания выполнения операторов.

Положим , где j = 1, …, RS.

Просматриваются столбцы матрицы S справа налево, выбирается первый необработанный столбец матрицы и производится переход к следующему шагу. Если обработаны все столбцы, то – конец алгоритма.

Пусть j – номер очередного необработанного столбца, если он не содержит единичных элементов, то вычислим , где Т – время решения задачи, и переходим на шаг 5.

Если столбец j содержит единичные элементы, то вычисляется , т.е. минимум определяется по всем jνединичным элементам j-го столбца. Если , то выполняется шаг 6.

Обработанный j-й столбец исключаем из рассмотрения, затем выполняется шаг 2.

Если найден столбец jν, для которого , то производится поиск необработанного столбца jν, вычисляется j = jν и выполняется переход на шаг 3.

Конец алгоритма.

Примечание: пункт 6 используется для не треугольной матрицы S.

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

Рассмотрим пример получения ранних и поздних сроков окончания выполнения операторов для графа, представленного на рисунке 6.1.

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

Ранние сроки будут выглядеть следующим образом:

Поздние сроки (при T = 18):

 

Диаграммы выполнения операторов для вычисленных ранних и поздних сроков окончания выполнения операторов показаны на рисунке 6.2.

Рисунок 6.2. Временные диаграммы ранних (а) и поздних (б) сроков окончания выполнения операторов

Определение 6.1. Множество входных вершин графа G называется минорантой графа G.

Определение 6.2. Множество выходных вершин графа G называется мажорантой графа G.

Пусть А есть миноранта , B – мажоранта графа G, а pj – вес j-го оператора, тогда множество значений сроков окончания выполнения операторов определяется следующими неравенствами:

 (6. 1)

 (6. 2)

 (6. 3)

Множество значений, определяемых неравенствами (8 – 1) – (8 – 3), задает многоугольник MT в RS-мерном пространстве: , тогда справедливо следующее определение.

Определение 6.3. Функция , где  называется плотностью загрузки ВС в точке  для значения .

Значение функции PZ в каждый момент времени формируется операторами множества ВНО, т.е. в каждый момент времени значение функции PZ совпадает с числом одновременно выполняемых операторов.

Определение 6.4. Функция  называется загрузкой отрезка  для

Функция Z определяет количество выполненных на этом отрезке операторов (с учётом частично выполненных операторов).

Определение 6.5. Функция  называется минимальной загрузкой отрезка  для .

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

Для составления алгоритма вычисления данной функции введем функцию :

Алгоритм 6.3. Вычисление функции

С помощью алгоритмов 6.1 и 6.2 вычисляются ранние  и поздние  сроки окончания выполнения операторов.

Полагаем  .

Анализируем последовательность оператора  Если просмотрены все операторы, то конец алгоритма.

Вычислим

. (6. 4)

После перебора всех операторов получаем значение

Конец алгоритма.

Лемма 6.1. «Об оценке сверху требуемого количества процессоров для решения задачи за время Т».

Минимальное количество однородных процессоров N, способных выполнить данный алгоритм за время , не превышает , где  – число операторов, входящих в i-ое полное множество ВНО, полученное для информационного графа G, соответствующего исследуемому алгоритму.

Следствие. При N = E время решения данного алгоритма Т = Ткр.

Примечание. Получаемое количество процессоров N на основании этой леммы является верхней оценкой требуемого количества процессоров (т.е. для решения данной задачи требуется не более N процессоров).

Теорема 6.1. «Об оценке снизу числа процессов, необходимых для решения задачи за время Т».

Для того чтобы N процессоров было достаточно для выполнения заданного алгоритма, представленного информационным графом со скалярными весами вершин за время Т, необходимо, чтобы для отрезка   выполнялось соотношение:

,

где  – минимальная загрузка отрезка [a,b].

Теорема 6.2. «Об оценке снизу времени выполнения задачи при заданном количестве процессоров».

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

,

где  – минимальная загрузка отрезка [a,b].

Теорема 6.3. «Об уточнении оценки снизу времени выполнения задачи на N процессорах».

Если Т1 – оценка снизу времени выполнения алгоритма, представленного информационным графом со скалярными весами вершин на ВС, имеющей N процессоров, и на отрезке  выполняется соотношение  тогда наименьшее время Т реализации алгоритма удовлетворяет соотношению

.

Алгоритм 6.4. Оценка минимального числа процессоров, необходимого для выполнения алгоритма за время Т.

Положим N := 0.

Последовательно перебираем интервалы   в порядке:

Всего отрезков: .

Для очередного интервала [a,b] вычислим , где   определяется по алгоритму 6.3.

Если N1 > N, то N := N1.

После обработки всех интервалов, получается требуемое N.

Конец алгоритма.

Алгоритм 6.5. Оценка минимального времени Т выполнения заданного алгоритма на ВС, содержащей N процессоров.

Вычислим , где ]х[ – ближайшее к х целое, не меньшее х, pi – вес i-го оператора.

Просматриваются интервалы , как в алгоритме 6.4 пункте 2.

Примечание. При таком выборе последовательности отрезков значение T можно увеличивать, не пересчитывая при этом ранее вычисленные значения d.

Для очередного интервала   вычислим значение , величина  вычисляется по алгоритму 6.3.

Если d > 0, вычислим .

Вычислим .

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

Конец алгоритма.

Вопросы для самопроверки

Что характеризует ранние и поздние сроки выполнения операторов?

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

При совпадении Ткр с временем Т ранние или поздние сроки выполнения каких операторов совпадают?

Почему при вычислении функции Z(T) нужно выбирать минимальное значение из разности соответствующих времен в формуле (6.4)?

Какой смысл имеют величины a и b при вычислении функции Z(T)?

На каком временном интервале функция  принимает значение 1?

Почему количество требуемых процессоров не может быть больше числа операторов, входящих во множество ВНО в рассматриваемый момент времени?

В чём смысл леммы 1, в каких целях его можно использовать?

Почему минимальная загрузка на рассматриваемом интервале [a,b] может сравниваться с выражением .

Задание на лабораторную работу

Необходимо дополнить имеющуюся программу следующими функциями:

нахождения ранних и поздних сроков окончания выполнения операторов, отображения их в виде таблицы-дополнения одновременно с матрицей S и весами операторов;

отображения полученных результатов на диаграммах выполнения работ;

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

Продемонстрировать работающую программу преподавателю и получить отметку о ее выполнении.

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

Ответы на вопросы для самопроверки.

Схемы алгоритмов и их описание.

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

Анализ полученных результатов.

Лабораторные работы