O Gargalo de Von Neumann

Meu professor de Computação Paralela perguntou à turma durante uma aula se os alunos sabiam a razão do desenvolvimento da computação paralela. Naquele momento, eu apenas pude apontar a dificuldade de melhorar o desempenho sequencial em razão das limitações físicas na construção de circuitos integrados como tal razão. Estudando o conteúdo da disciplina de Paradigmas de Linguagens de Programação, vi esta passagem que fala do gargalo de Von Neumann:

The speed of the connection between a computer’s memory and its processor usually determines the speed of the computer, because instructions often can be executed faster than they can be moved to the processor for execution. This connection is called the von Neumann bottleneck; it is the primary limiting factor in the speed of von Neumann architecture computers. The von Neumann bottleneck has been one of the primary motivations for the research and development of parallel computers. [1]

Esse trecho aponta uma razão para desenvolver a computação paralela que me era desconhecida. A razão é o gargalo de Von Neumann, que é visto como um problema. Porém, a computação paralela não está totalmente livre desse problema:

…one may be left wondering why anyone would build or use a distributed memory parallel machine. For systems with larger numbers of processors the shared memory itself can become a bottleneck because there is limited bandwidth capability that can be engineered into a single-memory subsystem. This places a practical limit on the number of processors that can be supported in a traditional shared memory machine, on the order of 32 processors with current technology. [2]

Isso evidencia o fato de que a quantidade de computação realizada em um instante é limitada pela velocidade de comunicação entre processador e memória em arquiteturas de Von Neumann no contexto da computação serial e no contexto da computação paralela com memória compartilhada, sendo que nesta o número de processadores que podem trabalhar em conjunto também é limitado por o barramento entre memória e processador agir como um gargalo.

O número de processadores em uma arquitetura paralela pode ser aumentado com o uso de sistemas com memória distribuída, especialmente com sistemas ccNUMA (Acesso à Memória não Uniforme com Coerência de Cache). Esses sistemas podem ocultar a complexidade de um sistema de memória distribuído sob a forma de um sistema lógico de memória compartilhada enquanto mantêm um número muito grande de processadores trabalhando em conjunto. (CHANDRA, 2007)

Pesquisando superficialmente na Web, encontrei uma página do wiki colaborativo da C2 com o seguinte texto:

So whoever said “The obvious solution is parallel processing” — that’s not a random proposal, that is precisely what VonNeumannBottleneck means in the first place. The second most popular architecture, HarvardArchitecture, is non-von to a tiny extent: it separates data from program memory, accesses the two on independent buses, and allows e.g. a data fetch to happen in parallel with an instruction fetch. [3]

A Arquitetura de Harvard propõe que o processador tenha acesso a memórias diferentes – com diferentes endereçamentos. Uma figura exemplifica esse modelo de arquitetura:

Harvard_architecture.svg

Criador: Noelia (Nessa Los)

O que a arquitetura de Harvard faz é paralelizar o acesso aos bits que o processador requer para trabalhar, permitindo a busca simultânea das instruções e dos dados que servirão de base para um cálculo. Do ponto de vista do desempenho, o acesso aos bits nessa arquitetura pode ter latência variável e, se uma operação precisar de bits que estão espalhados por todas as memórias, o desempenho do processador será limitado pela memória mais lenta. Assim, essa arquitetura oferece uma maior vazão de dados para o processador ao custo de sujeitar seu desempenho ao desempenho do elo mais fraco. O aforismo “uma corrente é tão forte quanto seu elo mais fraco” vem à mente.

No wiki da C2, na página de título “VonNeumannBottleneck”, lê-se:

The other obvious solution (which doesn’t require abandoning a VonNeumannArchitecture), which I’m surprised hasn’t been mentioned on this page, is moving memory into the same package as the processor. Either in explicitly-separate address spaces (large memory files, special “processing” memories, etc.), or via caching. [3]

A otimização da banda de memória disponível ao processador na arquitetura de Von Neumann seria possível – segundo o texto – movendo a memória para dentro do processador ou com o uso de cache. O conceito prático de localidade diz que quando o processador busca o conteúdo de uma célula de memória, há uma alta probabilidade não aleatória de que ele acessará o mesmo endereço ou endereços vizinhos em breve. Isso justifica o uso como cache de memória mais veloz – e de maior custo financeiro – que a memória principal do sistema. A abordagem que propõe mover a memória para perto do processador considera que, como bits são sinais elétricos que viajam com velocidade finita, quanto mais os dados estão próximos do processador, mais rapidamente eles podem ser entregues ao processador. (CHANDRA, 2007)

As medidas citadas podem gerar uma melhora no desempenho, no entanto essa melhora é restrita ao caso particular de um programa que não faz acessos totalmente aleatórios à memória e essa melhora é restringida também por questões físicas, uma vez que há um limite no tamanho dos circuitos de memória que podem ser colocados próximos aos processadores e mesmo que quantidades muito grandes de memória fossem colocadas no pacote do processador, teríamos, concomitantemente, um aumento da complexidade do endereçamento que diminuiria o tempo de acesso. (RAUBER; RÜNGER, 2013)

No caso de sistemas paralelos, a adição de cache é muito complicada, pois há o problema adicional de garantir que um processador sempre acesse a versão mais atualizada dos dados. Por isso, é necessário usar um protocolo para manter a coerência de todos os caches. Também há uma complicação adicional de implementar um único grande cache no caso de um sistema de memória compartilhada com um número muito grande de processadores, pois, por limitação física, alguns processadores podem ficar mais distantes que os demais da memória/cache, fazendo com que seus acessos à memória sejam mais lentos e que seus cálculos demorem mais que os dos demais processadores. No caso de esse sistema processar um laço paralelo com barreira, os processadores mais próximos à memória estarão impedidos de proceder para fora do laço até que os processadores que estão mais distantes terminem de computar.

Concluímos que a arquitetura de Von Neumann e os sistemas de memória compartilhada são mais fáceis de implementar que os demais, no entanto, o desempenho de suas implementações tem limitações que são difíceis de evitar e amenizar. Alternativas para esses modelos são a arquitetura de Harvard e os sistemas de memória distribuída (com destaque para os sistemas ccNUMA), que, respectivamente, permitem uma maior agilidade na transferência de dados ao processador e uma maior quantidade de processadores trabalhando simultaneamente ao custo de grande complexidade.


Referências
[1] SEBESTA, R. W. Concepts of Programming Languages. 10 edition ed. Boston: Addison-Wesley, 2012.

[2] CHANDRA, R. et al. Parallel Programming in OpenMP. 1 edition ed. San Francisco, CA: Morgan Kaufmann, 2000.

[3] Von Neumann Bottleneck. C2, http://c2.com/cgi/wiki?VonNeumannBottleneck , 7 jan. 2014.

[4] RAUBER, T.; RÜNGER, G. Parallel Programming: for Multicore and Cluster Systems. 2nd ed. 2013 edition ed. New York: Springer, 2013.


Licenças e Créditos

Imagem destacada publicada por amontei e licenciada sob os termos da Creative Commons Attribution-NonCommercial 2.0 Generic (CC BY-NC 2.0).

CC0 1.0 To the extent possible under law, Anderson N. Nunes has waived all copyright and related or neighboring rights to O Gargalo de Von Neumann.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *