¿Por qué las computadoras no vienen con hardware especializado como ordenar redes?

10

En lugar de programar de la manera en que lo hacemos, ¿por qué no hacemos especificaciones de tareas comunes como "ordenar" y luego dejamos que el entorno lo compile para aprovechar al máximo su hardware? De esta manera, podríamos enviar computadoras con nuevo hardware especializado, como clasificar redes, y funcionaría automáticamente con el código existente.

MaiaVictor
fuente
2
Compre una placa PCI FPGA e implemente las extensiones que desee.
SK-logic
El hardware no es mágico. Muchas cosas no pueden acelerarse mucho (o en absoluto) mediante hardware especializado, e incluso si puede, el hardware existente a menudo tiene que adaptarse (o al menos volver a compilarse). Consulte yosefk.com/blog/its-done-in-hardware-so-its-cheap.html
3
@WorldEngineer No veo cómo eso entra en escena. Su usuario promedio no sabe para qué sirve el 80% de las cosas en una CPU moderna, está contento porque le dicen que hace que sus programas sean más rápidos (y esto tiene un núcleo de verdad). Si la clasificación fuera tan común como supone OP y podría optimizarse con hardware dedicado, lo pondrían al lado del predictor de rama ("¿qué es eso, jardinería?"), Emitir un comunicado de prensa diciendo que hicieron aplicaciones X e Y 5% más rápido y véndelo.
1
Esto me recuerda la idea de los núcleos de conservación , que están destinados a la eficiencia energética en lugar del rendimiento máximo.
Paul A. Clayton el

Respuestas:

19

En primer lugar, las computadoras vienen con hardware especializado . Cada computadora portátil y de escritorio vendida durante varios años ahora tiene un coprocesador especializado, una Unidad de procesamiento de gráficos, que maneja algoritmos de procesamiento visual, como lo requieren las aplicaciones de video y juegos. Equipos muy grandes ( por ejemplo , "superordenadores", familia de System z de IBM) tienen una variedad de procesadores especializados para manejar el procesamiento numérico ( "proceso de vectores"), etc .

En segundo lugar, la clasificación es uno de los aspectos mejor investigados de la informática, y resulta ser demasiado complejo para integrarlo en el hardware por más que los casos más simples. La clasificación tiene que ver con la velocidad y la corrección. La velocidad depende de la elección del algoritmo, el tipo y la variación de los datos y el volumen de datos. La corrección depende del tipo y contexto de los datos. Es positivamente trivial clasificar una matriz de enteros de tamaño mediano que se ajuste al tamaño de palabra nativa de la CPU ( p . Ej., 31 o 63 bits más signo). Ordenar cadenas de caracteres que contienen más que simples valores ASCII es extremadamente complejo: IBM publicó un libro de más de 500 páginas hace 20 años simplemente discutiendo los problemas de los juegos de caracteres en el contexto de las fronteras nacionales y el uso común. Y luego está la cuestión de los datos no contiguos: ordenar una lista vinculada implica perseguir punteros por toda la memoria.

Ross Patterson
fuente
10

El problema principal es que los algoritmos de clasificación (1) necesitan mucha flexibilidad y (2) sería muy difícil acelerar el uso de hardware de todos modos.

Una cosa es que los algoritmos de clasificación ya son lo suficientemente rápidos como para superar el ancho de banda de la memoria del procesador: el procesador ya pasará una gran parte de su tiempo esperando que los datos se muevan hacia atrás y hacia adelante a la memoria principal. Un coprocesador de clasificación acelerado por hardware o una instrucción de clasificación especial tendrían el mismo problema.

