|
Title:
|
Hypercube algorithms on mesh connected multicomputers
|
|
Author:
|
Díaz de Cerio Ripalda, Luis Manuel; Valero García, Miguel; González Colás, Antonio María
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors; Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions; Universitat Politècnica de Catalunya. ARCO - Microarquitectura i Compiladors |
|
Abstract:
|
A new methodology named CALMANT (CC-cube Algorithms on Meshes and Tori) for mapping a type of algorithm that we call CC-cube algorithm onto multicomputers with hypercube, mesh, or torus interconnection topology is proposed. This methodology is suitable when the initial problem can be expressed as a set of processes that communicate through a hypercube topology (a CC-cube algorithm). There are many important algorithms that fit into the CC-cube type. CALMANT is based on three different techniques: (a) the standard embedding to assign the processes of the algorithm to the nodes of the mesh multicomputer; (b) the communication pipelining technique to increase the level of communication parallelism inherent in the CC-cube algorithms; and (c) optimal message-scheduling algorithms proposed in this work in order to avoid conflicts and minimizing in this way the communication time. Although CALMANT is proposed for multicomputers with different interconnection network topologies, the paper only focuses on the particular case of meshes. |
|
Abstract:
|
Peer Reviewed |
|
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors
-Multiprocessors
-Mapping algorithms
-Hypercube algorithms
-Mesh interconnected multicomputers
-Standard embedding
-Communication pipelining
-Message-scheduling algorithms
-Complete exchange
-Multiprocessadors |
|
Rights:
|
|
|
Document type:
|
Article - Published version
Article |
|
Share:
|
|
