processamento de imagem de vários segmentos em C ++

https://stackoverflow.com/questions/326487

11-07-2019
|

Pergunta

Eu estou trabalhando em um programa que manipula imagens de diferentes tamanhos. Muitas dessas manipulações ler dados de pixel de uma entrada e gravação para uma saída separada (por exemplo, blur). Isso é feito em uma base per-pixel.

Esses mapulations imagem são muito estressante para o CPU. Eu gostaria de usar multithreading para acelerar as coisas. Como eu faria isso? Eu estava pensando em criar um thread por fila de pixels.

Eu tenho vários requisitos:

Tamanho do executável deve ser minimizado. Em outras palavras, eu não posso usar bibliotecas massivas. Qual é o peso-leve mais, biblioteca de threading portátil para C / C ++?
Tamanho do executável deve ser minimizado. Eu estava pensando em ter um forEachRow função (fp *) que corre um fio para cada linha, ou mesmo um forEachPixel (fp *), onde fp opera em um único pixel em seu próprio segmento. Qual é melhor?
- Devo usar funções normais ou functors ou functionoids ou algumas funções lambda ou ... outra coisa?
- Algumas operações usar otimizações que requerem informações a partir do pixel anterior processado. Isso faz com que forEachRow favorável. Faria usando forEachPixel ser melhor, mesmo considerando isso?
Será que eu preciso para bloquear a minha read-only e matrizes só de escrita?
- A entrada é somente leitura a partir, mas muitas operações exigem a entrada de mais de um pixel na matriz.
- O ouput está escrito apenas uma vez por pixel.
A velocidade também é importante (é claro), mas otimizar o tamanho do executável tem precedência.

Graças.

Mais informações sobre este tópico para os curiosos: C ++ paralelização Bibliotecas: OpenMP vs. Tópico Building Blocks

Solução

Se suas sustentações do compilador OpenMP (eu sei VC ++ 8.0 e 9.0 fazer, como faz gcc), ele pode fazer coisas como esta muito mais fácil de fazer.

Você não quer apenas fazer um monte de tópicos - há um ponto de retornos decrescentes, onde a adição de novos tópicos atrasa as coisas como você começar a ficar mais e mais trocas de contexto. Em algum momento, usando muitos segmentos pode realmente fazer a versão paralela mais lento do que apenas usando um algoritmo linear. O número ideal de threads é uma função do número de CPUs / núcleos disponíveis, e a porcentagem de tempo cada thread gasta bloqueado em coisas como I / O. Dê uma olhada na este artigo por Herb Sutter para alguma discussão sobre ganhos de desempenho paralelas.

OpenMP permite que você facilmente adaptar o número de threads criadas para o número de CPUs disponíveis. Usá-lo (especialmente em dados de processamento de casos), muitas vezes envolve simplesmente colocar em poucas #pragma omps no código existente, e deixando a alça compilador criação de threads e sincronização.

Em geral - desde que os dados não está mudando, você não terá de bloqueio somente leitura de dados. Se você pode ter certeza que cada slot de pixel só vai ser escrito uma vez e você pode garantir que toda a escrita tenha sido concluída antes de começar a ler a partir do resultado, você não terá que bloquear o que quer.

Para OpenMP, não há necessidade de fazer nada de especial, tanto quanto objetos functors / função. Escrevê-lo do jeito que faz mais sentido para você. Aqui está um exemplo de processamento de imagem de Intel (convertidos rgb para tons de cinza):

#pragma omp parallel for
for (i=0; i < numPixels; i++)
{
   pGrayScaleBitmap[i] = (unsigned BYTE)
       (pRGBBitmap[i].red * 0.299 +
        pRGBBitmap[i].green * 0.587 +
        pRGBBitmap[i].blue * 0.114);
}

Isto divide automaticamente em tantos tópicos como você tem CPUs, e atribui uma seção da matriz para cada segmento.

Outras dicas

NÃO embarcar em enfiar levemente! As condições de corrida pode ser uma grande dor na bunda para descobrir. Especialmente se você não tem muita experiência com tópicos! (Você foi avisado:!! Aqui há dragões grandes cabeludo não-determinístico dragões impossíveis-se confiantemente-reproduzirem)

Sabe o impasse é? Como cerca de Livelock?

