¿Podemos construir máquinas informáticas con operaciones elementales que demoren más que el tiempo constante en las máquinas actuales?

Imagine la placa que contiene una cuadrícula de clavijas N x N que se pueden subir o bajar mediante interruptores electrónicos. Usted especifica una matriz que define las clavijas que se generarán. La computadora es un procesador vectorial, por lo que puede digerir la matriz en una sola operación, elevando las clavijas relevantes simultáneamente, no secuencialmente. Si lo desea, haga que las clavijas contengan sensores que se activan si la banda elástica está en contacto con la clavija. Sí, porque es una cuadrícula que está cuantificada, pero puede definir que N sea lo suficientemente grande como para que sea continua dentro del error experimental. Debido a las propiedades mecánicas de los materiales, no puedes hacerlo mejor que eso de todos modos. Construir un procesador vectorial que pueda digerir una matriz de tal tamaño como una sola operación no sería trivial, pero ciertamente se puede hacer. Ahora ha transferido parte de la complejidad del problema a la complejidad de la máquina. Pero es un tipo diferente de complejidad.

Eso es lo divertido de la complejidad. Nunca se comporta como cabría esperar.

Aquí, el problema es un simple caso SIMD. Imagine una red tipo Transputer de tales procesadores vectoriales, cada uno con un conjunto completo de instrucciones pero ejecutando programas locales y no solo copias del original. En otras palabras, un entorno MIMD. Ahora, vamos un paso más allá y digamos que cada procesador tiene un conjunto arbitrario de registros internos de los que se puede seleccionar cualquier vector y una capa de traducción similar a Transmeta. (Se han jugado procesadores con memoria de almacenamiento dinámico y registros definidos por el usuario). En otras palabras, podemos imitar un número finito de instancias de una clase de objeto a nivel de procesador, con la lógica de la clase definida por la traducción.

En otras palabras, ahora tiene la capacidad de hacer MIMD sobre SIMD en procesadores vectoriales orientados a objetos. Sin embargo, el usuario no ve esa parte. El programador ve una máquina con un compilador para un lenguaje que es objetos puros y admite de forma nativa el modelo de actor para la paralelización explícita. ¿Tendrá eso diferentes métricas de rendimiento que las máquinas SISD multinúcleo modernas? No puedo ver cómo no pudo. No esperaría que una computadora de tiempo compartido de conmutación de tareas, que emula el paralelismo, tenga métricas similares a un sistema operativo preventivo en tiempo real en una computadora con subprocesos de 16 núcleos porque la emulación tiene su propio orden de complejidad y usted ‘ Lo he cambiado por completo. En mi máquina hipotética, prácticamente no hay emulación, el paralelismo es completamente nativo.

Esto es importante porque el algoritmo óptimo para diferentes tipos de emulación será diferente, para evitar las limitaciones. El algoritmo teóricamente óptimo seguirá siendo del mismo orden, siempre que no haga suposiciones. El procesamiento secuencial, a excepción de una tarea demostrablemente secuencial, es una suposición.

Se ha propuesto una máquina que podría factorizar números más rápido que las computadoras actuales: TWINKLE. Agrega muchos números en una sola instrucción midiendo la intensidad combinada de muchos LED diferentes.