Difference between revisions of "Plan Max Manfrin"

From IridiaWiki
Jump to navigationJump to search
 
(87 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
= Plan (future work) =
  
= Plan (future work) =
   
  +
== Milestone I: Jan - Mar 2006==
   
−
'''Parallelization of ACO algorithms'''
  
   
−
'''Milestone I''': Jan - Mar 2006
  
 
* Acquire practical experience in explicit parallelization on ACO algorithms
  
* Acquire practical experience in explicit parallelization on ACO algorithms
 
** Start from sequential ACOTSP and implement various MPI variants
  
** Start from sequential ACOTSP and implement various MPI variants
 
*** Sync
  
*** Sync
−
**** Multicolony - completly-connected
 +
**** Multicolony - fully-connected
−
***** each colony identifies the best bsf and grab it
 +
***** colony 0 identifies the best colony; best colony broadcast its bsf solution
−
***** the colony with the worst bsf grab the best bsf
 +
***** colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
 
**** Multicolony - ring
  
**** Multicolony - ring
  +
***** unidirectional ring
 
**** Multicolony - hypercube
  
**** Multicolony - hypercube
  +
***** 3D hypercube
 
**** Single colony, multi local search
  
**** Single colony, multi local search
 
*** Async
  
*** Async
 
**** Multicolony - completly-connected
  
**** Multicolony - completly-connected
−
***** each colony identifies the best bsf and grab it
 +
***** colony 0 identifies the best colony; best colony broadcast its bsf solution
−
***** the colony with the worst bsf grab the best bsf
 +
***** colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
 
**** Multicolony - ring
  
**** Multicolony - ring
  +
***** unidirectional ring
 
**** Multicolony - hypercube
  
**** Multicolony - hypercube
  +
***** 3D hypercube
−
**** Single colony, multi local search
  
 
* Paper submission to ANTS 2006 of "explicit parallelization of ACOTSP"
  
* 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 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 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?)
 +
* 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 ?
  
** 1. Parallelization of ACO on multi-core architectures ?
 
** 2. Parallelization of ACO on collection of interesting problems?
  
** 2. Parallelization of ACO on collection of interesting problems?
   
   
−
'''Milestone II''': Apr - Jun 2006
 +
==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"
  
   
   
  +
* Development and empirical test of different communication schemes among colonies
−
'''Milestone III''': Jul - Sep 2006
  
  +
<pre>
  +
The i.a.k identify how often we do communication among colonies.
  +
  +
The law used to generate the periods is SQRT[(10)^(i+1)], so
  +
i = 1 --> T = 10
  +
i = 2 --> T = 31
  +
i = 3 --> T = 100
  +
i = 4 --> T = 316
  +
i = 5 --> T = 1000
  +
i = 6 --> T = 3162
  +
i = 7 --> T = 10000
  +
i = 8 --> T = 31622
  +
i = 9 --> T = 100000
  +
  +
The jth exchange happens at iteration
  +
  +
  +
T * (1 - 0.a^j)/(1 - 0.a) IF (int)[x_j - x_(j-1)] > k
  +
x_j =
  +
k OTHERWISE
  +
</pre>
  +
* Start from sequential ACOTSP and implement various MPI variants
  +
** Sync
  +
*** Multicolony - ring
  +
**** unidirectional ring
  +
***** 4.8.10
  +
***** 4.9.10
  +
***** 5.8.10
  +
***** 5.9.10
  +
***** 6.8.10
  +
***** 6.9.10
  +
***** 7.6.10
  +
***** 7.7.10
 
* Transfer the knowledge and experience on TSP to other problems
  
* 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
  
** Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
  +
*** he doesn't use ACO for SCP, but I've helped him anyway to parallelize his own primal-dual algorithm
  +
** Collaboration with Daniele Catanzaro on parallel ACO for phylogeny reconstruction
  +
*** Start from sequential ACO algorithm and implemented MPI variant
  +
**** Sync
  +
***** Multicolony - fully-connected
  +
****** colony 0 identifies the best colony; best colony broadcast its bsf solution
  +
** Identify possible problems for which IRIDIA has expertise and state-of-the-art ACO algo as starting points (Scheduling: Blum, QAP: Thomas)
  +
