¿Hay algún algoritmo que sea muy difícil de paralelizar o la investigación aún está activa?
Quería saber sobre cualquier algoritmo o cualquier campo de investigación en computación paralela.
Todo lo que busqué tiene una implementación "paralela". Solo quiero estudiar un poco sobre cualquier campo de computación paralela inexplorado.
algorithms
parallel-computing
Protón polinomial
fuente
fuente
Respuestas:
Esto es básicamente un problema de investigación abierto relacionado con la pregunta NC =? P donde NC se toma como la clase de algoritmos eficientemente paralelizables.
En una encuesta influyente / amplia de Berkeley "el panorama de la computación paralela" , hay clases de algoritmos o patrones de paralelismo separados en "enanos". de los primeros 6 identificados, parece que los problemas de cuerpos pueden ser relativamente difíciles de paralelizar de manera eficiente a medida que aumenta n porque hay n 2 interacciones entre todos los n puntos.norte norte norte2 norte
ver también hay algoritmos famosos en sci. comp. que no se pueden paralelizar , scicomp.se
fuente
Este artículo presenta una serie de problemas que son fáciles de resolver secuencialmente pero difíciles de paralelizar: http://en.wikipedia.org/wiki/P-complete
El problema del valor del circuito ("dado un circuito booleano + su entrada, decir lo que emite") es un buen punto de partida: fácil de entender, fácil de resolver con algoritmos secuenciales, y nadie sabe si se puede paralelizar de manera eficiente.
fuente
Desde una perspectiva práctica, está preguntando acerca de algoritmos inherentemente secuenciales. Hay muchos candidatos, como el encadenamiento hash, que se cree que es muy difícil de paralelizar. El encadenamiento de hash se usa ampliamente en criptografía. Por ejemplo, el esquema de hash de contraseña bcrypt fue diseñado para intentar dificultar la aceleración del hash a través de la paralelización. Otro ejemplo es la cuadratura repetida (nuevamente, en criptografía).
fuente