⚡ electrical engineering

Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

Este artículo extiende un marco de filtrado recursivo en cascada paralelo a CPUs y GPUs mediante la resolución de las dependencias entre bloques a través de estrategias de superposición y divide y vencerás, logrando velocidades de procesamiento por lotes y de transmisión en tiempo real de alto rendimiento que superan significativamente a las líneas base existentes mientras mantiene la estabilidad numérica.

Autores originales: Haotian Zhai, Bernd-Peter Paris

Publicado 2026-07-28

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Haotian Zhai, Bernd-Peter Paris

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando limpiar la grabación ruidosa de tu canción favorita, o quizás estás construyendo un robot que necesita reaccionar a su entorno al instante. En ambos casos, necesitas un "filtro" digital para separar los buenos sonidos de los malos. Las herramientas más potentes para este trabajo se llaman filtros recursivos. Piensa en ellos como una cámara de eco mágica: para determinar cuál debería ser el siguiente sonido, el filtro observa el sonido actual y los sonidos que produjo un momento antes. Este "mirar hacia atrás" los hace increíblemente eficientes, utilizando muy poca potencia informática para realizar tareas complejas. Sin embargo, hay un inconveniente: debido a que cada nuevo sonido depende del anterior, el filtro tiene que trabajar paso a paso, como una sola persona caminando por un largo pasillo. Esto crea un cuello de botella, ralentizando todo cuando se necesita procesar cantidades masivas de datos, como video de alta definición o radio en tiempo real.

Durante décadas, los científicos han intentado acelerar esto consiguiendo que más computadoras ayuden. El desafío es que, si divides el trabajo entre muchas computadoras, estas se confunden porque todas están esperando a que la persona anterior termine su paso antes de poder comenzar el suyo. Es como una carrera de relevos donde los corredores están atrapados esperando el testigo, incluso si están en pistas diferentes. Este artículo aborda exactamente ese problema. Toma un truco matemático ingenioso que ya se había demostrado que funcionaba en un chip de computadora único y superrápido, y lo escala para ejecutarse en computadoras de múltiples núcleos modernas y potentes tarjetas gráficas (GPUs). Los autores encontraron una forma de permitir que estas computadoras trabajen juntas sin esperar, convirtiendo una fila lenta de un solo archivo en una autopista de múltiples carriles de alta velocidad, logrando velocidades que antes se consideraban imposibles para este tipo de matemáticas.

El problema de la carrera de relevos y el truco mágico

Para entender el avance, veamos cómo funcionan estos filtros normalmente. Imagina una larga fila de personas pasando un mensaje a lo largo de una cadena. Cada persona tiene que esperar a que la persona delante de ella le susurre el mensaje antes de poder añadir su propia parte y pasarlo. Esta es la parte "recursiva". Si tienes una cadena larga, el mensaje tarda mucho tiempo en llegar al final.

Los autores de este artículo ya habían encontrado una forma de dividir una cadena larga en trozos más pequeños, o "bloques", que pudieran procesarse más rápido. Pero cuando intentaron asignar estos bloques a muchas computadoras a la vez (como un equipo de trabajadores), apareció un nuevo problema: el final de un bloque es el punto de partida para el siguiente bloque. Si le das el Bloque A al Trabajador 1 y el Bloque B al Trabajador 2, el Trabajador 2 se queda esperando a que el Trabajador 1 termine el Bloque A antes de que pueda empezar el Bloque B. El equipo termina trabajando uno por uno de todos modos, invalidando el propósito de tener un equipo.

El principal descubrimiento del artículo es un "truco mágico" matemático llamado superposición. En lugar de esperar la respuesta del bloque anterior, los trabajadores adivinan cuál sería la respuesta si comenzaran desde cero (un supuesto de "estado cero"). Realizan este cálculo inmediatamente. Luego, esperan a que llegue el número inicial real del trabajador anterior. Una vez que llega, simplemente añaden una pequeña "corrección" a su suposición. Es como un chef que comienza a cocinar una sopa basándose en una receta, asumiendo que aún no tiene ingredientes. Cuando el camión de entregas finalmente deja las verduras reales, el chef solo las añade y revuelve. La sopa está lista casi instantáneamente porque el trabajo duro del proceso de cocina ya se había realizado en paralelo.

Dos formas diferentes de correr la carrera

