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 - 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 schema 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
• Identify possible problems for which IRIDIA has expertise and state-of-the-art ACO algo as starting points (Scheduling: Blum, QAP: Thomas)
  • Transfer the knowledge and experience on TSP to other problems
    • Start from sequential MMASQAP and implement various MPI variants
      • Sync
        • Multicolony - fully-connected
          • colony 0 identifies the best colony; best colony broadcast its bsf solution
            • 2.8.5
          • colony 0 identifies the best colony and the worst colony; best colony send its bsf solution to worst colony
            • 2.8.5
        • Multicolony - ring
          • unidirectional ring
            • 2.8.5
        • Multicolony - hypercube
          • 3D hypercube
            • 2.8.5
• 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

Milestone III: Jul - Sep 2006

• Tech Report on extended TSP 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 v2	Apr 10, 2006

Weekly planning

Description	Start date	Deadline	Completion date	status	Note
Disable the queues on the nodes r21, r24, r26, r27, r29, r31, r32, r33	Mar 29			done
Generate 2 instances with portgen (pgua3162.tsp, pgub3162.tsp) and 2 instances with portcgen (pgca3162.tsp, pgcb3162.tsp)				done
Solve the generated instances to optimum with concorde and double check with ILK-H	Mar 29	Mar 31		done	pgua3162.tsp --> 50121985 pgub3162.tsp --> 47500868 pgca3162.tsp --> 18547858 pgcb3162.tsp --> 21884136
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).
SEQUENTIAL ALGORITHMS
PIR (no-restart) using 16 CPUs for 3600 sec on 6 instances	Mar 29	Mar 31	Apr 3	done
SEQ (no-restart) on 1 CPU for 57600 sec on 6 instances	Apr 4	Apr 11		done
SEQ3 (restart) on 1 CPU for 57600 sec on 6 instances	Apr 4	Apr 11		done
PIR3 (restart) using 16 CPUs for 3600 sec on 6 instances	Mar 31	Apr 3	Apr 4	done
SYNC ALGORITHMS
SR2 (no-restart) using 16 CPUs for 3600 sec on 6 instances	Apr 11	Apr 13		done
SRW2 (no-restart) using 16 CPUs for 3600 sec on 6 instances	Apr 13	Apr 16		done
SR3 (restart) using 16 CPUs for 3600 sec on 6 instances	Apr 16	Apr 18		done
SRW3 (restart) using 16 CPUs for 3600 sec on 6 instances	Apr 19	Apr 21		aborted
ASYNC ALGORITHMS
ACC3 (restart) using 16 CPUs for 3600 sec on 6 instances	Apr 21	Apr 24		aborted

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