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

logo del sistema bibliotecario dell'ateneo di padova

Gianelle, Alessio (1996) Instradamento di messaggi sulla rete multibutterfly. [Laurea vecchio ordinamento]

Full text disponibile come:

[img]
Anteprima
Documento PDF
326Kb

Abstract

Nella tesi abbiamo analizzato il problema del routing di h-relation sulla rete multibutterfly [22]. Questa si ottiene come generalizzazione di una rete della famiglia del cubo, la rete butterfly. Infatti possiamo vedere una multibutterfly come la sovrapposizione di pi`u reti butterfly, nelle quali gli archi sono stati opportunamente permutati.

Tipologia del documento:Laurea vecchio ordinamento
Corsi di Laurea vecchio ordinamento:Facoltà di Scienze MM. FF. NN. > DU Matematica
Informazioni aggiuntive:Corso di Laurea in matematica
Parole chiave:calcolo parallelo multibutterfly algoritmo routing
Settori scientifico-disciplinari del MIUR:Area 01 - Scienze matematiche e informatiche > INF/01 Informatica
Codice ID:231
Relatore:Colussi, Livio
Data della tesi:1996
Biblioteca:Polo di Scienze > Biblioteca del Seminario Matematico
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:No

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 e non da noi.

[1] M. Ajtai, J. Komlos, and E. Szemeredi. An O(n log n) sorting network. 15th Symp. on Theory of Computing, 1983. Cerca con Google

[2] R. Aleliunas. Randomized parallel communication. In Proc. ACM Symp on Priciples of Distributed Computing, pages 60—72, 1982.3] S. Arora, F. T. Leighton, and B. M. Maggs. On-line algorithms for path selection in a non-blocking network. SIAM Journal on Computing, 25(3):600—625, June 1996. Cerca con Google

[4] L. A. Bassalygo and M. S. Pinsker. Complexity of an optimum nonblocking switching network without reconnections. Problems of Information Trasmission, 9:64—66, 1974. Cerca con Google

[5] K. Batcher. Sorting networks and their applications. In Proc. AFIPS Spring Joint Comp. Conf, pages 307—314, 1968. Cerca con Google

[6] A. B’¨aumker, W. Dittrich, and A. Pietracaprina. The deterministic complexity of parallel multisearch. In Proc. ot the 5th Scandinavian Workshop on Algorithm Theory, pages 404—415, 1996. Cerca con Google

[7] V. E. Beneˇs. Mathematical theory of connecting networks and telephone traffic. Academic Press, New York, 1965. Cerca con Google

[8] G. Bilardi, K.T. Herley, A. Pietracaprina, G. Pucci, and P. Spirakis. Bsp vs logp. In Proc. of the 8th ACM Symp. on Parallel Algorithms and Architectures, pages 25—32, 1996. 52 Cerca con Google

[9] F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays • Trees • Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992. Cerca con Google

[10] F. T. Leighton, C. E. Leiserson, and D. Kravets. Theory of parallel and VLSI computation. Research Seminar Series Report MIT/LCS/RSS 8, Laboratory for Computer Science, Massachusette Institute of Technology, Cambridge, MA, 1990. Cerca con Google

[11] T. Leighton. Tight bounds on the complexity of parallel sorting. 16th Symp. on Theory of Computing, pages 71—80, 1984. Cerca con Google

[12] G. Lev, N.J. Pippenger, and L.G. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput., 30(2):93—100, 1981. Cerca con Google

[13] B.M. Maggs and B. V’¨ocking. Improved routing and sorting on multibutterflies. Technical report, CMU-CS-96-192, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, November 1996. Cerca con Google

[14] D. Nassimi and S. Sahni. Parallel algorithms to set-up the beneˇs permutation network. IEEE Trans. Comput., 31(2):148—154, 1982. Cerca con Google

[15] N. Pippenger. Comunication networks. In Handtesivo of Theoretical Computer Amsterdam, 1990. Cerca con Google

[16] N. Pippenger and A.C.-C. Yao. Rearrangeable networks with limited depth. SIAM J. Algebraic Discrete Methods, 3:411—417, 1982. Cerca con Google

[17] A.G. Ranade. Constrained randomization for parallel communication. Technical report, YALEU/DCS/TR-511 Dept. Comput. Sci. Yale Univerity, New Haven, CT, 1987. Cerca con Google

[18] R.Cypher and G.Plaxton. Deterministic sorting in nearly logarithmic time on the hypercube and related computers. In 22nd ACM Symposium on Theory of Computing, pages 193—203, 1990. 53 Cerca con Google

[19] J. T. Schwartz.19] J. T. Schwartz. Ultracomputers. In ACM TOPLAS 2, pages 484—521, 1980. Cerca con Google

[20] C.E. Shannon. Memory requirements in a telephone exchange. Bell Systems Tech. J., 29:343—349, 1950. Cerca con Google

[21] E. Upfal. Efficient schemes for parallel communication. J. ACM, 31(3):507—517, 1984. Cerca con Google

[22] E. Upfal. An O(log n) deterministic packet routing scheme. Proceedings of the 21st Annual ACM Symphosium on Theory of Computing, pages 241—250, May 1989. Cerca con Google

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

[24] L.G. Valiant. General purpose parallel architectures. In Handtesivo Leeuwen, North-Holland, Amsterdam, 1990. Cerca con Google

[25] L.G. Valiant and G.J. Brebner. Universal schemes for parallel communication. In Proc. 13th Ann. ACM Symp. on Theory of Computing, pages 263—277, 1981. 54 Cerca con Google

Solo per lo Staff dell Archivio: Modifica questo record