*** QAP: start from sequential MMASQAP and implement various MPI variants (in total we consider 72 algo)
  +
**** Factor 1: Connection topology
  +
***** Multicolony - fully-connected
  +
****** colony 0 identifies the best colony; best colony broadcast its bsf solution
  +
****** colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
  +
***** Multicolony - ring
  +
****** unidirectional ring
  +
***** Multicolony - hypercube
  +
****** 3D hypercube
  +
**** Factor 2: Communication schema
  +
***** Sync
  +
****** 1.x.10 (constant gap of 10 iterations)
  +
****** 2.9.10
  +
****** 2.8.10
  +
****** 2.7.10
  +
****** 2.6.10
  +
****** 3.9.10
  +
****** 3.8.10
  +
****** 3.7.10
  +
****** 3.6.10
  +
**** Factor 3: Local Search
  +
***** 2-opt
  +
***** tabu search
   
  +
==Milestone III: Jul - Sep 2006==
   
−
'''Milestone IV''': Oct - Dec 2006
  
   
  +
* Tech Report on TSP and QAP experiments
  +
** decision if and how to extend the paper for possible journal article
  +
* Literature survey on parallel ACO algorithms (version 3)
  +
* 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"
   
−
'''Milestone V''': Jan - Mar 2007
 +
==Milestone IV: Oct - Dec 2006==
   
   
−
'''Milestone VI''': Apr - Jun 2007
 +
==Milestone V: Jan - Mar 2007==
   
   
−
'''Milestone VII''': Jul - Sep 2007
 +
==Milestone VI: Apr - Jun 2007==
  +
  +
  +
==Milestone VII: Jul - Sep 2007==
 
* Write PhD thesis
  
* Write PhD thesis
   
Line 69: Line 136:
   
 
= Things to do =
  
= Things to do =
−  
−
{| border=1 cellspacing=0 cellpadding=2
  
−
! 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 || || ||
  
−
|-
  
−
|}
  
−  
   
 
{| border=1 cellspacing=0 cellpadding=2
  
{| border=1 cellspacing=0 cellpadding=2
Line 99: Line 144:
 
| '''Implicit parallelization of ACOTSP using OpenMP''' || - || - || - || Need a compiler
  
| '''Implicit parallelization of ACOTSP using OpenMP''' || - || - || - || Need a compiler
 
|-
 
|-
  +
| Parallel ACO survey v3 || Jul 1, 2006 || Aug 31, 2006 || ||
  +
|-
 
|}
  
|}
   
Line 106: Line 153:
 
