Routing Problems on the Mesh of Buses |
| |
Authors: | Kazuo Iwama Eiji Miyano Yahiko Kambayashi |
| |
Institution: | aDepartment of Computer Science and Communication Engineering, Kyushu University, Fukuoka, 812, Japan;bIntegrated Media Environment Experimental Laboratory, Kyoto University, Kyoto, 606, Japan |
| |
Abstract: | The mesh of buses (MBUSs) is a parallel computation model which consists ofn×nprocessors,nrow buses, andncolumn buses, but no local connections between neighboring processors. Annlower bound for the permutation routing on this model is shown. The proof does not depend on common predetermined assumptions such as “if a packet has to move horizontally then it has to ride on a horizontal bus at least once.” As for upper bounds, a 1.5nalgorithm is shown. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|