dc.contributor.author | Gaioso, Roussian Di Ramos Alves | |
dc.date.accessioned | 2019-07-05T18:12:01Z | |
dc.date.available | 2019-07-05T18:12:01Z | |
dc.date.issued | 2019-02-13 | |
dc.identifier.citation | GAIOSO, Roussian Di Ramos Alves. Paralelização de algoritmos de busca de documentos mais relevantes na web utilizando GPUs. 2019. Tese (Doutorado em Ciência da Computação) – Universidade Federal de São Carlos, São Carlos, 2019. Disponível em: https://repositorio.ufscar.br/handle/ufscar/11481. | * |
dc.identifier.uri | https://repositorio.ufscar.br/handle/ufscar/11481 | |
dc.description.abstract | Search engines are facing performance challenges because of the large number of documents and the increase of query loads in the Web environment. The success of a search engine is related to the ability of the query processing system to find documents that match the needs of information expressed in user queries in a short time interval. Despite the large amount of documents, users are more interested in fewer results in a query. This causes few documents to be highly relevant in most queries. DAAT dynamic pruning algorithms have been exploring the efficiency of query processing systems, avoiding wasting time sorting documents that are not likely to be relevant. To handle the scale and dynamics of user query traffic, query processing needs to make efficient use of hardware resources.
The main objective of this doctoral thesis is to investigate the use of parallel computing in the process of identifying the most relevant documents to a given query in the GPU architecture. For this, strategies of parallelization of algorithms that aim to reduce the latency of response of a given query and to increase the flow of queries are proposed and evaluated in the GPU. The parallelization proposals are well suited to the category of DAAT algorithms and dynamic pruning algorithms. In the DAAT category, partitioning strategies are offered in a way that performs an investigation into the location of occurrences of the same document in the memory hierarchy of the GPU. At the level of dynamic pruning algorithms, threshold propagation policies among processors are proposed and the impacts generated on the efficiency of the parallel algorithms are analyzed. To verify efficiency in practice, the parallel proposals were implemented and tested in the Pascal GPU architecture and obtained a performance of 4x to 40x relative to the fundamental algorithms. | eng |
dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) | por |
dc.language.iso | por | por |
dc.publisher | Universidade Federal de São Carlos | por |
dc.rights.uri | Acesso aberto | por |
dc.subject | Busca na Web | por |
dc.subject | Processamento de consultas | por |
dc.subject | Algoritmos DAAT | por |
dc.subject | Algoritmos de Poda | por |
dc.subject | Algoritmo WAND | por |
dc.subject | Algoritmo MaxScore | por |
dc.subject | Algoritmos paralelos | por |
dc.subject | Arquitetura GPU | por |
dc.subject | Web search | eng |
dc.subject | Query processing | eng |
dc.subject | DAAT Algorithms | eng |
dc.subject | Pruning algorithms | eng |
dc.subject | WAND Algorithm | eng |
dc.subject | MaxScore algorithm | eng |
dc.subject | Parallel algorithms | eng |
dc.title | Paralelização de algoritmos de busca de documentos mais relevantes na web utilizando GPUs | por |
dc.title.alternative | Parallelization of search algorithms of most relevant documents on the web using GPUs | eng |
dc.type | Tese | por |
dc.contributor.advisor1 | Senger, Hermes | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/3691742159298316 | por |
dc.description.resumo | As máquinas de busca estão enfrentando desafios de desempenho devido à grande quantidade de documentos e ao aumento de cargas de consultas no ambiente Web. O sucesso de uma máquina de busca está relacionado à capacidade do sistema de processamento de consultas de encontrar, em um curto intervalo de tempo, documentos que correspondam às necessidades de informações expressas nas consultas dos usuários. Apesar da grande quantidade de documentos, os usuários estão mais interessados em poucos documentos de resultados de uma consulta. Isso faz com que haja poucos documentos que são altamente relevantes na maioria das consultas.
Os algoritmos de poda dinâmica DAAT vêm explorando a eficiência dos sistemas de processamento de consulta evitando perder tempo ao classificar documentos que provalvemente não são relevantes. Para lidar com a escala e a dinâmica do tráfego de consultas do usuário, o processamento de consulta precisa fazer o uso eficiente dos recursos do hardware.
O objetivo principal desta tese de doutorado é investigar o uso da computação paralela no processo de identificar os documentos mais relevantes a uma consulta realizando processamento na arquitetura GPU. Para isso, este trabalho apresenta estratégias de paralelização de algoritmos que visam a reduzir a latência de resposta de uma dada consulta e a aumentar a vazão das consultas. As propostas de paralelização são bem adequadas à categoria de algoritmos DAAT e aos algoritmos de poda dinâmica. Na categoria DAAT, estratégias de particionamento são oferecidas de modo que realizam uma investigação na localização das ocorrências de um mesmo documento na hierarquia de memória da GPU. No nível dos algoritmos de poda dinâmica, políticas de propagação de threshold entre os processadores são propostas e os impactos gerados na eficiência dos algoritmos paralelos são analisados. Para mostrar a eficiência na prática, as propostas paralelas foram implementadas e experimentadas na arquitetura da GPU Pascal e obtiveram um desempenho de 4x a 40x em relação aos algoritmos fundamentais. | por |
dc.publisher.initials | UFSCar | por |
dc.publisher.program | Programa de Pós-Graduação em Ciência da Computação - PPGCC | por |
dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | por |
dc.ufscar.embargo | 18 meses após a data da defesa | por |
dc.publisher.address | Câmpus São Carlos | por |
dc.contributor.authorlattes | http://lattes.cnpq.br/3536210071193629 | por |