Занятие №4

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

1. ЦЕЛЬ ЗАНЯТИЯ: практическое закрепление знаний о распределении загрузки между процессорами многопроцессорной системы.

2. ОСНОВНЫЕ СВЕДЕНИЯ.

Рассматриваемый в данном разделе метод распределения известен под названием "алгоритм Хорошевского". Он основывается также на поярусном распределении и может быть применен в случае, когда количество процессоров меньше ширины яруса.

Пусть в f-м ярусе b^f>n, где b^f - количество работ; n - когда количество процессоров, причем производительности процессоров характеризуются S = {S₁, S₂, …, Sn} и процессоры, как и в предыдущем разделе, упорядочены по производительности. Кроме того, известны матрицы

где l^fim - время реализации i-й работы на m-м процессоре. Элемент, каждой строки матрицы (времена реализации одной и той же i-й работы на каждом из m данных процессоров) расположены в соответствии с упоря­доченностью процессоров по производительности.

Минимально-возможное время реализации всех работ данного f-го яруса с помощью заданной вычислительной системы определяется с помощью выражения:

Это время является нижней теоретической оценкой в случае работы систе­мы на f-м ярусе без простоев процессоров.

Сущность данного метода распределения состоит в том, что путем перебора на каждый из процессоров распределяется такая группа работ из яруса, время обслуживания которой имеет минимальное отклонение от w^f. Тогда и общее время обслуживания одного яруса всеми процессорами вычи­слительной системы имеет минимальное отклонение от w^f. Практически по­лучить время обслуживания всех работ в ярусе, равное w^f, при исполь­зовании рассматриваемого метода возможно только в случае, когда ЯПФ, по крайней мере, равномерна, а количество работ в ярусе кратно количе­ству процессоров. В произвольном же случае время обслуживания всех работ будет превышать w^f.

Введем следующие обозначения:

Q^fm - нераспределенные работы к моменту распределения на m-й процессор;

P^fт - распределенные работы к моменту распределения на (m+1) процессор;

Процесс начинается с определения w^f. Далее производится распреде­ление на самый малопроизводительный n-й процессор. Методом перебо­ра выбираются две группы работ, суммарное время реализации одной из которых на n-м процессоре наиболее близко подходит к w^f снизу (d_m), а другой - сверху (d^m). Если оказалось, что d^m существует, то оцени­вается, какое из отклонений d_m или d^m наиболее близко находится к w^f. На процессор распределяется та группа работ, суммарное время реализации которых имеет наименьшее отклонение от w^f*.

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

Если при распределении на m-й процессор (m = n, …, 1) оказалось, что не существует d_m, то необходимо вычислить новое значе­ние w^f без учета т-го процессора. При слабом влиянии на производительность системы остается соотношение d_m> w^f *, и тогда можно иск­лючить из рассмотрения m-й процессор, как затормаживающий работу системы и для дальнейшего рассмотрения принять w^f = w^f*. Если же оказывается, что d_m< w^f*, то на m-й процессор необходимо распределить ту работу, для которой l^fim = d_m.

Время обслуживания работ f-го яруса оценивается (d_m) max. Если оказывается, что количество работ в ярусе меньше, чем количество процессоров, то распределение осуществляется на основе методики, при­веденной в предыдущем разделе.

Пример распределения загрузки.

В качестве примера распределим загрузку для реализации алгоритма, заданного ЯПФ (рис. 4.1.). Алгоритм будет реализовываться на вычислительной системе состоящей из двух параллельно работающие процессоров, относительная производительность которых, по сравнению с эталонной, производительность которого принята за единицу, приведена в табл. 4.1.

Таблица 4.1.

N процессора		П1	П2
Sm		1	0,6
f=1	11	10	/16, 86/
	21	/15/	25
	31	/20/	33, 33
	41	18	/30/
	51	/12/	20
f=2	12	/9/	15
	22	5	/8, 33/
	32	14	/23, 33/
	42	/3/	5
	52	/9/	15
	62	/11/	18, 33
f=3	13	/8/	13, 33
	23	/11/	18, 33
	33	6	/10/
	43	7	/11, 66/

рис.4.1.

Рассчитаем длины работ с учетом их реализации на процессоре m-го типа по формуле:

где l^fiэ – время реализации работы на процессоре, производительность которого принята за эталонную Sэ = 1. Составим матрицу обслуживания работ на процессорах, входящих в систему, и формируем на основе ее табл. 4.1. для всех ярусов.

По полученной матрице рассчитаем w^f*, f ⁼ 1, 2, 3:

w¹ = 46.88, w² = 31.94, w³ = 20.

Распределение работ начинаем с процессора, имеющего наименьшую производительность (Пр.2). Находим:

а) f = 1;

d₂[1¹, 4¹] = 46.66; t₂ = 46.88 - 46.66 = 0.22;

d²[1¹, 3¹] = 49.98; t² = 49.99 - 46.88 = 3.11;

t₂ < t², следовательно, P²{1¹, 4¹}. Оставшиеся работы распределяем на Пр.1, и тогда время обслуживания этих работ составит

d¹ [2¹, 3¹, 5¹] = 47;

Таким образом, время обслуживания первого яруса при подученном, распри делении составляет

T¹реш = 47.

б) f = 2;

d₂[2², 3²] = 31.66; t₂ = 31.94 – 31.66 = 0.28;

d²[5², 6²] = 33.33; t² = 33.33 – 31.94 = 1.39;

t² < t₂, следовательно, P²{2², 3²}. Оставшиеся работы распределяем на Пр.1. и тогда время обслуживания этих работ составит

d₁[1², 4², 5², 6²] = 32.

Таким образом, время обслуживания второго яруса при полученном распределении составляет

T²реш = 32;

в) f = 3;

d₂[2³] = 18.33; t₂ = 20 – 18.33 = 1.67;

d²[3³, 4³] = 21.66; t² = 21.66 – 20 = 1.66;

t² < t₂, следовательно, P²{3³, 4³}. Оставшиеся работы распределяем на Пр.1, и тогда время обслуживания этих работ составит

d₁[1³, 2³] = 19.

Таким образом, время обслуживания третьего яруса при полученном распре явлении составляет

T³реш = 21.66;

Работы, распределенные по процессорам, отмечены в табл.4.1. в соответствующем столбце знаками //.

В результате получаем:

в) время решения задачи в системе:

;

б) суммарные простои процессоров:

;

в) коэффициент простоя процессоров:

;

г) повышение производительности системы по сравнении со случаем использования одного процессора:

3. ВАРИАНТЫ ЗАДАНИЯ.

По заданной преподавателем первой букве выбрать матрицу графа прог­раммы по табл. 1.3 - 1.7. По заданной цифре из табл. 1.6 выбрать значения трудоемкости работ при обслуживании их процессором с относи­тельной производительностью Sэ = 1. По заданной второй букве выбрать относительные производительности процессоров по таблице 3.2.

Необходимо выполнить:

1. преобразовать граф в ярусно-параллельную форму

2. построить по графу ЯПФ G сеть G`;

3. распределить работы по процессорам в каждом ярусе;

4. вычислить основные характеристики распределения.

4. ФОРМА ОТЧЕТА.

Отчет должен включать:

- вариант задания;

- чертеж полученной ЯПФ;

- чертеж сети G`;

- таблицу распределения работ;

- расчет характеристик распределения.