Embedding the optimal all-to-all personalized exchange on multistage interconnection networks+

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.