241 lines
12 KiB
C
241 lines
12 KiB
C
/*
|
||
StarForth — Steady-State Virtual Machine Runtime
|
||
|
||
Copyright (c) 2023–2025 Robert A. James
|
||
All rights reserved.
|
||
|
||
This file is part of the StarForth project.
|
||
|
||
Licensed under the StarForth License, Version 1.0 (the "License");
|
||
you may not use this file except in compliance with the License.
|
||
|
||
You may obtain a copy of the License at:
|
||
https://github.com/star.4th@proton.me/StarForth/LICENSE.txt
|
||
|
||
This software is provided "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
||
express or implied, including but not limited to the warranties of
|
||
merchantability, fitness for a particular purpose, and noninfringement.
|
||
|
||
See the License for the specific language governing permissions and
|
||
limitations under the License.
|
||
|
||
*/
|
||
|
||
#ifndef COMPUDYNAMICS_H
|
||
#define COMPUDYNAMICS_H
|
||
|
||
#include <stdint.h>
|
||
|
||
/* ============================================================================
|
||
* Compudynamics: Generic Entity-Agnostic Physics Engine
|
||
* ============================================================================
|
||
*
|
||
* Four operational levels observe and adapt to their own execution history:
|
||
* - words (dictionary entries, driven by ssm_jacquard.c) -- LIVE
|
||
* - VMs (Tripod fleet, driven by capsule_vm_physics.c) -- reserved
|
||
* - blocks (Artemis block storage) -- reserved
|
||
* - messages (Hermes event routing) -- reserved
|
||
*
|
||
* This module provides the entity-agnostic machinery shared by all four:
|
||
* a deterministic regime classifier over an entity-ID touch history, and a
|
||
* generic UCB1 bandit over a caller-sized config space. "Entity-ID" means
|
||
* whatever the level touches -- word_id for words, vm_id for VMs, block
|
||
* LBN for blocks, message type for messages.
|
||
*
|
||
* Determinism is the entire point of this module. Every input is an
|
||
* execution count or an entity-ID sequence -- never a wall-clock timestamp,
|
||
* never a duration. Two architectures executing the same instruction
|
||
* sequence at different real speeds (e.g. QEMU/TCG amd64 vs aarch64) must
|
||
* produce byte-identical classifier output. This was violated once
|
||
* (ssm_jacquard.c's temporal_decay input, derived from a wall-clock-tainted
|
||
* decay slope) and broke cross-architecture dict_hash parity; this module
|
||
* exists so that mistake has nowhere to hide the second time.
|
||
*
|
||
* Word-level and VM-level are the only two levels with real, instantiated
|
||
* CDTuning constants today (CD_TUNING_WORD, CD_TUNING_VM). Only word-level
|
||
* is actually wired through this module (ssm_jacquard.c); VM-level's own
|
||
* fleet mechanism (capsule_vm_physics.c, VMFleetWindow) is a separate,
|
||
* already-validated, already-accepted design that legitimately depends on
|
||
* real elapsed time for its rate-recovery math (fleet_transfer_slope_q48)
|
||
* and is out of scope here. CD_TUNING_VM documents what this module's
|
||
* classifier-side parameters would be if VM-level regime classification
|
||
* were ever migrated onto it; its bandit-side fields are zeroed and
|
||
* unused because VM level has no config-space bandit today. Block and
|
||
* message levels have no Artemis/Hermes compudynamics implementation yet
|
||
* -- CD_TUNING_BLOCK and CD_TUNING_MESSAGE are deliberately not defined
|
||
* here rather than filled with invented numbers.
|
||
* ============================================================================
|
||
*/
|
||
|
||
/* Hard cap on how many recent entity-ID touches cd_classify_ids() will look
|
||
* at. Callers pass a shorter slice via count; this cap bounds the classifier's
|
||
* O(depth^2) worst case and the stack scratch space it uses internally. */
|
||
#define CD_MAX_CLASSIFY_DEPTH 64u
|
||
|
||
/* ============================================================================
|
||
* Deterministic Regime Classification
|
||
* ============================================================================
|
||
*/
|
||
|
||
typedef struct {
|
||
uint32_t diversity_q16; /* distinct IDs in window / window size, Q16 [0,65536] */
|
||
uint32_t volatility_q16; /* dispersion (coefficient of variation) of per-ID
|
||
* touch counts within the window, Q16, unclamped
|
||
* above 65536 is possible and meaningful (high CV) */
|
||
uint32_t locality_q16; /* fraction of touches that repeat an ID seen within
|
||
* the preceding locality_lookback touches, Q16 [0,65536] */
|
||
} CDRegimeMetrics;
|
||
|
||
/**
|
||
* @brief Classify a recent entity-ID touch sequence into diversity/volatility/
|
||
* locality, purely from execution counts -- no wall-clock input anywhere.
|
||
*
|
||
* @param ids Recent entity IDs, oldest first, chronological order
|
||
* @param count Number of valid entries in ids (clamped internally
|
||
* to CD_MAX_CLASSIFY_DEPTH)
|
||
* @param locality_lookback How many preceding touches count as "recent" for
|
||
* the locality measure (clamped to count)
|
||
* @return Classified regime metrics; all-zero if count == 0
|
||
*/
|
||
CDRegimeMetrics cd_classify_ids(const uint32_t *ids, uint32_t count,
|
||
uint32_t locality_lookback);
|
||
|
||
/* ============================================================================
|
||
* Per-Level Tuning Knobs
|
||
* ============================================================================
|
||
*/
|
||
|
||
typedef struct {
|
||
/* --- Classifier knobs (used by cd_classify_ids callers) --- */
|
||
uint32_t id_window_depth; /* touches to classify over, <= CD_MAX_CLASSIFY_DEPTH */
|
||
uint32_t locality_lookback; /* recurrence lookback within id_window_depth */
|
||
uint32_t diversity_high_threshold_q16;
|
||
uint32_t volatility_high_threshold_q16;
|
||
uint32_t locality_high_threshold_q16;
|
||
|
||
/* --- Bandit knobs (used by cd_config_table_*); 0 where the level has
|
||
* no config-space bandit (e.g. VM level today -- see file header) --- */
|
||
uint32_t num_configs; /* size of the config space, e.g. 128 */
|
||
uint32_t num_regimes; /* size of the regime space, e.g. 8 */
|
||
uint32_t score_max;
|
||
uint32_t score_min;
|
||
uint32_t score_decay_factor_q16; /* per-tick exponential decay of benefit_score */
|
||
uint32_t ucb_k; /* UCB1 exploration coefficient */
|
||
uint32_t reward_gain; /* max per-tick score delta magnitude */
|
||
uint32_t joint_weight_q16; /* weight of window/locality joint-convergence
|
||
* signal in the combined reward, Q16 */
|
||
uint32_t anova_weight_q16; /* weight of the caller-supplied stability
|
||
* signal (e.g. ANOVA early-exit) in the
|
||
* combined reward, Q16 */
|
||
} CDTuning;
|
||
|
||
/* Tuning knobs are returned by value, not exposed as addressable globals.
|
||
* This freestanding kernel's boot-time loader does not reliably relocate
|
||
* the address of an extern const aggregate referenced from a different
|
||
* translation unit (confirmed by direct QEMU/gdb-style fault tracing:
|
||
* &CD_TUNING_WORD-style access faulted on an unrelocated pointer, while
|
||
* cross-TU function calls -- including struct-return-by-value, which
|
||
* uses a caller-local hidden pointer, never a global's address --
|
||
* worked correctly). Every existing scalar tunable elsewhere in this
|
||
* codebase already avoids this by being a #define immediate rather than
|
||
* a referenced global; these accessors are the aggregate-typed
|
||
* equivalent of that same constraint. */
|
||
|
||
/* Word level (ssm_jacquard.c): 128 configs (7-bit L1-L7), 8 regimes
|
||
* (3-bit diversity/volatility/locality). Values match the constants
|
||
* ssm_jacquard.c/.h used before this module existed -- this is a lift,
|
||
* not a retune. */
|
||
CDTuning cd_tuning_word(void);
|
||
|
||
/* VM level (capsule_vm_physics.c): classifier-side parameters only, for a
|
||
* future migration off Hera's word-level regime proxy. Not consumed by
|
||
* any call site today -- see file header. Bandit fields are zero: VM
|
||
* level modulates a continuous multiplier (fleet_transfer_slope_q48)
|
||
* rather than selecting from a discrete config space. */
|
||
CDTuning cd_tuning_vm(void);
|
||
|
||
/* ============================================================================
|
||
* Generic UCB1 Config-Space Bandit
|
||
* ============================================================================
|
||
*
|
||
* Stratified by regime: each (regime, config) pair has its own benefit
|
||
* score and tick count, so the bandit learns "best config per regime"
|
||
* rather than one global best. One clock only: cd_config_table_tick()
|
||
* scores the currently-active config and reselects on every call -- no
|
||
* derived multi-tick batching unit exists anywhere in this mechanism.
|
||
* ============================================================================
|
||
*/
|
||
|
||
typedef struct {
|
||
uint8_t config_bits;
|
||
uint8_t has_prev; /* 1 once prev_window/prev_locality_q16 hold real data */
|
||
uint8_t _pad[2];
|
||
uint32_t benefit_score;
|
||
uint32_t tick_count;
|
||
uint32_t prev_window;
|
||
uint32_t prev_locality_q16;
|
||
} CDConfigEntry;
|
||
|
||
typedef struct {
|
||
CDConfigEntry *entries; /* num_configs entries, malloc'd */
|
||
uint32_t *regime_scores; /* num_regimes * num_configs, row-major [regime][config] */
|
||
uint32_t *regime_ticks; /* same shape as regime_scores */
|
||
uint32_t *total_regime_ticks; /* num_regimes entries */
|
||
uint32_t num_configs;
|
||
uint32_t num_regimes;
|
||
uint8_t current_config;
|
||
uint8_t current_regime;
|
||
} CDConfigTable;
|
||
|
||
/**
|
||
* @brief Allocate a config table sized for tuning->num_configs / num_regimes.
|
||
* @return 0 on success, -1 on malloc failure (table left zeroed, unusable)
|
||
*/
|
||
int cd_config_table_init(CDConfigTable *table, const CDTuning *tuning);
|
||
|
||
/**
|
||
* @brief Free all memory owned by a config table. Safe on a zeroed table.
|
||
*/
|
||
void cd_config_table_free(CDConfigTable *table);
|
||
|
||
/**
|
||
* @brief Seed every (regime, config) score with initial_scores[config], and
|
||
* set the starting active config to initial_config.
|
||
* @param initial_scores Array of tuning->num_configs initial benefit scores
|
||
*/
|
||
void cd_config_table_seed(CDConfigTable *table, const CDTuning *tuning,
|
||
const uint32_t *initial_scores, uint8_t initial_config);
|
||
|
||
/**
|
||
* @brief Score the currently-active config from this tick's outcome and
|
||
* UCB1-reselect this tick's config, for the given regime.
|
||
*
|
||
* Combined reward = joint_weight * window/locality-convergence-stability
|
||
* + anova_weight * anova_stability_q16
|
||
* Joint-convergence is skipped (falls back to ANOVA-only) on a config's
|
||
* first tick, or when use_joint_convergence is false (the caller's config
|
||
* bits don't include loops whose convergence this signal is meant to
|
||
* track -- word level's L5/L6, see ssm_jacquard.c).
|
||
*
|
||
* @param table Config table (must be initialised)
|
||
* @param tuning Tuning knobs matching this table's sizing
|
||
* @param regime Current regime index, < tuning->num_regimes
|
||
* @param anova_stability_q16 Caller-supplied stability signal, Q16 [0,65536]
|
||
* @param use_joint_convergence Whether to include the window/locality signal
|
||
* @param current_window Caller's current window-width metric
|
||
* @param current_locality_q16 Caller's current locality_q16 from cd_classify_ids
|
||
* @return The newly-selected config's config_bits
|
||
*/
|
||
uint8_t cd_config_table_tick(CDConfigTable *table, const CDTuning *tuning,
|
||
uint8_t regime, uint32_t anova_stability_q16,
|
||
int use_joint_convergence,
|
||
uint32_t current_window, uint32_t current_locality_q16);
|
||
|
||
/**
|
||
* @brief Force the table onto an externally-chosen config (as if UCB1 had
|
||
* picked it). One-tick nudge, not a hold -- see ssm_l8_force_config().
|
||
*/
|
||
void cd_config_table_force(CDConfigTable *table, uint8_t config_idx);
|
||
|
||
#endif /* COMPUDYNAMICS_H */
|