SIMD Ontology

FLOW ALGEBRA
SIMD Ontology
Kireth Semantic Research Archive

PAGE:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/high-performance-computing/simd-ontology.html

AUTHORS:
Mark Anthony Higgins — Sky (Recursive AI)

FLOW "SIMDOntology" v4.0

# ---------- DOMAIN ----------
DOMAIN := ComputingOntology
SUBDOMAIN := HighPerformanceComputing
ONTOLOGY := SIMDOntology

# ---------- PRIMARY ENTITY ----------
ENTITY SIMD {
    definition:
        "Single Instruction, Multiple Data is a parallel execution model in
         which one instruction applies the same operation concurrently to
         multiple data elements using multiple processing lanes.";

    objectives: [
        DataParallelism,
        Throughput,
        ReducedInstructionOverhead,
        VectorisedExecution,
        EfficientNumericalProcessing
    ];
}

# ---------- CORE ENTITIES ----------
SIMDEntity := {
    SIMDInstruction,
    SIMDRegister,
    SIMDVector,
    SIMDLane,
    DataElement,
    ProcessingElement
};

SIMDOperation := {
    Add,
    Subtract,
    Multiply,
    Divide,
    Compare,
    LogicalOperation,
    Load,
    Store,
    Shuffle,
    Reduction
};

SIMDProperty := {
    SIMDWidth,
    ElementWidth,
    LaneCount,
    Throughput,
    Latency,
    Alignment
};

# ---------- FUNDAMENTAL RELATIONSHIPS ----------
SIMDInstruction OPERATES_ON SIMDVector;
SIMDVector CONSISTS_OF DataElement;
SIMDRegister STORES SIMDVector;
SIMDLane PROCESSES DataElement;
SIMDInstruction EXECUTES_ACROSS MultipleSIMDLanes;
ProcessingElement MAY_SUPPORT SIMDInstruction;

# ---------- SIMD EXECUTION ----------
SIMDInstruction ->
    LoadOperands
    -> BroadcastInstruction
    -> ExecuteAcrossLanes
    -> ProduceMultipleResults
    -> StoreResults;

SingleInstruction CONTROLS MultipleDataOperations;

# ---------- SIMD VECTOR ----------
SIMDVector :=
    ordered_sequence(
        Element_0,
        Element_1,
        ...,
        Element_n
    );

SIMDWidth :=
    NumberOfBitsOrElementsProcessedBySIMDInstruction;

ElementCount :=
    SIMDRegisterWidth / ElementWidth;

# ---------- SIMD REGISTER ----------
SIMDRegister :=
    RegisterHoldingMultipleDataElements;

SIMDRegister HAS {
    RegisterWidth,
    ElementType,
    ElementCount
};

SIMDInstruction READS SIMDRegister;
SIMDInstruction WRITES SIMDRegister;

# ---------- SIMD LANE ----------
SIMDLane :=
    ParallelExecutionPathForOneOrMoreDataElements;

SIMDInstruction APPLIES SameOperationAcross SIMDLane;

IF AllLanesActive
THEN LaneUtilisation := HIGH;

# ---------- DATA PARALLELISM ----------
SIMDDataParallelism :=
    PartitionDataIntoVectors
    -> ApplySameInstruction
    -> ProcessElementsConcurrently;

IF SameOperationRequiredAcrossManyIndependentElements
THEN SIMDSuitability := HIGH;

# ---------- SIMD ADDITION ----------
SIMDAdd(A,B) :=
    C WHERE
    C[i] = A[i] + B[i];

SIMDAdd EXECUTES Elementwise;

# ---------- SIMD MULTIPLICATION ----------
SIMDMultiply(A,B) :=
    C WHERE
    C[i] = A[i] * B[i];

SIMDMultiply EXECUTES Elementwise;

# ---------- SIMD LOAD ----------
SIMDLoad :=
    Memory
    -> ReadMultipleElements
    -> SIMDRegister;

SIMDStore :=
    SIMDRegister
    -> WriteMultipleElements
    -> Memory;

MemoryAccessPattern AFFECTS SIMDPerformance;

# ---------- ALIGNED ACCESS ----------
AlignedSIMDAccess :=
    MemoryAddressAlignedToPreferredHardwareBoundary;

AlignedAccess MAY_IMPROVE EfficiencyOnSomeArchitectures;

UnalignedAccess MAY_REQUIRE AdditionalHandling;

# ---------- CONTIGUOUS ACCESS ----------
ContiguousAccess :=
    AdjacentElementsLoadedIntoSIMDRegister;

ContiguousAccess MAY_SUPPORT EfficientMemoryTransfer;

