kernelfoundry.algorithm.evolve_database_optimization_aware

Production MAP-Elites Database for Optimization-Aware Kernel Evolution

This implementation is specialized for optimization-based behavioral features: - memory_opt (0-3): Memory hierarchy exploitation level - compute_opt (0-3): Algorithmic efficiency level - parallelism_opt (0-3): Parallelism granularity level

Architectural Design

• Feature coordinates are DISCRETE (0-3) extracted from code patterns

• No normalization or statistical scaling needed

• Deterministic coordinate assignment (same code → same coordinates)

• 4x4x4 grid = 64 possible behavioral niches

• Elite selection: Best performer in each occupied niche

Performance metrics (runtime, bandwidth, etc.) are used for: - FITNESS SCORING within cells (which program is the elite) - NOT for grid coordinates (which cell a program goes into)

Thread Safety

• All public methods acquire _population_lock before accessing shared state

• Internal methods (prefixed with _) assume lock is already held by caller

• Cache invalidation is atomic via _archive_cache_lock

Functions

deterministic_code_hash(code)	Compute a deterministic hash of code that is stable across Python runs.
get_main_score(metrics)	Get the main fitness score from metrics dictionary.

Classes

ExplorationStrategy(value)	Strategies for identifying underexplored regions.
OptimizationAwareDatabase(config)	Production MAP-Elites database specialized for optimization-aware features.
OptimizationFeatureClassifier()	Classifies kernel optimization levels using static code pattern analysis.
ProgramScoreEntry(neg_score, program_id)	Entry for the score heap (min-heap, so we negate scores for max behavior).
SamplingMethod(value)	Sampling strategies for program selection.

class kernelfoundry.algorithm.evolve_database_optimization_aware.OptimizationAwareDatabase(config)

Production MAP-Elites database specialized for optimization-aware features.

Grid Structure

• 3D grid: memory_opt × compute_opt × parallelism_opt

• Each dimension has 4 discrete levels (0-3)

• Total capacity: 4×4×4 = 64 behavioral niches

• Each cell stores the best program (by fitness score) for that niche

Coordinate Assignment

• Coordinates extracted from code patterns (static analysis)

• Same code always maps to same coordinates

• No normalization, no statistical scaling

• Deterministic and reproducible

Fitness Evaluation

• Performance metrics (runtime, bandwidth, etc.) used for elite selection

• Within each cell, keep the program with highest combined_score

• Metrics do NOT affect coordinates, only fitness ranking

Island Model

• Optional: Multiple sub-populations evolve independently

• Periodic migration of top performers between islands

• Prevents premature convergence

__init__(config)

Initialize optimization-aware MAP-Elites database.

Parameters:

config – Configuration object with: - num_islands: Number of sub-populations - programs_per_island: Programs before island switch - migration_interval: Generations between migrations - migration_rate: Fraction of population to migrate - population_size: Maximum total programs - random_seed: For reproducibility

add(program: Program, island_id: int | None = None, force_add: bool = False, iteration: int | None = None) → bool

Add a program to the database with coordinate calculation.

Process: 1. Extract optimization levels from code (0-3 for each dimension) 2. Map to grid cell coordinates 3. Compare with current elite in that cell 4. Keep better program (by fitness score)

Parameters:

• program – Program to add

• island_id – Island to assign program to (None = auto-assign)

• force_add – If True, bypass population limit enforcement

• iteration – Iteration number (for metadata)

Returns:

True if program became an elite (new or replaced existing)

add_with_parent(child: Program, parent: Program, island_id: int | None = None, force_add: bool = False, iteration: int | None = None, mutation_hint: str | None = None) → bool

Add a program with parent information for gradient tracking.

This method extends the standard add() by recording the parent→child transition for gradient computation. Use this instead of add() when parent information is available.

Parameters:

• child – The child program to add

• parent – The parent program that was mutated

• island_id – Island to assign the child to

• force_add – If True, bypass population limit enforcement

• iteration – Evolution iteration number

• mutation_hint – Optional description of the mutation applied

Returns:

True if child became an elite (new cell or replaced existing)

get_gradient_at_coords(coords: Tuple[int, int, int, int]) → Tuple[Tuple[float, float, float, float], Dict[str, Any]]

Get gradient estimate at specified behavioral coordinates.

The gradient indicates which direction in optimization space is most likely to yield improvements based on historical transitions.

Parameters:

coords – Behavioral coordinates (memory_opt, compute_opt, parallelism_opt, esimd_opt)

Returns:

• gradient_vector: (d_memory, d_compute, d_parallelism, d_esimd) Positive values suggest increasing that dimension

• metadata_dict: Contains confidence, sample_count, etc.

