当前位置：文档之家 › Communication Reduction in Iterative Grid-based Computing Using SuperBoundary Exchange Tech

Communication Reduction in Iterative Grid-based Computing Using SuperBoundary Exchange Tech

  • 格式：pdf
  • 大小：88.62 KB
  • 文档页数：6

CommunicationReductioninIterativeGrid-basedComputingUsingSuperBoundaryExchangeTechnique

HairongKuang,LubomirF.Bic,andMichaelB.DillencourtInformationandComputerScienceUniversityofCalifornia,Irvine,CA92697-3425,USAhkuang,bic,dillenco@ics.uci.edu

ABSTRACTIterativegrid-basedapplications,typifiedbythefinitedif-ferencemethodforsolvingpartialdifferentialequations[1]andspatiallyorientedindividual-basedsimulations[2],areimportantapplicationsfordistributedcomputing.How-ever,iterativegrid-baseddistributedcomputationsrequirethatcommunicationbeperformedateverystep,whichcanleadtosignificantcommunicationoverhead.WeshowhowatechniquecalledSuperBoundaryExchange(SBX)forsignificantlyreducingthisoverheadinfinite-differencecomputations,firstintroducedin[3],canbeappliedtoindividual-basedcomputationsaswell,atacostofasome-whatcoarsergridthanmightotherwisebenecessary.

KEYWORDSgrid-basedcomputing,individual-basedsimulations,boundaryexchange

1.IntroductionDistributedcomputing,whichallowscomputingoveranet-workofworkstations,isbecomingincreasinglypopularandcosteffective,asworkstationsbecomelessexpensiveandnetworksareavailabletomoreusers.Iterativegrid-basedapplicationsareonetypeofapplicationthatcanbenefitfromdistributedimplementation.Theseapplica-tionsarefrequentlytime-consuming,whichmakesthemworthdistributingovermultiplecomputers.Spatiallyori-entedcomputationsmakeiteasytopartitionthesimulationspace.Nearneighborcomputationsreducethecommuni-cationcost.Typicalexamplesofiterativegrid-basedcom-putationsarethefinitedifferencemethodforsolvingpartialdifferentialequations[1],andspatiallyorientedindividual-basedsimulations,inwhichthebehaviorofentitiesisbasedsolelyontheirinteractionswithnearbyentities[2].Oneoftheissueswiththedistributedimplementedofiterativegrid-basedcomputationisprogramperformance.Iterativegrid-baseddistributedcomputationsrequirethatcommunicationbeperformedateverystep,whichcanleadtosignificantcommunicationoverhead.Inapreviouspa-per[3],weintroducedatechniquecalledSuperBoundaryExchange(SBX)forsignificantlyreducingthisoverheadinfinite-differencecomputations.Theunderlyingtradeoffisfewermessagesagainstpotentiallylongermessagesandsomeadditional,redundant,computation.TheSuperboundaryExchangetechniqueisillustratedinFigure1.Supposethatwearesolvinga1-dimensionalfinitedifferenceequationonanetworkofprocessors.Supposethatthevaluesofassociatedwithintherangearecomputedonaparticularprocessor,andthevaluesofassociatedwithintherangearecomputedonaneighbor-ingprocessor.Inordertocomputethevalueof,mustknowthevalueof;hencethisdata(the“ghostboundary”)mustbesenttobyitsneighboronceitisknown.Ifeachprocessoronlystoresthedatafortheval-uesdirectlyassociatedwithit,suchanexchangeofbound-arydatamustoccurateachtimestepinthecomputation.ThisisillustratedinFigure1(a),whichshowsthecom-putationfromtheendoftimestep3totheendoftimestep6.Thefirstrowshowsthecomputationattheendoftimestep3.Thenextthreedoublerowsillustratetimesteps4,5,and6;eachofthesetimestepsisshownaftertheghostboundaryhasbeenexchangedatthebeginningofthetimestep(thedottedboxindicatestheghostboundary),andthenafterthecomputationforthetimestephasbeencompleted.SuperBoundaryExchangeisatechniqueforreducingthefrequencyofthisboundaryexchange.Suppose,atthebe-ginningoftimestep,thevalues,andaresenttobyitsneighbor.Thenattime,hasalldatanecessarytocomputethevalues,,and.Itcanthenusethisdatatocompute,and,andthentocompute.Hencenofur-therboundarydatamustbeexchangeduntiltime,andingeneral,datamustonlybeexchangedeverythreeitera-tions.ThisisillustratedforinFigure1(b).WhiletheonlyapplicationweusedtoillustratetheSuperBoundaryExchangein[3]isthefinitedifferencemethod,theSuperBoundaryExchangetechniquecanbeappliedtoawiderclassofproblems.Thetechniquecanbeappliedtoanyapplicationthathasanunderlyinglog-icalspacewithawell-definednotionofneighbor,andaniterativecomputationwherethecomputationataparticu-larlocationinanygiventimestepdependsonthestateof.........

