2
$\begingroup$

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

I Google about this, but pretty much all hits were about job dependencies, which I don't think is an adequate solution. The easy way out would be to run the "ea_loop" in the headnode, but computing on the head node is frowned upo (and probably disallowed). How should I go about this?

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?

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – Abdullah Ali Sivas Nov 26 '20 at 18:47
  • 3
    $\begingroup$ 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. $\endgroup$ – Bill Barth Nov 28 '20 at 16:28
2
$\begingroup$

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?

Some other comments:

  • Submitting jobs from the compute nodes is disabled by default on most PBS implementations, but can be enabled easily by an administrator. It was probably purposely disabled, but if e.g. it's a small cluster maintained by your research group or something this is an easy fix.
  • 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 :) )
  • I don't have a problem with just periodically checking for job completion like you're doing. I think if you want to do something fancier you should just go to the full MPI solution that @WolfgangBangerth has proposed.
$\endgroup$
2
  • 2
    $\begingroup$ I think this approach (creating many small jobs instead of one "thick", long-lasting one) is friendlier (?) because, in principle, jobs from other people could "squeeze in" between one generation and another. I indeed can wrap all EA operations into small jobs, making the ea_loop very slim. However, I am not sure if there is a time limit for commands running on the head node. I sent an email to the administrators asking about this (time limits, subs from other jobs, etc.) As soon as I solve this issue I'll post here :) $\endgroup$ – Trauer Nov 28 '20 at 16:54
  • $\begingroup$ @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. $\endgroup$ – LedHead Nov 28 '20 at 17:14
1
$\begingroup$

While not a direct answer to your question, have you considered using a library which manages the parallelization for you like Pagmo? Presumably, then you just need to request a certain amount of resources from the scheduler on your cluster.

$\endgroup$
1
  • $\begingroup$ I haven't. I mean, the algorithm logic is rather simple and the parallelization is almost trivial. But thank you for the suggestion, I'll check the Pygmo (Pagmo's Python bindings). $\endgroup$ – Trauer Nov 26 '20 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.