Sistema integrado de processamento baseado em redes em chip que não faz uso de processadores do tipo von neumann

  • Número do pedido da patente:
  • PI 0925284-3 A2
  • Data do depósito:
  • 03/04/2009
  • Data da publicação:
  • 06/01/2015
Inventores:
  • Classificação:
  • G06F 15/80
    Computadores digitais em geral; Equipamento de processamento de dados em geral; / Arquiteturas de computadores com programas armazenados de finalidades gerais; / que compreendem um conjunto de unidades de processamento com controle comum, p. ex. v?rios processadores de dados com instru??o ?nica;
    ;

SISTEMA INTEGRADO DE PROCESSAMENTO BASEADO EM REDES EM CHIP QUE NÃO FAZ USO DE PROCESSADORES DO TIPO VON NEUMANN A presente invenção refere-se a um sistema integrado baseado em rede em chip capaz de executar aplicações (programas ), descritas em um formato de pacote específico contendo instruções e operandos transmitidos e executados pelo elementos de processamento e roteamento da rede, chamados de Routing and Processing Unit ou RPU. A execução das instruções das aplicações é realizada pelas RPUs, no percurso por onde tais pacotes são encaminhados, sem a necessidade do processamento do tipo Von Neumann. Os pacotes , armazenados na memória , são injetados no sistema através de Memory Access Unit ou MAU ligados aos RPUs dos cantos da rede , que também têm a função de executar instruções de sincronização e acesso a memória. A memória é fisicamente distribuída em quatro módulos (gerenciados pelas MAUs) formando um espaço de endereçamento único. Os pacotes são encaminhados utilizando um algoritmo de roteamento próprio, denominado spiral complement, que garante a execução de todas as instruções das aplicações

Página de 5

Documento

“SISTEMA INTEGRADO DE PROCESSAMENTO BASEADO EM REDES EM CHIP QUE NÃO FAZ USO DE PROCESSADORES DO TIPO VON NEUMANN”

t

A presente invenção refere-se a um sistema de processamento basQldo em redes em chip, no qual as aplicações são descritas em um formato de pacote contendo instruções e dados, que são executadas nos elementos de roteamento, por onde o pacote trafega, ou nos núcleos de acesso a memória, e, portanto não faz uso de processadores do tipo Von Neumann. Para tanto esse sistema utiliza um algoritmo de roteamento próprio que permite re-rotear um pacote quando o mesmo atinge seu destino e ainda possui instruções a serem executadas.

Desde que o computador IAS (Institute for Advanced Studies) foi proposto por Von Neumann, estruturalmente as arquitetura de computadores subsequentes têm sofrido poucas modificações, e por isso são comumente chamadas de processadores do tipo Von Neumann. Esse modelo conceituai de arquitetura pode ser simplificado por uma Unidade Central de Processamento - CPU (1), memória (5) e dispositivos de entrada e saída (6), como ilustra a Figura 1. Na memória (5) são armazenados os dados e os programas (em forma de instruções), os quais são buscados quando solicitados pela unidade de controle (3) da CPU (1). A CPU (1) também é formada por uma unidade lógica e aritmética ou ULA (2) e registradores (4). A ULA(2) realiza as operações lógica ou aritméticas de acordo com instrução decodificada pela unidade de controle (3) que também controla quando e que informações são armazenadas nos registradores (4). Da mesma forma, a unidade de controle (3) define o momento de ler ou escrever nos dispositivos de entrada e saída (6), que são responsáveis pela comunicação do processador com o meio externo. Assim, o trabalho do processador pode ser resumido como a busca, descodificáção e execução de cada instrução que forma o programa, como ilustra a Figura 2,

Do IAS até os dias atuais, a tecnologia na fabricação de chips passou pelo uso de válvulas até os transistores. Do mesmo modo, as técnicas empregadas ao longo dos anos permitiram construir transistores cada vez menores, possibilitando integração de um número muito maior desses elementos em um mesmo chip, chegando atualmente aos bilhões. Consequentemente, processadores cada vez mais complexos e com maior desempenho foram surgindo juntamente com a tecnologia empregada e a metodologia de reuso.

Seguindo esse raciocínio surgiram sistemas completos dentro de um chip, os chamados SoCs (SoC - System-on-Chip). Os SoCs podem ser formadas por dezenas a centenas de componentes independentes, os quais podem ser elementos de