......

......(a)

...............(b)

Figure1.SuperboundaryExchangeforfinite-differencecomputations[3].

thatlocationanditsneighborsintheprecedingtimestep.Oneexampleofthistypeofapplicationisindividual-basedsimulation.Here,theboundarydatatobeexchangedisthestateoftheentitiesinneighboringnodes.TheSuper-BoundaryExchangewouldrequireredundantcomputationofthebehaviorsoftheseentitiesafteranexchangeofdata.However,individual-basedsimulationsaredifferentfromthefinitedifferencemethodinthattheentitiesmigrateinthesimulationspace.Thus,ineachtimestep,notonlytheboundarybutalsothemigratingentitiesneedtobeex-changed.

合集下载

6G智能超表面技术应用与挑战

6G智能超表面技术应用与挑战

２０２１年第４７卷第６期无线电通信技术

６７９　

ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００３－３１１４．２０２１．０６．００２引用格式：赵亚军，菅梦楠．６Ｇ智能超表面技术应用与挑战［Ｊ］．无线电通信技术，２０２１，４７（６）：６７９－６９１．［ＺＨＡＯＹａｊｕｎ，ＪＩＡＮＭｅｎｇｎａｎ．ＡｐｐｌｉｃａｔｉｏｎｓａｎｄＣｈａｌｌｅｎｇｅｓｏｆＲｅｃｏｎｆｉｇｕｒａｂｌｅＩｎｔｅｌｌｉｇｅｎｔＳｕｒｆａｃｅｆｏｒ６ＧＮｅｔｗｏｒｋｓ［Ｊ］．ＲａｄｉｏＣｏｍｍｕｎｉ⁃

ｃａｔｉｏｎｓＴｅｃｈｎｏｌｏｇｙ，２０２１，４７（６）：６７９－６９１．］

６Ｇ智能超表面技术应用与挑战

赵亚军１，２，菅梦楠１，２（１．中兴通讯股份有限公司，北京１００１９２；２．移动网络和移动多媒体技术国家重点实验室，广东深圳５１８０５５）

摘　要：智能超表面（ＲｅｃｏｎｆｉｇｕｒａｂｌｅＩｎｔｅｌｌｉｇｅｎｔＳｕｒｆａｃｅ，ＲＩＳ）因为其能够灵活操控信道环境中的电磁特性，在学术研究及产业推进上发展迅速，被认为是５Ｇ⁃Ａｄｖａｎｃｅｄ和６Ｇ网络的关键候选技术之一。ＲＩＳ通过其人为灵活异常调控无线电波传输的能力，有机会构建一个智能的无线电磁环境。ＲＩＳ的引入可能构建全新的网络范式，在给未来网络带来全新可能的同时，也导致了诸多全新的技术及工程应用挑战。该综述首先从新的角度介绍了ＲＩＳ使能未来无线通信网络的主要方面，然后重点对ＲＩＳ引入后面临的关键挑战进行了探讨。归纳汇总了ＲＩＳ网络面临的主要工程化应用技术挑战，并对其中信道降秩、网络间共存、网络内共存、网络部署等几方面的关键技术挑战进行了深入分析和探讨，提出可能的解决方案。关键词：６Ｇ；智能超表面；信道降秩；多网络共存；多用户复用；多小区共存；网络部署

中图分类号：ＴＮ９２９．５ 文献标志码：Ａ 开放科学（资源服务）标识码（ＯＳＩＤ）：文章编号：１００３－３１１４（２０２１）０６－０６７９－１３ＡｐｐｌｉｃａｔｉｏｎｓａｎｄＣｈａｌｌｅｎｇｅｓｏｆＲｅｃｏｎｆｉｇｕｒａｂｌｅＩｎｔｅｌｌｉｇｅｎｔ

预处理子空间迭代法的一些基本概念

预处理子空间迭代法的一些基本概念

CG算法的预处理技术：、为什么要对A进行预处理：其收敛速度依赖于对称正定阵A的特征值分布特征值如何影响收敛性：特征值分布在较小的范围内，从而加速CG的收敛性特征值和特征向量的定义是什么？（见笔记本以及收藏的网页）求解特征值和特征向量的方法：Davidson方法：Davidson 方法是用矩阵( D - θI)- 1( A - θI) 产生子空间，这里D 是A 的对角元所组成的对角矩阵。