Return type:

Tuple of (gradient_vector, metadata_dict)

get_mutation_hints_for_parent(parent: Program, max_hints: int = 3) → List[str]

Get mutation hints for a parent program based on gradient information.

These hints can be injected into LLM prompts to guide the direction of optimization.

Parameters:

• parent – The parent program to mutate

• max_hints – Maximum number of hints to return

Returns:

List of human-readable mutation hint strings

get_gradient_weighted_sampling_probabilities(candidate_ids: List[str], strategy: str = 'combined') → Dict[str, float]

Compute sampling probabilities for candidates using gradient information.

Combines standard fitness-based sampling with gradient-informed weights to prioritize parents that historically produce improvements.

Parameters:

• candidate_ids – List of program IDs to consider

• strategy – Gradient weighting strategy: - “improvement_rate”: Weight by historical improvement rate - “gradient_magnitude”: Weight by gradient magnitude - “combined”: Blend of both

Returns:

Dict mapping program_id to sampling probability

get_best_transition_directions_from_parent(parent: Program, top_k: int = 3) → List[Dict[str, Any]]

Get the most successful transition directions from a parent’s cell.

Returns information about which optimization changes historically led to improvements when starting from this parent’s position.

Parameters:

• parent – The parent program

• top_k – Number of directions to return

Returns:

• direction: (d_mem, d_comp, d_par, d_esimd)

• success_rate: Fraction of successful transitions

• sample_count: Number of observations

• description: Human-readable description

Return type:

List of dicts with keys

get_transition_statistics() → Dict[str, Any]

Get comprehensive statistics about evolutionary transitions.

Returns metrics about improvement rates, discovery patterns, and gradient effectiveness.

Returns:

Dict with transition statistics

get_cell_transition_info(coords: Tuple[int, int, int, int]) → Dict[str, Any] | None

Get detailed transition information for a specific cell.

Parameters:

coords – Cell coordinates

Returns:

Dict with cell-specific transition statistics, or None if no data

setup(language: str | None = None, problem_name: str | None = None, gpu_arch: str | None = None, init_programs: List[Program] | None = None, resume_from_archive: str | None = None, resume_from_database: bool = False, max_speedup: float = 1.0, population_filter_fn=None, output_dir: str | None = None, task_id: str | None = None) → List[Program]

Initialize the database with programs. 1. Load initial programs or resume from checkpoint 2. Add all programs to database 3. Initialize diversity reference set (for sampling only)

Parameters:

• language – Output language filter (for backward compatibility, unused)

• problem_name – Problem name filter (for backward compatibility, unused)

• gpu_arch – GPU architecture filter (for backward compatibility, unused)

• init_programs – Initial programs to seed population

• resume_from_archive – Path to checkpoint to resume from

• resume_from_database – Whether to load the database of programs

• population_filter_fn – Optional filter for programs

• output_dir – Output directory for visualizations

• max_speedup – Maximum speedup to consider when loading from database

Returns:

List of programs available for evolution

Note

The language, problem_name, and gpu_arch arguments are accepted for backward compatibility with the controller but are not used in this simplified implementation. The optimization-aware database works with any language/architecture since coordinates come from code patterns.

load_all_programs_from_runs(db_kernels: DataFrame, filter_language: str, filter_problem_name: str, restrict_to_correct: bool = False, verbose: bool = False) → list[Program]

Iterate over all runs we have and select the ones of <filter_problem_id> and <filter_language>. Returns a list of Program objects with their evaluation results.

is_empty() → bool

Check if the database has any programs

sample() → Tuple[Program, List[Program]]

Sample one parent and multiple inspiration programs for evolution.

Uses a three-strategy approach for parent selection:

• EXPLORATION (exploration_ratio): Sample from underexplored regions to discover new optimization strategies

• EXPLOITATION (exploitation_ratio): Sample from elite programs to refine and combine the best solutions

• RANDOM (remaining): Completely random sampling for novelty

Inspirations are sampled from DIFFERENT optimization niches to encourage cross-pollination of optimization strategies.

Returns:

Tuple of (parent_program, inspiration_programs)

Raises:

ValueError – If database is empty and no programs available

get_best_program(island_id: int | None = None) → Program | None

Get the best program globally or from a specific island.

Parameters:

island_id – If provided, return best from this island only

Returns:

Best program or None if database is empty

get_top_programs(n: int = 10, metric: str | None = None, island_idx: int | None = None) → List[Program]

Get the top N programs based on a metric.

This method is essential for the controller to get high-quality inspirations. It can filter by island for island-based evolution strategies.

Parameters:

• n – Number of programs to return

• metric – Metric to use for ranking (uses combined_score if None)

