Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний»


Скачать 105.18 Kb.
НазваниеМетодические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний»
Дата публикации17.02.2014
Размер105.18 Kb.
ТипМетодические указания
vb2.userdocs.ru > Информатика > Методические указания

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ


ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


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

и автоматизированных систем”


Методы получения расписаний для неоднородных систем обработки информации

Методические указания

и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний», для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование»

Ростов-на-Дону

2006
^

Составитель: Кобак В.Г., Красный Д.Г.




Методы получения расписаний для неоднородных систем обработки информации: Методические указания. - Ростов н/Д : Издательский центр ДГТУ, 2006.-10 с.

Предназначены для лабораторных и практических занятий, курсового проектирования по теме «Теория расписаний», для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование»

Печатается по решению методической комиссии факультета «Автоматизация и информатика».

Рецензент

Издательский центр

ДГТУ, 2006 г.

1. Введение


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

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

В настоящем руководстве приводятся методы получения расписаний, приводящие к небольшим затратам на вычисление за счет отказа от получения оптимального решения, но в тоже время позволяющие найти приемлемое решение, близкое к оптимальному.
  1. ^

    2. Постановка задачи


Имеется независимых работ , которые необходимо распределить на параллельно работающих разнородных устройств по критерию , где - время завершения работы процессора . Каждое устройство выполняет только одну работу в определенный момент времени и выполнение задания не прерывается для передачи на другой процессор. Известно (вес) время выполнения задания на любом из устройств . Требуется найти такое распределение заданий по процессорам, при котором суммарное время выполнения заданий на каждом из процессоров было бы минимальным.

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

Задача №1

Значения задаются матрицей размером , при , где i-номер алгоритма, j-номер процессора. Рассмотрим задачу 3, 3. Исходная матрица времени выполнения работ

.

Задача №2

Матрица размером , при . Рассмотрим задачу 8, 8. Исходная матрица времени выполнения работ

.

Задача №3

Значения задаются матрицей размером , где i-номер алгоритма, j-номер процессора. , Где , . Исходная матрица времени выполнения работ Задача №2

Значения задаются матрицей размером , где i-номер алгоритма, j-номер процессора. , Где , . Исходная матрица времени выполнения работ


^

3. Алгоритмы распределения работ на параллельно работающие устройства

    1. Распределение независимых работ (Бондаренко А.Т., Сапатый П.С.)


Ш.1 Определяются элементы множества и , где и .

Ш.2 Формируется последовательность I, для которой выполняется неравенство и последовательность J, для которого справедливо .

Ш.3 Получаем предварительное распределение работ по устройствам путем постановки в соответствие элементов I и J.

Ш.4 Упорядочиваем последовательности I и J для выполнения неравенства .

Ш.5 В последовательности элементов , входящей в J, ищем первый элемент (k-й по порядку в J), для которого и. Если таких элементов нет, переход к Ш.7, в противном случае переход к следующему шагу.

Ш.6 Выполняем транспозицию элементов и в J. Восстанавливаем упорядоченность последовательностей I и J для выполнения условий Ш.5.

Ш.7 Конец работы алгоритма. Решением считаются все соответствующие пары из I и J.

Рассмотрим более подробно работу алгоритма на примере, решив задачу №1.

Предварительное распределение на Ш.1-Ш.4 предполагает распределение на более быстродействующие процессоры более длительных работ. Быстродействие процессора определяется временем выполнения на нем заданного набора работ, а длительность выполнения конкретной работы оценивается по суммарному времени выполнения ее последовательно на всех устройствах.

Для построения расписания выполним алгоритм.

Ш.1 Определим множества элементов и , как сумма по строкам и сумма по столбцам.







Упорядочив множества, получим последовательность I и J;

I=(3,1,2); J=(1,2,3). Переставляем элементы I,J так, чтобы выполнялось условие в Ш.4.



, для того чтобы выполнялось условие Ш.4, сделаем перестановку попарно i,j

I=(3,2,1); J=(1,3,2).

Тогда - условие выполняется .

Выполним Ш.5 к=1..J , при к=2

и т.е.,и ;

меняем местами 2 и 1 элементы в J, J=(3,1,2); с учетом того, чтобы выполнялось условие Ш.4 .

Ставя в соответствие элементы множеств I и J, получаем следующее решение =11.
    1. ^

      Алгоритм построения расписания при N=M


Число процессоров равно числу заданий и на каждом процессоре должно выполниться только одно задание. Использование приближенного метода в данном случае представляется наиболее целесообразным для сокращения времени решения. Метод основывается на учете специфического свойства матрицы. Это свойство определяет стратегию распределения согласно следующей теореме.

Теорема 1: Если в каждой i-й строке матрицы приращения , для всех j от 1 до N-1 и строки матрицы расположены так, что , то приемлемое (оптимальное) распределение будет составлено из элементов главной диагонали. ([3] – доказательство теоремы).

Ш.1 Для каждой строки матрицы весов определяется приращение и строки переставляются по порядку убывания приращения.

Ш.2 Преобразованная матрица разбивается на 4 квадратных подматрицы размером для четных N и размером и для нечетных N.

