From c5e1141650462fe452663bbf018f1c136914de28 Mon Sep 17 00:00:00 2001 From: Kahina Date: Fri, 23 Oct 2015 14:59:38 +0200 Subject: [PATCH 1/1] MAJ figure 4 et quelques remarques faites par SIDER --- figures/EA_DK.pdf | Bin 7714 -> 7711 bytes figures/EA_DK.txt | 6 +++--- paper.tex | 8 ++++++-- 3 files changed, 9 insertions(+), 5 deletions(-) diff --git a/figures/EA_DK.pdf b/figures/EA_DK.pdf index 732fb08bea92ed5762845ea7bb2f77e448c06752..5eb980829bce00777b3105f5491fcd948aca0002 100644 GIT binary patch delta 2365 zcmb7=c~laJ7RK8xE1h1sBq?fYS`i?!Dv(P$rB+&vHMj;!7^0~yGZQd{Wtyo^%oR1u zo}-z$GBqeGDzZ+~o8BMw&UwB2*FC@c-S6D*-gGK(NRdY&yJ+rQ{LVf0`Qlw$55sN+BDJ{3C`kA;ph5DKHzW=I_ z8QNmww3?Z#yKV?nvlAgo#r|$Hf|vL;9xU2LyFC$;UNuyeIX*EkY(^(1#{XyIgI60UWQeK%Tif{7N@(Jyetm;5FnO|IL|< z#2ij4Rt26%-Dmw&%IrJpCwFfamz0z>G zPh@xcRpg7_Z*tY?f=8N~UoDTMy%q7q+RmjVjU85(_@G9V)!-9ats|kZ+F}(Tnz(SP z{O$)mYyE>t9nKv+V`Q6YY&mAhOs1o`r(&Vo4JsXteRxQJFtyKy_2z^NCgNtFsKkT3 zBNovZ>`Ie5R=AAbG+y93O+8;ZQgd9f5vl zPfJg&^A4P>I#6duoOY*GG;VKkO$OMu-^*#(f>0v>z=(Vv17)ueQ)dp!1 zzEu|*CT9IVK?|>{zhVA3X$R9vTtr$9Amro}G@6T2FM4}%i?XU$S~jO*2-7EpTgZKf zyxSkuz2$_X7LGI@%1Ku)lcd*ksFz5&>D1r~vb62HZ@GJ)u0n9rA6kh&I;`V9UrXNc z(U+C?EQ;$=<-HF95&dq;xtmI5r>*yz_m@5p&0fYD@j5%0`z~F96_Egp2+oj-=T$m< zD)2(vEuH?O7AX{8+B#~}PAKLt+p4amEKt4pQ^>J0%TIZ7+G_vKLpwRn?WQ45{+e4W zPTEGeQGMh+RT#Wr*z=FtcoTkao+f$*?_Z zew=yHF~1mY6s1;cKn=rqe)3ot^JM@rqhwR47ddHoj9EU(P)BP=CG$g?0mXgw)H{u2 zUM}?eF)pTPFXr9$)|`0NVn@7|p^`;uCGmJH4Ij|Y!{0 z&uE8&#FBPAgTbt$c}`B(9K?H9`O8T+;_BympBxnK%OFH#0M`-<9&$F-=hLmlLHbQiOd=~wX$PxjWo4b5*_rt+q$kOL<*eCVG{+>?`r3;4f$Ut9 z^6!t7XGCvI$iG#UG0H8?EWLh+O5x=`Qf=T~a2tT$`;wm1> zW<{^aTYWy4$G>p)W>GT#H2HPjJJJfH+^N$G# z@()+EPK3U79NB6U?{Rx->KtdtiB2<6n4o?DvzufanuJ@k)hdPU*0XucZ`YS-YV=EX zRyWHwC|S&xM$2!slYUWm7Nqg(EuCfc=bsh5UyOzjeaAXImemd_tb-|@+vzE{vx)KK zW44`55>7FrY_p<^)}I#l;$DIxBOA@*~wcp^g z2!-lsx*b{3tYsM-JfJN!&(Q9pO$D*ER(LO_;DNR*JbZ0=-oj%k)=Ak-IMwF6T0-F1Fk2^d`706Pl%9uXOex?suNbBc>;sM6ogS%JF^)m z%MtRt!_>V*J@hU$uCP5@v{tr=2cEIrRHEPXv*lxDv$|NF8Mf8w(SI zz+nP7t_vK7SN>6n+fWjj0tIR3_S5;3os(t-H`tVODk(I@KydMe;(5txP*YoLGkyAO zu#wJ)JXv!uHIlECQ10ump)&sopNF^_+shxB-S%s4Rd5pR%1g4|q78`LN%EMqBze{* zCx`AyXu7^6pXd`cS81DkZTLFm$vYynSkyg|um(Nz2f)&U7O$^A(9vYpKFto#M@pJX z7klNEtb5b0jwnV^01vm0pj67C#2$I!csv0}Yf2ekq^h!5-SV(Pf!@N=5v0UJ)-Ic! zChiZA#N+0tVZ2N*=S{bKP+qyaY+86fN|p7<1b>X9Ij=f8)h!R%iDtMp%x&lc(362{ z#hC{Z196dBZRmVGNuyn|^%~np$84!Xb(GG}`ry#eP$Yze zgo2JkL!cliGzsqUiR-h>>=!40APg! z9PYrD1FqtrX!E}w0WqhU>wat?NC+JIIkSf#AfGcR8iHmwY_Zvn`oh8|AN6FXf!*-bfW?6a|bvaf@CL{It9Q#M1Z=Z9bDa9P;dy!0SR++ uL&IS1usv{B1l-*P=kz}n0lGMxZcJ=QbnLn4&@f%3JshQLZN2A!yY8R*flV*~ delta 2404 zcma)&dpy(s9>-7lML+RdH>u-iA#k!3~hRWu$xt!{8I*;?HKTe;&-jCR$0|Tx)}4JZipbma zM0Ri5pPOj0zbQMq`*~%*05iBUV=zDX*Pn+4c2OAeC7!9aQCx^9xwht!WOasq3)g7S z>Z(zE!WEZ$Ne?Kr)MBRh_9g}M>fEcUh1Ajws^Qq|ShxFyB}Dg7BeM&^A)p^kAx@!Y z^qkxnb3eDlw{k(dM4v11nX^{-Fs*&fty5M7+=Yb>njtmfUT!=J zicWyZpXrw91L8a*=B<{u$75xK+vV4_Ou!bchH{WjTHjIXt%Fl-`>B(P7|FFL@3VN2 zTap~lCq}sFp@sxKJSXr=g`#ISWmfU1yCcW)+6T4VJxmJhvSaC8TD=F4ds|;CSX994 zUmrcXR|pk88dBM5?v4Q)=tJ6`)eX3EaUrG{$70vy#jwxn>+uuTHyE6y`Zk=nO}m06 zn@TLqjW#Oqy^a5Y&^u;dpv0RG5*tV!sCsTi)ttLty1te8Zm4Ir6WJtPuZm~Tj(Qj? zaDJ+^d1&2Jb&^5J#8tSr*u%XgU7h~B`0kzB+DySjOlIhXf|$S%&mX-S^gkyAcHKO} z|C|dKSLsDqn+=qQYGv3;Z%cGLQC5;$p}qG?Pdn4a46dg$ShM>S#>IpGN+j6d)818{ z43!&<;F90v8hkisF)X;1@Nn%F-ltfyFU>){Y+h(udzqiylwlCA98u z?M`Y~fhAY;p!5>xu~MoJ-@SLbU5rKtWv*1RgKh&;4>Z1AOpyk>qpMW)URt2}7nE5- zoT;3;gk_@k$ro!=7G-12v}r>rGQ8O1H$l80scliNo)Fp3aPTzB1gw@d0HIG1Xe>fX z#ZJu5^W`D6PpXgI=MYk7Cxt$c8A94@pKQ8MwICncGuo&?4xF>o3{Ir|>*m}veSkhg zS!{G(oR`T#;TT^D^;xCrGwaIq(e@CNIaEDlb!f}e@VSVfv32Lzmqom~9nw5=!wZMB z;x42MZ35QBzAiORPw5{_f|b?mwE z;HfX|m&c6V{RpYQ%C|Aju{-dh9o3SQ5*1Zj;WQ4C@3|d_lxKRq4zRrum=f8FWBlz* z*}4;Sh6w%6yWr2qXmvS#v}WI>9O2rGXt{}Xr#0hR8;3-B+@8h6guNXIDT=NgJMBqo zm;B+CqLX@e=-svTP$-Lcv9h;@NYS#K4Et~n|2iqjjK`tC!iH+6AXTPMIn$Gv%jnufrwkU1k3~*#3hJ)xBbp>&Q^Nvssm? zPP#btCkyG){%o9lcC{M$+Y5w4gh(Vj@4Zx1z-_mf%;<+q@3e!JcAr@62w7FRlzp&; z#DSeg412-m!20EHM+xiiexP*fFGj!P3}u0%=o!u)67{yK=G0KMMCF9LsMbJ3rnTbI_3#HI2Dvd%vT@L+v0nZH3&Ydv)OzE9E-|IY#e#d6K?dM zPX;tK@2k=PjYNl~`p2$RW=_;xUEh#h zT!=h8ZA&%YyS!QO%YoLT#Ml@mcZ=<>v-@(?eNw07VB#6v?8*E21Ft$n zynB{=I1QDico{wa=%+KVC{Zn>qkj>f_E3yWi`2a8&l-3i!o(X9-jqcl(?;xJgy@uK zvhi8v`;PacGNI7&O}8ST?MO0N#+C_}a|IAtTvF)SCJIv#+ekSBTlM^}gdB4rE5(L6 zx4D^7ND#7Cq~vlO7OxeFOAAUg4!4DWJho_L5Hc7Z9v+McLb2BvQtiJ-v@}Vg#?TnpBb4z?$NgX9kS-pt%ZLw(i%*IR3)e*> OP=KzvxvP(x?!N)7)ky>Z diff --git a/figures/EA_DK.txt b/figures/EA_DK.txt index e20822a..dca073f 100644 --- a/figures/EA_DK.txt +++ b/figures/EA_DK.txt @@ -31,10 +31,10 @@ 50000 385.266 823 9.27 19 100000 447.364 408 7.73 15 150000 1524.08 552 8.64 21 -200000 3.92233 17 7.84 16 +200000 1530.86 360 7.84 16 250000 1958.24 348 11.33 18 -300000 12.3981 21 20.47 21 -350000 23.813 21 35.07 26 +300000 2800.53 319 20.47 21 +350000 4071.47 378 35.07 26 400000 450000 500000 diff --git a/paper.tex b/paper.tex index b9ed2ff..02f98de 100644 --- a/paper.tex +++ b/paper.tex @@ -330,7 +330,9 @@ Q(z_{k})=\exp\left( \ln (p(z_{k}))-\ln(p(z_{k}^{'}))+\ln \left( \sum_{k\neq j}^{n}\frac{1}{z_{k}-z_{j}}\right)\right). \end{equation} -This solution is applied when it is necessary ??? When ??? (SIDER) +This solution is applied when the root except the circle unit, represented by the radius $R$ evaluated as: + +$$R = \exp( \log(DBL\_MAX) / (2*n) )$$ where $DBL\_MAX$ stands for the maximum representable double value. \section{The implementation of simultaneous methods in a parallel computer} \label{secStateofArt} @@ -356,7 +358,7 @@ parallelism that can be suitably exploited by SIMD machines. Moreover, they have fast rate of convergence (quadratic for the Durand-Kerner and cubic for the Ehrlisch-Aberth). Various parallel algorithms reported for these methods can be found -in~\cite{Cosnard90, Freeman89,Freemanall90,,Jana99,Janall99}. +in~\cite{Cosnard90, Freeman89,Freemanall90,Jana99,Janall99}. Freeman and Bane~\cite{Freemanall90} presented two parallel algorithms on a local memory MIMD computer with the compute-to communication time ratio O(n). However, their algorithms require @@ -382,6 +384,8 @@ GPUs, which details are discussed in the sequel. \section {A CUDA parallel Ehrlisch-Aberth method} +In the following, we describe the parallel implementation of Ehrlisch-Aberth method on GPU +for solving high degree polynomials. First, the hardware and software of the GPUs are presented. Then, a CUDA parallel Ehrlisch-Aberth method are presented. \subsection{Background on the GPU architecture} A GPU is viewed as an accelerator for the data-parallel and -- 2.39.5