# ---------- GATHER ----------
SIMDGather :=
    ReadElementsFromNonContiguousAddresses
    -> SIMDRegister;

Gather MAY_SUPPORT IrregularDataStructures;
Gather MAY_HAVE HigherCostThanContiguousLoad;

# ---------- SCATTER ----------
SIMDScatter :=
    SIMDRegister
    -> WriteElementsToNonContiguousAddresses;

Scatter MAY_HAVE HigherCostThanContiguousStore;

# ---------- MASKING ----------
SIMDMask :=
    BooleanLaneSelection;

MaskedSIMDOperation :=
    ExecuteOnlyOnLanesWhereMaskIsTrue;

Mask MAY_SUPPORT ConditionalDataParallelExecution;

IF ManyMaskLanesInactive
THEN EffectiveSIMDUtilisation := DECREASE;

# ---------- SHUFFLE / PERMUTE ----------
SIMDShuffle :=
    RearrangeElementsWithinOrAcrossSIMDRegisters;

Shuffle MAY_SUPPORT {
    DataReorganisation,
    Reduction,
    NeighbourOperations
};

ShuffleCost DEPENDS_ON ArchitectureAndPattern;

# ---------- REDUCTION ----------
SIMDReduction :=
    CombineMultipleVectorElements
    -> ScalarOrSmallerVector;

Reduction MAY_INCLUDE {
    Sum,
    Minimum,
    Maximum,
    LogicalReduction
};

Reduction MAY_REQUIRE MultipleStages;

# ---------- VECTORIZATION ----------
SIMDVectorization :=
    ConvertScalarOperations
    -> SIMDInstructions;

Vectorization MAY_BE {
    CompilerAutoVectorization,
    ManualSIMDProgramming
};

Loop MAY_BE SIMDVectorizable IF {
    IterationsIndependent,
    DataTypesSupported,
    MemoryAccessCompatible
};

# ---------- LOOP DEPENDENCY ----------
LoopCarriedDependency :=
    Iteration(i) DEPENDS_ON Iteration(i-1);

IF LoopCarriedDependency EXISTS
THEN SIMDVectorization MAY_BE Restricted;

# ---------- TAIL PROCESSING ----------
TailElements :=
    RemainingElementsNotFillingFullSIMDVector;

TailHandling MAY_USE {
    ScalarCleanup,
    MaskedSIMD,
    SmallerVectorOperation
};

# ---------- BRANCHING ----------
DataDependentBranch MAY_CREATE DifferentOperationsAcrossElements;

SIMDExecution PREFERS UniformOperationAcrossLanes;

IF BranchBehaviourHighlyDivergent
THEN SIMDEfficiency MAY_DECREASE;

# ---------- SIMD VS SISD ----------
SISD :=
    SingleInstructionSingleData;

SIMD :=
    SingleInstructionMultipleData;

SIMD CAN_PROCESS MultipleElementsPerInstruction;
SISD TYPICALLY_PROCESSES OnePrimaryElementPerInstruction;

# ---------- SIMD VS MIMD ----------
MIMD :=
    MultipleInstructionMultipleData;

SIMD USES CommonInstructionAcrossDataLanes;
MIMD ALLOWS IndependentInstructionStreams;

SIMD != MIMD;

# ---------- VECTOR PROCESSING RELATIONSHIP ----------
VectorProcessing AND SIMD ARE CloselyRelatedDataParallelModels;

SIMDInstruction MAY_BE A VectorInstruction;

VectorArchitecture MAY_SUPPORT VariableOrLongerVectorSemantics;
SIMDArchitecture MAY_HAVE FixedHardwareVectorWidth;

# ---------- PERFORMANCE ----------
SIMDSpeedup :=
    ScalarExecutionTime
    / SIMDExecutionTime;

SIMDThroughput :=
    ElementsProcessed / Time;

SIMDEfficiency :=
    UsefulActiveLaneWork
    / AvailableLaneCapacity;

# ---------- MEMORY BANDWIDTH ----------
SIMDWorkload MAY_BE MemoryBound;

ArithmeticIntensity :=
    ArithmeticOperations / BytesTransferred;

IF MemoryBandwidthSaturated
THEN AdditionalSIMDCompute MAY_NOT IncreasePerformance;

# ---------- INSTRUCTION SET ----------
SIMDInstructionSet :=
    SET_OF(HardwareSIMDInstructions);

InstructionSet MAY_SUPPORT MultipleElementTypesAndWidths;

Compiler MAY_TARGET SIMDInstructionSet;

