# k2-fsa/k2 architecture

> Architecture diagram of the GitHub repository k2-fsa/k2, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-02-19). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/k2-fsa/k2
- Repository: https://github.com/k2-fsa/k2

## Overview

##### Project Type and Purpose
- k2 is designed as a library for integrating FSA/FST algorithms with machine learning frameworks (especially PyTorch). Its goal is to enable efficient, parallel processing (in C++ and CUDA) of operations typically used in speech recognition (e.g., decoding and training with objectives such as CTC and LF-MMI).
- The README emphasizes that most of the heavy lifting is done in C++/CUDA (with templated Ragged data structures and performance-tuned CUDA kernels), which is then exposed to Python via pybind11. Additionally, there is dedicated support for PyTorch integration.

##### File Structure and Architectural Implications
- Notice the central directories:
- “k2/csrc”: The core C++ source code including both host and CUDA implementations of FSA/FST operations, along with specialized algorithms and support utilities.
- “k2/python”: The Python layer that wraps the C++ implementation using pybind11 to allow seamless integration into Python-based workflows.
- “k2/torch”: Extension components specifically for interfacing with PyTorch (including additional C++ files for torch operations).
- Supporting directories (cmake, docs, scripts, tests, and various GitHub workflow files) indicate a robust build/test infrastructure utilizing CMake, GitHub Actions, and multiple test suites.
- The depth of the file tree (e.g., specialized modules for benchmarking, autograd support, and tests) suggests that the system is modular with clear separation between the computational kernels, the bridging to Python, and the testing/CI layers.

##### Key Components
a. Core Engine:
- C++ core library (located mostly in “k2/csrc”), which is responsible for implementing the FSA/FST operations.
- The “Ragged” data structure implementation that underlies many operations.
- Templated CUDA kernels and C++ lambdas that execute core algorithms in parallel.
- Integration with third-party libraries like NVIDIA’s cub for reduction operations.

b. GPU Acceleration and Backend:
- CUDA kernels and utilities (within the C++ code) handle the heavy numerical computations.
- Both CPU and GPU (CUDA) backends coexist, with relevant selection/configuration managed via CMake (refer to the various “cmake” directories and files).

c. Python Binding Layer:
- The interface built using pybind11 from “k2/python”, which wraps the C++/CUDA implementation into Python callable functions.
- This layer makes it possible to interface with autograd systems (e.g., PyTorch’s Function classes) to propagate derivatives efficiently.

d. PyTorch Integration:
- A dedicated module (“k2/torch”) that further extends the functionality to integrate with PyTorch.
- Special torch-related APIs and additional C++ code for bridging CUDA kernels and autograd (e.g., in “k2/torch/csrc”).

e. Build, Testing, and CI Infrastructure:
- Build configuration: Use of CMake (with various supporting modules) for the native C++ build.
- Testing: Separate test suites in the “k2/python/tests” and “k2/csrc” directories.
- CI/CD: A collection of GitHub workflows under “.github/workflows” and scripts under “scripts/” ensure cross-platform builds (both CPU and CUDA), style checks, and automated tests.

##### Relationships and Interactions
- Python applications (or PyTorch scripts) call into the Python binding layer.
- The Python binding layer (pybind11) invokes the corresponding C++ functions from the core engine.
- The C++ engine dispatches calls to either CPU implementations or CUDA kernels (depending on configuration and runtime requirements).
- CUDA kernels use external libraries (like cub) to perform parallel reduction and other high-performance tasks.
- Build and test systems (via CMake and CI scripts) depend on the modular structure to ensure all components (core engine, bindings, and integrations) compile correctly.

##### Architectural Patterns and Design Principles
- Modularity: Separate components for core algorithms, Python bindings, and PyTorch enhancements.
- Parallelization: Heavy use of CUDA and parallel C++ patterns make the expensive parts “embarrassingly parallel.”
- Template-based Programming: The use of C++ templates for creating a flexible, efficient “Ragged” object (akin to TensorFlow’s RaggedTensor but built from a different design philosophy).
- Separation of Concerns: The design clearly isolates the computational kernel layer from interface layers (both Python and PyTorch).

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Top-Level Node
    E1["Python/PyTorch Applications"]:::external

    %% k2 System Subgraph
    subgraph "k2 System"
        %% Core Engine Components
        subgraph "Core Engine Components"
            A1["C++ Core Engine (k2/csrc)"]:::core
            A2["Ragged Data Structures & CUDA Kernels (k2/csrc/ragged*)"]:::core
            A3["Third-party Libraries (cub)"]:::core
        end

        %% Python Layer
        subgraph "Python Layer"
            B1["Python Bindings (pybind11, k2/python)"]:::binding
        end

        %% PyTorch Integration Layer
        subgraph "PyTorch Layer"
            C1["PyTorch Integration (k2/torch)"]:::pytorch
        end

        %% Build & CI Infrastructure
        subgraph "Build & CI Infrastructure"
            D1["CMake & Build Config (cmake)"]:::infra
            D2["CI Workflows (.github/workflows)"]:::infra
            D3["Scripts (scripts/)"]:::infra
        end
    end

    %% Connections for Data Flow
    E1 -->|"calls"| B1
    B1 -->|"invokes"| A1
    C1 -->|"bridges"| A1
    A1 -->|"dispatches"| A2
    A1 -->|"leverages"| A3

    %% Build and CI relationships
    D1 -->|"builds"| A1
    D1 -->|"builds"| B1
    D1 -->|"builds"| C1
    D2 -->|"monitors"| A1
    D2 -->|"monitors"| B1
    D2 -->|"monitors"| C1
    D3 -->|"executes"| A1
    D3 -->|"executes"| B1
    D3 -->|"executes"| C1

    %% Class Definitions for Color Coding
    classDef core fill:#f9d,stroke:#333,stroke-width:2px;
    classDef binding fill:#ccf,stroke:#333,stroke-width:2px;
    classDef pytorch fill:#cfc,stroke:#333,stroke-width:2px;
    classDef infra fill:#ffc,stroke:#333,stroke-width:2px;
    classDef external fill:#cff,stroke:#333,stroke-width:2px;

    %% Click Events
    click A1 "https://github.com/k2-fsa/k2/tree/master/k2/csrc"
    click A2 "https://github.com/k2-fsa/k2/tree/master/k2/csrc/ragged*"
    click B1 "https://github.com/k2-fsa/k2/tree/master/k2/python"
    click C1 "https://github.com/k2-fsa/k2/tree/master/k2/torch"
    click D1 "https://github.com/k2-fsa/k2/tree/master/cmake"
    click D2 "https://github.com/k2-fsa/k2/tree/master/.github/workflows"
    click D3 "https://github.com/k2-fsa/k2/tree/master/scripts/"
```
