Сравнительный анализ критериев эффективности при решении неоднородной минимаксной задачи списочным алгоритмом

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

Планирование выполнения функциональных операторов вычислительной системой. Имеется вычислительная система, состоящая из N несвязанных устройств (процессоров) P = { P 1 ,P 2 ,-, P n } . На обработку поступает M - множество независимых параллельных заданий (работ, операторов) T = { t 1 , t 2 ,...,t m } , известно время решения т ( t , p j ) каждого задания t_t на устройстве p_j – матрица Τ_τ . Устройства неоднородны, но каждое задание может выполняться на любом устройстве, время выполнения определяется значением т ( tp ) . Если задание не может быть выполнено на каком-либо из обслуживающих устройств совсем, то это устройство с избирательными свойствами и время выполнения задачи на этом устройстве определено как т ( tp ) = да [1]. В каждый момент времени отдельный процессор обрабатывает не более одного задания и выполнение задания не прерывается для передачи на другой процессор. Требуется найти такое распределение заданий по процессорам, при котором суммарное время выполнения заданий на каждом из процессоров было бы минимальным.

Алгоритм В.Н. Плотникова – В.Ю. Зверева. При решении распределительной задачи эффективность полученного решения зависит от выбора алгоритма, который должен наилучшим образом учитывать структуру и характеристики вычислительных устройств. Широкое распространение получили простые и достаточно эффективные списочные расписания, основанные на эвристических алгоритмах. Среди таких алгоритмов можно выделить алгоритм, предложенный В.Н. Плотниковым и В.Ю. Зверевым. Это приближенный метод для поиска близкого к оптимальному решению использующий критерий минимакса.

• 1.    Упорядочим строки матрицы Τ _τ по убыванию сумм всех элементов строки nn   n

• 2.    В преобразованной матрице Т _т выделим первую строку i =1 и найдем в ней min ( T ( 1 1 p j )) - минимальный элемент. Примем этот элемент за элемент распределения и прибавим его к соответствующему элементу второй строки min ( T ( 1 1 p j )) + ( т ( t ₂ p j )) .

• 3.    Вторая строка теперь учитывает предыдущее решение. Выберем из нее минимальный min ( T ( t ₂ p j )) ,прибавим его к соответствующему элементу третьей строки min ( T ( 1 ₂ p j )) + ( т ( t ₃ p j ))

• 4.    На выполнение назначается минимальный элемент строки min (T"( t i p )) , такой что ^min( T ( tp )) # 0 .

∑ (т( t i Pj)) > ∑ (Т(t2Pj )) > ->^ (т(tmpj)). Этим достигается распределение на первых этапах j=i                     j=i                               j=i алгоритмов с большим временем счета и более равномерная загрузка ими вычислительных машин.

и т.д., получим матрицу Т _т .

Данный алгоритм применяется для неоднородной вычислительной системы, т. е. тогда когда время выполнения одного и того же задания может отличаться на разных вычислительных устройствах. Алгоритм отличается наибольшим по сравнению с точными быстродействием, простотой и позволяет получить приемлемые по точности решения [2].

Адаптация алгоритма В.Н. Плотникова – В.Ю. Зверева к квадратичному критерию.

• 1.    Упорядочим строки матрицы Т _т по убыванию сумм всех элементов строки nn   n

• 2.    Объявим строку в - строкой текущего состояния.

• 3.    Для каждого элемента столбца посчитаем квадратичный критерий ^= £ ( ^в+Н ¹ i p j ) ) ) .

• 4.    К строке в добавим элемент строки ( т ( 1 1 p_j )) такой, что ц i минимально.

• 5.    Повторить последовательно для всех строк матрицы.

2 ( ^т ( ¹ i p j )) >  2 ( ^Т ( ¹ 2 p j )) >  - >  2 ( ^т ( t m p_j )) . Этим достигается распределение на первых этапах j = 1                      j = 1                                j = 1

