MESH PERMUTATION ROUTING WITH LOCALITY

作     者：CHEUNG, S LAU, FCM 

作者机构：UNIV HONG KONGDEPT COMP SCIHONG KONGHONG KONG 

出 版 物：《INFORMATION PROCESSING LETTERS》 (Inf. Process. Lett.)

年 卷 期：1992年第43卷第2期

页      面：101-105页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：PARALLEL ALGORITHMS MESH-CONNECTED COMPUTERS PERMUTATION ROUTING K-K ROUTING ROUTING WITH LOCALITY MIMD 

摘      要：Given the permutation routing problem on mesh-connected arrays with a known maximum distance, d, between any source-destination pair, we show how sorting and the greedy algorithm can be combined to yield a deterministic, asymptotically optimal algorithm for solving the problem. This simple algorithm runs in d + O(d/f(d)) time and requires an O(f(d)) buffer size (or O(d) time and constant buffer size if we choose f(d) to be a constant). It also gives efficient solutions to the k-k routing problem with locality.