Parallel prefix computation on extended multi-mesh network

摘要

A parallel algorithm for prefix computation of N = n~4 lements on an n x n extended multi-mesh network is presented. The network is a modified version of an earlier multi-mesh network with a 4-regular structure. The algorithm takes O(N~(1/4)) time on N processors (13N~(1/4)-5 communication steps and log N + 4 arithmetic/logic steps).