Parallel Four-color Map Solver
We are going to implement a parallel map solver for the four-color problem using openMP and perform a detailed analysis of performance characteristics. We will measure time and memory costs on different region maps and compare the performance between different scheduling algorithms.
Schedule (Updated on Apr. 20)
| Week | Plan | State |
|---|---|---|
| Week 1 (3/27 - 4/2) | Research on the topic and write proposal. | |
| Week 2 (4/3 - 4/9) | Implement a sequential version and successfully run on GHC. | |
| Week 3 (4/10 - 4/16) | Build the frontend web page and backend servers to realize an interactive web application | |
| Week 4 first half (4/17 - 4/19) | Write milestone report. | |
| Week 4 second half (4/20 - 4/23) |
Parallelize the backtracking algorithm using OpenMP. Fine-tune the
scheduling policy and the task size (Yuqing Qiu).
Implement the sequential version of map-to-graph conversion algorithm (i.e. converting a pixel-based map image to an abstract topological graph composed of vertices and edges, with each vertix representing a country and each edge representing a common border) (Chenfei Lou). |
|
| Week 5 first half (4/24 - 4/26) |
Parallelize the first phase in map-to-graph conversion (i.e. finding all countries from
pixel matrix) algorithm by dividing the pixel matrix into multiple sub-matrices that could
be processed in parallel (Yuqing Qiu).
Parallelize the second phase in map-to-graph conversion (i.e. finding all country pairs that have a border in common, i.e. adjacent countries on the original map) algorithm by dividing the pixel matrix into multiple sub-matrices that could be processed in parallel (Chenfei Lou). |
|
| Week 5 second half (4/27 - 4/30) |
Optimize two phases of map-to-graph conversion by experimenting with different task size,
static/dynamic scheduling options that optimize work balancing and minimize cache false
sharing (Yuqing Qiu).
Finish the program to efficiently merge results from different cores and generate the final colored pixel array (Chenfei Lou). |
|
| Week first half 6 (5/1 - 5/4) | Write final report and prepare for the poster session. |