Определение минимального числа процессоров p, обеспечивающих заданное ускорение Sp

↑

⇐ ПредыдущаяСтр 5 из 5

ПРИЛОЖЕНИЕ 1.

Определение минимального числа процессоров p, обеспечивающих заданное ускорение Sp

Пусть  временная сложность 4 задач (подзадач) и возможные затраты времени на передачу сообщений между этими задачами заданы матрицей смежности взвешенного графа G(V,E), приведенной в табл.1:

Табл.1

№/№

При этом T1 = 100+ 180 + 120 + 110= 510.  Пусть требуемое ускорение Sp=2, (T1/Sp)=255. Тогда если, при наличии в разбиении k блоков, выполняется Tkmax <= T1/Sp , то p=k.

1. Проверяем достижимость: пусть k =4,  тогда  выполняется Tkmax= max( 100+10+10+40=160, 180+10+ 30+10= 230, 120+10+30+10=170, 110+40+10+10=170)=230,)=230, т.е. при k =4 решение существует.

2. Выполним поиск минимального значения k , при котором выполняется Tkmax <= T1/Sp (см. табл 2).

Табл. 2

№

PS

CH

k

Tk1

Tk2

Tk3

Tk4

Tkmax

Tkmax<T1/ Sp

400+60

110+60

390+50

120+50

280+90

230+90

330+50

180+50

220+90

290+90

210+40

300+40

100+60

310_60

280+90

120+50

110+60

220+90

180+50

110+60

100+60

300+40

110+60

210+40

180+50

120+50

Минимальное количество процессоров, обеспечивающих  Sp=2, составляет p=k=3.

ПРИЛОЖЕНИ 2.

Экспериментальная проверка эффективности разработанного метода двоичного поиска: сравнение алгоритмов Eq2_1 (усовершенствованный последовательный поиск) алгоритма Eq3_1 (двоичный поиск)

СМ. УСКОРЕНИЕ!

Исходные данные:

TestPartEq_n2nkpR22.cpp (r22):TEST FOR PARTITIONS OF THE GRAPH_

Enter number of elements:NumberOfRepeat=10 n= 12 ns=1 nf= 12 kf=10 kp=3

A[12][12]=

127.947 14.7766 12.8361 11.6984 11.3207 11.3167 10.71 13.3677 13.4231 12.5915 11.6858 10.6027

13.9036 121.183 11.586 14.8625 13.9174 14.4726 13.1594 14.2114 13.8597 12.392 12.8993 11.2491

11.4199 12.6792 141.997 11.948 12.7699 13.2466 11.0678 13.9917 12.3557 11.1483 14.1131 10.7102

14.2619 13.9427 13.0282 142.051 10.6163 14.2259 12.2852 13.7561 10.0056 14.6869 14.2622 13.1057

11.3683 13.5208 11.5201 12.7155 113.352 12.5489 12.4497 10.5846 10.4868 12.8867 12.0052 12.7282

11.494 10.5051 11.7457 11.9071 14.6141 115.271 10.9011 10.7036 13.5067 14.6062 12.6827 12.5364

11.8433 10.2255 12.5567 11.7089 13.6747 14.2697 126.984 11.0839 13.0273 10.7012 14.3487 13.4802

10.6975 10.6987 12.2875 10.3824 13.7114 13.0892 13.1468 140.596 10.4187 13.4249 11.7791 11.6858

11.6926 11.5467 12.4029 12.5565 11.1977 14.976 13.7399 11.9935 102.034 12.9824 14.8671 13.0346

14.9045 13.6683 10.9999 14.499 11.72 13.9132 10.9261 11.5235 13.5418 145.26 10.3069 12.1645

12.3959 10.4434 12.5692 11.1556 11.491 13.3232 11.6016 14.4205 12.1201 11.3713 129.777 10.4276

13.3833 13.7519 12.9218 11.9889 10.202 14.4189 11.7396 14.5874 12.595 12.7155 10.9284 148.34

Должны быть получены результаты:

/////*****NNNN******Последовательный поиск****NNNN***///

minSA=518.264

N=4 NN=0*2174464 duration = 4.765

np= 6 maxSA= 517.727

pPsi=[02174464]=1,1,2,3,3,4,4,5,6,6,6,6; pChi=[02174464]=1,1,2,3,3,4,2,5,6,4,5,6

SA[]=501.292,517.727,509.063,505.383,506.814,504.967

******************************************************

****************/////////////////////////********************

*******N2N*********Двоичный поиск*******N2N*************

 minSA=518.264

N=4 NN=0*2103546 duration = 4.672

minnp= 6 minmaxSA= 517.727

minpChi=[02103546]=1,1,2,3,3,4,2,5,6,4,5,6

mnpSA[]=501.292,517.727,509.063,505.383,506.814,504.967

******************************************************

****************************************************************

Вручную или на компьютере надо проверить, что вектор pChi=[02174464]=1,1,2,3,3,4,2,5,6,4,5,6 найден правильно:

(max((Q_i  + R_i), где i=1, 2, …, k) < или = minSA=518.264, которое обеспечивает заданное ускорение (kp=3). Обратите внимание на pChi последовательного и двоичного поиска и на времена поисков.

Ускорение =1,019906.

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



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману