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

| Crea un account

Zago, Nicola (2015) Time Lower Bounds for Parallel Network Computations. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF (Time Lower Bounds for Parallel Network Computations) - Versione sottomessa
977Kb

Abstract (inglese)

Direct Acyclic Graphs (DAGs) are a suitable way to describe computations, expressing precedence constraints among operations. Beyond the representation of the execution of an algorithm, a DAG can effectively represent the execution of a parallel network. This last kind of DAG has a regular structure, consisting in the repetition over time of the original network; these common representations suggest a possible uniform approach in the study of execution of algorithms and emulation of networks.
Both in parallel computing and computational complexity, DAGs have been extensively employed in the study of algorithmic features, as lower bounds for the execution/emulation time of algorithms/networks, the minimum quantity of memory needed for computing an algorithm or the minimum I/O complexity of an algorithm given a certain amount of fast memory cells. Developed techniques are quite different in their assumptions; one of the more fundamental differences is that some of them allow recomputation of intermediate results, while others disallow it, requiring the storage in memory of intermediate results for their further usages.
In nowadays computations the trade-off between data recomputation and data storing is important both in parallel and in local elaborations, since in the former we can increase the bandwidth and reduce the latency with whom data can be accessed (by computing the same data in several points of the network), while in the latter we can avoid to pay the latency of the access in memory to reload data, by recomputing them possibly loading fewer data or using data already present in memory.
So far it does not exist an universal technique able to foresee the strict lower bound for each execution of algorithm or emulation of network in each network and the known results derive from several theorems. On the contrary there are a lot of cases for which it neither exists a tight result; among these there are also emulations of extensively studied networks, such as multidimensional arrays.
The first part of our thesis starts from this state-of-the-art: we propose a survey of several known lower bound techniques involving DAGs, followed by original theorems which clarify or solve open problems. In particular, in our survey we consider lower bound techniques for execution of algorithms and emulation of networks in parallel networks, showing their principles and their limits.
In the discussion we show relationships among theorems, proving that no one of them is better of the others in general terms: there are counter-examples in which each theorem gives better bounds than others. We also exhibit examples where no bound among the considered techniques is tight. Moreover we generalize some theorems originally suited for network emulations, adapting them to execution of general DAGs in parallel networks, showing examples of their application. We also consider theorems for determining minimum I/O complexity, presenting similarities and differences with emulation theorems.
One of the main results of the thesis is a new general technique which provides lower bounds almost tight (except for a logarithmic factor) in a class of network emulations including multidimensional arrays. We improve previously better known results which have a polynomial gap between lower bound and actual emulation time. Our theorem considers emulations with recomputation, giving results valid in the most general context.
Finally we consider the role of recomputation in performance, trying to understand when it gives a real advantage respect to storing intermediate results in memory. In particular we introduce the problem in simple networks, showing a class of them in which recomputation can not improve I/O performance, ending in butterfly DAGs where recomputation can save a number of I/O accesses at least as big as the fast memory available during the computation. The approach used highlights the difficulty of exploit recomputation in executions of algorithms when their DAG representation exhibits an high bisection bandwidth.

Abstract (italiano)

