Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/105278

The Xor embedding: An embedding of hypercubes onto rings and toruses
González Colás, Antonio María; Valero García, Miguel
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. ARCO - Microarquitectura i Compiladors; Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions
Many parallel algorithms use hypercubes as the communication topology among processes, which make them suitable to be executed on a hypercube multicomputer. In this way the communication cost is kept to a minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputer is constrained by the fact that the interconnection cost per node increases with the total number of nodes. From the point of view of scalability, meshes and toruses are a more interesting class of interconnection topologies. In this paper the authors propose an embedding of hypercubes onto toruses of any given dimension, incuding one-dimensional toruses which are also called rings. They also prove that the embedding is optimal in the sense that it minimizes the execution time on a ring of a class of parallel algorithms frequently found in real applications, such as FFT and some class of sorting algorithms.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors
Parallel processing (Electronic computers)
Parallel algorithms
Sorting
Hypercube networks
Fast Fourier transforms
Parallel architectures
Processament en paral·lel (Ordinadors)
Algorismes paral·lels
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
Institute of Electrical and Electronics Engineers (IEEE)
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Díaz de Cerio Ripalda, Luis Manuel; Valero García, Miguel; González Colás, Antonio María
González Colás, Antonio María; Valero García, Miguel; Díaz de Cerio Ripalda, Luis Manuel
Royo Vallés, María Dolores; Valero García, Miguel; González Colás, Antonio María; Marí, Carme
Royo Vallés, María Dolores; Valero García, Miguel; González Colás, Antonio María
Royo Vallés, María Dolores; Valero García, Miguel; González Colás, Antonio María; Mari Vila, Carme