Título:	Algoritmos paralelos e eficientes para consultas IP no Intel(R) Xeon Phi(tm) e CPUs Multi-Core
Autor(es):	Alencar, Alexandre Lucchesi
Orientador(es):	Teodoro, George Luiz Medeiros
Assunto:	Roteadores (rede de computadores) Computação paralela Algoritmos de computador
Data de publicação:	9-Out-2017
Data de defesa:	29-Jun-2017
Referência:	ALENCAR, Alexandre Lucchesi. Algoritmos paralelos e eficientes para consultas IP no Intel(R) Xeon Phi(tm) e CPUs Multi-Core. 2017. xii, 56 f., il. Dissertação (Mestrado em Informática)—Universidade de Brasília, Brasília, 2017.
Abstract:	Software routers are a promising solution to deal with packet forwarding because of their good cost benefit and flexibility. However, it is challenging to develop software routers that can attain the required packet forwarding rates. The use of parallel computing systems and techniques may be a viable approach to improve the performance of these solutions. The IP lookup phase is a core operation in packet forwarding, which is implemented via a Longest Prefix Matching (LPM) algorithm to find the next hop address for every input packet. Therefore, this work proposes and evaluates the use of parallel processors and techniques in the development of an optimized algorithm that employs Bloom filters (BFs) and hash tables to the IP lookup problem. Specifically, we target the implementation on the Intel® Xeon Phi™ (Intel Phi) many-core coprocessor, but we also evaluate its performance on multi-core CPUs and on a cooperative execution model that uses both processors with several optimizations. The experimental results show that we were able to attain high IP lookup throughputs — up to 182.7 Mlps (million packets per second) or 119.9 Gbps for 84B IPv6 packets — on a single Intel Phi. This performance indicates that the Intel Phi is a very promising platform for deployment of IP lookup algorithms. We have also compared the BFs algorithm to an efficient approach based on the Multi-Index Hybrid Trie (MIHT) in which the BFs algorithm was up to 5.39x faster. This comparison shows that the most efficient sequential algorithm may not be the best option in a parallel setting. Instead, it is necessary to evaluate the processors characteristics, algorithms compute/data demands, and data structures employed to analyze how the algorithms will benefit from parallel computing devices, potential limitations on scalability and opportunities for optimizations. These findings are also important to new efforts in algorithmic developments in the topic, which have been highly focused on sequential solutions.
Unidade Acadêmica:	Instituto de Ciências Exatas (IE) Departamento de Ciência da Computação (IE CIC)
Informações adicionais:	Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017.
Programa de pós-graduação:	Programa de Pós-Graduação em Informática
Licença:	A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
DOI:	http://dx.doi.org/10.26512/2017.06.D.24784
Aparece nas coleções:	Teses, dissertações e produtos pós-doutorado

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.