Parallel Programming Ontology

AI SEARCH

FLOW ALGEBRA — PARALLEL PROGRAMMING ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/programming/parallel-programming-ontology.html

FLOW PARALLEL_PROGRAMMING_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Programming"
    ONTOLOGY = "Parallel Programming Ontology"
    PURPOSE = "Formalise parallel programming concepts including tasks, threads, processes, data decomposition, work distribution, synchronisation, communication, accelerators, scalability and parallel execution relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    PARALLEL_PROGRAMMING
    PARALLELISM
    CONCURRENCY
    PROGRAM
    PARALLEL_PROGRAM
    PROCESS
    THREAD
    TASK
    WORKER
    WORKGROUP
    THREAD_GROUP
    KERNEL
    COMPUTE_KERNEL
    PROCESSOR
    CPU
    CORE
    GPU
    ACCELERATOR
    COMPUTE_UNIT
    DISTRIBUTED_NODE
    CLUSTER
    SHARED_MEMORY_SYSTEM
    DISTRIBUTED_MEMORY_SYSTEM
    HYBRID_MEMORY_SYSTEM
    PARALLEL_ARCHITECTURE
    SIMD
    MIMD
    SPMD
    SIMT
    DATA_PARALLELISM
    TASK_PARALLELISM
    PIPELINE_PARALLELISM
    DOMAIN_DECOMPOSITION
    DATA_DECOMPOSITION
    TASK_DECOMPOSITION
    WORK_PARTITION
    WORKLOAD
    WORK_ITEM
    SCHEDULER
    LOAD_BALANCER
    LOAD_BALANCE
    WORK_STEALING
    SHARED_MEMORY
    LOCAL_MEMORY
    DISTRIBUTED_MEMORY
    MESSAGE
    MESSAGE_PASSING
    CHANNEL
    COMMUNICATION
    COLLECTIVE_OPERATION
    BROADCAST
    REDUCTION
    SCATTER
    GATHER
    BARRIER
    LOCK
    MUTEX
    SEMAPHORE
    ATOMIC_OPERATION
    SYNCHRONISATION
    CRITICAL_SECTION
    DATA_DEPENDENCY
    CONTROL_DEPENDENCY
    COMMUNICATION_DEPENDENCY
    RACE_CONDITION
    DATA_RACE
    DEADLOCK
    CONTENTION
    FALSE_SHARING
    CACHE_COHERENCE
    MEMORY_MODEL
    SPEEDUP
    EFFICIENCY
    SCALABILITY
    STRONG_SCALING
    WEAK_SCALING
    SERIAL_FRACTION
    PARALLEL_FRACTION
    OVERHEAD
    COMMUNICATION_OVERHEAD
    SYNCHRONISATION_OVERHEAD
    LOAD_IMBALANCE
    LATENCY
    BANDWIDTH
    THROUGHPUT
    UTILISATION
    PERFORMANCE_METRIC
    EXECUTION_TRACE
    STATE
    EVENT
    ERROR
    FAILURE
    RUNTIME
    LANGUAGE_VERSION
    CONFIGURATION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    DECOMPOSES_INTO
    PARTITIONS
    DISTRIBUTES_TO
    ASSIGNS_TO
    EXECUTES
    RUNS_ON
    SCHEDULES
    BALANCES
    STEALS_WORK_FROM
    RUNS_IN_PARALLEL_WITH
    SHARES
    READS
    WRITES
    COMMUNICATES_WITH
    SENDS
    RECEIVES
    BROADCASTS
    REDUCES
    SCATTERS
    GATHERS
    SYNCHRONISES_WITH
    WAITS_AT
    LOCKS
    UNLOCKS
    PRECEDES
    FOLLOWS
    DEPENDS_ON
    CONFLICTS_WITH
    CONTENDS_FOR
    HAS_MEMORY_MODEL
    HAS_SPEEDUP
    HAS_EFFICIENCY
    HAS_SCALABILITY
    HAS_OVERHEAD
    HAS_LATENCY
    HAS_BANDWIDTH
    HAS_THROUGHPUT
    HAS_UTILISATION
    HAS_STATE
    TRANSITIONS_TO
    HAS_CONFIGURATION
    HAS_LANGUAGE_VERSION
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    SOURCE_CODE
    LANGUAGE_SPECIFICATIONS
    LANGUAGE_VERSION_DATA
    PARALLEL_RUNTIME_DATA
    PROCESS_THREAD_AND_TASK_DATA
    PROCESSOR_TOPOLOGY
    CPU_AND_CORE_DATA
    GPU_AND_ACCELERATOR_DATA
    CLUSTER_TOPOLOGY
    WORKLOAD_DATA
    DECOMPOSITION_DATA
    SCHEDULER_TRACES
    LOAD_BALANCE_DATA
    SHARED_MEMORY_TRACES
    MESSAGE_TRACES
    SYNCHRONISATION_TRACES
    DEPENDENCY_GRAPHS
    MEMORY_MODEL_DATA
    CACHE_COHERENCE_DATA
    EXECUTION_TRACES
    PERFORMANCE_METRICS
    SCALING_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_PARALLEL_ENTITY_IDENTIFIERS
    NORMALISE_LANGUAGE_NAMES
    NORMALISE_LANGUAGE_VERSIONS
    NORMALISE_PROCESS_THREAD_AND_TASK_IDENTIFIERS
    NORMALISE_PROCESSOR_AND_CORE_IDENTIFIERS
    NORMALISE_GPU_AND_ACCELERATOR_IDENTIFIERS
    NORMALISE_NODE_IDENTIFIERS
    NORMALISE_PARALLELISM_MODELS
    NORMALISE_MEMORY_MODEL_TERMS
    NORMALISE_COMMUNICATION_OPERATIONS
    NORMALISE_SYNCHRONISATION_PRIMITIVES
    NORMALISE_PERFORMANCE_METRICS
    NORMALISE_SCALING_MEASURES
    RESOLVE_PARALLEL_ENTITY_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS PARALLEL_REASONING_PIPELINE {
    PARALLEL_WORKLOAD
      -> WORK_DECOMPOSITION
      -> DEPENDENCY_ANALYSIS
      -> RESOURCE_MAPPING
      -> WORK_DISTRIBUTION
      -> PARALLEL_EXECUTION
      -> COMMUNICATION_AND_SYNCHRONISATION
      -> RESULT_COMPOSITION
      -> PERFORMANCE_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS WORK_DECOMPOSITION_REASONING {
    WORKLOAD
      -> DECOMPOSITION_STRATEGY

    DECOMPOSITION_STRATEGY
      -> DATA_PARTITIONS
      OR -> TASK_PARTITIONS
      OR -> PIPELINE_STAGES

    PARTITIONS
      -> DEPENDENCY_ANALYSIS

    DEPENDENCY_ANALYSIS
      -> PARALLELISABLE_WORK_UNITS
  }

  PROCESS RESOURCE_MAPPING_REASONING {
    PARALLEL_WORK_UNITS
      -> RESOURCE_REQUIREMENTS

    RESOURCE_REQUIREMENTS
      -> AVAILABLE_PROCESSORS_CORES_GPUS_OR_NODES

    AVAILABLE_RESOURCES
      -> PLACEMENT_AND_AFFINITY

    PLACEMENT_AND_AFFINITY
      -> EXECUTION_ASSIGNMENT
  }

  PROCESS SHARED_MEMORY_REASONING {
    PARALLEL_TASKS + SHARED_MEMORY
      -> MEMORY_ACCESS_SET

    MEMORY_ACCESS_SET
      -> CONFLICT_ANALYSIS

    CONFLICTING_ACCESSES
      -> SYNCHRONISATION_AND_ORDERING_CHECK

    SYNCHRONISED_ACCESS
      -> CONTROLLED_SHARED_MEMORY_OPERATION

    UNSYNCHRONISED_CONFLICT
      -> DATA_RACE_CANDIDATE
  }

  PROCESS DISTRIBUTED_MEMORY_REASONING {
    PROCESS_A + PROCESS_B
      -> COMMUNICATION_REQUIREMENT

    COMMUNICATION_REQUIREMENT
      -> MESSAGE_CREATION

    MESSAGE_CREATION
      -> SEND_OPERATION

    SEND_OPERATION
      -> NETWORK_OR_INTERCONNECT

    NETWORK_OR_INTERCONNECT
      -> RECEIVE_OPERATION

    RECEIVE_OPERATION
      -> RECEIVER_STATE_UPDATE
  }

  PROCESS COLLECTIVE_REASONING {
    PARTICIPATING_TASKS
      -> COLLECTIVE_OPERATION

    COLLECTIVE_OPERATION
      -> BROADCAST
      OR -> REDUCTION
      OR -> SCATTER
      OR -> GATHER
      OR -> BARRIER

    COLLECTIVE_OPERATION
      -> PARTICIPANT_SYNCHRONISATION_AND_DATA_MOVEMENT
  }

  PROCESS LOAD_BALANCING_REASONING {
    WORK_ASSIGNMENTS
      -> PER_RESOURCE_LOAD

    PER_RESOURCE_LOAD
      -> IMBALANCE_ANALYSIS

    LOAD_IMBALANCE
      -> REDISTRIBUTION_OR_WORK_STEALING

    REDISTRIBUTION_OR_WORK_STEALING
      -> UPDATED_WORK_ASSIGNMENTS
  }

  PROCESS DEPENDENCY_REASONING {
    WORK_UNIT_A + WORK_UNIT_B
      -> DATA_CONTROL_OR_COMMUNICATION_DEPENDENCY

    DEPENDENCY
      -> ORDERING_CONSTRAINT

    INDEPENDENT_WORK_UNITS
      -> PARALLEL_EXECUTION_CANDIDATES

    DEPENDENT_WORK_UNITS
      -> ORDERED_OR_SYNCHRONISED_EXECUTION
  }

  PROCESS PERFORMANCE_REASONING {
    SERIAL_EXECUTION_TIME + PARALLEL_EXECUTION_TIME
      -> SPEEDUP

    SPEEDUP + PROCESSING_RESOURCE_COUNT
      -> PARALLEL_EFFICIENCY

    WORKLOAD + RESOURCE_COUNT + EXECUTION_TIME
      -> SCALING_PROFILE

    SCALING_PROFILE
      -> STRONG_OR_WEAK_SCALING_ANALYSIS

    EXECUTION_TRACE
      -> COMMUNICATION_OVERHEAD
      -> SYNCHRONISATION_OVERHEAD
      -> LOAD_IMBALANCE
      -> MEMORY_CONTENTION
      -> SERIAL_FRACTION

    PERFORMANCE_COMPONENTS
      -> BOTTLENECK_HYPOTHESIS
  }

  PROCESS FAILURE_REASONING {
    PARALLEL_EXECUTION_ERROR
      -> AFFECTED_TASK_OR_RESOURCE

    AFFECTED_TASK_OR_RESOURCE
      -> DEPENDENCY_IMPACT

    DEPENDENCY_IMPACT
      -> PARTIAL_OR_GLOBAL_FAILURE_EFFECT

    FAILURE_CONTEXT
      -> RECOVERY_OR_ABORT_STRATEGY
  }

  RULES {
    IF TASKS_EXECUTE_IN_PARALLEL
    THEN REQUIRE OVERLAPPING_EXECUTION_ON_DISTINCT_EXECUTION_RESOURCES_OR_EQUIVALENT_PARALLEL_HARDWARE_CONTEXT

    IF TASKS_ARE_CONCURRENT
    THEN DO_NOT_AUTOMATICALLY_ASSERT PHYSICAL_PARALLELISM

    IF SHARED_MUTABLE_DATA_IS_ACCESSED
    THEN CHECK SYNCHRONISATION_ORDERING_AND_MEMORY_MODEL

    IF DISTRIBUTED_TASKS_EXCHANGE_DATA
    THEN PRESERVE MESSAGE_SOURCE_DESTINATION_ORDER_AND_COMMUNICATION_CONTEXT

    IF RESOURCE_COUNT_INCREASES
    THEN DO_NOT_AUTOMATICALLY INFER PROPORTIONAL_SPEEDUP

    IF SPEEDUP_IS_REPORTED
    THEN REQUIRE SERIAL_BASELINE_PARALLEL_RUNTIME_WORKLOAD_AND_RESOURCE_COUNT

    IF EFFICIENCY_IS_REPORTED
    THEN REQUIRE SPEEDUP_AND_RESOURCE_COUNT_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND PARALLEL_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ENTITY_IDENTITY_CERTAINTY,
        EXECUTION_TRACE_COMPLETENESS,
        RESOURCE_TOPOLOGY_CERTAINTY,
        WORK_DECOMPOSITION_CERTAINTY,
        COMMUNICATION_TRACE_COMPLETENESS,
        SYNCHRONISATION_TRACE_COMPLETENESS,
        PERFORMANCE_MEASUREMENT_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF RESOURCE_TOPOLOGY_OR_WORKLOAD_IS_UNKNOWN
    THEN REDUCE_SCALABILITY_INFERENCE_CONFIDENCE

    IF EXECUTION_TRACE_IS_PARTIAL
    THEN REDUCE_DEPENDENCY_AND_OVERHEAD_CONFIDENCE

    IF REPRODUCIBLE_PARALLEL_RUNS_CONFIRM_BEHAVIOUR
    THEN INCREASE_CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        CANONICAL_IDENTIFIER,
        PROGRAM_OR_RUNTIME_INSTANCE,
        LANGUAGE_VERSION,
        PARALLEL_MODEL,
        RESOURCE_TOPOLOGY,
        CONFIGURATION
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    PARALLELISM != CONCURRENCY
    THREAD != PROCESS
    TASK != HARDWARE_CORE
    DATA_PARALLELISM != TASK_PARALLELISM
    SHARED_MEMORY != DISTRIBUTED_MEMORY
    SPEEDUP != EFFICIENCY
    STRONG_SCALING != WEAK_SCALING
    MORE_RESOURCES != PROPORTIONAL_SPEEDUP
    PEAK_HARDWARE_THROUGHPUT != APPLICATION_PERFORMANCE
    COMMUNICATION != SYNCHRONISATION
    CONTENTION != DEADLOCK
    CONCURRENT_ACCESS != DATA_RACE
    LOAD_BALANCE != EQUAL_TASK_COUNT
    SERIAL_FRACTION_LIMITS_SCALABILITY
    COMMUNICATION_AND_SYNCHRONISATION_OVERHEAD_AFFECT_SCALABILITY
    MEMORY_HIERARCHY_AND_TOPOLOGY_AFFECT_PARALLEL_PERFORMANCE
    WORKLOAD_AND_CONFIGURATION_MUST_BE_PRESERVED
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_LANGUAGE_AND_VERSION
    CHECK_PARALLEL_ENTITY_IDENTITIES
    CHECK_PROCESSOR_AND_NODE_TOPOLOGY
    CHECK_WORK_DECOMPOSITION
    CHECK_RESOURCE_MAPPING
    CHECK_DEPENDENCIES
    CHECK_SHARED_MEMORY_RELATIONS
    CHECK_MESSAGE_PASSING_RELATIONS
    CHECK_COLLECTIVE_OPERATIONS
    CHECK_SYNCHRONISATION
    CHECK_DATA_RACE_RELATIONS
    CHECK_LOAD_BALANCE
    CHECK_EXECUTION_TRACE
    CHECK_SPEEDUP
    CHECK_EFFICIENCY
    CHECK_SCALING_PROFILE
    CHECK_PERFORMANCE_CONTEXT
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_PARALLEL_PROGRAMMING_ENTITIES
    WORK_DECOMPOSITION_RELATIONS
    DATA_AND_TASK_PARALLELISM_RELATIONS
    RESOURCE_MAPPING_RELATIONS
    SHARED_MEMORY_RELATIONS
    DISTRIBUTED_MEMORY_RELATIONS
    MESSAGE_PASSING_RELATIONS
    COLLECTIVE_OPERATION_RELATIONS
    SYNCHRONISATION_RELATIONS
    DEPENDENCY_RELATIONS
    DATA_RACE_RELATIONS
    LOAD_BALANCE_RELATIONS
    EXECUTION_TRACES
    SPEEDUP_RELATIONS
    EFFICIENCY_RELATIONS
    STRONG_AND_WEAK_SCALING_PROFILES
    OVERHEAD_RELATIONS
    BOTTLENECK_HYPOTHESES
    FAILURE_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON PARALLEL_EXECUTION_EVENT {
      NORMALISE
      RESOLVE_PARALLEL_ENTITIES
      UPDATE_WORK_ASSIGNMENTS
      UPDATE_RESOURCE_MAPPING
      UPDATE_DEPENDENCY_RELATIONS
      UPDATE_COMMUNICATION_AND_SYNCHRONISATION
      UPDATE_EXECUTION_TRACE
      RECOMPUTE_PERFORMANCE_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON NEW_PERFORMANCE_OR_TOPOLOGY_DATA {
      LINK_EVIDENCE
      UPDATE_RESOURCE_TOPOLOGY
      UPDATE_LOAD_BALANCE_PROFILE
      UPDATE_SPEEDUP_AND_EFFICIENCY
      UPDATE_SCALING_PROFILE
      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_PARALLEL_PROGRAM
      BY_PROCESS
      BY_THREAD
      BY_TASK
      BY_CPU
      BY_GPU
      BY_NODE
      BY_WORKLOAD
      BY_DECOMPOSITION
      BY_SHARED_MEMORY
      BY_MESSAGE
      BY_COLLECTIVE
      BY_SYNCHRONISATION
      BY_SPEEDUP
      BY_SCALABILITY
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      ANALYSE_WORK_DECOMPOSITION
      ANALYSE_RESOURCE_MAPPING
      ANALYSE_SHARED_MEMORY
      TRACE_DISTRIBUTED_COMMUNICATION
      ANALYSE_COLLECTIVE_OPERATIONS
      ANALYSE_LOAD_BALANCING
      ANALYSE_DEPENDENCIES
      ANALYSE_PARALLEL_PERFORMANCE
      ANALYSE_FAILURES
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_PARALLELISM_FROM_CONCURRENCY
      DISTINGUISH_DATA_TASK_AND_PIPELINE_PARALLELISM
      PRESERVE_WORKLOAD_RESOURCE_TOPOLOGY_LANGUAGE_RUNTIME_AND_CONFIGURATION_CONTEXT
      DISTINGUISH_SPEEDUP_FROM_EFFICIENCY
      DISTINGUISH_STRONG_FROM_WEAK_SCALING
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_PARALLEL_PROGRAMMING_INFERENCE
    }
  }

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

END FLOW