Olá, Hugo,
Eu não programei nada ainda pq nem consegui instalar o cuda.
Mas isso não me impediu de pensar em como paralelizar a solução do n-rainhas, o que acredito ser o fator determinante do desempenho.
O cuda permite executar milhares de threads concorrentemente, não?
Agora, como usar?
Ele não permite manipular threads de forma concreta como qnd usamos a biblioteca pthread.
Deixar várias threads manipulando a mesma estrutura de dados (tabuleiro) produziria mtas condições de corrida e consequentemente mto overhead no seu tratamento.
Qnd tentamos alocar uma rainha na posição (i,j) temos que olhar toda linha i e toda coluna j e diagonais. Pra entender se essa operação vale a pena ser paralelizada tenho q entender melhor como o cuda lida com memória. Pq se fosse com pthread não valeria a pena, eu acho.
Não sei se conseguirei esclarecer todas minhas dúvidas até o dia de entrega atual.
Nem sei se posso postar todas as minhas dúvidas pq elas vão dar dicas para os meus colegas. Não q eu não queira, mas não sei se seria adequado.
Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Ricardo Cillo -
Número de respostas: 11
Em resposta à Ricardo Cillo
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Ricardo Cillo -
Retificando:
Não programei nada em Cuda.
Eu tinha (de mac0122) o pseudo-código da solução iterativa do n-rainhas e estou tentando fazer rodar em C.
Meu colega de grupo já conseguiu instalar o cuda no feriado da semana passada.
Acontece que um monte de gente levou bomba na prova de autômatos. Então priorizaram estudar pra autômatos. Entre outras coisas. Não quero aborrecer ngm falando das nossas obrigações.
Não programei nada em Cuda.
Eu tinha (de mac0122) o pseudo-código da solução iterativa do n-rainhas e estou tentando fazer rodar em C.
Meu colega de grupo já conseguiu instalar o cuda no feriado da semana passada.
Acontece que um monte de gente levou bomba na prova de autômatos. Então priorizaram estudar pra autômatos. Entre outras coisas. Não quero aborrecer ngm falando das nossas obrigações.
Em resposta à Ricardo Cillo
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Hugo Corbucci -
Pode postar suas dúvidas a vontade. Respostas a perguntas (que não sejam: este código está certo?) são o objetivo deste fórum.
O CUDA permite usar todas as GPUs da sua placa de vídeo concorrentemente sim. O uso delas é realmente o desafio nesse EP.
A idéia, nesse caso, é que algumas coisas que fazemos para otimizar o desempenho seqüencial, podem atrapalhar um programa altamente concorrente (já que envolve muito uso de memória). Pense em como você pode gerar uma solução bem simples só com concorrência. Deixe de lado todas as otimizações da solução seqüencial.
Arranje uma solução ruim que funcione. Quando ela estiver OK, aí pense em como você pode podar algumas possibilidades da árvore.
A API que o Cuda fornece para lidar com memória é bem simples. Você aloca memória compartilhada entre as GPUs e pode copiar de uma thread para outra (de uma GPU para outra). Daí em diante, o problema é todo seu
Lidar com a memória é um problema bem complicado. Por isso, minha sugestão seria tentar usar o mínimo de memória possível e abusar do processamento. A idéia é que, se as coisas rodam em paralelo, elas podem ser mais lentas que o mesmo passo no seqüencial porque ainda rodam "quase" n vezes mais rápido.
A resposta foi meio abstrata porque a pergunta tambem foi. Não quero dar aqui um algoritmo porque seria quebrar um pouco a competição mas tentei passar as idéias que podem ajudar. Se conseguir formular perguntas mais específicas relacionadas à memória ou aos processos, talvez eu possa ajudar mais diretamente.
O CUDA permite usar todas as GPUs da sua placa de vídeo concorrentemente sim. O uso delas é realmente o desafio nesse EP.
A idéia, nesse caso, é que algumas coisas que fazemos para otimizar o desempenho seqüencial, podem atrapalhar um programa altamente concorrente (já que envolve muito uso de memória). Pense em como você pode gerar uma solução bem simples só com concorrência. Deixe de lado todas as otimizações da solução seqüencial.
Arranje uma solução ruim que funcione. Quando ela estiver OK, aí pense em como você pode podar algumas possibilidades da árvore.
A API que o Cuda fornece para lidar com memória é bem simples. Você aloca memória compartilhada entre as GPUs e pode copiar de uma thread para outra (de uma GPU para outra). Daí em diante, o problema é todo seu
Lidar com a memória é um problema bem complicado. Por isso, minha sugestão seria tentar usar o mínimo de memória possível e abusar do processamento. A idéia é que, se as coisas rodam em paralelo, elas podem ser mais lentas que o mesmo passo no seqüencial porque ainda rodam "quase" n vezes mais rápido.
A resposta foi meio abstrata porque a pergunta tambem foi. Não quero dar aqui um algoritmo porque seria quebrar um pouco a competição mas tentei passar as idéias que podem ajudar. Se conseguir formular perguntas mais específicas relacionadas à memória ou aos processos, talvez eu possa ajudar mais diretamente.
Em resposta à Hugo Corbucci
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Alfredo Goldman -
Olá,
Apenas completando a resposta do Hugo existem placas Nvídia que processam
128 threads ao mesmo tempo (isto é, possuem 128 processadores simples). Isto sem considerar que existem mecanismos para multi-threading...
Alfredo
Apenas completando a resposta do Hugo existem placas Nvídia que processam
128 threads ao mesmo tempo (isto é, possuem 128 processadores simples). Isto sem considerar que existem mecanismos para multi-threading...
Alfredo
Em resposta à Alfredo Goldman
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Paulo Henrique Floriano -
Eu tenho uma dúvida quanto à forma de paralelizar o algoritmo.
Normalmente, com threads rodando separadamente, não é possível saber exatamente em que ordem as soluções vão ser encontradas e impressas, por isso, todas as idéias que meu grupo teve falham.
Existe algum jeito de paralelizar o programa que consiga imprimir as soluções em ordem ou devemos pensar em jeitos de ordenar as soluções?
Normalmente, com threads rodando separadamente, não é possível saber exatamente em que ordem as soluções vão ser encontradas e impressas, por isso, todas as idéias que meu grupo teve falham.
Existe algum jeito de paralelizar o programa que consiga imprimir as soluções em ordem ou devemos pensar em jeitos de ordenar as soluções?
Em resposta à Paulo Henrique Floriano
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Cauê Haucke Porta Guerra -
Estou tendo o mesmo problema
Em resposta à Cauê Haucke Porta Guerra
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Atol Fortin de Oliveira -
Eu tambem , sem contar o problema com a memoria ... um deles eh, quando eu declaro uma variavel global no meu codigo, e compilo com emu=1 nao tem problema nenhum, mas quando dou soh o make, ele reclama :
"Advisory: Cannot tell what pointer points to, assuming global memory space"
ao tentar acessar uma variavel global... e nao é no kernel.
Alguem sabe como arrumar isso? (ou isso nao precisa ser arrumado ... ? ).
"Advisory: Cannot tell what pointer points to, assuming global memory space"
ao tentar acessar uma variavel global... e nao é no kernel.
Alguem sabe como arrumar isso? (ou isso nao precisa ser arrumado ... ? ).
Em resposta à Atol Fortin de Oliveira
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Marcos Takechi Hirata -
eu acho que isso é resolvido copiando essa variável para dentro da memória para o cuda utilizando a função cudaMemcpy, esta função copia os dados que estão no host, ou seja, na CPU para a GPU. Ou declarar essa váriavel com __global__ alguma coisa, assim ele colocará essa variável para dentro do cuda tb!
Eu acho que isso resolve! Não tenho certeza! ^^
Eu acho que isso resolve! Não tenho certeza! ^^
Em resposta à Paulo Henrique Floriano
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Hugo Corbucci -
Façam o seguinte: deixem a ordem de lado por enquanto.
Considerem a ordenação como um bônus.
Prefiro que vocês se preocupem em paralelizar o máximo que puderem para achar um algoritmo BEM rápido do que se preocuparem com a ordenação.
Eu me viro para ordenar e verificar que tudo está lá.
Considerem a ordenação como um bônus.
Prefiro que vocês se preocupem em paralelizar o máximo que puderem para achar um algoritmo BEM rápido do que se preocuparem com a ordenação.
Eu me viro para ordenar e verificar que tudo está lá.
Em resposta à Hugo Corbucci
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Marcos Bonci Cavalca -
Bom, isso traz de volta a polêmica questão do adiamento.
Tirar o requisito da saída em ordem não complica em nada o EP, com certeza. Mas, em compensação, isso complica a comparação dos trabalhos, prevista no enunciado.
Até agora, quem tinha um programa que não dá a saída em ordem estaria teoricamente fora da competição. Mas esse mesmo programa pode muito bem ser o mais rápido de todos, e agora de repente está na disputa.
Por isso acho que seria justo haver um adiamento, para que sejam feitos os ajustes nos programas dos grupos que, como o meu, se prenderam ao problema da saída ordenada.
Veja bem que aqui se encaixa o conceito de justiça, já que estamos falando não só de entrega de EP, mas também de uma competição cujas regras mudaram na última hora.
Tirar o requisito da saída em ordem não complica em nada o EP, com certeza. Mas, em compensação, isso complica a comparação dos trabalhos, prevista no enunciado.
Até agora, quem tinha um programa que não dá a saída em ordem estaria teoricamente fora da competição. Mas esse mesmo programa pode muito bem ser o mais rápido de todos, e agora de repente está na disputa.
Por isso acho que seria justo haver um adiamento, para que sejam feitos os ajustes nos programas dos grupos que, como o meu, se prenderam ao problema da saída ordenada.
Veja bem que aqui se encaixa o conceito de justiça, já que estamos falando não só de entrega de EP, mas também de uma competição cujas regras mudaram na última hora.
Em resposta à Marcos Bonci Cavalca
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
Apoiado, companheiro ultra-jovem.
Em resposta à Marcos Bonci Cavalca
Re: Os diferentes níveis de paralelismo na solução do n-rainhas com GPU
por Hugo Corbucci -
Ok. A resposta tem duas partes, uma primeira onde digo não e outra onde digo sim então segurem seus ânimos ao lerem a primeira parte.
Ao meu ver, mudanças para não ter mais que ordenar envolvem tirar código. Espero que o código de impressão e o de armazenamento de solução esteja bem fatorado de toda forma. Ainda, eu só consegui pensar em dois jeitos de tratar a ordenação: pós processamento ou construção da solução. Se tiverem outra solução, por favor, compartilhem.
O pós processamento deveria ser BEM fácil de tirar já que é só não chamar sua função de ordenação. Por construção me parece mais complicado de garantir uma ordem aproveitando o multiprocessamento disponível já que não temos garantia de ordem de execução. Ao meu ver, nesse caso, só resta a opção de sincronizar threads para garantir ordem. Se for esse o caso, basta não sincronizar.
De ambas formas, tirar a ordenação deveria ser algo bem trivial e que dê tempo de fazer em 2 horas contando com os devidos testes. Logo, não acho que isso necessita de um adiamento.
Por outro lado, eu entendo que vocês possam tentar novas abordagens sabendo que não precisa garantir ordem ou mesmo usar alguns truques para salvar um pouco de memória ou processamento.
De todo jeito, se vocês já estão mais preocupados com a competição que com o EP, vocês já estão melhor do que a grande maioria dos grupos ao que parece. O que indicaria que, quanto menos tempo para os adversários, melhor para vocês ;)
Enfim, o EP vai ser adiado apesar das minhas características inhumanas. Não por esse motivo mas pelas demonstração de empenho em atingir o objetivo e pelo fato de eu preferir imensamente corrigir EPs bons do que EPs ruins ou medíocres. Mais detalhes na thread sobre o adiamento.
Ao meu ver, mudanças para não ter mais que ordenar envolvem tirar código. Espero que o código de impressão e o de armazenamento de solução esteja bem fatorado de toda forma. Ainda, eu só consegui pensar em dois jeitos de tratar a ordenação: pós processamento ou construção da solução. Se tiverem outra solução, por favor, compartilhem.
O pós processamento deveria ser BEM fácil de tirar já que é só não chamar sua função de ordenação. Por construção me parece mais complicado de garantir uma ordem aproveitando o multiprocessamento disponível já que não temos garantia de ordem de execução. Ao meu ver, nesse caso, só resta a opção de sincronizar threads para garantir ordem. Se for esse o caso, basta não sincronizar.
De ambas formas, tirar a ordenação deveria ser algo bem trivial e que dê tempo de fazer em 2 horas contando com os devidos testes. Logo, não acho que isso necessita de um adiamento.
Por outro lado, eu entendo que vocês possam tentar novas abordagens sabendo que não precisa garantir ordem ou mesmo usar alguns truques para salvar um pouco de memória ou processamento.
De todo jeito, se vocês já estão mais preocupados com a competição que com o EP, vocês já estão melhor do que a grande maioria dos grupos ao que parece. O que indicaria que, quanto menos tempo para os adversários, melhor para vocês ;)
Enfim, o EP vai ser adiado apesar das minhas características inhumanas. Não por esse motivo mas pelas demonstração de empenho em atingir o objetivo e pelo fato de eu preferir imensamente corrigir EPs bons do que EPs ruins ou medíocres. Mais detalhes na thread sobre o adiamento.