p No jargão da ciência de dados, gráficos são estruturas de nós e linhas de conexão usadas para mapear dezenas de relacionamentos de dados complexos. A análise de gráficos é útil para uma ampla gama de aplicações, como a classificação de páginas da web, analisando redes sociais para insights políticos, ou traçando estruturas de neurônios no cérebro. p Consistindo em bilhões de nós e linhas, Contudo, grandes gráficos podem atingir terabytes de tamanho. Os dados do gráfico são normalmente processados ​​em uma dispendiosa memória dinâmica de acesso aleatório (DRAM) em vários servidores que consomem muita energia.

p Pesquisadores do Laboratório de Ciência da Computação e Inteligência Artificial do MIT (CSAIL) desenvolveram agora um dispositivo que usa armazenamento flash barato - o tipo usado em smartphones - para processar gráficos enormes usando apenas um único computador pessoal.

p O armazenamento em Flash é normalmente muito mais lento do que o DRAM no processamento de dados gráficos. Mas os pesquisadores desenvolveram um dispositivo que consiste em um array de chips flash e um "acelerador de computação, "que ajuda o flash a atingir um desempenho semelhante ao DRAM.

p Ligar o dispositivo é um novo algoritmo que classifica todas as solicitações de acesso para dados gráficos em uma ordem sequencial que o flash pode acessar de forma rápida e fácil. Ele também mescla algumas solicitações para reduzir a sobrecarga - o tempo de computação combinado, memória, largura de banda, e outros recursos de computação - de classificação.

p Os pesquisadores executaram o dispositivo em vários sistemas tradicionais de alto desempenho, processando vários gráficos grandes, incluindo o enorme Web Data Commons Hyperlink Graph, que tem 3,5 bilhões de nós e 128 bilhões de linhas de conexão. Para processar esse gráfico, todos os sistemas tradicionais exigiam um servidor que custava milhares de dólares e continha 128 gigabytes de DRAM. Os pesquisadores obtiveram o mesmo desempenho conectando dois de seus dispositivos - totalizando 1 gigabyte de DRAM e 1 terabyte de flash - em um computador desktop. Além disso, combinando vários dispositivos, eles podiam processar gráficos enormes - até 4 bilhões de nós e 128 bilhões de linhas de conexão - que nenhum outro sistema poderia manipular no servidor de 128 gigabytes.

p "O resultado final é que podemos manter o desempenho com muito menor, menos, e mais frias - como em temperatura e consumo de energia - máquinas, "diz Sang-Woo Jun, um estudante de pós-graduação CSAIL e primeiro autor em um artigo que descreve o dispositivo, que está sendo apresentado no Simpósio Internacional de Arquitetura de Computadores (ISCA).

p O dispositivo pode ser usado para cortar custos e energia associados à análise gráfica, e até mesmo melhorar o desempenho, em uma ampla gama de aplicações. Os pesquisadores, por exemplo, estão atualmente criando um programa que poderia identificar genes que causam câncer. Grandes empresas de tecnologia como o Google também podem aproveitar os dispositivos para reduzir sua pegada de energia, usando muito menos máquinas para executar análises.

p "O processamento de gráficos é uma ideia geral, "diz o co-autor Arvind, o professor Johnson em Engenharia de Ciência da Computação. "O que a classificação da página tem em comum com a detecção de genes? Para nós, é o mesmo problema de computação - apenas gráficos diferentes com significados diferentes. O tipo de aplicativo que alguém desenvolve determinará o impacto que terá na sociedade. "

p Os co-autores do artigo são o estudante de pós-graduação do CSAIL Shuotao Xu, e Andy Wright e Sizhuo Zhang, dois alunos de pós-graduação no CSAIL e no Departamento de Engenharia Elétrica e Ciência da Computação.

p Classificar e reduzir

p Na análise gráfica, um sistema irá basicamente pesquisar e atualizar o valor de um nó com base em suas conexões com outros nós, entre outras métricas. Na classificação da página da web, por exemplo, cada nó representa uma página da web. Se o nó A tiver um valor alto e se conectar ao nó B, então, o valor do nó B também aumentará.

p Os sistemas tradicionais armazenam todos os dados gráficos em DRAM, o que os torna rápidos no processamento de dados, mas também caros e com alto consumo de energia. Alguns sistemas descarregam algum armazenamento de dados para o flash, que é mais barato, mas mais lento e menos eficiente, então eles ainda requerem quantidades substanciais de DRAM.

p O dispositivo dos pesquisadores é executado no que os pesquisadores chamam de algoritmo de "redução de classificação", que resolve um grande problema com o uso de flash como fonte primária de armazenamento:resíduos.

p Os sistemas de análise gráfica requerem acesso a nós que podem estar muito distantes uns dos outros em um enorme, estrutura de gráfico esparsa. Os sistemas geralmente solicitam acesso direto a, dizer, 4 a 8 bytes de dados para atualizar o valor de um nó. A DRAM fornece esse acesso direto muito rapidamente. Clarão, Contudo, acessa apenas dados em blocos de 4 a 8 kilobytes, mas ainda atualiza apenas alguns bytes. Repetir esse acesso para cada solicitação enquanto pula pelo gráfico desperdiça largura de banda. "Se você precisar acessar todos os 8 kilobytes, e use apenas 8 bytes e jogue o resto, você acaba jogando 1, 000 vezes o desempenho de distância, "Jun diz.

p Em vez disso, o algoritmo de redução de classificação pega todas as solicitações de acesso direto e as classifica em ordem sequencial por identificadores, que mostram o destino da solicitação, como agrupar todas as atualizações para o nó A, tudo para o nó B, e assim por diante. O Flash pode acessar blocos do tamanho de kilobytes de milhares de solicitações de uma vez, tornando-o muito mais eficiente.

p Para economizar ainda mais potência de computação e largura de banda, o algoritmo mescla simultaneamente os dados nos menores agrupamentos possíveis. Sempre que o algoritmo observa identificadores correspondentes, ele os soma em um único pacote de dados - como A1 e A2 tornando-se A3. Continua fazendo isso, criando pacotes cada vez menores de dados com identificadores correspondentes, até produzir o menor pacote possível para classificar. Isso reduz drasticamente a quantidade de solicitações duplicadas de acesso.

p Usando o algoritmo de redução de classificação em dois gráficos grandes, os pesquisadores reduziram o total de dados que precisavam ser atualizados em flash em cerca de 90 por cento.

p Descarregando computação

p O algoritmo de redução de classificação é intensivo em computação para um computador host, Contudo, então os pesquisadores implementaram um acelerador personalizado no dispositivo. O acelerador atua como um ponto intermediário entre o host e os chips flash, executando todos os cálculos para o algoritmo. Isso descarrega tanta energia para o acelerador que o host pode ser um PC ou laptop de baixa potência que gerencia dados classificados e executa outras tarefas menores.

p "Os aceleradores devem ajudar a computação do host, mas chegamos tão longe [com os cálculos] que o host se torna sem importância, "Arvind diz.

p "O trabalho do MIT mostra uma nova maneira de realizar análises em gráficos muito grandes:seu trabalho explora a memória flash para armazenar os gráficos e explora 'matrizes de portas programáveis ​​em campo' [circuitos integrados personalizados] de uma maneira engenhosa para realizar a análise e a processamento de dados necessário para usar a memória flash de forma eficaz, "diz Keshav Pingali, professor de ciência da computação na Universidade do Texas em Austin. "A longo prazo, isso pode levar a sistemas que podem processar grandes quantidades de dados de forma eficiente em laptops ou desktops, que vai revolucionar a forma como fazemos o processamento de big data. "

p Como o host pode ter pouca energia, Jun diz, uma meta de longo prazo é criar uma plataforma de propósito geral e biblioteca de software para os consumidores desenvolverem seus próprios algoritmos para aplicativos além da análise de gráfico. "Você pode conectar esta plataforma em um laptop, baixe [o software], e escrever programas simples para obter desempenho de classe de servidor em seu laptop, " ele diz. p Esta história foi republicada por cortesia do MIT News (web.mit.edu/newsoffice/), um site popular que cobre notícias sobre pesquisas do MIT, inovação e ensino.