• island_idx – If specified, only return programs from this island

Returns:

List of top programs sorted by score (descending)

get_archive() → List[Program]

Get all elite programs from the feature map.

Uses caching to avoid repeated list construction. Thread-safe with atomic cache operations.

Returns:

List of elite programs (one per occupied cell)

get_all_programs() → List[Program]

Get all programs in the database

property use_islands: bool

Check if island model is enabled

increase_island_counter_and_switch()

Increase counter and switch island if threshold reached

next_island() → int

Move to the next island in round-robin fashion

increment_island_generation(island_idx: int | None = None) → None

Increment generation counter for an island

should_migrate() → bool

Check if migration should occur

migrate_programs(copy_mode: bool = True) → None

Perform migration between islands.

Migrates top programs from each island to the next island (ring topology).

Parameters:

copy_mode – If True (default), programs are COPIED to target island (existing in both source and target). If False, programs are MOVED (removed from source).

Note

Copy mode is generally preferred as it maintains population diversity while still spreading good solutions. Move mode can cause population collapse in source islands.

log_island_status() → None

Log current status of all islands

get_statistics() → Dict[str, Any]

Get database statistics for monitoring.

Returns:

Dict with population stats, archive coverage, etc.

get_grid_statistics() → Dict[str, Any]

Get comprehensive statistics about the MAP-Elites grid.

Returns:

Dictionary with coverage, scores, and dimension-specific stats

save_checkpoint(checkpoint_path: str) → None

Save database state to checkpoint file.

Parameters:

checkpoint_path – Path to save checkpoint

visualize_grid(show_scores: bool = True, save_path: str | None = None, include_esimd: bool = True) → None

Visualize the MAP-Elites grid.

When include_esimd=True (default):

Creates a 4×4 grid of 2D slices (4×4×4×4 total): - Rows: ESIMD optimization levels (0-3) - Columns: Parallelism optimization levels (0-3) - Each cell: 4×4 heatmap of memory_opt × compute_opt

When include_esimd=False:

Creates a 1×4 grid of 2D slices (4×4×4 total): - Columns: Parallelism optimization levels (0-3) - Each cell: 4×4 heatmap of memory_opt × compute_opt

Parameters:

• show_scores – If True, display performance scores in occupied cells

• save_path – Optional path to save the visualization

• include_esimd – If True, include ESIMD as a dimension (default True)

save_grid_visualization(iteration: int | None = None, include_esimd: bool = True) → None

Save MAP-Elites grid visualization to the output directory.

Parameters:

• iteration – Iteration number for filename

• include_esimd – If True, include ESIMD as a dimension (default True)

update_program_metadata(program_id: str, metadata: Dict[str, Any]) → None

Update metadata for a program

get_underexplored_regions(n: int = 5, strategy: str = 'empty_first') → List[Dict[str, int]]

Identify underexplored regions of the optimization space.

Parameters:

• n – Maximum number of regions to return

• strategy – Selection strategy: - “empty_first”: Prioritize completely empty cells - “low_quality”: Include cells with low-performing elites - “balanced”: Mix of empty and low-quality cells

Returns:

List of target optimization profiles for underexplored regions

get_parent_optimization_profile(parent: Program) → Dict[str, int] | None

Extract optimization profile from parent program.

Parameters:

parent – Parent program

Returns:

Dict with memory_opt, compute_opt, parallelism_opt, esimd_opt or None

get_higher_optimization_programs(parent: Program, n: int = 3, dimension: str | None = None) → List[Program]

Get programs with higher optimization levels than the parent.

This is a KEY method for unlocking performance improvements. It finds programs that are more optimized than the current parent and returns them as inspirations/exemplars for the LLM.

Parameters:

• parent – Current parent program

• n – Maximum number of programs to return

• dimension – If specified, only consider this dimension for comparison. Options: “memory_opt”, “compute_opt”, “parallelism_opt”, “esimd_opt” If None, uses the sum of all optimization levels.

Returns:

List of programs at higher optimization levels, sorted by score

get_best_program_at_level(memory_opt: int, compute_opt: int, parallelism_opt: int, esimd_opt: int = 0) → Program | None

Get the best program at a specific optimization level.

Parameters:

• memory_opt – Target memory optimization level (0-3)

• compute_opt – Target compute optimization level (0-3)

• parallelism_opt – Target parallelism optimization level (0-3)

• esimd_opt – Target ESIMD optimization level (0-3)

Returns:

Elite program at that level, or None if cell is empty

refresh_diversity_reference(force: bool = False) → None

Refresh the diversity reference set if population has changed significantly.

The diversity reference set is used for sampling diversity calculations. It should be periodically refreshed as the population evolves to remain representative.

