Connor Mayon

Title of Work: 

Design and programming of multi-threaded algorithms

Abstract:

Genetic algorithms are often used when there is a set of data that we want to manipulate to create the best outcome. The program "Scotch" is a graph-partitioning software that can create balanced cuts when given graph data. My primary goal when interning at the lab "Inria" as part of the “TADaaM” team in Bordeaux, France was to develop a genetic algorithm that could create many different child partitions and pick the best one through natural selection. One specification of this algorithm was that it had to take advantage of parallelization. This means that it needed to use multiple threads, dividing the data and workload among a variable number of processor cores, thus speeding up overall execution time. The genetic algorithm was one of several that could be used through various command line arguments, each one providing different results and taking different amounts of time.

Title of Work (IGP Language):  

La programmation des algorithmes multithreads

Abstract (IGP Language):

On utilise des algorithmes génétiques quand on veut manipuler un ensemble de données pour trouver les meilleurs résultats. Le logiciel « Scotch » crée une division dans un graphique pour créer deux parties équilibrées. J’ai passé un semestre dans le laboratoire « Inria » à Bordeaux, en France, en tant que membre de l’équipe « TADaaM ». Mon but principal était de développer un algorithme pour ce logiciel. Une partie du développement était la parallélisation. L’algorithme devait être multithread pour diviser les données entre les cœurs du processeur. Avec une bonne implémentation de la parallélisation, on pourrait augmenter la vitesse de l’exécution du programme. Mon algorithme est un de plusieurs, chacun donne des résultats diffèrents.

Elevator Pitch Video

Elevator Pitch Transcript: 

Hello! My name is Connor Mayon. I'm an L5 IGP student and the title of my presentation is Design and programming of multi-threaded algorithms. So, a bit about me, my major is computer science, and my IGP language is French. I spent last year in Bordeaux, France, and I studied at the Université de Bordeaux. I found my internship at the lab Inria. And my first task there was to learn about the Scotch software. Scotch is a graph partition software. It takes in a set of vertices and edges and can create divisions resulting in 2 or more balanced subgraphs. I had to design and develop a genetic algorithm for Scotch and a genetic algorithm, in this case it would create a bunch of random partitions, and then it would rank those partitions in terms of fitness and would remove the lowest fit and have the highest fit ones mate. And they would keep doing this over number of generations until we finally pick the best fit one, and that is the one we use as our partition. So in order to create this algorithm, I had to write steps down in English. I had to then turn that into code, and then I could test and debug the code. And once it's all working, I would parallelize the code. And what that involves is, instead of having one thread handle all of the data and doing all of the tasks in the algorithm. The the data which would be the partitions in this case would be split across multiple threads which would run concurrently, thus speeding up the overall process. So overall takeaways, I got I got to experience working with larger code bases, while my code was contained to a small handful of files. The overall Scotch Repository consisted of probably around hundreds of files, at least 100. I got to learn extra steps to take for debugging, such as using tools like Gdb. And it helped me improve my problem solving. So overall, I really enjoyed my experience, and I wouldn't mind continuing down the road of data sciences. And that's all for my presentation. Thank you.

Digital Poster