Vergonzosamente paralelo
En computación paralela, una carga de trabajo o problema vergonzosamente paralelo (también llamado vergonzosamente paralelizable, perfectamente paralelo, deliciosamente paralelo o placenteramente paralelo) es aquel en el que se necesita poco o ningún esfuerzo para separar el problema en varias tareas paralelas.[1] Este suele ser el caso cuando hay poca o ninguna dependencia o necesidad de comunicación entre esas tareas paralelas, o de resultados entre ellas.[2]
Por tanto, son diferentes de los problemas de computación distribuida que necesitan comunicación entre tareas, especialmente comunicación de resultados intermedios. Son fáciles de realizar en granjas de servidores que carecen de la infraestructura especial utilizada en un verdadero cluster de supercomputadoras. Por tanto, se adaptan bien a las grandes plataformas de computación voluntaria basadas en Internet, como BOINC, y no sufren de ralentización paralela. Lo contrario de los problemas vergonzosamente paralelos son los problemas inherentemente seriales, que no pueden paralelizarse en absoluto.
Un ejemplo común de un problema vergonzosamente paralelo es el renderizado de vídeo 3D manejado por una unidad de procesamiento gráfico, donde cada fotograma (método de avance) o píxel (método de trazado de rayos) se puede manejar sin interdependencia.[3] Algunas formas de descifrado de contraseñas son otra tarea vergonzosamente paralela que se distribuye fácilmente en unidades centrales de procesamiento, núcleos de CPU o clústers.
Etimología
editar"Vergonzosamente" se utiliza aquí para referirse a problemas de paralelización que son "vergonzosamente fáciles".[4] El término puede implicar vergüenza por parte de los desarrolladores o compiladores: "Dado que muchos problemas importantes siguen sin resolverse debido principalmente a su complejidad computacional intrínseca, sería vergonzoso no desarrollar implementaciones paralelas de métodos de continuación de homotopía polinómica".[5] El término aparece por primera vez en la literatura en un libro de 1986 sobre multiprocesadores escrito por Cleve Moler, creador de MATLAB,[6] quien afirma haber inventado el término.[7]
Un término alternativo, agradablemente paralelo, ha ganado cierto uso, quizá para evitar las connotaciones negativas de la vergüenza en favor de una reflexión positiva sobre la paralelizabilidad de los problemas: "Por supuesto, estos programas no tienen nada de vergonzoso".[8]
Ejemplos
editarAlgunos ejemplos de problemas vergonzosamente paralelos son:
- Análisis Monte Carlo[9]
- Consultas distribuidas a bases de datos relacionales mediante procesamiento distribuido de conjuntos.
- Integración numérica[10]
- Servir archivos estáticos en un servidor web a varios usuarios a la vez
- Procesamiento masivo de archivos no relacionados de naturaleza similar en general, como redimensionamiento y conversión de galerías de fotos.
- El conjunto de Mandelbrot, el ruido Perlin e imágenes similares, en las que cada punto se calcula de forma independiente.
- Renderizado de gráficos por computadora. En animación por computadora, cada fotograma o píxel puede renderizarse independientemente (véase renderización paralela).
- Algunas búsquedas de fuerza bruta en criptografía.[11] Ejemplos notables en el mundo real incluyen los sistemas distributed.net y proof-of-work utilizados en criptodivisas.
- Búsquedas BLAST en bioinformática con bases de datos divididas.[12]
- Sistemas de reconocimiento facial a gran escala que comparan miles de rostros adquiridos arbitrariamente (por ejemplo, un vídeo de seguridad o de vigilancia a través de un circuito cerrado de televisión) con un número similar de rostros almacenados previamente (por ejemplo, una galería de pícaros o una lista de vigilancia similar).[13]
- Simulaciones por ordenador que comparan muchos escenarios independientes.
- Algoritmos genéticos.[14]
- Cálculos conjuntos de predicción meteorológica numérica.
- Simulación y reconstrucción de eventos en física de partículas.
- El algoritmo de los cuadrados móviles.
- El algoritmo de tamizado cuadrático y del tamiz de campo numérico.
- Etapa de crecimiento del árbol de la técnica de aprendizaje automático de bosque aleatorio.
- Transformada discreta de Fourier en la que cada armónico se calcula de forma independiente.
- Redes neuronales convolucionales ejecutadas en GPU.
- Búsqueda de hiperparámetros en el aprendizaje automático
- Búsqueda paralela en la programación con restricciones[15]
Aplicaciones
editar- En R (lenguaje de programación) - El paquete Simple Network of Workstations (SNOW) implementa un mecanismo sencillo para utilizar un conjunto de estaciones de trabajo o un clúster Beowulf para cálculos vergonzosamente paralelos.[16] Paquetes similares de R incluyen "future", "parallel" y otros.
Véase también
editar- La ley de Amdahl define el valor P, que sería casi o exactamente igual a 1 para problemas vergonzosamente paralelos.
- Mapa (patrón paralelo)
- Multiprocesamiento
- Paralelismo masivo
- Computación paralela
- Programación orientada a procesos
- Arquitectura compartida (SN)
- Multiprocesamiento simétrico (SMP)
- Máquina de conexión
- Autómata celular
- Marco CUDA
- Procesador multinúcleo
- Procesador vectorial
Referencias
editar- ↑ Herlihy, Maurice; Shavit, Nir (25 de junio de 2012). The Art of Multiprocessor Programming, Revised Reprint (en inglés). Elsevier. ISBN 978-0-12-397795-3. Consultado el 18 de septiembre de 2023.
- ↑ Section 1.4.4 of: Foster, Ian (1995). «Designing and Building Parallel Programs». Addison–Wesley. ISBN 9780201575941. Archivado desde el original el 1 de marzo de 2011. Consultado el 19 de septiembre de 2023.
- ↑ Chalmers, Alan; Reinhard, Erik; Davis, Tim (26 de junio de 2002). Practical Parallel Rendering (en inglés). CRC Press. ISBN 978-1-4398-6380-0. Consultado el 18 de septiembre de 2023.
- ↑ Matloff, Norman (2011). «The Art of R Programming: A Tour of Statistical Software Design». No Starch: 347. ISBN 9781593274108.
- ↑ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). «Parallel Homotopy Algorithms to Solve Polynomial Systems». Mathematical Software - ICMS 2006: 225-234. ISBN 978-3-540-38084-9. doi:10.1007/11832225_22.
- ↑ Moler, Cleve (1986). Heath, Michael T. (1986). Matrix Computation on Distributed Memory Multiprocessors. ISBN 978-0898712094.
- ↑ «The Intel Hypercube, part 2, reposted». Cleve’s Corner: Cleve Moler on Mathematics and Computing (en inglés). 12 de noviembre de 2013. Consultado el 19 de septiembre de 2023.
- ↑ Kepner, Jeremy (2009). «Parallel MATLAB for Multicore and Multinode Computers». SIAM. ISBN 9780898716733.
- ↑ Kontoghiorghes, Erricos John (21 de diciembre de 2005). Handbook of Parallel Computing and Statistics (en inglés). CRC Press. ISBN 978-1-4200-2868-3. Consultado el 19 de septiembre de 2023.
- ↑ Deng, Yuefan (2013). Applied Parallel Computing (en inglés). World Scientific. ISBN 978-981-4307-60-4. Consultado el 19 de septiembre de 2023.
- ↑ Percival, Colin; Josefsson, Simon (2016-08). The scrypt Password-Based Key Derivation Function (RFC 7914). Internet Engineering Task Force. Consultado el 19 de septiembre de 2023.
- ↑ Mathog, David R. (22 de septiembre de 2003). «Parallel BLAST on split databases». Bioinformatics 19 (14): 1865-1866. ISSN 1367-4811. doi:10.1093/bioinformatics/btg250. Consultado el 19 de septiembre de 2023.
- ↑ «How We Made Our Face Recognizer 25x Faster by Louis Brandy». lbrandy.com. Consultado el 19 de septiembre de 2023.
- ↑ Tsutsui, Shigeyoshi; Collet, Pierre (5 de diciembre de 2013). Massively Parallel Evolutionary Computation on GPGPUs (en inglés). Springer Science & Business Media. ISBN 978-3-642-37959-8. Consultado el 19 de septiembre de 2023.
- ↑ Hamadi, Youssef; Sais, Lakhdar (5 de abril de 2018). Handbook of Parallel Constraint Reasoning (en inglés). Springer. ISBN 978-3-319-63516-3. Consultado el 19 de septiembre de 2023.
- ↑ «cluster.nw». homepage.divms.uiowa.edu. Consultado el 19 de septiembre de 2023.