CMU 15-418 (Spring 2012) Final Project

CMU 15-418 (Spring 2012) Final Project:

Parallel Graph Isomorphism Solver

Henry Leung

Reports

Working Schedule

Week What We Plan To Do What We Actually Did

Apr 1-7 Serial implementation Researched for a new project idea

Apr 8-14 Basic (small grid and small number of particles) parellel simulation with statically assigning threads to particles. Continued exploration of NP-complete problems and decided on producing a parallel graph isomorphism solver.

Apr 15-21 Increase particles, dynamically reassign particles to threads. Found a understandable code base.

Apr 22-28 Improve the simulation algorithm for better speedups. Serial implementation complete. Starting parallel program.

Apr 29-May 5 Add rendering

May 6-11 Speed up rendering algorithm

Working Log

Up till April 12th: procrastinate and decided on different project idea.

April 12th - 15th: Researched graph isomorphism solvers/get confused/changing project again
Implement Floyd Warshall Algorithm

Week	What We Plan To Do	What We Actually Did
Apr 1-7	Serial implementation	Researched for a new project idea
Apr 8-14	Basic (small grid and small number of particles) parellel simulation with statically assigning threads to particles.	Continued exploration of NP-complete problems and decided on producing a parallel graph isomorphism solver.
Apr 15-21	Increase particles, dynamically reassign particles to threads.	Found a understandable code base.
Apr 22-28	Improve the simulation algorithm for better speedups.	Serial implementation complete. Starting parallel program.
Apr 29-May 5	Add rendering
May 6-11	Speed up rendering algorithm