θ是由Rayleigh-Ritz 过程所得到的A的近似特征值。

什么是子空间法：Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi 的迭代形式来求解。

这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。

如何取正定矩阵Mk为：Span是什么？:设x_(1,)...,x_m∈V ,称它们的线性组合∑_(i=1)^m?〖k_i x_i \|k_i∈K,i=1,2...m〗为向量x_(1,)...,x_m的生成子空间，也称为由x_(1,)...,x_m张成的子空间。

记为L（x_(1,)...,x_m），也可以记为Span（x_(1,)...,x_m）什么是Jacobi迭代法：什么是G_S迭代法：请见PPT《迭代法求解线性方程组》什么是SOR迭代法：什么是收敛速度：什么是可约矩阵与不可约矩阵？：不可约矩阵（irreducible matrix）和可约矩阵（reducible matrix）两个相对的概念。

定义1：对于n 阶方阵A 而言，如果存在一个排列阵P 使得P'AP 为一个分块上三角阵，我们就称矩阵A 是可约的；否则称矩阵A 是不可约的。

定义2：对于n 阶方阵A=(aij) 而言，如果指标集{1，2，...，n} 能够被划分成两个不相交的非空指标集J 和K，使得对任意的j∈J 和任意的k∈K 都有ajk=0, 则称矩阵 A 是可约的；否则称矩阵A 是不可约的。

数据网格中一种启发式副本放置算法

数据网格中一种启发式副本放置算法

数据网格中一种启发式副本放置算法付雄;王汝传;邓松【摘要】副本技术广泛用于数据网格中来减少数据访问代价,增强容错能力,从而提高数据网格中数据访问的性能和可靠性.如何合理地放置副本来更有效地提高数据访问性能成为一个需要解决的重要问题.针对无向连通图表示的数据网格模型,在考虑通信代价和存储代价的基础上,提出了一种启发式副本放置算法(heuristic replica placement algorithm, HRPA),通过该算法能够得到k个副本的放置位置,并且使得整个系统的代价最小.最后,通过相应的仿真实验证明了该算法的可行性和有效性.【期刊名称】《系统工程与电子技术》【年(卷),期】2010(032)007【总页数】4页(P1513-1516)【关键词】分布式系统;数据网格;副本放置;启发式算法【作者】付雄;王汝传;邓松【作者单位】南京邮电大学计算机学院,江苏,南京,210003;南京邮电大学计算机学院,江苏,南京,210003;南京邮电大学计算机学院,江苏,南京,210003【正文语种】中文【中图分类】TP3010 引言数据网格(data grid,DG)的概念源自于网格在数据管理方面的应用,即一种在网格环境下实现分布、异构数据资源管理的新的体系结构[1]。

网格作为一种分布式计算的基础架构,其目的是在动态跨组织域的虚拟组织内部实现资源共享和协同问题求解[2]。

近年来,随着网格技术的迅速发展,网格应用领域得到迅速扩张,出现了专门面向数据密集性问题的数据网格[1,3]。

数据网格屏蔽底层资源的异构性,建立海量数据的一体化访问、存储、传输和管理,解决大规模分布式存储环境下的高效可靠的数据共享问题。

在数据网格中,为了减少数据访问的代价,提高整个系统性能,通常在不同的存储节点上建立数据的副本,以实现对数据的就近访问[1,3]。

同时,通过数据副本的复制功能,也增强数据网格的容错能力,提高了整个系统的可靠性。

IBM网格计算

IBM网格计算


links to the Management Modules - 14, 1 Gbps links to the blades An additional or redundant Ethernet
… :: ::
…
ConsIBole
ThinkVision
OOO O
Switch Module may be installed in bay 2
Hot-swap Ethernet Switch Module – bay 1 provides:
- 4-port 1 Gbps Ethernet
(Serial over LAN) for Management Module connection
to network
- 2 internal 10/100 Mbps
Up to four hot-swap 1800/2000 watt Power Modules
Up to eight Ethernet ports
Up to four Fibre Channel ports
Single
management
IBM
console
Resource sharing allows: - Power and cooling savings
~ 326
高性能机架式服务器
支持双 Xeon™ 处理器 支持最大16GB内存 6 个热拔插 SCSI 硬盘 集成系统管理
2U
支持双 Opteron™ 处理器 支持最大16GB内存 2 个热拔插 SCSI 或SATA硬盘 集成系统管理
1U
~ JS20 刀片服务器
基于PowerPC 的刀片服务器 采用双路 2.2GHz PPC 970 芯片 每个刀片最大 4GB 内存 双IDE 硬盘 支持安装2个子卡 (以太网、光纤通道等)