алгоритмов с большим временем счета и более равномерная загрузка ими вычислительных машин.

Адаптация алгоритма В.Н. Плотникова – В.Ю. Зверева к кубическому критерию.

Упорядочим строки матрицы    Т _т   по убыванию сумм всех элементов строки

2(т(11 pj)) > 2(т(12pj))> ->2(т(tmp^ . Этим достигается распределение на первых эта-j=i                      j=i                              j=i пах алгоритмов с большим временем счета и более равномерная загрузка ими вычислительных машин.

• 1.    Объявим строку в - строкой текущего состояния.

• 2.    Для каждого элемента столбца посчитаем кубический критерий ц i = 2 ( в + ( ^т ( 1 1 p _j ) ) ) •

• 3.    К строке в добавим элемент строки ( т ( 1 1 p_j )) такой, что ц i минимально.

• 4.    Повторить последовательно для всех строк матрицы [3].

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

	24	14	22		24	[14]	22
	9	22	24		[9]	22	24
T ' =	6	23	14	T ' =	6	23	[14]
	19	13	9		19	13	[9]
	6	1	10		[6]	1	10

Используя минимаксный критерий, получаем распределение (15, 14, 23); теперь использу-

ем квадратичный критерий. 24 [14] 22 576 [196] 484 [9] 22 24 [277] 1296 772 T'= [6] 23 14 Z' = [421] 1450 473 . 19 13 [9] 1352 954 [502] 6 [1] 10 718 [531] 782 На приведенной матрице Z' , в правой части представлен подсчет квадратичного крите- рия критерия. В результате вычисления получили распределение (15, 15, 9). Теперь используем кубический критерий:

24	[14]	22		13824	[2744]	10648
[9]	22	24		[3473]	46656	16568
[6]	23	14	Z ' =	[6119]	51382	6217
19	13	[9]		42048	23058	[6848]
6	[1]	10		12734	[7479]	12978

На приведенной матрице Z ^' , в правой части представлен подсчет кубического критерия. Используя кубический критерий, получаем следующее распределение (15, 15, 9).

Так как алгоритм, предложенный В.Н. Плотниковым и В.Ю. Зверевым, использует минимаксный критерий, а авторы предлагают использовать кубический и квадратичный критерий, необходимо определить, какой критерий даст более приемлемый результат. Аналитически доказать, какой лучше критерий, авторам не удалось. Поэтому для ответа на данный вопрос были проведены вычислительные эксперименты при размерностях задачи из интервала [25, 30]. Минимальное количество экспериментов по каждой размерности равнялось 1000. Результат представлен в табл.1.

Таблица 1

Сравнение кубического, квадратичного и минимаксного критерия

Наименование/nxm	2x31	3x31	4x31	2x131	3x131	4x131	2x531	3x531	4x531
Средний t max по куб. крит.	415	289	214	1737	1157	858	6999	4613	3421
Средний t max по минимак. крит.	418	291	215	1750	1181	882	7130	4749	3525
Средний t max по квадрат. крит.	414	288	212	1731	1151	853	6977	4596	3408

Для большого числа приборов результаты представлены в табл.2.

Сравнение кубического, квадратичного и минимаксного критерия

Таблица 2

Наименование/nxm	7x31	8x31	9x31	7x131	8x131	9x131	7x531	8x531	9x531
Средний t max по куб. крит.	128	104	102	491	438	388	1949	1705	1522
Средний t max по минимак. крит.	129	107	102	500	442	391	2029	1773	1566
Средний t max по квадрат. крит.	128	104	101	488	434	385	1938	1702	1498

Выводы. Для алгоритма В.Н. Плотникова – В.Ю. Зверева наиболее приемлемым критерием является квадратичный, так как применение его дает лучшие результаты. Преимуществом данного критерия является то, что при увеличении размерности задачи применение квадратичного критерия приводит к получению результатов на порядок лучше, чем минимаксный и более предпочтительный, чем кубический.