Plan Max Manfrin

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	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

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		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	experiments running	9 runs in instance pr2392 are corrupted, redo (4.5h)
2.0.2 Async - Multicolony - ring	Mar 5	Mar 6		done	3 runs in instance pr2392 are corrupted, redo (1.5h)
2.0.3 Async - Multicolony - 3D hypercube	Mar 6	Mar 9		done	[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

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.
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.

Referee activities

International journals

Journal	# papers	paper received on	review to submit before

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