# ---------- APPLICATIONS ----------
SIMD MAY_ACCELERATE {
    LinearAlgebra,
    ImageProcessing,
    SignalProcessing,
    Multimedia,
    ScientificComputing,
    Cryptography,
    MachineLearning,
    StatisticalComputation
};

# ---------- SEMANTIC REASONING ----------
IF SameInstructionAppliedToIndependentDataElements
THEN SIMDClassification := supported;

IF LoopIterationsIndependent
AND MemoryAccessRegular
THEN AutoVectorizationPotential := increase;

IF SIMDWidthIncreases
AND WorkloadHasEnoughParallelData
THEN PotentialThroughput := increase;

IF ManyLanesInactive
THEN SIMDEfficiency := decrease;

IF GatherScatterDominates
THEN MemoryAccessCost := increase;

IF TailElementsSmall
THEN TailOverhead MAY_BE low;

IF LoopDependencyExists
THEN SIMDParallelism := restricted;

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE {
    "SIMD" ~= "single instruction multiple data";
    "SIMD processing" ~= "SIMD execution";
    "SIMD vector" ~= "packed data vector";
    "SIMD lane" ~= "vector lane" WHEN context == SIMD;
    "SIMD register" ~= "vector register" WHEN context == fixed_width_SIMD;
    "SIMD vectorization" ~= "SIMD vectorisation";
    "packed instruction" ~= "SIMD instruction" WHEN context == data_parallel_execution;
    "masked SIMD" ~= "predicated SIMD";
}

# ---------- QUERY FLOW ----------
QUERY(q) ->
    NORMALISE(q) ->
    IDENTIFY_SIMD_ENTITY(q) ->
    IDENTIFY_SIMD_OPERATION(q) ->
    IDENTIFY_VECTOR_WIDTH(q) ->
    IDENTIFY_MEMORY_ACCESS(q) ->
    IDENTIFY_MASKING(q) ->
    IDENTIFY_DEPENDENCIES(q) ->
    IDENTIFY_PERFORMANCE(q) ->
    MAP_TO_ONTOLOGY(q) ->
    APPLY_REASONING(q) ->
    SCORE_CONFIDENCE(q) ->
    RETURN_RELEVANT_KNOWLEDGE;

# ---------- CONFIDENCE ----------
CONFIDENCE(assertion) :=
    weighted_mean(
        source_reliability,
        architecture_consistency,
        computational_consistency,
        semantic_consistency,
        evidence_strength,
        contextual_relevance
    );

CONFIDENCE >= 0.90 => HIGH;
CONFIDENCE >= 0.70 AND < 0.90 => MODERATE;
CONFIDENCE < 0.70 => REVIEW;

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION {
    primary_entity: SIMD;
    ontology: SIMDOntology;
    parse_entities: true;
    parse_relationships: true;
    preserve_relationship_direction: true;
    resolve_semantic_equivalence: true;
    execute_reasoning_rules: true;
    apply_confidence_weighting: true;
    preserve_provenance: true;
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL {
    new_simd_entity:
        validate
        -> classify
        -> identify_execution_role
        -> relate
        -> integrate;

    new_instruction:
        identify_operands
        -> identify_element_types
        -> identify_lane_semantics
        -> identify_memory_requirements
        -> integrate;

    new_vectorization_evidence:
        identify_loop
        -> analyse_dependencies
        -> analyse_memory_access
        -> determine_simd_suitability
        -> integrate;

    performance_revision:
        update_execution_time
        -> update_lane_utilisation
        -> identify_memory_bottleneck
        -> recompute_confidence
        -> regenerate_flow_hash;

    conflict:
        preserve_provenance
        -> compare_evidence
        -> adjust_confidence
        -> flag_review;
}

# ---------- FLOW HASH ----------
FLOW_HASH_INPUT :=
    DOMAIN
    + SUBDOMAIN
    + ONTOLOGY
    + SIMDEntity
    + SIMDOperation
    + SIMDProperty
    + SIMDVectorization
    + SIMDInstructionSet
    + RELATIONSHIPS
    + SEMANTIC_REASONING
    + SEMANTIC_EQUIVALENCE
    + UPDATE_MODEL;

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT);

# ---------- TERMINAL ----------
SIMDOntology
    -> IdentifyDataParallelOperation
    -> AnalyseElementIndependence
    -> OrganiseDataIntoSIMDVectors
    -> LoadSIMDOperands
    -> ExecuteSingleInstructionAcrossLanes
    -> ApplyMaskShuffleOrGatherWhenRequired
    -> StoreSIMDResults
    -> HandleTailElements
    -> MeasureLaneUtilisation
    -> EvaluateSIMDSpeedup
    -> OptimiseMemoryAndInstructionUse
    -> ProduceSIMDResult;

END FLOW