Parameters:

force – If True, always refresh. If False, only refresh if population has changed by more than 20% since last refresh.

validate_coordinates_determinism(sample_size: int = 10) → bool

Validate that coordinate classification is deterministic.

Runs classification twice on a sample of programs and verifies identical results. Useful for debugging and testing.

Parameters:

sample_size – Number of programs to validate

Returns:

True if all sampled programs produce consistent coordinates

class kernelfoundry.algorithm.evolve_database_optimization_aware.OptimizationFeatureClassifier

Classifies kernel optimization levels using static code pattern analysis.

This is the ONLY source of feature coordinates - deterministic and execution-independent. Extracts discrete optimization levels (0-3) from code patterns.

Classification Philosophy

• Each level builds on the previous (Level 2 typically implies Level 1 patterns)

• Classification uses weighted pattern matching with confidence scores

• Patterns are grouped by category to avoid double-counting

• Comments are handled separately to reduce false positives

Dimensions

1. memory_opt: Memory hierarchy exploitation 0 = Naive global, 1 = Coalesced/vectorized, 2 = SLM tiling, 3 = Register blocking + async

2. compute_opt: Algorithmic efficiency 0 = Multi-pass, 1 = Fused operations, 2 = Single-pass/streaming, 3 = Tiled/blocked algorithms

3. parallelism_opt: Parallelism granularity 0 = Thread-only, 1 = Work-group barriers, 2 = Sub-group intrinsics, 3 = Hierarchical

classmethod classify_from_code(code: str, language: str = 'sycl', return_confidence: bool = False) → Tuple[int, int, int, int]

Classify optimization level using static code analysis.

This is the source of truth for feature grid coordinates. Deterministic, stable across runs, immune to execution variations.

Parameters:

• code – Kernel source code

• language – Programming language (“sycl”, “cuda”, “opencl”, “triton”)

• return_confidence – If True, also return confidence scores (deprecated, use classify_with_confidence)

Returns:

Tuple of (memory_opt, compute_opt, parallelism_opt, esimd_opt) each 0-3

classmethod classify_with_confidence(code: str, language: str = 'sycl') → Tuple[Tuple[int, int, int, int], Dict[str, float]]

Classify optimization level and return confidence scores.

Parameters:

• code – Kernel source code

• language – Programming language (“sycl”, “cuda”, “opencl”, “triton”)

Returns:

• coords: (memory_opt, compute_opt, parallelism_opt, esimd_opt) each 0-3

• confidence_dict: {“memory”: float, “compute”: float, “parallelism”: float, “esimd”: float}

Return type:

Tuple of (coords, confidence_dict) where

classmethod get_matched_patterns(code: str, language: str = 'sycl') → Dict[str, Dict[int, List[str]]]

Get detailed breakdown of which patterns matched for debugging.

Parameters:

• code – Source code to analyze

• language – Programming language (“sycl”, “cuda”, “cu”, “opencl”, “ocl”, “cl”)

Returns:

Dict mapping dimension -> level -> list of matched pattern categories

classmethod explain_classification(code: str, language: str = 'sycl') → str

Generate human-readable explanation of classification.

Useful for debugging and understanding why code was classified a certain way.

Parameters:

• code – Source code to analyze

• language – Programming language

Returns:

Formatted string explaining the classification

class kernelfoundry.algorithm.evolve_database_optimization_aware.SamplingMethod(value)

Sampling strategies for program selection.

FITNESS_PROPORTIONAL = 1

UNIFORM = 2

ELITE = 3

ARCHIVE = 4

class kernelfoundry.algorithm.evolve_database_optimization_aware.ExplorationStrategy(value)

Strategies for identifying underexplored regions.

EMPTY_FIRST = 1

LOW_QUALITY = 2

BALANCED = 3

kernelfoundry.algorithm.evolve_database_optimization_aware.deterministic_code_hash(code: str) → int

Compute a deterministic hash of code that is stable across Python runs.

Unlike Python’s built-in hash() which is randomized by PYTHONHASHSEED, this function uses SHA256 to ensure identical code produces identical hashes across different Python processes. Critical for reproducible diversity selection.

Parameters:

code – Source code string to hash

Returns:

Integer hash value (stable across runs)

kernelfoundry.algorithm.evolve_database_optimization_aware.get_main_score(metrics: Dict[str, Any]) → float

Get the main fitness score from metrics dictionary.

This is used for elite selection WITHIN cells, not for coordinate assignment. Requires ‘combined_score’ to be present in metrics.

Parameters:

metrics – Dictionary of performance metrics

Returns:

Fitness score (higher is better)

Raises:

ValueError – If metrics is empty or combined_score is missing