Há algo que DEVE ser feito em uma CPU multi-core?

45

Ao considerar como nosso programa deve ser compatível com vários segmentos, minha equipe ficou intrigada com a possibilidade de algo que absolutamente não pode ser feito em uma CPU de núcleo único. Eu afirmei que o processamento gráfico requer processamento paralelo em massa, mas eles argumentam que coisas como DOOM foram feitas em CPUs de núcleo único sem GPUs.

Há algo que deve ser feito em um processador multi-core?

Suponha que haja tempo infinito para desenvolvimento e execução.

Ben Leggiero
fonte
8
Embora as respostas abaixo pareçam em grande parte "não", historicamente existem sistemas que literalmente não poderiam ter funcionado sem um co-processador que lida com algumas tarefas. Um forte exemplo que eu conheço é o Nintendo DS, que inclui uma CPU ARM9 de 67MHz e uma CPU ARM7 de 33MHz (também usada para compatibilidade traseira ao jogar jogos GBA). Para jogos DS, o ARM7 lida com a reprodução de áudio e comunicação Wi-Fi, porque o ARM9 não pode processar e chamar nada de nota na tela enquanto acompanha o áudio diretamente no chip de som. Portanto, como o @jmite declara "sob quais restrições", a falta de velocidade pode exigir várias CPUs.
Slip D. Thompson
10
No meu trabalho, usamos Xeons multicore e as extensões Linux em tempo real Xenomai para fazer processamento de áudio de baixa latência. Temos um pipeline de processamento de áudio em três estágios, e cada estágio recebe seu próprio núcleo dedicado, que utiliza ~ 70% dos ciclos. Tarefas não em tempo real usam o quarto núcleo e os ciclos restantes nos três primeiros. Isso só seria possível em uma CPU de núcleo único se esse núcleo fosse mais de três vezes mais rápido que um núcleo na atual CPU de quatro núcleos; dado que a CPU atual roda em 2GHz, isso pode ser difícil de alcançar.
precisa saber é o seguinte
19
O software em uma CPU de núcleo único pode emular uma CPU de vários núcleos. A diferença é quase inteiramente velocidade.
user253751
24
Uma coisa que deve ser feita em um sistema com vários núcleos é testar o software multithread. Porque alguns defeitos (quase) nunca acontecem em um sistema de núcleo único. Eu não tenho certeza que se qualifica como uma resposta, embora ...
Nikie
13
@nikie Um sistema de single-core pode emular ordenação memória e caches velhos também - mas eu imagino que seria extremamente ineficiente (como 10 × desaceleração)
Nayuki

Respostas:

47

Se você não se importa com o tempo de execução, tudo o que você pode fazer em uma máquina com vários núcleos, você pode fazer em uma máquina com um único núcleo. Uma máquina com vários núcleos é apenas uma maneira de acelerar alguns tipos de cálculos.

Se você puder resolver um problema no tempo em uma máquina com vários núcleos com núcleos, poderá resolvê-lo com o tempo (ou menos, observe a lei de Amdahl ) em uma máquina com um único núcleo. A máquina de núcleo único pode emular uma máquina com vários núcleos usando divisão de tempo / compartilhamento de tempo .n T nTnTn

DW
fonte
3
Não tenho certeza absoluta de que esteja absolutamente correto. Eu não acho que os erros de consistência de memória sejam possíveis de gerar em um único núcleo (Sim, pode-se emular um sistema multicache em um unicore, mas essa indireção é meio que trapaça). (Talvez o equivalente à implementação de troca reg. Por operações op em um VLIW, explorando || ism garantido?) Suponho que, mesmo em um núcleo de thread único, ainda seria possível extrair entropia da variabilidade de tempo multithread, mas a quantidade de a entropia seria menor por unidade de tempo (o que é realmente apenas uma questão de desempenho, como as outras diferenças).
Paul A. Clayton
6
@ PaulA.Clayton Os erros de consistência da memória geralmente são indesejados e o software bem escrito não deve exibi-los. No entanto, se você realmente quisesse, poderia imitá-los em uma única CPU. (Embora possa ser lenta)
user253751
4
Às vezes, o tempo em um único núcleo será vezes maior do que em uma máquina -core, por exemplo, para pesquisar com reinicializações aleatórias ou se as peças caberem no cache nos múltiplos núcleos, mas não no núcleo único. nnn
András Salamon
11
"A máquina de núcleo único pode emular uma máquina com vários núcleos usando divisão de tempo / compartilhamento de tempo". E, de fato, o fazem desde o início do sistema operacional "moderno".
Lightness Races com Monica
1
@ PaulA.Clayton Acho que você poderia ter problemas de consistência de memória (como um incremento não atômico) se tivesse dois processos diferentes que modificassem a mesma memória compartilhada. Você só precisa de multitarefas preventivas. Obviamente, é por isso que os sistemas operacionais modernos não têm processos que compartilham a mesma memória gravável, a menos que solicitem explicitamente.
Patrick M
58

