Uma Implementação Paralela para o Problema da Junção por Similaridade em Conjuntos

...

generalizar a solução para qualquer

dispositivo, sem a preocupação relacionada

à escolha dos tamanhos do grid e dos blocos

(para problemas unidimensionais).

Software de junção

Definimos uma função get_grid_config [2],

que obterá informações sobre o

dispositivo, e fornecerá um tamanho para

o grid e os blocos, aproveitando ao

máximo a capacidade do dispositivo:

Software de junção

Software de junção

Assim, poderemos processar os dados em

blocos do tamanho do número de threads

disponíveis:

Software de junção

Basta usar esse código nos kernels:

Onde data é o array que contém os dados

a serem processados pelo kernel.

Software de junção

O sistema implementado neste trabalho foi

dividido em 4 fases:

–

Tokenização

–

Cálculo do índice invertido

–

Filtragem de candidatos

–

Cálculo da similaridade

Software de junção

Tokenização

Após a leitura dos dados de um arquivo

teste, cada registro (linha) será pré-

processado e tokenizado de acordo com

o tamanho do qgram fornecido como

parâmetro para o sistema.

Software de junção

Tokenização

Em nossa abordagem paralela, este

processo ocorrerá “simultâneamente” para

todos os registros do arquivo de teste, de

forma que um kernel será lançado, e cada

thread realizará, para um registro, o pré-

processamento e a tokenização, em

sequência.

Software de junção

Tokenização

Cuda não lida de forma amigável com arrays

de indexação dupla (2D). Assim, definimos

uma estrutura unidimensional que conterá

todos os registros concatenados, um array

de índices apontando o início de cada

registro e um array de tamanhos, contendo

os comprimentos de cada registro.

Software de junção

Tokenização

Software de junção

Índice Invertido

Após a fase de tokenização obtemos uma

estrutura contendo, para cada registro, o

conjunto de tokens que ele contém.

Agora precisamos calcular o índice invertido,

para realizarmos a filtragem de candidatos

que contém pelo menos um token em

comum.

Software de junção

Índice Invertido

O cálculo do índice invertido é realizado por três

passos:

–

Geração do vetor document_frequency, que

contém o número de ocorrências de cada token

no conjunto de registros.

–

Cálculo do prefix sum (scan), para obtenção dos

índices.

–

Montagem do índice invertido.

Software de junção

Índice Invertido

Software de junção

Índice Invertido

Software de junção

Índice Invertido

Software de junção

Índice Invertido

Software de junção

Cálculo da similaridade

O