Procedimiento y arquitectura de circuito en pipeline para el cálculo de la regresión lineal.

Procedimiento y arquitectura de circuito que permiten calcular la regresión lineal sobre una secuencia de muestras sin tener que almacenar dichas muestras previamente en una memoria. El cálculo se va realizando conforme las muestras van llegando al sistema, consiguiendo así que la latencia sea baja y constante a partir del instante en el que llega la última muestra. Por otra parte, la forma de calcular la regresión lineal permite obtener de forma independiente los parámetros de la misma: pendiente, ordenada en el origen y error. Además, gracias a la reutilización de operaciones empleada se disminuye considerablemente el número de operaciones respecto a la forma habitual de cálculo de la regresión.

Procedimiento y arquitectura de circuito en pipeline para el cálculo de la regresión lineal.

Sector técnico

La invención que se describe se enmarca dentro del campo del procesado de señal, más en concreto en lo referente a la elaboración de algoritmos y el desarrollo de arquitecturas de circuito eficientes para llevar a cabo dichos algoritmos.

Estado de la técnica

La regresión lineal [DS80] es una de las técnicas más utilizadas en el análisis estadístico de datos. Su objetivo es determinar la relación estadística que existe entre una variable dependiente, Y, y una variable independiente, X, suponiendo que dicha relación se puede modelar con una recta, es decir:

siendo β₀ y β₁ los parámetros que definen la relación, y que representan respectivamente la ordenada en el origen y la pendiente de la recta.

Para ello se dispone de un conjunto de N pares de muestras de las variables, (X_i, Y_i), siendo i = 1, ..., N. Se supone además que cada par de muestras cumple:

siendo ε_i el error cometido en la muestra i-ésima.

El criterio utilizado para obtener la recta de ajuste consiste en minimizar el error cuadrático medio de los errores cometidos, por lo que la función que se debe minimizar será:

El proceso de minimización consiste en derivar la función e igualarla a cero, es decir:

Las soluciones de este sistema de ecuaciones serán los valores b₀ y b₁, que son respectivamente los estimadores de los parámetros β₀ y β₁, y cuyo valor obtenido mediante la minimización del error cuadrático medio es:

donde todos los sumatorios son para el intervalo i = 1 ... N, y tilde{X} e tilde{Y} son respectivamente los valores medios de las muestras tomadas para cada una de las variables, es decir:

Así, la recta estimada será:

y para cada una de las muestras se cumplirá:

Operando sobre los estimadores b₁ y b₀ se llega a que éstos se pueden reescribir de la siguiente forma:

donde todos sumatorios se refieren al intervalo i = 1 ... N.

Por otra parte, el error cometido en cada muestra respecto al valor estimado será:

y el error cuadrático medio se calcula como:

De esta forma, el problema está solucionado desde el punto de vista matemático, puesto que se pueden aplicar las ecuaciones obtenidas para calcular, a partir de las muestras de entrada, los tres valores de interés en la regresión lineal: b₁, b₀ y ECM. Sin embargo, en sistemas de procesado de señal, y especialmente cuando se trabaja en tiempo real, la aplicación directa de las fórmulas no resulta adecuada para el cálculo de la regresión lineal, puesto que presenta un conjunto de problemas que se detallan a continuación.

A día de hoy los sistemas analógicos han sido ya superados por los digitales, y es necesario recurrir a estos últimos si se desea obtener las máximas prestaciones. Del mismo modo, con los sistemas hardware se pueden alcanzar mejores resultados que los programas software [FBL07], ya que permiten realizar los diseños a más bajo nivel.

Una primera aproximación para conseguir un diseño hardware eficiente consiste en utilizar un sistema basado en un microprocesador, una memoria de instrucciones y una memoria de datos, donde el microprocesador lee las instrucciones de la memoria de programa y las aplica sobre los datos. Esta forma de proceder es equivalente a la programación software, aunque más eficiente puesto que las operaciones son específicas a nivel hardware. Así, se han propuesto métodos para acelerar el cálculo de regresión utilizando este planteamiento [Was07].

