Cache Architecture Ontology

AI SEARCH

FLOW ALGEBRA — CACHE ARCHITECTURE ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/computer-architecture/cache-architecture-ontology.html

FLOW CACHE_ARCHITECTURE_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Computer Architecture"
    ONTOLOGY = "Cache Architecture Ontology"
    PURPOSE = "Formalise cache hierarchy entities, cache lines, mappings, lookup behaviour, replacement, write policies, coherence and performance relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    CACHE_ARCHITECTURE
    CACHE
    INSTRUCTION_CACHE
    DATA_CACHE
    UNIFIED_CACHE
    L1_CACHE
    L2_CACHE
    L3_CACHE
    PRIVATE_CACHE
    SHARED_CACHE
    CPU
    PROCESSOR
    CORE
    MEMORY
    MAIN_MEMORY
    MEMORY_HIERARCHY
    CACHE_LINE
    CACHE_BLOCK
    CACHE_SET
    CACHE_WAY
    TAG
    INDEX
    OFFSET
    ADDRESS
    VIRTUAL_ADDRESS
    PHYSICAL_ADDRESS
    CACHE_ENTRY
    VALID_BIT
    DIRTY_BIT
    COHERENCE_STATE
    CACHE_HIT
    CACHE_MISS
    COMPULSORY_MISS
    CAPACITY_MISS
    CONFLICT_MISS
    COHERENCE_MISS
    REPLACEMENT_POLICY
    LRU_POLICY
    FIFO_POLICY
    RANDOM_POLICY
    WRITE_POLICY
    WRITE_THROUGH
    WRITE_BACK
    WRITE_ALLOCATE
    NO_WRITE_ALLOCATE
    PREFETCHER
    PREFETCH
    EVICTION
    FILL
    MEMORY_REQUEST
    READ_REQUEST
    WRITE_REQUEST
    COHERENCE_PROTOCOL
    SNOOP
    DIRECTORY
    LATENCY
    BANDWIDTH
    HIT_RATE
    MISS_RATE
    CACHE_SIZE
    LINE_SIZE
    ASSOCIATIVITY
    STATE
    EVENT
    CONFIGURATION
    VERSION
    PERFORMANCE_METRIC
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    HAS_CACHE
    HAS_LEVEL
    HAS_LINE
    HAS_SET
    HAS_WAY
    HAS_TAG
    HAS_INDEX
    HAS_OFFSET
    MAPS_TO
    LOOKS_UP
    HITS_IN
    MISSES_IN
    FILLS
    EVICTS
    REPLACES
    PREFETCHES
    READS_FROM
    WRITES_TO
    FORWARDS_TO
    RECEIVES_FROM
    COHERENT_WITH
    INVALIDATES
    UPDATES
    SNOOPS
    HAS_STATE
    TRANSITIONS_TO
    HAS_REPLACEMENT_POLICY
    HAS_WRITE_POLICY
    HAS_COHERENCE_PROTOCOL
    HAS_SIZE
    HAS_LINE_SIZE
    HAS_ASSOCIATIVITY
    HAS_HIT_RATE
    HAS_MISS_RATE
    HAS_LATENCY
    HAS_BANDWIDTH
    HAS_CONFIGURATION
    HAS_VERSION
    DEPENDS_ON
    PRECEDES
    FOLLOWS
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    CACHE_SPECIFICATIONS
    CACHE_HIERARCHIES
    CACHE_SIZES
    LINE_SIZES
    ASSOCIATIVITY_DATA
    ADDRESS_TRACES
    MEMORY_ACCESS_TRACES
    REPLACEMENT_POLICIES
    WRITE_POLICIES
    COHERENCE_PROTOCOLS
    PREFETCHER_DEFINITIONS
    PERFORMANCE_COUNTERS
    LATENCY_METRICS
    BANDWIDTH_METRICS
    CONFIGURATION_DATA
    VERSION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_CACHE_IDENTIFIERS
    NORMALISE_CACHE_LEVEL_NAMES
    NORMALISE_MEMORY_UNITS
    NORMALISE_LINE_SIZES
    NORMALISE_ASSOCIATIVITY
    NORMALISE_ADDRESS_FORMATS
    NORMALISE_REPLACEMENT_POLICY_NAMES
    NORMALISE_WRITE_POLICY_NAMES
    NORMALISE_COHERENCE_STATE_NAMES
    NORMALISE_LATENCY_UNITS
    NORMALISE_BANDWIDTH_UNITS
    NORMALISE_VERSION_IDENTIFIERS
    RESOLVE_CACHE_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS CACHE_ACCESS_PIPELINE {
    MEMORY_REQUEST
      -> ADDRESS_DECOMPOSITION
      -> CACHE_LEVEL_LOOKUP
      -> TAG_COMPARISON
      -> HIT_OR_MISS
      -> DATA_RETURN_OR_NEXT_LEVEL_REQUEST
      -> CACHE_STATE_UPDATE
  }

  PROCESS ADDRESS_MAPPING {
    ADDRESS
      -> TAG
      + INDEX
      + OFFSET

    INDEX
      -> CACHE_SET

    CACHE_SET
      -> CANDIDATE_WAYS

    TAG + CANDIDATE_WAYS
      -> MATCH_CHECK

    MATCH_CHECK
      -> HIT_OR_MISS
  }

  PROCESS CACHE_HIT_REASONING {
    VALID_TAG_MATCH
      -> CACHE_HIT

    CACHE_HIT
      -> CACHE_LINE_ACCESS

    CACHE_LINE_ACCESS
      -> REQUESTED_DATA

    REQUESTED_DATA
      -> PROCESSOR_OR_REQUESTER
  }

  PROCESS CACHE_MISS_REASONING {
    NO_VALID_TAG_MATCH
      -> CACHE_MISS

    CACHE_MISS
      -> NEXT_CACHE_LEVEL_OR_MEMORY

    NEXT_CACHE_LEVEL_OR_MEMORY
      -> DATA_RETURN

    DATA_RETURN
      -> CACHE_FILL

    CACHE_FILL
      -> REPLACEMENT_IF_REQUIRED
      -> REQUESTER
  }

  PROCESS REPLACEMENT_REASONING {
    CACHE_SET_IS_FULL + CACHE_FILL
      -> REPLACEMENT_POLICY

    REPLACEMENT_POLICY
      -> VICTIM_LINE_SELECTION

    VICTIM_LINE_SELECTION
      -> DIRTY_CHECK

    DIRTY_LINE
      -> WRITEBACK_IF_POLICY_REQUIRES

    VICTIM_LINE_SELECTION
      -> EVICTION
      -> NEW_LINE_INSTALLATION
  }

  PROCESS WRITE_REASONING {
    WRITE_REQUEST
      -> CACHE_LOOKUP

    CACHE_HIT
      -> APPLY_WRITE_POLICY

    WRITE_THROUGH
      -> UPDATE_CACHE
      -> UPDATE_NEXT_MEMORY_LEVEL

    WRITE_BACK
      -> UPDATE_CACHE
      -> SET_DIRTY_BIT

    CACHE_MISS
      -> WRITE_ALLOCATE_OR_NO_WRITE_ALLOCATE
  }

  PROCESS COHERENCE_REASONING {
    SHARED_MEMORY_BLOCK + MULTIPLE_CACHES
      -> COHERENCE_TRACKING

    READ_OR_WRITE_EVENT
      -> COHERENCE_PROTOCOL_TRANSITION

    COHERENCE_PROTOCOL_TRANSITION
      -> INVALIDATE_OR_UPDATE_OR_SHARE

    RESULT
      -> NEW_COHERENCE_STATES
  }

  PROCESS PREFETCH_REASONING {
    ACCESS_PATTERN
      -> PREFETCH_PREDICTION

    PREFETCH_PREDICTION
      -> PREFETCH_REQUEST

    PREFETCH_REQUEST
      -> CACHE_FILL

    LATER_ACCESS
      -> USEFUL_OR_UNUSED_PREFETCH
  }

  PROCESS PERFORMANCE_REASONING {
    CACHE + WORKLOAD + CONFIGURATION
      -> CACHE_PROFILE

    CACHE_PROFILE
      -> HIT_RATE
      -> MISS_RATE
      -> MISS_CLASSIFICATION
      -> AVERAGE_ACCESS_LATENCY
      -> BANDWIDTH_USAGE
      -> PREFETCH_EFFECTIVENESS

    CACHE_PROFILE
      -> BOTTLENECK_HYPOTHESIS
  }

  RULES {
    IF CACHE_ACCESS_OCCURS
    THEN REQUIRE {
      ADDRESS
      CACHE_LEVEL
      ACCESS_TYPE
      CONFIGURATION_CONTEXT
    }

    IF CACHE_HIT_OCCURS
    THEN REQUIRE VALID_TAG_MATCH

    IF CACHE_MISS_OCCURS
    THEN TRACE_REQUEST_TO_NEXT_LEVEL_OR_MEMORY

    IF DIRTY_LINE_IS_EVICTED
    AND WRITE_POLICY == WRITE_BACK
    THEN REQUIRE WRITEBACK

    IF CACHE_IS_SHARED
    THEN PRESERVE SHARING_AND_COHERENCE_CONTEXT

    IF SAME_ADDRESS_IS_USED
    THEN DO_NOT_ASSUME_SAME_CACHE_MAPPING_WITHOUT_CONFIGURATION_CONTEXT

    IF HIT_RATE_IS_COMPARED
    THEN REQUIRE WORKLOAD_AND_CACHE_CONFIGURATION

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND CACHE_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        CACHE_SPECIFICATION_COMPLETENESS,
        ADDRESS_TRACE_QUALITY,
        CONFIGURATION_CERTAINTY,
        POLICY_CERTAINTY,
        COHERENCE_MODEL_CERTAINTY,
        TRACE_COMPLETENESS,
        PERFORMANCE_COUNTER_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF CACHE_CONFIGURATION_IS_UNKNOWN
    THEN REDUCE_MAPPING_AND_PERFORMANCE_CONFIDENCE

    IF COHERENCE_PROTOCOL_IS_UNKNOWN
    THEN REDUCE_MULTICORE_STATE_CONFIDENCE

    IF REPRODUCIBLE_TRACE_CONFIRMS_CACHE_BEHAVIOUR
    THEN INCREASE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        CANONICAL_IDENTIFIER,
        CACHE_LEVEL,
        CACHE_SIZE,
        LINE_SIZE,
        ASSOCIATIVITY,
        POLICY_CONTEXT,
        VERSION
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    CACHE != MAIN_MEMORY
    CACHE_LINE != MEMORY_ADDRESS
    CACHE_HIT != GUARANTEED_LOW_LATENCY_WITHOUT_CONTEXT
    CACHE_MISS != MAIN_MEMORY_ACCESS_IF_LOWER_CACHE_EXISTS
    HIT_RATE_IS_WORKLOAD_DEPENDENT
    MISS_RATE_IS_WORKLOAD_DEPENDENT
    CACHE_MAPPING_IS_CONFIGURATION_DEPENDENT
    REPLACEMENT_POLICY_AFFECTS_BEHAVIOUR
    WRITE_POLICY_AFFECTS_MEMORY_TRAFFIC
    PREFETCH != DEMAND_ACCESS
    PREFETCH_HIT != NECESSARILY_USEFUL_PREFETCH
    COHERENCE_STATE != CACHE_VALIDITY_ALONE
    VIRTUAL_AND_PHYSICAL_ADDRESSING_CONTEXT_MUST_BE_PRESERVED
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_CACHE_IDENTIFIER
    CHECK_CACHE_LEVEL
    CHECK_CACHE_SIZE
    CHECK_LINE_SIZE
    CHECK_ASSOCIATIVITY
    CHECK_ADDRESS_MAPPING
    CHECK_TAG_AND_VALIDITY
    CHECK_REPLACEMENT_POLICY
    CHECK_WRITE_POLICY
    CHECK_COHERENCE_PROTOCOL
    CHECK_PREFETCH_RELATIONS
    CHECK_ACCESS_TRACE
    CHECK_PERFORMANCE_CONTEXT
    CHECK_CONFIGURATION
    CHECK_VERSION_CONTEXT
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_CACHE_ENTITIES
    CACHE_HIERARCHY_RELATIONS
    ADDRESS_MAPPING_RELATIONS
    CACHE_LINE_RELATIONS
    HIT_AND_MISS_RELATIONS
    MISS_CLASSIFICATIONS
    REPLACEMENT_RELATIONS
    WRITE_POLICY_RELATIONS
    COHERENCE_RELATIONS
    PREFETCH_RELATIONS
    CACHE_STATE_TRANSITIONS
    ACCESS_TRACES
    PERFORMANCE_PROFILES
    BOTTLENECK_HYPOTHESES
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON CACHE_OR_CONFIGURATION_CHANGE {
      NORMALISE
      ENTITY_RESOLUTION
      UPDATE_CACHE_HIERARCHY
      UPDATE_ADDRESS_MAPPING
      UPDATE_REPLACEMENT_POLICY
      UPDATE_WRITE_POLICY
      UPDATE_COHERENCE_MODEL
      UPDATE_PREFETCHER_MODEL
      RECOMPUTE_AFFECTED_RELATIONS
      UPDATE_CONFIDENCE
      PRESERVE_VERSION_HISTORY
    }

    ON NEW_ACCESS_OR_PERFORMANCE_DATA {
      LINK_EVIDENCE
      UPDATE_ACCESS_TRACE
      UPDATE_HIT_MISS_PROFILE
      UPDATE_PREFETCH_PROFILE
      UPDATE_COHERENCE_STATE
      REASSESS_BOTTLENECKS
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_CACHE
      BY_CACHE_LEVEL
      BY_ADDRESS
      BY_CACHE_LINE
      BY_SET
      BY_WAY
      BY_HIT
      BY_MISS
      BY_REPLACEMENT_POLICY
      BY_WRITE_POLICY
      BY_COHERENCE_STATE
      BY_PREFETCH
      BY_PERFORMANCE
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_CACHE_ACCESS
      TRACE_ADDRESS_MAPPING
      ANALYSE_HITS_AND_MISSES
      ANALYSE_REPLACEMENT
      ANALYSE_WRITE_POLICY
      ANALYSE_COHERENCE
      ANALYSE_PREFETCHING
      ANALYSE_PERFORMANCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_CACHE_FROM_MAIN_MEMORY
      DISTINGUISH_DEMAND_FROM_PREFETCH_ACCESS
      PRESERVE_CACHE_CONFIGURATION_AND_WORKLOAD_CONTEXT
      PRESERVE_ADDRESSING_CONTEXT
      PRESERVE_COHERENCE_CONTEXT
      DISTINGUISH_THEORETICAL_FROM_OBSERVED_PERFORMANCE
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_CACHE_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              CACHE_ARCHITECTURE_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW