Resumo: Bilhões de dispositivos comporão a Internet das Coisas (do inglês, "Internet of Things" (IoT)) nos próximos anos, gerando uma vasta quantidade de dados que necessitarão ser processados e interpretados eficientemente. A maioria dos dados é atualmente processada na nuvem, contudo, esse paradigma não pode ser adotado para processar a vasta quantidade de dados gerados pela IoT, principalmente devido a limites de largura de banda e requisitos de latência de muitas aplicações. Assim, pode-se usar a computação na borda para processar esses dados usando os próprios dispositivos. Neste contexto, técnicas de aprendizado profundo são adequadas para extrair informações desses dados, mas os requisitos de memória de redes neurais profundas podem impedir que até mesmo a inferência seja executada em um único dispositivo restrito em recursos. Além disso, os requisitos computacionais de redes neurais profundas podem produzir um tempo de execução inviável. Para habilitar a execução de modelos de redes neurais em dispositivos de IoT restritos em recursos, o código pode ser particionado e distribuído entre múltiplos dispositivos. Abordagens diferentes de particionamento são possíveis, no entanto, algumas delas reduzem a taxa de inferência à qual o sistema pode executar ou aumentam a quantidade de comunicação entre múltiplos dispositivos. Nesta tese, o objetivo é distribuir a execução da inferência de Redes Neurais de Convolução entre diversos dispositivos da IoT restritos. Três algoritmos de particionamento automático que modelam a rede neural profunda como um grafo de fluxo de dados e focam nas características de IoT foram propostos, usando funções-objetivo como maximização da taxa de inferências ou minimização de comunicação e considerando limites de memória como restrição. O primeiro algoritmo é o Particionamento baseado em Kernighan e Lin, cuja função-objetivo é minimizar a comunicação, respeitando as restrições de memória de cada dispositivo. O segundo algoritmo é o Particionamento de Redes Neurais Profundas para Dispositivos Restritos da IoT, que, adicionalmente ao primeiro algoritmo, pode maximizar a taxa de inferências da rede neural e também pode contabilizar apropriadamente a quantidade de memória requerida pelos parâmetros compartilhados e biases de Redes Neurais de Convolução. Finalmente, o terceiro algoritmo é o Particionamento Multinível de Redes Neurais Profundas para Dispositivos Restritos da IoT, um algoritmo que emprega a abordagem multinível para reduzir o tamanho do grafo e aproveitar as capacidades do algoritmo anterior. A principal contribuição desta tese é mostrar que se deve considerar o particionamento por neurônios ao particionar redes neurais profundas em dispositivos restritos da IoT. Comparada aos algoritmos na literatura, a redução de comunicação é geralmente a única função-objetivo oferecida e não há consideração de restrições de memória, permitindo que esses algoritmos produzam particionamentos inválidos. Além disso, os algoritmos propostos nesta tese, na maioria das vezes, produzem resultados melhores do que as abordagens na literatura. Finalmente, outra contribuição é que se podem utilizar os algoritmos propostos para particionar entre quaisquer dispositivos qualquer computação que possa ser expressa como um grafo de fluxo de dados Ver menos

Abstract: Billions of devices will compose the Internet of Things (IoT) in the next few years, generating a vast amount of data that will have to be processed and interpreted efficiently. Most data are currently processed on the cloud, however, this paradigm cannot be adopted to process the vast amount of data generated by the IoT, mainly due to bandwidth limits and latency requirements of many applications. Thus, we can use edge computing to process these data using the devices themselves. In this context, deep learning techniques are generally suitable to extract information from these data, but the memory requirements of deep neural networks may prevent even the inference from being executed on a single resource-constrained device. Furthermore, the computational requirements of deep neural networks may yield an unfeasible execution time. To enable the execution of neural network models on resource-constrained IoT devices, the code may be partitioned and distributed among multiple devices. Different partitioning approaches are possible, nonetheless, some of them reduce the inference rate at which the system can execute or increase the amount of communication that needs to be performed between the IoT devices. In this thesis, the objective is to distribute the inference execution of Convolutional Neural Networks to several constrained IoT devices. We proposed three automatic partitioning algorithms, which model the deep neural network as a dataflow graph and focus on the IoT features, using objective functions such as inference rate maximization or communication minimization and considering memory limitations as restrictions. The first algorithm is the Kernighan-and-Lin-based Partitioning, whose objective function is to minimize communication, respecting the memory restrictions of each device. The second algorithm is the Deep Neural Networks Partitioning for Constrained IoT Devices, which, additionally to the first algorithm, can maximize the neural network inference rate and can also account appropriately for the amount of memory required by the shared parameters and biases of Convolutional Neural Networks. Finally, the third algorithm is the Multilevel Deep Neural Networks Partitioning for Constrained IoT Devices, an algorithm that employs the multilevel approach to reduce the graph size and take advantage of the previous algorithm capabilities. The major contribution of this thesis is to show that we should consider the partitioning per neurons when partitioning deep neural networks into constrained IoT devices. When compared to the literature algorithms, communication reduction is usually the only offered objective function and there is no consideration of memory restrictions, allowing these algorithms to produce invalid partitionings. Additionally, our algorithms mostly produce better results than the approaches in the literature. Finally, another contribution is that we can use the proposed algorithms to partition into any kind of device any computation that can be expressed as a dataflow graph Ver menos