Skip to content

eilut_analysis.md

Latest commit

 

History

History
351 lines (266 loc) · 9.15 KB

eilut_analysis.md

File metadata and controls

351 lines (266 loc) · 9.15 KB
Raw

EiLUT: LUT Optimizer Analysis

Overview Architecture

graph TD
    A[Python Function Input] --> B[AST Parser]
    B --> C[Custom Compiler]
    C --> D[VM Bytecode]
    D --> E[Candidate Synthesis]
    E --> F[LUT Generation]
    F --> G[Selection Strategy]
    G --> H[Code Replacement]
    H --> I[Optimized Bytecode]
    I --> J[Verification]
    J --> K[Python Code Generation]
Loading

1. System Architecture

The EiLUT system follows a multi-stage optimization pipeline:

$$\text{Python Code} \xrightarrow{\text{Compile}} \text{Bytecode} \xrightarrow{\text{Analyze}} \text{Candidates} \xrightarrow{\text{Select}} \text{LUTs} \xrightarrow{\text{Replace}} \text{Optimized Code}$$

Core Components

  1. AST Compiler: Converts Python functions to custom VM bytecode
  2. Candidate Synthesizer: Identifies pure computational windows
  3. LUT Generator: Creates lookup tables for identified windows
  4. Selection Engine: Chooses optimal LUT replacements
  5. Code Generator: Produces optimized Python with embedded LUTs

2. Virtual Machine Architecture

Instruction Set

The system uses a stack-based VM with the following instruction categories:

graph LR
    subgraph "Stack Operations"
        A1[PUSH]
        A2[POP]
        A3[DUP]
        A4[SWAP]
    end
    
    subgraph "Arithmetic"
        B1[ADD]
        B2[SUB]
        B3[MUL]
    end
    
    subgraph "Bitwise"
        C1[AND]
        C2[OR]
        C3[XOR]
        C4[NOT]
        C5[SHL/SHR]
    end
    
    subgraph "Control Flow"
        D1[JZ]
        D2[JMP]
        D3[CMPZ]
    end
    
    subgraph "Memory"
        E1[LOAD]
        E2[LOCAL_LOAD]
        E3[LOCAL_STORE]
        E4[LUT]
    end
Loading

Opcode Structure

Each opcode is defined with:

  • Name: Operation identifier
  • Stack Pops: Number of values consumed from stack
  • Stack Pushes: Number of values produced to stack
  • Code Size: Instruction size in bytes
  • Time Cost: Execution time in cycles

$$\text{OPCODE} = (\text{name}, \text{pops}, \text{pushes}, \text{size}, \text{time})$$

Stack Execution Model

sequenceDiagram
    participant S as Stack
    participant VM as VM Engine
    participant M as Memory
    
    VM->>S: PUSH value
    VM->>S: LOAD arg_index
    VM->>S: ADD (pop 2, push 1)
    VM->>M: LOCAL_STORE index
    VM->>S: RET (pop 1)
Loading

3. Compilation Process

AST to Bytecode Translation

The compiler uses the visitor pattern to traverse Python AST nodes:

graph TD
    A[Python Function] --> B[ast.parse]
    B --> C[AST Tree]
    C --> D[Compiler.visit]
    D --> E{Node Type}
    E -->|BinOp| F[emit arithmetic ops]
    E -->|Name| G[emit LOAD/LOCAL_LOAD]
    E -->|Constant| H[emit PUSH]
    E -->|If| I[emit conditional jumps]
    E -->|While| J[emit loop structure]
    F --> K[Bytecode List]
    G --> K
    H --> K
    I --> K
    J --> K
Loading

Example Compilation

For the function:

def f(a, b):
    return a + b

The compilation process generates:

  1. LOAD 0 (load parameter a)
  2. LOAD 1 (load parameter b)
  3. ADD (add top two stack values)
  4. RET (return top of stack)

4. Candidate Synthesis Algorithm

Pure Window Identification

The system identifies "pure" computational windows that can be replaced with LUTs:

graph TD
    A[Scan Bytecode] --> B{Check Window i to j}
    B --> C[Stack Balance Analysis]
    C --> D{Valid Balance?}
    D -->|No| E[Try Next Window]
    D -->|Yes| F[Simulate All Input Combinations]
    F --> G{All Simulations Pure?}
    G -->|No| E
    G -->|Yes| H[Generate LUT Table]
    H --> I[Calculate Cost/Benefit]
    I --> J[Add to Candidates]
    E --> K[Next Window]
    J --> K
    K --> L{More Windows?}
    L -->|Yes| B
    L -->|No| M[Return Candidates]
Loading

Stack Balance Calculation

For a window from instruction $i$ to $j$, the stack balance is:

$$\text{balance}(i,j) = \sum_{k=i}^{j-1} (\text{pushes}_k - \text{pops}_k)$$

The minimum depth during execution must be negative (indicating required inputs):

$$\text{min_depth} = \min_{k=i}^{j-1} \sum_{l=i}^{k} (\text{pushes}_l - \text{pops}_l)$$

LUT Table Generation

For each valid window, the system:

  1. Determines required inputs: $\text{inputs} = -\text{min_depth}$
  2. Generates all possible input combinations: ${0, 1, ..., 2^{BITWIDTH}-1}^{inputs}$
  3. Simulates window execution for each combination
  4. Records output mappings: $\text{LUT}: \mathbb{Z}^{inputs} \rightarrow \mathbb{Z}^{outputs}$

