HPC. Sobre la red de interconexión Hex-cell.

1.Es una red propuesta en 2008 por diversos investigadores del frente occiriental😉. Son interesantes entre otras cosas por su escalabilidad: la diferencia entre un tamaño y el siguiente no es muy grande.

Me parece claro, aunque de momento no tengo demostración, que es isomorfa a un (di)grafo de Cayley podado, es decir al que se le han eliminado algunos arcos. O dicho de otra manera, a todo Hex-cell de cualquier dimensión se le le puede convertir en un (di)grafo de Cayley añadiéndole arcos que saturen los vértices de su frontera.

Actualización, día siguiente. Sin haberlo estudiado todavía detenidamente, no está tan claro que se puedan expresar como Grafos de Cayley, aunque posiblemente sí como grafos vértice transitivos. Fin de actualización.

Es un dígrafo de Cayley que entiendo se puede generar con dos generadores de orden 6 (y sus inversos). O quizás esta topología no se pueda expresar como (di)grafo de Cayley y solo como grafo vértice transitivo. Tema a investigar.

La relación de la Hex-cell con el (di)grafo de Cayley del que se deriva es la  misma que la de la mesh con el toro. En la mesh la célula es un cuadrado en vez de un hexágono y ambas se pueden construir de la misma manera, por un proceso iterativo muy sencillo.  La mesh es más flexible pues admite más tamaños diferentes. Por otra parte la Hex-cell no sería conmutativa.

Todo esto seguramente ya es perfectamente conocido, pues es bastante evidente. Por evidente o se ha publicado ya o no se publicará nunca.

Hex-cell de dimensión 2.

Hex-cell de dimensión 2.

2. He aprendido recientemente lo importante que es el problema del empotrado de unas topologías en otras, y la relevancia para esto del problema de recorridos hamiltonianos: cuando existen en una red de interconexión, permiten el empotrado de las muy importantes topologías, las más sencillas bus y ring. que son óptimas para implementar algoritmos  de múltiples problemas.

No conocía por ejemplo que los parámetros importantes para evaluar un empotrado son los de dilation, congestion y expansion.

El lector interesado puede ver este artículo dónde analizan el empotrado de diversas topologías,  entre ellas las dos señaladas, precisamente en redes de interconexión de tipo Hex-cell.

3. Seguramente se pueda generalizar este resultado a los 11 polígonos regulares que teselan el plano.

P.s.

Encontrado posteriormente.

Title. Interconnection networks of degree three obtained by pruning two-dimensional tori

Iain A. Stewart

Abstract—We study an interconnection network that we call 3T orus(m, n) obtained by pruning the 4m × 4n torus (of links) so that the resulting network is regular of degree 3. We show that 3T orus(m, n) retains many of the useful properties of tori (although, of course, there is a price to be paid due to the reduction in links). In particular: we show that 3T orus(m, n) is node-symmetric; we establish closedform expressions on the the length of a shortest path joining any two nodes of the network; we calculate the diameter precisely; we obtain an upper bound on the average internode distance; we develop an optimal distributed routing algorithm; we prove that 3T orus(m, n) has connectivity 3 and is Hamiltonian; we obtain a precise expression for (an upper bound on) the wide-diameter; and we derive optimal one-toall broadcast and personalized one-to-all broadcast algorithms under both a one-port and all-port communication model. We also undertake a preliminary performance evaluation of our routing algorithm. In summary, we find that 3T orus(m, n) compares very favourably with tori.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: