Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Milani, Emanuele (2014) Efficient Execution of Sequential Instructions Streams by Physical Machines. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF
528Kb

Abstract (inglese)

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.

Abstract (italiano)

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.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Gianfranco, Bilardi
Dottorato (corsi e scuole):Ciclo 25 > Scuole 25 > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:28 Gennaio 2014
Anno di Pubblicazione:28 Gennaio 2014
Parole chiave (italiano / inglese):memory hierarchy pipelined locality concurrency algorithm computational models limiting technology machine instruction dependence instruction level parallelism
Settori scientifico-disciplinari MIUR:Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:6530
Depositato il:19 Mag 2015 16:11
Simple Metadata
Full Metadata
EndNote Format

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione.

[1] A. Aggarwal, B. Alpern, A. Chandra, and M. Snir. A model for hierarchical memory. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, STOC ’87, pages 305–314, New York, NY, USA, 1987. ACM. Cerca con Google

[2] A. Aggarwal, A. K. Chandra, and M. Snir. Hierarchical memory with block transfer. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, SFCS ’87, pages 204–216, Washington, DC, USA, 1987. Cerca con Google

IEEE Computer Society. Cerca con Google

[3] Gene M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In AFIPS Spring Joint Computing Conference, pages 483–485, 1967. Cerca con Google

[4] G. Bilardi, K. Ekanadham, and P. Pattnaik. On approximating the ideal random access machine by physical machines. J. ACM, 56(5):27:1–27:57,August 2009. Cerca con Google

[5] G. Bilardi and F. P. Preparata. Horizons of parallel computation. Journal of Parallel and Distributed Computing, 27:172–182, 1993. Cerca con Google

[6] Gianfranco Bilardi and Franco P. Preparata. Processor-time tradeoffs under bounded-speed message propagation: Part i, upper bounds. Theory Comput. Syst., 30(6):523–546, 1997. Cerca con Google

[7] R. P. Brent. The parallel evaluation of general arithmetic expressions. J.ACM, 21(2):201–206, April 1974. Cerca con Google

[8] Robert J. Collins. Multiple instruction multiple data emulation on the connection machine. Technical Report CSD-910004, University of California (Los Angeles, CA US), 1991. Cerca con Google

[9] Steven Fortune and James Wyllie. Parallelism in random access machines.In Proceedings of the tenth annual ACM symposium on Theory of computing,STOC ’78, pages 114–118, New York, NY, USA, 1978. ACM. Cerca con Google

[10] Leslie M. Goldschlager. A unified approach to models of synchronous parallel machines. In Proceedings of the tenth annual ACM symposium on Theory of computing, STOC ’78, pages 89–94, New York, NY, USA, 1978. ACM. Cerca con Google

[11] Joseph J´aJ´a. An introduction to parallel algorithms. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1992. Cerca con Google

[12] D. E. Knuth, J. H. Jr. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323–350, 1977. Cerca con Google

[13] C. P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. Comput., 32(10):942–946, October 1983. Cerca con Google

[14] Fabrizio Luccio and Linda Pagli. A model of sequential computation with pipelines access to memory. Mathematical Systems Theory, 26(4):343–356, 1993. Cerca con Google

[15] Emanuele Milani and Nicola Zago. Exploiting fine grained parallelism on the spe. ICTCS 2012, 2012. Cerca con Google

[16] Clark D. Thompson and H. T. Kung. Sorting on a mesh-connected parallel computer. Commun. ACM, 20(4):263–271, 1977. Cerca con Google

[17] Jeffrey Scott Vitter. External memory algorithms. In Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci, editors, Algorithms - ESA ’98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings, volume 1461 of Lecture Notes in Computer Science, pages 1–25. Springer, 1998. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record