El artículo muestra que este truco mágico puede usarse de dos maneras muy diferentes, dependiendo de lo que estés intentando hacer.

1. El flujo en tiempo real (La línea de montaje)
Si estás procesando datos en vivo, como una transmisión de radio, no puedes esperar a que todo el lote termine antes de reproducir el siguiente segundo de audio. Necesitas que los datos salgan en el mismo orden en que entraron (Primero en entrar, Primero en salir).

La solución: Los autores construyeron un "pipeline de frente de onda" para CPUs multinúcleo. Imagina una línea de montaje donde diferentes trabajadores están manejando diferentes etapas de la misma canción al mismo tiempo. El Trabajador 1 está limpiando el bajo, el Trabajador 2 está arreglando las voces y el Trabajador 3 está añadiendo el eco. Tan pronto como el Trabajador 1 termina un fragmento, se lo pasa al Trabajador 2, quien se lo pasa al Trabajador 3.
El resultado: En una computadora moderna con seis núcleos potentes, este método logró una velocidad de 2.4 Gigasamples por segundo para un filtro complejo de orden 16. Eso es casi 4 veces más rápido que usar un solo núcleo. Curiosamente, descubrieron que añadir núcleos de "eficiencia" más lentos a la mezcla en realidad ralentizaba la línea, demostando que para esta tarea específica, unos pocos trabajadores rápidos son mejores que muchos lentos.

2. El procesamiento por lotes (La fábrica)
Si estás procesando un archivo enorme de datos grabados (como una película o una base de datos), no te importa tanto el orden como la velocidad bruta. Puedes procesar todo el archivo a la vez.

La solución: Utilizaron Unidades de Procesamiento Gráfico (GPUs) potentes, que tienen miles de trabajadores diminutos. Utilizaron una técnica llamada lookback desacoplado. Imagina una fábrica donde cada trabajador calcula su parte del producto inmediatamente. Si un trabajador necesita una pieza de la estación anterior, no se detiene; simplemente consulta un "tablón de anuncios" para ver si la estación anterior ha terminado. Si es así, toma la pieza. Si no, sigue trabajando en otras cosas hasta que esté lista.
El resultado: Este enfoque fue increíblemente rápido. En una tarjeta gráfica NVIDIA RTX 3060, el sistema alcanzó los 38.2 Gigasamples por segundo para una sola sección de filtro. Esto es el 85% de la velocidad absoluta máxima que el hardware es teóricamente capaz de alcanzar (el "techo de ancho de banda de memoria").

Por qué esto importa y a qué vence

Los autores no solo hicieron las cosas más rápidas; demostraron que su método es más confiable que las formas antiguas de hacer las cosas.

El fallo de la "forma directa": Existe un método más antiguo llamado "forma directa" que intenta hacer las matemáticas en un solo paso gigante. El artículo muestra que para filtros complejos (como uno de orden 16), este método antiguo falla. Los números se vuelven tan desordenados que la computadora empieza a producir resultados basura o se bloquea. El nuevo método "cascada" utilizado en este artículo mantiene la precisión incluso en estos niveles altos.
Venciendo a la competencia: Compararon su nuevo código de GPU contra los motores de filtrado paralelo más fuertes disponibles actualmente. Su método fue más rápido en cada orden de filtro probado.
El costo de la velocidad: El artículo también midió cuidadosamente el "costo" de su velocidad. Encontraron que en chips más nuevos y rápidos (como el RTX 3060), las "barreras" (las comprobaciones que hacen los trabajadores para ver si pueden proceder) son baratas, por lo que pueden usar métodos más complejos y rápidos. En chips más antiguos, esas comprobaciones son costosas, por lo que tienen que usar métodos más simples. Esto ayuda a los ingenieros a saber exactamente cómo ajustar su software para diferentes hardware.

La conclusión

Este artículo toma un problema matemático difícil y secuencial y lo convierte en una fiesta paralela. Al usar una estrategia inteligente de "suponer y corregir", permitieron que las computadoras trabajen juntas sin quedarse esperando unas a otras.

Para el streaming en vivo, construyeron un pipeline que es 3.95 veces más rápido en una computadora estándar.
Para el procesamiento por lotes, construyeron un motor de GPU que funciona a 38.2 Gigasamples por segundo, lo cual es un salto masivo hacia adelante.
Crucialmente, demostraron que este método no solo funciona más rápido, sino que funciona mejor, manteniéndose preciso donde los métodos antiguos fallan.

