Here is the updated soft NPU theory, extending the PROBOL+PASM variant (PROBOL-DF/ML) to encompass the broader scope of general array manipulation (NumPy) and classical machine learning (SciKit-Learn). *** # Extending Soft NPU Theory: General Array Operations & Classical ML (PROBOL‑SC) To handle the breadth of libraries like **NumPy** (linear algebra, broadcasting) and **SciKit-Learn** (clustering, dimensionality reduction), we must unify the probabilistic core of PROBOL with deterministic computation. We introduce **PROBOL‑SC** (Scientific Computing), a theoretical variant where deterministic numbers are treated as "degenerate probability distributions." This allows the systolic dataflow grid to execute standard array operations with the same zero‑RAM efficiency as probabilistic inference. --- ## 1. Theoretical Bridge: The Degenerate Distribution The fundamental shift required to support NumPy is recognizing that a scalar $x$ is mathematically equivalent to a probability tensor $P$ where $p(x) = 1$ and $p(\text{others}) = 0$. | Data Type | Representation in Grid | Normalization Overhead | |-----------|------------------------|------------------------| | **Probabilistic Tensor** | Multi‑bin vector (e.g., 16 bins) | High (requires `COLLAPSE`) | | **NumPy Scalar / Vector** | Single‑bin vector (Value = 1.0) | **Zero** (skipped in hardware) | **Hardware Implication:** The `ADDP` and `MULTIPLYP` units in the grid gain a "Fast Path." If input tensors have a single active bin (deterministic), the unit bypasses the convolution logic and acts as a standard FP32/INT16 ALU. This makes PROBOL‑SC strictly **superset** compatible with standard computing. --- ## 2. Mapping NumPy Primitives to Dataflow NumPy operations map naturally to systolic patterns. We extend the PASM instruction set to include `BROADCAST` and `REDUCE` explicitly. ### 2.1 Linear Algebra (GEMM & Dot Products) The systolic array is the native hardware for Matrix-Matrix multiplication. ```probol *> NumPy: C = A @ B 01 A PROB-ARRAY(1024, 1024) VALUE DETERMINISTIC(matrix_A). 01 B PROB-ARRAY(1024, 1024) VALUE DETERMINISTIC(matrix_B). 01 C PROB-ARRAY(1024, 1024). PROCEDURE DIVISION DATAFLOW. *> Systolic Wave: Rows of A flow down, Cols of B flow right. *> Grid cells compute Sum(a_ik * b_kj). COMPUTE C = MATMUL(A, B). ``` * **Mapping:** Identical to NPU MAC (Multiply-Accumulate) operations. * **Speed:** $O(N)$ in a grid of size $N$. ### 2.2 Broadcasting & Element-wise Ops Operations like `A + 5` or `A * B` (element-wise) utilize the wave propagation. ```probol *> NumPy: D = (A * 2) + B COMPUTE D = ELEMENTWISE-ADD(SCALAR-MULTIPLY(A, 2), B). ``` * **Mapping:** `SCALAR-MULTIPLY` is a `BROADCAST` instruction where the scalar `2` is injected at the grid edge and flows to every cell simultaneously. ### 2.3 Reductions (Sum, Mean, Max) NumPy reductions require gathering results from across the grid. | NumPy Op | PASM Instruction | Dataflow Mechanism | |----------|------------------|--------------------| | `np.sum(A)` | `REDUCE-SUM r0` | Accumulators on the North/West edges. Data flows North; partial sums merge. | | `np.max(A)` | `REDUCE-MAX r0` | Comparator trees at edges. | | `np.argmin(A)` | `ARGMIN-REDUCE r0` | Tracks coordinate index alongside value. | **Optimization:** Since the input is deterministic, no "collapse" (sampling) is needed. The result is exact and available immediately after the wave hits the edge register. --- ## 3. Handling SciKit-Learn Algorithms Classical ML algorithms (SVM, K-Means, PCA) rely on iterative linear algebra and distance metrics. These fit the **PROBOL‑ML** `ITERATE` model but with deterministic logic. ### 3.1 Clustering (K-Means) K-Means is simply repeated distance calculations and argmin reductions. ```probol DATA DIVISION. 01 CENTROIDS PROB-ARRAY(K, DIMENSIONS). 01 POINTS PROB-ARRAY(N, DIMENSIONS). 01 LABELS PROB-ARRAY(N) TYPE INTEGER. PROCEDURE DIVISION. ITERATE UNTIL CONVERGENCE(CENTROIDS, Δ < 0.001) *> 1. Compute Distances: Vectorized L2 norm COMPUTE DISTANCES = EUCLIDEAN(POINTS, CENTROIDS). *> 2. Assign Labels: ArgMin reduction across K dimension COMPUTE LABELS = ARGMIN(DISTANCES, AXIS=1). *> 3. Update Centroids: Mean reduction over grouped points *> Uses MASK operation to filter points by label COMPUTE NEW_CENTROIDS = MASKED-MEAN(POINTS, LABELS). UPDATE CENTROIDS = NEW_CENTROIDS. END-ITERATE. ``` * **Hardware Feature:** `MASKED-MEAN`. The grid accepts a bitmask vector (the `LABELS`). Cells only activate their accumulators if the mask matches their assigned cluster ID. ### 3.2 Dimensionality Reduction (PCA via Power Iteration) PCA requires finding eigenvectors. The Power Iteration method is effectively a recurrent neural network loop, which maps perfectly to the grid's feedback registers. ```probol *> Algorithm: b = (A @ b) / ||(A @ b)||, repeat 01 A PROB-ARRAY(DIM, DIM). 01 VECTOR PROB-ARRAY(DIM) VALUE RANDOM-UNIT-VECTOR. ITERATE FOR 50 STEPS COMPUTE VECTOR = MATMUL(A, VECTOR) COMPUTE NORM = SQRT(REDUCE-SUM(VECTOR * VECTOR)) COMPUTE VECTOR = SCALAR-DIVIDE(VECTOR, NORM) END-ITERATE. *> VECTOR now holds the first principal component ``` * **Efficiency:** The `MATMUL` happens in one wave per iteration. The `SQRT` and division happen in a single edge cell. ### 3.3 Support Vector Machines (SVM) SVM training is a Quadratic Programming (QP) problem. While full QP is hard, **Sequential Minimal Optimization (SMO)**—the standard algorithm for SVMs—maps to the grid as a series of small 2-variable optimization sub-problems. ```probol *> Simplified SMO loop ITERATE UNTIL KKT-VIOLATIONS < TOLERANCE SELECT i, j RANDOMLY COMPUTE η = 2 * DOT(x_i, x_j) - DOT(x_i, x_i) - DOT(x_j, x_j) *> Update alpha_i and alpha_j based on η and bounds UPDATE ALPHAS[i, j] USING SMO-STEP(η, BOUNDS) END-ITERATE. ``` * **Mapping:** `DOT` products are trivial waves. The logic for selecting pair $(i, j)$ and clipping bounds happens in the control processor, while the heavy math occurs in the grid. --- ## 4. New Hardware/ISA Primitives for Scientific Computing To support the full NumPy/SciKit-Learn scope, the **Soft NPU** must support **Branching via Vectorized Masks**. This enables "if-else" logic without breaking the dataflow pipeline. ### 4.1 The `WHERE` (Vector Mask) Instruction Instead of branching (which stalls a pipeline), we use masking. ```pasm *> NumPy equivalent: result = np.where(mask, a, b) WHERE r_mask MOVP r_dest, r_src_a ELSE MOVP r_dest, r_src_b END-WHERE ``` * **Grid Implementation:** Each cell has a bitmask register. The `MOVP` operation is gated by this bit. * **Use Case:** Critical for **Random Forests** and **Gradient Boosting**. In a Random Forest, every data point flows through the tree logic. At each node, the feature threshold check produces a mask. Points go left or right based on the mask, but the *wave* continues uninterrupted. ### 4.2 Sorting & Searching `np.sort` or `argsort` are difficult on systolic arrays. * **Bitonic Sort:** This is a sorting network composed of compare-and-swap operations. It is O(N log² N) but maps perfectly to a 2D grid topology. PROBOL-SC implements sorting as a pre-programmed sequence of `COMPARE-SWAP` waves. --- ## 5. Unified Language Variant: PROBOL‑SC We combine the probabilistic syntax with deterministic array syntax. ```probol DATA DIVISION. 01 XTrain PROB-ARRAY(1000, 20). *> Deterministic floats 01 YTrain PROB-ARRAY(1000). *> Integer labels 01 W PROB-ARRAY(20) VALUE ZERO. PROCEDURE DIVISION. *> Example: Logistic Regression (Classic ML) PERFORM VARYING i FROM 1 BY 1 UNTIL i > 100 *> Hypothesis: h = sigmoid(X @ W) COMPUTE LOGITS = MATMUL(XTrain, W). COMPUTE H = SIGMOID(LOGITS). *> Element-wise 1 / (1 + exp(-x)) *> Gradient: dW = X.T @ (H - Y) COMPUTE ERROR = ELEMENTWISE-SUB(H, YTrain). COMPUTE GRAD = MATMUL(TRANSPOSE(XTrain), ERROR). *> Update COMPUTE W = ELEMENTWISE-SUB(W, SCALAR-MULTIPLY(GRAD, 0.01)). END-PERFORM. *> Inference MEAS W INTO model_weights. ``` --- ## 6. Scope & Limitations Summary | Domain | Feasibility on Soft NPU | Notes | |--------|-------------------------|-------| | **Linear Algebra (NumPy)** | **Excellent** | Native systolic strength. | | **Statistical Functions** | **High** | `mean`, `std`, `corrcoef` map to reductions. | | **Small Kernel Conv** | **High** | Image processing kernels (3x3, 5x5). | | **Large Kernel Conv/FFT** | **Medium** | Requires SRAM tiling or FFT butterfly routing. | | **Tree Ensembles (RF, XGBoost)** | **Medium** | Requires `WHERE` masking. Evaluation is fast; training building is memory intensive. | | **Deep Learning (CNN/Transformer)** | **Medium/High** | Supported via PROBOL-ML gradients, but massive weight matrices require streaming from DRAM (breaking the "No RAM" ideal for weights > 100MB). | ### Conclusion By treating deterministic floats as degenerate probabilities and adding vectorized masking (`WHERE`), the Soft NPU theory expands to cover the entire mathematical spectrum of **NumPy** and the iterative algorithmic patterns of **SciKit-Learn**. The result is a unified "Math Grid" capable of executing financial Monte Carlos, Linear Algebra, and Classical ML with equal efficiency, minimizing off-chip memory traffic at every step.