A questão é: sob quais restrições?

Certamente existem problemas em que, se fizermos a pergunta "podemos resolver esse problema no hardware X dentro de um determinado período de tempo", a resposta será não.

Mas essa não é uma resposta "à prova de futuro": coisas que no passado não podiam ser feitas com rapidez suficiente em um único núcleo provavelmente podem ser agora, e não podemos prever de que hardware futuro será capaz.

Em termos de computabilidade, sabemos que uma máquina de Turing de fita única é capaz de computar todas as mesmas funções que um computador único ou com vários núcleos; portanto, além do tempo de execução, não há problemas que um computador com vários núcleos possa resolver que um single-core não pode.

Em termos de gráficos, literalmente tudo o que está na GPU pode ser feito na CPU ... se você estiver disposto a esperar o suficiente.

jmite
fonte
3
@JanDvorak Na verdade, eu diria que isso não é feito pela GPU;))
TomTom
15
Se o tempo não for uma restrição, você poderá fazer todos os cálculos à mão, caneta e papel.
mathreadler
2
@mathreadler Sim, porque o cérebro é Turing Complete. Algo que se transformou em um longo debate sobre a troca de pilhas da física.
JBentley
4
Na verdade, @JanDvorak, gerando VGA é bastante simples e pode ser feito em software num micro controlador modesto 16 MHz, como se pode observar no projecto: pyroelectro.com/tutorials/arduino_basic_vga
axello
3
@ Matthreadler Essa é realmente uma pergunta mais complicada do que parece à primeira vista. Uma resposta curta pode ser "sim", porque uma máquina especializada pode construir um computador sem precisar de ferramentas completas para isso. Uma resposta mais longa pode ser "não", porque a capacidade de construir uma máquina de turing pode implicar que se tenha uma máquina de turing maior que esteja em um estado de "inicialização" onde constrói o restante da máquina de estado. A resposta completa é ainda mais complicada porque nunca construímos um dispositivo Turing Complete. Desenvolvemos idéias abstratas para máquinas que são ...
Cort Ammon
17

Como outras respostas apontaram, uma única CPU sempre pode emular várias CPUs reduzindo o tempo e desempenhando o papel de cada CPU virtual. Essa emulação certamente calculará as respostas corretas.

No mundo real, o tempo de execução pode ser importante. Pode significar a diferença entre uma taxa de quadros medíocre e uma experiência visual estelar. Ou a diferença entre lucro e perda na negociação.

Uma situação patológica em que um multiprocessador é muito mais rápido que um uniprocessador é onde o processamento é um pipeline de dados, a alternância de contexto é cara e o código da máquina para cada estágio do pipeline mal se encaixa no cache de uma CPU.

Deixe-me ilustrar com alguns números. Suponha que você tenha um pipeline de dados (renderização em 3D etc.) que possua 4 estágios de processamento, cada estágio tenha 256 KiB de código de programa e você tenha convenientemente 4 CPUs com cache de 256 KiB de L2. Se você tentar executar esse processamento em uma única CPU, a alternância entre as 4 tarefas será cara e envolverá falhas graves no cache. Por outro lado, se você executá-lo em um sistema de quatro núcleos, o cálculo pode ser muito suave, as perdas de cache são mínimas e as alternâncias de contexto são inexistentes. (Como uma observação lateral, isso está relacionado à noção de fixar certos aplicativos a determinados núcleos - por exemplo, apenas executar operações do kernel do SO em um núcleo ou manipulação de TCP / IP etc.)

Nayuki
fonte
7

É muito mais difícil desenvolver corridas de dados realmente nefastas com uma única CPU. Quero dizer, com certeza, você pode usar o rasgo entre palavras se interromper uma única CPU, mas pode criar cenários exóticos onde não há uma intercalação única de threads que faça o que você deseja?

