Posts Tagged ‘ estudo ’

Tempo de processamento – Funções muito rápidas

Medir o tempo que uma função gasta para ser executada parece ser bem simples, olhando superficialmente.

Teoricamente, só seria necessário gravar o tempo de início e subtrair do tempo do fim.

O problema nesse tipo de medição é que, nos PCs só temos acesso à milisegundos (10⁻³ s) no relógio e uma instrução que seja processada em poucos ciclos de clock dura alguns nanosegundos (10⁻⁹ s).

O que fazer para medir esses nanosegundos?

A primeira solução é usar probabilidade:

pulso

Olhando a imagem, podemos perceber que a medição de tempo pode ser tanto zero ou um, dependendo se a função começou a ser executada próximo do início da borda de subida do pulso de clock.

Assim, mandamos a função ser executada centenas ou milhares de vezes e teremos como encontrar sua duração, com um erro que diminui com o aumento do número de execuções.

Note que o processador conta ciclos de clock, que na função clock() duram 1 milisegundo cada. Por isso, em alguns lugares teremos divisões por 1000.

Exemplo:

#define N 1000000
tempo_inicial = clock() / 1000;
for (i =0; i < N; i++) {
    funcao();
}
tempo_final = clock() / 1000;
duracao = (tempo_final - tempo_inicial)/N;

Essa solução funciona muito bem, mas na medida que você vai aumentando a complexidade ou os dados de entrada vai ser preciso ficar ajustando o número de execuções, para que não demore tempo demais para dar precisão de nanosegundos à uma função que demore microsegundos ou até alguns milisegundos.

Assim, é aconselhado usar um medidor de tempo máximo para executar instruções. Ou seja, antes de executar a função novamente, deve-se conferir se o tempo de execução de esgotou ou não, garantindo um número mais alto de execuções para funções mais rápidas e um número menor (com erro maior) para funções mais demoradas.

Exemplo:

#define tTotal 1000
numExecs = 0;
t1 = clock();
limite = t1 + tTotal;
while ( clock() < limite ) {
    funcao();
    numExecs++;
}
t2 = clock();
duracao = (t2-t1) / (numExecs*1000);

Como o Sistema Operacional está quase sempre realizando operações leves, podemos ter erros de medidas caso a função fosse rodada apenas uma vez, como inicialmente proposto. Com o uso de probabilidade, podemos diluir esse gasto entre todas as medidas, tornando-o desprezível.

Alguns erros de medida podem ser gerados por causa do “warm-up” de cache, entre outras coisas, sendo aconselhado repetir o teste algumas vezes. O valor medido será quase constante após algumas medidas.

Uma Observação:

Caso a função a ser medida seja muito rápida, esse segundo método pode criar um overhead, fazendo com que o tempo total para entradas com poucos dados seja confundido com o gasto de processamento do código do nosso cronômetro.

Para amenizar isso, é possível repetir o bloco sem chamar a função e depois subtrair o tempo gasto do tempo total anterior.

Note que isso só será necessário em funções que durem menos de microsegundos.

VHDL

Very complicated Hardware Description Language.

Pessoa sobre VHDL

Claro que não significa isso, mas bem que poderia.

Aprendendo VHDL para programar uma CPLD a fazer um simples circuito para criar um pulso ao clique de um botão me custou 3 dias.

E o projeto era simples: Criar um divisor de frequência para o conseguir 100Hz ao invés de 250MHz, esperar 3 ciclos do novo clock após o botão ser pressionado (evita ruído) e depois gerar um pulso para a saída.

Placa UP1 da Altera

Placa UP1 da Altera

Coisas que podem ser feitas em outras linguagens de programação dão problemas em VHDL, como mudar o valor de uma das variáveis duas vezes no processo.

Acho melhor começar a ler mais sobre VHDL.

Fui.