t

processamento (como processadores de uso geral), módulos de memória ou 9'dtro núcleo de processamento útil para 0 sistema de computação, simplesmente chamados de núcleos. Muitas vezes, SoCs formados por vários processadores são também chamados de multiprocessadores em chip ou multiprocessors SoC (MP-SoC).

Com tantos elementos dentro de um chip, é necessário um mecanismo de comunicação entre os componentes. O mecanismo tradicional é chamado de barramento (7), que é um conjunto de linhas de transmissão compartilhado pelos núcleos (8) que estão ligados a ele, ilustrados na Figura 3. Nesse modelo, apenas um núcleo pode transmitir em um dado instante, controlado possivelmente por um árbitro (9) ou uma lógica compartilhada pelos núcleos. Já foram construídos MP-SoCs usando barramentos como US 1990/4905145, mas a medida que novos núcleos são incluídos, é possível que também seja aumentada a espera de cada núcleo para transmitir algum dado ou diminuída a largura de banda oferecida para cada um. Além disso, 0 aumento do número de núcleos interligados por barramento aumenta a energia consumida e o tempo de propagação dos sinais nos fios, devido ao aumento da carga capacitiva desses canais,

Para minimizar 0 problema da baixa escalabilidade dos barramentos, foi proposto hierarquias de barramentos, Figura 4. Essa solução propõe barramentos mais curtos, possivelmente com diferentes velocidades interligados através de pontes (10). Mesmo assim, esta solução ainda não apresenta a escalabilidade desejada. Outra desvantagem da hierarquia de barramentos é a impossibilidade de reuso, uma vez que é sempre uma solução ad hoc para um sistema. Uma variação desse modelo pode ser encontrada em US 2007/0079046. Desse modo, as redes de interconexão em chip ou NoC (.Network-on-Chip), Figura 5, emergiram como a solução para 0 problema de baixa escalabilidade e reuso dos mecanismos de interconexão nos projetos de SoC ou Mp-SoC (.Multiprocessor SoC).

As NoCs são baseadas nos modelos de rede de computadores, com a diferença de estarem dentro do chip e, consequentemente, estarem restritas às características próprias desse ambiente. Elas podem ser definidas como um conjunto de roteadores (11) e canais ponto-a-ponto que interconectam os núcleos do sistema (12). A arquitetura de comunicação em uma NoC, geralmente, é baseada em canais bidirecionais ou enlaces (12) chaveados que interligam os núcleos. Esses enlaces permitem comunicações simultâneas entre diferentes núcleos ou entre os mesmo núcleos nos dois sentidos da comunicação. Além disso, as NoCs também podem fazer

f

uso de canais virtuais, que é um o compartilhamento do canal físico. Canais virtuai^ áão implementados a partir de múltiplos buffers de entrada e saída, onde vários pacotes são transmitidos entre dois roteadores utilizando canais virtuais diferentes. Nesse processo, o canal físico é alocado de forma alternada (multiplexação no tempo) para a transmissão das palavras de cada pacote. No roteador receptor o processo inverso (demultiplexação) permite recebê-los,armazenando-os em buffers diferentes mantendo sua integridade.

Em uma NoC o modelo de comunicação é geralmente baseado na troca de mensagens entre os núcleos do sistema. Essas mensagens são encapsuladas junto com informações adicionais (como o cabeçalho) que são utilizadas pelos roteadores para encaminhá-las da origem até o destino. O conjunto: mensagem (também chamada de carga útil), cabeçalho, e eventualmente um finalizador da mensagem, é comumente chamado de pacote.

Um pacote é normalmente formado por um conjunto de palavras de determinada largura, onde uma ou mais palavras iniciais fonnam o cabeçalho e as palavras seguintes, a mensagem propriamente dita. O cabeçalho da mensagem contém informações que permitem a um roteador encaminhai1 o pacote para o próximo roteador a caminho do destino, e este encaminha a um outro, e assim segue até o roteador apto a entregar o pacote para o núcleo destino. No cabeçalho também pode haver outras informações, como comprimento do pacote e informações específicas para o núcleo que receberá a mensagem contida no pacote. Existem diversos modelos de NoC que se diferenciam nas seguintes características: topologia, roteamento, chaveamento, controle de fluxo, arbitragem e armazenamento.    '

