O que é o oposto de “embaraçosamente paralelo”?

Question

De acordo com a Wikipedia, um "embaraçosamente paralelo" problema é aquele para o qual é exigido pouco ou nenhum esforço para separar o problema em uma série de tarefas paralelas. Raytracing é frequentemente citado como um exemplo porque cada raio pode, em princípio, ser processados ??em paralelo.

Obviamente, alguns problemas são muito mais difícil de paralelizar. Alguns podem até ser impossível. Eu estou querendo saber o que termos são utilizados e quais os exemplos padrão são para esses casos mais difíceis.

Posso propor "Irritantemente Sequential" como um nome possível?

Answer 1

inerentemente sequencial .

Exemplo: O número de mulheres não vai reduzir a duração da gravidez.

Answer 2

Há mais de um oposto de um "embaraçosamente paralelo" problema.

Perfeitamente sequencial

Uma frente é um não paralelizável problema, isto é, um problema para o qual não aceleração pode ser alcançado através da utilização de mais de um processador. Várias sugestões foram já publicadas, mas eu proponho ainda outro nome:. perfeitamente sequencial problema

Exemplos: I / O-bound problemas ", calcular f ^1000000 (x ₀ )" tipo de problemas, calculando certo funções criptográficas hash .

Comunicação intensivo

Outra frente é um problema paralelizável que exige muita comunicação paralela (a -comunicação intensiva problema). Uma implementação de tal problema um irá dimensionar corretamente somente em um supercomputador com alta largura de banda e baixa latência de interconexão. Compare isso com os problemas embaraçosamente paralelos, implementações de que funcionar de forma eficiente mesmo em sistemas com muito pobre interconexão (por exemplo fazendas ).

Um exemplo notável de um problema-comunicação intensiva: resolver A x = b onde A é uma matriz grande, densa. Por uma questão de fato, uma implementação do problema é usado para compilar o TOP500 classificação. É um bom ponto de referência, uma vez que enfatiza tanto o poder computacional dos processadores individuais e a qualidade de interconexão (devido à intensidade da comunicação).

Em termos mais práticos, qualquer modelo matemático que resolve um sistema de equações diferenciais parciais em uma grade regular usando stepping tempo discreto (pense: previsão do tempo, in silico testes de colisão), é paralelizável por domínio decomposição . Isso significa que, cada CPU cuida de uma parte do grid, e no final de cada passo de tempo as CPUs trocar seus resultados na região fronteiras com CPUs "próximo". Estas trocas tornar esta classe de problemas-comunicação intensiva.

Answer 3

Im tendo um momento difícil não postar isso ... porque eu sei que não acrescentam nada à discussão .. mas para todos os fãs southpark lá fora

"Super série!"

Answer 4

"Teimosamente série"?

Answer 5

O oposto de embarassingly paralelo é de Amdahl Lei, que diz que algumas tarefas não pode ser paralelas, e que o tempo mínimo de uma tarefa perfeitamente paralelo exigirá é ditada pela porção puramente sequencial dessa tarefa.

Answer 6

"standard" exemplos de processos sequenciais:

• fazer um bebê: “programas Crash falham porque eles são baseados em teoria de que, com nove mulheres grávidas, você pode obter um bebê de um mês” - atribuída a Werner von Braun
• cálculo do pi, e, sqrt (2), e outros números irracionais para milhões de dígitos: a maioria algoritmos sequencial
• navegação:. Para ir do ponto A ao ponto Z, você deve primeiro passar por alguns pontos intermediário B, C, D, etc
• O método de Newton: você precisa de cada aproximação, a fim de calcular o próximo, melhor aproximação
• autenticação desafio-resposta
• fortalecimento chave
• cadeia de hash
• Hashcash

Answer 7

P-completo (mas que não se sabe com certeza ainda).

Answer 8

Eu uso "humilhantemente Sequential"

Paul

Answer 9

"Gladdengly Sequential"

Answer 10

Tudo tem a ver com dependências de dados. Embaraçosamente problemas paralelos são aqueles para os quais a solução é composta de muitas partes independentes. Problemas com o oposto dessa natureza seriam aqueles que têm dependências de dados maciços, onde há pouco ou nada que pode ser feito em paralelo. Degeneratively dependente ?

Answer 11

O termo que eu ouvi na maioria das vezes é "fortemente acoplado", em que cada processo deve interagir e comunicar muitas vezes, a fim de compartilhar dados intermediário. Basicamente, cada processo depende dos outros para completar o seu cálculo.

Por exemplo, o processamento de matriz envolve frequentemente a partilha valores de fronteira nas extremidades de cada partição matriz.

Isto está em contraste com problemas embarassingly paralelas (ou fracamente acoplados), onde cada parte do problema é completamente auto-contido, e não (ou muito pouco) IPC é necessária. Pense paralelismo master / trabalhador.

Answer 12

boastfully seqüencial.

Answer 13

Eu sempre preferi 'infelizmente seqüencial' ala a fase de partição em quicksort.

Answer 14

Se alguma vez se deve especular o que seria como ter, incorrigivelmente problemas sequenciais naturais, tente

alegremente sequencial

para contador de ' embaraçosamente paralelo '.

Answer 15

"Completamente de série?"

Ele realmente não deve surpreender que os cientistas pensam mais sobre o que pode ser feito do que o que não pode ser feito. Especialmente neste caso, em que a alternativa a paralelização está fazendo tudo como um faria normalmente.

Answer 16

Completamente non-paralelizável? Pessimally paralelizável?

Answer 17

O oposto é "desconcertante de série".

Answer 18

tendo em conta que o paralelismo é o ato de fazer muitos trabalhos ao mesmo tempo etapa t. o contrário pode haver problemas de tempo sequencial

Answer 19

Um exemplo problema inerentemente sequencial. Isso é comum em pacotes CAD e alguns tipos de análise de engenharia.

passagem de árvore com dependências de dados entre os nós.

Imagine que atravessa um gráfico e adicionando-se pesos dos nodos.

Você simplesmente não pode parallelise-lo.

software CAD representa partes como uma árvore, e para tornar a opor você tem que percorrer a árvore. Por esta razão, estações de trabalho CAD usar menos núcleos e mais rápido, ao invés de muitos núcleos.

Obrigado por leitura.

Answer 20

Você poderia naturalmente, no entanto, penso que ambos os 'nomes' é um não-problema. De uma perspectiva de programação funcional pode-se dizer que a parte 'irritantemente seqüencial' é a menor parte mais ou menos independentes de um algoritmo.

Enquanto o 'embaraçosamente paralelo' se não mesmo levando-se em uma abordagem paralela é ruim codificação prática.

Assim eu não vejo um ponto em dadas estas coisas um nome se boas práticas de codificação é sempre a travar-se a sua solução em partes independentes, mesmo se você naquele momento não tirar proveito do paralelismo.