Tudo bem, talvez fazer erros insidiosos não conte como um uso válido de avanços em vários códigos. Como se vê, não há muito que o mutli-core possa fazer; esse único núcleo não pode dar tempo. O motivo é simples. Se você tentar evitar essas corridas de dados incorretos, precisará ter pontos de sincronização no seu código. Se você modelar seu código como uma rede de cálculos em que as entradas devem ser completas e sincronizadas antes que você possa calcular e produzir saídas, é fácil ver que uma única CPU pode simplesmente trabalhar ao longo da rede, calculando o próximo bloco de trabalho disponível. .

De fato, se você puder demonstrar que seu algoritmo pode ser resolvido por uma máquina de Turing (que é praticamente todos os algoritmos de que gostamos), pode ser comprovado que o algoritmo pode ser feito não apenas por uma CPU de núcleo único, mas de fato um máquina de estado com um pedaço muito longo de fita para memória!

O detector de corrida CHESS realmente aproveita isso para encontrar casos de corrida. Ele executa tudo individualmente e explora sistematicamente todas as intercalações possíveis entre os threads, tentando encontrar casos em que um teste falha devido a um caso de corrida. O CHESS depende do fato de que você pode executar qualquer aplicativo multithread em um único núcleo.

Os casos em que você precisa de vários núcleos aparecem quando você começa a esticar os limites do hardware. O óbvio é quando você tem restrições de tempo. Alguns problemas com restrições de tempo em tempo real são impossíveis de serem executados em núcleo único, porque eles simplesmente não conseguem acionar o relógio de um único núcleo com rapidez suficiente. Há uma razão pela qual as CPUs subiram para 4Ghz e depois se estabeleceram um pouco, preferindo mais núcleos em velocidades mais baixas.

Uma versão mais exótica dessa restrição de tempo está em sistemas de tempo difícil. Em alguns sistemas em tempo real, o serviço de interrupções é tão exigente que você realmente precisa escolher uma CPU com vários núcleos que permita dividir as interrupções entre os núcleos ou ter limitações de tempo.

Outro limite surge com os barramentos de dados. Considere o Blue Gene / P como um exemplo. JUGENE, um supercomputador Blue Gene / P específico, possui 144 terabytes de memória. Eles simplesmente não fabricam computadores com CPU única que podem acessar toda essa memória.

Cort Ammon
fonte
1
Re, eles simplesmente não fazem computadores com CPU única que podem acessar [tanta quantidade] de memória. "Não" não é o mesmo que "não posso". Você pode projetar e construir um uniprocessador com 144 terabytes ou mais de memória principal. A única razão pela qual as pessoas não sabem disso é por causa dos retornos decrescentes: o valor prático e incremental de adicionar mais memória a um design de processador único atinge um pico em algum momento e depois diminui à medida que o tamanho da memória aumenta, enquanto o custo incremental permanece constante .
Solomon Slow
@jameslarge Essa seria a razão pela qual essa frase veio na parte da minha resposta, discutindo o hardware prático da vida real, e por que ela não apareceu nos primeiros 2/3 da resposta que discutia as capacidades teóricas.
Cort Ammon
"Não" vs. "Não posso" é ilustrado por dois sistemas no meu porão. Se eu pudesse adicionar fisicamente tanta memória em suas configurações de hardware, suas CPUs "poderiam" acessar cada byte. Mas eu não posso, então eles "não podem". Os recursos das CPUs estão além da praticidade.
user2338816
Eu estava pensando em algo como esta resposta. Parece que as condições da corrida seriam impossíveis (ou aconteceriam 100% do tempo) em um ambiente de núcleo único. Quanto a uma aplicação prática, teorizo ​​que um desenvolvedor de software pode projetar alguma forma exclusiva de proteção contra cópia, codificando algum teste de condição de corrida estranho que sempre passa no hardware de destino específico, mas falha no hardware emulado executado por um único núcleo . Nesse caso, a emulação por um sistema multinúcleo provavelmente passaria às vezes, mas de maneira não confiável.
Dan Henderson
6

Se você precisar observar um processo em execução em um único elemento de processamento sem atrapalhar o comportamento em tempo real (ou o mínimo possível), como comparações ou registros de atividades, provavelmente precisará de um recurso de processamento separado.

Yves Daoust
fonte
Bom, exemplo concisa de algo que exigiria emulação precisa se não múltiplos processadores
Ben leggiero
Ei, essa é a sua conta? Mayby você gostaria de mesclar?
Mal
4

As outras respostas aderem à visão limitada do paralelismo como "concorrência distribuída". Isso fornece algumas respostas: em um modelo limpo de computação à la Turing, múltiplos núcleos não oferecem uma vantagem; a única vantagem que você pode obter é eficiência.

