DOCSEARCHbyAlgolia
Submit Docs

weave

repository·master·Indexed 20 days ago

https://github.com/mratsim/weave

A high-performance, message-passing based multithreading runtime for the Nim programming language, designed for ultra-low overhead in task and data parallelism. The project includes a comprehensive parallel benchmark suite covering workloads such as GEMM, Black & Scholes option pricing, Bouncing Producer-Consumer (BPC), and a Raytracing demo based on SmallPT.

Tokens
22.6K
Snippets
30
Records
108
Agent score
69%

What's inside weave

  1. Overview of Single-Producer Multiple-Consumers (SPC) benchmarks

    master

    The single_task_producer benchmark is designed to measure the scalability of a single producer when feeding tasks to multiple concurrent consumers.

    In this benchmark:

    1. A single worker (the producer) generates n tasks.
    2. Each task is configured to run for a specific duration t (in microseconds).

    The primary goal is to determine the maximum number of concurrent consumers that a single producer can sustain before performance degrades or throughput limits are reached.

  2. Overview of the Black Scholes Benchmark

    master

    The Black Scholes benchmark evaluates the performance of pricing multiple financial options in parallel. It compares two approaches for evaluating the cumulative normal distribution function (CND): numerical evaluation and pre-computed table lookup.

    In this benchmark, parallelization is achieved by pricing individual options across multiple threads. The analytical approach to pricing options is primarily limited by the processor's floating-point calculation capacity.

  3. Overview of Pure Nim GEMM implementation

    master

    The gemm_pure_nim benchmark provides a pure Nim implementation of a GEneralized Matrix Multiplication (GEMM) kernel. This implementation is derived from the Laser project.

    Key features include:

    • High Performance: Utilizes state-of-the-art loop tiling, register blocking, SIMD vectorization, and code generation techniques.
    • Competitive Speed: Designed to match the performance of pure Assembly libraries such as OpenBLAS or MKL.
    • Portability: Uses generic code that is easily portable to new platforms (e.g., ARM, RISCv5, MIPS) and new data types (e.g., integers).

  4. Overview of the Weave Parallel Benchmark Suite

    master
    The Weave Parallel Benchmark Suite is a collection of workloads designed to stress various aspects of the Weave multithreading runtime. These benchmarks help verify the runtime's suitability for different workload types, including task parallelism, data parallelism, and nested parallelism. They cover scenarios such as extreme load balancing, scheduler overhead, SIMD vectorization, and memory contention.

  5. Overview of the Weave Memory Subsystem

    master

    The Weave memory subsystem is designed to optimize memory allocation, prevent fragmentation, and reduce cache misses in a multithreaded environment. It employs specialized data structures for different object lifetimes to ensure scalability and high performance.

    Allocation Strategies by Object Type

    Object TypeLifetimeAllocation Strategy
    Thread-local objectsEqual to thread lifetimeAllocated directly with no caching.
    Steal requestsBounded; exchanged between threadsCached via a Persistack (a simple stack that recycles or tracks unused objects).
    Task channelsBounded; tied to steal request lifetimeCached via a Persistack.
    Flowvars / FuturesUnbounded; visible to usersCached via a thread-safe memory pool. If WV_LazyFlowvar is used, they are allocated on the stack until their lifetime must extend beyond the task stack.
    TasksUnbounded; exchanged or localCached via a look-aside list that cooperates with the memory pool to adaptively store/release tasks.

    Key Features

    • Scalability: The memory pool and look-aside list allow the runtime to handle massive bursts of tasks (billions in milliseconds).
    • Memory Reclamation: The memory pool can release memory back to the OS. It uses a "deterministic heartbeat" (triggered every ~N allocations) to perform amortized, expensive maintenance tasks like releasing arenas.

  6. Overview of Project Picasso (Weave)

    master

    Project Picasso (codenamed Weave) is a high-performance multithreading runtime for the Nim programming language. It is designed to provide an efficient, ergonomic, and scalable multithreading environment by leveraging Nim's lightweight borrow-checker and state-of-the-art work-stealing schedulers.

    Key characteristics include:

    • Throughput Optimized: Focused on maximizing total work processed rather than individual task latency.
    • Message-Passing Architecture: All communications, including core synchronization and memory pool management, occur through channels.
    • Future Model: Uses a model similar to async/await for IO, multiplexing an arbitrary number of user tasks onto a limited number of kernel threads.
    • Dynamic Load Balancing: Implements lazy loop splitting and adaptive stealing to manage task granularity based on real-time conditions.
    • Composable: Designed to prevent resource oversubscription when multiple libraries using the runtime are used together.

  7. Overview of the Multithreading API Standard

    master

    This RFC defines a standard for multithreading interfaces in Nim to ensure interoperability between different libraries. It focuses on two primary pillars:

    1. Task Parallelism: An API based on the fork-join model for managing tasks and execution resources. Threadpools and parallelism libraries are expected to implement this.
    2. Inter-thread Communication: An API for channels to facilitate communication between threads. Channels libraries are expected to implement this.

    The specification targets the public user API and does not dictate underlying implementations. It is designed to support scenarios where an application might use multiple executors, schedulers, or parallelism backends simultaneously (e.g., specialized threadpools tuned for specific workloads).

  8. Overview of the Weave Multithreading Runtime

    master

    Weave is a research-oriented multithreading runtime designed to address limitations found in standard implementations like OpenMP and GCC's libgomp. The runtime focuses on high-performance task scheduling and memory management with specific optimizations for:

    • NUMA-aware allocation: Ensuring threads are scheduled on work that uses memory directly connected to their NUMA node.
    • Hyperthread optimization: Scheduling hyperthreads on work that shares the same L1 cache to maximize efficiency.
    • Task Scheduling: Avoiding the bottlenecks found in central-list scheduling (e.g., libgomp's mutex-protected central list) by implementing more efficient tasking models.
    • Nested Loop Support: Addressing the design flaws of OpenMP where nested parallel regions can lead to thread explosion, favoring task queues for graph-level scheduling (e.g., for beam search or GANs).

  9. What is Weave multithreading runtime?

    master

    Weave (codenamed "Project Picasso") is a high-performance, fine-grained multithreading runtime designed for the Nim programming language. It is built to handle various workloads including compute-bound, memory-bound, load balancing, and nested parallelism.

    Key characteristics:

    • Low Overhead: Designed to be ultra-low overhead, performing 3x to 10x better than Intel TBB and GCC OpenMP on overhead-bound benchmarks (e.g., trillions of tasks in milliseconds).
    • Message-Passing Architecture: Unlike traditional work-stealing runtimes that use shared-memory deques, Weave is based on Message-Passing.
    • Synchronization Model: To reduce the bug surface, Weave limits synchronization to simple Single-Producer Single-Consumer (SPSC) and Multi-Producer Single-Consumer (MPSC) channels.
    • Cross-Platform Support: Tested on Linux, MacOS, and Windows for x86, x86_64, and ARM64 architectures using C and C++ backends.

  10. Overview of Weave multithreading runtime

    master

    Weave (codenamed "Project Picasso") is a high-performance, fine-grained multithreading runtime for the Nim programming language.

    Unlike traditional runtimes that use work-stealing with shared-memory deques, Weave is based on Message-Passing. This design aims to provide ultra-low overhead and composable parallelism, making it suitable for workloads ranging from compute-bound and memory-bound tasks to massive-scale task parallelism (trillions of tasks) and nested parallelism.

    Key Characteristics:

    • Low Overhead: Designed to outperform industry standards like Intel TBB and GCC OpenMP in overhead-bound scenarios.
    • Fine-grained: Aims to solve the "grain size" problem, allowing developers to parallelize tasks without worrying if they are large enough to justify the overhead.
    • Supported Platforms: Linux, MacOS, and Windows on x86, x86_64, and ARM64 architectures using C and C++ backends.

  11. Understand the research foundations of Weave

    master

    Weave's design is informed by extensive research in multithreading, task scheduling, and NUMA-aware systems. The research covers several key areas:

    • Memory Allocation: Focuses on NUMA-aware allocators (e.g., OpenMP) to optimize memory access patterns.
    • Hardware Details: Considers memory models (weak/relaxed vs. strong ordering) and their impact on atomic operations.
    • Scheduling Paradigms:
      • Earliest Deadline First (EDF): Optimized for latency, suitable for real-time or latency-constrained systems like games.
      • Parallel Depth-First (PDF): An alternative to work-stealing that provides optimal asymptotic behavior when sufficient parallelism is available.
      • Work-Stealing (WS): The most common implementation, providing optimal asymptotic behavior with sufficient parallelism.
    • Heterogeneous Architectures: Research into scheduling across mixed CPU/GPU environments (e.g., Kokkos, StarPU).