ࡱ> -/,bjbjUU >??|| 3555555*J55J33`0ttt,55t| : Resumo Meta-heursticas paralelas tm sido empregadas em muitas aplicaes industriais e cientficas para a resoluo eficaz de problemas de otimizao combinatria. A busca local um componente essencial para muitos desses mtodos e, frequentemente, representa o esforo computacional dominante empenhado pelo algoritmo. Atradas pelo potencial paralelo das plataformas CPU/GPU, muitas abordagens heursticas tentam adaptar algoritmos de busca local tradicionais para essa plataforma sem considerar suas caractersticas intrnsecas. Esse trabalho apresenta um estudo detalhado sobre aspectos relacionados ao desempenho em sistemas hbridos CPU/GPU, alm de introduzir novos mtodos para a abordagem de problemas combinatrios nesses sistemas. Para tanto, um algoritmo bastante eficaz baseado na busca local RVND (Randomized Variable Neighborhood Descent) foi decomposto, adaptado e avaliado em diferentes configuraes nessa plataforma. Adicionalmente, uma nova estratgia de seleo em vizinhana denominada multi improvement, capaz de aplicar mltiplos movimentos em uma vizinhana, foi utilizada para acelerar um novo procedimento de busca local chamado DVND (Distributed Variable Neighborhood Descent), especialmente concebido para ambientes multi-GPU. Para validar as abordagens propostas, um problema combinatrio NP-Difcil, o Problema da Mnima Latncia (PML), foi submetido a um framework heurstico baseado em GRASP e VNS denominado GVNS. Diversas configuraes paralelas do GVNS envolvendo o DVND e RVND foram experimentadas e apresentaram resultados que suplantaram o melhor algoritmo da literatura, com speedups de at 13,7 para instncias do MLP com at 1.000 clientes. Os resultados obtidos indicam a eficcia das tcnicas propostas em termos de qualidade da soluo, desempenho e escalabilidade. Palavras-chave: DVND; Multi improvement; Busca Local; GRASP; VNS; VND; GPU; Problema da Mnima Latncia. Abstract Parallel metaheuristics have been used in many industrial and scientific applications to effectively solve combinatorial optimization problems. The local search is an essential component of many of these methods and, very often, represents the dominant computational effort accomplished by algorithm. Attracted by the massive parallel potential of platform CPU/GPU, many heuristic approaches try to adapt traditional local search algorithms for this plataform without considering its intrinsic characteristics. This work presents a detailed study of aspects related to performance in CPU/GPU hybrid systems, and introduces new methods to tackle combinatorial problems. A very effective algorithm based on the local search RVND (Randomized Variable Neighborhood Descent) was decomposed, adapted and evaluated in different configurations in that platform. Additionally, a new neighborhood search strategy called multi improvement, capable to apply multiple moves in a neighborhood, is used to accelerate a new local search procedure called DVND (Distributed Variable Neighborhood Descent), specially designed for multi-GPU environments. To validate the proposed approaches, a NP-Hard combinatorial problem, the Minimum Latency Problem (MLP), was subjected to a heuristic framework based on GRASP and VNS called GVNS. Several parallel configurations of GVNS involving DVND and RVND were tested and showed results that outperformed the best known algorithm of the literature, achieving speedups up to 13.7 for the larger MLP instances with up to 1,000 clients. The results demonstrated the effectiveness of the proposed techniques in terms of solution quality, performance and scalability. Keywords: DVND, Multi improvement, Local Search, GRASP, VNS, VND, GPU, Minimum Latency Problem.   Fd4 \ s | W_,h;=F㽵hDhU5\mH sH hUmH sH hDhUmH sH hDhU5\hDhU6] hDhUhUhDhU5CJ\aJhU5CJ\aJ  $a$gdD$a$gdD<=$a$gdD$a$gdD<P1h:pU. A!"#$% Dp^ 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtH@`@ NormalCJ_HaJmHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]   DrLU>@@@UnknownG*Ax Times New Roman5Symbol3" ArialACambria Math"HGHGHU !0$PD!xxResumoHelioHelioOh+'0x  4 @ LX`hpResumoHelioNormal_WordconvHelio1Microsoft Office Outlook@@X1@IJHU ՜.+,0 hp|   Resumo Title  !"#%&'()*+.Root Entry F01TabletWordDocument>SummaryInformation(DocumentSummaryInformation8$CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q