Dito isto ...

Como ckarmann e outros já sugeriu: Use um modelo de trabalho em fila. Um thread por núcleo da CPU. Quebrar o trabalho em pedaços N. Faça os pedaços razoavelmente grande, como muitas linhas. Como cada segmento torna-se livre, ela senões o próximo pedaço de trabalho fora da fila.

No mais simples IDEAL versão, você tem núcleos de N, N fios e subpartes N do problema com cada thread sabendo desde o início exatamente o que ele vai fazer.

Mas isso não costuma acontecer na prática, devido à sobrecarga de iniciar / parar threads. Você realmente quer os fios de já ser gerado e à espera de ação. (Por exemplo, em um semáforo.)

O próprio modelo de trabalho-fila é bastante poderoso. Ele permite que você paralelizar coisas como quick-sort, que normalmente não paralelizar através N fios / núcleos graciosamente.

Mais tópicos do que núcleos? Você está apenas perdendo em cima. Cada segmento tem a sobrecarga. Mesmo em # tópicos = # núcleos, você nunca vai conseguir um fator perfeito Nx aceleração.

Uma discussão por linha seria muito ineficiente! Uma discussão por pixel? Eu não quero nem pensar nisso. (Essa abordagem per-pixel faz muito mais sentido quando se joga com unidades do processador vectorized como tiveram nas velhas Crays. Mas não com tópicos!)

Libraries? Qual é a sua plataforma? No Unix / Linux / g ++ eu sugiro pthreads e semáforos. (Pthreads também está disponível sob janelas com uma camada de compatibilidade Microsoft. Mas, uhgg. Eu realmente não confiar nele! Cygwin pode ser uma escolha melhor lá.)

No Unix / Linux, man :

* pthread_create, pthread_detach.
* pthread_mutexattr_init, pthread_mutexattr_settype, pthread_mutex_init,
* pthread_mutexattr_destroy, pthread_mutex_destroy, pthread_mutex_lock,
* pthread_mutex_trylock, pthread_mutex_unlock, pthread_mutex_timedlock.
* sem_init, sem_destroy, sem_post, sem_wait, sem_trywait, sem_timedwait.

Algumas pessoas como variáveis ??de condição pthreads. Mas eu sempre preferi semáforos POSIX 1003.1b. Eles lidar com a situação onde você quer sinalizar outro segmento ANTES ele começa a esperar um pouco melhor. Ou onde outro segmento é assinalado várias vezes.

Oh, e faça um favor: Enrole seu segmento / mutex / semáforo pthread chamadas em um par de classes C ++. Isso vai simplificar muito!

que eu preciso para bloquear a minha read-only e matrizes só de escrita?

Depende do seu hardware e software precisa. Normalmente somente leitura matrizes podem ser livremente compartilhados entre threads. Mas há casos em que não é assim.

A escrita é a mesma coisa. Normalmente, desde que apenas um thread está escrevendo para cada local de memória particular, você está ok. Mas há casos em que não é assim!

A escrita é mais problemática do que a leitura que se pode chegar a estas situações fencepost estranhas. A memória é muitas vezes escrito como palavras não bytes. Quando uma thread escreve parte da palavra, e outro escreve uma parte diferente, dependendo do momento exato da qual thread faz o quê e quando (por exemplo, não-determinístico), você pode obter alguns resultados muito imprevisíveis!

eu jogar pelo seguro: Dê a cada fio de sua própria cópia das áreas de leitura e gravação. Depois elas são feitas, copiar parte de trás de dados. Tudo sob mutex, é claro.

A menos que você está falando de gigabytes de dados, blits de memória são muito rápidos. Que alguns microssegundos de tempo de desempenho só não vale a pena o pesadelo de depuração.

Se você fosse para compartilhar uma área de dados comuns entre threads usando semáforos, a colisão / espera ineficiências mutex se acumulam e devastar sua eficiência!

Olhe, limites de dados limpas são a essência de um bom código multi-thread. when seus limites não são claros, que é quando você entrar em apuros.

Da mesma forma, é essencial para manter tudo no limite mutexed! E para manter as áreas mutexed curto!

Tente evitar o bloqueio mais de um mutex ao mesmo tempo. Se você fizer bloqueio mais de um mutex, sempre travá-los na mesma ordem!

