Difference between revisions of "Plan Max Manfrin"

From IridiaWiki
Jump to navigationJump to search
Line 86: Line 86:
 
! Description !! Start date !! Deadline !! Completion date !! status !! Note
  
! Description !! Start date !! Deadline !! Completion date !! status !! Note
 
|-
  
|-
−
| ''' SEQUENTIAL ALGORITHMS''' || || '''Mar 10''' || || ||
 +
| ''' SEQUENTIAL ALGORITHMS''' || || || || ||
 
|-
  
|-
−
| Parallel independent run (900 sec, 1100 sec, 1500 sec, 1800 sec) || Feb 17 || Feb 19 || || done ||
+
| PIR (no-restart) using 16 CPUs for 3600 sec on 6 instances || Mar 29 || Mar 31 || || running ||
 
|-
  
|-
−
| Sequential code (7200 sec, 8800 sec, 12000 sec, 14400 sec) || Feb 21 || Mar 10 || || done||
+
| SEQ (no-restart) on 1 CPU for 57600 sec on 6 instances || Apr 1 || Apr 2 || || ||
 
|-
  
|-
  +
| PIR3 (restart) using 16 CPUs for 3600 sec on 6 instances || Apr 3 || Apr 5 || || ||
⚫
| '''SYNC ALGORITHMS''' || || '''Mar 3''' || || ||
  
 
|-
  
|-
  +
| SEQ3 (restart) on 1 CPU for 57600 sec on 6 instances || Apr 6 || Apr 7 || || ||
−
| '''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 ||
+
| '''SYNC ALGORITHMS''' || || || || ||
 
|-
  
|-
  +
| '''1''' 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). || || || || ||
−
| '''1.1.2''' Sync - Multicolony - replace-worst || Feb 19 || Feb 25 || || done ||
 
 
|-
  
|-
−
| '''1.1.3''' Sync - MultiLS || Feb 19 || Feb 27 || || done || will not use it for ANTS'06
 +
| '''2''' SRW2 (no-restart) || || || || ||
 
|-
  
|-
−
| '''1.1.4''' Sync - Multicolony - ring || Feb 20 || Feb 28 || Mar 16 || done ||
+
| '''3''' SR2 (no-restart) || || || || ||
 
|-
  
|-
−
| '''1.1.5''' Sync - Multicolony - 3D hypercube || Feb 27 || Mar 2 || Mar 17 || done ||
+
| '''4''' SRW3 (restart) || || || || ||
 
|-
  
|-
  +
| '''5''' SR3 (restart) || || || || ||
−
| '''1.1.6''' Sync - Multicolony - ring2 || Mar 19 || Mar 22 || || done || new communication schema: exchange every n/4 iteration except during the first n/2
 
 
|-
  
|-
  ⚫
| '''ASYNC ALGORITHMS''' || || || || ||
−
| '''1.1.7''' Sync - Multicolony - replace-worst2 || Mar 19 || Mar 22 || || done || new communication schema: exchange every n/4 iteration except during the first n/2
 
 
|-
  
|-
−
| '''ASYNC ALGORITHMS''' || || '''Mar 14''' || || ||
+
| '''1''' ACC3 || Mar 1 || Mar 5 || || done ||
−
|-
  
−
| '''2.0.1''' Async - Multicolony - all-all || Mar 1 || Mar 5 || || done ||
 
−
|-
  
−
| '''2.0.2''' Async - Multicolony - ring || Mar 5 || Mar 6 || Mar 12 || done||
 
−
|-
  
−
| '''2.0.3''' Async - Multicolony - 3D hypercube || Mar 6 || Mar 9 || || done ||
  
−
|-
  
−
| '''2.0.4''' Async - Multicolony - replace-worst || Mar 7 || Mar 11 || Mar 12 || done ||
 
−
|-
  
−
| '''2.0.5''' Asynch - MultiLS || || || || || will not use it for ANTS'06
  
−
|-
  
−
| '''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''' Submit the abstract via conftool || || Mar 12 || Mar 10 || done ||
  
−
|-
  
−
| ''' 3.5''' Prepare draft for final paper || Mar 17 || Mar 19 || || done ||
 
−
|-
  
−
| ''' 3.5''' Prepare support web page for paper || Mar 21 || Mar 23 || || done ||
  
−
|-
  
−
| ''' 3.6''' Write a Tech Report with the same structure as 3.3 with all results available || Mar 13 || Mar 27 || || done ||
  
 
|-
  
|-
 
| '''DATA ANALYSIS''' || || '''Mar 12''' || || ||
  
| '''DATA ANALYSIS''' || || '''Mar 12''' || || ||
−
|-
  
−
| '''4.1''' Write scripts to collect experimental results, bring them into R, and plot graphs || || Mar 9 || Mar 10 || done ||
 
−
|-
  
−
| '''4.2''' Write scripts to produce boxplot at fulltime, fulltime/2, fulltime/4, ..., up to fulltime/128 || Mar 14 || Mar 15 || || done ||
  
−
|-
  
−
| '''4.3''' Select 1 random CPU from PIR algo to create a new sequential reference || || || || ||
  
 
|-
  
|-
 
|}
  
|}

Revision as of 16:40, 30 March 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"
  • 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)
  • 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


Weekly planning

Description Start date Deadline Completion date status Note
SEQUENTIAL ALGORITHMS
PIR (no-restart) using 16 CPUs for 3600 sec on 6 instances Mar 29 Mar 31 running
SEQ (no-restart) on 1 CPU for 57600 sec on 6 instances Apr 1 Apr 2
PIR3 (restart) using 16 CPUs for 3600 sec on 6 instances Apr 3 Apr 5
SEQ3 (restart) on 1 CPU for 57600 sec on 6 instances Apr 6 Apr 7
SYNC ALGORITHMS
1 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).
2 SRW2 (no-restart)
3 SR2 (no-restart)
4 SRW3 (restart)
5 SR3 (restart)
ASYNC ALGORITHMS
1 ACC3 Mar 1 Mar 5 done
DATA ANALYSIS Mar 12

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
Update Dorigo website with new portoguese interview Feb 19, 2006
Retrieved from "https://iridia.ulb.ac.be/w/index.php?title=Plan_Max_Manfrin&oldid=3823"