Ш.3 С двумя матрицами, главные диагонали которых совпадают с главной диагональю исходной матрицы, выполняют Ш.1. Процесс последовательной декомпозиции подматриц заканчивается при размерах или .
      1. ^

        Выбор показателя s для критерия


Показатель s подбирается из условия , при использовании критерия минимакса в качестве a берется ближайшее к значение.

Рассмотрим более подробно работу алгоритма на примере, решив задачу №2.

Матрица

(1)
Слева от матрицы (1) проставлены номера строк, справа - значения приращения . Параметр s=2, т.к. =10 , и a=9 . Расположим строки по убыванию приращений и разобьем полученную матрицу на 4 подматрицы .
(2)
Для левой верхней подматрицы вычислим приращение по формуле ,где (i=5,7,6,3); для правой нижней – по формуле ,где (i=2,4,1,8). Полученные приращения указаны справа от матрицы (2).

В каждой из подматриц матрицы (2) упорядочим строки по убыванию приращений и разобьем каждую из подматриц на 4 подматрицы размером .



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

Результат: =5.
    1. ^

      Алгоритм построения расписания с произвольной загрузкой


Описанный ниже метод более эффективен по скорости поиска приемлемого по точности решения.

Дана прямоугольная матрица .

Ш.1 Упорядочим строки матрицы ^ T по убыванию сумм всех их элементов.

Ш.2 В преобразованной матрице T
в первой строке и найдем минимальный элемент. Примем этот элемент за элемент распределения и прибавим его к соответствующему элементу следующей строки.

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

Решим задачу №2 рассматриваемым алгоритмом: после выполнения Ш.1, множество заданий примет вид:

Сложили элементы в строках матрицы.



Упорядочиваем строки в порядке убывания по суммам, матрица примет вид:



Согласно Ш.2 строим расписание (справа вверху над элементом указывается суммарная загрузка процессора в столбце):





Выполнив алгоритм, получим расписание:



Результат: =20.
  1. ^

    4. Варианты заданий


Задание определяется согласно № - номера студента в списке, по приведенным ниже таблицам (таблица 1, таблица 2). Алг. - номер алгоритма в данном руководстве, который необходимо запрограммировать. Параметр n-определяет число устройств. m – количество работ, выбирается одно значение из указанного отрезка в таблице 2, T – множество весов работ, случайным образом берется m работ в пределах указанных в таблице 2.

Например, если студент в списке под номером №8, то Алг. = “Алгоритм 3.2”, n = 8, m для указанного алгоритма равно n, T формируется из m работ, вес которых выбирается случайным образом в отрезке [1,25], в результате T – матрица размером , где каждый элемент определяет время выполнения задачи на конкретном устройстве, т.к. устройства разнородные.
Таблица 1



1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Алг.

Алгоритм 3.1

Алгоритм 3.2

Алгоритм 3.3

n

3

4

5

8

9

10

4

5

6

m, T

1

2

1

2

1

2

8

1

9

2

10

1

1

2

1

2

1

2


Таблица 2

m, T

1

6-15

1-25

2

8-14

3-30



  1. Литература


  1. Поспелов Д.А. Введение в теорию вычислительных машин. – M.: Советское радио, 1972

  2. Пашкеев С.Д. Основы мультипрограммирования для специализированных вычислительных машин. – M.: Советское радио, 1964

  3. Плотников В.Н., Зверев В.Ю. Техническая кибернетика №3 M., 1974

  4. Бондаренко А.Т., Сапатый П.С. Техническая кибернетика №4 –Киев, 1975







Похожие:

Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания и контрольные задания к практическим, лабораторным...
«Теория расписаний», для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование»
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания и контрольные задания к практическим, лабораторным...
Кафедра “Программное обеспечение вычислительной техники и автоматизированных систем”
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания к курсовому проектированию
Методические указания к курсовому проектированию по учебной дисциплине «Управленческие решения» / Сост.: Л. В. Орлова; гуу. – М.,...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания и контрольные задания по курсу «Транспортное право»
Методические указания содержат контрольные задания, состоящих из двух разделов, вопросов к контрольной работе и списка рекомендуемой...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания к лабораторным и практическим занятиям по дисциплине «Газоснабжение»
«Газоснабжение» для студентов специальностей 290700, 100700 очной и заочной форм обучения
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания к практическим занятиям для студентов медицинского...
Методические указания к лабораторным занятиям по гистологии предназначены для самостоятельной работы студентов I курса медицинского...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания к практическим занятиям составлены в соответствии...
Методические указания к практическим занятиям составлены в соответствии с программой по дисциплине «Механика ii» для бакалавров по...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические указания к практическим занятиям по дисциплине «Английский язык»
Методические указания предназначены для практических занятий студентов 2 курса всех специальностей факультета «Автоматики и вычислительной...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодические рекомендации к практическим занятиям направление подготовки:...
Строительные машины и оборудование: методические рекомендации к практическим занятиям / сост. Костина Н. В.— Ставрополь: Изд-во скфу,...
Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию по теме «Теория расписаний» iconМетодическое пособие к практическим занятиям по дисциплине «Основы теории систем и управления»
«Методические указания к практическим занятиям по дисциплине «Основы теории систем и управления» по профессиональному направлению...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
vb2.userdocs.ru
Главная страница