Entries Tagged 'ANSI C' ↓

Apenas uma dica rápida, outro dia me peguei programando em pThreads e, como qualquer coisa um pouco mais complexa, cai no famoso “race-condition”, quando uma thread tenta utilizar dados ao mesmo tempo em que outra thread tenta (por exemplo) criar os dados.
Existem várias formas de se resolver isso, porém acredito que a mais simples é a utilização de mutex (atenção, isso é exclusivo do SO, no nosso caso sistemas baseados em UNIX como Linux ou FreeBSD). A idéia do mutex é:

1. Cria uma variável do tipo pthread_mutex_t
2. Inicializa
3. Dentro da thread, efetue um lock na área crítica da memória
4. Trabalhe na memória
5. Efetue um unlock da área crítica.

Vamos ao exemplo mais simples possível: Continue reading →

Como muitos sabem, uma das minhas maiores paixões justamente a programação paralela. Faz um certo tempo (desde o mestrado), que não programo para paralelismo, nem em algoritmos genéticos, nem autômatos celulares, etc. Obviamente isso muito me fazia falta e, resolvi fazer um upgrade na máquina, trocando a velha boa de guerra GeForce 8500 GT, por uma GTX 580 (pequeno upgrade ).

Para relembrar como se programa em CUDA, resolvi utilizar a versão 5.0, recém lançada, e entender como funciona a biblioteca CURAND para a geração de números aleatórios em GPU (extremamente importante ao utilizarmos AG). Os resultados que obtive foram, extremamente satisfatórios, veja dois exemplos de execução:

• Geração de 787.021.824 números aleatórios utilizando uma distribuição binomial

*********INFO********
*min:0
*max:100
*qtd:787021824
*output:binomial.csv
*distribution: BINOMIAL
*Verify? NO
********************
[*] Initializing host memory…OK (0.00000 ms)
[*] Initializing GPU memory…OK (1.76182 ms)
[*] Creating random numbers…OK (3018.16577 ms)
[*] Accumulatting…OK (1090.85291 ms)
[*] Writing accumulatted values to ‘binomial.csv’…OK
[*] Cleaning up memory…OK

Geração de 787.021.824 números aleatórios utilizando uma distribuição uniforme:

[*] Initializing host memory…OK (0.00000 ms)
[*] Initializing GPU memory…OK (1.76829 ms)
[*] Creating random numbers…OK (36.34749 ms)
[*] Accumulatting…OK (707.11194 ms)
[*] Writing accumulatted values to ‘/home/zarnick/tmp/uniform.csv’…OK
[*] Cleaning up memory…OK

Essa velocidade, convence?

Continue reading →

Então, eu programao em C, programo a tanto tempo que até não me lembro quando comecei. E, como bom programador de C, eu tenho alguns vícios e algumas coisas que sempre levei por verdade.
Vícios:

• Sempre estruturar um bloco na ordem: declarações->código, nunca colocar uma declaração depois de iniciar um código.
• Sempre tomar cuidado com o tamanho do que vai na Stack.

E por verdade, sempre levei que o seguinte código não funciona:

#include <stdio.h>
int main(int argc, char *argv[]){
  int qtd;
  scanf("%d",&qtd);
  int vet[qtd];
  int i;
  for(i=0;i<qtd;i++) vet[i]=i;
  return 0;
}

Pois bem, esse código quebrava tudo que eu tomava por verdade, estou declarando uma variável depois de inicializar um código e, estou tentando alocar um vetor de tamanho desconhecido em tempo de compilação, na memória stack, não deveria funcionar certo? Continue reading →

Dennis Ritchie, um dos pioneiros e cientistas mais visionários, morreu aos 70 anos de uma doença ainda desconhecida. Acredito que não é necessário falar o quanto ele foi importante, sem ele não teríamos C, UNIX, o Mac OSX, iOS, Windows, Linux, UNIX, enfim, praticamente nada.
Parece que ultimamente estamos perdendo cada vez mais pessoas importantes, o que me faz pensar, quem vai substituir essas pessoas?

Quem gosta de CUDA e Linux, sabe que não existe (a não ser que você procure na internet) suporte para CUDA nas autotools. Bom, eu procurei a um bom tempo atrás e criei um template para iniciar todos os meus projetos de CUDA e agora, não apenas estou liberando ele como um template, mas também estou criando um repositório completo sobre CUDA no meu SVN onde obviamente esse é o primeiro projeto.
Sem demoras, é possível efetuar o download e entender um pouco mais do projeto na página do projeto.
PS: Saiu a versão 3.1 com suporte a printf() em interfaces Fermin

