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 | Real deadline |
|---|---|---|---|---|---|
| Study MPI | Nov 14, 2005 | ongoing process | In progress | ||
| Explicit parallelization of ACOTSP using MPI | Nov 14, 2005 | Jan 8, 2006 | ~9 weeks | done | Jan 24, 2006 |
| Synch version of "One colony - many LS (3-opt)" | Nov 14, 2005 | Dec 5, 2005 | ~26 days | done | Jan 24, 2006 |
| Synch version of "Many homogeneous colonies - all-all" | Dec 10, 2005 | Dec 22, 2005 | ~13 days | done | Jan 24, 2006 |
| --= DISCUSSION WITH MARCO, MAURO, THOMAS =-- | Jan 30, 2006 | ||||
| Profile sequential ACOTSP code with instaces (1000 < size < 2000) | Jan 30, 2006 | 1 day | done | ||
| Abstract submission for ANTS 2006 | Mar 12, 2006 | ||||
| Submission of paper for ANTS 2006 | Mar 19, 2006 |
| 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 |
Weekly planning
| Description | Start date | Deadline | Completion date | status | Note |
|---|---|---|---|---|---|
| SEQUENTIAL ALGORITHMS | Mar 10 | ||||
| Parallel independent run (900 sec, 1100 sec, 1500 sec, 1800 sec) | Feb 17 | Feb 19 | done | ||
| Sequential code (7200 sec, 8800 sec, 12000 sec, 14400 sec) | Feb 21 | Mar 10 | done | ||
| SYNC ALGORITHMS | Mar 3 | ||||
| 1.1 Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour, they write the output on /tmp (local to the node) instead of /home (NFS mounted) | Feb 16 | Feb 21 | Feb 27 | done | |
| 1.1.1 Sync - Multicolony - all-all | Feb 16 | Mar 3 | done | ||
| 1.1.2 Sync - Multicolony - replace-worst | Feb 19 | Feb 25 | done | ||
| 1.1.3 Sync - MultiLS | Feb 19 | Feb 27 | done | ||
| 1.1.4 Sync - Multicolony - ring | Feb 20 | Feb 28 | done | ||
| 1.1.5 Sync - Multicolony - 3D hypercube | Feb 27 | Mar 2 | done | ||
| ASYNC ALGORITHMS | Mar 14 | ||||
| 2.0.1 Async - Multicolony - all-all | Mar 1 | Mar 5 | Mar 6 | rerunnig | [6,9] runs in instance [d2103,pr2392] are corrupted, redo ([3h,4.5h]) |
| 2.0.2 Async - Multicolony - ring | Mar 5 | Mar 6 | Mar 12 | done | |
| 2.0.3 Async - Multicolony - 3D hypercube | Mar 6 | Mar 9 | to correct | [9,10] runs in instace [d2103,pr2392] are corrupted, redo ([4.5h,5h]) | |
| 2.0.4 Async - Multicolony - replace-worst | Mar 7 | Mar 11 | Mar 12 | done | |
| 2.0.5 Asynch - MultiLS | Mar 14 | experiments to be launched Mar 12 at 00:00 | |||
| PAPER WRITING | Mar 19 | ||||
| 3.1 Send to Thomas and Mauro a list of all paper that deals with Parallel ACO for TSP that contains experimental results in order to check what the others have been doing | Feb 19 | Feb 21 | Feb 19 | done | |
| 3.2 Read the paper: M. Middendorf, F. Reischle, and H. Schmeck. Multi colony ant algorithms. Journal of Heuristics, 8(3):305â320, May 2002. | Feb 20 | Feb 21 | Feb 20 | done | |
| 3.3 Put down the structure of the paper | Mar 7 | done | |||
| 3.4 Write a Tech Report with the same structure as 3.3 with all results available | Mar 10 | ||||
| 3.5 Submit the abstract via conftool | Mar 12 | Mar 10 | done | ||
| CLUSTER SETTINGS | |||||
| 4.1 Disable cron jobs on nodes r05, r07, r19, r32 | Feb 21 | done | RE-ENABLE cron scripts after finishing experiments | ||
| 4.2. Disable cron jobs (disk-usage every night and monthly report) on majorana | Feb 23 | done | RE-EANBLE cron script "monthly report" after finishing experiments | ||
| DATA ANALYSIS | Mar 12 | ||||
| 5.1 Write scripts to collect experimental results, bring them into R, and plot graphs | Mar 9 | Mar 10 | collection and import done, code for plotting done |
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. |
| Parallel ant colony optimization for the traveling salesman problem | Ants 2006 international workshop | Mar 12, 2006 |
| 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 |
|---|---|---|---|
| GECCO 2006 | 5 | Feb 6, 2006 | Mar 20, 2006 |
| 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 | |
| Update Dorigo website with new portoguese interview | Feb 19, 2006 |