Los autores han publicado su código como una biblioteca de código abierto, lo que significa que cualquiera puede usar ahora estos filtros superrápidos para construir mejores herramientas de audio, videos más claros y robots más inteligentes. Han convertido efectivamente un cuello de botella "secuencial" en una superautopista "paralela", demostando que incluso los problemas matemáticos más obstinados pueden resolverse dejando que un equipo de computadoras trabaje en sincronía.

Resumen Técnico: Filtrado Recursivo en Cascada Paralelo en CPUs Multi-núcleo y GPUs

Planteamiento del Problema
Los filtros recursivos (IIR) son fundamentales en el procesamiento digital de señales debido a su eficiencia computacional en comparación con los filtros no recursivos (FIR). Sin embargo, la dependencia de retroalimentación inherente al filtrado recursivo crea un cuello de botella secuencial: cada muestra de salida depende de las salidas anteriores. Mientras que el artículo complementario (Parte I) de esta serie reformuló las secciones de segundo orden (biquad) en cascada como un sistema lineal tridiagonal por bloques y logró un alto rendimiento en un único núcleo SIMD mediante la factorización PH y la reducción cíclica, escalar este marco de trabajo a CPUs multi-núcleo y GPUs introduce un obstáculo nuevo: la dependencia de estado entre grupos.

En un esquema de procesamiento de múltiples bloques, las salidas terminales de un grupo de bloques de señal sirven como condiciones iniciales para el siguiente grupo. La distribución ingenua de estos grupos en unidades de procesamiento paralelas serializa la ejecución, ya que los grupos subsiguientes deben esperar a que se resuelva el estado de los grupos precedentes. Además, diferentes escenarios de despliegue imponen requisitos conflictivos: el streaming en tiempo real exige baja latencia y orden FIFO (primero en entrar, primero en salir), mientras que el procesamiento por lotes (batch) prioriza el máximo rendimiento sin restricciones de orden. La literatura existente ofrece soluciones parciales, como construcciones de escaneo de prefijo (prefix-scan) para recurrencias de primer orden o implementaciones de forma directa que sufren de inestabilidad numérica en órdenes elevados, pero ningún trabajo previo integra la propagación de estado entre grupos con algoritmos de procesamiento paralelo a nivel de grupo específicamente para la realización de cascada de segundo orden en arquitecturas heterogéneas modernas.

Metodología
El artículo extiende el marco de filtrado multi-bloque a CPUs multi-núcleo y GPUs resolviendo la dependencia entre grupos mediante estrategias de superposición y divide y vencerás.

Propagación de Estado entre Grupos mediante Superposición:
Los autores derivan que la salida de cualquier grupo puede descomponerse en dos componentes:
- Una respuesta de estado cero, computable inmediatamente sin conocimiento del estado inicial.
- Una corrección homogénea, aplicada una vez que llega el estado terminal del grupo precedente.
  Esto permite que todos los grupos ejecuten sus computaciones de estado cero de forma concurrente. Los estados terminales (acarres locales) se propagan entonces a través de los grupos para computar los acarreos globales (condiciones iniciales resueltas), que se aplican como correcciones.
Reducción Cíclica de Divide y Vencerás:
La reducción cíclica estándar es de "un solo lado", exponiendo solo un bloque terminal ( $\bar{y}_{N-1}$ ) en el nivel más profundo de reducción, con el bloque compañero ( $\bar{y}_{N-2}$ ) recuperado solo durante la sustitución hacia atrás. Para soportar la propagación de estado asíncrona, los autores reformulan la reducción cíclica para eliminar ambos paridades simultáneamente. Esta variante de "divide y vencerás" expone ambos bloques terminales antes de que comience la sustitución hacia atrás, permitiendo la propagación del vector de estado terminal completo al grupo subsiguiente.
Implementaciones Específicas de Arquitectura:
- CPU Multi-núcleo en Tiempo Real (Pipeline de Frente de Onda): Apuntando al streaming de baja latencia, la implementación utiliza una estrategia de ejecución de frente de onda (wavefront) realizada con grafos de flujo de Threading Building Blocks (TBB). Cada hilo procesa un grupo de bloques de señal a través de toda la cascada de secciones. Esto preserva el orden FIFO y evita los protocolos de estado entre grupos al depender de la estructura de pipeline donde una sección espera únicamente al estado de su predecesor inmediato.
- GPU por Lotes (Lookback Desacoplado de Núcleo Único): Apuntando al máximo rendimiento, la implementación utiliza un único kernel donde cada bloque de hilos procesa un grupo a través de todas las secciones de la cascada, manteniendo los datos en registros. Emplea un protocolo de lookback desacoplado: cada bloque computa su respuesta de estado cero, publica un "acarreo local" e inspecciona los estados publicados de sus predecesores para resolver su "acarreo global" antes de aplicar las correcciones. Esto evita la serialización sin requerir barreras de sincronización global para cada paso.