La forma en que se aborda este ancho de banda de memoria es mediante el uso de mejores algoritmos y estructuras de datos que tienen una mejor "localidad", y todavía se está realizando un trabajo significativo en este campo, particularmente "algoritmos ajenos a la memoria caché" (son ajenos en el sentido de que funcionan bien independientemente de los detalles del almacenamiento en caché, mientras que los algoritmos "conscientes de caché" están ajustados para un tamaño de página de caché particular, etc.

En contraste, las aplicaciones de medios (audio y gráficos, particularmente gráficos en 3D) hacen uso de algunas estructuras muy repetitivas; por supuesto, hay flexibilidad, pero está construido sobre una base grande y muy bien estructurada. Eso permitió que la aceleración de gráficos comenzara de manera simple con cosas como Blitting (una operación de copia en bloque configurable pero aún muy estructurada) y dibujo de línea / polígono. Significaba que a medida que los gráficos y el procesamiento de sonido se volvían más sofisticados, las operaciones vectoriales se convirtieron en un objetivo obvio para la optimización: primero MMX (vectores de enteros) y luego SSE (vectores de flotadores). Significaba que había una estructura bastante bien definida de cómo funcionaba un motor de gráficos 3D cuando la antigua tubería de gráficos 3D de función fija se movía al hardware de gráficos 3D.

Sin embargo, con los gráficos en 3D, lo que una vez se hizo en hardware ahora se hace en software por flexibilidad: los sombreadores son software, por ejemplo, y así es como obtenemos una amplia gama de diferentes sombreadores que dan la apariencia de diferentes materiales. Sin embargo, ese software todavía funciona de una manera mucho más estructurada que el software general y, por lo tanto, todavía puede usar una plataforma de hardware mucho más especializada. Es por eso que su tarjeta gráfica ahora puede acelerar todo, desde física hasta descifrar contraseñas, aplicaciones que también se ajustan al mismo modelo y pueden implementarse eficientemente utilizando los conjuntos de instrucciones que proporcionan los procesadores gráficos modernos.

Los procesadores gráficos ahora son descendientes espirituales o reales de los procesadores de señales digitales, que eran (y probablemente aún lo son) un tipo de procesador especializado para manejar señales digitales (por ejemplo, audio).

Lo que lleva a un punto final: los algoritmos de clasificación pueden acelerarse por hardware. Dependiendo de sus datos, la ordenación puede manejarse usando instrucciones MMX o SSE (instrucción única-datos múltiples) en su procesador, pero probablemente no tenga mucho sentido debido al problema del ancho de banda de la memoria; tal vez pueda ser un poco más eficiente en cuanto a consumo de energía de esa manera, sin embargo. Sin embargo, también podría usar su hardware de gráficos. De esa manera, puede beneficiarse del ancho de banda de memoria, a menudo mucho mejor, para las tarjetas gráficas. No podrá reemplazar todo tipo de esta manera, pero ciertamente es posible y probablemente se haga cuando sea apropiado.

IOW debido a los diversos problemas económicos y prácticos, el diseño de hardware específicamente para acelerar una tarea relativamente estrecha como la clasificación realmente no tiene sentido. Una característica que acelera una gama más amplia de tareas, o que hace que el hardware de aceleración existente sea aplicable a una gama más amplia de tareas, a menudo tiene mucho más sentido.

Steve314
fuente
3

¡Pero lo hacen! Se llaman extensiones de conjunto de instrucciones. (Cosas como SSE y similares)

Ciertas tareas tienen implementaciones muy buenas en software. Por lo general, esas implementaciones son lo suficientemente buenas como para hacer el trabajo, por lo que no se necesita hardware especializado. Si hiciera algún tipo de hardware especializado, necesitaría tener una amplia gama de aplicaciones para que valga la pena.

Si observa el hardware que podría hacer que esto funcione, supongo que estaría viendo algo como FPGA. Como puede ver con los FPGA, el chip se volvería mucho más costoso y no sería aplicable para muchas aplicaciones.

En ningún
fuente
Tendré que buscar en Google SSE, pero, de antemano, la clasificación es probablemente universal. ¿Se implementa a nivel de hardware?
MaiaVictor
Eh también, como estamos allí, ¿recomendarías libros?
MaiaVictor
Estaba hablando de optimizaciones específicas de trabajo que se implementan en procesadores de estilo de CPU en general, ya que las redes de clasificación se usan como ejemplo. No sé si SSE o cualquier otro conjunto de instrucciones incluye ordenar optimizaciones específicas. Hice redes de clasificación de Google, y dado que hay implementaciones generales optimizadas, creo que las implementaciones de software podrían funcionar igual de bien si la implementación se realiza correctamente.
Onno
Debo señalar que la mayoría de las extensiones del conjunto de instrucciones operan en un nivel más bajo que la red de clasificación que usó como ejemplo, pero no es imposible diseñar una optimización de registro múltiple que pueda hacer la clasificación de esta manera. Pero la pregunta para los fabricantes de CPU sería: "¿pagaría lo suficiente como para justificar el costo?".
Onno