matthewlam721/octopus-parallel: Pre-balanced GPU workload distribution inspired by octopus neural coordination. Achieves up to 14.84x speedup on imbalanced parallel tasks.

A journey from marine biology to GPU optimization

I achieved 14.84x speedup (93.3% time reduction) on GPU parallel processing by applying a simple insight from octopus neuroscience: instead of waiting for the slowest worker, pre-distribute work so everyone finishes together.

Results on real image processing workloads:

Code: [GitHub link]

I was reading about octopuses when something clicked.

An octopus has about 500 million neurons—two-thirds of which are distributed across its eight arms. Each arm can make independent decisions: taste, grab, explore. Yet they coordinate perfectly. Arms don’t fight each other. When an octopus swims, all arms arrive at the target position simultaneously.

How?

The octopus doesn’t wait for its slowest arm. It pre-computes how much force each arm should exert so they all finish together.

I’m a CS grad student. My brain immediately went: “That’s a parallel computing insight.”

Traditional parallel processing has a fundamental inefficiency.

Say you have 4 images to process:

• Image A: 8 million pixels
• Image B: 2 million pixels
• Image C: 1 million pixels
• Image D: 4 million pixels

Naive approach: Assign one image per thread.

Thread 0: ████████████████ (8M) → finishes last
Thread 1: ████ (2M)             → waiting...
Thread 2: ██ (1M)               → waiting...
Thread 3: ████████ (4M)         → waiting...

Total time = slowest thread = 8M cycles
Efficiency = 15M / (8M × 4) = 47%

More than half the compute is wasted on waiting.

What if we distributed work like octopus arms distribute force?

Pre-balanced approach: Divide total pixels evenly.

Total pixels = 15M
Threads = 4
Each thread = 3.75M pixels

Thread 0: █████████ (3.75M) → finishes together
Thread 1: █████████ (3.75M) → finishes together
Thread 2: █████████ (3.75M) → finishes together
Thread 3: █████████ (3.75M) → finishes together

Total time = 3.75M cycles
Efficiency = ~100%

Theoretical speedup: 8M / 3.75M = 2.13x

The key insight: don’t copy data, use index ranges.

# Before: separate arrays per task
images = [image_a, image_b, image_c, image_d]

# After: one contiguous array
flat_data = concatenate(images)  # [all pixels...]

total_work = len(flat_data)
work_per_thread = total_work // num_threads

# Each thread just needs: where to start, where to end
work_start = [0, 3.75M, 7.5M, 11.25M]
work_end = [3.75M, 7.5M, 11.25M, 15M]

@cuda.jit
def balanced_kernel(flat_data, work_start, work_end, output):
    tid = cuda.grid(1)
    
    result = 0.0
    for i in range(work_start[tid], work_end[tid]):
        result += process(flat_data[i])
    
    output[tid] = result

That’s it. No complex data structures. No runtime synchronization. Just pre-computed index ranges.

I tested this on an NVIDIA RTX 4090 with real-world image processing scenarios.

29 low-resolution frames (640×360) + 1 4K keyframe (3840×2160)

This simulates video encoding where most frames are small but keyframes are huge.

Configuration:
  Total pixels: 14,976,000
  Imbalance ratio: 16.6x (keyframe is 16x larger than average)
  
Results:
  Naive:    703.5 ms
  Balanced:  47.4 ms
  
  >>> SPEEDUP: 14.84x <<<
  >>> TIME SAVED: 93.3% <<<

The balanced approach achieved 89.3% of the theoretical maximum speedup.

Pattern: Higher imbalance → Higher speedup.

• Variable-size image batches (web images, medical scans)
• Video processing (variable frame complexity)
• Scientific simulation (non-uniform particle density)
• Any embarrassingly parallel workload with size variance

• Already balanced workloads (nothing to optimize)
• Tasks with dependencies (can’t freely redistribute)
• Memory-bound operations (bottleneck elsewhere)

Imbalance ratio > 2x → Worth trying this approach

GPUs are massively parallel but hate imbalance.

When one thread takes 10x longer than others:

• Other threads finish and sit idle
• The GPU’s thousands of cores wait for one slow thread
• Utilization drops to ~10%

By pre-balancing:

• All threads do equal work
• All threads finish together
• No idle time
• Near 100% utilization

This isn’t just a cute analogy. The octopus nervous system genuinely solves the same problem.

The problem: Coordinate 8 independent processors (arms) with different workloads to reach a goal simultaneously.

Octopus solution: Pre-compute force distribution so all arms arrive together.

GPU solution: Pre-compute work distribution so all threads finish together.

Evolution solved this problem millions of years ago. I just translated it to CUDA.

Let’s talk real numbers.

If you’re processing video at scale:

At cloud GPU rates (~$2/hour for A100), saving 18 hours = saving $36 per 100K batches.

At scale, this is real money.

The implementation is surprisingly simple. Here’s the core logic:

def compute_balanced_assignments(task_sizes, num_threads):
    """Pre-compute balanced work distribution."""
    total_work = sum(task_sizes)
    work_per_thread = total_work // num_threads
    
    work_start = []
    work_end = []
    
    current = 0
    for tid in range(num_threads):
        work_start.append(current)
        current += work_per_thread
        work_end.append(current)
    
    return work_start, work_end

Full code with benchmarks: [GitHub link]

1. Cross-domain insights are powerful. The best solution came from biology, not computer science papers.

2. Simple beats clever. The final implementation is ~20 lines of code. No fancy data structures.

3. Benchmark everything. My first implementation was actually slower due to memory access patterns. Only profiling revealed the fix.

4. Constraints define applicability. This works great for imbalanced, independent workloads. Knowing when NOT to use it is as important as the algorithm itself.

I’m exploring:

• Adaptive thresholds (when to use balanced vs. naive)
• Integration with existing frameworks (PyTorch, JAX)
• Other applications (ray tracing, graph processing)

If you work on GPU optimization and this interests you, reach out.

Sometimes the best algorithms come from unexpected places.

I started with a random thought about octopuses and ended up with a 14.84x speedup on real GPU workloads.

The octopus doesn’t wait for its slowest arm. Neither should your GPU threads.

Thanks for reading. If you found this useful, consider sharing it.

Code: [GitHub link]
Contact: matthewlam721@gmail.com

============================================================
SUMMARY
============================================================

Test                 Pixels      Imbalance  Theoretical  Actual   Status
-------------------------------------------------------------------------
Web Images          11,248,640      3.1x       3.15x      3.41x   ✓ WIN
Thumbnails + 8K     33,189,888      4.0x       4.00x      3.99x   ✓ WIN
Medical Imaging     18,087,936      5.6x       5.57x      5.37x   ✓ WIN
Satellite Imagery  100,458,752      8.0x       7.96x      8.15x   ✓ WIN
Video Frames        14,976,000     16.6x      16.62x     14.84x   ✓ WIN

Balanced approach wins: 5/5 tests
Best speedup: 14.84x on 'Video Frames'
Best time saved: 93.3%

Tested on NVIDIA RTX 4090, January 2025