Plan Max Manfrin
From IridiaWiki
History (past work)
http://iridia.ulb.ac.be/wiki/index.php/History_Max_Manfrin
Plan (future work)
Parallelization of ACO algorithms
Milestone I: Jan - Mar 2006
- Acquire practical experience in explicit parallelization on ACO algorithms
- Start from sequential ACOTSP and implement various MPI variants
- Sync
- Multicolony - completly-connected
- each colony identifies the best bsf and grab it
- the colony with the worst bsf grab the best bsf
- Multicolony - ring
- Multicolony - hypercube
- Single colony, multi local search
- Multicolony - completly-connected
- Async
- Multicolony - completly-connected
- each colony identifies the best bsf and grab it
- the colony with the worst bsf grab the best bsf
- Multicolony - ring
- Multicolony - hypercube
- Single colony, multi local search
- Multicolony - completly-connected
- Sync
- Start from sequential ACOTSP and implement various MPI variants
- Paper submission to ANTS 2006 of "explicit parallelization of ACOTSP"
- By end of March decision if and how to extend the paper for possible Journal article
- By end of March decision if proceed with MPI version of ILK-H + ACOTSP
- By end of March find the sentence that explain what the PhD thesis is about (what is the contribution of this thesis?)
- 1. Parallelization of ACO on multi-core architectures ?
- 2. Parallelization of ACO on collection of interesting problems?
Milestone II: Apr - Jun 2006
- ? Evolve practical experience in explicit parallelization on ACO algorithms
- ? Start from sequential ILK-H and parallelize it with MPI, calling it within parallel ACOTSP
- Acquire practical experience in implicit parallelization on ACO algorithms
- Start from sequential ACOTSP and implement various OpenMP variants
- Sync ( i.e. implicit barrier in for directives)
- Async (i.e use of the nowait clause)
- Start from sequential ACOTSP and implement various OpenMP variants
- Paper on "implicit vs explicit parallelization of ACOTSP"
- ? Paper on "hybridization of parallel ACOTSP and ILK-H"
Milestone III: Jul - Sep 2006
- Transfer the knowledge and experience on TSP to other problems
- Identify possible problems for which IRIDIA has expertise and state-of-the-art ACO algo as starting points (Scheduling - Blum?)
- Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
Milestone IV: Oct - Dec 2006
Milestone V: Jan - Mar 2007
Milestone VI: Apr - Jun 2007
Milestone VII: Jul - Sep 2007
- Write PhD thesis
Goals
- Investigate the effect of parallelization on Ant Colony Optimization algorithms
- Acquire practical experience in parallelization on ACO algorithms (both explicit and implicit parallelism)
- Implicit parallelism is the new trend (multi core CPUs), not much work has been done on them yet
Things to do
| Description | Start date | Deadline | Time required | status |
|---|---|---|---|---|
| Study OpenMP | Jan 9, 2005 | ongoing process | In progress | |
| Implicit parallelization of ACOTSP using OpenMP | - | - | - | Need a compiler |
| Parallel ACO survey v2 | Apr 10, 2006 |
Weekly planning
| Description | Start date | Deadline | Completion date | status | Note |
|---|---|---|---|---|---|
| Disable the queues on the nodes r21, r24, r26, r27, r29, r31, r32, r33 | Mar 29 | done | |||
| Generate 2 instances with portgen (pgua3162.tsp, pgub3162.tsp) and 2 instances with portcgen (pgca3162.tsp, pgcb3162.tsp) | done | ||||
| Solve the generated instances to optimum with concorde | Mar 29 | Mar 31 | done | pgua3162.tsp --> 50121985 pgub3162.tsp --> 47500868 pgca3162.tsp --> 18547858 pgcb3162.tsp --> 21884136 | |
| Patch the algorithms in such a way that they use restart and communication schema (no-comm for n/2 iter and then exchange bsf every n/4 iter). | |||||
| SEQUENTIAL ALGORITHMS | |||||
| PIR (no-restart) using 16 CPUs for 3600 sec on 6 instances | Mar 29 | Mar 31 | Apr 3 | done | |
| SEQ (no-restart) on 1 CPU for 57600 sec on 6 instances | Apr 4 | Apr 11 | done | ||
| SEQ3 (restart) on 1 CPU for 57600 sec on 6 instances | Apr 4 | Apr 11 | done | ||
| PIR3 (restart) using 16 CPUs for 3600 sec on 6 instances | Mar 31 | Apr 3 | Apr 4 | done | |
| SYNC ALGORITHMS | |||||
| SR2 (no-restart) using 16 CPUs for 3600 sec on 6 instances | Apr 11 | Apr 13 | running | ||
| SRW2 (no-restart) using 16 CPUs for 3600 sec on 6 instances | Apr 14 | Apr 16 | |||
| SRW3 (restart) using 16 CPUs for 3600 sec on 6 instances | Apr 17 | Apr 19 | |||
| SR3 (restart) using 16 CPUs for 3600 sec on 6 instances | Apr 20 | Apr 22 | |||
| ASYNC ALGORITHMS | |||||
| ACC3 (restart) using 16 CPUs for 3600 sec on 6 instances | Apr 23 | Apr 25 |
Seminars participation
| Title | Author | Location | Dates |
|---|---|---|---|
Events participation
| Event | Location | Dates |
|---|---|---|
Papers to write
| Title | Journal/Conference targeted | Submission deadline |
|---|---|---|
| A Survey of Parallel ACO algorithms | N.A. | N.A. |
| Thread-level parallelization of ACOTSP | N.A. | N.A. |
Referee activities
International journals
| Journal | # papers | paper received on | review to submit before |
|---|---|---|---|
International conferences
| Conference | # papers | paper received on | review to submit before |
|---|---|---|---|
| ANTS 2006 | 3 | March 28 | Apr 23 |
| WSC11 | 3-4 (estimation) | May/June 2006 (estimation) | 30 Jun 2006 |
IRIDIA chores
| Chore | assigned | status |
|---|---|---|
| Update Dorigo website with Master, DEA, and PhD thesis data | Feb 2, 2006 | working on it |
| Update Dorigo website with new portoguese interview | Feb 19, 2006 |
