¿Hay algún "umbral" que justifique el cálculo multiproceso?

Question

Así que, básicamente, necesitaba optimizar este código hoy. Se trata de encontrar la secuencia más larga producida por alguna función en los primeros números de millones de partida:

public static void main(String[] args) { 
    int mostLen = 0; 
    int mostInt = 0; 
    long currTime = System.currentTimeMillis(); 
    for(int j=2; j<=1000000; j++) { 
     long i = j; 
     int len = 0; 
     while((i=next(i)) != 1) { 
      len++; 
     } 
     if(len > mostLen) { 
      mostLen = len; 
      mostInt = j; 
     } 
    } 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 


static long next(long i) { 
    if(i%2==0) { 
     return i/2; 
    } else { 
     return i*3+1; 
    } 
} 

Mi error fue tratar de introducir multihilo:

void doSearch() throws ExecutionException, InterruptedException { 
    final int numProc = Runtime.getRuntime().availableProcessors(); 
    System.out.println("numProc = " + numProc); 
    ExecutorService executor = Executors.newFixedThreadPool(numProc); 
    long currTime = System.currentTimeMillis(); 
    List<Future<ValueBean>> list = new ArrayList<Future<ValueBean>>(); 
    for (int j = 2; j <= 1000000; j++) { 
     MyCallable<ValueBean> worker = new MyCallable<ValueBean>(); 
     worker.setBean(new ValueBean(j, 0)); 
     Future<ValueBean> f = executor.submit(worker); 
     list.add(f); 
    } 
    System.out.println(System.currentTimeMillis() - currTime); 

    int mostLen = 0; 
    int mostInt = 0; 
    for (Future<ValueBean> f : list) { 
     final int len = f.get().getLen(); 
     if (len > mostLen) { 
      mostLen = len; 
      mostInt = f.get().getNum(); 
     } 
    } 
    executor.shutdown(); 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 

public class MyCallable<T> implements Callable<ValueBean> { 
    public ValueBean bean; 

    public void setBean(ValueBean bean) { 
     this.bean = bean; 
    } 

    public ValueBean call() throws Exception { 
     long i = bean.getNum(); 
     int len = 0; 
     while ((i = next(i)) != 1) { 
      len++; 
     } 
     return new ValueBean(bean.getNum(), len); 
    } 
} 

public class ValueBean { 
    int num; 
    int len; 

    public ValueBean(int num, int len) { 
     this.num = num; 
     this.len = len; 
    } 

    public int getNum() { 
     return num; 
    } 

    public int getLen() { 
     return len; 
    } 
} 

long next(long i) { 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

Por desgracia, la versión multiproceso trabajó 5 veces más lento que el single-threaded en 4 procesadores (núcleos).

Luego probé un poco más de enfoque crudo:

static int mostLen = 0; 
static int mostInt = 0; 

synchronized static void updateIfMore(int len, int intgr) { 
    if (len > mostLen) { 
     mostLen = len; 
     mostInt = intgr; 
    } 
} 

public static void main(String[] args) throws InterruptedException { 
    long currTime = System.currentTimeMillis(); 
    final int numProc = Runtime.getRuntime().availableProcessors(); 
    System.out.println("numProc = " + numProc); 
    ExecutorService executor = Executors.newFixedThreadPool(numProc); 
    for (int i = 2; i <= 1000000; i++) { 
     final int j = i; 
     executor.execute(new Runnable() { 
      public void run() { 
       long l = j; 
       int len = 0; 
       while ((l = next(l)) != 1) { 
        len++; 
       } 
       updateIfMore(len, j); 
      } 
     }); 
    } 
    executor.shutdown(); 
    executor.awaitTermination(30, TimeUnit.SECONDS); 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 


static long next(long i) { 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

y funcionó mucho más rápido, pero aún así, era más lento que el enfoque de un solo hilo.

Espero que no sea porque haya estropeado la forma en que estoy haciendo multihilo, sino que este cálculo/algoritmo en particular no es una buena opción para el cálculo en paralelo. Si cambio de cálculo para que sea más intensivo del procesador mediante la sustitución método next con:

long next(long i) { 
    Random r = new Random(); 
    for(int j=0; j<10; j++) { 
     r.nextLong(); 
    } 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

ambas versiones multiproceso empiezan a ejecutar más de dos veces más rápido que la versión singlethreaded en una máquina de 4 núcleos.

Así que está claro que debe haber algún umbral que se puede utilizar para determinar si vale la pena introducir multihilo y mi pregunta es:

¿Cuál es la norma básica que ayudar a decidir si un determinado cálculo es lo suficientemente intensiva para ser optimizado ejecutándolo en paralelo (sin gastar esfuerzo para implementarlo realmente?)

Answer 1

Creo que hay otro componente que no está considerando. La paralelización funciona mejor cuando las unidades de trabajo no dependen entre sí. Ejecutar un cálculo en paralelo no es óptimo cuando los resultados del cálculo posterior dependen de los resultados del cálculo anterior. La dependencia podría ser fuerte en el sentido de "Necesito el primer valor para calcular el segundo valor". En ese caso, la tarea es completamente en serie y los valores posteriores no se pueden calcular sin esperar cálculos anteriores. También podría haber una dependencia más débil en el sentido de "Si tuviera el primer valor podría calcular el segundo valor más rápido". En ese caso, el costo de la paralelización es que algunos trabajos pueden duplicarse.

Este problema se puede optimizar sin multihilo porque algunos de los valores posteriores se pueden calcular más rápido si ya tiene los resultados previos disponibles. Tome, por ejemplo, j == 4. Una vez que el ciclo interno produce i == 2, pero acaba de calcular el resultado para j == 2 hace dos iteraciones, si guardó el valor de len puede calcularlo como len (4) = 1 + len (2).

Utilizando una matriz para almacenar los valores previamente calculados de len y un poco moviéndose en el método next, puede completar la tarea> 50 veces más rápido.

Answer 2

"¿El rendimiento será mayor que el costo de cambio de contexto y creación de subprocesos?"

Eso es un costo muy dependiente del sistema operativo, el idioma y el hardware; this question tiene alguna discusión sobre el costo en Java, pero tiene algunos números y algunos consejos sobre cómo calcular el costo.

También desea tener un hilo por CPU, o menos, para el trabajo intensivo de la CPU. Gracias a David Harkness por el puntero to a thread on how to work out that number.

Answer 3

La clave para implementar eficientemente el multihilo es asegurarse de que el costo no sea demasiado alto. No hay reglas fijas, ya que dependen en gran medida de su hardware.

Arrancar y detener roscas tiene un alto costo. Por supuesto, ya usó el servicio de ejecutor, que reduce estos costos considerablemente porque usa un montón de subprocesos de trabajo para ejecutar sus Runnables. Sin embargo, cada Runnable todavía viene con algunos gastos generales. Reducir el número de ejecutables y aumentar la cantidad de trabajo que cada uno tiene que hacer mejorará el rendimiento, pero aún desea tener suficientes ejecutables para el servicio del ejecutor para distribuirlos de manera eficiente sobre los subprocesos de trabajo.

Ha elegido crear un ejecutable para cada valor de inicio para que termine creando 1000000 ejecutables. Probablemente obtendrás resultados mucho mejores si permites que cada Runnable haga un lote de, digamos, 1000 valores de inicio. Lo que significa que solo necesita 1000 ejecutables que reducen en gran medida la sobrecarga.

Answer 4

Estimar la cantidad de trabajo que un hilo puede hacer sin interacción con otros hilos (directamente o a través de datos comunes). Si ese trabajo puede completarse en 1 microsegundo o menos, la sobrecarga es demasiado y el multihilo no sirve. Si es de 1 milisegundo o más, el multihilo debería funcionar bien. Si está en el medio, se requieren pruebas experimentales.