Nos sistemas em chip baseados em NoC, os dados e instruções das aplicações circulam sob a forma de pacotes. No trajeto dos pacotes, da origem ao destino, os roteadores interessam-se apenas pelo cabeçalho do pacote sem que nenhum processamento útil, do ponto de vista da execução da aplicação, seja realizado, como em US 2006/6988170 e US 2009/0109996. Esse processo de transmissão funciona como um pipeline, que poderia ser aproveitado para a execução das instruções e dados da aplicação. Mesmo utilizando meios de comunicação diferentes dos tradicionais, como comunicação ótica empregada na patente US 2006/0036831, ainda assim os MP-SoC utilizam processadores do tipo Von Neumann que podem funcionar em paralelo, mas de forma independente dos demais, deixando o mecanismo de comunicação com o potencial pipeline intrínseco destinado unicamente para transmissão dos pacotes entre os núcleos.

Os Computadores Baseados em Fila (Queue-based cornputers) ou Máquinas em Fila (Queue machines) propõem um modelo de computação que se aproxima dessa ideia, entretanto tais máquinas são apenas processadores, e não utilizam NoCs. Elas são fundamentadas no uso de referência implícita para uma fila de operandos na execução das instruções, de modo análogo às stcick machine. Algumas pesquisas apontam que a partir das Máquinas em Fila, é possível construir eficientes máquinas superescalares ou máquinas de fluxos de dados (dataflow machine). Também podem ser uma nova alternativa para arquiteturas embarcadas devido seus compactos conjuntos de instrução, que promovem códigos densos, alta capacidade de paralelismo em nível de instrução e hardware simples, que reduz a área em chip e o consumo de energia.

Arquiteturas de fluxo de dados (.Dataflow Architecture) também são bem empregadas para processamento de alto desempenho. Em US 2007/0266223 e US 2009/7533244 é proposto uma arquitetura de fluxo de dados onde parte da execução das aplicações é realizada em NoC. A arquitetura é formada por um processador e duas redes em chip com topologia em malha (uma rede de dados e uma rede de instruções). Entretanto, a arquitetura não utiliza instruções de desvio (branch) como os processadores do tipo Von Neumann, ao invés disso são usadas instruções específicas de branch e de união (merge) não sendo necessária a utilização da técnica de predição. O processador é responsável pela busca de instruções e operandos e pela execução das instruções fora de laços de repetição. Instruções dentro de laços de repetição devem ser executadas nas NoCs, nesse caso o processador configura os elementos de processamento da rede instruções de acordo com o grafo de fluxo de dados da aplicação que deve ser gerado pelo compilador. Após a configuração da rede de instruções, os dados são distribuídos para a rede de dados através de um barramento localizado na borda superior dessa rede. Essa arquitetura tem escalabilidade comprometida pelo barramento, os grafos de fluxo de dados que determinam a configuração dos elementos de processamento têm tamanho limitado pelas dimensões da NoC e o processamento feitos pelas NoCs é dependente da busca e configuração das instruções pelo processador. Além disso, o desempenho da arquitetura está relacionado com a forma que as aplicações são programadas, uma vez que a arquitetura explora o paralelismo de instruções dentro de laços de repetição.

Outra proposta que faz uso de redes em chip para o processamentq' é o chip iWatp. Esse chip é resultado do esforço entre a Universidade Camegie Mellon e a Intel, que tinha o objetivo de desenvolver um poderoso processador single-chip VLSI configurável para diversos sistemas de computação paralela com memória distribuída. iWarp implementa uma variedade de topologia de processadores interconectados. A comunicação pode ser feita através de dois modelos: passagem de mensagem ou sistólica. No modelo de passagem de mensagem os dados são transmitido através de mensagens onde há um endereço remoto para o receptor da mensagem. No modelo sistólico o iWarp usa um escalonamento estático para assegurar o sincronismo da computação entre os processadores. Entretanto é necessário uma pré-configuração de acordo com as características da aplicação a ser executada.

Breve descrição da invenção