Sempre que possível o uso de verificação de erros ou mutexes recursiva. mutexes FAST são apenas pedindo para ter problemas, com muito pouco real (medido) o ganho de velocidade.

Se você entrar em uma situação de impasse, executá-lo no gdb, hit ctrl-c, visite cada segmento e backtrace. Você pode encontrar o problema muito rapidamente dessa maneira. (Livelock é muito mais difícil!)

Uma última sugestão: Constituição-lo single-threaded, em seguida, começar a otimizar. Em um sistema single-core, você pode encontrar-se ganhar mais velocidade a partir de coisas como foo [i ++] = bar ==> * (foo ++) = bar que de threading.

Adenda: O que eu disse sobre manter áreas mutexed curto acima? Considere dois tópicos: (. Dado um objeto mutex global compartilhada de uma classe Mutex)

/*ThreadA:*/ while(1){  mutex.lock();  printf("a\n");  usleep(100000); mutex.unlock(); }
/*ThreadB:*/ while(1){  mutex.lock();  printf("b\n");  usleep(100000); mutex.unlock(); }

O que vai acontecer?

Sob a minha versão do Linux, um segmento será executado continuamente e o outro vai morrer de fome. Muito raramente eles vão mudar de lugar quando uma troca de contexto ocorre entre mutex.unlock () e mutex.lock ().

Adenda: No seu caso, isso é pouco provável que seja um problema. Mas com outros problemas um pode não saber com antecedência quanto tempo um determinado trabalho pedaço levará para ser concluído. Quebrando um problema em 100 partes (em vez de 4 partes) e usando um trabalho-fila para dividi-lo em frente 4 núcleos suaviza tais discrepâncias.

Se um trabalho pedaço leva 5 vezes mais tempo para concluir do que o outro, bem, tudo se equilibra no final. Embora com muitos pedaços, a sobrecarga de aquisição de novos work-pedaços cria atrasos perceptíveis. É um ato de equilíbrio específico de problemas.

Eu recomendaria boost::thread e boost::gil (genérico imagem libray). Porque há bastante tanto modelos envolvidos, eu não tenho certeza se o código de tamanho ainda será aceitável para você. Mas é parte do impulso, por isso é provavelmente olhar um valor.

Como um pouco de uma idéia-campo deixou ...

O sistema está executando isso em? Você já pensou em usar a GPU em seus PCs?

Nvidia têm a CUDA APIs para este tipo de coisa

Eu não acho que você quer ter um thread por fila. Não pode haver um monte de linhas, e você vai gastar muita memória / recursos da CPU apenas o lançamento / destruir os fios e para a CPU para mudar de um para o outro. Além disso, se você tiver P processadores com núcleo de C, você provavelmente não vai ter um monte de ganho com mais de tópicos C * P.

Eu aconselho você a usar um número definido de threads de cliente, por exemplo, N fios e usar o fio condutor de sua aplicação para distribuir as linhas a cada thread, ou eles podem simplesmente começar a instrução de uma "fila de trabalho". Quando um segmento terminou com uma fileira, ele pode verificar nesta fila para outra linha para fazer.

Como para as bibliotecas, você pode usar boost :: segmento, que é bastante portátil e não muito pesado.

Posso perguntar qual plataforma você está escrevendo isso? Eu estou supondo que porque o tamanho executável é um problema que você não está targetting em uma máquina desktop. Caso em que é que a plataforma tem vários núcleos ou hyperthreaded? Se não, então a adição de tópicos para a sua aplicação poderia ter o efeito oposto e retardá-lo ...

Para otimizar transformações de imagem simples, você é muito melhor fora de usar SIMD vector de matemática do que tentar vários thread-seu programa.

Verifique a Criando uma de processamento de imagem de rede passo a passo no MSDN, o que explica como usar padrões paralelas Biblioteca para compor um pipeline de processamento de imagem em simultâneo.

Eu também sugerem Boost.GIL , que gera altamente código eficiente. Por exemplo simples de multi-roscado, verificar gil_threaded por Victor Bogado. O href="http://dancinghacker.com/code/dataflow/dataflow/signals/introduction/examples/gil.html" rel="nofollow"> Uma rede de processamento de imagem explica um interestnig fluxo de dados modelo também.