I Direct Acyclic Graphs (DAG, grafi orientati e aciclici) sono dei grafi che descrivono in modo semplice ed efficace le esecuzioni di algoritmi, e permettono di rappresentare graficamente le relazioni di precedenza tra le operazioni. Al di là dell’esecuzione di algoritmi, un DAG può anche rappresentare l’esecuzione di una rete parallela. Quest’ultimo tipo di DAG ha una struttura molto regolare, corrispondente alla ripetizione nel tempo della rete stessa; il fatto che l’esecuzione di algoritmi e di reti parallele abbiano questa rappresentazione comune ci suggerisce un possibile approccio unificato nel loro studio.
I DAG sono stati molto usati nello studio di caratteristiche di algoritmi, in calcolo parallelo e nello studio della complessità computazionale. Ad esempio sono stati impiegati per ottenere lower bound per il tempo di esecuzione di algoritmi e di emulazione tra reti, per la quantità minima di memoria necessaria al calcolo di un algoritmo e il numero minimo di accessi in memoria lenta durante l’esecuzione di un algoritmo con una quantità di memoria veloce predeterminata.
Le tecniche sviluppate in questi studi partono da ipotesi diverse, una delle più importanti è la possibilità o meno di ricalcolare i risultati intermedi: se ciò non è possibile infatti è necessario salvarli in memoria per poterli usare in momenti successivi del calcolo.
Il trade-off tra ricalcolo e salvataggio in memoria dei dati è importante sia in ambito parallelo che nelle elaborazioni locali; infatti nel primo caso il ricalcolo può ridurre la latenza ed aumentare la banda con cui possiamo accedere ai dati in una rete di processori, calcolando gli stessi risultati in più punti della rete, mentre nel caso di elaborazioni locali il ricalcolo può evitare i problemi di latenza e banda nel recupero dei dati dalla memoria.
Ad oggi non esiste una tecnica universale in grado di fornire lower bound stretti per ogni algoritmo od emulazione di rete eseguiti in reti parallele, e i risultati conosciuti derivano da diversi teoremi. Al contrario, ci sono molti casi in cui mancano risultati stretti, anche per reti molto studiate e relativamente semplici com gli array multidimensionali.
La tesi inizia da questo stato dell’arte: la prima parte propone una panoramica delle tecniche di lower bound per DAG note, e termina con la presentazione dei teoremi originali sviluppati con la tesi, che migliorano o risolvono alcuni dei problemi aperti noti. In particolare, nella panoramica consideriamo tecniche di lower bound per l’esecuzione di algoritmi e emulazione di reti da parte di reti parallele, mostrando le idee su cui si basano e i loro limiti. Nello svolgimento vengono messe in evidenza le relazioni tra i teoremi, mostrando che attualmente nessuno di essi dà in assoluto risultati migliori: è possibile infatti presentare controesempi in cui ciascun teorema fornisce risultati più stretti degli altri. E' anche possibile mostrare esempi di coppie di reti dove il miglior bound tra le tecniche considerate non è stretto. Inoltre generalizziamo alcuni teoremi originariamente pensati per emulazioni di reti e che noi adattiamo all’esecuzione di DAG generici in reti parallele, mostrandone alcune applicazioni. Consideriamo anche teoremi per determinare la complessità minima di accessi alla memoria per il calcolo di un algoritmo, mostrandone similarità e differenze con i teoremi per le emulazioni.
Uno dei risultati più interessanti della tesi è una nuova tecnica generale che fornisce lower bound quasi stretti – eccetto per un fattore moltiplicativo logaritmico – in una classe di emulazione di reti che include gli array multidimensionali. Precedentemente il miglior risultato noto differiva di un fattore polinomiale dal miglior tempo di emulazione noto. Il nostro teorema ammette il ricalcolo durante l’emulazione, ponendosi nel contesto più generale possibile.
Infine consideriamo il ruolo del ricalcolo nelle performance, cercando di capire quando esso possa dare un reale vantaggio rispetto alla memorizzazione di risultati intermedi. Introduciamo il problema partendo da reti semplici, mostrando una classe di esse in cui il ricalcolo non migliora la complessità di accessi in memoria, terminando con i DAG a butterfly, dove il ricalcolo riesce a migliorare questa complessità di un termine almeno pari alla memoria usata durante il calcolo. L’approccio usato mette in luce la difficoltà` di usare proficuamente il ricalcolo durante l’esecuzione di algoritmi che presentano un’elevata connettività.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Bilardi, Gianfranco
Dottorato (corsi e scuole):Ciclo 26 > Scuole 26 > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:29 Gennaio 2015
Anno di Pubblicazione:29 Gennaio 2015
Parole chiave (italiano / inglese):Lower bound emulation recomputation memory complexity
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:7722
Depositato il:10 Nov 2015 12:55
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.

[A67] Amdahl, G.: Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS Conference Proceedings, 30, 483–485, 1967. Cerca con Google

[AACS87] Aggarwal, A., Alpern, B., Chandra, A. K., and Snir, M.: A model for hierarchical memory. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM, New York, 305–314, 1987. Cerca con Google

[ABK95] Adler, M., Byers, J. W., Karp, R. M.: Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, USA. Cerca con Google

[ACS87] Aggarwal, A., Chandra, A. K., and Snir, M.: Hierarchical memory with block transfer. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 204–216, 1987. Cerca con Google

[ACS90] Aggarwal, A., Chandra, A.K., and Snir, M.: Communication complexity of PRAMs. Theoretical Computer Science, 71:328, 1990. Cerca con Google

[AM10] Adams, I. F., Madden, B. A.: Automating Analysis of the Computation Storage Tradeoff, Thesis. UC Santa Cruz, 2010. Cerca con Google

[AV88] Aggarwal, A. and Vitter, J. S.: The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, 1988. Cerca con Google

[B74] Brent, R. P.: The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM 21, 2, 201–206, April 1974. Cerca con Google

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

[BHP+96] Bilardi, Herley, K. T., Pietracaprina, A., Pucci, G., Spirakis, P.; BSP vs LogP, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.25-32, June 24-26, 1996, Padua, Italy. Cerca con Google

[BP01] Bilardi, G., Peserico, E.: A Characterization of Temporal Locality and Its Portability across Memory Hierarchies. ICALP 2001 : 128–139, 2001. Cerca con Google

[BP95] Bilardi, G., and Preparata, F.: Horizons of parallel computation. J. Parall. Distrib. Comput., vol. 27, n. 2, pp. 172–182, 1995. Cerca con Google

[BP99] Bilardi, G., and Preparata, F.: Processor–Time Tradeoffs under Bounded–Speed Message Propagation: Part II, Lower Bounds. Theory Comput. Syst. 32(5): 531–559, 1999. Cerca con Google

[BPD00] Bilardi, G., Pietracaprina, A. and D’Alberto, P.: On the space and access complexity of computation dags. In Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000, LNCS 1928, 47–58, June 2000. Cerca con Google

[BPP07] Bilardi, G., Pietracaprina, A. and Pucci, G.: Decomposable BSP: A Bandwidth-Latency Model for Parallel and Hierarchical Computation, in Handbook of Parallel Computing (J. Reif and S. Rajasekaran Eds.), CRC Press, Boca Raton Fl USA, 2007. Cerca con Google

[BSS12] Bilardi, G., Scquizzato, M. and Silvestri, S.: A Lower Bound Technique for Communication on BSP with Application to the FFT, Euro-Par 2012 : 676-687. Cerca con Google

[CD82] Cook, S. A. and Dwork, C.: Bounds on the Time for Parallel RAM’s to Compute Simple Functions. STOC 1982: 231-233 Cerca con Google

[CGG+95] Chiang, Y., Goodrich, M. T., Grove, E. F., Tamassia, R., Vengroff, D. E., Vitter, J. S.: External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA 95, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1995, ISBN 0-89871-349-8. Cerca con Google

[CKP+96] Culler, D.E., Karp, R., Patterson, D., Sahay, A., Santos, E., Schauser, K.E., Subramonian, R., and Eicken, T.V.: LogP: A practical model of parallel computation. Communications of the ACM, 39(11):7885, November 1996. Cerca con Google

[CLU12] Cole-Mullen, H., Lyons, A., Utke, J.: Storing Versus Recomputation on Multiple DAGs, in Recent Advances in Algorithmic Differentiation, Lecture Notes in Computational Science and Engineering Volume 87, pp 197–207, 2012. Cerca con Google

[CR73] Cook, S. A., Reckhow, R. A.: Time Bounded Random Access Machines. J. Comput. Syst. Sci., vol. 7, n. 4, pp. 354–375, 1973. Cerca con Google

[CLR01] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, second edition. MIT Press, 2001. Cerca con Google

[DK96] P. De la Torre and C.P. Kruskal. Submachine locality in the bulk synchronous setting. In Proc. of EUROPAR 96, LNCS 1124, pp. 352–358, August 1996. Cerca con Google

[EPR+13] Elango, V., Pouchet, L. N., Ramanujam, Rastello, F., J. and Sadayappan, P.: Data access complexity: The red/blue pebble game revisited, Technical report, OSU/INRIA/LSU/UCLA, Sept. 2013. OSU-CISRC-7/13-TR16 Cerca con Google

[EPR+15] Elango, V., Pouchet, L. N., Ramanujam, Rastello, F., J. and Sadayappan, P.: On Characterizing the Data Access Complexity of Programs, in Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’15, pp. 567–580, 2015. 1 Cerca con Google

[FF82] Fishburn, J. P., and Finkel, R. A.: Quotient networks, IEEE Trans. Comput., C-31, 4 (Apr.), 288–295, 1982. Cerca con Google

[FPP06] Fantozzi, C., Pietracaprina, A., Pucci, G.: Translating submachine locality into locality of reference, J. Parallel Distrib. Comput., 66(5), May 2006, 633–646, ISSN 0743-7315. Cerca con Google

[FW78] Fortune, S., and Wyllie, J.: Parallelism in Random Access Machines. In Proceeding STOC ’78 Proceedings of the tenth annual ACM symposium on Theory of computing, pp. 114–118, 1978. Cerca con Google

[G78] Goldschlager, L. M.: A Unified Approach to models of Synchronous Parallel Machines. In Proceeding STOC ’78 Proceedings of the tenth annual ACM symposium on Theory of computing, pp. 89–94, 1978. Cerca con Google

[GH91] Gupta, A., K. and Hambrusch, S., E.: Embedding Complete Binary Trees into Butterfly Networks, IEEE Transactions on Computers, vol. 40, pp. 853–863, 1991. Cerca con Google

[HK81] Hong, J., and Kung, H. T.: I/O complexity: The red-blue pebble game. In Proceedings of the 13th ACM Symposium on Theory of Computing, pp. 326–333, New York, NY, USA, 1981. ACM. Cerca con Google

[HKMU91] Heckmann, R., Klasing, R., Monien, B., Unger, W.: Optimal Embedding of Complete Binary Trees into Lines and Grids, Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Computer Science, WG91, 1991. Cerca con Google

[HWV77] Hopcroft, J. E., Wolfgang, J. P., Valiant, L. G.: On Time Versus Space. J. ACM 24(2): 332–337, 1977. Cerca con Google

[Jaja92] Jaja, J. F.: An introduction to parallel algorithms. Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA, 1992. ISBN:0-201- 54856-9. Cerca con Google

[K70] Kerr, L. R.: The Effect of Algebraic Structure on the Computational Complexity of Matrix Multiplication, Ph.D. Thesis, Cornell University, New York, 1970. Cerca con Google

[K83] Kruskal, C. P.: Searching, Merging, and Sorting in Parallel Computation. IEEE Trans. Computers 32(10): 942–946, 1983. Cerca con Google

[KR94] Kruskal, C. P. and Rappoport, K. J., Bandwidth-based Lower Boundson Slowdown for Efficient Emulations of Fixed-connection Networks, Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’94, 132–139, ISBN 0-89791-671-9, 1994. Cerca con Google

[KLM+97] Koch, R. R., Leighton, F. T., Maggs, B. M., Rao, S., Rosenberg, A. L., Schwabe, E. J.: Work-preserving emulations of fixed-connection networks. J. ACM 44(1): 104–147, 1997. Cerca con Google

[LMR88] Leighton, T., Maggs, B., Rao, S.: Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (Oct.). IEEE, New York, pp. 256–271, 1988. Cerca con Google

[LP93] Luccio, F., Pagli, L.: A Model of Sequential Computation with Pipelines Access to Memory, Mathematical Systems Theory, 26(4), 1993, 343–356. Cerca con Google

[M65] Moore, G. E.: Cramming more components onto integrated circuits. Electronics Magazine, p. 4, 1965. Cerca con Google

[M83] Meyer auf der Heide, F.: Efficiency of Universal Parallel Computers, Acta Inf. 3(19), 269–296, 10.1007/BF00265559, Springer-Verlag, 1983. Cerca con Google

[M86] Meyer auf der Heide, F.: Efficient Simulations Among Several Models of Parallel Computers, SIAM J. Comput., 15(1) , 106–119, 1986. Cerca con Google

[MZ12] Milani, E. and Zago, N.: Exploiting Fine Grained Parallelism on the SPE. ICTCS, 2012. Cerca con Google

[PKK+04] Parikh, A., Kim, S., Kandemir, M. T., Vijaykrishnan, N. and Irwin M. J.: Instruction Scheduling for Low Power. In Journla of VLSI Signal Processing 37(1): 129–149, 2004. Cerca con Google

[PPS06] Pietracaprina, A., Pucci, G., Silvestri, F.: Cache-oblivious simulation of parallel programs, 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Proceedings, 25-29 April 2006, Rhodes Island, Greece, IEEE, 2006. Cerca con Google

[PSZ+02] Parikh, D., Skadron, K., Zhang, Y., Barcella, M., and Stan. M.: Power Issues Related to Branch Prediction. In Proc. of the 2002 International Symposium on High-Performance Computer Architecture, February, 2002, Cambridge, MA. Cerca con Google

[PU87] Papadimitriou, C. H. and Ullman, J. D.: A Communication-Time Trade-off. SIAM J. Comput. 16(4): 639–646, 1987. Cerca con Google

[S95] Savage, J.: Extending the Hong-Kung Model to Memory Hierarchies. In Computing and Combinatorics, v. 959 of LNCS, pp. 270–281. 1995. Cerca con Google

[SS14] Scquizzato, M. and Silvestri, S.: Communication Lower Bounds for Distributed-Memory Computations. STACS 2014 : 627–638. Cerca con Google

[T36] Turing, A.M.: On Computable Numbers, with an Application to the Entscheidungs problem, Proceedings of the London Mathematical Society, 2 (42): 230–265, 1937. Cerca con Google

[V90] Valiant, L.G.: A bridging model for parallel computation. Communications of the ACM, 33(8):103111, August 1990. Cerca con Google

[V98] Vitter, J. S.: External Memory Algorithms, Algorithms - ESA 98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings (G. Bilardi, G. F. Italiano, A. Pietracaprina, G. Pucci, Eds.), 1461, Springer, 1998, ISBN 3-540-64848-8. Cerca con Google

[VW85] Vishkin, U. and Wigderson, A.: Trade-Offs between Depth and Width in Parallel Computation, SIAM Journal of Computing, 14(2): pp. 303–314, 1985. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record