Exploiting an alternative labeling for efficient hypercube algorithms

Abstract

Bu çalışmada hiperküp çok işlemcileri için yeni bir indeksleme yöntemi önerildi. Önerilen indeksleme, dolaylı giriş-çıkış kaydedicisi eklenmiş SIMD hiperküp modeli üzerinde algoritmalar geliştirilerek kullanıldı. Bazı algoritmaların geliştirilmesi ve SIMD çalışma zamanlarının düşürülmesiyle, bu yeni indekslemenin alışılmış indekslemeden daha üstün olduğu gösterildi. Alışılmış indekslemede, içe konmuş halka ve ağlardaki en yakın komşu haberleşmesinde gereken işlemci indeksi hesaplamaları cü-boyutlu hiperküpte 0(d) zamanında yapılabilmektedir. Bu rota hesaplamaları eğer gray kodu çeviri tabloları kullanılırsa 0(1) zamanda yapılabilir. Bu rota hesaplamaları, önerilen indekslemede esnek bir paralel programlama ortamı sağlayacak şekilde sabit zamanda, basit ondalık aritmetik kullanarak ve hiçbir kod çeviri tablosuna ihtiyaç olmadan yapılabilmektedir. İçe konmuş halka ve ağ işlemlerinde, alışılmış indekslemedeki gray kodu sıralaması yerine önerilen indekslemedeki doğal ondalık sıralama yeterli olmaktadır. Geliştirilen çoğu SIMD algoritmalarında önceki en iyi MIMD zamanlarına ulaşılmış bulunulmaktadır. Son olarak, içe konmuş halka işlemlerinde algoritmik uyumluluk sağlayan, önerilen indeksle menin genelleştirilmiş hiperküp çok işlemcileri için genelleştirilmesi sunulmaktadır.

In this work, a new labeling scheme for hypercube multicomputers is proposed. The proposed labeling is exploited by developing algorithms on the SIMD hy percube model with the indirect I/O port register enhancement. Through the construction of some algorithms and reduction in their SIMD complexities, it is shown that this new labeling is superior to the common labeling used so far. In the common labeling, processor index computations required for nearest neighbor communications in ring and mesh embeddings can be performed in 0(d) time in a e?-dimensional hypercube. These routing computations can be performed in 0(1) time only if a number of gray code conversion tables are used. In the proposed labeling, these routing computations can be performed in 0(1) time, using simple decimal arithmetic and without the need of any code conversion tables, which provides a flexible parallel programming envi ronment. Instead of gray code ordering in the common labeling the natural decimal ordering of the processors in the proposed labeling suffices for the em bedded ring and mesh operations. In most of the SIMD algorithms developed, best previous MIMD complexities are reached. Finally, the generalization of the proposed labeling for the generalized hypercube architecture is presented which provides algorithmic compatibility in embedded ring operations. m