Difference between revisions of "Plan Max Manfrin"

From IridiaWiki
Jump to navigationJump to search
Line 126: Line 126:
 
| '''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 ||
 
|-
 
|-
| '''2 Async algorithms''' || || || || ||
+
| '''2 Async algorithms''' || || || || || In case of problem try to get help from Anders
 
|-
 
|-
| '''2.0.0''' Implement async versions || || Feb 26 || || || 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.01''' 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.02''' 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.3''' Async - Multicolony - ring || || Mar 3 || experiments to be launched Mar 3 at 09:00 || ||

Revision as of 17:05, 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
      • 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
  • 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)
  • 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
1 Sync algorithms
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.0 Disable cron jobs on nodes r05, r07, r19, r32 Feb 21 done RE-ENABLE cron scripts after finishing experiments
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
2 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
3 Paper related work
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

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