{| border=1 cellspacing=0 cellpadding=2
  
{| border=1 cellspacing=0 cellpadding=2
 
! Description !! Start date !! Deadline !! Completion date !! status !! Note
  
! 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 || || to correct || 3 runs in instance pr2392 are corrupted, redo (1.5h)
  
−
|-
  
−
| '''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
  
 
|-
  
|-
 
|}
  
|}
Line 168: Line 161:
 
! Title !! Author !! Location !! Dates
 
! Title !! Author !! Location !! Dates
 
|-
  
|-
  +
| IRIDIA Optimization meeting ||Ch. 4 of the book to present || || Apr 27, 2006
−
| || || ||
 
 
|-
 
|-
 
|}
  
|}
−  
   
 
= Events participation =
  
= Events participation =
Line 189: Line 181:
 
|-
  
|-
 
| A Survey of Parallel ACO algorithms || N.A. || N.A.
  
| 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.
  
| Thread-level parallelization of ACOTSP || N.A. || N.A.
 
|}
  
|}
  +
   
 
= Referee activities =
  
= Referee activities =
Line 206: Line 197:
 
|-
  
|-
 
|}
  
|}
  +
   
 
== International conferences ==
  
== International conferences ==
Line 212: Line 204:
 
! Conference !! # papers !! paper received on !! review to submit before
 
! 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 =
  
= IRIDIA chores =
  +
 
{| border=1 cellspacing=0 cellpadding=2
  
{| border=1 cellspacing=0 cellpadding=2
 
! Chore !! assigned !! status
 
! Chore !! assigned !! status
 
|-
  
|-
−
| Update Dorigo website with Master, DEA, and PhD thesis data || Feb 2, 2006 ||
+
| Update Dorigo website with Master, DEA, and PhD thesis data || Feb 2, 2006 || done
  +
|-
  +
| Create a Wiki page with list of all the software we have for the Mac with #licenses and where they are installed || Apr 21, 2006 ||
 
|-
  
|-
−
| Update Dorigo website with new portoguese interview || Feb 19, 2006 ||
  
 
|}
  
|}

Latest revision as of 21:38, 6 July 2006

History (past work)

http://iridia.ulb.ac.be/wiki/index.php/History_Max_Manfrin


Plan (future work)

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 - fully-connected
          • colony 0 identifies the best colony; best colony broadcast its bsf solution
          • colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
        • Multicolony - ring
          • unidirectional ring
        • Multicolony - hypercube
          • 3D hypercube
        • Single colony, multi local search
      • Async
        • Multicolony - completly-connected
          • colony 0 identifies the best colony; best colony broadcast its bsf solution
          • colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
        • Multicolony - ring
          • unidirectional ring
        • Multicolony - hypercube
          • 3D hypercube
  • 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
  • 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

  • Development and empirical test of different communication schemes among colonies
The i.a.k identify how often we do communication among colonies. 

The law used to generate the periods is SQRT[(10)^(i+1)], so
i = 1 --> T = 10
i = 2 --> T = 31
i = 3 --> T = 100
i = 4 --> T = 316
i = 5 --> T = 1000
i = 6 --> T = 3162
i = 7 --> T = 10000
i = 8 --> T = 31622
i = 9 --> T = 100000

The jth exchange happens at iteration


      T * (1 - 0.a^j)/(1 - 0.a)  IF (int)[x_j - x_(j-1)] > k
x_j = 
      k                          OTHERWISE
  • Start from sequential ACOTSP and implement various MPI variants
    • Sync
      • Multicolony - ring
        • unidirectional ring
          • 4.8.10
          • 4.9.10
          • 5.8.10
          • 5.9.10
          • 6.8.10
          • 6.9.10
          • 7.6.10
          • 7.7.10
  • Transfer the knowledge and experience on TSP to other problems
    • Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
      • he doesn't use ACO for SCP, but I've helped him anyway to parallelize his own primal-dual algorithm
    • Collaboration with Daniele Catanzaro on parallel ACO for phylogeny reconstruction
      • Start from sequential ACO algorithm and implemented MPI variant
        • Sync
          • Multicolony - fully-connected
            • colony 0 identifies the best colony; best colony broadcast its bsf solution
    • Identify possible problems for which IRIDIA has expertise and state-of-the-art ACO algo as starting points (Scheduling: Blum, QAP: Thomas)
      • QAP: start from sequential MMASQAP and implement various MPI variants (in total we consider 72 algo)
        • Factor 1: Connection topology
          • Multicolony - fully-connected
            • colony 0 identifies the best colony; best colony broadcast its bsf solution
            • colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
          • Multicolony - ring
            • unidirectional ring
          • Multicolony - hypercube
            • 3D hypercube
        • Factor 2: Communication schema
          • Sync
            • 1.x.10 (constant gap of 10 iterations)
            • 2.9.10
            • 2.8.10
            • 2.7.10
            • 2.6.10
            • 3.9.10
            • 3.8.10
            • 3.7.10
            • 3.6.10
        • Factor 3: Local Search
          • 2-opt
          • tabu search

Milestone III: Jul - Sep 2006

  • Tech Report on TSP and QAP experiments
    • decision if and how to extend the paper for possible journal article
  • Literature survey on parallel ACO algorithms (version 3)
  • 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"

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
Parallel ACO survey v3 Jul 1, 2006 Aug 31, 2006


Weekly planning

Description Start date Deadline Completion date status Note

Seminars participation

Title Author Location Dates
IRIDIA Optimization meeting Ch. 4 of the book to present Apr 27, 2006

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

IRIDIA chores

Chore assigned status
Update Dorigo website with Master, DEA, and PhD thesis data Feb 2, 2006 done
Create a Wiki page with list of all the software we have for the Mac with #licenses and where they are installed Apr 21, 2006
Retrieved from "https://iridia.ulb.ac.be/w/index.php?title=Plan_Max_Manfrin&oldid=4196"