Plan Max Manfrin
From IridiaWiki
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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 | to correct | [6,9] runs in instance [d2103,pr2392] are corrupted, redo ([3h,4.5h]) |
2.0.2 Async - Multicolony - ring | Mar 5 | Mar 6 | 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 |