Проверка монотонности зависимости Tk от числа процессоров к

↑

⇐ ПредыдущаяСтр 2 из 5Следующая ⇒

Результаты теоретического анализа предложенных вычислительных схем и экспериментального исследования временной сложности алгоритма Eq2_1 показали эффективность этого математического обеспечения. Но эта эффективность основывалась на неявном предположении о монотонном убывании значений функции T_k, удовлетворяющего соотношению (1.1), при увеличении числа процессоров k. Проверка монотонности T_k выполнялась с использованием статистического моделирования: в каждой точке эксперимента рассчитывалась матрица смежности вершин взвешенного графа (матрица A), который затем подвергался разбиению. Каждая экспериментальная точка характеризовалась числом вершин в графе (n =10, 11, …, 15) и диапазоном отклонения весов вершин и рёбер графа от среднего значения (dtmax=10, 20, …50). При генерации случайных значений матрицы матрица A, подчиняющихся равномерному распределению, использовались стандартные функции языка Си [2, стр. 753]. В ходе вычислительного эксперимента анализировались все возможные варианты разбиения множества V. Эти варианты разбиений были разбиты на классы эквивалентности, каждый из которых включал в себя разбиения с одинаковым числом подмножеств (np). Это число подмножеств являлось номером соответствующего класса эквивалентности. Таким образом, классы эквивалентности получили номера 1, 2, …, n, где n – это число вершин в графе G(V,E). Для каждого класса эквивалентности определялось разбиение, обеспечивающее минимизацию функции T_k.

Основные результаты вычислительного эксперимента с программной реализацией приведённого выше алгоритма представлены в таблицах 1, 2 .

Таблица 1

np

Функция  max((Q_i  + R_i), где i=1, 2, …, k), n= 10, kf=5

dtmax=10

dtmax=20

dtmax=30

dtmax=40

dtmax=50

1047.93

1109.71

1204.94

1207.09

1326.16

1046.84

1099.97

1183.43

1197.96

1278.16

912.141

939.28

990.687

999.382

1075.45

748.269

781.278

830.781

840.565

892.291

547.908

573.773

628.536

631.851

665.934

542.773

572.548

608.786

626.196

659.396

542.584

566.843

606.34

607.744

648.45

540.253

559.112

589.004

600.598

636.543

538.378

553.213

584.825

589.711

623.346

300.195

321.148

345.694

359.529

382.16

Таблица 2

np

Функция  S , n= 10, kf=10

dtmax=10

dtmax=20

dtmax=30

dtmax=40

dtmax=50

1055.85

1085.55

847.791

1224.94

1281.17

788.788

815.194

685.55

911.122

951.402

663.544

670.366

558.81

729.754

752.192

532.374

542.54

409.554

598.506

620.633

380.065

393.036

403.619

442.324

462.905

378.611

389.079

396.358

432.056

450.07

375.762

384.239

390.168

428.051

445.064

374.347

380.112

382.772

412.031

425.039

370.591

375.182

233.047

408.587

420.734

203.888

218.698

847.791

246.71

260.888

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

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры