![Fechar [x]](http://dw1.s81c.com/i/c.gif){kind=small}
Este artigo explicará a implementação paralela do algoritmo AES discutida na Parte 1 desta série usando a estrutura CUDA. O primeiro foco é na implementação de todas as transformações AES e suas transformações inversas correspondentes em CUDA. Em seguida, veja os gargalos na implementação básica e aplique otimizações específicas ao GPU para mitigar seu efeito. No final do artigo, revise as referências que significam a aceleração atingida usando GPUs ativados para CUDA em CPUs padrão.
Antes de examinar como o AES é implementado na CUDA, vamos começar com uma visão geral da criptografia em GPUs.
O uso de hardware gráfico de uso geral para acelerar soluções criptográficas tem um longo histórico. Gershon Kedem e Yuriko Ishihara publicaram o primeiro artigo abordando a criptografia em hardware gráfico, em agosto de 1999 (consulte Recursos). Os autores relataram o fracionamento bem-sucedido de uma cifra de senha do UNIX® usando o mecanismo de gráficos PixelFlow executando a 100 MHz.
No entanto, placas gráficas iniciais de mercadoria não eram muito adequadas para aplicativos criptográficos devido à falta de um ambiente de programação flexível, além de deficiências de hardware, como suporte a número inteiro ausente. Isso tem mudado nos últimos anos com as placas gráficas mais recentes de fabricantes como NVIDIA, que oferecem mais flexibilidade para aplicativos de cálculo de uso geral. Essa concepção de CUDA e o padrão de programação paralelo aberto, OpenCLTM, tornaram os GPUs plataformas ainda mais atraentes para aplicativos de cálculo paralelo. Diversos artigos recentes lidaram especificamente com a implementação do AES no GPU da NVIDIA usando CUDA (consulte Recursos). Em todos esses artigos, o algoritmo de criptografia principal é implementado no GPU, mantendo tarefas como expansão principal na CPU, o que simplifica a implementação. No entanto, também investigamos o planejamento principal do GPU usando memória compartilhada disponível no hardware mais recente, sem sobrecarga significante de desempenho.
A implementação de CUDA do AES
Agora vamos discutir a implementação e a otimização paralelas do AES usando a estrutura CUDA. Comece com uma implementação básica de transformações AES e o esquema de indexação necessário seguido por uma discussão sobre os fatores de limitação do desempenho. Em seguida, consulte as estratégias de otimização possíveis para mitigar esses gargalos e desenvolver um kernel de criptografia eficiente que aproveita totalmente a capacidade de cálculo paralelo de GPUs.
Para a implementação do AES, considere o caso mais simples de um encadeamento CUDA simples operando em um bloco de estado de 128 bits. A primeira etapa é alocar memória no dispositivo GPU para entrada, saída, chave expandida e tabelas do AES usando a chamada de API cudaMalloc . Esses
buffers são criados na memória global ou no D-RAM do GPU. Os dados de entrada, a chave expandida e as tabelas do AES são, então, copiadas do host para o dispositivo usando a chamada de API cudaMemcpy .
Agora, é possível ativar o kernel do AES e analisar as etapas executadas pelo seu encadeamento CUDA para o processo de criptografia e de decriptografia.
No início do Encaminhamento ou da Cifra Inversa, a matriz de entrada é copiada para a matriz de estado de acordo com a seguinte convenção:
S [ r , c ] = Em [ r + 4c ] para 0 <= r < 4; e 0 <= c Nb, em que Nb = 4 para o caso de exemplo. A Figura 1 descreve este padrão de acesso importante da coluna. (Veja uma versão de texto do diagrama na Figura 1.)
Figura 1. Copiando a matriz de entrada para a matriz de
estado 
A generalização desse esquema de indexação para acomodar mais encadeamentos requer algum mecanismo de identificação de qual encadeamento está sendo executado. Uma nova variável chamada idx é introduzida, o que requer o tempo de execução da CUDA para um ID Global de cada encadeamento. O deslocamento líquido para cada encadeamento é
16*idx, pois cada encadeamento manipula 16 elementos (bytes) da matriz de entrada. O mesmo é verdadeiro na gravação dos dados na matriz de saída após a conclusão do processo de criptografia ou decriptografia.
Todas as transformações AES são implementadas como funções do dispositivo para otimizar o uso do recurso e melhorar a capacidade de leitura do código. Dois blocos de tamanho de estado são criados nos arquivos de registro, pois nem todas as transformações AES podem ser executadas no local. Vamos explicar como as transformações são implementadas na ordem em que são executadas durante a criptografia dos dados de entrada.
-
AddRoundKeyEsta transformação é aplicada combinando cada byte do estado com um byte correspondente da matriz de chave expandida, usando uma operação XOR bit a bit. A chave expandida está disponível no GPU em um buffer de Memória Global. A transformação é aplicada durante cada arredondamento usando uma parte diferente da chave expandida, dependendo do número do arredondamento. A
transformação AddRoundKeyé aplicada de acordo com a equação na Figura 2.
Figura 2.A transformação AddRoundKeyé aplicada de acordo com esta equação
Cada encadeamento requer 16 acessos de memória global de locais aleatórios, resultando em transferências de memória não unida. A memória global é a memória com menor largura da banda no GPU e não é sustentada por um cache. Isso introduz uma longa latência por acesso e bloqueia com eficácia todo o agrupamento contra execução até que todas as solicitações de memória sejam concluídas.
-
SubBytesEsta transformação substitui cada byte da matriz de estado por um elemento do S-Box do AES localizado em um índice igual ao valor do byte em si. Por exemplo, se S0,0 = {64}, então o valor de substituição do S-Box seria determinado pela intersecção da linha com o índice
6e da coluna com o índice4. O S-Box é uma tabela fixa que reside na Memória Global do GPU. Aqui, a situação é semelhante à transformaçãoAddRoundKey. Até aqui, os acessos da Memória Global são o gargalo de desempenho em sua implementação básica. -
TransformaçãoEm uma transformação
ShiftRows, cada byte da segunda, terceira e quarta linhas é deslocado para a esquerda por um deslocamento de um, dois e três bytes, respectivamente. A transformação de linhas de deslocamento usan_statee as matrizes deestado, pois não é uma transformação no local, como naFigura 3.
Figura 3. Aplicando uma transformaçãoShiftRows
A transformação
ShiftRowsnão inclui acessos de memória global. Tanto a matriz de estado quanto a matriz n_state residem nos registros e, portanto, podem ser acessadas na largura da banda mais alta disponível, sem problemas de desempenho.O arredondamento inicial se aplica apenas à transformação
AddRoundKey. Os arredondamentos centrais começam com a transformação SubBytes e se aplicam, respectivamente, aShiftRows,MixColumnseAddRoundKeypara o número específico de arredondamentos calculado pelo comprimento da chave. O arredondamento final executa a transformaçãoSubByteseShiftRowsseguida porAddRoundKey. Os dados criptografados são, então, copiados de volta do estado para o buffer de saída global, conforme descrito a seguir.
Copiar estado para o buffer de saída
No final do Encaminhamento ou da Cifra Inversa, a matriz de
estado é copiada de volta para a matriz de saída na memória global, conforme a Figura 4. A convenção seguida para esse padrão pode ser definida como
De [ r + 4c ] = S [ r , c ] para 0 <= r < 4; e 0 <= c <Nb. (Veja uma versão de texto do diagrama na Figura 4.)
Figura 4. Copiando a matriz de estado para a matriz de saída
Nesta seção, você verá as transformações AES inversas e a ordem em que são aplicadas para o processo de decriptografia. A Cifra Inversa incorpora pequenas mudanças nas transformações, na ordem de execução e nas Tabelas do AES necessárias. A Figura 5 descreve a ordem na qual as transformações são aplicadas para o processo de decriptografia.
Figura 5. Gráfico do fluxo inverso do AES
A transformação InvSubBytes , que é o inverso da transformação SubBytes , requer uma tabela do S-box inversa, em vez da tabela do S-box para a substituição de byte. A lógica de substituição permanece igual à da transformação
SubBytes .
A transformação InvShiftRows desloca cada byte da segunda, terceira e quarta linhas por um, dois e três bytes à direita, respectivamente, em vez de comparado com o deslocamento à esquerda na transformação
ShiftRows . A Figura 6 descreve como a transformação InvShiftRows
é aplicada.
Figura 6. Transformação
InvShiftRows 
As outras duas transformações, MixColumns e AddRoundKey, permanecem intactas.
Otimizando o AES para a arquitetura CUDA
Na implementação básica discutida até aqui, você usou a Memória global (D-RAM) disponível no GPU e a Memória de registro disponível para cada encadeamento. Lembre-se: a Memória global possui a menor largura da banda da memória comparado a outros espaços e memória disponíveis no GPU, como a Memória constante e compartilhada. Seu desempenho de kernel é limitado pela largura da banda da memória global em uma extremidade. A principal desvantagem da baixa largura de banda da memória é o acesso de longa latência. Uma otimização rápida é reduzir o número de acessos à memória global necessários em cada transformação. O segundo fator que degrada o desempenho de kernel é um baixo nível de ocupação do dispositivo, resultante do uso excessivo do registro por encadeamento. No recurso de cálculo 2.0, o máximo de registros permitidos de hardware por Multiprocessador Simétrico (SM) é limitado a 32768. O uso mais alto de registros reduz o número de blocos de encadeamento em andamento em cada SM e resulta na subutilização dos recursos de cálculo. Para atingir o nível máximo de ocupação do dispositivo, é necessário colocar o uso de registro por encadeamento dentro dos limites, permitindo, assim, que mais blocos de encadeamento sejam processados por SM. Para isso, transfira as matrizes de estado e n_state para a memória compartilhada.
Reduzindo o acesso à memória global
O primeiro fator de degradação do desempenho nessa implementação do AES é o acesso frequente à memória global. Os dados sendo acessados da memória global incluem as tabelas do AES fixas e a chave expandida. Para acesso em cache mais rápido, mova esses dados somente leitura para a memória constante de GPUs.
A memória constante é uma memória de leitura de alta largura de banda disponível nos GPUs. Esse é um espaço de memória ideal para armazenar dados constantes para acesso somente leitura, pois fica visível a todos os encadeamentos de todos os blocos de encadeamento em um kernel. O processador do host é responsável por alocar e inicializar os objetos da memória que residem no espaço de memória constante. A memória constante é suportada por cache, portanto, leituras sucessivas da memória constante não sofrem uma penalidade de latência de memória, assim como acontece com as leituras da memória global. Quando os dados são gravados na memória constante, todos os encadeamentos podem acessar esses dados para operações de leitura com latência mínima. O tamanho do cache constante é limitado a 64 KB no hardware atual. No AES, há quatro tabelas constantes que são lidas somente dentro do kernel. São elas: logt, ilogt, sbox e isbox. Cada tabela tem 256 bytes de tamanho, totalizando 1 KB para 4 tabelas, portanto, é possível colocar todas as tabelas em cache constante. Outros dados somente leitura para seu kernel são a chave expandida, que consome até 240 mais bytes do cache constante com facilidade.
O código do kernel não requer nenhuma modificação, pois a memória constante é alocada e inicializada pelo processador de host. A movimentação das tabelas do AES e da chave expandida para a memória constante resulta em um aumento significativo do desempenho, pois reduz substancialmente o número de acessos à Memória global por encadeamento. A memória global agora é acessada somente para copiar dados do buffer de entrada para o estado e de volta para o buffer de saída após a conclusão de todas as transformações.
Melhorando a ocupação do dispositivo e o kernel do AES usando a memória compartilhada
A segunda etapa na otimização do AES é melhorar a ocupação do dispositivo, que é atualmente limitada por um uso de registro excessivo por encadeamento. Cada encadeamento mantém duas matrizes de tamanho de estado (16 bytes) na memória de registro para calcular com eficiência as transformações AES, sem retornar para a memória global. Para salvar a memória de registro sem incorrer em sobrecargas significativas, transfira essas matrizes para um espaço de memória apropriado que oferece desempenho comparável a registros. A memória compartilhada existe para salvar o seu dia.
A memória compartilhada é uma memória de alta largura de banda em GPUs usados para compartilhamento de dados entre encadeamentos no mesmo bloco de encadeamento. GPUs da NVIDIA com recurso de cálculo 2.x têm no máximo 48 KB de memória compartilhada por Multiprocessador Simétrico(SM). A memória compartilhada oferece largura da banda muito alta; mais ou menos uma ordem de magnitude maior que a memória global. Outra vantagem da memória compartilhada é que ela não requer união; depois de carregados para a memória local, os dados podem ser acessados em qualquer padrão sem degradação do desempenho, o que os tornam um substituto ideal da memória de registro.
Coloque os buffers de estado e n_state na memória compartilhada, não nos registros. Nem todos os encadeamentos em um bloco de encadeamento compartilham os buffers de estado e n_state
. Cada encadeamento carregará 16 elementos do buffer de entrada global para o buffer de estado na memória compartilhada em um deslocamento definido. Dois buffers na memória compartilhada ainda são necessários, pois nem todas as transformações AES estão em vigor. Portanto, isso não é um aviso, pois há 48 KB de memória local por SM à sua disposição e cada bloco de encadeamento usa no máximo 8 KB no maior grupo de trabalho de 256, permitindo, assim, que seis blocos de encadeamento sejam processados por SM.
O uso da memória compartilhada requer alguma modificação no esquema de indexação. Agora é necessário controlar o ID local de cada encadeamento, pois o buffer de estado local agora está sendo preenchido cooperativamente por todos os encadeamentos em um bloco de encadeamento. Uma nova variável chamada tid é introduzida e consulta o ID local de cada encadeamento.
Cada encadeamento gravará 16 elementos na matriz de
estado com um deslocamento de
16*tid. O mesmo acontece para o esquema de indexação da matriz de saída. O uso da memória compartilhada para buffers de estado reduz o uso de arquivos de registro por encadeamento e melhora a ocupação do dispositivo. Isso permite que mais agrupamentos sejam executados simultaneamente em cada SM, melhorando o desempenho geral do kernel.
GPUs são processadores Single Instruction Multiple Data (SIMD). Quanto melhor seu cálculo corresponder ao modelo de SIMD, maior será o rendimento que pode ser atingido a partir de um GPU. Na implementação do AES, cada encadeamento está lidando com um bloco de estado (16 bytes) independentemente. Portanto, todas as transformações AES usam um loop for para operar em todos os 16 bytes do estado, como nos códigos de amostra para várias etapas. A implementação do GPU pode aproveitar o desenrolamento de loops, pois ela remove toda a sobrecarga associada a cálculos de índice no tempo de execução.
É possível desenrolar manualmente cada loop ou simplesmente usar a diretiva
#pragma unroll antes de um loop e o compilador fará o mesmo para você. O desenrolamento de loops aumenta o uso do Registro por encadeamento, mas você ainda está dentro do tamanho permitido de 32768 registros por bloco. O desempenho é melhor com loops desenrolados, pois a sobrecarga de instruções é completamente removida e o kernel corresponde melhor ao modelo de processamento SIMD.
A implementação básica do AES expande a chave no processador de Host e copia a chave expandida para a memória constante no GPU. Agora, você investigará o planejamento principal no próprio GPU usando memória compartilhada de alta largura da banda. É necessário expandir a chave para cada bloco de encadeamento individualmente, pois a memória compartilhada não pode ser acessada em vários blocos de encadeamento. A chave de cifra não expandida é copiada de um host para um buffer de memória constante no GPU.
Para cada bloco de encadeamento, uma matriz de tamanho igual à chave expandida é criada na memória compartilhada. O tamanho da chave expandida depende do comprimento da chave sendo usado e é 240 bytes para a chave de 256 bits. O primeiro encadeamento
(tidx=0) de cada bloco de encadeamento copia a chave de cifra para essa matriz compartilhada e chama a função de expansão principal.
A Figura 7 abaixo descreve o caminho seguido por cada bloco de encadeamento. Uma barreira é colocada no kernel após a função de expansão principal. Isso é necessário para garantir que nenhum encadeamento prossiga sem as transformações AES antes que a expansão principal seja concluída.
Figura 7. Planejamento principal no dispositivo
O planejamento principal no GPU aumenta o uso da memória compartilhada por bloco de encadeamento, em 240 bytes, passando para 8432 bytes. A ocupação do dispositivo agora é limitada pela memória compartilhada a 5 blocos de encadeamento por SM. O uso de Registro por bloco de encadeamento não é maior que o gargalo, pois ainda permite 6 blocos de encadeamento por SM. A sobrecarga de cálculo incorrida pelo bloco de encadeamento não é significativa, pois a expansão principal não é uma função de cálculo intenso.
O desempenho geral do kernel diminuiu como resultado da menor ocupação do dispositivo. A degradação do desempenho não é muito significativa, pois a menor ocupação do dispositivo está, até certo ponto, sendo compensada pelo acesso relativamente mais rápido à chave expandida na memória compartilhada.
O paralelismo inerente no algoritmo AES mostra melhores ganhos de desempenho para tamanhos de dados grandes, portanto, é bem adequado para a criptografia em massa. Nas referências, isso será validado por meio dos resultados de desempenho obtidos em vários tamanhos de entrada. A Figura 8 mostra uma comparação de desempenho do Tesla C2050 com uma CPU de núcleo i7 a 2,8 GHz e indica um aumento rápido do tempo de criptografia na Intel para arquivos maiores com um aumento do tempo mínimo no processador gráfico. O gráfico foi plotado com o tamanho de entrada no eixo horizontal (megabytes) e o tempo de execução do kernel (milissegundos) para o AES de 256 bits no eixo vertical.
Figura 8. Desempenho do AES no NVIDIA TESLA C2050
A Figura 9 mostra a comparação de desempenho de vários hardwares para um kernel do AES totalmente otimizado. As referências para a CPU Core i7 são obtidas usando 8 encadeamentos no OpenCLTM. Os resultados indicam valores baixos na Intel e valores 25 vezes maiores na NVIDIA.
Figura 9. Comparação de desempenho do AES
Descrevemos uma implementação CUDA do AES e demonstramos um procedimento de otimização passo a passo para ela. Os resultados provam a enorme melhoria de desempenho por meio de GPUs e mostra acelerações consideráveis em comparação com o processador Intel de geração atual ou placas gráficas de mercadoria. Essas técnicas de otimização são utilizadas no aplicativo gKrypt e no mecanismo para acelerar as tarefas de criptografia de cálculo intensivo. As técnicas facilitam o uso do gKrypt e o amplo suporte à plataforma facilita sua implementação com produtos do consumidor.
Aprender
- Proteja seus dados à velocidade da luz com o gKrypt, Parte 1 (Jawad masood, developerWorks, abril de 2012) apresenta uma introdução ao mecanismo gKrypt e algoritmo AES.
- Examine AES Encryption Implementation and Analysis on Commodity Graphics Processing Units (Owen Harrison e John Waldron, 2007) e suas abordagens recentes para a implementação do algoritmo de criptografia da cifra do bloco do AES em GPUs.
- Leia Brute Force Attack on UNIX Passwords with SIMD Computer (Gershon Kedem e Yuriko Ishihara, Proceedings of the 8th USENIX Security Symposium, agosto de 1999) para avaliações da segurança do esquema de senha do UNIX.
- Revise CUDA compatible GPU as an efficient hardware accelerator for AES cryptography (Svetlin A. Manavski, IEEE International Conference on Signal Processing and Communications, 2007), um estudo da eficiência na aplicação de Modern Graphics Processing Units em soluções criptográficas de chave simétrica.
- Examine A performance prediction model for the CUDA GPGPU platform (K.Kishore, Rishabh Mukherjee, Suhail Rehman, P.J.Narayanan e K.Srinathan; Technical Report IIIT/TR/2009/82, IIIT Hyderabad, 2009) para ver um modelo de previsão de desempenho para a plataforma GPGPU de CUDA.
- Leia aFIPS 197: Advanced Encryption Standard (AES), 2001, do National Institute of Standards and Technology (NIST), que especifica um algoritmo criptográfico aprovado por FIPs que pode ser usado para proteger dados eletrônicos.
- Revise FIPS 46-3: Data Encryption Standard (DES) [o National Institute of Standards and Technology (NIST), 1999], que especifica dois algoritmos criptográficos, o Padrão de Criptografia de Dados (DES) e o Algoritmo de Criptografia de Dados Triplo (TDEA).
- Saiba mais sobre Programming Massively Parallel Processors: A Hands-on Approach (David B. Kirk e Wen-mei W. Hwu, Elsevier, 2010) nesses conceitos básicos de programação paralela e de arquitetura do GPU.
- Na rotina zona Linux do developerWorks, encontre vários artigos de instruções e tutoriais, bem como downloads, fóruns de discussão e muitos outros recursos para desenvolvedores e administradores Linux.
- O texto zona de software livre do developerWorks fornece muitas informações sobre ferramentas de software livre e de como utilizar tecnologias de software livre.
- Fique por dentro dos eventos técnicos e webcasts do developerWorks com ênfase em uma série de produtos IBM e assuntos relacionados ao segmento de mercado de TI.
- Participe de um briefing ao vivo e gratuito
do developerWorks para se atualizar rapidamente sobre produtos e ferramentas IBM e tendências do segmento de mercado de TI.
- Acompanhe as demos on demand do developerWorks , que abrangem desde demos de instalação e configuração de produtos para iniciantes até funcionalidades avançadas para desenvolvedores experientes.
- Siga o DeveloperWorks no Twitter, ou inscreva-se em um feed de tweets sobre o Linux no developerWorks.
Obter produtos e tecnologias
- Obtenha os drivers habilitados para CUDA mais recentes do NVIDIA.
- Faça o download do código fonte do módulo Calculadora de Ocupação do CUDA, que permite calcular a ocupação do multiprocessador de um GPU por um determinado kernel do CUDA.
- Avalie produtos IBM da maneira que for melhor para você: faça download da versão de testes de um produto, avalie um produto online, use-o em um ambiente de nuvem ou passe algumas horas na SOA Sandbox para saber como implementar arquitetura orientada a serviço (SOA) de maneira eficiente.
Discutir
- Confira os blogs do developerWorks e participe da
comunidade do developerWorks.
- Participe dos comunidade do developerWorks. Entre em contato com outros usuários do developerWorks e explore os blogs, fóruns, grupos e wikis voltados para desenvolvedores.
Jawad Masood é o desenvolvedor líder na gKrypt Data Security Solutions, uma startup com ênfase em fornecer soluções de segurança de dados com custo reduzido usando uma combinação de processadores de diversos núcleos para oferecer uma criptografia de dados em massa e desempenho de compactação acelerados.