os uma coisa várias unidades de processamento (pus) pode fazer que uma única pessoa não pode, no entanto: executar operações em paralelo , que é ao mesmo tempo .

Isso é muito útil se você executar vários programas ao mesmo tempo. É verdade que raramente é necessário mais do que execução simultânea, e a maioria dos usos se resume a maior eficiência. Mas não é essa diferença.

Digamos que você precise processar dados do sensor de dados de várias fontes em tempo real. Seja lá o que isso signifique precisamente em seu aplicativo, um PU pode lidar com tantos fluxos de entrada simultaneamente sem violar seu limite de tempo de resposta. Então, você precisa de várias PUs depois de ter muitos sensores para sua atual geração de PU.

No domínio mais clássico, um exemplo talvez convincente são os algoritmos de portfólio . Digamos que você tenha um problema para o qual possui vários algoritmos (digamos ) com custos ortogonais; casos bons de um são ruins para outros. Porém, você não pode dizer rapidamente qual é o melhor para uma determinada entrada.k

Você pode executar todos os algoritmos em paralelo e abortar assim que terminar. Se você possui pelo menos PUs, obtém o tempo de execução mínimo entre todos os algoritmos do portfólio. Com apenas uma PU, você obteria vezes isso, assumindo um agendador justo, além de toda a sobrecarga.k kkkk

Rafael
fonte
0

de um ponto de vista de CS, "multicore" não é muito diferente em teoria do que "computação distribuída". o conceito básico é de "elementos independentes de computação (que computam em paralelo". portanto, reformular ligeiramente a questão ("multicore" não é exatamente um conceito teórico no CS) leva a algumas outras possibilidades. Como apontado em outras respostas, a programação seqüencial é equivalente à programação paralela de um ponto de vista de CS. Isso remonta à definição do sistema teórico de computação, ou seja, uma máquina de Turing. embora exista alguma analogia aproximada com as TMs multitape ).

mas considerando essa questão de maneira menos abstrata, a computação distribuída é realmente superior ou possivelmente quase necessária para alguns problemas que envolvem tolerância a falhas . nessa área, existe um conceito que se aplica quando / onde os elementos independentes de computação são considerados como tendo algum grau de confiabilidade (essa não é realmente uma suposição universalmente aplicável a todos os contextos). Aqui estão vários casos em que a tolerância a falhas é aprimorada ou requer elementos de computação independentes.

  • considere que cada processador tem uma chance independente de "[x]%" de falhar durante o cálculo. um sistema pode ser concebido pelo qual, através da comunicação, a tolerância geral a falhas do sistema é superior aos componentes individuais. isso foi aplicado há muitas décadas, por exemplo, nos sistemas de ônibus espaciais. mais recentemente, existem protocolos básicos projetados para utilizá-lo, por exemplo, Paxos, que resolvem o chamado problema de consenso . um exemplo mais prático é o Google, que possui muitos algoritmos proprietários para criar essencialmente seus supercomputadores a partir de elementos não confiáveis ​​individualmente, juntamente com algoritmos tolerantes a falhas.

  • O Bitcoin envolve transações distribuídas para calcular o razão e isso não se deve apenas a simples problemas de carga de processamento. o algoritmo é cuidadosamente projetado para impedir nós corrompidos. em resumo, "resolve" / implementa o problema dos generais bizantinos, que não se limita a maximizar o desempenho paralelo, envolve entidades independentes "checando" umas às outras e "algoritmicamente / criptograficamente / com segurança" rejeitando cálculos inválidos, conhecidos como uma espécie de "trapaça" ou " corrupção".

  • uma análise clássica do paralelismo conclui que existem cerca de 7 tipos de padrões de problemas "fundamentais" que se decompõem em falhas de execução paralela específicas. veja O cenário da pesquisa em computação paralela: uma visão de Berkeley

  • há algum elemento de uma questão teórica aberta aqui, com considerações de desempenho abordadas na maioria das outras respostas. a questão de saber se há problemas "inerentemente mais rápidos" em paralelo do que seqüencial também é conhecida aproximadamente como o problema P =? NC, em que NC é considerado a classe de algoritmos "eficientemente paralelizáveis" e P é algoritmos "eficientes [seqüenciais] "

vzn
fonte
1
Eu amo essa resposta! Eu aprendi muito com seus exemplos: D
Ben Leggiero 8/16/16
+1 para tolerância a falhas em ambientes críticos com radiação, -1 por falta de limites e redundância.
Cees Timmerman