Bom, todos nós sabemos que rand() nos retorna uma distribuição uniforme de números aleatórios, na realidade praticamente todos os geradores de números aleatórios nos retorna uma distribuição uniforme, o problema é como utilizamos. Procurando sobre isso, encontrei esse artigo que explica o motivo do “erro” de utilização e como corrigir o mesmo.
Enquanto ele não resolve o problema para geração de números aleatórios em paralelo (minha mais nova paixão), ele dá boas dicas de como solucionar isso, e provavelmente como solucionar também em paralelismo (já que o problema está na utilização e não no algorítmo).
Vale a pena dar uma lida, esse é um assunto muito importante para todos, principalmente para quem ainda gera os números dessa forma:

srand(time(NULL));
int num = rand()%max;

Quem já programou em clusters (ou até mesmo utilizando paralelismo) sabe das enormes vantagens que o paralelismo pode trazer. O que poucas pessoas sabem é que você pode ter tudo isso na sua casa, programando em sua placa de vídeo nVidia utilizando CUDA, uma arquitetura de programação paralela genérica, disponibilizada Free pela nVidia.
Diferente de várias formas de programação paralela, as placas da nVidia utilizam muito mais transistores para para processamento de dados no lugar de memória, dessa forma temos o chamado SIMT(Single Instruction Multiple Threads), não vou explicar exatamente como o CUDA faz ou até mesmo como programar para CUDA agora (mais tarde sem dúvida vou colocar algum código bem explicado, mas o tempo está cada vez mais escasso). Basta falar que em uma GeForce 8500GT temos 16 cores separados em 2 processadores, e uma GTX280 conta com 280 cores, o que a nVidia fez que é extremamente elegante, foi separar o número de threads possíves pela quantidade de memória a ser processada, e não pela quantidade de processadores, dessa forma você tem uma escalabilidade praticamente perfeita.
Explicando um pouco melhor isso, para rodar algo em uma GPU utilizando CUDA você precisa criar um Grid de execução, cada Grid possui um conjunto de Blocks (blocos de threads) e cada Block possui um número n de threads que é ditado pela quantidade de dados a ser processado. Mais interessante ainda é que cada bloco de thread possui um espaço de memória do tipo shared (compartilhada) que é extremamente rápida, porém apenas as threads daquele bloco podem acessar esse espaço de memória. Além disso existe a memória do tipo global, que fica toda na GPU e qualquer thread (ou bloco) pode acessar, e outros tipos (constant, register, local e texture).
Bom, esse não é nem o básico sobre CUDA, é apenas um texto para dar um gostinho de quero mais. Um pequeno teste que fiz foi portar o algoritmo de ordenação Bitonic Sort para CUDA (código retirado dessa thread do Forum da nVidia), e comparar a versão sem paralelismo com a versão do CUDA, pois bem, o programa faz isso:

1. Cria um array de 2^25 números = 33.554.432
2. Copia a memória para a GPU (apnas na versão CUDA)
3. Popula o array com o indíce invertido (array[0]=33554432, …, array[33554432]=0)
4. Ordena utilizando o algoritmo Bitonic Sort
5. Copia de GPU para a memória local de volta (apenas na versão CUDA)
6. Valida os dados

na versão simples (sem paralelismo) tudo isso demorou em média 4 minutos e meio para executar, na versão CUDA demorou 0.3 segundos em uma GeForce 8500GT. Isso convence do poder do CUDA?

Para saber mais:

CUDA Zone: Site oficial com uma extensa documentação sobre o CUDA
Dr.Dobbs: Tutorial fantástico sobre CUDA

Demorou, vou assumir, mas finalmente eu programei mais uma estrutura de dados simples, a árvore. Vou preparar uma explicação sobre o que é uma árvore em computação (essa pode ser um pouco complexa) e assim que eu tiver eu posto aqui, mas por enquanto vocês podem ver o código no svn (http://svn.geekvault.org/c/trees)

Have fun.

Certo dia eu estava conversando com um amigo meu sobre C e ele me falou que a coisa que ele mais odiava era ter que tomar cuidado com a ordem dos include que ele fazia quando iniciava um projeto em C. Ora, vamos pensar um pouco, se você incluir duas vezes o cabeçalho stdio.h por exemplo, em dois arquivos diferentes, e incluir os dois, não da erro certo?
Continue reading →

Quem nunca teve o problema clássico de ter que armazenar uma quantidade X de valores, sem limite máximo e com buscas, remoção e adição em qualquer lugar de forma rápida? Pois bem as listas estão ai exatamente para isso. Claro, poderíamos criar um vetor com um número X, e caso precisa-se, utilizaríamos realloc() para aumentar o vetor. Porém, qualquer coisa que fizéssemos com um vetor (ordernar, busca, remoção, adição) é muito custosa, uma lista ligada nos permite fazer isso de forma rápida, customizáda, e econômica. Vamos explicar aqui a lista duplamente ligada, uma das mais completas, porém vamos mostrar também a teoria de suas variações (lista ligada e lista circular).
Continue reading →