Sin embargo, para obtener las mejores prestaciones en cuanto a área, consumo y velocidad, es necesario utilizar hardware dedicado que realice físicamente las operaciones deseadas. Para ello hay que recurrir al empleo de ASICs (Application-Specific Integrated Circuit) o FPGAs (Field Programmable Gate Array), que permiten definir el interconexionado de los circuitos a nivel de puertas lógicas. En este ámbito las arquitecturas hardware en pipeline [Par99] permiten procesar un flujo continuo de datos y con ellas se pueden alcanzar las mejores prestaciones en cuanto a velocidad, rendimiento y latencia, lo que hace que sean la mejor opción para el procesado de señal en tiempo real. Además de dichas prestaciones, al estar trabajando con circuitos hardware es necesario también tener en cuenta el área de los mismos como un parámetro importante de diseño.

En este contexto, el cálculo de la regresión lineal plantea una nueva problemática. En primer lugar, el número de operaciones y en qué orden son éstas calculadas resulta ahora un punto fundamental de cara a reducir el área y la latencia del circuito. Así, por ejemplo, una multiplicación más en los cálculos supone a veces añadir físicamente un multiplicador al sistema, lo cual puede representar un aumento no despreciable de área. Observando las ecuaciones para calcular b₁, b₀ y ECM se puede ver que requieren divisiones, y un elevado número de sumas y multiplicaciones que aumenta con N, lo cual hace inviable la implementación directa del circuito a partir de las fórmulas. Así, se hace necesario buscar una forma de realizar los cálculos que permita reutilizar componentes hardware sin perjudicar a la velocidad, al rendimiento y a la latencia.

Otro punto que conviene destacar es que, de acuerdo con las ecuaciones, es necesario tener almacenadas todas las muestras sobre las que se calcula la regresión. Por ejemplo, hacen falta todas muestras para calcular ECM, que sólo se puede empezar a calcular una vez se conozcan b₁, y b₀. Así, una vez se recogen todos los datos se podrá calcular b₁, posteriormente b₀, y después ECM a partir de las muestras y los dos parámetros anteriores. Ello hace que sea necesario establecer de antemano el número de muestras de la regresión, N, para fijar el tamaño de la memoria de datos o bien sobredimensionar la misma pensando en el peor caso.

Las dependencias de ECM respecto a b₁ y b₀, y de b₀ respecto a b₁, conllevan él problema añadido de que la latencia depende del número de muestras. Ello no sólo hace que la latencia del circuito sea elevada cuando el número de muestras es alto sino que también impone una latencia no constante. Así, sería deseable conseguir una latencia baja y constante, necesaria para el procesado en tiempo real y que permitiría a su vez poder variar...

1. Arquitectura de circuito para el cálculo de una regresión lineal en un sistema de procesado digital de señal sobre una secuencia de N muestras (X_i, Y_i), i = 1, ..., N, que van llegando de forma secuencial al sistema, caracterizada por que comprende:

• un módulo de acumulación de datos (1), que obtiene los valores de A, B, C, D, E y N, siendo:

mediante:

• registros (11), que guardan los valores de A, B, C, D, E y N, los cuales se actualizan cada vez que llega una nueva muestra al sistema,

• sumadores (12), que actúan como acumuladores para actualizar los valores A, B, C, D, E y N cada vez que una nueva muestra llega al sistema,

• multiplicadores (13), para calcular los productos previos a las acumulaciones,

• un módulo de cálculo de operaciones intermedias (2), que calcula F, G, H, I, J y K a partir de A, B, C, D, E y N, siendo:

• un módulo de salida (3), que obtiene el resultado final de la regresión y comprende divisores para calcular los parámetros de la recta de ajuste, b₁, b₀, y ECM a partir de los valores de F, G, H, I, J y K, o bien multiplicadores para calcular los parámetros de la recta de ajuste, b₁, b₀, y ECM a partir de los valores de F, G, H, 1/I, 1/J y 1/K, siendo:

2. Arquitectura de circuito según la reivindicación 1 para el caso particular en el que X_i = i, caracterizada por que:

• el módulo de acumulación de datos (1) sólo necesita obtener los valores de B, C, E y N.

• el módulo de cálculo de operaciones intermedias (2) calcula F, G, H, I, J y K a partir de B, C, E y N, siendo:

• el módulo de salida (3) obtiene b₁, b₀, y ECM a partir de los valores de F, G, H, I, J y K, siendo:

3. Arquitectura de circuito según las reivindicaciones 1 a 2, caracterizada por que, para el caso en el que haya que comparar los valores de los parámetros de la recta de ajuste con ciertos umbrales U_a, U_b y U_ε, el módulo de salida se sustituye por multiplicadores para calcular los productos I • U_a, J • U_b y K • U_ε y comparadores para realizar tras los productos las comparaciones: