Skip to main content

GEC

Overview

Generation Core, or GEC, was initially created to serve as the core engine of several verification tools in the verification and analytics department at HRL. GEC consists of:

  • Systematic MAC-based solver with powerful search algorithms over conditional and non-conditional problems.
  • Library of primitive variable types (integer, enum, Bool, and bitstream) with compact representation of domains, including extensive list of set-operations over this representation.
  • Expression-relation propagator for generic propagation of constraints written in a general purpose expression language.
  • Limited set of constraint propagators.

The expression-relation propagator (ERP) provides a rich language for arithmetic, bitwise, and logical expressions over all supported types of data. Given an expression, it automatically constructs a suitable propagator that can either be invoked stand-alone or can be linked to the main solver as one of the CSP's constraints.

GEC implements MAC-3. A few of the distinguishing aspects of this solver are:

  • Support for representation and operation on huge (possibly exponentially large) variable domains.
  • Support for conditional problems, where, depending on the values assigned to certain variables, other variables may become irrelevant to the problem. GEC implements a novel early-pruning algorithm that allows it to conditionally prune the search tree even before it is known whether conditioned variables exist or not.
  • Ability to define a hierarchy of prioritized soft constraints (so-called Borning Hierarchy).
  • Ability to define an objective function for optimization.
  • Generation of random solutions: for a given problem, each run of GEC will produce a random solution out of the solution space. Uniformity of the sampled solutions is attempted, but not always achieved.
  • A command-line-based browser for debugging and analyzing the CSP model and the solution process.

GEC is used in GenesysPro, X-Gen, FPgen, CacheLoader, Floorplanning and Workforce management.

Contact: Merav Aharoni (merav@il.ibm.com)