Skip to content

multithreading-strategy.md

Latest commit

 

History

History
52 lines (32 loc) · 5.89 KB

multithreading-strategy.md

File metadata and controls

52 lines (32 loc) · 5.89 KB
Raw

Multithreading Strategy for C++ Core

Approach: Direct std::thread per Chunk

For the C++ core of the AgentSimMiddleware, a direct std::thread per chunk approach is currently employed, built upon the C++ Standard Library concurrency primitives (<thread>, <mutex>). This approach is chosen for its simplicity in initial implementation and direct mapping to parallel processing of agent data chunks.

Justification

  1. Simplicity and Direct Parallelism: Creating std::thread instances directly for processing distinct chunks of AgentData provides a straightforward way to achieve parallelism without the overhead of a complex job system. Each thread operates on its own segment of data, minimizing contention.

  2. Data-Oriented Design (DOD) Compatibility: This approach naturally complements data-oriented principles. By having threads operate on contiguous chunks of AgentData (Structure of Arrays - SoA), cache locality is maintained, leading to improved cache performance.

  3. Platform Agnostic: Leveraging the C++ Standard Library ensures that the multithreading solution remains highly portable across various operating systems and compiler toolchains without relying on third-party libraries.

  4. Resource Management: Threads are created and joined per update cycle, ensuring that computational resources are utilized efficiently for the duration of the processing.

Core Components

The current multithreading approach primarily involves:

  • Worker Threads (std::thread): Threads are created dynamically for each update cycle, with each thread assigned a specific chunk of agents to process.
  • Synchronization Primitives (std::mutex): std::mutex is used to protect access to shared resources, specifically the AgentCommand buffer and its counter (commandCount), to prevent race conditions during command generation.

Integration with AgentData

Threads operate directly on chunks of the AgentData structure. For example, a thread might take a range of indices and update the positions and FSM states for agents within that range. This approach maintains cache locality, as different threads operate on distinct memory ranges, reducing false sharing.

Future Enhancements: Custom Job System

For future, more advanced multithreading, a custom job system is envisioned with the following principles:

Agent Batch Processing

  • Chunking AgentData: The AgentData Structure of Arrays (SoA) will be divided into smaller, contiguous batches. Each batch will represent a subset of agents (e.g., agents 0-99, 100-199, etc.).
  • Job Creation: For each major simulation step (e.g., position update, FSM evaluation), multiple jobs will be created, with each job responsible for processing one of these agent batches. This allows for parallel execution across worker threads.
  • Read-Only vs. Read-Write Access: Jobs will be designed to clearly define their data access patterns.
    • Read-Only Operations: Many simulation steps involve reading agent data without modification (e.g., sensing nearby agents). These can be run highly concurrently without extensive synchronization.
    • Read-Write Operations: Steps that modify agent data (e.g., applying movement, changing FSM state) will require careful management. Jobs modifying disjoint batches of agents can run in parallel.

Synchronization Mechanisms and Thread Safety

To avoid race conditions, ensure data consistency, and maintain thread safety, the following mechanisms and considerations will be employed:

  • Job Dependencies: Jobs will declare their dependencies. The job system will ensure that a job only starts once all its dependencies are completed. This is crucial for operations where the output of one set of jobs is the input for another (e.g., all position updates must complete before collision detection begins). This can be managed using atomic counters where a job decrements a counter upon completion, and a dependent job waits for the counter to reach zero.
  • Atomic Operations (std::atomic): For small, frequently accessed, and independently modifiable values (e.g., counters, flags, indices), std::atomic types will be used to ensure thread-safe updates without requiring full mutex locks.
  • Mutexes (std::mutex): Mutexes will be used sparingly and only for protecting access to genuinely shared, mutable data structures that cannot be made thread-safe through other means (e.g., adding a new agent to the AgentData from a non-main thread, or modifying the job queue). The goal is to minimize mutex contention.
  • Condition Variables (std::condition_variable): Condition variables will be used in conjunction with mutexes to enable threads to wait for specific conditions to be met (e.g., a worker thread waiting for new jobs to appear in the queue, or a main thread waiting for all jobs in a frame to complete).
  • Thread-Local Storage (TLS): Where possible, data that is unique to a thread's execution context will be stored in thread-local storage to eliminate the need for synchronization.
  • Avoiding False Sharing: The Structure of Arrays (SoA) design inherently helps mitigate false sharing by ensuring that data for different properties of an agent (or different agents) are stored in separate, often non-contiguous memory regions. When processing batches, jobs will operate on distinct memory ranges, further reducing the likelihood of false sharing.
  • Immutable Data: Wherever feasible, data passed to jobs will be immutable, preventing modification and thus eliminating the need for synchronization during read operations. If data needs to be modified, it will either be localized to the job (working on its own copy or a specific range) or explicitly protected.

By adhering to these principles, the custom job system will enable highly parallel and efficient processing of agent simulations while rigorously maintaining data integrity and avoiding common multithreading pitfalls.