Difference between revisions of "Plan Max Manfrin"
From IridiaWiki
Jump to navigationJump to search| Line 108: | Line 108: | ||
! Description !! Start date !! Deadline !! Completion date !! status !! Note |
! Description !! Start date !! Deadline !! Completion date !! status !! Note |
||
|- |
|- |
||
| − | | ''' |
+ | | '''SYNC ALGORITHMS''' || || Feb 25 || || || |
|- |
|- |
||
| '''1.0''' Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour || Feb 16 || Feb 21 || || in progress || |
| '''1.0''' Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour || Feb 16 || Feb 21 || || in progress || |
||
| Line 124: | Line 124: | ||
| '''1.1.5''' Sync - Multicolony - 3D hypercube || || Feb 25 || || experiments to be launched Feb 25 at 12:00 || |
| '''1.1.5''' Sync - Multicolony - 3D hypercube || || Feb 25 || || experiments to be launched Feb 25 at 12:00 || |
||
|- |
|- |
||
| − | | ''' |
+ | | '''ASYNC ALGORITHMS''' || || || || || In case of problem try to get help from Anders |
|- |
|- |
||
| '''2.0.1''' Async - Multicolony - all-all || || Feb 26 || experiments to be launched Feb 27 at 00:30 || || |
| '''2.0.1''' Async - Multicolony - all-all || || Feb 26 || experiments to be launched Feb 27 at 00:30 || || |
||
| Line 136: | Line 136: | ||
| '''2.0.5''' Asynch - MultiLS || || Mar 6 || experiments to be launched Mar 6 at 12:00 || || |
| '''2.0.5''' Asynch - MultiLS || || Mar 6 || experiments to be launched Mar 6 at 12:00 || || |
||
|- |
|- |
||
| − | | ''' |
+ | | '''PAPER WRITING''' || || || || || |
|- |
|- |
||
| '''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.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 || |
||
| Line 142: | Line 142: | ||
| '''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.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, and begin to write Intro, Literature, Description of Algorithms || || || || || |
||
| ⚫ | |||
| + | |- |
||
| ⚫ | |||
|- |
|- |
||
| '''4.1''' Disable cron jobs on nodes r05, r07, r19, r32 || Feb 21 || || || done || '''RE-ENABLE cron scripts after finishing experiments''' |
| '''4.1''' Disable cron jobs on nodes r05, r07, r19, r32 || Feb 21 || || || done || '''RE-ENABLE cron scripts after finishing experiments''' |
||
|- |
|- |
||
| − | | ''' |
+ | | '''DATA ANALYSIS''' || || || || || |
|- |
|- |
||
| '''5.1''' Write scripts to collect experimental results, bring them into R, and plot graphs || || || || || |
| '''5.1''' Write scripts to collect experimental results, bring them into R, and plot graphs || || || || || |
||
Revision as of 17:12, 21 February 2006
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"
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
- Move to Vehicle Routing Problem
- Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
Milestone IV : Oct - Dec 2006
- Add complexity to the VRP problem moving into Rich VRP
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 | ||
| Implement Asynch versions | |||||
| Experiments on TSP instances (1000 < size < 6000) | Feb 26, 2006 | in progress | |||
| 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 |
|---|---|---|---|---|---|
| SYNC ALGORITHMS | Feb 25 | ||||
| 1.0 Patch the algorithms in such a way that they use only globabl best in pheromone update and they use quadrant nearest neighbour | Feb 16 | Feb 21 | in progress | ||
| 1.0.1 Sync - Multicolony - all-all | Feb 16 | Feb 21 | Feb 19 | done | experiments finished |
| 1.0.2 Sync - Multicolony - replace-worst | Feb 19 | Feb 21 | Feb 19 | experiments running | |
| 1.1 Patch the 3 following algorithms in such a way that they write the output on /tmp (local to the node) instead of /home (NFS mounted) | Feb 21 | Feb 23 | in progress | Will have to do also for completly-connected and replace-worst | |
| 1.1.3 Sync - MultiLS | Feb 19 | Feb 21 | Feb 21 | development complete, experiments to be launched Feb 22 at 09:00 | test before launching experiments |
| 1.1.4 Sync - Multicolony - ring | Feb 23 | experiments to be launched Feb 23 at 23:00 | |||
| 1.1.5 Sync - Multicolony - 3D hypercube | Feb 25 | experiments to be launched Feb 25 at 12:00 | |||
| ASYNC ALGORITHMS | In case of problem try to get help from Anders | ||||
| 2.0.1 Async - Multicolony - all-all | Feb 26 | experiments to be launched Feb 27 at 00:30 | |||
| 2.0.2 Async - Multicolony - replace-worst | Mar 1 | experiments to be launched Mar 1 at 14:00 | |||
| 2.0.3 Async - Multicolony - ring | Mar 3 | experiments to be launched Mar 3 at 09:00 | |||
| 2.0.4 Async - Multicolony - 3D hypercube | Mar 4 | experiments to be launched Mar 4 at 23:00 | |||
| 2.0.5 Asynch - MultiLS | Mar 6 | experiments to be launched Mar 6 at 12:00 | |||
| PAPER WRITING | |||||
| 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, and begin to write Intro, Literature, Description of Algorithms | |||||
| CLUSTER SETTINGS | |||||
| 4.1 Disable cron jobs on nodes r05, r07, r19, r32 | Feb 21 | done | RE-ENABLE cron scripts after finishing experiments | ||
| DATA ANALYSIS | |||||
| 5.1 Write scripts to collect experimental results, bring them into R, and plot graphs |
Seminars participation
| Title | Author | Location | Dates |
|---|---|---|---|
| 2nd BEGrid tutorial | - | ULB | Feb 21, 2006 |
Events participation
| Event | Location | Dates |
|---|
Papers to write
| Title | Journal/Conference targeted | Start date | Submission deadline |
|---|---|---|---|
| A Survey of Parallel ACO algorithms | N.A. | N.A. | N.A. |
| Process-level parallelization of ACOTSP | Ants 2006 international workshop | N.A. | Mar 12, 2006 |
| Thread-level parallelization of ACOTSP | N.A. | N.A. | N.A. |
Referee activities
International journals
| Journal | # papers | paper received on | review to submit before |
|---|---|---|---|
| European Journal of Operational Research | 1 | Dec 21, 2005 | Jan 31, 2006 |
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 |
