Evaluator

New evaluator architecture: caching, multi-threading

Rationale

The upcoming work on group evolution stategies will introduce new fitness metrics based on the evaluation of several subgroups of any given group. A naive implementation would lead to multiple evaluations of the same subgroups, since two distinct groups can have common subgroups. To keep things simple from the main algorithms of MicroGP, we decided to implement caching inside the evaluation system: thus the GroupPopulation algorithms can request all the needed evaluations without worrying about costs, since the evaluator will transparently eliminate duplicated requests.

However, even with caching, the evaluator will have to deal with an increased volume of groups to evaluate. A simple solution to reduce the time of evaluation is to use multiple threads. In previous versions of MicroGP it was up to the user to implement his own multithreading system. With the new evaluator architecture, users can benefit from automatic multithreading, even when calling external programs, by using a Lua evaluation script. See for example the OneMax/Assembly sample.

Class diagram

We present here a simplified version of the class diagram: only the most important members and methods are shown.

The parts shown in red are conditionally compiled depending on the flag UGP3_USE_LUA, which means that it is possible to get the previous behavior back very easily (for example if the user does not have the required Lua libraries on his system).

Here is a collaboration diagram that shows how two groups containing respectively the individuals A, B, C and B, C, D are evaluated, when we define the fitness of an individual as the fitness of the singleton containing it.

Caching

We see that the class EvaluatorCommon can filter duplicate queries (in this case, we ask two times for the evaluation of a singleton containing only B) and uses the cached value from the first evaluation (GB1) to set the fitness of the second singleton (GB2).

In fact, due to the asynchronous nature of the new evaluation model, the evaluation of GB2 might be requested before the end of the evaluation of GB1. In this case, the cache does not contain the fitness of GB1 yet but it contains an indication that the fitness is about to become available. GB2 is simply put in a list of duplicate requests bound to this cache entry, and when the fitness of GB1 is inserted into the cache, GB2 is updated and removed from the list. This behavior is implemented in the class EvaluatorCommon::CacheEntry, not represented here for the sake of simplicity.

Paralellization

In the diagram, the two workers run in two seperate threads, and the evaluations (of {A} and {A, B, C} in the example) are performed concurrently. From the point of view of MicroGP, the flush() function guarantees that all evaluations requested before it has been called will be performed before it returns. This means that the established way of calling several times eval() and then flush() keeps the same semantics with the new evaluator.

Data races

First of all, the class EvaluatorLuaWorker does not take advantage of MicroGP's Log facilities, and in general does not call any method of any other class of MicroGP, because the main codebase is not synchronized and trying to do anything at all from a thread would result in massive memory corruption and eventually a segmentation fault. This is why all the data needed by Lua workers is extracted from MicroGP's classes and put in a Wrapper object inside a non-paralellized funtion of EvaluatorLuaDispatcher.

Then, we see from the collaboration diagram that both the classes EvaluatorCommon and EvaluatorLuaDispatcher read and write the fitnesses of individuals. These accesses could happen at the same time, since they are not synchronized on the same mutex (some of them are synchronized on the cache mutex from EvaluatorCommon, others rely on the mutex of EvaluatorLuaDispatcher), however it is never the case: EvaluatorCommon only writes fitnesses to individuals that are already in the cache, while EvaluatorLuaWorker only writes the fitnesses of evaluated individuals.

Compiling

The compilation of the presented evaluator requires a C++11 compiler and a matching standard library, which provide the required synchronization abstractions and threads. The Lua part requires the availability of a LuaJIT distribution on the user's system. For example, it can be installed using the package manager on GNU/Linux ditributions.

The main CMake file of the project has been updated with a section that automatically enables the Lua based evaluator when such a LuaJIT distribution is found. To manually force the compilation of the Lua subsystem, one must set the CMake cache variable UGP3_USE_LUA to ON or OFF.