This section gives some information on the low-level workings of GFD and how to adjust it. This information is not needed for most users, and can be skipped and consulted only when GFD is not behaving well with the user’s program.
GFD is designed so that the user can write programs that will run with Gecode without knowing any details about Gecode or how GFD interfaces to it. However, GFD does provide some parameters to control its behaviour. While the default settings should work well under most circumstances, some understanding of the inner workings of GFD is needed to change this default behaviour.
Gecode implements search using a recomputation and cloning model, which is fundamentally different from the backtracking model of ECLiPSe. When failure occurs, Gecode does not backtrack to a previous computation state; instead, the previous state is recomputed. To reduce the amount of recomputation, the computation state is cloned periodically during execution, and the recomputation would start from the nearest such cloned state rather than from the start.
With GFD, when the search is done in Gecode (via GFD’s search/6), the recomputation and cloning is handled by Gecode. When the search is done at the ECLiPSe level, GFD handles the recomputation and cloning automatically, so that the user does not need to be aware of it.
GFD will create clones of the Gecode state periodically, and when the current Gecode computation state becomes invalid through ECLiPSe backtracking, GFD will recompute the new state from the closest cloned state. The frequency at which GFD create clones can be adjusted by the user – the more frequently clones are created, the more memory will be used, but the cost of recomputation will be less. Cloning itself will take time, and depends on the size of the state. Normally, the cost of cloning is quite low, so GFD by default will clone frequently during search, as this leads to faster execution times. However, if the program has a large state (many variables and constraints), then frequent cloning may lead to excessive memory consumption (and larger computation state will also be more expensive to clone), and reducing the frequency of cloning may improve performance.
The frequency of cloning in GFD is controlled by the cloning_distance parameter, which can be changed by gfd_set_default/2 (and the current value can be accessed with gfd_get_default/2) The cloning_distance specifies a threshold for the number of changes GFD makes to the Gecode state before a clone is created. Note that GFD does not create a clone simply when cloning_distance is exceeded, as it only creates a new clone when the cloned state would be the state just before a choice-point, so clones will normally only be created during search phase of the user program.
While it is not necessary for the user to specify the creation of a clone, under very unusual circumstances – when the cloning_distance is set very high – GFD may not produce a clone at the right place. So gfd_update/0 is provided to force the creation of a clone. The expected usage is to call this predicate just before search starts. For example, labeling/3 can be written as:
labeling(Vs, Select, Choice) :-
gfd_update,
labeling1(Vs, Select, Choice, _).
labeling1(Vs, Select, Choice, VsH) :-
( select_var(V, Vs, 0, Select, VsH) ->
indomain(V, Choice),
labeling1(Vs, Select, Choice, VsH)
;
true
).
Calling gfd_update before calling labeling1 ensures that GFD will only recompute inside the search.