La mejor manera de calcular el resultado de una fórmula?

Question

Actualmente tengo una aplicación que puede contener 100s de fórmulas definidas por el usuario. Actualmente, utilizo la notación polaca inversa para realizar los cálculos (empujando los valores y variables a una pila, y luego hacerlas estallar de la pila y la evaluación). ¿Cuál sería la mejor manera de empezar la paralelización de este proceso? Debo buscar en un lenguaje funcional?

Los cálculos se realizan en las matrices de números así que por ejemplo un Un simple + B en realidad podría significar 100s de adiciones. Actualmente estoy usando Delphi, pero esto no es un requisito en el futuro. Voy a usar la herramienta más adecuada para el trabajo. Fórmulas también pueden ser dependientes entre sí de manera que podemos tener una C = A + B fórmula y una segunda D = C + A por ejemplo.

Answer 1

Vamos a suponer que sus fórmulas (ecuaciones) no son cíclicos, de lo contrario no se puede "sólo" evaluarlos. Si ha vectorizado ecuaciones como A = B + C, donde A, B y C son matrices, vamos a ellas conceptualmente dividido en las ecuaciones de los componentes, por lo que si el tamaño de la matriz es de 5, esta ecuación se divide en

a1 = b1 + c1
a2 = b2 + c2
...
a5 = b5 + c5

Ahora suponiendo esto, usted tiene un gran conjunto de ecuaciones en cantidades simples (ya sea enteros, racionales o algo más).

Si tiene dos ecuaciones E y F, digamos que F depends_on E si el lado derecho de F menciona la parte izquierda de E, por ejemplo

E: a = b + c
F: q = 2*a + y

Ahora para conseguir hacia la forma de calcular esto, siempre se podría utilizar iteración aleatorizado para resolver este (esto es sólo un paso intermedio en la explicación), a raíz de este algoritmo:

1 while (there is at least one equation which has not been computed yet)
2   select one such pending equation E so that:
3     for every equation D such that E depends_on D:
4       D has been already computed
5   calculate the left-hand side of E

Este proceso termina con la respuesta correcta, independientemente de la forma de hacer sus selecciones en línea // 2. Ahora lo interesante es que también paraleliza fácilmente. Se puede ejecutar en un número arbitrario de hilos! Lo que necesita es una cola de concurrencia de fallos que reciba tales ecuaciones cuyos requisitos previos (esas las ecuaciones dependen) se han calculado, pero que no se han computado a sí mismos todavía. Cada hilo se sale (rosca a la seguridad) una ecuación de esta cola a la vez, calcula la respuesta, y luego comprueba si existen ahora nuevas ecuaciones de modo que todos sus requisitos previos se han calculado, y luego agrega las ecuaciones (rosca a la seguridad) a la cola de trabajo. Hecho.

Answer 2

Sin saber más, sugeriría tomar un enfoque de estilo SIMD si es posible. Es decir, crear hilos para calcular todas las fórmulas para un solo conjunto de datos. Tratar de dividir el cálculo de fórmulas para paralelizar ellos no daría mucha mejora velocidad que la lógica necesaria para ser capaz de dividir los cálculos en unidades discretas adecuadas para roscar sería difícil escribir y más difícil de hacerlo bien, la sobrecarga cancelaría cualquier ganancia de velocidad. También sufriría rápidamente de los rendimientos decrecientes.

Ahora, si usted tiene un conjunto de fórmulas que se aplican a muchos conjuntos de datos a continuación, la paralelización se hace más fácil y se escala mejor. Cada hilo hace todos los cálculos para un conjunto de datos. Crear un hilo por núcleo de la CPU y establecer su afinidad a cada núcleo. Cada hilo instancia una instancia del código de evaluación fórmula. Crear un supervisor que carga un solo conjunto de datos y se lo pasa un subproceso inactivo. Si no hay hilos están inactivos, esperar a que el primer hilo para terminar de procesar sus datos. Cuando todos los conjuntos de datos se procesan y todas las discusiones han terminado, entonces la salida. Usando este método, no hay ventaja de tener más hilos que los que hay núcleos en la CPU como conmutación hilo es lento y tendrá un efecto negativo sobre la velocidad global.

Si usted ha conseguido solamente un conjunto de datos, entonces no es una tarea trivial. Sería necesario analizar el árbol de evaluación para sucursales sin dependencias en otras ramas de la agricultura y las ramas para separar los hilos que se ejecutan en cada núcleo y en espera de los resultados. A continuación, obtener los problemas de sincronización de los datos y garantizar la coherencia de los datos.