punto - Paralelo al bucle while con OpenMP

pragma omp parallel

Question

Tengo un archivo de datos muy grande, y cada registro en este archivo de datos tiene 4 líneas. He escrito un programa C muy simple para analizar archivos de este tipo e imprimir información útil. La idea básica del programa es esto.

int main()
{
  char buffer[BUFFER_SIZE];
  while(fgets(buffer, BUFFER_SIZE, stdin))
  {
    fgets(buffer, BUFFER_SIZE, stdin);
    do_some_simple_processing_on_the_second_line_of_the_record(buffer);
    fgets(buffer, BUFFER_SIZE, stdin);
    fgets(buffer, BUFFER_SIZE, stdin);
  }
  print_out_result();
}

Esto, por supuesto, deja de lado algunos detalles (comprobación de cordura / error, etc.), pero eso no es relevante para la pregunta.

El programa funciona bien, pero los archivos de datos con los que estoy trabajando son enormes. Pensé que trataría de acelerar el programa paralelizando el ciclo con OpenMP. Sin embargo, después de un poco de búsqueda, parece que OpenMP solo puede manejar bucles donde el número de iteraciones se conoce de antemano. Como no conozco el tamaño de los archivos de antemano, e incluso comandos simples como wc -l toman mucho tiempo para ejecutarse, ¿cómo puedo paralelizar este programa?

Answer 1

¿Ha comprobado que su proceso está realmente vinculado a la CPU y no vinculado a E / S? Su código se parece mucho al código vinculado a E / S, que no ganaría nada con la paralelización.

Answer 2

Como mencionó Thiton, este código podría estar limitado por E / S. Sin embargo, en la actualidad, muchas computadoras pueden tener SSD y discos RAID de alto rendimiento. En tal caso, puede obtener aceleración de la paralelización. Además, si el cálculo no es trivial, entonces se paralelizan las ganancias. Incluso si la E / S se serializa de manera efectiva debido al ancho de banda saturado, aún puede obtener una aceleración distribuyendo el cálculo a multinúcleo.

Volviendo a la pregunta en sí, puedes paralelizar este ciclo mediante OpenMP. Con stdin , no tengo idea de paralelizar porque necesita leerse secuencialmente y sin información previa del final. Sin embargo, si está trabajando en un archivo típico, puede hacerlo.

Aquí está mi código con omp parallel . Utilicé algunos Win32 API y MSVC CRT:

void test_io2()
{
  const static int BUFFER_SIZE = 1024;
  const static int CONCURRENCY = 4;

  uint64_t local_checksums[CONCURRENCY];
  uint64_t local_reads[CONCURRENCY];

  DWORD start = GetTickCount();

  omp_set_num_threads(CONCURRENCY);

  #pragma omp parallel
  {
    int tid = omp_get_thread_num();

    FILE* file = fopen("huge_file.dat", "rb");
    _fseeki64(file, 0, SEEK_END);
    uint64_t total_size = _ftelli64(file);

    uint64_t my_start_pos = total_size/CONCURRENCY * tid;
    uint64_t my_end_pos   = min((total_size/CONCURRENCY * (tid + 1)), total_size);
    uint64_t my_read_size = my_end_pos - my_start_pos;
    _fseeki64(file, my_start_pos, SEEK_SET);

    char* buffer = new char[BUFFER_SIZE];

    uint64_t local_checksum = 0;
    uint64_t local_read = 0;
    size_t read_bytes;
    while ((read_bytes = fread(buffer, 1, min(my_read_size, BUFFER_SIZE), file)) != 0 &&
      my_read_size != 0)
    {
      local_read += read_bytes;
      my_read_size -= read_bytes;
      for (int i = 0; i < read_bytes; ++i)
        local_checksum += (buffer[i]);
    }

    local_checksums[tid] = local_checksum;
    local_reads[tid]     = local_read;

    fclose(file);
  }

  uint64_t checksum = 0;
  uint64_t total_read = 0;
  for (int i = 0; i < CONCURRENCY; ++i)
    checksum += local_checksums[i], total_read += local_reads[i];

  std::cout << checksum << std::endl
    << total_read << std::endl
    << double(GetTickCount() - start)/1000. << std::endl;
}

Este código se ve un poco sucio porque necesitaba distribuir con precisión la cantidad de archivo que se debe leer. Sin embargo, el código es bastante directo. Una cosa a tener en cuenta es que necesita tener un puntero de archivo por subproceso. No puede simplemente compartir un puntero de archivo porque la estructura de datos interna puede no ser segura para subprocesos. Además, este código puede ser paralelizado por parallel for . Pero, creo que este enfoque es más natural.

Resultados experimentales simples

He probado este código para leer un archivo de 10 GB en un HDD (WD Green 2TB) y un SSD (Intel 120 GB).

Con un HDD, sí, no se obtuvieron aceleraciones. Incluso se observó desaceleración. Esto muestra claramente que este código está limitado por E / S. Este código virtualmente no tiene cómputo. Solo E / S.

Sin embargo, con una SSD, tuve una aceleración de 1.2 con 4 núcleos. Sí, la aceleración es pequeña. Pero aún puede obtenerlo con SSD. Y, si el cálculo se vuelve un poco más (simplemente pongo un ciclo muy corto de espera ocupada), las aceleraciones serían significativas. Pude obtener una aceleración de 2.5.

En resumen, me gustaría recomendar que intentes paralelizar este código.

Además, si el cálculo no es trivial, recomendaría pipelining . El código anterior simplemente se divide en varios trozos grandes, lo que resulta en una pobre eficacia de caché. Sin embargo, la paralelización de canalizaciones puede producir una mejor utilización de la memoria caché. Intente utilizar TBB para la paralelización de canalizaciones. Proporcionan una construcción de tubería simple.

Answer 3

En respuesta a "importar", no creo que tu código realmente optimice nada aquí. Hay una gran cantidad de malentendidos comunes sobre esta afirmación "#pragma omp parallel", esta en realidad generará los hilos, sin la palabra clave "for", todos los hilos ejecutarán los códigos que siguen. Entonces su código en realidad estaría duplicando el cálculo en cada hilo. En respuesta a Daniel, tenías razón, OpenMP no puede optimizar mientras está en bucle, la única forma de optimizarlo es reestructurando el código para que la iteración se conozca de antemano (por ejemplo, mientras se repite una vez con un contador). Perdón por publicar otra respuesta, ya que aún no puedo hacer ningún comentario, pero con suerte, esto borra los malentendidos comunes.