Παράλληλη υλοποίηση αλγόριθμου υπερβολικής χαρτογράφησης δικτύων και εφαρμογή του στο διαδίκτυο

Abstract

The purpose of the thesis is the parallel implementation of a hyperbolic network mapping algorithm in order to achieve runtime speed-up. To make this feasible, we need a parallel computing system and/or multiprocessor system. After a briefing conducted by the Staff of CY-Tera at the Cyprus University of Technology for the above possibilities that can be offered to the scientific-research community, we thought to take this opportunity by implementing our parallel algorithm in CY-Tera. During studying parallel programming, we were faced with the two methods, the parallelization using the MPI library and the parallelization using the OPM library (openmp). The MPI Library enables one to build a message passing interface between computers using TCP/IP protocols. The OPM library (openmp) enables one to parallelize processes on different processors on the same computer. We studied the advantages and disadvantages of these two parallelization methods and decided a hybrid solution using both methods, parallelizing processes per computer and per processor. First, we have done an extensive study of the original serial code, and especially of the mapping algorithm’s data dependencies, and then we implemented a parallel version of the same algorithm. We execute and illustrate experiments using different input networks to the network mapping algorithm, and measure the improved running time (speedup) that is achieved due to the parallel implementation of the algorithm.