close

Вход

Забыли?

вход по аккаунту

?

О длительности вычислений минимальных сплайнов первой высоты на параллельной системе.

код для вставкиСкачать
Y,lI,K
518
BeCTHllK CII6ry. Cep.
10. K.j{e.M:b.ft1W8U"t,
M.
10, 2006,
BbIll.
3
A. Mapm1Owo8
o ,I1;JIMTEJIbHOCTM BbPIMCJIEHMM
MMHMMAJIbHbIX CIIJIAMHOB IIEPBOM BbICOTbI
HA IIAPAJIJIEJIbHOM CMCTEME *)
PaCnapaJIJleJII1Bamle BbI~I1CJIeHI1i1: 51BJUleTC.H O.n,HI1M 113 OCHOBHbIX cnOC060B I1X YCKOpeHI151
(CM.
[1, 2]).
TaKoe YCKopeHI1e oc06eHHo mi)KHO npI1 06pa60TKe 60JIblllI1X nOTOKOB
~I1CJIOBOi1:
I1H<popMall,I1I1, nocTynaIOlll,I1x B peaJIbHOM MaclllTa6e BpeMeHI1. 11cnOJIb30BaHI1e MI1HI1MaJIb­
HbIX CnJIai1:HoB Ha nepaBHoMepHoi1: ceTKe n03BOJI5IeT oCYlll,eCTBJI.HTb 3<p<peKTI1BHOe C)KaTI1e
nOTOKOB C 6bICTPO MeH.HIOIIWMI1C.H xapaKTepI1CTI1KaMI1, a pacnapaJIJIeJII1BaHI1e npI1Bo.n,I1T K
6bICTPOMY I1X BOCCTaHOBJIeHI1IO.
IJ,eJIb .n,aHHoi1: pa60TbI -
Oll,eHI1Tb ,n;JII1TeJIbHOCTb BbI~I1CJIeHI1i1: MI1HI1MaJIbHbIX CnJIaHHOB
nepBoi1: BbICOTbI Ha HepaBIIOMepHoi1: ceTKe npI1 pa3JII1~HbIX npe.n,nOJIO)KeI-II151X OTHOCI1TeJIbHO
BhI~I1CJII1TeJIhlloi1: CI1CTeMbI KaK B o,n;HonpOll,eCCOpnoM BapI1aIiTe, TaK 11 B MHOrOnpOll,eccop­
HOM. I10JIy~eHHbIe pe3YJIhTaTbI .HBJI.HIOTC.H pa3BI1TI1eM no,n;xo,n;OB, npe.n,JIO)KeHHbIX B I1CCJIe,n;o­
BaHI1.HX
1.
1.1.
[1-4] .
BbPIHCJIeIlI'Ie MHnHMaJIbIlbIX CIIJIa:nnoB na o.n;noIIpo:u;eccopno:n CHCTeMe.
11 C x o.n, H hI e
n p e,n; n 0 JI O)K e H 11 .H. PaCCMOTpI1M o,n;Honpon;eccopHyIO CI1CTeMY, y,n;o­
BJIeTBOp.HIOlll,YIO yCJIOBI1.HM
(A):
• CI1CTeMa onepI1pyeT C CI1MBOJIaMI1 O.n,I1I-IaKOBOi1: .n,JII1HbI, COCTO.Hlll,I1MI1 113 6YKB KOHe'-IHOrO
aJI<paBI1Ta(MO)KnO CI1MBOJIbI c~wraTb 6I1HapHbIM CJIOBOM, a ynOM.HHYThIH aJI<paBI1T, COCTO51lll,I1M 113 .n,ByX 3JIeMenTOB -
0
11
1);
TaKI1e CI1MBOJIbI 6y.n,eM Ha3bIBaTb cmaUaapm'l-t'btMU; B
.n,aJIbHeilIneM CTaH,n;apTI-IbIe CI1MBOJIbI o603Ha~aIOTC.H 6YKBaMI1 JIaTI1HCKOrO I1JII1 rpe~eCKoro
aJI<paBI1ToB.
• Ka)K,n;oMY BeIlJ,ecTBcHHOMY ~I1CJIy CI1CTeMa conOCTaBJI51eT cTan.n,apTHbIH CI1MBOJI (MO)K­
HO npe.n,CTaBJI.HTb ce6e Mo.n,eJIbHhIH cJIy~ai1:: npe,n;cTaBJleHI1e ~I1ceJI B CI1CTeMe C nJiaBaIOlll,ei1:
TO~KOH).
• B
CI1CTeMe onpe,n;eJIeHa nceB.n,oapI1<pMepI1Ka «<MaIllI1I-IHa51 apI1<pMeTI1Ka»), a I1MeHHO,
6I1lIapHbIe onepall,I1I1 «CJIO)KCHI1.H», «BbI~I1TaI-II1.H», «YMHO)KeHI1.H»
11 «,n;eJIeHI151», onepaH,n;a­
MIl (11 pe3YJIbTaTOM) KOTOPbIX CJIY)KaT CTaH,n;apTHbIe CI1MBOJIbI; CJIe.n,yeT no,n;~epKHyTb, '-ITO
06bI~HbIe rpymloBble (11 TeM 60JIee KOJIbIJ,eBbIe) CBoi1:cTBa He npe.n,nOJIaraIOTC.H (B ynOM.HHy­
TOM MOlI,eJIhHOM CJIy~ae MO)KHO rOBOpI1Tb JII1111h 0 <<npI16JII1)KeHHOH»
peaJII13all,I1I1 06bI~HbIX
apI1<pMeTI1~eCKI1X onepaIJ,UH); TeM He Menee B .n,aJIbHei1:IlleM I1MeHa nepe~UCJIeHHbIX 6I1Hap­
HhIX onepmWi1: ynoTpe6mlIOTC.H 6e3 CK060K, onepaIJ,I1I1 CJIO)KeHI1e 11 BbI~I1TaHI1e Ha3bIBaeM
aaaUmU8U'btMU, a YMHO)KeHI1e 11 .n,eJIeHUe -
MY.l/,bmun.l/,U1WmU8'1-t'btMU.
• Cpe.n,I1 CTaU,II,apTI-lbIX CUMBOJIOB I1MeeTC.H TOT, KOTOPhIH 6y.n,eM Ha3hIBaTb OCo6'btM 11 060­
31Ia~aTh 6YKBOH
F;
IIpI1 ero IIO.HBJIeUI1U cpe,n;I1 onepaH.n,OB I1JII1 pe3YJIhTaTa CUCTeMa npeKpa­
IIJ,aeT BhI'-II1CJIeI-II1.H (B Mo,n;eJIbHOM CJIy~ae TaKOH: CI1MBOJI II05lBJI5IeTC5I npI1 BhIxo,n;e 3a f1.I1a­
IIa30I-I npe.n,cTaBI1MOCTI1 BenJ,eCTBeHI-IhIX ~I1ceJI, KOTOPbIH B pa3HhIX CI1CTeMaX MO)KeT 6bITh
pa3JII1~HhIM) .
• 11MeIOTC.H YHapHhle onepall,I1I1 pa60Thi C IIaM.HTbIO, a UMeHHO onepaIJ,I1I1 3aIII1CU U ~Te­
HI1.H CTan.n,apTHoro CI1MBOJIa, ,n;JII1TeJIhHOCTb KOTOPbIX o,n;unaKOBa H palma O:ca; Ha BbIXO.n,e
.) Pa60Ta BbIllOJIHCHa rrpll <pllHaHCOBOH nOMCp)KKC POCCllHCKoro <pOH.n;a <PYH.n;aMCHTaJIbHbIX llCCJIe.n;OBa­
HllH (rpaHTbI
Ng 04-01-00692
© lO. K. ,lI,CMb5!HOBll'I,
'32
M .
04-01-00026.)
A. MapTIOIIIoB, 2006
II
yaapHoH OnepaIl,MM nO.HBJUleTC.H 3anMCbIBaeMbIH ('fMTaeMblH) CMMBOJI BO BCeX CJIY'fMX, KO­
:.:la 3anMCb ('fTeHMe) B03MO)KHO, MJIM OC06blH CMMBOJI
F , KOr,n;a 3TO
ec..TII OTCYTCTByeT CB060,1J;HM naM.HTb HJIM nocTynMJI CMMBOJI
• 11MeIOTC.H YI-I apHbIe OnepaIl,MM pa60TbI C K3111eM
I
HeB03MO)KHO (HanpMMep,
F).
ypOBI-I.H, a MMeHHO OnepaIl,MM 3anMCH M
"H'eHIDl cTaH,n;apTllOrO CHMBOJIa; ,n;JIMTeJIbHOCTb MX BeCbMa MaJIa M B ,n;aHHOM paccMoTpeHMH
~eTC.H paBHOH HYJIIO; Ha BblXo,n;e YHapHOH OnepaIl,MM nO.HBJI.HeTC.H 3an11CbIBaeMbIH ('fM­
Tae~lhrn) CMMBOJI BO Bcex CJIY'fa.HX, Kor,n;a 3anMCb ('fTeHMe) B03MO)KHO, MJIM OC06bIH CHMBOJI
F
Kor,n;a 3TO neB03MO)KHO (nanpMMep, eCJIM OTCYTCTByeT cB060,n;na.H naM.HTb MJIM nocTynMJI
cm.mOJI
F).
.
• ,n;JIMTeJIbHOCTM aMMT11BnbIX OnepaIl,MH O,1J;MHaKOBbI (ne 3aBMC.HT OT onepan,n;oB) M paBnbI
'UfC-lIy {lad.
• ,n;JIMTeJIbnOCTM MYJIbTMnJIMKaTMBnbIX OnepaIl,MH O,n;MHaKOBbI (ne 3aBMC.HT OT onepan,n;OB)
Z p aBHbI 'fMCJIY
{lmul.
• ,n;mITeJIbHOCTM OnepaIl,MH 3anMCH / 'fTeHM.H B naM.HTb o,n;MnaKOBbI (He 3aBMC.HT OT one­
paHAOB) M paBIlbI 'fMCJIY (lea.
B ,n;aJIbHeHllleM
paCCMOTpMM peaJll13aIl,MIO <PYHKIl,MOllaJIa
Po (X)
,n;JIMTeJIbnOCTM Bbl'fMCJIe­
mill
Po (X) ~f (ladPad(X)
Pad (X), Pmul (X), Pea (X) -
:::Ie
IIIIH
'fMCJIO aMMTMBHbIX, MYJIbTMnJIMKaTMBHbIX OnepaIl,MH M onepa­
'fTeH11.H/3an11CM B naM.HTb
(X -
CJIOBO B aJI<paB11Te
craH,n;apTHblX C11MBOJIOB; CM. TaK)Ke
1.2. B
bI 'f M C JI e H 11 e
+ (lmuIPmul(X) + {lea Pea (X) ,
[3,
c.
323-325]).
K 0 0 P ,n; 11 HaT H bI X
A,
.
COCTO.HlIl,ee 113 ynOM.HHYTbIX BbIlile
M M H M M a JI b H bI X
C n JI a
i1
HOB. 113­
eecrno, 'fTO M11HMMaJIbHbIe CnJIaHHbI nepnOH BbICOTbI BbI'f11CJI.HIOTC.H no <popMYJIe
U(X) = L)VjI ,0Wj',0(x)
+ Vj' ,1Wj',1 (X)).
(1)
j'
3,J.ecb Vj',O M Vj',l - 'f11CJIOBbIe K03<P<PMIl,MeHTbI, a MMH11MaJIbHbIe Koop,n;11HaTHbIe CnJIaHHbI
-: - ,o(x) M Wj',l(X) onpe,n;eJI.HIOTC.H C nOMOlIl,bIO HaTYPaJIbHOrO 'fMCJIa M ~ 2, Il,eJIoro 'f11CJIa l,
- .:\. tf + 1 ~ l ~ -1 11 C nOMOlIl,bIO (6ecKOHe'fHOH B 06e CTOpOHbl) ceTKM
... < X- 2 < X-I < Xo < Xl < X2 < ...
COOTHOllleH11.HM11 supp
Wj,O
= supp Wj,l = [Xj+l, Xj+l+M],
(3)
IT
(4)
j'-:f-j
k-I-M+1~j'~k - 1
~1llI 3<p<peKT11BHOCT11 BbI'f11CJIeI-lMH npe06pa3yeM <P0PMYJIY (2), 11CnOJIb3Y.H TO)K,n;eCTBO
R J' . k(x)
,
= ddx
IT(x - xj'?
j'
= 2Rj ' dx) ~
_1_,
~x-x
P
P
33
r,Il.e B np0l13Be,Il.emUII1 B cyMMe I1H,Il.eKChI np06eraIOT MHO)I(eCTBO Jj ,k
l}\{j}.
~f {k-l-M +1,
... , k­
Tor,Il.a Wj,o(x) npl1MeT y,Il.06HhIll ,Il.JUI BhI'Il1CJIeHl1ll BI1,I1.
(5)
BI1,I1.I10, 'ITO Wj,O (X) 11 Wj,l (X) CO,Il.ep)I(aT 06III,l1ll COMHO)I(I1TeJIh:
(6)
BBe,Il.eM 0603Ha'IeHI1e
n = M - 1.
IIpe,Il.noJIO)I(MM, 'ITO BhITIOJIHeHhI YCJIOBI15l (B):
(2)- (6),
• Y3JIhI, qmrypMpYIOIII,Me B <popMYJIaX
(7)
Xk-l-n, Xk-l-n+l,· .. ,Xk- l, XpaH5lTC5l B naM5lTM BhI'IMCJIMTeJIhHOll CI1CTeMhl.
• BeJm'IMHhI, paCCMaTpl1BaeMhIe B <p0pMYJIaX
BO,Il.5lT K n05lBJIeHMIO CMMBOJIa
(2)- (5),
TaKOBhI, 'ITO BhI'IMCJIeHI15l He npl1­
F.
IIocJIe,Il.oBaTeJIhHO npOM3BO,Il.I1M CJIe.n.yIOIII,l1e onepa1V1l1:
I. BhI'Il1CJIelme X - Xj Tpe6yeT
II. BhI'Il1CJIeHMe pa3HOCTell Xj -
BhITIOJIHI1Th
1
aMMTI1BHYIO onepall,I1IO.
xp 11 X - xp npM
pE
Jk,j Tpe6yeT
2(M - 1)
a,n,n;I1TMBHhLX
onepau,Mll.
III.
BhI'Il1CJIeHMe 'IaCTHhlX
X-Xp
X3 - Xp
npM
p E Jk , j
M - 1
Tpe6yeT
MYJIhTMnJIMKaTMBHhIX
Onepau,l1ll.
IV.
BhI'IMCJIeHHe npOH3Be,Il.eHM5l
rIpE] k , 3,
x ____x p Tpe6yeT
X3
Xp
M - 2 MYJIhTMnJIHKaTHBHhIX one-
paI~l1ii; ,Il.06aBJI5l5l CIO,Il.a eIII,e O,Il.Hy MYJIhTl1nJII1KaTMBHYIO onepau;MIO - B03Be,Il.eHHe B KBa,n;paT
!vI - 1 MYJIhTl1nJII1KaTHBHhIX onepau,Mll.
LpEJ,."j Tpe6yeT M - 2 aMI1TI1BHhIX Onepall,Hll.
ynOM5lHYToro npOH3Be,Il.eHH5l - nOJIY'IaeM
V. BhI'IHCJIelme CyMMhI
VI. ,n;JI5l BhI'IMCJIeHM5l CO,Il.ep)I(MMOrO KBa,n;paTHhlx cKo6oK nOna,Il.06I1TC5l YMHO)I(MTh nOJIy­
'IeHHYIO CyMMy na 2 H ,Il.06aBI1Th 1, TaK 'ITO nOTpe6yeTC5l 1 aMMTI1BHa5l 11 1 MYJIhTHnJIMKa­
TI1BHa5l onepau,HI1.
VII.
Ha OCHOBe nOJIY'IeHUhIX pe3YJIhTaTOB BhI'Il1CJIeHl1e <PYHKll,Mll Wj,O M Wj,l nOTpe6YeT
,Il.onOJIHHTeJIhHO
2
MYJIhTHnJII1KaTMBHhle Onepall,MM.
3M - 3
Teneph BH,11,HO, 'ITO BcerO Tpe6YIOTC5l
OIIepaJ~Mll. Y'II1ThIBa51 paBeucTBo
,Il.JI51 npO'ITeHH51 y3JIOB
(7)
n
=M
- 1
2M + 1 MYJIhTMnJIMKaTMBHhLX
+ 1 oIIepau,l1ll '-ITeHM51/3anI1CM
a,IJ.,II.I1TI1BUhIX,
11 I1CIIOJIh3Y51
n
B K3llJ-naM5lTh, uaXO,Il.I1M
P mu1 = 2n
+ 3,
Pad = 3n + 1,
Pea
= n + 1.
OTCIO,Il.a CJIe.n.yeT
TeopeMa 1.
llpu 6'btnOJI:H.e'HUU YC./I,06UU
(A)
U
(B)
a./l,ume./l,'b'Hocm'b 6'bt"tUC.I£e'HUU MU'HU­
Ma./l,'b'H'btx cn./l,aU'H06 Wj,l U Wj,l eau'Hu"t'HOU 6'btCOm'bt 6 mO"t1Ce
Po(X) ~
1.3.
Qad(3n
B hI '-I H C JI e H H e
Il 11 M ' a JI h H hI X
'34
t
ya06./1,em60pJtem 'Hepa6e'HCm6Y
+ 1) + Qmul(2n + 3) + Qea(n + 1).
JI 11 U e
II
H 0
II
K 0 M 6 H H a l~ M M
K 0 0
P ,II. 11
If aT H hI X
M H­
C n JI a ii II 0 B . .JIl1ueiiHoii KOM6uuau,uell MUHI1MaJIhUhLX Koop.n.uHaTHhLX
(1)
Ol.'laHHOB 5!BJI5!eTC5! cYMMa
If3
n
+ 1 CJIaraeMhIX.
113 (4)
Bl1,n;HO, '-ITO Ha60p y3JIOB, IfC­
Oo.l h3yeMhIx B Ka)K,n;OM CJIaraeMOM, o,n;IfHaKOB (He 3aBIfCl1T OT HOMepa
:IaraeMoro) 11 COBIIa,n;aeT C MHO)KeCTBOM
j
paCCMaTpIfBaeMoro
I
YPOBH5!.
(7).
IIpe,n;noJIO)KIfM, '-ITO BhIllOJIHeHhI YCJIOB115! (C):
• Bce y3JIhI 113BJIeKaIDTC5! If3 naM5!TIf O,n;l1H pa3 If XpaH5!TC5! B K3IIIe
•
j
3Ha'-lCH115! Vj ,O, Vj,l
=
k - 1 - n, . .. , k - I,
Haxo,n;5!TC5! B naM5!Tl1 BhI'-IIfCJIl1TeJIhHOll
cncreMhI.
• Pa3HOCTl1
x - xp
o,n;mI
paCC'-IIfThIBaIDTC5!
pa3 ,n;JI5! Bcex CJIaraeMhIX 11 XPaH5!TC5! B K3IIIe
.H >OBH5!.
IIpIf YCJIOBIf5!X (C) JIerKO nOJIY'-IaeM, '-ITO
1)
2)
3)
KOJIl1'-1eCTBO pa3HOCTell Bl1,n;a
x - xp ,
xp
KOJIlf'-leCTBO pa3HocTell BIf,n;a Xq -
He06xo,ll;l1MhIX ,n;JI5! BhI'-IIfCJIeUl1ll, paBHo
paBHo
n
+ 1;
n 2;
He C'-IIfTa5! BhIIIIena3BaHHhIX, B Ka)K,n;Oll KBa,n;p a THOll cK06Ke
(5)
n
l1MeeTC.H eIIIe
CJIO­
~eUl'fJ1;
4)
KOJIIf'-leCTBO CJIO)KefIlfll B <p0pMYJIe
Pad
TaKl1M 06Pa30M,
=
(n
+ 2)2.
(1)
paBHo
2n + 1.
KpOMe Toro, 6hIJIO nOKa3aHO , '-ITO ,n;JI5! BhIQIfCJIeHIf5!
2n + 3 MYJIhTIfnJIl1KaTl1BHhIe Onepa IIl1If, l1JIl1 C Y'-IeTOM YMHO)KCHIf5!
2n + 5 YMHO)KefIlfii, a nOCKOJIhKY Bce ro nap n + 1,
MYJlbTl1llJIlfKaTIfBHhIX onepal~Ifii paBHo (n + 1)(2n + 5). l'haK, Pmul =
nap bI Wj,O, Wj ,l Tpe6yeTC5!
Ha K03<P<PIfIIIfeHThI Vj,O, Vj ,l nOJIY'-Iae TC5!
ro
06IIIee '-IIfCJIO
+ 1)(2n + 5).
HaKoII el~, KOJIl1'-1eCTBO '-ITeHl1llIf3 naM.HTl1 B COOTBeTCTBIfIf C YCJIOBl15!Ml1 (C) paBHO
n60
T pe6YeTc5!
(n
+ 1)
'-ITeHl1ii ,n;JI5! If3BJIe '-leHIf5! Y3JIOB If
li iOBJleQelU15! K03<P<P11-III1eHToB), TaK '-ITO
2(n
Pea = 3(n + 1).
+ 1)
3(n+l)
'-ITeUl1M If3 naM5!T If ,n;JI5!
O T cro,n;a CJIe,n;y eT
(A), (B), (C) o,//,ume,//,bHocmb 8wtUc,//,eHUU '//'u­
(1) 8 mo"t'X:e t cMeMeHmapH020 UHmep8a,//,a cem'X:u o~eHU6aernCJl, Hepa­
Po(X) :::; Qad(n + 2)2 + Qmul(n + 1)(2n + 5) + Qea3(n + 1) .
TeopcMa
2.
IJpu 8'btnO,//,'HeHUU YC,//,08UU
.eiiH.OU1WM6uHa~uu
8eH Cm80M
2.
BbPIHCJICHHe MHHHMaJIbHbIX CI1JIaMHOB I1CPBOM BbICOTbI C HCI10JIb30BaHHeM
n apaJIJIeJIbHOM CHCTeMbI.
2.1.
IT p e ,n; n 0 JI O)K e H 1151
3 H a '-I e H If 51. By,n;eM C'-IIfTaTh,'-ITO BhIIIOJUIeHhI YCJIOBIf5!
• CHcTeMa IfMeeT
J())KeHIf5!M
(A), (B),
n
If
He 0 6 X o,n; If M hI e
060­
(D):
+ 1 napaJIJIeJIhHhlX npoIIeccopoB, KOTophIe y,n;oBJIeTBOp5!IDT npe,n;no­
(C) .
• CIfcTeMa pa60TaeT CI-iHXPOHHO, 11 Ha Ka)K,n;OM TaKTe ee npOIIeccophI MoryT napaJIJIeJIh­
:HO o Cylu;eCT BJI5!Th JI1160 aMI1'.r11BHble , JI1160 MYJlhTIfnJIIfKaTIfBllhIe onepaIIlIlf, JI1160 OnepaIIl1l1
"'IT€H H5! / 3anHcIf.
• LIIfCJIO TaKT OB ,n;JI51 OCYIIIeCTBJIeHIf5! aMIfTIfBHhIX onepaIIIfii He 3aBIfCl1T OT onepaH,n;OB
pamIO
f3ad ·
• LIIfCJIO TaKTOB ,n;JI5! OCYIIIeCTBJIeHIf5! MYJIhTl1nJIIfKaTIfBHhIX OnepalIlfH TaK)Ke He 3aBIfCIfT
_ o nepaH,n;OB If paBHO
f3mul .
• LIIfCJIO TaKTOB ,n;JI5! OCYIIIeCTBJIeHIf5! OnepaIIl1M '-ITeUIf5!/3anl1Cl1 He 3aBl1CIfT OT onepau,n;a
P aEUO
•
f3ca .
TIm CB5!3eii Me)K,n;y
npOl~eccopaMIf - 6YJleBCK11ii rl1nepKy6 (~K~,ll;hIM C Ka)K,n;hIM»),
..:LUI nepe,n;a'-lIf MaCCIfBa 113 K3Il1a o,n;Horo npOIIeCCopa B K3Il1 ,n;pyroro Tpe6yeTC5!
f3tr
TaKTOB,
Ta.KIfe nepe,n;a'-lIf MoryT npOBo,n;IfTbC5! napaJIJIeJIhUO.
3a.Me"taHue
1.
ITocJIe,n;nee npe,n;nOJIO)KeHHe BeChMa Tpy,n;no BbIllOJInIfTh npH 60JIhIllOM
"m e .n e npoIIeccopoB , no MlflUIMaJIhHhle CllJlaHnbI 06bl'-lHO YIIOTpe6JI51IDTC5! ,n;JI5! MaJIhIX
~ ~e Bcero He npeBocxo,n;HT
n
(ono
10).
35
2.2. Pac nap a JI JI
e JI H D a
B bI ~ H C JI e H H H
H Hen p H
M H H H M a JI b H 0 r 0
K 0­
o P,lI, H HaT H 0 r o c n JI a Ii H a. llpe,n.noJIo)KHM, ~TO BbI~HCJIeHH51 npOHCXO,lI,51T B CJIe,n,yIO­
I1I,eli nOCJIe,lI,OBaTeJIbHOCTH:
I
mar: Bce npOIIeccopbI C~HTbIBaIOT Y3JIbI B K3m
I
YPODll5l - ,lI,JI51 3TOro nOTpe6yeTC51
fJea
TaKTOB;
mar: ~HCJIa
II
x
H Xj,
COrJIaCHO npe,lI,nOJIO)KeHHIO
III
j = k - 1 - n, ... , k - I,
(D),
I-Ia 3TO nOTpe6yeTC51
mar: COCTaBJI51IOTC51 Pa3HOCTH
x - xp
paCCbIJIaIOTC51 no BceM npoIIeccopaM ;
fJtr
TaKTOB;
BO Bcex npolleccopax; Ha 3TO nOTpe6yeTC51
fJad
TaKTOB;
IV
mar: COCTaBJI51IOTC51 Pa3HOCTH Xj -
xp
BO Bcex npolleccopax; Ha 3TO npH,lI,eTC51 HCnOJIb­
30BaTb fJnd TaKToB;
V mar: COCTaBJI51IOTC51 (:.-~
_:p )2; Ha 3TO nOTpe6yeTC51 2fJmul TaKTOB;
J
p
VI mar: COCTaBJI51eTC51 npOH3Be,lI,eHHe BH,lI,a (6) no aJIrOpHTMy C,lI,DaHBaHH51;
y~eToM Heo6xo,lI.HMbIX nepeCbIJIOK) nOTpe6yeTC51
(fJmul
+ ,Btr ) [log2 n ]
Ha 3TO (c
TaKTOB;
VII mar: COCTaBJI51IOTC51 BbIpa)KeHH51 Xx-=-xXpP ; ,lI,JI51 3Toro HY)KHO ,Bmul TaKTOB;
J
VIII mar: COCTaBJI51eTC51 cyMMa H3 (5) no aJIrOpHTMy C,lI,BaHBaHH51; Ha 3TO nOTpe6YeTC51
(,Bad + ,Btr) [log2n] TaKTOB;
IX mar: 06Pa3YIOTC51 OKOH~aTeJIbHbI€ 3Ha~eHH51 Wj,O, Wj,I; Ha 3TO Tpe6yeTc51 ,Bad + ,Bmul
TaKTOD;
X
mar: npOH3BO,lI.HTC51 3anOMHuaHHe pe3YJIbTaTOB 3a
,Bca
TaKTOB.
OTCIO,lI,a BbITeKaeT CJIe,n,yIOlllee YTDep)K,lI,eHHe.
TeopeMa 3. llpu 6'btnO.lt'He'HUU YC.lt06UU (D) a.ltJ/, (n + l)-npov,.eccop'HoU cucmeM'bt a.lt1j­
me.lt'b'Hocm'b PI napa.lt.lte.lt'b'H'btx 6w/,uC.lte'Huu cn.ltaU'H06 (2), (3) 6 mo"t'X:e t :').fteMe'Hmap'H020
U'Hmep6a.lta cem'X:u ya06.1tem6opJ/,em 'Hepa6e'HCm6Y
PI :::; 3,Bca + ,Btr + 2,Bad + 5,Bmul + (,Bad + ,Bmul + 2,Btr )[log2 n].
2.3.
Pac nap a JI JI e JI H BaH Hen p H
H a II H H
K 0 0 P,lI, H HaT H bI X
BaHH51 npH BbI~HCJIeHHH BbIpaJKeHH51
,n.oro
j
B bI ~ H C JI e H H H
M H H H M a JI b H bI X
(1)
JI H H e Ii H 0 Ii
K 0 M 6 H­
C n JI a Ii HOB. CxeMa pacnapaJIJIeJIH­
MO)KeT COCT051Tb B CJIe,n,yIOllleM: CHa~aJIa ,lI,JI51 KaJK­
= k -1- n, . .. ,k -I npOBO,lI,51TC51 marH I-X, a 3aTeM K HHM ,n.06aBJI51IOTC51 CJIe,n,yIOI1.V'fe
marH:
XI mar. C~HTbIBaHHe 3Ha~eHHIi Wj,O, Wj,l H Vj,O, Vj,l H3 naM51TH; ,lI,JI51 3Toro nOTpe6YeTC51
4,Bca TaKTOB.
XII mar. llepeMHo)KeHHe ynOM51HYTbIX 3Ha~eHHIi - nOTpe6yeTC51 2,Bmul TaKTOB.
XIII mar. CJIO)KeHHe TOJIbKO ~TO nOJIy~eHHbIX pe3YJIbTaTOB no cxeMe C,lI,BaHBaHH51; ,l1,JI5l
;n oro nOTpe6yeTC51 (,Bad + ,Btr)[log2(2n + 2)] TaKTOD.
XIV mar. 3aCbIJIKa nOJIy~eHHoro pe3YJIbTaTa D naM51Tb; 3TO nOTpe6yeT ,Bca TaKTOB.
OKOH~aTeJIbHO C y~eToM pe3YJIbTaTOB n. 2.3 npHxo,n.HM K TaKOMY YTBep)K,n;eHHIO:
TeopeMa 4. llpu 6'btnO.lt'He'H,UU YC.lt06UU (D) a.ltJ/, (m
+
l)-npov,.eccop'HoU CUCmeM'bt a.ltu­
me.lt'b'Hocm'b P2 a.ltJ/, napa.lt.lte.lt'b'H'btX 6WtUC.lte'Huu .ltu'Heu'Hou 'X:oM6u'Hav,.uu (1) no cxeMe I-XIV
UMeem ov,.e'H'X:y
P2
:::;
(n + 1){3,Bca + ,Btr + 2,Bad + 5,Bmul + (,Bad + ,Bmul +
2,Btr)[log2
+ 4,Bca + ,Bmul + (,Bad + ,Btr)([log2(n + 1)] + 1).
36
n]}
+
Summary
Demjanovich Yu. K., Martushov M. A. On calculation duration of the first height minimal
splines for a parallel computer system.
Evaluations of calculation duration of the first height minimal splines in the case of an irregular
net are discussed. They are discovered under different suppositions as to parallel computer system.
JIHTepaTypa
1. BOe60aU'H. B. B ., BOe60aU'H. 1M. B. IIapaJIJIeJIbHble BbI'll1CJIemUI. CII6.: 113,n;-Bo BXB­
IIeTep6ypr, 2002 . 608 c .
2. KOp'H.ee6 B. B. IIapaJIJIeJThHble BbI'lHCJlliTeJIbHble CHCTeMbI. M.: HOJIH,l1;:>K, 1999. 320 c.
3. AeM/bJl,'H.06U'4, 10. K . J10KaJIbHruI aImPOKCHMa,wi.a Ha MHOroo6pa3HH H MHlIHMaJIbHble cIIJIaifI!bI.
CII6.: lb,n;-Bo C .-IIeTep6. Yll-Ta, 1994. 356 c.
4. BYPo6a H. r., AeMibJl,'H.06U'4, 10. K. 0 AJlliTeJIbHOCTH BbI'll1CJIemlli MHHHMaJIbHbIX CIIJIamlOB
IIpH paCIIapaJIJIeJIHBaHHH / / BecTH. C .-IIeTep6. YH-Ta. Cep. 1: MaTeMaTHKa, MeXaHHKa, aCTpOHOMH.a.
2003. C. 13-19.
CTaTb.H nocTymwa B pep;aK~HIO 6 MapTa 2006 r.
'
Документ
Категория
Без категории
Просмотров
4
Размер файла
2 823 Кб
Теги
сплайнов, вычисления, длительность, система, первое, параллельное, высота, минимальное
1/--страниц
Пожаловаться на содержимое документа