¿Cómo escribo código dimensionalmente agnóstico?

19

A menudo me encuentro escribiendo código muy similar para versiones de una, dos y tres dimensiones de una operación / algoritmo dado. Mantener todas estas versiones puede volverse tedioso. La generación de código simple funciona bastante bien, pero parece que debe haber una mejor manera.

¿Existe una forma relativamente simple de escribir una operación una vez y hacer que se generalice a dimensiones superiores o inferiores?

Un ejemplo concreto es: supongamos que necesito calcular el gradiente de un campo de velocidad en el espacio espectral. En tres dimensiones, los bucles Fortran se verían así:

do k = 1, n
  do j = 1, n
    do i = 1, n
      phi(i,j,k) = ddx(i)*u(i,j,k) + ddx(j)*v(i,j,k) + ddx(k)*w(i,j,k)
    end do
  end do
end do

donde la ddxmatriz se define adecuadamente. (También se podría hacer esto con multiplicaciones matriciales). El código para un flujo bidimensional es casi exactamente el mismo, excepto: la tercera dimensión se elimina de los bucles, índices y número de componentes. ¿Hay una mejor manera de expresar esto?

Otro ejemplo es: supongamos que tengo velocidades de fluido definidas puntualmente en una cuadrícula tridimensional. Para interpolar la velocidad a una ubicación arbitraria (es decir, que no corresponde a los puntos de la cuadrícula), se puede utilizar el algoritmo unidimensional de Neville sucesivamente en las tres dimensiones (es decir, reducción dimensional). ¿Existe una manera fácil de hacer la reducción dimensional dada una implementación unidimensional de un algoritmo simple?

Matthew Emmett
fuente

Respuestas:

13

