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)
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
- Multicolony - fully-connected
- 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
- 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
- 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
- unidirectional ring
- Multicolony - ring
- Sync
- 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
- Multicolony - fully-connected
- Sync
- Start from sequential ACO algorithm and implemented MPI variant
- 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
- Multicolony - fully-connected
- 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
- Sync
- Factor 3: Local Search
- 2-opt
- tabu search
- Factor 1: Connection topology
- QAP: start from sequential MMASQAP and implement various MPI variants (in total we consider 72 algo)
- Collaboration with Marco Caserta on parallel ACO for Set Covering Problem
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)
- Start from sequential ACOTSP and implement various OpenMP variants
- ? 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 |