Efficient Execution of Sequential Instructions Streams by Physical Machines

Any computational model which relies on a physical system is likely to be subject to the fact that information density and speed have intrinsic, ultimate limits. The RAM model, and in particular the underlying assumption that memory accesses can be carried out in time independent from memory size itself, is not physically implementable. This work has developed in the field of limiting technology machines, in which it is somewhat provocatively assumed that technology has achieved the physical limits. The ultimate goal for this is to tackle the problem of the intrinsic latencies of physical systems by encouraging scalable organizations for processors and memories. An algorithmic study is presented, which depicts the implementation of high concurrency programs for SP and SPE, sequential machine models able to compute direct-flow programs in optimal time. Then, a novel pieplined, hierarchical memory organization is presented, with optimal latency and bandwidth for a physical system. In order to both take full advantage of the memory capabilities and exploit the available instruction level parallelism of the code to be executed, a novel processor model is developed. Particular care is put in devising an efficient information flow within the processor itself. Both designs are extremely scalable, as they are based on fixed capacity and fixed size nodes, which are connected as a multidimensional array. Performance analysis on the resulting machine design has led to the discovery that latencies internal to the processor can be the dominating source of complexity in instruction flow execution, which adds to the effects of processor-memory interaction. A characterization of instruction flows is then developed, which is based on the topology induced by instruction dependences.Qualsiasi modello computazionale basato su un sistema fisico e' verosimilmente soggetto al fatto che densita' e velocita' di propagazione dell’informazione sono intrinsecamente limitati. Per questo motivo, il modello RAM, in particolare per il presupposto che il costo di un accesso in memoria sia indipendente dalla taglia della stessa, non `e implementabile su sistemi fisici. Questo lavoro si inserisce nel contesto delle limiting technology machine, modelli computazionali in cui si ipotizza provocatoriamente di aver raggiunto con la tecnologia di fabbricazione i limiti fisici di densita' e velocita' dell’informazione. Questo, allo scopo di affrontare il problema delle latenze intrinseche a ogni sistema fisico evidenziando organizzazioni scalabili per processori e memorie. Viene quindi presentato uno studio algoritmico, che illustra l’implementazione di programmi a elevata concorrenza per SP ed SPE, modelli di macchine sequenziali in grado di eseguire programmi direct-flow in tempo ottimale. Successivamente, viene introdotta una innovativa organizzazione di memoria gerarchica e pipelined, con latenza e banda ottimali per un sistema fisico. Allo scopo di sfruttarne appieno le caratteristiche, e trarre vantaggio dall’eventuale instruction level parallelism del codice da eseguire, viene sviluppato un innovativo modello di processore. Particolare attenzione e' rivolta all’implementazione di un efficiente flusso di informazione all’interno del processore stesso. Entrambe le organizzazioni sono estremamente scalabili, in quanto basate su un insieme di nodi a taglia e capacita fisse, connessi con una topologia ad array multidimensionale. Lo studio delle prestazioni computazionali della macchina risultante ha evidenziato come le latenze interne al processore possono diventare la principale componente della complessita temporale per l’esecuzione di un flusso di istruzioni, che va ad aggiungersi all’effetto dell’interazione tra processore e memoria. Viene pertanto sviluppata una caratterizzazione dei flussi di istruzioni, basata sulla topologia indotta dalle dipendenze tra istruzioni