An Integrated Simdization Framework using Virtual Vectors

An Integrated Simdization Framework
Using Virtual Vectors
Peng Wu
Alexandre E. Eichenberger
IBM T.J. Watson Research Center
Yorktown Heights, NY, USA
Amy Wang
IBM Toronto Laboratory
Markham, Ontario, Canada
"!$#
ABSTRACT
-/.01$24350687:9682<;*6>=350681
?A@B1
C 2D.E80682<F;*63GFH'0F?9681$?9 @3I7F9G9FJ'K
FLC35E(?FMN7PO35E8E8F?Q$F9R0O,3I0S3ICFT?1$0VU*CF9F?'0V68?40C35;*6>0681$?,35E(JFL7K
01$C68='350681
?WYX1$2<FZ1$@[0O*FZ?*FM\6899.*F9]35CFZ;.*F^01_0OF42<1$CF
CFL90C6>7L06>J
F4X`acbd3IC7PO*6>0FL70.CF9R;*F968Q
?*F;Z@B1
CR2D.E80682<F;*63eFH'K
0FL?9681
?*9Wf-V2<1$?Qg0O*F2h3ICF]35E868Q
?*2<F?'0i71
?*90C3568?'09jkE3I7Pl]1$@
2TF2<1
CmRQ350O*FCG35?*;e97'3500FCn9.UUo1$C0j'35?;e0O*F9O*1
C0 3I?;epH'F;*K
E8F?*Q
0Oe?,3I0.CF(1
@nX`acbAJF701$C9WkX68?*7F(0OF9Fq71
?*90C3568?'09 3IroF70
91$2<FRJFCmSs359687R71$2<Uo1
?*F?'09t1$@G3tU*C1
Q$C3524ju3t71$2<U68E8FCG2[.*90
?*1
0(1
?*E8mDU*C1J68;*Fv91
E868;<91
E8.*06>1$?9q01:68?;*6>J'68;.35E'6899.F9js.0 35E891
03IlFw35?x6>?'0FQ$C350F;_3IUU*C1o3575OA0143I;;*CF99/0O*F9FR71$?90C3568?'09t6>?
7L1
2Ds68?,3I06>1$?,W
`y?g0O*6>9DU,3IUoFCjzMFiUC1
Uo1$9FZ3[9682<;68='3I06>1$?]@{C352TFMk1$Clg0O,3I0
3I;;*CF99F9 9FJFLC35E|1
C0O*1
Q
1$?,3IEv3I9UoF709 1
@z9682<;68='3I0681
?,j'9.75OZ359
3IE86>Q$?2<FL?0TO,35?*;E868?Qjn96>2T;68='350681$?}1$@/E811
U*9TM 680O]2<68H'F;];,3503
E8F?*Q
0O*9j35?*;~X`acb4U,3IC35E8E8FE86>92FH'0C3I70681
?D@{C1
2€;68roFCF?'0U*C1
K
Q$C352971
UoFL9c‚{@{C1$2ƒs359687wsE817Pl'9D01c68??FLC[E811
U*9„WA… OFi?1J'K
FLE>0ym~1$@,0O689G@{C3I2<FMk1$Clx689G6809<3Is68E86>0ym~01T@357L6>E8680350FD68?'0FC3570681$?9
soFL0MkFLF?†;68roFCF?'0D0F75O?68‡'.FL9Ds359F;]1$?†0OFS9682<UE8Fw68?0FLC2<FK
;*6y350FTCFLUCF9F?'03I06>1$?41
@qJ68C0.35EJFL701
C9W[aTF'359.*CF2<F?'09V1$?}3
ˆqˆq‰ Š
‹5Œ M 680O43<aTŽX`acbZ.*?680(6>?*;687'3I0F 9UoFF;.*UT@"35701$C91$@
.*Uc01Z
W8‘
‘R@{1$C:?'.2<FC687'3IEy’5J'68;F1’571$2<2[.*?687'3I06>1$?glFLC?FE89T35?;
9UoFLF;.*U“@3I701
C9[1
@ .UZ01_”
W8‘
•T@B1
CDsoF?75O2c35Cl'9juM OFL?–35.*01
K
2c350687e96>2T;68='350681$?c6>9G0.*C?F;~1
?,W
1.
$%&
'()*'+''!
,
"!$#
71$2<U68E8FC9e9068E>E(O3J
FT;68§<7L.E8068F9R68?ZQ$F?FC3I068?QxFL§<768F?'0R71;FL9
@{1$C<X`acb}.*?6809j;F9U*6>0FR7L1
?968;*FC35s*E>FeFH'UoFC0689FR68?x7L1
2<U*6>E868?Q
@{1$CGJF701$C 9.UoFC71$2<U.*0FC9Wn`?w0O689 U35UoFCjMkF:CFL@{FCG01cX`acb
JF7L01
C68='350681$?_359e¨©«ª“¬©«­®*¯©«°±(W
… OF/.?*;FCE8m'68?QDCF'3591$?9D35CFV0Mk1[@{1$E>;*F;,W ²k?w0OF/1
?*FVO,3I?;j
243I?mc6899.*F9R@3I7F;^sm_3I.01$24350687<FH'U*E>1$680350681
?Z1
@VX`acb–U,3ICK
35E8E8FE8689235CF/7'35.*9F;~s'm<0O*F/?*FM‚{91$2<F0682<F9 2<1$CFVCF90C687068JF„
O,3IC;M:35CFR@{F350.CFL9/68?A01;3mu³ 9[X`acbš35C75O680F70.*CF9W
´
aT1
90iX`acb¥.?6809j9.75O}359:<aTŽµ35?; ‰ q n vjo1$?E8m_357LK
7F99(7PO'.*?l'91
@,¶5·
¸¹«º¼»½'·½'¾u2<FL2<1
Cme0O,3I0t35CFD¿ÀÁº{»¸ÂIÃR350t3
2[.*E>068U*E>FV1
@n0O*FVJFL701
CvCFLQ
6890FCGE8F?Q$0O,Wn… OFV71
?*90C3568?'09
1
?<2<FL2<1
Cmx35E868Q
?*2<F?'0:3I?;[71
?'068Q
.*6>0ym[CFL9.E8068?[96>2TUE8FCj
@3590FLCq2TF2<1
Cme1$UoFC350681
?*9:3I9(;,3503(;1/?1
0,9U35?[2[.*E>068U*E>F
7'3575OFRE868?F9T35?*;xCF‡'.*6>CFR?*1<O,3IC;M:35CFR9O'.Ä<68?*Q<?F0yMk1$Cl
soF0MFF?›0O*Fc2<F2<1$Cmš3I?;X`acbd.*?6809W–`y?›71$?0C3I90j
JF701$C[243I7PO*68?F9[9.75O–359 ‰ C3mg… Š5Œ 7'35?]E81o3I;]2<F2<1$Cm
JF701$C9/.*96>?*QZ3RJ
F701
Ct1
@(C3I?;1$2Å3I;;*CF99F9VCFLQo35C;*E8F99
1
@q2<F2<1$Cm]35E868Q
?*2<F?'0Wt`y?90F'3I;,j*0O*F[s*.C;FL?c01wQ350O*FCj
97'3500FCj'1
CGCFKP35E868Q
?x;,3503t6>9G9O*6>@B0F;A01<0O*F:91
@B0M:35CF'W
´
X`acbc.?*6809n1
@B0F?TUoFLC@{1
C2N1
UoFC3I0681
?9,1$?[J
F701
C9n1
@J3ICK
6>1$.9S;3503wFLE>FL2<F?'0<E8F?Q$0O9W]Æ1
C<FLHn3I2<UE8F'j(SaTŽÇ9.U*K
Uo1
C09eJF701$Ce1
UoFC3I06>1$?9[1
?“Èc68?'0’5É*1o350jk[9O1$C0ju1
Cx‘
•
7PO35Cq;,3503kU3575lF;<68?'01w3k968?Q$E>FT‘
•IK)sm'0F JFL701
CWv²k?*FG6>2TK
UE8687'350681
?c1$@,0OF:U3575lF;~CFUCF9FL?03I0681
?c01<0O*FR71
2<U*68E>FLC
6>9R0O350:0O*F[?'.*2[soFCV1
@kJ
F701
C9V6>?'J1$E8JF;468?›3e71
2<U*.03IK
06>1$?A75O,35?*Q
F9G;*.C68?Q<;3503/7L1
?'JFC9681
?*9G1
@,;68roFCFL?0 ;3503
E>FL?Q
0O*9WwÆ1$C[FLHn3I2<UE8F'jz;.C68?*Q_3T71
?'JFC9681$?“@{C1$2Ê3c‘IK
sm'0F475O,35C~01N”5K)s'm0Fc9O*1
C0j[3cU3575lF;¥JFL701
C~1
@e9O1$C0
9O1
.*E8;AFH'U,3I?;w6>?'01<0yMk1<J
F701
C9G1$@68?0W
INTRODUCTION
a 1$90S2<1;FLC?_2T6>7LC1
UC17LF991
C9wO,3"JFg35;*1
U0FL;_2D.E80682<F;*6y3
T
FLH0FL?9681
?*901<3I7PO*68FJFqO68Q
O*FCnUoFC@B1
C243I?7Fk1
?e68?7CF'3I968?Q
E8me682<K
Uo1$C035?'0V2D.E80682<F;*6y3eM1
Cl'E81o35;*9W<bF9U*680F[0O*FDJ35C68F0ymA1
@(2D.E8K
0682<FL;6y3:FH'0F?9681
?*9/1$?c0OFR243IClF0ju350t0OFe71
CFj*0OF9FeFH'0F?*K
9681$?9i7'35?fsoFA7PO35C3I70FC68=F;3I9c—68?Q$E>F†˜y?90C.*70681
?š™›.*E806>U*E8F
œ 3503[‚X`acbV„z.?*6809v1
UoFC3I068?QT1$?~;*F?9FLE>m'K)U,3I7Pl
F;,j$9O*1
C0 JFL7K
01$C9WvHu352TUE8F9V1$@(9.75Oc9m90FL2<9<3ICF[<aTŽ@{1$C ˆ 1MkFC ˆq‰€ž ‘IŸj
X*X}@{1
C ˆ F?'068.2 ž ”IŸyjn35?*;A0OF ‰  u “UC17FL991
C ž>¡ ŸyW
¢ O68E8FiX`acb_.?*6809e35CF:soFL71
2<68?*QT.s*68‡.*6801
.9j
0O*F68Cv682<U,3I70
1$?~2c3568?90CF'3I2£U*C1
Q
C3I2¤UoFC@B1
C243I?7F/6>9k906>E8E|.?*;FC0OF68C@{.E8E
Uo1$0F?'06y35EyW ˆ C1$Q
C352T2<68?Q†X`acb¥.?*6>09VsmxO,35?*;46>9Vso1
0O40682<F
7L1
?9.*2<68?Q›35?;]FCC1$CSUC1$?F'Wg`y?_0O*F~2TF'35?'0682<F'j(1
U0682<68=68?*Q
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
ICS’05, June 20-22, Boston, MA, USA.
Copyright 2005 ACM 1-59593-167-8/06/2005 ... ¦ 5.00.
Peng Zhao
´†Ë F7'3I.9FZX`acbN.?*6>09w3ICFS68?“Q
F?*FC35E2<1
CFS7L1
?90C3I68?F;
0O,35?]0O*F~97'3IEy35CS.?*6809c3"J3I68E3IsE8Fx1$?]0OFw9352<F~243575O68?F
35?;soF735.9F}1
@~0OF_9O1
C0Z?,3I0.CFf1$@“X`acbYJF701$C9j
0OF468?0FLC3570681
?¥soFL0MkFLF?¥9682<;68='3I06>1$?¤3I?;›1$0OFC~71
2TK
U68E8FCR1
U*06>2T6>=350681
?*9DO359R968Q
?*68p7'3I?0R682<U3570V01x9682<;68='3IK
06>1$?<UoFC@B1
C243I?7F'WG²k?*Fv9.75O<FHu352TUE8F 6890O*F 6>?'0FC3I70681
?
soF0MFF?¥9682<;68='3I0681
?d35?*;›FH'UE81
68068?Q†68?*90C.70681
?¥E8FJ
FE
U,35C3IE8E>FLE>68924W ¢ 680O1$.0qFH'0C3v7'35CF'j
0O*F/7L1
2<U*6>E8FC7'35?iF'3I9K
6>E8m~96>2T;68=F~3VE811
U4M O68E8FA3I70.,3IE8E>m~;FQ$C35;35068?Qi0OFRUoFLCK
@{1
C2c35?7LF'W
²k?_0OFx1$0OFCSO35?*;,jq0O*F†3IUUE8687'3I06>1$?9i035CQ$F0F;}smÌX`acb
.?*6809T3ICFe1
@{0FL?c2<1
CFe71$2<UE8FH~0O,35?x0O1
9FR03ICQ
F0FL;csmw0C35;*68K
0681
?35E|JF701$C 243575O68?*F9Wn… OF:?*FMÍ35U*UE8687'350681$?x;1$243568?~sC68?Q$9
0OFV71
2<U*68E>FLC/so1$0Ox75O,35E8E8F?*Q
F9T35?*;A1
U*Uo1
C0.?*6806>FL9W
´
O68E8FE81$?QtC.??*68?Q E811
U*9G35CF0OF(UC68243ICm:91
.*C7Fk1$@*0C3IK
;680681
?,3IE(JF701$C:U,3IC35E8E8FE86>92cjz0OF[9O1$C0:?,3I0.CFD1
@RX`acb
¢
Î#Ï&€&kÐ)Ñ,^!
#
$ÒÐ)Ñ,Ó
Ò'#ϤÔ5ÕÖÓ^$×Ø*Ù
'&*uÓ^Ú
ÚÛ_
&N
NÕfÖÓ
Ò'#ÏÜÔÝ
ÕÖnÓAÝ×*ÞßnÓAÝ
ÚÚÛ
NÚՖ'&м%'ÚÝ
ÑNàf!
#$ÒÐ)Ý
Ñ,Ó
#&$'&kÐyѥՖ$kÓ
E811
U*9j01T1$UoFC350FR2T1
CFRF'3I96>E8mwsoF7'3I.9FR0OFLm^35CFR@{CFLFR1
@243I?'m
35C75O680F7L0.C35Eo7L1
?90C3I68?09k1
@ X`acb“.?*6809WnV68C0.,3IEJF701$C9e35CF
0OFL?†Q
C35;*.,3IE>E8m†;*FJ'6>C0.35E868=F;]01cUO'm'9687'35EkJF701$C9TM OFLCF†357LK
0.,3IEz35C75O680F70.*CFk71$?90C3I6>?'09j9.75O~359,2<F2T1
Cmw35E868Q
?*2<F?'0G3I?;
UO'm'9687'35EzJF7L01
C E8F?Q$0O]35?*;x1$UoFC350681
?*9j35CFRO35?*;E8F;,W
Ë 3I9F;<1
?T0O689(@{C352TFMk1$Clnj
MF UC1$Uo1
9F @{1$.Cq0F75O?68‡'.FL9,0O,350
ñ 1$68?0E8mwFH'FC7689Fe2435?'mZ‚{1
C0O*1
Q$1
?,3IEy„t3I9UoF709t1
@9682<;*68='350681
?ú
´
96>2T;68='350681$?N1$@DE811$U9AM 680O–s,3I96>7LKðs*E817Pl3I?;–E811
U*KðE8FJ
FE
U,35C3IE8E>FLE>68924j
´
96>2T;68='350681$?c1
@E811
U*9/M 680OA;3503/7L1
?'JFC9681
?j
´
96>2T;68='350681$?“3I7C1
99 E811
Uw?FL909R‚{M 680Oi9O1
C0k6>?*?FCK)E811
U*9„j
´
96>2T;68='350681$?SCF9.E8068?Q:68?<2T6>H'F;T97'35Ey35CV35?*;cX`acbg71;*F9W
á ©«âãäåcæç<聯Pézê©«ë®*ì á ˜Líîì«°|°êï
JF7L01
C9qQ
CF'3I0E>m[68?7CF'3I9F9k6809V35U*UE8687'35s*6>E8680mT@{1
Cq9O1$C0j$.?*K
90C.7L0.CF;c71$2<U.*0350681
?*9WG`y?c2435?'m~2[.*E>0682<FL;6y3e7L1;F9j
X`acb^U35C35E8E8FE86892243"mRsoFk@B1
.?*;[68?D71
2TU.03I0681
?TM 680O*6>?
3<s,3I96>7LKðs*E817Pluj68?€3I?†68??FLC2<1
90[E>11$Uš‚{91$2<F0682<F9TM 6>0O
JFCm^9O1$C0T0C68U†71$.?'0„jn1
CDFJF?†68?Ì3I?†6>?*?FC2T1
90TE811$U
?FL90WZ… O689SUCFL9F?'09T0OFw71$2<U68E8FCS0OFw1
U*Uo1
C0.*?680m“01
ñ 1$68?0E8meFH'0C357L0GX`acb^U,3IC35E8E8FE86892@{C1
2€J3IC6>1$.9,U*C1
Q
C3I2
971$UoF9W
O*6>E8FSE811
U*9eM 6>0Og.?68@B1
C2ò;3503[0ymUoFA35CFS;*1
2<68?,3I?'0R6>?
0C35;*6806>1$?,3IE JF701$C[U35C35E8E8FE868924jq0O*Fi0m'UoFS2<68H“@{1$.?*;†6>?
2D.E80682<F;6y3¥3IUUE8687'3I06>1$?9Z6>94FH'0CF2TFE8mNC6875OÇ35?;€;,3503
71$?J
FC9681
?9Z3ICFc@{CF‡'.FL?0WfÆ1
CiFHu352<U*E8F'j;,3I03“35CFc1$@{K
0F?]901
CFL;€3I94‘5K)s'm'0Fi7PO35Cc3I?;]1
UoFLC350F;_1
?N359c”5K)s'm0F
9O1$C0W ¢ 680O1$.0VFLH0C3R7'3ICF'j|1$?FD243"mcF'35968E8m4.068E868=FT0O*F
@{.*E8E71$2<U.*0350681
?Ss35?;*M 68;0O<1$@o0OF 243I7PO*6>?*F'jÂó{»ó¼j71$2<K
U.*068?Qfw9O1$C09^350^3i06>2TF'jqM O*6>E8FcM:359068?QZO,35E8@:1$@V0O*F
2<F2T1
Cm]s,3I?;M 68;*0O,jVÂó{»ó¼jsm†901$C68?Qg1$?E8mNw75O,3IC9g3I0
3<0682<F'Wx… O'.9jG3T71$2<U68E8FCT2D.90DsoFg35sE8Fi014F§<768F?'0E8m
O,3I?;*E>FT2<68HFL;Z;3503D0ym'UoF9:68?¥3eE>11$U“01x2c35H'682<68=F<so1
0O
71$2<U.*0350681
?]3I?;~2<F2<1$Cm~s35?;*M 68;0Ox1$@tX`acb}.?*6>09W
´ ¢
¢ O68E8F 9FJFC3IECF7FL?0(CF9F35C75OF9 ž Èojô$j•
j ‹ Ÿ*O3"JF @{17.*9F;S1
?
3I;;*CF9968?Q“68?;*68J68;*.,35E 9682<;*68='350681
?f6>99.*F9S2<F?'0681
?*F;€35so1JF'j
MF†3IE>91^1
s*9FCJFw0O,3I0T0OFw71$2<UE8FH'680mZ1
@t96>2T;68='[email protected]
0O*FCS71$2<Uo1
.*?;FL;}s'm†0OFx@357L0w0O350S0O*F9FA6899.F9i@BCF‡'.F?'0E8m
17L7.C]3IE8Ew350A1$?7F^68?ÌCF35ERUC1$Q
C3I2<9W ‰ 1
?*96>;*FCjt@B1
CAFLHn3I2<K
U*E8F'j0OFVÆ,68?*6>0FV`2<U*.E89F<õ,F9Uo1$?9Fi‚{Æ,`õ/„|71
2<U*.03I06>1$?x9O*1M ?
68?ZÆ,6>Q$.CF4‘$WD… O*6>9R7L1;FöGFH'O*6>s*6809:9FJFC3IE9682<;*68='350681
?g6>99.*F9
MF/2TF?'06>1$?F;j
9.75O^3592<68935E868Q
?FL;“3I77F99F9j;3503v71
?'JFLC96>1$?,j
3I?;]X`acb}U35C3IE>E8FE86892÷357C1$99/?*F90F;xE811$U9W
`y?g0O*6>9DU,3IUoFCjzMFiUC1
Uo1$9FZ3[9682<;68='3I06>1$?]@{C352TFMk1$Clg0O,3I0
68?'0FQ$C350F9<;*68roFCF?'0~359UoF709T1
@G9682<;68='3I06>1$?N35?;†FL?,35s*E8F9T0O*F
68?'0FC1$UoFC35s*6>E8680md3I2<1
?*Q}0O*F24WY²k?F^lFmfCF9.E80A689A0O350xMF
735?_?1M‚ ñ 1$6>?'0E8mu„/FH'0C357L0cX`acbÍU35C35E8E8FE86892ø@{C1$2Å2[.*E806>U*E8F
U*C1
Q$C352î971
UoFL9TùAs359687K)sE8175lnjn68?*?FC2<1$90eE>11$U9j 3I?;“68??*FCK
2T1
90GE811
UA?*F909 ùT.*96>?*QT@B1
CGF'3575Ox97L1
UoFw3t;*68roFCF?'0 0F75O?68‡'.F
0O350v689 soF90k9.680F;w@{1
C 6809v68?*;68J'6>;*.,3IEo7PO35E8E8F?Q$F9W(`y?Z35;;*6806>1$?,j
0O*FiFH'0C3570681
?†1$@DX`acb€U,35C3IE8E>FLE>6892ƒ6>9x35E8914@{.*E8E>mZ68?0FLQ
C350FL;
M 680OS0yMk1R1
0O*FC(1
C0O*1
Q
1$?,3IE(359UoF7L091$@o96>2T;68='350681$?,jo35E868Q
?*2<F?'0
O35?*;E868?Q43I?;A;3503/71$?'JFC9681
?j91S0O,3I0 0OFR71$2<U68E8FCt243"m~FL@{K
p*768F?'0E8mg9682<;68=Fi71;*F9T68?'J1$E>J'68?Q†35Cs680C3ICmg71$2[s*6>?350681
?*9T1$@
2T6>93IE86>Q$?2<FL?0<35?*;A;,3I03/0m'UoF:2<68Hw68?cE>11$U9tM 680O]35?'mw1
@,0OCFLF
E8FJ
FE89/1$@GX`acb}U,3IC35E8E8FE86>92cW
… O*F6>?'0FC1$UoFC35s*68E>680ymò1
@]0OF9682<;*68='350681
?@{C3I2<FM1
Clò689
3I7PO*68FJF;^s'mA0OFD.9F[1
@kJ'68C0.,3IE,JF701$C9i35?*;›3R2D.E8068Kð90FLU^;*FK
J'68C0.,3IE86>=350681
?cU*C17F99Wq-NJ'6>C0.35EzJF701$CG7'35?AO3"JF:UC1$UoFC068F9
0O350^3ICFAE8F99i71
?*90C3568?F;f0O,35?_0O1$9FA1
@VO,35C;*MR3ICFcUO'm'96>735E
J
F701
C9jG9.75Od359xO3"J68?*Q€3ICs680C35Cm¥E8F?*Q
0O–1
C~?1N35E868Q
?*2<F?'0
7L1
?90C3I68?09Wn… O*689kF?35sE8F9q91
2TFt1$@|0OF F'3ICE>m[0C35?*9@{1
C2c350681
?*9j
9.*7PO_3I9:FH'0C357L06>?*QZX`acb›U35C35E8E8FE86892\@BC1
2\s359687DsE817Pl'9<35?;
ö X1
2TFTÆ,`õ›682<U*E>FL2<F?'0350681
?*9~35E891x71$2<UE8F0FLE>m4.*?C1
E8E(0OF[68?K
?*FC2<1$90tE811$U,W
aTF'3I9.CF2<FL?09/1
?_3 ˆqˆ‰ Š$‹5Œ M 6>0O}3:SaTŽÇX`acbf.*?680/68?*K
;687'3I0F~9UoFLF;.*U“@3I701
C9[1
@G.U“01_$W8‘
‘^‚”
W8• ¡ O,3IC2<1
?*687w2TF'35?
9UoFF;*.Ud@357L01
C„c@{1
CN•}l
FC?FE89†FH'0C3I70F;£@BC1
2û?'.2<FLC6>735Eyj
J'68;F1jz3I?;w71
2T2[.*?687'350681$?†35U*UE8687'350681$?9WGaTF'359.*CF2<F?'09D3IE>91
68?;*6>7350F:9UoFFL;.U~@3I701
C9G1
@n.Uw01c”
W8‘$•<‚‘
W8” Œ O,35C2T1
?687:2TF'35?
9UoFF;*.U~@357L01
C„@{1$C Š soF?75O2c35CliUC1$Q
C352T9W,Æ,35701$C9T3ICFR0OF
C350681^1
@/0OFi0682<F9<@B1
C^3<?1$?K)9682<;68=F;N3IUUE8687'3I06>1$?f1JFC[0OF
9682<;68=FL;]35U*UE8687'350681
?_3I7PO*68FJF;~0OFR9352TFR1
U0682<68='3I0681
?cE8FJFEyW
… OFSCFL90[1$@ 0OFSU,3IUoFCe689[1$CQo35?*68=F;N359D@{1$E>E81M 9W†XFL70681
?–”
68?'0C1;.7LF9V0O*FD1JFLC35E8E9682<;68='3I0681
?^@{C352TFMk1$ClnW ¢ Fe0O*F?A;FLK
97C68soFT@B1
.*CR96>2T;68='350681$?Z0F75O?*68‡.*F9Vs359F;^1
?^J'68C0.,35EnJF701$C9
68?]XFL70681
? ¡ jÈojuô
ju35?;†•
jCFL9UoF7068JFE8mW,H'UoFC682<F?'03IEuCF9.*E809
35CFSU*CF9F?'0F;Z6>?›XF7L06>1$? ‹ WcXF70681$?¥[;*6>97L.99F9e0OFTCFEy350F;
Mk1$Cl“3I?;~MkFR71$?7E8.;*FR68?]XF7L06>1$? Š W
2. OVERVIEW OF FRAMEWORK
`?^0O689R9F7L06>1$?,juMF<68?'0C1;.7LF<J'6>C0.35E(JF7L01
C9~35?*;ZQ$6>J
F^35?
1JFCJ'68FM–1
@,0O*F:UC1$Uo1
9F;A9682<;*68='350681
?c@BC352<FLMk1
CluW
2.1 Virtual Vectors
V68C0.35EJFL701
C9:35CFT35?Z35s*90C3570681
?Z3Iso1J
F/0O*FtU*O'm9687'3IEJF7LK
01
C9GU*C1J'68;FL;As'm^3VO,35C;*MR3ICFwX`acb_.?680WGXUoFL768p7'3IE>E8mjz3/J'68CK
0.,3IE(JF701$CRO,359w3I?¥3ICs680C35Cm4;,3I03DE8F?*Q
0O¥3I?;^?1“35E868Q
?2TF?'0
71$?90C3568?'0WN`y0w689wCFUCFL9F?'0F;¥OFCFcs'm€3NüSýþÿ 40.UE8Fc01
68?;*6>7350Fc3:JFL701
C/1
@ “U,3I7PlFL;cFE8F2<F?'09V1$@;3503:0m'UoF W … OF
?'.2DsoFC,1
@oFLE>FL2<F?'0(UoFC,JF701$Cj qj$689/371$2<U68E8FK)0682<FG71
?*9035?'0W
… OFt0m'UoF 1$@z0O*FGJF701$CFE8F2TF?'09j j$689kFL6>0O*FCV3 U*C682<6806>J
Ft;3503
0m'UoF:1$CG6>9G6809FE8@t3/JFL701
CW
… OFwpC90DUC1$UoFC0mZ1
@T3<J68C0.35EvJFL701
CD689T6809Ts'm'0FiE>FL?Q
0Oj
‚ R‚
‚ „W ¢ OF? ,689kU*C6>2TK
„„jM O687POi689k;*Fp?*F;^359
68068JFR;,3I03V0m'UoF'j9.75O]359 !ÎÏ 1$C Ò'#& j ‚ L„n6>9t9682<UE8mw0OF
s'm'0FA968=F41
@:0O350i0m'UoF'j:Âó{»ó¼j +'#Ò ‚ L„W ¢ OFL? T689Z3~JF7LK
01
CT0m'UoF'j,0OFxE8F?*Q
0O_@{1$C2[.*E3i689<CF7.*C96>J
FE8mÌ35UU*E86>FL;f.?'068Ee3
UC682<68068JFR0ymUoFV6>9GCF'3I7PO*F;,W
… O689/E>FL?Q
0OcU*C1
UoFC0ym~689/?1
0t01isoFe71
?*@{.9FL;cM 6>0O40O*FDs'm'0F
E8F?Q$0O†1
@G0OFiU*Om'9687'3IEkJF7L01
C9D9.UUo1$C0F;†s'mZ0O*FiO,35C;*MR3ICF'j
M O6875OA689GpH'F;†3I?;~;F?*1
0F;~OFCFw3I9
zW
… OFS9FL71
?*;†UC1
UoFLC0m^1
@D3TJ'68C0.,35EqJF7L01
Ce689[6809x35E868Q
?2TF?'0
UC1$UoFC0mW€-/?Í¿ÀÁº¼»¸*Â5ÃcJF7L01
CxE8135;,’I901
CF›35s90C3I709A0O*F^soFLK
O,3"J'681
C<1$@S3I?š3IE>68Q$?F;}2<F2<1$Cm†6>?*90C.70681$?,W“Æ1
CTFHu352<U*E>Fj/3
E81o3I;f1
@T35?€35E868Q
?*F;_JF701$C D‚
L„t@BC1
2h3I;;CFL99
AE>135;*9
‚ R‚
„„s'm'0F9G@{C1$2
M OFLCF'359<3VE>135;
1
@~3I?ͽ¸*¿ÀÁº¼»¸*Â5ÃAJFL701
CwE81o35;*9xJFL701
CwE8F?Q$0O¥sm'0F9i@BC1
2
35?
35Cs*680C35Cmg35;;*CF99
W
…1]71$?7E8.;*F'j MkF^93mf0O,350g3AJ'6>C0.35E:J
F701
CwCFU*CF9F?'09†3
UO'm'9687'35E(JFL701
CR68@v0O*FTJF7L01
CR689
†3I?; ‚ e‚
„„
WVÆ1$C:0OF[CF90:1
@0OFDU,3IUoFCjMkF43I99.2<F[0O,350
689w‘
•
s'm'0F9W
. !!"
!!"
$#% !!"'&( )!* +-,
0/2143!657
4 98
: -V@B0FC^0OF]71
2TUE8F0681
?1
@i0O*6>9ZUO359F'jRJF701$C9gO3J
F_s'm'0F
E8F?Q$0O9w0O,3I0g3ICF42[.*E>068U*E>FL9~1$@
]s'm'0F9is.*0S243"m}9068E8E:soF
.?35E868Q
?*F;,W
VR
Basic−block aggregation
virtual vectors
Loop−level aggregation
; Alignment devirtualization
Length devirtualization
physical vectors
<
>=ð䮪“å ?D°ä7@A®¨å'¬“°±CBu©«ä¯ã®*ì
¨©«ª“¬©«­®*¯©«°±
`y?41
.C/@{C3I2<FMk1$Clujo0O*FCFx35CFT0O*F[968HA2c3568?Z0C3I?9@B1
C243I06>1$?
7L1
2<Uo1$?F?'09j|359G;FLU6870F;i68?xÆ,68Q
.*CFi”
Wn… O*F:pC90k0OCFF/UO,3I9F9
FLH0C3I70xX`acb€U35C3IE>E8FE86892h3I0[;*6>roFLCF?'0DU*C1
Q$C352971
UoF9[68?01
Q$F?FLC6>7D1
UoFLC350681
?*9:1
?cJ'68C0.,3IEJF701$C9Wv… OFe?FH'0t0M1SUO,3I9F9
U*C1
Q$CF9968JFE8m4;FJ'68C0.,3IE>68=F[J'6>C0.35EJ
F701
C9V01w2c35075O^0O*F[U*CFK
7L6>9F¥35C75O680F70.*CF“71
?*90C3568?'09W¤… OFgp*?,3IEDU*O,3I9FgE81MkFC9c0O*F
Q$F?FLC6>7eJFL701
C 1$UoFC350681
?*9/01TUEy350@B1
C2 9UoF768p7R68?*90C.70681
?*9W
HG
JIKA @
B
®¨å4˜Lç [®¨©«ë ì«°|ë ]ì«å oå'ì®*ââäå'⮯©«°±ïʅ O689
U*O,3I9F
FLH0C3I709iX`acb¥U,35C3IE8E>FLE>6892îM 680O68?f3es359687Ts*E>175lcs'mAU,3I7Pl'68?Q
6891$2<1
CU*O687†71
2TU.03I0681
?š1$?¤3I; ñ 3I7F?'042<F2<1$Cmd3577FL99F9Z01
J
F701
CG1$UoFC350681
?*9W
 F701$C9UC1;*.7FL;Ds'm:0O*689UO359FkO3"JFR3ICs680C35CmRE8F?*Q
0O9 35?;
q
2c3mwsoF:.*?,35E868Q
?*F;,W
DFE
E
®¨å4˜˜Lç — °ä¯Sì«°z°ê›®ââäå'â®*¯©«°±ï
… O689fU*O,3I9FÌFLE>682<68K
?350F9[9682<;68='3IsE8F~68?*?FCDE811
U9[M 680O_9O*1
C0jn71$2<U68E8FK)0682<Fw0C6>U
7L1
.?'09/smg35Q$Q
CFQ35068?Q~90350687T7L1
2<U*.0350681$?c1
?490C68;FK)1
?*FA3I7K
7LF99F9x357C1$99[0O*F<F?'068CFSE>11$U“68?'01A1
UoFC3I0681
?9e01AE81$?Q
FLC[JFL7K
01$C9W k68JF?c3q9O1
C0(E811
UTM 6>0OT71
2<U*68E>FLKð0682<FG0C68UT7L1
.?'0 ,j*35?'m
;3503e1
@q0m'UoF G68?Z0O*F[E811$UgsoF71$2<F9RJFL701
C e‚
L„V3I@{0FCR0O*F
3IQ
Q$CFQo3I06>1$?,W
L
O
P
MN
NM
qF701$C9UC1;*.7FL;Ds'm:0O*689UO359FkO3"JFR3ICs680C35CmRE8F?*Q
0O9 35?;
2c3mwsoF:.*?,35E868Q
?*F;,W
RQ
DFE
0I B
®¨å4˜˜˜Lç k°|°ê ì«å oåì®ââäå'â®*¯©«°±ï
… O689
U*O,359F
FH'K
0C3I709cX`acbU,3IC35E8E8FE86>92Ê357C1$99SE811
U]680FC350681
?*9W ‰ 1$2<U.*035K
0681$?9 1
?~90C68;FK)1
?*FS3I77F99F9[3I7C1
99G680FC350681$?9[35CFi3IQ
Q$CFQo3I0F;
68?'01RJF7L01
Cq1
UoFC3I06>1$?9smDsE8175l'6>?*QR0OFGE811
Uis'mA3k@"35701$Ck1$@ ~W
-/?'m<;,3I03t1
@u0m'UoF (68?~0O*FVE811
UxsoF71
2TF9 JF701$C e‚
L„v35@B0FC
0O*Fw35Q$Q
CFQ350681
?W
:
SU
OS
SU4
VSW NXFY Z-[ 6\
S]8 L ‰ bV‚ ‚) „ \^\^\ ‚ ^_$„„ ö
TS
… O*FisE817Pl'68?Qc@"35701$C Ç689[;*F0FC2<68?FL;†9.75O“0O,3I0D0O*FSs'm0F
E8F?*Q
0O_1
@tF'3575O]JF701$C e‚
„t68943IE8MR3"m'943i2D.E8068UE8Fw1
@
‚ L„
s'm'0F9j?,3I2<FE8m
Œ … O*Fv92435E8E8F90(9.75OesE8175l68?*Q
@"35701$C/689
L
`?_1
.*C^35E8Q
1$C680O24jk90C68;FLKð1$?FA2TF2<1
CmN3I77F99F9Z3I7C1
99w680K
FC3I06>1$?9w3ICFTJ'68FMkF;}3I9i¾I¹ ÂI¿ T¾Ij|M OFCF[0OFx35E868Q
?2TF?'0:1
@q0OF
soFQ$6>?*?68?Qw1
@V3R90CF'352ò689:735E8E8F;›¾I¹ yÂ5¿ Y· v¾I¹«W:… Mk1~90CF'352T9
35CF471$?968;FLCF;¥CFEy35068JFE8m}2<68935E868Q
?FL;Ì68@R0O*Fm]O,3"JFc;68roFCFL?0
90CF'3I2
1$ro9F09WN`?¥0O*689~7'3I9F'j 01†F?9.*CFc0OF471
CCFL70?F99~1
@
0OFx71
2<U*.03I06>1$?35@B0FCw96>2T;68='350681$?,jv0OFA7L1
2<U*6>E8FCw68?9FC09Z3
U9FL.;1D1
UoFLC350681
?~7'35E8E8F;g¾5¹ yÂI¿
¾ º I¹*01D9O68@{0k6>?wCFQ$6>90FLC9 1
?F
90CF'3I2d01:2c35075OS0OF 1
ro9FL0k1
@o0O*FG1
0OFLCq90CF3524W X0CF'3529O68@B0
689GE3I0FCG2435U*UoF;x01A3/9F‡'.FL?7F:1$@?,3I068JF:;,3I03tCF1$CQo3I?68='350681$?
68?90C.*70681
?9W
dc fe Jg
-G0R0O689e9035Q$F'jnJF701$C9~35CF^35E868Q
?*F;Ì35?*;“O,3"JFTsm'0F<E8F?*Q
0O*9
0O,3I0D35CFe2D.E8068UE8F9G1
@
<s'm'0F9W
2.2 Simdization Framework
DFE
0B
dc e (h i
SIMD code generation
B
bI B
dc e
transition
á «© âãnäå çDè
oå'ë¯L°ä¨
a` Q
DFE
®*¨åc˜ wç k°|°ê ì«å oå'ìk®*ì«©«â±ª“å'±z¯[¬nå z©«ä¯ã®*ì«©«­®¯©«°±ï
… O 689UO359F¤0C3I?9@B1
C2<9E81o3I;9µ35?*;ƒ901$CF9@{C1
2
Uo1$9968sE8m
.?35E868Q
?*F;]JF701$C9T01}35E868Q
?*F;}J
F701
C9W ¢ FiO3J
Fw;*FJ'689F;N35?
35E8Q$1
C680O2 0O,350w7'3I?ÌO35?*;E8FZE811$U9AM 680OÍ35Cs*680C35Cm›2<6893IE>68Q$?K
2<F?'09]s'mCF'35E868Q
?*68?Q;,3I03}68?£CFQ$6>90FLC9j~M O68E8F¥2<68?682<68=68?Q
so1
0O~2<F2<1$Cm“3I?;~;,3503tCF1
CQ35?68='3I0681
?41JFCOF35;x68?'J1$E>J
F;x68?
;,3I03/CF'3IE>68Q$?2<F?'0 ž •5ŸyW
Short loop aggregation
R+
‚‘$„
M *
O FCF
‰ bN7L1
2<U*.0F9:0O*F<Q
CF350F90R71$2<2<1$?g;68J'6891
Cw3I2<1
?*Q
3IE8En0OFV6>?*U.*09W
++
DFE ®*¨åj`~çHQå'±â¯ E ¬nå0zB ©«ä¯ã®*ì«©«­®¯©«°±ï
`y?T0O*6>9(U*O,359FjJF7LK
01
C9^3ICFApC90TÉ,3500FL?F;_01ZJ
F701
C9S1$@VU*C6>2T6>068JF~0m'UoF9W“… OF
71$2<U68E8FCV0O*F?A243IU9t1
UoFC3I0681
?9/1
?cJ'68C0.,3IEuJFL701
C9t01S1
UoFC3IK
0681
?*9T1
?]2D.E8068UE8FwUO'm'96>735EkJ
F701
C9W_X1$2<F0682<F9j1$UoFC350681
?*9
J'68C0.,35ERJ
F701
C9x243"m›soFg;*FJ'6>C0.35E868=F;Ì01}9735Ey35Cc1$UoFC350681
?*9
M OFL?,jk@{1$Cx68?903I?7Fj 0O*Fc035CQ$F0~U*Ey350@{1$C2 ;*1F9w?1
0i9.*UUo1
C0
3:U,3IC06>7L.Ey35CiX`acb›1
UoFLC350681
?WG… O*F[;*F7689681
?^6>9/s,3I9F;41
?40OF
E8F?Q$0OT1$@0OFJF701$CjM O*F0OFLC,0OFkJ
F701
Cn6>9t3IE86>Q$?F;j3I?;T1$0OFC
OFL.C68906879G0O,350 ;*F0FC2<68?*FRM OF0O*FC 01<UoFC@B1
C2Ü0OFV71
2<U*.03IK
0681
?A68?AJ
F701
C9 1$CG97'35Ey35C9W
qF701
C9 U*C1;.*7F;xs'mi0O689GUO359Fi3ICFR?1M–UO'm'9687'35EzJF701$C9W
DFE j`
®*¨å ~˜Pç —˜L™ œ ë°|¬å4âå'±å'䮯©«°±ï
… O*6>9ZUO359F_2435U*9
Q
FL?FC687V1$UoFC350681$?9v1$?wU*O'm9687'3IEJF7L01
C9k01e1$?Ft1
Cv2<1$CF<X`acb
68?90C.*70681
?91
Cv68?'0C68?96879j
1$Ck01eE86>s*C35CmS7'3IE8E>9R35771$C;68?QD01e0OF
035CQ$F0GUEy350@B1
C24W
`?Z0O689D@{C352TFMk1$Clnj X`acb¤3IQ
Q$CFQo3I06>1$?}17L7.C9DM 680O68?“J'68CK
0.,3IEvJF7L01
C9jnM O6875O]1
roFC[0OFi71
2TU68E8FCc3<.9FL@{.ER35s90C3I70681
?
7E81
9Fg01fJF7L01
C9AU*C1J'68;FL;Ìs'm›0C3I;680681
?35EDJF701$CA243575O68?*F9W
… O689V35Q$Q
CFQ350681
?i7'3I?<91
E8FE8mD@{17.*91$?<FH'0C357068?*QiX`acbZU,3IC35E8K
E8FE86892d@BC1
20OF 2T1
CFG;68JFC9F 91$.C7FL9U*CF9F?'0,68?<2<1;FLC?<2[.*E8K
0682<F;*63c3IUU*E>687'3I0681
?9Wx… O*FSE81
Q
6890687x1$@ ;F'3IE86>?*QcM 680O†CF;.*7F;
O,3IC;M:35CFe9.U*Uo1
C0 689/0O*F?xCFLE>FLQo350FL;c01<0OFREy350FLCt9682<;*68='350681
?
UO359F9G0O350v68?7LCF2<F?'035E8E8mg35;;*CF99 6899.F9G9.*7PO“359[35E868Q
?*2<F?'0j
9O1$C0kJFL701
C9jo3I?;iU,3I7PlFL;S;,3503v0ymUoFL9WuÆ,68?,35E8E8mj
0OFGÉ*FH'6>s*68E>680ym
1
@;FLJ68C0.35E868=68?QtJF701$C9n01G97'35Ey3IC9,2435lFL9n680nUo1$996>s*E8Fk01GCFJFC0
91
2TFV1
@z0OFtE8F99 1
U*0682435Eo;*F7689681
?9 2c35;Ft;.*C68?QeF'35CE8mSU*O,359FL9
1
@k96>2T;68='350681$?,juM O*F?gEy350FLCx3D2<1
CFSQ$E>1$s,3IEkJ'68FM1
@vCFL91
.C7LF9
soF71$2<F9T3"J3I6>Ey3IsE8F'W
`?40O*F[?*FH'0V9F70681$?9joMkFTM 68E8E(;F97LC6>soF[@{1$.C:0F75O?*68‡.*F9V68?*K
71$CUo1
C350FL;“68?g0O689R@BC352<FM1
Cl^0O,3I0R7E8F'35CE8m^;F2<1$?90C3I0F<0OF
soF?*Fp0 [email protected]?QTJ68C0.35EzJF701$C9T3I?;~;FJ'68C0.,3IE>68='3I0681
?,W
3. SIMDIZATION
WITH
MULTIPLE
SOURCES OF SIMD PARALLELISM
¢ F ;*F97C68soFt6>?T0O6899FL70681
?i1
.*C68?'0FQ
C3I0F;^35U*UC13575OS01RFH'K
0C357L06>?*QcX`acb†U,35C3IE8E>FLE>6892ÜU*CF9F?'0k68?ws,359687:s*E817Pl^3I?;Z357C1$99
71$?9F7.*068JFRE811
UA680FC3I06>1$?9W
Vectors
a) Original code
iter i=0
for(i=0;i<n;i++) {
a[i].x =
a[i].y =
a[i].z =
b[i]
= }
a0.x
iter i=1
a0.y
a0.z
b0
a1.x
a1.y
iter i=2
a1.z
a2.x
b0
b1
iter i=3
a2.y
a2.z
a3.x
b0
b2
a3.y
none
a3.z
none
b0
b3
b) Basic block aggregation
for(i=0;i<n;i++) {
(a[i].x,y,z) =
b[i]
=
}
a0.x
a0.y
a0.z
a1.x
b0
a1.y
a1.z
a2.x
b0
b1
a2.y
a2.z
a3.x
b2
b0
a3.y
V<3,int>
len(V)=12
a3.z
none
b0
b3
c) Loop aggregation
for(i=0;i<n;i+=4) {
(a[i].x...a[i+3].z) =
(b[i].......b[i+3]) =
}
a0.x
b0
a0.y
b0
b1
b2
b0
a0.z
a1.x
a1.y
a1.z
a2.x
a2.y
a2.z
a3.x
a3.y
V<4,v<3,int>>
len(V)=48
a3.z
V<4,int>
len(V)=16
b0
b3
d) Length devirtualization
for(i=0;i<n;i+=4) {
(a[i].x.....a[i+1].x)
(a[i+1].y...a[i+2].y)
(a[i+2].z...a[i+3].z)
(b[i].........b[i+3])
=
=
=
= }
a0.x
b0
a0.y
b0
b1
b2
b0
a0.z
a1.x
a1.y
a1.z
a2.x
a2.y
a2.z
a3.x
a3.y
V<4,int>
len(V)=16
a3.z
V<4,int>
len(V)=16
b0
b3
jkç<™€©dluå'¬f¨¯Lä©«¬nåKI°±åc®±n¬›®¬bmL®ë
å±z¯<®*ëëå'¨¨å'¨ï
á ©«âãäå
3.1 Mixed Sources of SIMD Parallelism
y` ?Z0O*Fc3Is9F?*7F<1
@kO,35C;*MR3ICF<9.U*Uo1
C0R@{1$CRQo3I0OFCw3I?;g97350K
0FLC~2<FL2<1
Cm_1
UoFC3I0681
?9jv0O*Fc2<1
90w71
90K)FroFL7068JFcFH'0C3570681$?
1$@/X`acb›U35C35E8E8FE86892ò689V01^3IQ
Q
CFLQo350F[71
2TU.03I0681
?41
?_3:71$?K
068Q$.1
.*9/75O'.?*lS1
@2<FL2<1
Cmw68?01TJF701$C 1
UoFC3I06>1$?9W,… OFCFw3ICF
Q$F?FLC35E8E8m“0M1c6>?*9035?*7F9T68?†M O*6>75O†71$?068Q$.1
.*9[2TF2<1
CmZE817'35K
0681$?9[35CFe@{1$.?*;x68?AUC1$Q
C3I2<9W
Jn
e Ke cJo Kp
´
-G0,0OF s359687K)sE8175l[E8FJFLEj2[.*E806>U*E8FD¿Ã I¿¶I¸*¹ T [· e¿¶
¶I¾I¾5¾Ij|9.75O›3I9 ,) 3I?; , 1$C ÐÑ 35?*; ÐyÚÞÑ j|7'35?
soF<71$2[s*68?F;“68?'01†3I?¥3I77F99D01]3D7L1
?'068Q
.1$.9e75O.*?lc1$@
2<F2T1
CmW
´
-G0(0OF E811
USE8FJFLEj68?9035?*7F9q1
@3:¾I¹ 5º¼Ã ð·¸Âe¿¶I¶I¾I¾5j
9.*7PO
359 !ÐÑ jS3I7C1
99471$?9F7.*068JF“680FC350681$?9}35CF“7L1
2Ds68?F;
68?'01435?]3I77F99t01c3t71
?'068Q
.*1
.9t75O.*?lS1$@2<F2<1$CmW
rq
dc Kp
… *
O F9FS0M1A0m'UoF9V1
@e3I77F99F9x35CFS1$@{0F?g?1
0R7L1
2<U35068sE8F'WTÆ1$C
ÐÑ( 243"mcsoFx35; ñ 357FL?0R2TF2<1
Cm_3I7K
FLHn3I2<UE8F'j ÐyÑq) 3I?;
7LF99F9[350 0O*FVs,3I9687K)sE817PlSE8FJ
FEyj's*.0R3ICF:;FLp?680FE8mS?*1
?w90C6>;*FK
1$?FR2<FL2<1
Cmg3577LF99F9j*68?;*68J68;*.,35E8E8mj|350G0OFVE>11$UcE8FJFEyW
+s
ts
rq
3.2 Integrated Loop Simdizer
uF0<.*9<68E>E8.*90C350FA0O*Fx71$2[s*6>?*F;_FH'0C3570681
?_1
@<X`acbU35CK
I3 E8E>FLE>6892 M 680O68?3is,3I96>7xsE817PlN3I?;€352<1$?Qg7L1
?9FL7.068JFAE811$U
680FC3I0681
?9w.968?*Qg0OFxFHu352<U*E>Fc9O*1M ?f68?ݮ,68Q
.*CF ¡ W ¢ FAM 68E>E
@B1
E8E81MÜ0O689TFHu3I2<UE8Fw0OC1
.*Q
O†0O*FwCFLE>FLJ3I?0[UO359F9[;F97C68soF;
68?–XF70681
?›”
W8”
W ¢ O*68E>FS0O*F4357L0.,35EV35E8Q$1
C680O2î035l
F9~35E8E2TF2<K
1$Cm<CF@BFCF?7LF9k68?'01~35771$.?'0j$MF/@B17.9OFCFG1
?*E8m<1
?S0O*Ft901$CF9
Q$F?FLC350F;ws'mTF'3I7POi1
@z0OFGE811
U³ 9 @{1
.*Ck903I0F2<F?'09j
@{1$Cv71$?7689FK
?*F99WnV3575O<68?;68J'68;.35EÈ
K)s'm0Fk901
CFG689CFU*CF9F?'0F;<s'm~3so1HD6>?
Æ,68Q$.CF ¡ 0O*F/so1H'F9³
9O35;1M 9D3ICFi35E80FC?35068JFE8mSQ
C3"mS1$CvsEy3575l
01T;689068?Q
.*689OA71
?*9F7.*06>J
FR6>0FLC350681
?*9/1$@0OFR1$C6>Q$68?,35EuE811
U,W
,
G[®¨©«ëJIKAì«°|ë@_ì«å Boåìq®ââäå⮯©«°±nï
… OF
71
2TU68E8FCÊCF71$Q
K
?*68=F9,0O,3I00OFpC900O*CFFk901$CF9,68?[Æ,68Q$.CF ¡ 3
j (ÐÑq« j (ÐyÑq j
3I?; ,ÐÑqð+ j 35CFZ35; ñ 357LF?'0D68?“2TF2<1
CmWS-V99.*2<68?QAO*FCFS0O,3I0
0O*FVC68Q
O'0O,35?*;i96>;*F9 1
@z0OF/0OCFFt90350FL2<F?'09e35CF/6891
2<1$CUO687'j
680V35Q$Q
CFQ350F9 0O*F 0OCFFG90350FL2<F?'09k68?'01w3kJF701$C1$@ ¡ 6>?'0FQ$FC9
901$CF;“68?'01 (ÐÑq)( ,+ j 359D9O1M ?“68?ZÆ,6>Q$.CF ¡ sWT… OF ÐyÑ
903I0F2<F?'0GCF243I68?A.?*7PO35?Q$F;,W
q
rq
Qk°|°ê0Iì«å Boåìk®ââäå'â®*¯©«°±ï õ(F7L1
Q
?*68=68?Qš0O*FfJF7L01
C†901
CF
(ÐÑq)(,
q + 3I?;¥0OF4FE8F2TF?'0~901$CF ÐyÑ 3I9~90C68;*FK)1
?Ff357LK
7F99FL9jo680/@{.C0O*FCT35Q
Q$CFQo3I0F9R0OFL9FA3I77F99F9S357C1$99:E811
U^6>0FLCK
q +
350681$?9Wf`?};1$6>?*Qg91jk6>0S0CF3509i0OFA?*FMÜJF7L01
C (ÐÑq)(,
90350FL2<F?'0T?*1c;68roFCF?'0E8mg0O35?N35?'mg1$0OFCD90350FL2<F?'09T68?]0OF
q y+ 35?*; ÐÑ
E811
UWn… OFG1
?*E>m[;68roFCF?*7F soF0yMkFF?S0O*F (ÐÑ()((
90350FL2<F?'09<689S0O,3I0<0OFwpC90<1$?F~Q
F?*FC350F9^3^‘
”is'm0FwJ35E8.F
M OFLCF'359t0OF:9FL71
?*;A1
?*FRQ
F?*FC350F9T3/È<s'm'0FVJ35E8.*F'W
b.*C6>?*QZ0O*689<UO359F'j(MkFAFH'0C3I704X`acbU35C3IE>E8FE86892
352<1$?Q
0OF 92c35E8E8F90?'.*2[soFC,1$@o71
?*9F7.*06>J
F 6>0FLC350681
?*9kM O68E8F F?*9.C68?Q
0O,3I0/F3575OcJF701$Ct68?c0O*FDE811$UcO,359T3:E8F?Q$0OA0O,3I0/689T3V2[.*E>068U*E>F
1
@u0OF:U*O'm9687'3IEoJF701$C E8F?Q$0O,j|‘
•Gsm'0F9kOFCF'Wn… O*F:@{1$C2[.*Ey3/1
@
q‡.350681
?“‚‘
„u;*F0FC2<68?*F9 0O,3I0 0OFV1$U068243IEzs*E817Pl'68?Q[@357L01
CG689
Èojn968?*7Fi6>0x35Q$Q
CFQ350F9TÈc1
@G0OF^‘$”5K)s'm0F ,ÐÑq), (+ JF701$C9
68?'01i3k?FM_71$2<Uo1
.*?;<JFL701
C(1
@oȐks'm0FL9V3I?;<ÈV1
@o0OF È$K)sm'0F9
ÐÑ J35E8.*F9 68?01c3/?FM–JFL701
CG1
@ ‘
•/s'm'0F9W
… OFSCFL9.E8068?QcE811
U†689D9O1M ?“68?“Æ,68Q
.*CF ¡ 7'W V1
0FS0O350eMkF
243"m<É3500F?SJFL701
C9v1$@|JF701$C9R350R35?'mT0682<F9joÂó{»ó¼j$9682<UE868@{m'68?Q
e‚{È e‚ ¡ & „„6>?~0OF:7L1;F~35so1JF:01 D‚‘$” '& „W
q
6^
B
u
èwì«©«â±ª“å'±z¯[¬å z©«ä¯ã®ì«©«­
®¯©«°±nï
… O*6>9\90FU
689ò?*F7F993ICm
1
C M OFL?
35CC3"m
35CF ?1$0Ê3IE86>Q$?F;W
X68?*7F so1
0O
(ÐÑq)('
$(ÐyÚ Ñq)+ 35?*; ÐÑ'$« ÐÚ $Ñ 35CFR90C68;*FK)1
?F
357L7F99F9j|0OF68Ci3IE>68Q$?2<F?'0R71$?90C3I6>?'09w3ICFTO,3I?;*E>FL;Z?*1~;*6>roFLCK
F?'0E8mi0O,35?“35?'mi90C68;FK)1
?*Fw3577LF99/1$@,?,3I06>J
F:;,3I03/0m'UoF9W
Æ1$Cx9682<UE8687680mjGÆ,68Q
.CF ¡ 3599.*2<F9A0O350xso1$0O–JF701$C9†35CF
35E868Q
?*F;,W Ë .*0G71
?*96>;*FCG68?x0O689 U35C35Q$C35U*OA0O,3I0 1
?FR1$@0OFL2¤689
?1$0jkÂó¼»ó{j|93"m (ÐðÖ
Ñq 689~‘
•Ts'm'0F43IE>68Q$?F;“68?*90F'35;“1$@ (ÐðÖ
Ñ() W
… OFL?,j0O689 UO359F:M1
.*E>;~E81
Q
687'3IE8E>m~9lFM¥0O*F:71
2TU.03I0681
?9D3I9K
9176y350FL;wM 680O<J
F701
C 01:0O*F C6>Q$O'0s'me1
?*F J3IE>.*F'Wu-/9V3kCFL9.E80j
0OFxsE817Pl
F;fE811
UfMk1
.*E8;fFroF7L06>J
FE8m_7L1
2<U*.0F]3I?;f901$CFc0OF
(ÐÑq ('
$(ÐyÚ Ñq« 68?90F'3I;A1
@ ,ÐÑq),'$"(ÐÚ $Ñqð+ W
!v
!v
dq
rq
Qkå'±â¯ E
B
fw
!v
v
(ÐÑq«('(ÐÚ Ñqð+
¬ å z©«ä¯Lã®ì«©«­®*¯©«°±ï … OF
JF7L01
Cx689As*C1
lFL?¥;1M ?N01 ¡ UO'm'9687'35E:J
F701
C9“359A9O*1M ?N68?
Æ,68Q
.*CF ¡ ;WD-G0:0O689R903IQ
F'j35E8EJ
F701
C9RO3"JFTsoF7L1
2<F<U*O'm9687'3IE
JF7L01
C9jq?352<FLE>m†0O*Fm–3ICF]35E868Q
?*F;š3I?;_1
UoFC3I0F9S1
?€‘
•IK)sm'0F
;,3I03
W
`?x0O689/FLHn3I2<UE8F'j's,3I96>7LKðs*E817PlAE8FJ
FE 3I?;AE811
U4E8FJFLEn9682<;68='3IK
0681
?AF3575OAO,3I?;E8F9G91$2<Fw359UoF7L09/1$@9682<;68=68?QS0O*F:E811
Uú
s
$
L'&–(мØÑ,Ó
$
LÎ#Ï&}vЫØÑ,Ó
Ò'#ÏÜÔ5'&€†Õ›ÖÓc
×Ø(Ó4ÚÚÛ_
,ÐћÕÇ
$Ó
vÐћÕÇ
$Ó
s
jxç<™š©dlzå'¬}¬n®¯®Zì«å±n⯠E
á ©«âãäå
a) After loop−level aggregation
}
}
&b[i+1]
&a[i]
V<8,uint,
unaligned>
®*ëä°¨¨S¨¯®¯Låªgå±z¯¨ï
L'&N(ЫØÑÓ
LÎ#Ï&f мØÑ,Ó
Ò'#ÏÜÔ5'&€†Õ›ÖÓc
×Ø(Ó4ÚÚÛ_
,ÐћÚÕ£Ôð'&ÛZ ÐÚÞÑ,Ó
load
V<8,ushort,
unaligned>
load
|
conv
V<8,uint>
SKIP (8)
add
V<8,uint>
store
V<8,int,
unaligned>
&a[i]
b) After alignment handling
}
&b[i+1]
jyçT™š©dluå'¬_¬®¯L®gì«å'±â¯ E ¨ ?<©«¯ E
á ©«âãäå
©«±}®g¨¯®*¯å'ª“å'±u¯Lï
}
&a[i]
´†Ë 3I96>7LKðs*E817Pl†E8FJFLEv9682<;68='3I06>1$?]71
2Ds68?FL9T0OFi1$0OFCM 689F
?1$?“90C68;FK)1$?FZ3577LF99F9j (ÐÑ() j (ÐÑ( j 35?*; (ÐÑqð+
68?'01<90C68;FK)1
?*Fw3577LF99F9t@{1
Ct9.s*9F‡'.F?'0vE811$UAE8FJFEyW
rq
´
z
4.
|
4q
SIMDIZATION WITH MIXED DATA
LENGTHS
`y?]0O689<9F70681$?,jqMFx;*F97C68soFA0F75O?*6>‡'.*F9T01^9682<;68=FAE811$U9
M 680OA2T6>H'F;x;,3503GE8F?Q$0O9W
4.1 Mixed Data Lengths
… O*FCF†3ICF~0yMk1^0m'UoF9[1
@tE>11$U9<0O350[2<68H“;,3I03S1$@/;*68roFCF?'0
E8F?*Q
0O*9W^… OF~pC90[0m'UoFi71
?'03568?*9<90350F2TF?'09T0O,3I0TF'3I7PO]1$UK
FLC350F9[1
?†;,3I03T1
@G.?*68@{1
C2îE8F?*Q
0O,jns*.0e;68roFCFL?0e903I0F2<F?'09
1$UoFC350F^1
?¥;3503A1
@R;*68roFCF?'0~E8F?*Q
0O*9W€Æ,6>Q$.CF^Ȇ68E>E8.*90C350F9
1$?F}9.75OÍE811$U£M 680O0m'UoFK)O1$2<1
Q$F?F1$.9“903I0F2<F?'09W
… O*F
9FL71
?*;Ì0ym'UoF^7L1
?'03568?9~90350F2TF?'09x0O,3I0~1$UoFC350F^1
?–;*6>9068?*70
;3503AE8F?Q$0O9wM 680O68?Í3A96>?*Q
E8F^90350F2<FL?0W£X.75O›903I0F2<F?'09
1$@{0F?g6>?'J1$E8JFS71
?'JFLC96>1$?g1$UoFC350681
?*9[soFL0MkFLF?“;,3I03[1
@k;68roFCK
FL?0eE8F?*Q
0O9jzCF@{FCCFL;“01]359xÀÁ¸»¹ ^¶I·¸  5¾Iº¼·¸A68?g0O*6>9eU35UoFCW
Æ,68Q$.CFiôG6>E8E8.90C3I0F9G1
?*FVE811
U~M 6>0O~0m'UoFK)OFL0FC1
Q$F?F1$.9v903I0FK
2TF?'09W
dh '{ Kc
4.2 Integrated Loop Simdizer
`y?fQ$F?FC3IEyjkE>11$U9w68?J
1
E8J'6>?*Qg903I0F2<F?'09iM 680O›E8F?Q$0Of71$?K
J
FC9681
?
35CFî2<1$CFî71
?*90C3568?68?Qø0O35?ÊE811$U9ÇM 6>0O
0ym'UoFK
O*1
2<1$Q
F?*F1
.*9~903I0F2<F?'09Wf… O*6>9i689i;.*FA01g0O*FApH'F;*KðE8F?*Q
0O
?350.*CFA1
@iX`acbJF701$C9WfÆ1
CSFHu3I2<UE8F'j:3i9682<;68=F;fE>FL?Q
0O
7L1
?'JFC9681
?¥@BC1
2
‘5K)s'm'0FA0m'UoFAE8F?*Q
0O¥01–”IK)sm'0FA0ym'UoFcE>FL?Q
0O
7L1
?9.*2<F9[‘tJ
F701
CD3I?;~UC1;.*7F9D”/J
F701
C9Wn… O*FRUC1$UoFC0mS1$@
7L1
?9.*2<68?Qi1
?*F[J
F701
C/s.*0tU*C1;.*768?Qi2[.*E806>U*E8F[JFL701
C9<‚{1
CT3
@BC3570681$?g1
@V3:JF701$Cj0OFe1
0O*FC:MR3"m]3IC1
.*?;,„(689:.?*?,350.*C35E01
2T1
90V7L1
2<U*6>E8FC/68?0FLC2<F;6y3I0F[CFU*CF9F?'0350681$?9W ¢ FR0O'.9t@{17L.9
1$?]0O689[2T1
CFw7PO35E8E8F?Q$6>?*Q49F71
?*;]7'359Fw@{1$CT0OFiCF2c3568?;*FCT1$@
0O*689/9F7L06>1$?,j.*96>?*QS0OFeE811
U468?cÆ,68Q
.CFxôS359<3VMk1$Cl68?*QwFLHn3I2<K
U*E8F'W
Q°|°ê¥ì«å Boåìq®ââäå⮯©«°±nï
… O689]UO359F¥;*1F9]?1
0†CFL‡.*68CF
.*?68@{1$C2Ü;,3I03/0m'UoF:E8F?*Q
0OA68?'J1
E8JFL;~68?]3/7L1
2<U*.0350681$?,W… O'.9j
V<8,ushort>
conv
V<8,uint>
SKIP (8)
add
V<8,uint>
store
V<8,uint,
aligned>
&a[i]
~
Qå±n⯠E
ç
á «© âãäå
¨©«ª“¬©«­
®¯©«°±nï
V<8,ushort,
aligned>
streamshift(2,0)
load
V<8,uint,
aligned>
n11$UK)E8FJFE9682<;*68='350681
?x35Q$Q
CFQ350F9(0O*F.*?,35E868Q
?*F;eJF701$C
1
@q‘$”s'm'0F9j (ÐyÑq)( (+ j
U*C1;.7LF;Ts'mes,3I96>7LKðs*E817PlDE8FJFE
68?'01¥35?š35E868Q
?*F;fJFL701
CS1$@:2[.*E806>U*E8Fx1
@VUO'm'96>735EGJF701$C
E8F?Q$0O9W
?E868lFq71
?'JF?'0681
?35E|3IUU*C1o3575OFL9j9682<;*68='350681
?[1
@0O689nE811$U[689
I3 7PO*68FJF;D0C35?*9U,35CFL?0E8m:M 680O*6>?D0OFqUC1$Uo1
9F;D@{C3I2<FM1
CleM 680OK
1$.0/FH'UoF?968JFeE811
U^CF90C.7L0.C68?Qi9.75O_359/E811
U^CFC1
E8E868?Qg35?;
7L1
E8Ey35U968?*Qoj*1$CtE811$Uc.?C1$E8E>68?*QoW
load
€B
ë°± oå䨩«°±
'=
® ð¯å'ä
bI 0B
ì«°|°ê ì«å oå'ì
K
3T;,3I03T71
?'JFLC96>1$?†@{C1$2ƒ0ymUoF
01A0m'UoF jk35@{0FLCTE811
U*KðE8FJ
FE
ö
35Q$Q
CFQ350681
?jsoF71
2TF9<3V7L1
?'JFC9681
?csoFL0MkFLF?cJF701$C e‚
„
ö
35?*;xJFL701
C e‚
„jM OFCF 689/0O*F:sE8175l68?*Q<@3I701
CW
S‚4
O
SU 
VS
‰ 1
?*968;FCR0O*F[E811
UZ68?^Æ,68Q$.CF4ôRM O6875OZ1$UoFC350F9R1$?Z;3503R1
@
9O1$C0~35?;Z68?0W z 96>?*QA@{1$C2[.*Ey3c‚‘
„jz0O*F<sE8175l'6>?*Qc@3I701
CD689x$j
U,3I7Pl'68?QZ Ð Ñ 9O1$C09:68?01Z3w‘
•IKðs'm'0FeJF701$CS3I?;} ,ÐÑ 68?*K
0FQ$FC9/68?'01c3 ¡ ”5K)s'm'0F:JF7L01
CW
`?wÆ,68Q
.*CFi•
3$jMF:Q
68JFV0OFVFLHU*CF99681
?~0CFFS3I@{0FCG0O689vU*O,3I9F'W
`?¥0O*F40CFF4CFUCF9FL?03I0681
?,j F'3I7PO¥?*1;F^6>9wEy35soFE8F;–M 680O–0OF
0.U*E8F D‚
|„01~CFUCFL9F?'0jzCF9UoF7L06>J
FE8mj
0OF?'.2DsoFC1
@*FE8F2<F?'09j0OFk0ym'UoF'j'35?;[0OF:35E868Q
?2TF?'0,UC1
UoFLCK
068F9,1
@*F'3575OTJ
F701
CWX68?7LFk0OF:35E868Q
?*2<F?'0,UC1$UoFC0mR1$?E8mw35roF7L09
JF7L01
CVE8135;K)901$CF[9F2c35?'06879j6>0/689V9UoF768p*F;41
?E8m~@{1
CV2<F2<1$Cm
?1;*F9W
^ /1r3!65ƒ€&M„6 /1r3!€57
B
èwì«©«â±ª“å'±z¯[¬å z©«ä¯ã®ì«©«­
®¯©«°±nï
… O*6>9UO359FtCF‡'.68CF9V35CC3"m
357L7F99F9:68?40OFeE811
U^soFe90C68;FK)1
?*FA3I7C1
99V6>0FLC350681
?*9:68?c1
C;FLC
01S@{1$C2Å3S¾I¹ yÂ5¿ 1$@,71
?'068Q
.*1
.9/2<F2<1$Cm†3I77F99F9WeX6>?*7Fe0OF
O,3I?;*E>68?*QZ1$@VE8F?Q$0O}7L1
?'JFC9681
?_;.*C68?Q}35?'m“1$@V0OF~0OCFFg35Q$K
Q
CFLQo350681$?gUO359F9VsoF@{1$CFT;1FL9:?1$0V75O,35?*Q
FD0OFD90C68;FK)1
?*F?FL99
1
@w3I?'mš3I77F99F9jG90C68;FK)1
?*F}3577FL99F9x0O350Z35CF468?U*.0i01†0OF
UCFLJ681$.9GUO359F9G9068E8EnCF243I68?A90C68;FK)1
?*FR68?x0OFV1
.0U*.0W
X68?*7FkE8F?*Q
0OT7L1
?'JFC9681
?[689,?1
0n9.UUo1$C0F;D6>?D1
.*C,1
C68Q
68?35En35E8K
Q
1$C680O2 ž •IŸyjMF/U*C1
Uo1$9F;Z35?iFH'0F?9681$?w01e68?7L1
CUo1
C3I0FVE8F?*Q
0O
71$?J
FC9681
?c68?'01S0OF~35E868Q
?*2<F?'0VO35?;*E86>?*QS@{C3I2<FMk1$Cl ž8‹ ŸyWk… OF
?FLMÍ35E8Q
1$C6>0O*2Ü689v243568?*E>mi71$?7FLC?F;wM 680Ox71;*F:Q
F?*FC350681$?x689K
9.FL9 M 6>0Ox90CF'352¤9O*68@{0G1
UoFC3I0681
?9GM O*F?xE8F?*Q
0Ox7L1
?'JFC9681
?~689
68?'J1
E8JF;W
Æ1$Ct1$.CGFHu352TUE8F'jn3I99.2<68?*QS0OFRs,3I9Fw35;*;CF99F9t1
@ 3I?; 35CF_3IE86>Q$?F;jk0OFc90CF'3I2<9iCFUCFL9F?'0F;fs'm (ÐÑ 3I?; ÐÚÞLÑ
O,3"JF35?¤1$ro9F0}1$@ Œ 35?*;Y”$jwCF9UoF7L06>J
FE8mji0O'.9j^35CF¥CFLE3IK
068JFE8mA2<6893IE>68Q$?F;WtÆ,68Q
.*CFc•5s4Q$6>J
F9V0O*FDFLHU*CF99681
?^0CFFx35@{0FLC
35E868Q
?*2<F?'0DO,35?*;E868?QW /1;F &
ÏoLÎÒ
&,Ô n"Ö*Û CFUCF9FL?09~3
U9FL.;1Z1
UoFC3I0681
?¥0O,3I0 «9O*6>@B09 †0OFAFL?068CFc68?U*.0S90CF'3I2ø1
@
ÐÚÞÑ M 680Of35?41
ro9FL0V1
@V”R01 Œ 01w2435075O40OFe1
ro9FL0:1
@ (ÐÑ
dc fe
u
ˆ‡
†‰
†…
Š
šw
load
V<8,ushort,
aligned>
streamshift(2,0)
ushort
unpack_low_pattern
Š
V<4,uint>
Š
V<4,uint>
unpack
V<4,uint>
add
add
j‹çQkå'±â¯ E
store
uint #1
€B
uint #2
b=
load
V<4,uint,
aligned>
V<4,uint>
V<4,uint,
aligned>
B
ë°± oå'䨩«°±f® y¯å'äi¬å z©«ä¯Lã®ì«©«­®*¯©«°±ï
E 0B
å'±â¯
¬nå z©«ä¯ã®*ì«©«­®¯©«°±ï
Æ1
Cg2T1
90“JFL701
C^1
UoFC3I0681
?9j
;*FJ'68C0.,35E868='3I06>1$?A9682<UE8mS68?'J1
E8JFL9vsCF'3Il'6>?*QA3GJF701$Cv68?'01[2D.E8K
068U*E>FRU*O'm9687'3IE|JF701$C9Wn nF?*Q
0Ox7L1
?'JFC9681
?jO1MkFJ
FCj'CFL‡.*68CF9
9UoFL76y35EvO35?;*E86>?*QcsoF7'3I.9Fg3T;FJ'68C0.,3IE>68=FL;†E>FL?Q
0O†7L1
?'JFC9681
?
2c3m–71$?9.*2<F“1
?*F†UO'm'9687'35EeJF7L01
C_35?*;€U*C1;.7LF9c2[.*E806>U*E8F
U*O'm9687'3IE JF701$C9jq1$C<J'6>7LFxJFC93$W ¢ Fx68?'0C1;.*7Fx0yMk1^Q
F?*FC687
1$UoFC350681$?9t01<FH'UCF99G9.*7PO~;,3503tCF1
CQ35?68='3I0681
?,W
Œ Œ  Œ KŽJr4‘(’
5. EXPANDING SCOPE OF INNERMOSTLOOP SIMDIZATION
`?x0O689G9F70681
?j*MkF~35;*;CF99t0OFR9682<;*68='350681
?41$@,9O1
C0GE811
U*9
0O,3I0D35CFeU,3IC0687.Ey35CE8mw71
2T2<1
?A68?A2D.E80682<F;*6y3/71;FL9W
5.1 Constraints of loop-level simdization
²k?F471$?90C3I6>?'0~1
@DE>11$UK)E8FJFEV96>2T;68='350681$?N689A0O350w6>0~0m'UK
687'35E8E8m3IUUE868F9~01†0OF468??FLC2<1
90wE811
U–1
?*E>mW€`y?›2D.E80682<F;6y3
71;*F9j|O*1MkFJFLCj|0O*FCFc3ICF<2435?'mc68??*FC2<1$90RE>11$U9RM 680OgCFLE3IK
068JFE8mi9O1$C0T3I?;~1
@{0FL?c71
?*9035?'0 0C68UA71
.*?'09W
²k?40OF[1
?FTO,35?*;,j9682<;68=68?*Qx9.75O^9O1
C0RE811$U9R243"mc91
2TFK
0682<F9/;FQ$C35;FD0OFeUoFC@B1
C243I?7F[;.*FD01i0O*FD1JFLCOF'3I;_35991768K
350FL;AM 680OAE811
UK)E8FJFLEu9682<;*6>=350681
?W(…1TQ
68JFw3/@BFMNFLHn3I2<UE8F9j
´†Ë E817Pl'68?Q43GE811
UA243"miUC1;*.7FVCF968;.,3IE|E>11$U9G0O,3I0 O,3"JF
01VsoFvFH'F7L.0F;D9F‡'.F?'06y35E8E8mW Ë E8175l'6>?*Q:243"mw35E891R;*F90C1m
UoFC@{F7L0 E>11$Ux?*F90j0O.*9e35roFL709 9.s*9F‡'.F?*7F/E811$UA0C35?*9K
@{1
C2c350681
?*9W
OF?^9682<;68=68?*Q]3[CF;*.70681
?j|0O*F<p?35E(9.2\CF;.*70681
?
6>?~0OFRFU*68E>1$Q
.*FR?FF;*9G01<soF:;1$?FR68?A9F‡'.*F?'063IE|2<1;F'W
´
¢
´
-VE868Q
?2TF?'0:O,3I?;E868?Qi68?7L.C9:1JFCO*F'35;*9j9.75O›3I9:9F0068?Q
.URUoFC2D.03I06>1$?[2c359l'9G35?*;RFH'F7.*06>?*Q/U*C1
E81
Q$.F:35?;eFU*68K
E>1$Q
.*F›‚{E811
U*9„D01†O35?;*E8FcU,35C06y3IE:901
CF9j 91
2TF0682<F9A68?
9F‡'.F?'06y35Ez2<1;FW
*!% ‚
„ïq… O689q1
UoFC3I06>1$?iUC1;.*7F9/3kUO'm'968K
ö
735EJFL701
Cusm/9FE8F7068?Qts'm'0F9n@BC1
2ÌUO'm'96>735EJF7L01
C
35?;
ö
3I771
C;*68?Qx01~0OF[sm'0FDU,3I00FC?Z9UoFL768pF;^s'mcUO'm'96>735E
J
F701
C
*W
´
Œ
´
TŒ
RŒ!KŽJr‘’
!% ‚Œ€Œ KŽJr4‘(’
„ï4… O689D1
UoFC3I06>1$?]UC1;.*7F9~3TUO'm'968K
735E|JF701$Cvs'm<9FE8F7068?*Q<s'm0FL9v@{C1$2¤UO'm'9687'35EoJFL701
C 43I7K
7L1
C;68?*QR01R0OF s'm'0F U,3500FLC?<9UoF768pFL;SsmDUO'm'9687'35E*JF701$C
W
Œ
Œ!KŽJr‘’
Æ1
Ck1$.CFHu352<U*E>Fj0O*FG71
?'JFC9681$?~1$UoFC350681
?w.?*U,3I7Pl'9V3GJFL7K
01$C1
@*9O1$C068?01t0M1VJFL701
C91$@68?'0WzÆ,68Q
.*CF ‹ Q
68JF9,0O*FFLHU*CF9K
9681$?}0CFFL9435@B0FCS;FJ'68C0.,3IE86>=350681
?W V1
0Fw0O,3I0j(0O*689T9682<;68=FL;
7L1;F9S71$?96890<1$@/0O*CFFx;*6>9068?*70TU35C09Wg… OFw01
U_U,3IC0TCFU*CFK
9FL?09D0OFi71$2<U.*0350681
?*9[;*1
?*FS6>?†9O*1
C0j º¼ó{Âó¼j|2c3568?E8mgE8135;68?*Q
@BC1
22<F2<1$CmWx… OFiso1
001$2î0Mk14U35C09DCFUCF9FL?09D0OFi71$2<K
U*.03I06>1$?9/;1
?*Fe6>?468?'0j*M 680O40OFeE8F@{0i3I?;cC68Q
O'0/so1
001
2ÇU,3IC09
F3575OA71
?*9.2<68?*Q<O,3IE>@,1$@0OFV;,3503tUC1;.*7F;As'mS0O*F:01
UAU35C0W
Cu
“L
—n˜L™ œ ë°|¬å4âå'±å'ä®*¯©«°±ï
kF?FLC6>7 !% 35?*; !% 1$UK
FLC350681
?*935CF¥2c35UUoFL;¤0168?90C.7L06>1$?9]1
@c0O*F¥035CQ$F0}U*Ey350K
@B1
C24Wۮ1
CwFHu352<U*E>Fj .*968?Q†SaTŽ\6>?'0C68?9687'je3I? !% 1$UK
FLC350681
?ZM 6>0O^91
2TFTU,3IC0687.Ey35CRs'm'0FeU,3I00FC?9:735?^soF[243IUUoF;
! *!%* 35?;
! *!%
Î W}²k0OFC9D7'3I?_soFi243IUUoF;
01
! Ï M OFCF]0OF†UoFLC2[.*0350681
?šU3500FC?€7'35?šsoF†U*CFK
01
7L1
2<U*.0F;~s,359FL;A1
?A0O*F:.?*U,3I7Pl'68?Q[@357L01
CW
•”
—”
–”
¢ F:Mk1$.E8;AE868lFR01<Uo1$6>?'0 1$.0 0O,3I0G6>?*71
CUo1$C35068?QS7L1
?'JFC9681
?
O35?*;E868?QD6>?'01D0OF/96>2T;68='350681$?x@{C3I2<FM1
Cli689v2435;*FVF'3I968FC ;.*F
01g1
.C^3Is68E8680m]01gU*CF9FCJFA90C68;*FK)1
?F_3I77F99FL9~;*.C68?Q^F'35CE8m
U*O,3I9F9[1$@ 9682<;68='3I06>1$?,W~-/9e9O1M ?“68?“Æ,68Q
.*CF ‹ juM OFL?†;FJ'68CK
0.35E868=68?QS0O*F Î#Ï& 01 L'& 71
?'JFLC96>1$?,j'0OF:90C68;FLKð1$?Fw3I77F99
,ÐÑ 6>?g0OFi1
C68Q
68?35EvE811
U†soFL71
2<FL9T0M1_¸·¸x90C68;*FK)1
?FiJFL7K
01$C“3I77F99FL9j (Ðy "Ú $Ñ 35?*; (ÐÚ "Ú Ñ WÜX68?*7F490C6>;*FK)1
?*F
3I77F99FL9435CFi7C680687'35Ek01Aso1
0O–3IQ
Q$CFQo3I06>1$?}U*O,3I9F9A3I?;–3IE86>Q$?K
2TF?'0vO,3I?;E868?Qj
s'm<243568?'03568?*6>?*QT90C68;FLKð1$?F?*F99v.*?068Eo;*FJ'6>C0.*K
3IE86>=350681
?j*0OF9FRF35CE8m~9682<;*68='350681
?4U*O,359FL9t735?AU*C17F99tE>FL?Q
0O
7L1
?'JFC9681
?~?1D;68roFCF?'0E8mS@{C1$2¤UC17LF9968?QT1$0OFC 1$UoFC350681$?9W
˜ !v
fw˜ ™
=yä°ª¡ !¢ƒ£ï
á ˜Píîë°ª“êãn¯®¯©«°±
&a[i+4]
90CF3524W
Q
jžç<胨©«ªgêì«©dŸå'¬
á ©«âãnäå
&a[i+4]
á ©«âãäå
s f›
unpack_high_pattern
unpack
V<4,uint, store
aligned>
&a[i]
ƒw
œ0
V<8,ushort>
&a[i]
load
V<4,uint,
aligned>
K…
Ò'#ÏÜÔÝ}Õ 'ÖÓxݛ×$ÕšÞ ÖÓAÝ
Ú
ÚÛ_
$N՛ÖÓ
Ò'#ÏÜÔ5ÕÖnÓ4
× 'ÖnÓ^ÚÚÛ
NÚÕ]&kÐÑNà
Ðy Ý
Ñ,Ó
Ï&kÐðÝ
іՖL
kÓ
&b[i]
²k?A0O*FD1$0OFCtO,3I?;js'm~CFL90C6>7L06>?*Qi96>2T;68='350681$?Z01^3V968?Q$E8F
E811
U^E8FJFEyj,º¼ó¼Âó{j0OFe68??*FC2<1$90V1
?*F'j1
?*F[2T6>99FL9:0OFe1
U*Uo1
C0.*K
?680ymT01eFH'UE81
680VX`acb†U35C3IE>E8FE86892î3I7C1
99vE811$Uw?*F909WnÆ,68Q
.*CF<
Q
68JFL9“3I?›FHu352<U*E8Fc1
@R9.75O3~E811$U¥FH'0C3570F;35?;f96>2TUE868pF;
@{C1$2Y0OF
Z35UU*E86>7350681
?“@BC1
2 Ë FCl
FE8Fm42[.*E>0682<FL;6y3 ¢ 1$ClK
E81o3I;AsoF?75O2c35Cl'9 ž 5ŸyW
!¢7£
5.2 Short loop aggregation
…1†FH'U35?;f0OF4971
UoF41$@DE811$UK)E8FJFE:9682<;*68='350681
?jG1$.Cg35U*K
UC13575O<689(01VFE8682<68?,3I0Ft68?*?FC2<1$90(E>11$U9(M 680O<9O1$C0,0C68U<71
.*?'0W
… OFGs359687/68;*F'3k689k01R71$E>Ey3IU9FV9682<;*68='35s*E>Ft9O1$C0E811$U9k68?'01RJF7LK
01
C,1$UoFC350681$?9j91/0O,3I0,0OFk?*FH'0E811
U[6>?[0OF1
C68Q
68?,3IE*E811$U<?F90
soF71$2<F90OFG?FM}68??FLC2<1
90qE811
U,W`y?<;1$6>?*Qe91oj
MkFtFroF7L06>J
FE8m
FH'U,3I?;*9~0O*FZ971$UoFg1$@D9.*s9F‡'.*F?'0~9682<;*6>=350681
?Ì0C35?*9@{1
C2c35K
0681
?*9W ¢ F:CF@BFC/01T0O689 0F75O?68‡'.FS359[¾ · 5¹vÀÁ·· g¿»» ÂI»¿¹«º¼·
¸W
… OFRCFL90t1$@,0OFR9F7L06>1$?c68E>E8.*90C350F9t1
.*CT3IUU*C1o3575Oc.968?*Q<0OF
E811
Uc68?AÆ,68Q
.*CF~S359[35?cFHu3I2<UE8F'W,Æ,68C90jMkFe68?'0C1;.*7FR9FJFC3IE
U9FL.;1T1
UoFC3I06>1$?9G0O,3I0[35CFR?FLF;F;~@{1$C/0O*6>9 FLHn3I2<UE8F'W
h c J¤
Kc
¥ƒ¦ .
Ï
Ï s !& ‚ ¥ƒ¦ §Na
D‚^
e‚§N4L„„„<UoFC@{1$C2<9C§šCFLK
;.7L06>1$?9w‚{1$@v1
UoFC3I0681
? ¥ƒ¦ „k68?gU35C35E8E8FEyjuM O*FCFSF'3575OgCFLK
;.7L06>1$?“1
UoFLC350F9D1JFCV}
;*68906>?*70eJ3IE8.F9W<… OFS;3503T68?
0OFtJF701$Cv689v68?0FLCE>F3J
F;,joº¼ó{Âó¼j$0OFtpC90w
§ J35E8.*F9e35CF/0OF
pC90:FE8F2TF?'09R6>?ZF'3575Og1$@k0O*FZ
§ CFL;.7L06>1$?9jo0OF[?FH'0F§
Ï
s
!&,Ô
[‚
L„ Û UoFLC@{1
C2T9G3CF;.*70681
?w‚{1
@1
UoFLC350681
?
„ 1J
FC435E8E ¥FE8F2<F?'09<1$@:JF7L01
C Y35?*;}Q$F?FLC350F9^3
t
96>?*Q
E8FeCF;.*70681
?~J3IE>.*F'W
¥¦
´
´
J3IE>.*F9c3ICF~0O*Fi9F71
?*;]FE8F2<F?'09T68?]F'3I7PO]1
@G0O*FwCFL;.7LK
06>1$?9jG35?*;“9141
?Wc… O*FiU,35C3IE8E>FLE CF;.*70681
?†Q
FL?FC3I0F9c3
JF701$C 1
@ xCF;*.70681$?AJ3IE8.F'W
N§
§
¨
^
§N4
´
L & ‚ [‚
L„ ,„:Q
FL?FC3I0F9“3x?*FM D‚
e‚ L„„
JF7L01
C:M O*FCFTF'3I7PO^1
@q0OF[J3IE8.F9/6>?^0OFD1
C68Q$6>?35EqJF701$C
35U*UoF'35C9 A0682<F9j71$?9F7.*068JFE8mW
UO'm'9687'35EoJ
F701
C9W X68?7Ft;68CF70O,3I?;E868?QD1
@z?1$?i90C6>;*FK)1
?*FS357LK
7F99FL9D689:?*1
0:0O*[email protected]$@k0OF[U,3IUoFCj|0O*F[2c35UUoFL;Z71;*F9w35CF
1
2T6>00FL;,W
´
L ‚ [‚
L„ [„*Q
F?*FC350FL9t3(?*FM D‚
e‚
L„„
JF7L01
CW~`y?“0OFi?FLMdJFL701
Cjn0O*FSpC90
zJ35E8.FL9D7L1
CCFK
9Uo1
?*;9~01}0O*F Œ
š‘
³ 0OÌJ3IE8.F9~6>?–0O*FZ1$C6>Q$68?,35E
JF7L01
Cjo35?*;i0OF P³ 0Oi?FLH0
$J35E8.*F9k71$CCF9Uo1
?*;9v01e0O*F
R‘$³ 0O[J3IE8.F9z68?D0O*F1$C68Q
68?,3IEJF701$CWz… O6897L1
CK
CF9Uo1$?;9R01“35U*UE8m'6>?*Q†3e9E>68;*6>?*QAM 68?;*1M1$@ FE8F2<F?'09
35E81$?Q:0O*Fk1
C68Q$6>?35E*JF701$CW V1$0Fv0O,3I0 †71
.*E8;TsoFe3(?FQ35K
068JFi‚{.*?;FLCÉ1MD’51JFCÉ*1MÌJ35E8.*F9 2[.*90[35E891<soFR7'3ICF@{.*E>E8m
71$?968;FCFL;,„W
`?^0O689eFHu352TUE8F'jzs'm_3IQ
Q
CFLQo35068?*Q «K)E811
U“68?'01†3D96>?*Q
E8FSJF7LK
01
CR903I0F2<F?'0j|MkF43ICF^35sE8FS01~96>2T;68=FS0OF «K SE811
Ug?F90R01$K
Q
FL0OFCWÍaT1
90i682<Uo1
C03I?'0w1$@w35E8Eyjv0OFAFH'U35?;*F;f9682<;*68='350681
?
971$UoFc35E8E81M 9R2<1
CF[F§<768F?'0/MR3"m'9:1
@qFH'0C357068?*Q“X`acb›U,3IC35E8K
E8FE868924WuÆ1$CnFHu352TUE8F'jMkF:35CFV35sE8Fq01GFH'UE81
680n0O*FCFL.9Fq1
@ &kÐÑ
Ðy Ý
Ñ 357C1$99 K)E811
Uj
2435?*6>@BF90F;^3I99.*sK)1
?*F 90C6>;*F9Wn`0
35?*;
35E891<FL?,35s*E8F9 0OF:0C3I?9@B1
C243I06>1$?A1
@v3tO*1
C68=1
?'03IEuCF;*.70681$?~01
3/2<1$CFRF§<768F?'0GJFC0687'3IEuU35C3IE>E8FEnCF;.*70681
?,W
²k?“0O*Fw1$0OFCDO,3I?;juFJF?g6>@GMFw@"3568Ev01c9682<;*6>=LF K)E811
UN35@BK
0FC<9O*1
C0<E811$Uš3IQ
Q
CFLQo350681$?,jkMkF~7'35?_9068E8Et93I@{FE8m†9682<;*6>=LFA0OF
Ï !& j'M O687POx6>9G0O*FR1
C68Q
68?,3IEn68??*FC2<1$90tE811$Uc71
2<U*.03I06>1$?,W
.§
s ©
\^\^\ ©]¬
1
:« ©«
1J \^\^\ 41a­©¬
€u
E
ª
^
« ©«%
U« ©O«
H©
+©
1
— °ä¯Sì«°|°ê›®ââäå⮯©«°±nïʅ OFA68?*?FC2<1$90 «KðE811$U›68?fÆ,68Q
K
.*CF~R689/96>2T;68='35s*E8F[M 680O_3:CF;.*70681
?_3I?;c0M1S90C68;FK)1
?*FA3I7K
vÐ Ý
Ñ W X68?7F 0O*F E811
USO,3I9:3q0C6>U
7LF99F9j
?,3I2<FE8m &kÐÑ 3I?;
7L1
.?'0,1$@È Œ j$0OFvE811$U<7'35?TsoFv9682<;68=F;T6>?'01<3968?Q
E8FG90350FL2<F?'0
1$UoFC35068?*Q^1$?–3TJF7L01
Ce1
@ È Œ FLE>FL2<F?'09Ww… O*FSE>11$U]?F90~35@B0FC
9682<;*68='350681
?c689t9O1M ?xsoFLE>1MDW
js f›
ˆw
K…
Ò'#ÏÜÔÝ_Õ 'ÖÓxݛ×$ÕšÞ ÖÓAÝ
Ú
ÚÛ_
ÌÕ¥ÖÓ
ÌÕÌ
NÚ_Ï !&,Ô"Ú,)&kÐðÖ
Ñà
Ï'&ÐðÝ
іՖ$kÓ
N˜4v® s Ð
› ÝN˜4v®!
› Ý
ÑÛoÓ
s
0œ 
Q°|°êbIì«å Boå'ìv®ââäå⮯©«°±nï … O689AU*O,3I9Fg9682<;68=FL9A0OF^?1M
68?*?FC2<1$90¯ K)E>11$U,W“`0TCF71
Q$?68=F9 $ 359^3SUC68J350F~J3IC63IsE8F'j
œ Ï*&kÐðÝ
Ñ 3I9t3(90C68;*FK)1
?F:3577LF99F9j3I?; Ï s !& 359t3(CF;.*7K
0681$?c1J
FC[3/JF701$CW(-/99.2<68?*Q^35E8En;3503<3ICF
@"35701$C/735?AsoFR71$2<U.*0F;†3I9j
S°8–‘
•f&L
L'& j*0O*F:sE8175l68?*Q
f +'#Ò ‚ '& „„N8̑
•&ÈP8]È \
X682<;68='3I06>1$?›1
@ 3I?; œ ÏL&kÐðÝ$Ñ 689S90C3I6>Q$O'0@{1
CM:35C;W
Ë .0w0OFcO,3I?;*E>68?*Q†1
@ Ï s !& 689w2<1
CF471$2<UE8687'3I0F;–soF7'35.*9F
;3503“68?'J1
E8JF;€6>?0O*F]CF;.*70681
?Ç35CF_?1$0Z90C68;*FK)1
?FN3I7C1
99
¯K)E811
UW XUoF768p*7'35E8E8mj &kÐðÖN˜4v
® Ñ 6>9~?1MÇE>11$UK)68?'J3IC63I?'0“‚º¼ó{Âó¼j
› ÝN˜v®
› Ý
Ñ O359c3<90C68;Fi1$@:¬ ‘fI& È Œ W^… O*F
90C68;*F~=FLC1o„T3I?;±s Ð4
Q$1o3IEn689/01T96>2T;68=F Ï s !& 68?01c3/È
K)MR3"m Ï' Ï s !& W
® Ñ 689<1$@/90C68;F~=FC1jq0142435l
Fx0OFwCF;*.70681
?
X68?7F &kÐðÖ+˜v
3cÈ
K)M:3mfU,35C3IE8E>FLERCF;.*70681
?,j F'3I7PO–1
@D6809xFE8F2TF?'09A?FFL;9x01
® Ñ ð Èo„WšÆ1$C
soF4CFU*E86>7350F;–È]0682<F9jDº¼ó¼Âó¼j & ‚ &kÐðÖ+˜v
s Ð
› ÝN˜4v®!
› Ý
Ñ jo0O*Fe@{1
.*C/J
F701
C9t01SsoFeCF;.*7F;A68?cU35C35E8E8FEG3ICF
s Ð
› ÝN˜4v®!
› Ý
Ñ j \^\a\ j9s Ð$› Ý!›fvN˜vf®!
› Ý!›f$v Ñ WªVu 1$0FA0O,3I0j0OFc7L1
CK
CFL9Uo1
?;*68?Q^FE8F2<F?'09<1$@V0OFwÈ^;,3503S90CF'3I2<9S@{1$C2h3iU3575lF;

J
F701
CT352T1
?Qi0O*F2<9FE8JF9 Wq…1SUC1;*.7F~3:È
K)MR3"m~U,35C3IE8E>FLECFK
‰ be‚‘
•
;*.70681$?,jF'3575OAFE8F2<FL?0G1$@,0OF:1$C6>Q$68?,35EnJF701$C ?FF;*9G01<soFRFH'K
U35?*;F;Zsm_3IUU*E>m'68?Q“3[9E868;68?QAM 68?*;1M1
@ È~FE8F2<F?'09jvº¼ó{Âó¼j
$ ‚ Ð Ý
Ý
Ñ Èo„W
… O*FR71;Fw3I@{0FCtE811
U*KðE8FJ
FEu9682<;*68='350681
?c689G9O1M ?AsoFLE>1MDW
¬
s ²s › N˜4v®!› ^¬
šw
”
”
œ0
B
7…
fw
Ò'#ÏÜÔ"ÝfÕ 'ÖnÓ4}×$Õ€Þ ÖÓ4ÚÕ Û}
L
€Õ£ÔÖn"Ö"ÖÖ*Û|Ó
L
€Õ
L
NÚ_Ï
Ï !&,Ô"Ú (" &Ô
&ÐðÖ
$ÑÛ$à
uÔ Ð Ý
Ý
Ñ, ÛÛ|Ó
Ï&kÐðÝ yÝ$Ú ÑÌÕ
Ó
”
N˜v®
N˜ !v
”

w
 s

s s › N4˜ v® › ›7w
s
œ å u©«ä¯ã®*ì«©«­®¯L©«°±ï
ˆ 9F.*;1¤1$UoFC350681$? Ï
Ï !& j
L& j 3I?; $
35CFi243IUUoF;Z01c1
UoFC3I0681
?9D1
?
…
s
O689:7'3I?^soFx35.*01
243I0687'35E8E8mc;F;*.7FL;^s359F;41$?^0O*F[90C68;*F[1$@
0O*FG1
C68Q
68?,3IEJF7L01
CW Ë FL7'35.*9F/F'3I7POS1$@o0OFGÈR90CF'3I2<91$@|;,3503k01
soFkCF;.*7F;T68?[U,35C3IE8E>FLE689,1
ro9F0FL;<s'm :‘ IÈ Œ 1
@0OFvJFL701
C,0ymUoF
e‚{È Œ '& „jº{ó¼Âó¼js'mD0OFtE8F?Q$0OS1
@k35? '& j
0O.*96891
@z90C6>;*F :‘
3I2<1
?*Q/7L1
CCF9Uo1$?;68?*Q/FE8F2TF?'09 357LC1
99,;68roFCFL?0z;,3I0390CF'352<9W
³¬ &
¬
W1
js f›
O1 ¯
H¯
‚¯
s
6. DEVIRTUALIZATION
MODE SIMDIZATION
AND
MIXED-
¢ Fq7'[email protected]*FCnFH'0F?*;R0OFq71
?*7FU*0n1
@J'68C0.,35E868='3I06>1$?T01GJF7LK
01
CR1$UoFC350681$?9WD`y?ZFL99F?7Fjz;.*C68?QwF'35CE8m4UO359F9R1$@k9682<;68='3IK
0681
?j35?<1$UoFC350681$?S7'35?<soF[3IQ
Q
CFLQo350FL;w68?'01i3J
F701
Cq1
UoFLC350681
?
FJFL?D0O*1
.*Q
Oe0OFq1
UoFC3I0681
?T689?*1
09.*UUo1$C0F;esm/0OFO,35C;*MR3ICF'W
-G0G0OF:;*FJ'6>C0.35E868='350681$?^U*O,3I9F'j'0O*FRp?35Ez;F7689681
?c689t2435;*Fe1
?
M OFL0OFCw01“243IUÍ3xJF701$Cw1$UoFC350681$?Ì01Ì3w96>?*Q
E8FfX`acb£68?*K
90C.7L06>1$?,jo3v9F‡'.FL?7FG1
@X`acb“68?90C.7L06>1$?9j
1$CR3v9F‡'.F?*7FG1
@
97'3IE3ICG1
UoFC3I06>1$?9js,3I9F;x1$?†3 71
90G2<1;*FEyW X68?7FV0O689v975OF2<F
F?35sE8F9t.9t01SQ
FL?FC3I0Fx3V2T6>H'0.*CFR1
@tX`acb35?*;c97'35Ey35C/71;FL9
M 680O68?€3iE811
UjqMFxCF@BFC<01^0O689<71;*FxQ
FL?FC3I06>1$?}975OFL2<F†3I9
2<68H'F;K)2<1;*F:9682<;68='3I0681
?,W
¢ F]p*C90Z;*6>97L1J
FCZ0O*F]?FF;1$@S2<68H'F;K)2<1;*F_9682<;*68='350681
?
M OFL?ÌMFgCF'3IE86>=LF“0OF «O*F0FC1
Q$F?FL1
.9 }?,3I0.CF^1
@D71
2<U*.03IK
0681
?†68?'J1
E8JFL;“68?Ì3SE811$U,WxÆ1$C[FHu3I2<UE8F'j 3<E811
U]243"m^71
?'03568?
71$2<U.*0350681
?“0O350R7'3I?gsoFSF§T768F?'0E>m4FH'F7L.0F;Z1
?g0O*F<97'3IE3IC
.?*680/1$?E8mj*1
?c0O*F~X`acb›.*?680/1$?E8mj*1$C/1$?^so1$0O,W
96>?*QiSaTŽ
359<35?cFHu3I2<UE8F'j;*1
.s*E8FK)É1o3I0/7L1
2<U*.0350681$?c2[.*90/soFeFH'F7.*0F;
1
?^97'3IE3ICe.?6809j9350.*C350F43IC680O2<F0687<689RsoF00FLC:UoFC@{1$C2<F;Z1
?
3RX`acb“.?680jM O68E8F/2<1$90kp*HFL;TUo1
68?'0q1
UoFC3I06>1$?9v735?SsoFG71
2TK
U.*0F;x1$?xso1$0OA.?*6>09WnÆ.C0OFLC2<1
CF'j968?7FwX`acb}.*?6809D35CFe68?
Q
FL?FC3IEt2T1
CFx7L1
?90C3I68?F;_0O,3I?_0O*F~9735Ey35CS1$?F9j,91
2<FL06>2TF9
680[2c3m^soFi2<1
CFiF§T768F?'0[01cUoFC@B1
C2î71$2<U.*0350681
?†68?†97'3IE3IC
2<1;*FR6>@ 3577FL99F9S3ICFR2<68935E868Q
?FL;c1
CG?1$0t90C68;*FK)1
?FW
²k?F“35U*UC1o3I7PO}01g9682<;*6>=LFAOF0FLC1
Q
FL?F1$.9iE811
U9i689S01g;*689K
0C68s.*0F 0OF E811
US91R0O350q1
?F 7L1
?'03568?9V35E8E1$UoFC350681$?9q01RsoF FH'K
F7.*0F;x1$?x0O*F:JF701$CG.?680j|35?*;x0O*F:1
0O*FC M 680OA1
UoFC3I0681
?9G01
soF(FH'F7.*0F;R1
?R97'3IEy35C.*?6809W|… O*F2c3 ñ 1
Cn;*C3"M s,3575l:1$@E811$UD;*689K
0C68s.*06>1$?T689,0O,3I0,680,7CF'350FL9q2T1
CFvE811
U*9(M 6>0O[9O1$C0FC,E811
U<so1;*K
68F9Wk… O689tMk1$Cl9<35Q3568?90/0OFRFH'UE81$6>03I0681
?41
@,68?90C.*70681
?*KðE8FJ
FE
U,3IC35E8E8FE86892î‚{` ˆ „j3I9k680k;*F7CF'3I9F9v0O*F/968=Ft1
@zs,3I96>7tsE8175l'9Wn`?
@3I70j*1JFCE8m“35Q
Q$CF9968JFDE>11$U4;6890C68s.0681$?c6>9t1
?*Fe1
@(0OFR243 ñ 1$C
7'3I.9F9t1
@9682<;*68='350681
?cCFLE3I0F;AUoFC@B1
C243I?7Fe;*FQ
C3I;,350681$?,W
¢ 680Oi2<68H'F;K)2<1;*F/9682<;*6>=350681
?j'MFV?1$0v1
?*E8m43"J1
68;wO.*C068?Q
` ˆ 359E>11$U~;*6890C6>s*.0681
?i;*1F9j
s.*0243"m[@{.C0O*FCkFL?O,3I?7Ft` ˆ
359q0OF 975OFL;.E8FCq7'3I?<?1M_.068E86>=LF/so1$0O4X`acb¥35?;T97'35Ey35C.?*6>09
35?*;SCFQ
6890FC9:350q0OFG9352TFt0682<FW X1
2TF0682<F'j$680q6>9?1$0q90C3I68Q
O'0K
@{1$CMR3IC;~01D;F7L6>;*F/1$?iM O687POi.*?680k0O*F/U*C17F9968?QD689v2<1
CFtsoF?*K
Fp*76y35EyW VF?*7F'jn1
?*F~2D.90e03IlFi6>?'01}357L71
.*?0Dso1
0O†O35C;*MR35CF
71$?90C3568?'09[35?*;xCF91$.C7Fe71$?90C3568?'09G1
@7L.CCF?'0 UC1$Q
C3I2ÜFH'K
F7.*0681
?<M O*F?<;FL768;68?Q:O*1M_01V;6890C68s.0F 7L1
2<U*.0350681$?4357C1$99
X`acb€3I?;x9735Ey35CG.?*6809WnÆ.C0O*FC2<1
CFj1$?F:2c3miFH'U*E>1$680 so1
0O
SaTŽò35?*;Z97'3IEy35CD.?6809:@B1
Ce0OFT9352<F<1$UoFC350681$?–350R0O*F<9352<F
0682<F'WÆ1
CGFHu352<U*E8F'j*1
?*FR7'35?c6899.*Fx‘VJ
F701
CT35;*;]35?*;]‘V97'3IE3IC
35;*;–350e0O*F<9352<Fi0682<F^3I9[68@ FH'F7.*068?Q†3cX`acb¤3I;;Z1
?–3côIK
FE8F2<FL?0K)M 68;FwX`acb}.*?680W
—‡
†‰
z
U´
Æ.C0OFLC2<1
CF'jo968?7FT0OFCF43ICF<;68roFCFL?0RM:3"m9R01~;6890C68s.*0F
7L1
2<U*.0350681$?^soFL0MkFLF?}X`acb3I?;497'3IE3IC:.?*6809/;*FUoF?;*68?QS1
?
0O*F7L1
?'0FH'0n1$@0O*FFLHFL7.0681
?j;FJ'68C0.,3IE>68='3I0681
?DUC1J'6>;*F9n.*9n0O*F
É*FH'68s68E86>0ymA01wCFJFC0/91
2<F[1
@k0O*F[E8F99V1
U068243IE,E817'35Eq;F7L6>9681$?9
2c35;FtF'3ICE>68FC M O*F?i2<1
CFt68?@B1
C243I06>1$?x689R3"J3568Ey35s*E>FW,Æ1
CkFLHn3I2<K
U*E8F'j';*.C68?QDs,3I9687K)sE817PliE8FJFLEz9682<;*68='350681
?j1$?FV2c3miU3575lS?1
?
90C68;*FK)1
?F“3577LF99F9i68?014JFL701
C9j(O1
U*68?Q40O,3I0<0OF9F~JF701$C9
2c3m~soF71$2<Fe90C6>;*FK)1
?*Fx3I@{0FC/E811
UK)E8FJFLE 35Q$Q
CFQ350681
?Wv`@,0O,3I0
689:?*1
0/0OFD7'359FA35?;40O*F[U3575l68?*Qw1JFLCOF'3I;^689:011w968Q
?*6>p*7'35?'0j
O*1MkFJFLCjMkFk7'35?[906>E8ECFJFC0n0OFv1JFCE8me1
U*0682<68906>7 U3575l'6>?*Q/;*FK
7L6>9681$?xs'm<;FLJ68C0.35E868=68?QT0O*F/J
F701
Ck1
UoFC3I06>1$?9 s3575l<01[9735Ey35C
1$UoFC350681$?9W
7.
EXPERIMENTAL RESULTS
… *
O FxU*C1
Uo1
9FL;}9682<;*6>=350681
?›@BC352<FLMk1
Cl]689<682<U*E>FL2<F?'0F;_6>?
` Ë ac³ 9[Ž/ ›UC1;*.70R7L1
2<U*6>E8FCjnM O*687PO“9.*UUo1$C09D2D.E8068UE8FSU*C1
K
Q$C352<2T6>?*QAEy35?*Q
.,3IQ
F9~3I?;gQ$F?FLC350F9RO*6>Q$OE8m41
U*06>2T6>=LF;g71;*F9
@B1
Ce2D.E8068UE8FS035CQ$F0e243575O68?FL9W ˆ C681$CD01x96>2T;68='350681$?,jv3eM 6>;*F
C3I?Q$Fk1
@*O68Q
O*K)E>FLJFE1$U0682<68='350681$?9/35CFUoFC@{1$C2<F;,j9.75O~359E811$U
;*6890C6>s*.0681
?^3I?;SE811
USJ
FC9681
?68?*QoW ²k0OFLCqO*68Q
OK)E8FJFLE1
U*0682<68='35K
0681$?9}35CFÌ3IUUE868F;¤35@{0FLCZ9682<;*6>=350681
? 3I94MkFE8Ec3I940C35;680681
?35E
s3575lF?*;x1
U*0682<68='350681
?*9W
²k.*Ce96>2T;68='350681$?_68?*@{C3590C.*70.CFw689[C3IU68;E8mZ24350.*C6>?*Qoju7L.CK
CFL?0E8m}96>2T;68=68?Q]68??*FC2<1
90~E811
U9xM 6>0O¥90C68;*FK)1
?F^2<F2T1
Cm
3I77F99FL9g3I9SMkFE8E[359S68?*;.7L06>1$?,j,CF;.*70681
?jV35?*;]UC68J3I0FxJ35C68K
3IsE8F9W“`0TUoFC@{1$C2<9S68?0FLCUC17F;*.C3IED35E868Q
?2TF?'0^35?,3IE8m9689W“`?
0FLC2<9i1
@w35E868Q
?*2<F?'0iO,3I?;E868?Qj680iO,35?*;E8F9iE811
U*9w1$@R2[.*E806>U*E8F
903I0F2<F?'09GM 680O]35Cs*680C35Cmw2<68935E868Q
?2TF?'09Wq`0 9.*UUo1$C09tE811$U9
M 680O›2T6>H'F;};,3I03w0m'UoF9W_`0S9.U*Uo1
C09Ss359687K)sE8175lš3I?;fE811$U
E8FJ
FE9682<;*68='350681
?j 359eMkFLE>E:359~3[U*CFE86>2T6>?35Cm^JFC9681
?g1
@ 9O1$C0
E811$U_35Q
Q$CFQo3I0681
?,W
aTF359.CFL2<F?'09t35CFvUoFLC@{1
C2TF;T1$?c3q` Ë a ˆ 1MkFC ˆq‰]ˆˆq‰ Š
‹IŒ
U*C17F991$Cg@{1$.?*;€68?š-VU*UE8F ˆ 1MkFLCac357 RôgM 6>0O€@{.E8ExX`acb
qF701$CSaT.*E>0682<FL;6y3DFŽ/0F?9681$?f‚{<aTŽS„(9.UUo1$C0<3I?;4C.?*?68?Q
.*?;*FCcaT- ‰ ²RXŽSWu`y?N35;;*6806>1$?]01Z0O*F“ô<97'3IE3ICS.?*6>09A‚”ip*H
Uo1$68?0jo”vÉ*1o35068?*Q[Uo1$6>?'0jo3I?;Z‘vsC35?*7PO„j$0OF ˆqˆ‰ Š$‹5Œ U*C1J68;*F9
”xX`acb̍SaTŽ£.*?6809~‚‘x3IC6>0O*2<F0687Z35?*;¥‘[UoFC2D.0F„kUE8.9 ¡ ”
3I;;*6>0681$?,35ED‘$•5K)s'm'0FwM 68;*F~JFL701
C[CFQ
6890FC9W4… OFgX`acbš.*?6809
9.*UUo1$C0/JFL701
Ct1
@ !ÎÏ j Î#Ï
& j '& jn35?; Ò#& Wv… M1w2TF2<K
1$Cm<.?*6809R35CFt9O,3ICF;isoF0MFF?i0OFG97'3IEy35CD35?*;SJF701$Ck.*?6809Wu`?
J
F701
Cn2<1;F'j0OF2<F2<1$CmR.?*6>09u9.U*Uo1
C01$?E8mw‘
•IKðs'm'0FV35E868Q
?FL;
2TF2<1
Cmg357L7F99F9W
µL
7.1 Kernel Results
¢ F4CFUo1
C0w68?ÌÆ,68Q$.CF Š 0OF49682<;68='3I06>1$?N9UoFLF;.*U›@3I701
C9
I3 7PO*68FJF;_1
?_968H†9768F?'06>p*7†3I?;]2[.*E806>2TF;6y3wl
FC?FE89W ˆ FC@B1
CK
2c35?7LF<689RCFUo1
C0F;f359w3e9UoFF;*.U4@3I701
C~3575O68FJ
F;Zs'mA0O*Fc3I.K
01$24350687'3IE8E>m~9682<;68=F;~E811
UA1JFC 0O*FV9F‡'.*F?'063IE|JFC9681
?~1
@0O*F
93I2<F:E811
Uw71$2<U68E8F;†3I0v0OFt9352TFV1
U*0682<68='350681
?~E8FJFEyW… 682<FV689
2TF'359.*CF;xM 680OxO35C;*MR35CFV71
.*?0FLC9e35?*;~68?7LE>.*;F9D3I?'mSsC35?*7PO*K
68?*Q[1JFCO*F'35;j|35;;*CF99v71$2<U.*0350681
?w1JFCO*F'35;jo35?;g35?'m<FLH0C3
7L1;FR68?'0C1;.7LF;A01T9FL0.UA0O*F:9682<;68=F;x71
2<U*.03I06>1$?9W
… O*FTlFLC?FE89S3ICFTFH'0C3I70F;4@{C1$2\CF'3IEt35UU*E86>7350681
?*9R0O,350/68?K
7LE>.*;FA?'.*2<FC687'35ET35U*UE8687'350681$?9g‚ C1$.068?F9„jqJ68;*F1¥3IUUE868K
7350681
?*9x‚ Î ' j L „jv3I?;^71
2T2[.*?687'350681$?
Ù f3I?; ÒÏ „W ¢ F4Q$6>J
Ff3x2T1
CF4;F03I68E>FL;
3IUU*E>687'3I0681
?9†‚
;*F97C68U0681$?A1
@,0O*F9FRlFC?*FE89D35?;x0OF68C 9682<;68='3I0681
?csoFE81MDW
› s
¶!·f¸0¹ ¸
s ” s
Anì«®¨ï«¨¬°¯Lêä°z¬ 68943<?.*2<FC687'3IE ;1
0[UC1;*.70[C1
.068?*F~71$2<K
U*.068?Q»º à7¼ M O*FCFº“3I?; ¼ 3ICF~968?Q$E8FxUCFL76896>1$?]JF701$C9W_²k?
0O*F ˆqˆ‰ Š$‹5Œ jzMkF<M1
.E8;ZFH'UoF70R.U^01†3e@3I701
Ce1
@:”D9UoFFL;.U
682<U*C1JF2<F?'0:‚3 È$K)MR3"m^X`acb†É*1o3I06>?*Q[Uo1$68?0k.?680qJ'9Wo” 9735Ey35C
É*1o3I06>?*Q†Uo1
68?'0i.?6809„W ¢ F†3575O68FJF_3~9UoFLF;.*U›1
@i‘$W ‹ Èoj E8F99
9
8.11
8
Speedup Factor
7
6
5
4
3.13
2.87
3
2.08
2
1.74
1.59
1.52
1
¾
su
m
he
ck
vi
de
o.
al
ph
ab
le
nd
in
g
tc
p/
ip
.c
bl
as
.s
ax
py
vi
de
o.
su
bd
iv
id
e
m
O½
á «© âãäå çDèwë
oå'ä±å'쫨ï
@
bl
as
.s
do
tp
ro
d
bl
as
.s
ge
m
ds
p.
fir
0
E ©«å oB å¬x¨©«ª“¬©«­®*¯©«°±4¨ê(åå'¬ãnê¨=ð°äFB®ä©«°ã¨
-VE868Q
?*2<F?'0
ÆF350.CFL9
…mUoFL9
sEy3I9W 9;*1
0U*C1;
sEy3I9W 9Q$F2<2
sEy3I9W 93IH'Um
;9UW pC
0Uo7'’I6>UW 7PO*F7Pl'9.*2
J'68;F1W 9.*so;68J'68;F
?1$?F
?1$?F
?1$?F
C.?'0682<F
C.?'0682<F
?1$?F
CF;*.70681$?
É*1o350
É*1o350
É*1o350
9O*1
C0 A6>?'0
9O*1
C0 A>6 ?'0
É*1o350
J'68;F1W>3IE8UO,3IsE8F?*;
?1$?F
FC?*FE
'À Á E
CF;*.70681$?
CF;*.70681$?
s359687esE817Pl
X`acb
¿
¿
„=R@oå'ä±å'쫨ï
á ©«âãnäåcæ ç
¿
¿
75O,3IC c9O*1
C0
9O*1
C0 A7PO35C
®*ä®*ë¯å'ä©«¨¯©«ë¨S°
0O,3I?AUoFFli;*.F:01<0O*FR2<1
CFRE8682<680F;_3I;;CFL996>?*QS2<1;FL9t1$@,0OF
SaTŽN.?*6>09GM 680OACF9UoFL70G01T0OFR9735Ey35Ct.?*6>09W
Aì«®*¨ï«¨âå'ª“ª 689š3f?'.2TFC687'35E~24350C68H£C1$.068?F–71$2<U.*068?Q
Îà º àK
¼ Ú&'à ·“M OFLCFšº'j ¼ j:35?*;·_35CF^96>?*Q
E8FgU*CF7689681
?
243I0C6>7LF9Wu… OFqC350681t1
@'97'3IE3IC,J'9vX`acbAÉ135068?QtUo1
68?'0n.*?6809u68?*K
;687'3I0F9V3UoFFlD9UoFF;*.UT1$@q”
Wu… O*FG91
2<FM O350q92435E8E8FCq9UoFF;*.U
3575O68FJ
F;–‚‘
W8ô Š „ 6>9DUC68243IC68E>mZ;.*F<01c0OFSU*CF9F?7LFS1
@ 71$?0C1$E
É1M–71;*F9G;689U,3I07PO*6>?*Q<01<;*6>roFLCF?'0 9UoF76y35Eu7'359F9W
Aì«®*¨ï«¨®'lzêué
Îà7
Ã ÚƒÄ M
6>9ƒ3 ?.*2<FC687'3IENJFL701
CÜC1$.068?FY71$2<U.*068?Q
O FCF
*
35?;
35CFG968?Q$E>FGU*CF7689681
?SJF7L01
C9W ¢ O*68E>F
.Ux01^3V9UoFF;.*Uc@3I701
C/1
@t”:7'35?csoFw3I7PO*68FJF;c1$?c0OFR71$2<U.*K
0350681$?,j$2<FL2<1
Cm[6>?'0F?*968JF lFC?*FE89q9.*7POc359k0O*689q735?^3575O68FJ
F .U
0143/@"35701$C/1$@,È<1
?xE>135;*9<3I?;x901$CF9W,… OFw3575O68FJ
F;A9UoFF;*.Uj
”
W8 ‹ j*689G68?xsoF0yMkFF?x0OF:0yMk1<so1$.?;*9W
Ã
Ä
dŸ
¬¨êï nä
689–3]p*E80FC68?QÌC1
.068?*F9“1
@B0F?@{1$.?;Í68?µb:X ˆ 3I?;
71$2<2[.*?687'3I06>1$?†3IUUE8687'3I06>1$?9[‚Âó¼»ó¼j RX*ac„j
96>2T6>Ey3IC/01D0OF/1
?F
9O1M ?i68?iÆ,6>Q$.CF<‘
Wn… O689vU35C0687.*E3ICk68?903I?7F/O,3I9kÈ Œ 035U*9R3I?;
UC17LF99S3I?^68?*U.0G1$@V‘$” Œ 9O1$C0VJ35E8.FL9Wk… OFeCF;.*70681
?c689VUoFLCK
@{1$C2<F;–3I9e6>?'0FQ$FC~‚{CF‡'.68C68?Q~E>FL?Q
0OZ71
?'JFLC96>1$?,„k68?“U35C35E8E8FEyj
35?*;}6809i1
.*0U.*0T689i97'35E8F;};1M ?fs3575l†01¥3w9O*1
C0WN²k?E8m†0OF
68??*FC2<1
90tE811
U4689V9682<;*6>=LF;cUCF9FL?0E8mW ¢ O68E8FA3V9UoFLF;.*UA@3I7K
01
C[1
@G.U†01_”<71$.E8;†soFg3575O68FJF;†@B1
C[0OFi68?0FLQ
FC[CF;.*70681
?
‚{1
?*FVÈ$KðM:3"mgX`acb].?680J9W|”G97'35Ey35C .*?6809„jMkF:Q$F0e3G@357L01
CG1
@
‘
W8ô$”
WS… O689eE>1MFC[?'.*2[soFCV6>9e;*.F<01A0O*F<243I?;,3I01
Cm^CF'35E868Q
?*K
2<F?'0 0O350 177.*C9[359G0OF/6>?*U.*09 1
@F'3I7POx71
?*9F7.068JFVpC J35E8.F
7m'7E8FR0OC1$.Q$O†35E8EuUo1
9968sE8Fe;,3I03<35E868Q
?*2<F?'09W
)Å
6L
E @
¯ëê ©«êï«ë å'ë z¨ãª
689S3V71$2<2[.*?687'3I06>1$?4C1
.068?*FD0O350t71
2TK
U.*0F9D0OFS75OF75l'9.2Y1
@G68?7L1
2<68?Qc?*F0M1
ClZU,3575lF09D01cJFC68@Bm
0OF468?'0FQ
C680ym›1
@e0OF468?U*.0i;,3I03
W… O689xU35C0687.*E3ICx68?903I?7F
71$2<U.*0F9435?]68?'0FQ
FLC<7PO*F75l9.*2ƒ1$@<3<È
7PO35C[s.roFLCTs'm–357LK
vðÒ'Ï jo0O689VlFLC?FE90CFL99F9
7.*2[.*E3I068?Qw9O1
C0/J3IE8.F9WG n68lF
;,3I03t71$?'JFC9681
?g35?*;~CF;*.70681$?,Wn`?Z3I;;680681
?j0O689vlFC?*FEo.9FL9
³s
¾
3
Speedup Factor
2.16
ª 2
1.62
1.41
1.20
1.02
1.05
1.02
1.02
s,3I7Pl
F?;c7'3I??*1
0VCFL.9F;40OFe9682<;*6>=LF;Z68?*U.0T359VMkFE8Eyj0O.*9/CFLK
9.E8068?Qi68?A9U*.C681
.*9VE81o3I;9T35?;c;3503VCF1$CQo3I?68='350681$?9W Æ,6>?35E8E8mj
1
?*E8m“3/@BFM–E811
U9t1
@,J'680FCs*6k3ICFR9682<;68=F;W
… OFx?FH'0TsoFL?75O243ICl9T6>?*;687'3I0FA2<1
CFcU*C1
2<68968?QZ9UoFF;*.U
+ jqMkFA9.*[email protected]}9682<;*6>=LF_3wE811
U}UoFC@{1$C2<K
@3I701
C9W_`?
68?Q[9350.C3I068?Q43IC6>0O*2<F0687'W`?w9M 6824jMkF:9682<;*6>=LF:2435?'mS1$@0OF
243I6>?gE>11$U9x‚{FH'7FU*0D0O*F<1
?*F9DM 6>0Og;68J'6>;*F'„jk3I@{0FCD71$?J
FC068?Q
680/01S.*9Fe96>?*Q
E8FDUCF7689681
?4É*1o3509W ¢ FeQ
F0T3V9UoFF;*.Uc@3I701
C/1
@
‘
W ȑe68?4E86>?*U,3I7Pl~6>?4968?Q$E8FTUCFL76896>1$?42<1;F'W `?_3IE8J68?*?,j*MFA3IE>91
&#!
#Ï jV34”
W8‘
•
9682<;68=F~2435?'mZ1
@t0OFi682<Uo1
C03I?0[E811
U9W4`?
9UoFF;*.UA689T3575O68FJFL;csmi9.*[email protected]<;68=68?Qi0O*FRE>11$U40O,350
68?'J1
E8JF9[C.?'0682<Fg35E868Q
?2TF?'0j(E8F?*Q
0O_71
?'JFC9681$?,jG35?*;_CFL;.7LK
0681
?W
1.06
1
ƺ
or
bc
.a
ut
c
ee
m
.s
p
im
sp
ec
92
.a
lv
in
n
lin
pa
ck
sp
ec
95
.s
w
sp
ec
2K
.g
zi
p
er
.v
ite
rb
i
m
hm
sp
ec
2K
.b
zi
p2
sp
ec
2K
.v
or
te
x
sp
ec
95
.to
m
ca
tv
0
E B
P= UB*®*ä© I
á «© âãnäåZææçAèwë ©«å oå¬}¨©«ª“¬©«­®*¯©«°±¥¨ê(å'å'¬ãê¨ y°ä
°ã¨ (å±në ªg®ä u¨ï
A
7@
E
FLH0FL?968JFSUo1
68?'0FCw3IC6>0O*2<F0687Z‚{0O,3I0R?FF;*9e01AsoFSCFJFC0FL;gs'm
0O*F~7L1
2<U*6>E8FC„T35?;]U3599F9<0O*Fis.roFLCT1
@[‘$•5K)s680<9O*1
C09c3I9435?
3ICC3"mA1
@/5K)s*6>0t75O,35CWv… O'.9jMFe243"mA?1$0<3I99.2<FD0O,3I0/0O*Fx‘$•5K
s*680V9O1$C09:@3IE8Et350V?350.*C35EG‘$•5K)s680:so1$.?;35C68F9jCF‡'.*6>C68?*QwFLH0C3
3IE86>Q$?2<FL?0D1
UoFLC350681
?*9W~`0~3575O68FJ
F^3T9UoFF;.*Ug@"35701$CT1
@ ¡ W8‘ ¡ j
vðÒ'Ï 243I68?E8m“soF7'3I.9F~0OFiCF;.*70681
?³ 9[1JFCK
O*68Q
OFLCT0O,3I?
LvðÒÏ W
O*F'35;†35CFw352T1
C068=F;c1JFCD3tE3ICQ
FCt;,3I03/9F0G0O,3I?
±s
Bz©«¬å'°ï«¨ãA(¬©dBz©«¬å
>s
689 3Q
C3IUO6879uC1
.*06>?*F0O350z9.so;*6>J'68;FL9u0C68K
I3 ?Q$E>F[CFUCFL9F?'0350681
?*9Wt`0t689i3:2<F2<1$Cm]35?*;c71
2TU.03I0681
?468?K
0FL?968JF(lFC?*FE
0O350zCF‡'.68CF9k•5ÈGs'm0FL9u1$@;,350301 U*C1;.7LFV3?*FM
‘$•s'm'0F0C6y35?*Q
E8F M 680Oc‘$•q968?Q$E>F U*CF7689681
?[É1o3I068?Q:Uo1$6>?'02D.E8068K
U*E8mA3I?;43I;;,Wz… OF 71$2<U.*0350681
?*9:3ICFtFLHU*CF99F;43I96891$2<1
CU*O687
903I0F2<F?'09t1JFCGÈ<FE8F2<FL?09t1
@t3V90C.*70j0O.*9GCF‡'.68C68?Q<s359687
s*E817PlZ35Q$Q
CFQ350681
?x01T9682<;68=FV6>09k6>?*?FC2T1
90 E811
UW,`y0R3I7PO*6>FLJF9
3i”$W Œ e9UoFLF;.*Uc@357L01
CjM O6875OcM 68E>E,[email protected]<UC1JFL;A1
?*7F
MFR9.77LFF;A68?ACF2T1J'68?Qc3/CF;.*?;35?'0v90C.7L0 71
U'mW
B
E 'A
z©«¬å'°ï«®*ì«ê ® nì«å±n¬©«±â
689“3wQ
C35U*O6879wC1
.*06>?*FA0O,3I0isE8F?;*9
U*6870.CF9eM 680OgJ35C6y3IsE8F^352<1$.?'0R1
@k0C35?9U35CF?*7mW
?E868lFT0O*F
U*CFJ'681
.9~lFC?*FE89~0O350xU*C17F99F;d‘$•}3I?; ¡ ”As*6>0~‡'.,35?'068068F9j
0O*689klFC?*FEU*C17F99F9R5K)s680k75O,3IC‡'.35?'06806>FL9j
M OFCFT3v9.s9FL01$@
0O*Fi71
2<U*.03I06>1$?9[6>9[UoFC@{1$C2<F;]1JFCA‘
•5K)s*6>0D9O1$C09W4`y0e0O.*9
!ÎÏ 01 Î#Ï& jk0OFL?}@B1
E8E81MF;¥s'm
CFL‡.*68CF9S71
?'JFLC96>1$?›@{C1$2
Î*#Ï& s,3I7Pl_01 !Î*Ï* W›`0^3I7PO*68FJF9Z3“$W>‘$‘
7L1
?'JFC9681
?f@{C1
2
9UoFLF;.*U^@"35701$CjM O687PO^689:soF0yMkFF?40O*F[243IH'6>2D.2Ç@3I701
CV1
@V
3I?;^‘$•D3I99176y350F;wM 680O,j$CFL9UoF7068JFE8mj$9O*1
C0k7L1
2<U*.0350681$?^35?;
75O,3ICG2<F2<1$Cm“3I77F99F9W
7.2 Application Results
… OFLCF[O359:soFFL?_3eCF7LF?'0/.*U9.CQ$F[1$@7L1
2<U*6>E8FCVCF9F'35C75O^1
?
35.*01
243I0687[JFL701
C68='3I06>1$?4@{1
C<X`acbf.?6809 ž Èoj,ô
j Š j‘ Œ j‘$‘
j,‘
”$j
‘ ¡ ŸyWk… Mk1iUC68?7L6>U35E9682<;*68='350681
?}3IUUC13575OF9/O,3"JFRsoFFL?c.9F;j
0OF~0C35;*6>0681$?,35EGE811
U*K)s,359FL;fJF7L01
C68='350681$? ž8Š j/‘
”
jV‘5Èoj/‘
ôIŸtU*68K
1
?*FFCF;_@{1$C<JF7L01
C<9.*UoFC71
2TU.0FLC9 ž ‘
•
j/‘ ‹ ŸT3I?;]0OFws,3I9687K
sE8175l_35U*UC1o3I7PO ž ô
j(‘$
jq‘ Š Ÿ,p*C90VU*C1
Uo1
9FL;Zs'm ž ô5ŸyW/…n1~FH'U*E>1$680
X`acb¤U,35C3IE8E>FLE>6892
350wso1
0O¥E8FJFE89j 2<1
90~UC681
CwMk1$Cl›75O11
9F
1
?*F[35UU*C1o3I7PO^3I9k0OFL6>Cq9682<;68='3I0681
?i2<F0O*1;,j$0O*F?<71$?J
FC0(1
?F
@{1$C2Ü1
@GX`acb]U,35C3IE8E>FLE>6892Ç01c3I?1
0O*FCWn… OFLCFw35CFR0OCFLF:71
2TK
2<1$?E8m~.*9F;x0FL7PO*?68‡'.F9W
yc ÂKc ·À{ÀÁº¼¸»471
?'JFC09^s,3I9687K)sE817Pl€E>FLJFE<U35C35E8E8FE86892
»0Ç 1Z··JE8¤È
11
U*K)E>FLJFEtsmgCFC1
E8E868?Q“6891
2T1
CUO*687c90350F2<FL?09S68?'01
´
E>11$U9 ž ” Œ ŸyW… OFR;*C3M s3575li1
@,E811
UcCFC1$E8E>68?*QS6>9G0O*FR6>?'0C1$K
;.7L06>1$?}1$@S3S?FMÜ68?*?FC2<1$90<E811
U}6>?'01^0OF~E>11$Uf?*F90W
X68?7F/E811
UK)E8FJFLEz9682<;*68='350681
?~O,3IUUoF?*9e350v0O*FV68??*FC2<1$90
E>FLJFEyjCFC1
E8E868?Qx;*1F9R?1$0VFH'U35?;40O*F[971$UoFT1$@k9682<;68='3IK
06>1$?,js.*0uC3I0OFCuFH'UE81
6809s359687K)sE8175l:E8FJFE
U,35C3IE8E>FLE>689268?
E>11$U“@{1$C2<9WSÆ.C0O*FC2<1
CFjzCFC1$E>E868?Q4CF‡'.*6>CFL9D0O*F<UCFL9K
F?7FG1$@q3kE>11$Ui71
.*?0FLCjM O6875OS243"mT?*1
0/35E8MR3"m'9kUo1$9968sE8F'W
¤ ¶I·À{ÀÁ¿J|¤ ¾Iº¼¸»SCFC1$E>E89A6891$2<1
CU*O687Z903I0F2<F?'09~6>?'01Ì3
»E>Ç 1·1$·JU~
35?;R0O*F?:71$E8E3IU9F9,680z01 0OF(68??*FC2<1
90u9.CC1$.?;*68?Q
z
F CFLUo1
C0k68?iÆ,68Q
.*CF<‘$‘G0O*F/9UoFFL;.US@"35701$C9e‚{C35?*Q
68?QD@{C1$2
/
‘$W Œ ”w01f”
W8‘$•
„S3575O68FJ
F;]smg96>2T;68=68?Q Š soF?*7PO*2435Cl›35U*UE8687'35K
0681$?9W:`?4Q
FL?FC3IEjo0OFD9UoFF;*.U4@3I701
C9w3ICF<2<1$CFT2<1;*F90j(359
1$?E8mwU,35C0G1$@t35UU*E86>7350681
?*9<3ICFR9.68035s*E>Fe@B1
CG9682<;68='3I06>1$?,W(-VE891oj
9682<;*68='350681
?}3I?;A0O*F:Q
F?*FC350681$?c1
@,SaTŽ€71;F9T35CFe90CF9968?*Q
?*FMU,3IC09R1
@0OFT7L1
2<U*6>E8FC³ 9Ds,3I7PlFL?;,jCFL‡.*68C6>?*[email protected]:p?*F
0.*?68?Qt68?[1$C;FCn01V243I07POD0OFFH'UoF70F;eUoFC@B1
C243I?7Fv682<U*C1JFK
2TF?'09W
-G00O*FkU*CF9F?'00682<F'j0OF@{1
E8E81M 68?QRsoF?*7PO*2435Cl'9G3I7PO*6>FLJFv2<68K
?*1
C/9UoFF;.*U4@357L01
C9W/… O*F[s*=68Uf3I?;4J1$C0FHx9UoF7” Œ
Œ$Œ soF?*7PO*K
2c35Cl'9:3I7PO*68FJF 2<68?1$C9UoFLF;.*U<soF7'3I.9F 0OF 9682<;*68=F;SE811
U*9k;1
?*1
0q968Q
?68p*7'35?'0E8m<71$?0C68s*.0FG01R0OFG1JFC3IE>E71
2<U*.03I06>1$?,Wn… O*F
01$2<7'3I0J~soF?*7PO*2435ClSM:359t0C35?*9@{1
C2TF;A01T1$UoFC350Fe1JFC 968?*Q
E8F
U*CF7689681
?›35?;_3I7PO*68FJFT1$?E8mA2<1;*FC350F[UoFC@{1$C2435?*7FT682<U*C1JFK
2TF?'0W†ac35?'m“1
@G0O*Fw9682<;*68=F;]E811
U9A35CFw@3I6>CE8m“7L1
2<U*.0350681$?
68?'0F?*96>J
F'jM 6>0O~9FJFC3IEu1$@n0O*FV68?U*.09v;3503tCFL.9F;~6>?~2[.*E806>U*E8F
9.*sK)71$2<U.*0350681
?W ¢ FesoFE868FJF[0O,3I0<3I0:0OFeUCFL9F?'0V0682<F'j0O*F
¢
8. RELATED WORK
´
E>11$U ž8Š ŸyW: n11$UZ7L1
E8Ey35U968?*QA689i35s*E>F[01~FLHU*E81
680VU35C35E8E8FE86892
350(so1
0O[E>FLJFE89W V1MkFLJFCj680,689V35E891R2<1
CF 7L1
?90C3I68?68?Qw3I9
6>0tCF‡'.68CF9t0OFe1$C6>Q$68?,35E,68?*?FC2<1$90VE811
U401SsoFeUoFC@BF70E8m
?F90F;g01A6809[9.*CC1
.?*;68?QxE>11$UÌ35?*;–35E8Ev6809e90350F2TF?'09
soFDCFLC1
E8E8F;,WvÆ1$CVFHu352TUE8F'j*680t7'35?4?1$0/7L1
E8Ey35U9F[0OFeE811
U
9O1M ?A68?xÆ,68Q
.*CF ¡ W
)´
FC09(E>11$UK)E8FJFEU,3IC35E8E8FE86892d01
»s,Ç 35·9·J68c¤ 7K)½'s*¸bE>1c 75·leÀ¼ÀÉðp E8¿FJ¸*FÃEp%¤ U,¿
3I¶KCqÊ 35E87E8F1$E8?6>9J
2
s'mRpC90,.*?C1$E>E868?QV0OFkE811$U,j
´
0OF?}U,3575l'68?Q“71$2<U.*0350681
?¥M 680O*6>?3xs,359687cs*E>175lf68?'01
X`acb68?90C.7L06>1$?9 ž ô
j/‘
IŸWNX68?7LFA9682<;68='3I06>1$?f689SE8682<K
6>0FL;x0143Gs,359687Rs*E>175luj'680 7'3I?AsoF:JFLCmS6>?*F§<768F?'0G01TO35?*K
;E8Fi2<68935E868Q
?2TF?'0c35?*;“CF;*.70681
?WwÆ.*C0OFC2T1
CF'juU3575l'K
6>?*Qi35E8Q$1
C680O2<9V‚{F680OFLCqQ$CFF;*mK|1$Cq9F35C75OK)s,3I9F;,„0F?*;T01
soF 2<1
CFGFH'UoF?*96>J
FD35?;TC35?;*1
2<68=FL;,j3I?;<91$2<F0682<FtE>FL99
1
U068243IE0O35?ZE>11$UK)E8FJFEqJF7L01
C68='350681$?†M O687PO›35CFS1$@{0F?
s,359FL;A1
?~;FUoF?*;F?*7F:JFL701
C9W
‰ 1
2TU,35CFL;[01t0OFV35so1JFV35U*UC1o3I7PO*F9j1
.Cu97PO*F2<F6>9nso1
0Oe2<1
CF
ÉFLH68s*E>F†35?;_2<1$CFcUo1MFC@{.*Eyj71
2Ds68?*6>?*Qg0O*FA2<FC6809S1
@Vso1
0O
35U*UC13575OF9Wš²k.*C<975OF2<Fx6>9Z3IE>91gE>FL99wFLHUoFL?968JFxsoFL7'35.*9FA680
CF‡'.68CF9G?*1T75O,35?*Q
F:01TE>11$UA?FL90 90C.70.*CF9W aT1
90G682<Uo1
C03I?'0
1
@ 35E8Eyj'680 68?'0FQ
C3I0F9 ?687FE8miM 680Ox1$0OFCD3I9UoF709 1
@n96>2T;68='350681$?,j
9.75O†3I9<3IE86>Q$?2<FL?0GO35?;*E86>?*QoW
Æ1$CSE>11$U9iM 680Of2<68H'F;_;,3I03~E8F?Q$0O9jq2c35?'m]71
2<U*68E>FLC9wCFLK
91
C0V01~E811
U^;6890C68s.*0681
?^01w7L1
?90C.*70:E811
U*9:M 680O›3R.?*68@{1
C2
;,3I03:E>FL?Q
0Oj*9.75O_359/0OFe`?'0FEu71
2TU68E8FC ž È
ŸyW Æ1
CtE8F?Q$0O471
?*K
JFC9681$?,jn243I?m^71$2<U68E8FC9TFL6>0O*FCD;1A?*1
0D96>2T;68=Fi0OFiE811
U†1$C
Ð'oƒe.¤ 0e ªÝ »ã Kc
Fu
jË
Ô e Ðbo Ke
NË
ÂL
.L
PÌ Kc
Pç
Õc Kc eße
PL
Ð
ê c(Ê h J¤
¾
Ì
JiNÕ c Õc Kc eße
u
Vë
tÕc
JiFÌ Kc
Ý e.¤ Kc ì.Íc Kh
c ì Ð'o dh
Ð'o Ke
1$?E8mw96>2T;68=FeE8F?Q$0OA71
?'JFLC96>1$?9G0O,3I0[35CFR;68CF7L0E>mw9.U*Uo1
C0F;
s'm^0OFiO,3IC;M:35CF'jn9.*7POÌ3I9c3T@3I701
C[1
@[”TU,3I7Pl'68?Q’5.*?U,3I7Pl'68?Q
ž È$ŸWt… OFD-SX…€71$2<U68E8FC ž ” Œ Ÿ/35UUoF35C9V01wO,3I?;*E>FDso1
0Oc0ym'UoF9
1$@e2<68HFL;›;,3I03xE>FL?Q
0OfE>11$U9W /1MFJFCjk0O*FCFc689x?*1“U.*sE8687
68?*@{1
C2c350681
?}3"J3I68E3IsE8FD1
@,0OFL6>Ct0F75O?*6>‡'.*F'W(`y?A1
.*CG@{C352TFMk1$Clnj
MF[35CF[35s*E>F 01R9.*UUo1$C0qFL6>0O*FC(0m'UoF9(1
@oE811$U9qM 6>0OS2T6>H'F;T;,3503
E8F?*Q
0O*9j*3I?;eE8F?Q$0OD7L1
?'JFC9681
?DM 680OA3ICs680C35CmR7L1
?'JFC9681
?e@"357K
01$C9W ¢ FT35E891T9.*UUo1
C0E8F?Q$0O~71$?'JFC9681
?iM 680O~2T6>93IE86>Q$?2<FL?0W
µ´
9.
ž
CONCLUSION AND FUTURE WORK
… O*FCFòO359¤soFFL?
68?7LCF'35968?Q÷71
2<U*E8FH'6>0ymø68?
3I.01
2c350687
9682<;*68='350681
?D@{1$C2D.E80682<F;6y3FH'0F?*96>1$?9Wu… O*689n689n243I68?E8m:;.*F01
0O*F<?FLF;Z01“35;*;CF99R2D.E8068UE8F<1$C0O1
Q$1
?35Ek9682<;*68='350681
?g6>99.*F9
so1$0OA68?;*FUoF?;*F?'0E8m^35?;~71
E8Ey35so1$C35068JFE8mW
`y?g0O*6>9DU,3IUoFCjzMFiUC1
Uo1$9FZ3[9682<;68='3I06>1$?]@{C352TFMk1$Clg0O,3I0
9F352<E8F99E8m†68?'0FQ
C3I0F9T;*6>roFLCF?'0A3I9UoF709T1$@G96>2T;68='350681$?,jtÂó¼»ó¼j
3IE86>Q$?2<FL?0[O,3I?;E868?QjuE8F?Q$0O†71
?'JFLC96>1$?,j 3I?;“2D.E8068UE8FiE8FJFE89
1$@,X`acbcU,35C3IE8E>FLE>6892FH'0C3I70681
?,Wk²k.Cn90C3I0FQ
me68901T35E8E81M_F35CK
E868FCt9682<;68='3I06>1$?4UO,3I9F9G01S1
UoFC3I0Fe1
?AJ'68C0.,3IEuJFL701
C9j'M O687PO
3ICFeE>FL99/71$?90C3I6>?*F;c0O,3I?x0O*FRUO'm'96>735EzJF701$C9t9.*UUo1$C0F;As'm
0O*FeO,35C;*MR3ICF'W`?*;68J'68;.,3IEv3IC7PO*680F70.C3IE71$?90C3568?'09T35CFe0OF?
O35?*;E8F;w6>?w9.7L7F99681
?A68?wEy350FC 9682<;*6>=350681
?AU*O,3I9F9jQ
C35;*.,3IE>E8m
7L1
?'JFC068?QTJ68C0.35EzJF701$C9 01<UO'm'9687'35EzJF701$C9W
aTF359.CFL2<F?'09g1$?Ç3 ˆˆq‰ Š
‹IŒ M 680OÇ3“SaTŽhX`acb\.*?680
68?*;687'350F 9UoFFL;.U
@357L01
C9÷1$@Ü.U
01

W8‘
‘÷@B1
C÷?'.*2<FC68K
735Ey’5J'68;F1’571$2<2D.?687'3I0681
?AlFLC?FE89R3I?;S9UoFFL;.US@"35701$C9 1
@z.U
01c”
W8‘
•V@B1
CtsoF?75O243ICl'9 M 6>0O†35.01$24350687R9682<;*6>=350681
?W
ac3I?'m¥@{.C0O*FCA6899.FL9c?FF;Ì01fsoFZ68?J
F9068Qo350FL;NsoF@B1
CF“MF
735?xFL? ñ 1mi0OF/UoFC@{1$C2435?*7FRsoF?*Fp0v1$@n9682<;*6>=350681
?A@B1
CD3GM 6>;*F
C3I?Q$F[1$@V3IUU*E>687'3I0681
?9WG… OFe2<1$CF[682<Uo1$C035?'0V@BF'350.*CF9S3I2<1
?*Q
0O*F2µ35CFG2<1$CFT3I;J35?*7F;<O35?;*E86>?*QR1
@o?*1
?<90C68;FLKð1$?F[357L7F99F9
3I?;N0OF¥3Is68E8680mÌ01f;FL768;F“M O*F?€9682<;*6>=350681
?š689cU*C1
p03IsE8F'W
q‡'.,3IE>E8mw682<Uo1
C03I?0G689[3/soF00FC .*?;*FC9035?*;68?Q[1
@,0OFV6>?'0FC3I7K
0681$?~soF0yMkFFL?~9682<;*6>=350681
?“35?;i1$0OFCv1$U0682<68='3I06>1$?9 68?g3G71$2<K
U*68E>FLCt@BC352<FLMk1
CluW
ž
ž
ž
Fu
ž
ž
10. REFERENCES
TË
̆Í.ÎÏÌ 9Íc Kh
c tÐ (i dÑ c •Ò K{ (¤ Kc6Ó Ô
Ñ dh>Õc e fcJoÌ Õ
e¨ÖCÕc cjÌ 7i c(e p
š× e ØÙ:Ú OÍc Kh
c
z
µÌ†ÛÛÛÜÌ Kc
.Ð pÐ ˆÝ c
Ý 7i Kc
Ë
ßÞ)h Ð Ji dÑ c š× c à –á â Ê
ˆÕc
Õc Kc eOe Ç
Ë
Ý 7i Kc
¤ Ke
Ji dh ³Ðb̃ãÕ Ç ÍäåÝ ƒi Kc
.Ò
F̆e.¤ Ke
¾
PÕc
Ji dh .Ð'̃ãÕ Ç Íä
UÕc Kc eOe Ç
ßÒ
̆eOp
)Ë
ˆL
PÕc
(i+Ì Kc fp
0c
Þbc
Kc eíã
PË
ž
ž
!L
€Õc Kc eße
‚L
Ji.Ì Kc
F´ ßë
Õ c
ž
ž
aT687C1$UC17F991$C›Æ(3I2<68E>muú
ž ‘IŸ:` Ë a
‰ 1$CUo1
C350681$?,W ˆ 1MkFC ˆq‰
-VE8068qF7e…F75O?1$E81
Q
m ˆ C1$Q
C352T2<68?Qw?'J'68C1
?2TF?'09<ac3I?K
.,3IEyj P.*E8m“” Œ
Œ ÈW
¸¹«ÂÀ
¶ º¼¹«ÂI¶¹«½  · I¹ (¿  V ÂÀÁ·  ¾ A¿¸*½'¿À
ž ”IŸ
(º¼¹
ÂÀÁº [º¼¸¿
¸¹«ÂÀ q¸¹«º¼½
y·¶5¾I¾I·
¸ I· T¿
¹«º¼·¸ ·ÀÁ½ TÂ
k¿¾Iº¼¶
y¶ º¼¹«ÂI¶¹«½ ÂW`?'0FE ‰ 1$CUo1
C350681$?,W
?680z@{1$CG3 ‰  u ž>¡ Ÿ Ë W Æ,Ey3575O9t¹|¿ÀÁó-ÌX0CF352<68?Q ˆ C17F9968?Q
¸¹«Â 5¸¿¹«º¼·
¸¿À ·ÀÁº{à *¹«¿¹«Â nº ¶½'º¼¹«¾
ˆ C17F991
CW(`?
n·¸ I ¸*¶5ÂjÆFsC.35Cm^” Œ
Œ ô$W
 *· I¹ (¿  ÂI¶¹«· 5º I¿¹«º¼·¸ t¿¸Ã I·· W
ž È$Ÿ:-S3IC0 W ‰ W Ë 68lnW
`?'0FE ˆ CF99jn” Œ
Œ ÈoW
ž ôIŸiX3I2[.*FE< v35C9F?µ35?*;ÇX3I2435?-V2c35C35968?*Q
OFWVH'UE81$6>068?*Q
X.*UoFCMk1$C;A nFLJFE ˆ 3IC35E8E8FE86892\M 680O]aT.E80682<F;*6y3R`y?90C.*7K
0681
?›XF09W`?
·¶IÂIÂ5Ã
º¼¸»¾S· D¹ Â
n·¸  ¸¶IÂ
·¸
·» y¿ [º¼¸» ¿
¸»½'¿»Â V¾Iº¼»¸<¿¸*Ã
|ÀÁ [¸¹«¿¹«º{·¸j
U,3IQ
F9T‘5Èô5ù‘
ô
•$j P.*?Fw” Œ$Œ
ΠW
FJ'6>?
ž •IŸ:-VE8FHu3I?;CFd:WAq687PO*F?'soFCQ
FCj ˆ F?Q ¢ .jN3I?;
²R³ Ë C68F?,W:qF701$C6>=350681
?Í@{1$C–X`acbî-/C7PO*6>0FL70.CF9gM 6>0O
-VE868Q
?*2<F?'0 ‰ 1$?90C3I6>?'09W`?
·¶IÂIÂIú¼¸*»¾v· (¹ Â
n·¸ I ¸*¶5Â[·¸
·» y¿ [º¼¸»
¿¸»½'¿»Â V¾Iº¼»¸A¿
¸Ã
|ÀÁ [¸¹«¿¹«º¼·
¸j 5.?Fw” Œ
Œ ÈoW
ž>‹ Ÿ ˆ F?*Q ¢ .,j
-VE8FHu3I?;CFtVW
6875OF?'soFCQ$FCj|35?;i-/2[m ¢ 35?*QoW
q§<768F?'0†X`acb ‰ 1;F kF?FC3I0681
?Ì@{1
C†õ(.*?0682<F4-/E>68Q$?K
2<F?'0k35?*;R nF?*Q
0O ‰ 1
?'JFLC96>1$?,WP`y?
y·¶IÂ5ÂIú{¸»¾k· ¸¹«Â 5¸¿
JiÕ c
PË
ž
ˆæ6¤ e à p
¹«º¼·¸¿
À
·
¾5º{½ î·¸ n·Ã ¸ y¿¹«º¼·¸}¿¸Ã
|¹«º [º I¿
¹«º¼·¸jzac35C75O]” Œ
Œ ô$W
ž IŸ S350O35?[…DW*XE>68?*Q
FCEy35?*;435?*;T-/E3I? 3"mxX2<680OWbqF968Q
?43I?;
‰ O,35C3I70FC68='3I06>1$?T1$@*0O*F Ë FLClFE8FmwaT.E80682<F;*6y3 ¢ 1
Cl'E81o35;W
A½'ÀÁ¹«º TÂIú¼¿
$¾I¹«Â T¾Iju
‚{Èo„ú ¡ ‘
ô5ù ¡ ” ‹ j P.E8mg” Œ$Œ ”
W
ž8Š ŸR-S35C0 Ë 6>luj:aT68E868?; k68Cl35Cj ˆ 3I.E[acW kCFmjV3I?;fŽ/68?2<68?
… 63I?,Wk-/.01
2c350687g`y?0C3IKPõ(FQ$6890FCxqF701$C6>=350681
?Ì@{1$CA0OF
`?'0FEi-VC75O680F70.*CF'W ¸¹«Â 5¸¿¹«º¼·
¸¿À ·½ P¸*¿Àw·
¿ ¿À¼ÀÁÂÀ
y·» ¿ Tº¼¸*»jn‚”
„ú8•$ô5ù Š 
j*-/UC68Ek” Œ
Œ ”
W
‘ Œ Ÿ kFC35E8; ‰ OF1$?QZ35?*;faT1$?687'3wXW* v3524W-V?}²kU0682<68=FC/@{1$C
aT.E80682<F;6y3v`?*90C.70681$?^XF09W$`y? ÂI¶I·¸*Ã
n· oº¼ÀÁÂ
· ¾ · |j'-V.*Q
.90D‘ Š
Š$‹ W
‘
‘IŸR-V?;*CF'359
C3IE8E<3I?;€Xm'E8J3I6>?} nFEy3I6>0W ‰ 1
2TU68Ey350681
?¥…FL7PO*K
?68‡'.F9R@B1
CxaT.E80682<F;6y3 ˆ C17F991$C9W ¸¹«Â 5¸¿¹«º¼·
¸¿À ·½
¸¿À'· q¿ y¿À¼ÀÁÂÀ y·» ¿ Tº¼¸*»j*‚{Ȅú ¡ È ‹ ù ¡ •
‘
j
-/.Q$.90 ” Œ
Œ$Œ W
‘
”IŸwb1
C680 S3I6>9O*E81
9jwac35C68?,3 Ë 68soFC90FL6>?jiXO,3"m Ë F?*KPb:3"J68;j
35?;]-/m|35E z35l'9WnqF701$C6>=L6>?*QZ@B1
C^3^X`aT;,b b:X ˆ -/C7PO*68K
0F70.CFW*`?
·¶IÂIÂIú¼¸»¾[· ¸*¹«Â P¸*¿¹«º¼·¸*¿À n·¸  ¸¶IÂi·¸
n· |º{ÀÁÂ P¾
¶ º¼¹«ÂI¶¹«½ ¾ R¿¸*Ã
¸¹ ¾Iº¼¾ I·
IÂ5Ã
ÃÂIÃ
¾5¹«Â [¾IjU,3IQ
F9T”5ù‘
‘$jn²k701$soFC[” Œ
Œ¡ W
‘ ¡ ŸRÆCFF
X1$@{0M:35CF
Æ1
.*?;350681
?W
O00Uú8’
’5Q$77'W Q
?'.W 1$CQo’IUC1 ñ F709’I0CFFK)993
W
‘5È$Ÿ SWXCFLC35243I?c35?*;cõtW k1J68?*;,35C3 ñ 3I?,W-}qF701$C6>=L6>?*Q ‰ 1$2<K
U68E8FCG@{1
CTaT.E80682<F;*6y3VH'0F?*96>1$?9W ¸¹«Â 5¸¿¹«º¼·
¸¿À ·
½ 5¸¿
À
· ¿ y¿À¼ÀÁÂÀ y·» ¿ Tº¼¸*»jn”$
‚{Èo„ú ¡ • ¡ ù$È Œ$Œ j-V.*Q
.90D” Œ
Œ$Œ W
‘
ôIŸ ‰ 1
C68??3 RW nFFA35?*;›ac3ICl RW,X011;E8FmW(X682<U*E8FTqF701
C
aT6>7LC1
UC17LF991
C9i@{1$CcaT.*E>0682<FL;6y3i-/UU*E>687'3I0681
?9Wn`y?
y·
¶5ÂIÂIú¼¸*»¾:· ¸*¹«Â P¸*¿¹«º¼·¸*¿À
·¾Iº¼½ Ü·¸ Aº¼¶ y·¿ ¶ º{¹«Â5¶
¹«½ yÂjU35Q
FL9<”$ô5ù ¡ •
j‘ Š
Š 
W
‘
•IŸ P1
O*?
õt35?;35E†-/E>E8F?Ê35?*;
F?
F?*?F;*mW~-V.*01
243I06>7
…C35?*9E3I0681
?i1
@|Æ1$C0C35? ˆ C1
Q
C3I2<9v01eqF701
C(Æ1$C24W
¿¸*¾I¿¶¹«º¼·¸*¾V·¸
·» y¿
[º¼¸»
¿
¸»½'¿»Â¾V¿
¸Ã
¾I¹«Â T¾Ij
‚{Èo„ú È Š ‘5ùoôIÈo”$j,²k701
soFC[‘ Š  ‹ W
‘ ‹ Ÿ S35?*9 '68243i35?*; Ë 3ICs,35C3 ‰ O35U2c35?,W ½  ¶I· |º¼ÀÁ 5¾ ·
¿ y¿À¼ÀÁÂÀz¿¸Ã ÂI¶¹«·
n· |½'¹«Â 5¾IW*- ‰ a ˆ CF99ju‘ Š
ŠIŒ W
‘
IŸRÆC35?*=gÆC3I?75OF006yj<X0F@3I?
C35Eyj /.FCQ$F?Ì n1
CFL?='jS3I?;
FsoFCO'.*soFCWGq§<768F?'0^.068E868='350681
?Í1
@^X`acb
‰ OC68901
U*O
H'0F?*96>1$?9W`?
·¶IÂIÂ5Ã
º¼¸»¾ ÂI¶º¼¿
À ¾I¾I½Â[·¸
y·
» ¿
¸* ¿¹«º¼·
¸
|¹«º Tº 5¿
¹«º¼·¸ (¿¸*à qÀÁ¿¹ I·
kÃ
¿ |¹«¿
¹«º¼·¸jz” Œ$Œ ô$W
‘ Š Ÿ 35FM11
l›XO68?j 357‡'.FLE>68?*F ‰ O,352TF'jk3I?;¥ac3ICm ¢ W <35E8EyW
‰ 1
2<U*6>E8FCK ‰ 1$?0C1$E8E>FL; ‰ 3I7PO*68?Qš68?îX.UoFCM1
C;Yõ,FQ$6>90FLC
Æ,6>E8F9e@B1
C~aT.E80682<F;*63TqH'0F?9681$?g-VC75O680F7L0.CF9W`?
y·
¶5ÂIÂIú¼¸*»¾V· ¸¹«Â 5¸¿¹«º{·¸¿À n·¸ I ¸*¶5Âe·¸ ¿ y¿À¼ÀÁÂÀ y¶ º
¹«Â5¶¹«½ y¾D¿
¸Ã n· |º{ÀÁ¿¹«º¼·¸ *ÂI¶ ¸*º ½'¾IjXFU*0F2DsoFCD” Œ$Œ ”
W
” Œ Ÿ ‰ CF97F?'0
X1
@B0MR3ICF'W€-<X… K)Æt’5-/E>068qF7'ú
-/.01
K
Ë 3m
24350687›Æ1$C0C35?͍FL701
C68=FCg@{1
C ˆ 1MFC ˆ‰ qF701$C
?*680W
Î'&&$
¼Ï "!
#
& &* !¼Î'& j” Œ
Œ ÈW
c
H˜ ¹¹
TÌ Kc
c
JitÕ fc
Ð+è+̆é–Ý e.¤ Kc
Kc
ç cJp
Ý ƒi Kc
9i fcÛeßâ
ç 0c
ˆL
±Õc p
)ÐboeR¤ e jÔ Kc c Kh Kp
¾ ¾
„ÍÝ)Ô
UÕc Kc eOe Ç
Ð'o Ke
TÐ ^¤ Kc eR¤ Kc Ri c
C× c³Ý e.¤ Kc
¾ ´
z
>̆ÛÛÛÕc
VЃ¤ )Ì
Õc p
Kc 'ìFæ-¤ e 2à 'ì ³Õ i fcJeîÍ J¤ p
Ë
6´
Õc p
JiHÌ Kc
Ý 7i Kc
‚Õ c -Íc Kh p
CÝ e.¤
tÞ Kh ï
z
” ¹7”
”