| Mapping Between 2-D Meshes of the Same Size |
| |
| 引用本文： | Peng Guoqiang. Mapping Between 2-D Meshes of the Same Size[J]. 计算机科学技术学报, 1997, 12(5): 470-475. DOI: 10.1007/BF02943178 |
| |
| 作者姓名： | Peng Guoqiang |
| |
| 作者单位： | Huazhong University of Science and Technology, Wuhan 430074; |
| |
| 摘 要： | 1IntroductionInrece11tyears,n1a11yparallelalgoritlImshavebeendesignedtosolvedifferentproblemso1lvario1ls11etworktopologics.Bi11arytrees,meshesandhypercubesarethethreeimportal1tl1etworktop()logieswllicllhaterpcoivedintensivestlldy.WiththeadvanceofVLSI,manyllewl1etworkssuchasstargrapl1[1]havebeenorwiIlbeintroduced.Inor
|
| 关 键 词： | 并行算法 并行处理 网络拓扑 |
Mapping between 2-d meshes of the same size |
| |
| Guoqiang Peng. Mapping between 2-d meshes of the same size[J]. Journal of Computer Science and Technology, 1997, 12(5): 470-475. DOI: 10.1007/BF02943178 |
| |
| Authors: | Guoqiang Peng |
| |
| Affiliation: | Huazhong University of Science and Technology, Wuhan 430074; |
| |
| Abstract: | Given two 2-D meshesM 1 andM 2 of sizess i×ti wheres i≤ti (i=1,2) ands 1×t 1=s 2×t 2, embeddingM 1 toM 2 with minimum dilation is studied. First, several lower bounds on the dilations of embedding in different cases are presented. Then, an embedding algorithm with dilation [s 1/s 2]+2 for the cases 1≤s 2 is proposed, which almost matches the lower bound [s 1/s 2]. For the cases 1<s 2, another embedding algorithm is given with dilation min {ζ(s 1,h′)°, ζ(s 2,s 1)}, where ζ(s 1,h′)=min{ζ(s 1,ϕs 2,s 1)†, ζ(t 1,ϕ(2,s 1)))} Peng Guoqiang is a Lecturer in Huazhong University of Science and Technology. His research interests include distributed operating systems and parallel processing. |
| |
| Keywords: | Dilation embedding mesh parallel processing |
| 本文献已被 CNKI SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