Contribuciones Clave

Algoritmos con Capacidad de Estado: Derivación de formas de factorización PH y reducción cíclica que soportan la propagación de estado entre grupos mediante superposición, permitiendo la ejecución concurrente de grupos.
Reducción Cíclica de Divide y Vencerás: Una reformulación que expone ambos bloques terminales antes de la sustitución hacia atrás, un requisito previo para la propagación de estado asíncrona.
Implementación en CPU en Tiempo Real: Un pipeline de frente de onda basado en TBB que logra un escalamiento de 3.95× en seis núcleos de rendimiento de un procesador Meteor Lake heterogéneo, alcanzando ~2.4 GS/s para un filtro de orden 16.
Implementación en GPU por Lotes: Una implementación de kernel único utilizando lookback desacoplado y un modelo de costo basado en la comunicación (techo de memoria, precio de la barrera, piso de ocultación de latencia) que reduce el ajuste a dos parámetros ( $L$ y $N$ ).
Evaluación Trans-Arquitectura: Demostración de que los algoritmos de cascada propuestos superan al baseline más fuerte publicado de recurrencia paralela (forma directa) en cada orden de filtro y mantienen la validez numérica en el orden 16, donde la forma directa falla.

Resultados

Rendimiento de CPU: En un procesador Meteor Lake, el pipeline de frente de onda alcanza 2.4 Gigasamples por segundo (GS/s) para un filtro de orden 16 en seis núcleos de rendimiento. El estudio señala que añadir núcleos de eficiencia (E-cores) degrada el rendimiento debido a cuellos de botella en el pipeline causados por sus menores velocidades de reloj y ancho de vector.
Rendimiento de GPU: En una NVIDIA RTX 3060, el mejor kernel (Reducción Cíclica de Doble Grupo de Hilos, configuración 64×64) alcanza 38.2 GS/s para una sola sección de segundo orden, utilizando el 85% del ancho de banda de memoria del dispositivo.
Escalabilidad y Validez: Los kernels de GPU mantienen la validez numérica en el orden 16, mientras que el baseline de forma directa (Recurrencia Lineal Paralela) produce salidas no finitas (divergencia) en este orden debido a problemas de cuantización de coeficientes.
Precisión del Modelo de Costo: El modelo de costo basado en la comunicación propuesto predice con precisión el comportamiento medido en dos generaciones de GPU (Pascal GTX 1070 y Ampere RTX 3060), identificando correctamente que los conteos de operaciones son "gratuitos" (ocultos por la latencia), mientras que las barreras entre warps y el ancho de banda de memoria son los factores limitantes.

Significancia
Este trabajo establece que el filtrado recursivo en cascada de segundo orden, considerado durante mucho tiempo una carga de trabajo inherentemente secuencial, puede ejecutarse como una carga de trabajo de primera clase en el hardware paralelo comercial moderno. Al resolver las dependencias entre grupos mediante la superposición y adaptar los algoritmos para restricciones arquitectónicas específicas (frentes de onda para CPUs, lookback para GPUs), los autores logran un rendimiento que supera significativamente a los baselines existentes. El trabajo demuestra que la realización en cascada no solo es numéricamente superior para filtros de alto orden, sino que también es apta para una paralelización masiva, cerrando la brecha entre las formulaciones teóricas de matrices por bloques y el despliegue práctico de alto rendimiento en CPUs multi-núcleo y GPUs.

El problema de la carrera de relevos y el truco mágico

Dos formas diferentes de correr la carrera

Por qué esto importa y a qué vence

La conclusión

Más como este