PARALLEL ALGORITHMS FOR CRYPTOGRAPHY, INTERACTING PARTICLES SYSTEMS AND MACHINE LEARNING

Abstract

The exponential growth of the new technologies and the development of hardware in modern computers are due to multi-core CPU1 and powerful GPU2. The High Performance Computing greatly improved the performance in solving several problems. I discuss in this thesis three different problems: 1) Factorization problem General Number Field Sieve (GNFS) is known to be the perfect candidate for the factorization task. The procedure is dominated by a step called sieving. Due to the size of the number we want to factor (ex: RSA modulus), the procedure needs to per form the same operation on a large set (Single Instruction Multiple Data). For this purpose, we exploit the features of the GPU to handle this operation, implementing the sieving procedure to run on the GPU. A benchmark that measure the perfor mance of GPU Tesla P100 compared to the CPU (serial and parallel) is provided. We obtained a speed-up of the algorithm which is parameterized by the features of the GPU (amount of cache memory) and the size of the input (cardinality of the factor-base). This experiment is implying a proof of concept which shows that the procedure can benefit from the new generation GPU. 2) Numerical methods in statistical mechanics The problem of describing the phase transition for the 2D Ising model is approached numerically. As a Markov Chain, the dynamics of this model can be simulated by means of Probabilistic Cellular Automata. Recently, dynamic known as shaken dy namics was introduced on two layers of square lattice. Using this dynamics we are able to estimate numerically the critical curve which separates the ordered and disordered phases on the parameter region (J, q). Furthermore, it induces a procedure suitable for a parallel environment to simulate in real-time the dynamics on GPU. Our experiment can be generalized as a study of the numerical aspect of shaken dy namics. In particular, we compare it with the alternate dynamics on the critical line (bisector J = q), also we are able to evaluate numerically the equilibrium distribu tion of the dynamics in a given region (J, q). 3) Machine learning Machine learning is one of our daily life applications which causes the fast development of dedicated hardware for High Performance Computing. Image classification belongs to the intersection between machine learning and computer vision which aims to detect the features from input pixel images in an elegant and fast way. As a fact, Deep Convolutional Neural Networks is among the best preforming techniques when dealing with this task. We applied this technique on architectural images to provide a light model with a good performance that can be used in a mobile device. The project can be seen as an instruction guide, starting from scratch for the building of mobile applications. It can be considered as a proposal for the interaction of Artificial Intelligence(AI) with the urban context, a starting point that leads to more complicated tasks in architecture that can be faced by means of AI.

La crescita esponenziale di nuove tecnologie e lo sviluppo dell’hardware nei moderni computer sono dovuti alle CPU multi-core e alla potenza delle GPU. L’High Performance Computing ha ampiamente migliorato le performance nella risoluzione di molti problemi. In questa tesi, discuto tre diversi problemi: 1) Il problema della fattorizzazione Il General Number Field Sieve (GNFS) è ritenuto un perfetto candidato per il problema della fattorizzazione. La procedura è dominata da un passaggio chiamato sieving. A causa della dimensione del numero che si vuole fattorizzare (RSA modulus ad esempio), la procedura deve ripetere la stessa operazione su un ampio insieme (Single Instruction Multiple Data). A questo fine, si sfruttano le caratteristiche della GPU per gestire l’operazione, implementando la procedura di sieving su GPU. Si fornisce un benchmark per misurare la performance di una GPU Tesla P100 rispetto alla CPU (seriale e parallela). Si ottiene un’accelerazione dell’algoritmo che dipende dalle caratteristiche della GPU (quantità di memoria cache) e dalla dimensione dell’input (cardinalità della factor-base). L’esperimento prevede una proof of concept per mostrare come la procedura possa beneficiare della nuova generazione di GPU. 2) Metodi numerici in meccanica statistica Si affronta numericamente il problema della descrizione della transizione di fase per il modello di Ising bidimensionale. Poiché il modello è una catena di Markov, la dinamica può essere simulata attraverso automi cellulari probabilistici. Di recente, dinamiche conosciute come shaken dynamics sono state introdotte su un reti colo quadrato a due livelli. Usando queste dinamiche è possibile stimare numericamente la curva critica che separa le fasi ordinata e disordinata nella regione di parametri (J, q). Inoltre, si introduce una procedura per simulare le dinamiche in tempo reale in ambiente parallelo su GPU. Gli esperimenti condotti possono es sere generalizzati come studio degli aspetti numerici delle shaken dynamics. In particolare, queste sono messe a confronto con dinamiche alternative sulla retta critica (bisettrice J = q) e si può inoltre calcolare numericamente la distribuzione d’equilibrio delle dinamiche in una data regione (J, q). 3) Machine Learning Il machine learning è una delle applicazioni che producono il rapido sviluppo di hardware dedicato per l’High Performance Computing. Il riconoscimento di immagine fa parte dell’intersezione tra machine learning e computer vision, finalizzata a individuare features in una immagine raster di input in maniera elegante e veloce. Di fatto, i modelli Deep Convolutional Neural Networks sono tra le tecniche che mostrano le migliori performance nell’affrontare questi problemi. Queste tecniche sono applicate a immagini con soggetto d’architettura, al fine di ottenere un modello leggero che possa essere usato con buone performance su un dispositivo mobile. Il progetto può essere visto come una guida che parte da zero per la costruzione di applicazioni mobili. Lo stesso può essere considerato una proposta per l’interazione dell’Artificial Intelligence (AI) con il contesto urbano, un punto d’inizio che conduca a più complessi problemi nel campo dell’architettura affrontati con AI.