5. Cost Model

Size Cost Calculation

The cost model compares original instruction sequence with LUT replacement:

$$\text{size_delta} = (\text{LUT_instr_size} + \text{LUT_data_size}) - \text{original_window_size}$$

Where:

  • $\text{LUT_data_size} = \frac{\text{entries} \times \text{outputs} \times \text{BITWIDTH} + 7}{8}$ bytes
  • $\text{entries} = 2^{\text{BITWIDTH} \times \text{inputs}}$

Time Cost Calculation

$$\text{time_delta} = \text{LUT_time_cost} - \sum_{k=i}^{j-1} \text{time_cost}_k$$

$$\text{LUT_time_cost} = \text{LUT_BASE} + \text{LUT_ADDR_COST} \times \text{inputs} + \text{LUT_MEM_COST} \times \frac{\text{entries}}{16}$$

6. Selection Strategies

Greedy Selection Algorithm

graph TD
    A[Start with All Candidates] --> B{Strategy Type}
    B -->|Size| C[Sort by size_delta ASC]
    B -->|Time| D[Sort by time_delta ASC] 
    C --> E[Filter: size_delta < 0]
    D --> F[Filter: time_delta < 0]
    E --> G[Greedy Selection Loop]
    F --> G
    G --> H{Next Candidate}
    H --> I{Overlaps Selected?}
    I -->|Yes| J[Skip Candidate]
    I -->|No| K[Add to Selection]
    K --> L[Mark Instructions as Covered]
    L --> M{More Candidates?}
    J --> M
    M -->|Yes| H
    M -->|No| N[Return Selection]
Loading

LUT Deduplication

The system detects equivalent LUT tables using hash-based deduplication:

$$\text{hash}(\text{LUT}) = \text{hash}(\text{sorted}(\text{flatten}(\text{table})))$$

Equivalent tables share the same LUT ID, reducing memory usage.

7. Code Generation

Bytecode Replacement

Selected candidates are replaced in the original bytecode:

sequenceDiagram
    participant O as Original Code
    participant R as Replacer
    participant N as New Code
    
    loop For each instruction
        O->>R: Current instruction
        R->>R: Check if start of replacement
        alt Is replacement start
            R->>N: Emit LUT instruction
            R->>R: Skip to end of window
        else Normal instruction
            R->>N: Copy original instruction
        end
    end
Loading

Python Code Generation with LUTs

The final step regenerates executable Python code with embedded LUT dictionaries:

# Generated LUT tables
lut_1 = {(0, 0): 0, (0, 1): 1, (1, 0): 1, (1, 1): 2}

def f(a, b):
    return lut_1[(a, b)]  # Replaces original a + b

8. Verification Process

Simulation-Based Verification

graph LR
    A[Generate Test Inputs] --> B[Run Original Bytecode]
    A --> C[Run Optimized Bytecode]
    B --> D[Original Result]
    C --> E[Optimized Result]
    D --> F{Results Match?}
    E --> F
    F -->|Yes| G[PASSED]
    F -->|No| H[FAILED]
Loading

The simulator executes both original and optimized bytecode with identical inputs to verify correctness.

Test Case Generation

For $n$ function parameters, the system uses predefined test vectors:

  • 1 param: $[1]$
  • 2 params: $[1, 2]$
  • 3 params: $[1, 2, 3]$
  • 4 params: $[1, 2, 3, 4]$

9. Web Interface Architecture

The system includes a Flask-based web IDE:

graph TD
    A[Browser] --> B[Flask Server]
    B --> C[Load Examples]
    B --> D[Process Optimization Request]
    D --> E[Run Optimization Pipeline]
    E --> F[Return Results]
    F --> G[Display in Browser]
    C --> H[Populate UI]
Loading

Debug Mode

The debug mode runs batch optimizations on all examples:

graph TD
    A[Load examples.json] --> B[For each example]
    B --> C[Run optimization]
    C --> D[Log results]
    D --> E[Parse status/metrics]
    E --> F[Add to summary table]
    F --> G{More examples?}
    G -->|Yes| B
    G -->|No| H[Generate Pandas DataFrame]
    H --> I[Print Summary Table]
Loading

10. Limitations and Constraints

Technical Constraints

  1. Bit Width: Limited to 4-bit integers (configurable via BITWIDTH)
  2. Window Size: Maximum 6 instructions (MAX_WIN = 6)
  3. LUT Inputs: Maximum 3 inputs per LUT (due to exponential table growth)
  4. Pure Operations: Only side-effect-free operations can be replaced

Complexity Analysis

  • Candidate Generation: $O(n \times w \times 2^{b \times i})$ where:

    • $n$ = number of instructions
    • $w$ = maximum window size
    • $b$ = bit width
    • $i$ = maximum inputs per LUT

  • Selection: $O(c^2)$ where $c$ = number of candidates (due to overlap checking)

Conclusion

EiLUT provides a comprehensive framework for optimizing small integer computations in MicroPython through systematic LUT replacement. The multi-stage pipeline ensures correctness while achieving significant size and time optimizations for suitable code patterns.

The system's modular design allows for easy extension of the instruction set, cost models, and selection strategies, making it adaptable to different target platforms and optimization goals.