Please use this identifier to cite or link to this item:
Title: Embedding the optimal all-to-all personalized exchange on multistage interconnection networks+
Authors: รสลิน, เพตะกร
Roselin, Petagon
Keywords: All-to-all personalized exchange (ATAPE)
Embedding f-in-1 dynamic ATAPE function incorporate with multistage pipelining
Fully self-routable multistage interconnection networks (MINs+)
A crossbar of MINs+ and the ultimate ATAPE embedding
Issue Date: Feb-2016
Publisher: Journal of Parallel and Distributed Computing
Abstract: All-to-all personalized exchange (ATAPE) is an inspired process to speedup the parallel and distributed computing. Recently, ATAPE algorithms were successfully applied on multistage interconnection networks (MINs), including baseline and butterfly networks. However, routing of those algorithms on MINs relies on switch-patterns for stage-control from sources (S), which is a half-routing solution since they cannot perform a full self-routing with the (S, D) protocol for all MINs. In this paper, first we propose a full-routing solution of the realizing ATAPE on a class of d-nary-switch MINs+ (i.e., baseline+, butterfly+, etc.). Our ATAPE can be embedded on-chip effectively for not only (S, D) self-routing but also stage-/switch-control routing. Two embedded ATAPE functions incorporate with multi-stage pipelining are proposed in optimal O(N+log2N): 1. a (default) static function D=S XOR (View the MathML source) mod N and 2. an (optional) f-in-1 dynamic function D=ρ [(View the MathML source) mod N] with the incrementing counter C=0 to N−1. Second, we introduce a crossbar of MINs+ with fewer delay-stages to achieve the ultimate ATAPE embedding. Finally, experimental results of applying ATAPE on such MINs+ are confirmed fruitfully, including the ATAPE-based NxN-matrix transposition in O(N+log2N), which yields the significant speedup.
Appears in Collections:Article

Files in This Item:
File Description SizeFormat 
Embedding the optimal all.pdf77.52 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.