A presente invenção propõe um modelo arquitetural de processador, diferente do tradicional modelo de Von Neumann, e permite o processamento paralelo e distribuído dos programas, implementados em forma de pacotes, em diversas unidades de processamento e roteamento. A invenção possibilita comunicação (transmissão) paralela de pacotes através dos diversos canais ponto-a-ponto entre os elementos de processamento e roteamento e os núcleos de acesso a memória. Permite o armazenamento temporário de pacotes ou partes de pacotes antes da transmissão, que se dá como em um pipeline nos elementos de processamento e roteamento que estão entre a origem e o destino dos pacotes, além de possibilitar que pacotes sejam roteados novamente sempre que chegam aos seus destinos, mas ainda carreguem instruções a serem executadas. Essa invenção é capaz de manter um fluxo de pacotes sem deadlock, livelock e starvation, problemas comumente atrelados a sistemas baseados em NoC. E, sobretudo, oferece recursos e lógica para a execução das instruções que implementam aplicações/programas nos elementos de processamento e roteamento, bem como nos núcleos de acesso a memória sem a necessidade de processadores do tipo Von Neumann.

Breve descrição das figuras

A Figura 1 apresenta um modelo simplificado de um computador do tipo Von Neumann, formado por CPU, memória, dispositivo de entrada e saída, todos ligados por um barramento.

A Figura 2 ilustra de maneira simplificada o ciclo de execução das instruções em processadores do tipo Von Neumann,

A Figura 3 representa um sistema formado por vários núcleos que utilizam um barramento como mecanismo de comunicação.

A Figura 4 ilustra um sistema formado por vários núcleos que utilizam uma hierarquia de barramento como mecanismo de comunicação, onde barramentos de velocidades diferentes se comunicam através de pontes.

A Figura 5 representa um sistema formado por vários núcleos que utilizam uma rede em chip como mecanismo de comunicação.

A Figura 6 ilustra uma instância da invenção, formada por uma rede 4x4, com 16 RPUs e 4 MAUs e 4 módulos de memória.

A Figura 7 apresenta o formato dos pacotes regulares utilizados para descrever aplicações/programas da invenção.

A Figura 8 ilustra o método de execução das instruções e inserção dos resultados no mesmo pacote.

A Figura 9 ilustra um simples exemplo e sua dependência de dados.

A Figura 10 apresenta o pacote regular da invenção correspondente ao exemplo anterior.

A Figura 11 ilustra o caminho da primeira espiral que um pacote segue utilizando o algoritmo spiral complement.

A Figura 12 ilustra o caminho da segunda espiral que um pacote segue utilizando o algoritmo spiral complement.

A Figura 13 ilustra o caminho da terceira espiral que um pacote segue utilizando o algoritmo spiral complement.

A Figura 14 ilustra o caminho da quarta espiral que um pacote segue utilizando o algoritmo spiral complement.

A Figura 15 representa a arquitetura interna da RPU.

A Figura 16 apresenta o fluxograma do funcionamento da RPU.

A Figura 17 representa a arquitetura interna da MAU.

A Figura 18 apresenta o formato dos pacotes de controle utilizados para descrever aplicações/programas da invenção.

Descrição detalhada da invenção

A invenção ilustrada através da Figura 6, é formado por uma rede de elementos de processamento e roteamento (13) ou RPU (Routing cmd Processing Unit), ligando as unidades de acesso a memória (14) ou MAU (Memory Access Unit) nos cantos da rede juntamente com os módulos de memória (15) também nos cantos. Essa rede possui topologia em grelha 2D de dimensão quadrada, ou seja, o número de linhas igual ao número de colunas; utiliza, no mínimo, dois canais virtuais; roteamento baseado no padrão XY; chaveamento que combina VCT e wormhole\ controle de fluxo baseado em crédito; arbitragem distribuída; armazenamento na entrada em buffers do tipo FIFO (First In First Out)\ e enlaces de comunicação entre as RPUs e MAUs com 36 bits de largura bits full-duplex. Essas características são comuns em redes em chip, entretanto algumas delas sofreram alterações, em relação ao que é tradicionalmente usado, de acordo com as particularidades do sistema. A Figura 6 ilustra uma instância da invenção formada por uma rede 4x4, com 16 RPUs (13) em forma de grelha 2D e as 4 MAUs (14) nos cantos da rede, cada uma ligada a um módulo de memória (15). Cada um dos componentes (RPU e MAU) é endereçável através da sua posição no plano cartesiano.