Write a fast parallelized implementation of calculating an EMA time series based on a…
- User
Write a fast parallelized implementation of calculating an EMA time series based on a fixed exponential decay value. Use JAX in python.
Assistant
Here's a fast and parallelized JAX implementation of the Exponential Moving Average (EMA) time series, based on a fixed exponential decay value (e.g.,
decayin[0, 1)).We will use JAX's XLA compilation, vectorization, and parallelism where applicable.
✅ EMA Definition
The Exponential Moving Average is defined recursively:
ema[0] = init_value ema[t] = decay * ema[t-1] + (1 - decay) * data[t]This recurrence is inherently sequential, but we can compute it efficiently using JAX's
lax.scan, which compiles the loop efficiently on accelerators like GPUs/TPUs.
🚀 JAX Implementation
import jax import jax.numpy as jnp from jax import lax def compute_ema(data, decay, init_value=0.0): """ Compute Exponential Moving Average (EMA) using JAX. Args: data: JAX array of shape (T,) representing time series. decay: float in [0, 1), decay factor for EMA. init_value: initial value for EMA. Returns: ema: JAX array of shape (T,) with EMA values. """ def update_ema(carry, x): ema_prev = carry ema_new = decay * ema_prev + (1.0 - decay) * x return ema_new, ema_new # (carry, output) ema_values, _ = lax.scan(update_ema, init_value, data) return ema_values
🔁 Vectorized / Batched Version
To handle batched time series (e.g.,
(B, T)), you can usejax.vmap.# Batched version using vmap compute_ema_batched = jax.vmap(compute_ema, in_axes=(0, None, None))Now you can pass in a batch of time series:
batch_size = 32 seq_len = 1000 data_batch = jnp.sin(jnp.linspace(0, 10, seq_len))[None, :].repeat(batch_size, axis=0) ema_batch = compute_ema_batched(data_batch, decay=0.9, init_value=0.0) print(ema_batch.shape) # (32, 1000)
🧪 JIT Compilation
You can compile the function using
jax.jitfor faster execution:compute_ema_jitted = jax.jit(compute_ema, static_argnums=(1,))Note: If you're batching, apply
jitto the batched version:compute_ema_batched_jitted = jax.jit(compute_ema_batched, static_argnums=(1, 2))
⚡ Performance Notes
- This uses
lax.scan, which is compiled and runs efficiently on GPU/TPU. - It cannot be fully vectorized due to its recursive nature, but JAX optimizes scan loops well.
- For large batches or sequences, the batched + JIT-compiled version performs very well.
📈 Example Usage
import matplotlib.pyplot as plt key = jax.random.PRNGKey(0) data = jax.random.normal(key, (1000,)) * 5 + jnp.sin(jnp.linspace(0, 10, 1000)) ema = compute_ema(data, decay=0.9) plt.plot(data, label='Noisy Data') plt.plot(ema, label='EMA', linewidth=2) plt.legend() plt.show()
Let me know if you want an implementation that supports variable decay per sample or more advanced variants like EWMAs with weights or centered windows!
- This uses
- User
Can you make them parallelized with the parallel prefix sum algorithm?
Assistant
Great question! You're asking whether we can compute the Exponential Moving Average (EMA) using a parallel prefix sum approach, which would allow true parallelism instead of relying on
lax.scan's sequential recurrence.
🧠 Why This Is Interesting
The standard EMA is defined recursively:
ema[0] = x[0] ema[t] = decay * ema[t-1] + (1 - decay) * x[t]This recurrence makes it inherently sequential, and hard to parallelize naively. However, there's a neat trick: we can express EMA as a weighted sum of the inputs, and that weighted form allows us to vectorize and parallelize the computation!
✅ Reformulating EMA as a Weighted Sum
We can rewrite the EMA at time
tas:Where:
- The denominator ensures normalization so the weights sum to 1.
This is called an Exponentially Weighted Moving Average (EWMA).
So now, we can compute this efficiently using cumulative sums and powers, both of which are vectorizable and parallelizable in JAX.
🚀 Fast Parallel JAX Implementation (No Scans)
import jax import jax.numpy as jnp def compute_ema_parallel(data, decay, init_value=0.0): """ Compute Exponential Moving Average using a parallelized, scan-free method. Args: data: JAX array of shape (T,) or (B, T) decay: float in [0, 1), exponential decay factor init_value: initial value for EMA Returns: ema: JAX array of same shape as data """ alpha = 1.0 - decay # EWMA parameter # Handle batch dimension if present batched = data.ndim == 2 if not batched: data = data[jnp.newaxis, :] # Add fake batch dim B, T = data.shape # Create weights powers = jnp.arange(T)[jnp.newaxis, :] # (1, T) weights = (alpha ** powers).astype(data.dtype) # (1, T) cum_weights = (weights.cumsum(axis=1)) # (1, T) # Scale each sequence independently by its cumulative weight ewma = (data * weights).cumsum(axis=1) / cum_weights # If no batch, remove batch dimension if not batched: ewma = ewma[0] return ewma
🔁 Batch Support via Vectorization
This function already supports batched input
(B, T)thanks to JAX’s broadcasting and vectorization.You can JIT and VMAP it further if needed:
compute_ema_parallel_jitted = jax.jit(compute_ema_parallel) compute_ema_parallel_batched = jax.vmap(compute_ema_parallel, in_axes=(0, None, None))
⚡ Performance Benefits
- Fully vectorized and scan-free, ideal for GPU/TPU acceleration.
- Uses prefix sums (
cumsum), which are highly optimized in XLA. - Can be used inside JIT-compiled functions and autograd seamlessly.
📈 Example Usage
import matplotlib.pyplot as plt key = jax.random.PRNGKey(42) data = jax.random.normal(key, (500,)) + 0.1 * jnp.linspace(0, 3, 500) ema = compute_ema_parallel(data, decay=0.9) plt.plot(data, label='Noisy Data', alpha=0.6) plt.plot(ema, label='Parallel EMA', linewidth=2) plt.legend() plt.show()
🔄 Comparison with
scanVersionMethod Sequential? Parallelizable? Stable? Notes lax.scanYes No High Exact recursive update Parallel (this) No ✅ Yes Good Approximates EMA; stable for small TFor long sequences, you may want to combine both approaches or use windowed EMA for stability.
✅ Summary
Yes, you can parallelize EMA using a prefix-sum-based formulation, avoiding recurrence entirely. This allows:
- Full GPU/TPU acceleration
- Better integration with JIT compilation
- Simpler behavior inside gradients or vmaps
Let me know if you want a version that uses logarithmic prefix sum (parallel binary operator) like in true parallel scan algorithms!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.