# Parallelizing evolutionary algorithm on PBS

I have been granted access to a cluster running PBS and I'd like to run a Evolutionary Algorithm (EA) on it.

To those unfamiliar with EAs, Wikipedia summarizes it as:

Part One: Generate the initial population of individuals randomly (first generation).

Part Two: Repeat the following steps until termination:

1. Evaluate the fitness of each individual in the population
2. Select the fittest individuals for reproduction (parents)
3. Breed new individuals through crossover and mutation operations to give birth to offspring.
4. Replace the least-fit individuals of the population with new individuals.

Evaluating the fitness of a individual may take up to 1 hour, and that is running on a node with specialized hardware (Xeon Phi). Everything else is relatively cheap (can be executed in less than 60 seconds on a single CPU).

What I planned to do was:

Generate the initial population on my own computer and upload it to the cluster, then launch a job "ea_loop" that:

1. Launches N jobs, with N=number on individuals in the population, to evaluate the fitness of the individuals.
2. Every 60 seconds check if all of jobs finished.
3. When all jobs have finished, execute steps 2, 3 and 4 of the EAs second part.
4. Check if a termination criteria has been met, if not goto 1.

My main problem is: it appears I can not launch the subjobs, I get the following error message when I try to launch them.

qsub: Bad UID for job execution

My secondary problems are related to the inelegance of my planned solution. Checking if the jobs finished every 60s seconds is somewhat smelly; is there a way to use some sort of callback?

You're using the wrong tool for this kind of operation. PBS schedules individual jobs, but it's intended to deal with jobs of the kind "run the optimization algorithm", not "run one function evaluation".

My suggestion to implement this kind of algorithm is to build on MPI and write it as a master-slave [1] algorithm where the slaves do the function evaluations and the master coordinates the overall orchestration. This is not too complicated to do with P2P communication.

[1] I'm no longer too fond of the expression "master-slave", but haven't yet found what the right replacement term should be that's understandable to everyone. What are people using?

• I have seen some people using conductor-worker when they refer to master-slave type parallelization algorithms. There is also cute alternative master-minion and sci-fi/bio alternative hivemind-drones. I find conductor-worker adequately descriptive, but it is still not that common in its use. – Abdullah Ali Sivas Nov 26 '20 at 18:47
• Fortunately our professional societies are working on guidance to help get rid of the master/slave terminology: eetimes.com/its-time-for-ieee-to-retire-master-slave. – Bill Barth Nov 28 '20 at 16:28

I think what you're trying to do is totally reasonable. I don't think there's any problem running your ea_loop script on the head node provided it's doing mostly control level operations like submitting jobs and checking for completion, etc.

Can you wrap your EA operations that take ~60 seconds into a small job that's submitted through PBS instead of trying to do those computations directly on the head node?

• Depending on how big $$N$$ is, you might want to break up each generation into sections out of courtesy so you don't flood the queue. While resource managers/schedulers are supposed to be able to handle a lot of queued jobs, in my experience it's extremely frustrating when someone floods the queue with 100s of jobs at a time. (I've also been that person who flooded the queue and gotten annoyed looks from my peers :) )
• @Trauer Agreed that it should be an efficient way of utilizing resources. That of course depends on how advanced the scheduling policies are. Regarding possible time limits on the head node, the only way I'm aware that could be enforced would be via ulimit (assuming Unix/Linux). You should be able to check that via the command ulimit -a or ulimit -t. Or just try it and see if it works. – LedHead Nov 28 '20 at 17:14