Observe cómo lo hace deal.II ( http://www.dealii.org/ ): allí, la independencia de la dimensión se encuentra en el corazón de la biblioteca y se modela como un argumento de plantilla para la mayoría de los tipos de datos. Consulte, por ejemplo, el solucionador de Laplace independiente de la dimensión en el programa tutorial del paso 4:

http://www.dealii.org/developer/doxygen/deal.II/step_4.html

Ver también

https://github.com/dealii/dealii/wiki/Frequency-Asked-Questions#why-use-templates-for-the-space-dimension

Wolfgang Bangerth
fuente
Estoy totalmente de acuerdo. No he encontrado un mejor enfoque que el que está haciendo Deal.II. Utilizan plantillas de una manera muy interesante para solucionar este problema.
Eldila
1
Un buen recurso, pero bastante intimidante si no compila plantillas C ++.
meawoppl
@Wolfgang Bangerth: ¿deal.ii define iteradores usando plantillas también?
Matthew Emmett
@MatthewEmmett: Sí.
Wolfgang Bangerth
@meawoppl: En realidad, no. Doy clases regularmente en Deal.II, y al principio simplemente les digo a los estudiantes que todo lo que dice ClassWhatever <2> está en 2d, ClassWhatever <3> está en 3d y ClassWhatever <dim> está en dim-d. Traigo la lección sobre las plantillas en algún lugar en la semana 3, y aunque lo más probable es que los estudiantes no entienden cómo funciona antes de eso, son completamente funcionales utilizando todos modos.
Wolfgang Bangerth
12

La pregunta destaca que la mayoría de los lenguajes de programación "simples" (C, Fortran, al menos) no le permiten hacer esto limpiamente. Una restricción adicional es que desea conveniencia de notación y buen rendimiento.

Por lo tanto, en lugar de escribir un código específico de dimensión, considere escribir un código que genere un código específico de dimensión. Este generador es independiente de la dimensión, incluso si el código de cálculo no lo es. En otras palabras, agrega una capa de razonamiento entre su notación y el código que expresa el cálculo. Las plantillas de C ++ equivalen a lo mismo: al revés, están integradas directamente en el lenguaje. Desventaja, son algo engorrosos de escribir. Esto reduce la pregunta de cómo realizar prácticamente el generador de código.

OpenCL le permite generar código en tiempo de ejecución de manera bastante limpia. También hace una división muy limpia entre 'programa de control externo' y 'bucles / núcleos internos'. El programa generador externo está mucho menos limitado al rendimiento y, por lo tanto, podría escribirse en un lenguaje cómodo, como Python. Esa es mi esperanza de cómo se usará PyOpenCL , perdón por el renovado enchufe descarado.

Andreas Klöckner
fuente
Andreas! ¡Bienvenido a scicomp! Me alegro de tenerte en el sitio, creo que sabes cómo ponerte en contacto conmigo si tienes alguna pregunta.
Aron Ahmadia
2
+10000 para la generación automática de código como solución a este problema en lugar de magia C ++.
Jeff
9

Esto se puede lograr en cualquier idioma con el siguiente prototipo mental aproximado:

  1. Cree una lista de las extensiones de cada dimensión (algo así como shape () en MATLAB, creo)
  2. Cree una lista de su ubicación actual en cada dimensión.
  3. Escriba un bucle sobre cada dimensión, que contenga un bucle sobre los cambios de tamaño basados ​​en el bucle externo.

A partir de ahí, se trata de luchar contra la sintaxis de su lenguaje específico para mantener su código compatible con nd.

Después de escribir un solucionador de dinámica de fluidos n-dimensional , descubrí que es útil tener un lenguaje que admita desempaquetar una lista como objeto como argumentos de una función. Es decir, a = (1,2,3) f (a *) -> f (1,2,3). Además, los iteradores avanzados (como ndenumerate en numpy) hacen que el código sea un orden de magnitud más limpio.

meawoppl
fuente
La sintaxis de Python para hacer esto se ve agradable y sucinta. Me pregunto si hay una buena manera de hacer esto con Fortran ...
Matthew Emmett
1
Es un poco doloroso lidiar con la memoria dinámica en Fortran. Probablemente mi mayor queja con el idioma.
meawoppl
5

norte1×norte2×norte3nortej=1

Arnold Neumaier
fuente
Por lo tanto, para ser independiente de la dimensión, su código debe escribirse para las dimensiones maxdim + 1, donde maxdim es la dimensión máxima posible que el usuario podría encontrar. Digamos maxdim = 100. ¿Qué tan útil es el código resultante?
Jeff
4

Las respuestas claras si desea mantener la velocidad de Fortran son usar un lenguaje que tenga una generación de código adecuada como Julia o C ++. Ya se han mencionado las plantillas de C ++, por lo que mencionaré las herramientas de Julia aquí. Las funciones generadas por Julia le permiten usar su metaprogramación para construir funciones a pedido a través de información de tipo. Así que esencialmente lo que puedes hacer aquí es hacer

@generated function f(x)
   N = ndims(x)
   quote
     # build the code for the function
   end
end

y luego usas el N para construir programáticamente el código que te gustaría ejecutar dado que es Ndimensional. Luego, la biblioteca cartesiana de Julia o paquetes como las expresiones Einsum.jl se pueden construir fácilmente para la Nfunción dimensional.

Lo bueno de Julia aquí es que esta función está compilada estáticamente y optimizada para cada nueva matriz dimensional que usa, por lo que no compilará más de lo que necesita, pero le dará la velocidad C / Fortran. Al final, esto es similar al uso de plantillas de C ++, pero es un lenguaje de nivel superior con muchas herramientas para hacerlo más fácil (lo suficientemente fácil como para que este sea un buen problema de tarea para un estudiante universitario).

Otro lenguaje que es bueno para esto es un Lisp como Common Lisp. Es fácil de usar, ya que, como Julia, le proporciona el AST compilado con muchas herramientas de introspección integradas, pero a diferencia de Julia, no lo compilará automáticamente (en la mayoría de las distribuciones).

Chris Rackauckas
fuente
1

Estoy en el mismo barco (Fortran). Una vez que tengo mis elementos 1D, 2D, 3D y 4D (hago geometría proyectiva), creo los mismos operadores para cada tipo y luego escribo mi lógica con ecuaciones de alto nivel que aclaran lo que está sucediendo. No es tan lento como parece tener bucles separados de cada operación y mucha copia de memoria. Dejo que el compilador / procesador haga las optimizaciones.

Por ejemplo

interface operator (.x.)
    module procedure cross_product_1x2
    module procedure cross_product_2x1
    module procedure cross_product_2x2
    module procedure cross_product_3x3
end interface 

subroutine cross_product_1x2(a,b,c)
    real(dp), intent(in) :: a(1), b(2)
    real(dp), intent(out) :: c(2)

    c = [ -a(1)*b(2), a(1)*b(1) ]
end subroutine

subroutine cross_product_2x1(a,b,c)
    real(dp), intent(in) :: a(2), b(1)
    real(dp), intent(out) :: c(2)

    c = [ a(2)*b(1), -a(1)*b(1) ]
end subroutine

subroutine cross_product_2x2(a,b,c)
    real(dp), intent(in) :: a(2), b(2)
    real(dp), intent(out) :: c(1)

    c = [ a(1)*b(2)-a(2)*b(1) ]
end subroutine

subroutine cross_product_3x3(a,b,c)
    real(dp), intent(in) :: a(3), b(3)
    real(dp), intent(out) :: c(3)

    c = [a(2)*b(3)-a(3)*b(2), a(3)*b(1)-a(1)*b(3), a(1)*b(2)-a(2)*b(1)]
end subroutine

Para ser utilizado en ecuaciones como

m = e .x. (r .x. g)  ! m = e×(r×g)

donde ee ry gpuede tener cualquier dimensión que tenga sentido matemático.

ja72
fuente