Uma discussão por linha pixel é insano, melhor ter em torno de n-1 a tópicos 2 N (para n CPU), e fazer com que cada um laço buscar um jobunit (pode ser uma linha, ou outro tipo de partição)

no UNIX-like, de uso pthreads é simples e leve.

Talvez escrever sua própria biblioteca pequena que implementa algumas funções de threading padrão usando #ifdef de para cada plataforma? Não há realmente muito a ele, e que reduziria a maneira tamanho do executável mais do que qualquer biblioteca que você poderia usar.

Update: E para distribuição do trabalho - dividir a sua imagem em pedaços e dar cada thread um pedaço. De modo que quando ele é feito com a peça, ele é feito. Desta forma, você evitar a implementação de filas de trabalho que irá aumentar ainda mais o tamanho do seu executável.

Eu acho que, independentemente do modelo de segmentação que você escolher (boost, pthread, threads nativas, etc). Eu acho que você deve considerar um pool de threads ao invés de uma linha por linha. Threads em um pool de threads são muito barato para "iniciar" uma vez que já são criados na medida em que o sistema operacional está em causa, é apenas uma questão de dar-lhe algo para fazer.

Basicamente, você poderia ter dizer 4 threads em sua piscina. Em seguida, em série, para cada pixel, diga o próximo segmento no pool de threads para processar o pixel. Desta forma, você está efetivamente processamento não mais de 4 pixels de cada vez. Você poderia fazer o tamanho da piscina, com base quer na preferência do usuário ou sobre o número de CPUs os relatórios do sistema.

Este é de longe o IMHO mais simples maneira de adicionar enfiar a uma tarefa SIMD.

O seu compilador não suporta OpenMP. Outra opção é usar uma abordagem de biblioteca, tanto da Intel Threading Building Blocks e Microsoft Runtime de simultaneidade estão disponíveis (VS 2010).

Há também um conjunto de interfaces de chamadas da Biblioteca Padrão Paralela, que são suportados por ambas as bibliotecas e estes têm um templated parallel_for chamada biblioteca. assim em vez de:

#pragma omp parallel for 
for (i=0; i < numPixels; i++) 
{ ...}

você escreveria:

parallel_for(0,numPixels,1,ToGrayScale());

onde ToGrayScale é um functor ou ponteiro para função. (Nota se suas sustentações do compilador lambda expressões que ele provavelmente não pode inline functor como uma expressão lambda).

parallel_for(0,numPixels,1,[&](int i)
{  
   pGrayScaleBitmap[i] = (unsigned BYTE)  
       (pRGBBitmap[i].red * 0.299 +  
        pRGBBitmap[i].green * 0.587 +  
        pRGBBitmap[i].blue * 0.114);  
});

-Rick

Eu acho mapa / framework reduzir será a coisa ideal para uso nesta situação. Você pode usar o Hadoop streaming para usar o aplicativo C ++ existente.

Apenas implementar o mapa e reduzir postos de trabalho.

Como você disse, você pode usar maniputations no nível de linha como uma tarefa mapa e combinar as manipulações nível de linha para a imagem final na tarefa reduzir.

Hope isso é útil.

É muito possível, que gargalo não é CPU, mas a largura de banda de memória, de modo multi-threading não vai ajudar muito. Tente minimizar o acesso à memória e trabalhar em blocos de memória limitada, de modo que mais dados podem ser armazenados em cache. Eu tive um problema semelhante há um tempo atrás e eu decidi otimizar meu código para usar instruções SSE. aumento de velocidade era quase 4x por fio simples!

Você também pode usar bibliotecas como IPP ou o Cassandra Visão C ++ que são na sua maioria muito mais otimizado do que você próprio código.

Há uma outra opção de usar a montagem para otimização. Agora, um projeto empolgante para a geração de código dinâmico é softwire (que remonta por algum tempo - aqui é site do projeto original). Ele foi desenvolvido por Nick Capens e cresceu em agora disponível comercialmente SwiftShader . Mas o spin-off da softwire original ainda está disponível em gna.org.

Este poderia servir como uma introdução para a sua solução .

Pessoalmente, eu não acredito que você pode obter um desempenho significativo, utilizando múltiplas threads para o seu problema.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow