论文部分内容阅读
从计算机诞生之日起,计算资源的稀缺性一直困扰着计算机专家,资源分配问题也一直是研究的热点。为了充分利用计算机资源,实现资源共享,学者们提出了很多有效的分布式计算模型,如中间件技术、移动Agent技术、P2P技术、网格技术以及Web Service技术等。网格技术,通过整合计算、存储和其他资源,使得需要大量计算资源的复杂问题求解成为可能。LHC计算网格(LCG)正在为地球上最大的科学设施(大型强子对撞机)存储和分析数据、美国网格超级计算机正在模拟婴儿期宇宙图景,中国国家网格(CNGrid)也聚合了高性能计算和事务处理能力。通过资源共享、协同工作和服务机制,有效支持科学研究、资源环境、先进制造和信息服务等应用。网格就是一个集成的计算与资源环境,或者说是一个计算资源池。网格能够充分吸纳各种计算资源,并将它们转化成一种随处可得的、可靠的、标准的同时也是经济的计算能力。网格是一个软硬件的基础设施,提供对高端计算能力可靠、一致、普遍并且廉价的访问。它是在动态的多机构的虚拟组织中协调资源共享和协同解决问题,将虚拟组织、资源共享和资源协同统一起来。网格资源具有异构性、动态性和自治性的特点。网格资源的这些特性给网格资源自身的管理带来了不可控性,其资源分配属于NP完全问题。针对网格计算的资源分配问题,很多学者进行了深入的研究,基于智能技术、经济理论等建立了诸多网格资源分配模型。本文在充分分析网格计算的特点和网格系统环境下资源分配固有的复杂性的前提下,基于新兴古典理论研究网格系统环境下的资源分配问题。其思想是不同的节点在处理不同的请求时具有比较优势,将这些请求分配到最具有比较优势的节点上执行,研究的是如何在众多节点中选取最优效能计算节点进行资源调度并动态调整网络结构。通过市场竞争不仅能有效地分配资源(角点均衡),而且能选择有效的分工结构(全部均衡),从而达到整体帕累托最优。所建立的计算模型既使用了古典经济学中的分工和专业化理论,也将新古典经济学的边际分析纳入其中,即新兴古典经济学中的超边际分析方法。它既不同于目前广泛研究的瓦尔拉斯一般均衡的资源定价模型,也不同于基于纳什均衡的拍卖模型。这两种模型的研究重点都在于资源分配问题本身,基于新兴古典经济学的资源分配方法不仅研究资源分配本身,同时也对资源的分配结构进行探讨,是一种高度自治的分配方法,每个节点根据本地信息做出分配策略,而不涉及全局信息,简化了资源分配的复杂性,缩小了解空间,有效地限制了解空间爆炸现象。本文基于新兴古典经济理论,研究网格环境下的资源分配问题。从网格资源的经济性分析入手,对网格资源分配的模型、资源分配算法和资源分配结构进行了深入的研究,并通过仿真试验验证了本文提出的方法。主要内容包括:(1)对网格环境下资源分配问题进行经济性分析,提出一种基于新兴古典经济理论的网格资源分配分析框架。通过建立网格资源环境下的生产系统,将资源消费者和资源提供者统一在一个框架中,引入专业经济和交易费用,确定多样化消费和交易费用,在瓦尔拉斯制度和库恩-塔克条件下,应用多步法求出候选的最优角点解集合。从对网格系统的经济性分析可以看出,网格环境下的资源分配问题涉及到资源提供者-消费者的个体行为,经济理论对资源分配特点进行了精确刻画,为量化分析提供了理论基础,非常适合于解决网格资源分配问题。(2)提出了一种基于超边际分析的网格资源分配模型。采用柯布-道格拉斯效用函数描述网格中用户效用,在时间禀赋条件下,基于消费者选择理论和比较优势,确定各服务节点的效用函数、服务向量和交换向量,建立了网格系统环境下资源分配的一般均衡模型,并以多种请求在任意两个节点间的情况为例说明模型的建立和求解过程。通过实验可以看出,分工和专业化可以将每种请求分配到合适的服务节点上执行,进而提高系统的整体执行效率。对于具体的分配方案,则需要借助于超边际分析,使得每一步都能量化。(3)在网格资源分配模型基础上,选择网络分工结构,进行比较静态分析。通过对执行能力、交换系数的确定来进行各分配结构的角点分析,得到合理分配资源的三种结构,并给出了相应的分配算法。分工结构确定后对每种结构进行比较静态分析,包括对资源供给和效用函数可能发生的跃变的确定,以及在给定的分工水平和结构下角点解对环境变化做出的反应。如果市场中全部服务的自给量和交易量使结构的效用极大化,则可解出给定结构的资源配置,即分工结构的局部帕累托最优配置。实验模拟给出了两组节点和两组效用函数指数。由实例分析可以看出,对于一个既定的节点,其执行能力为定值,相对均衡价格也为定值,其最大值的选择与交换效率密切相关,也就是与网络传输能力密切相关。当交换效率非常低时,自给自足结构的局部最大值就是整体最优解,两节点也选择自给自足结构。当交换效率逐步提高时,就会由自给自足结构转换成专业化服务结构,此时,专业化服务结构的最大值就是整体最优解。(4)提出一种基于帕累托最优化的分配决策分配模型,通过对不同分配结构进行决策分析,得出选择不同结构的条件并建立计算分配结构的算法。通过仿真试验模拟多种请求在两个节点进行分配的情况,根据初始数据本身的性质以及算法的特点,结合仿真图对各种分配方案进行结果分析和算法评估。同时对多节点执行多种服务的情况进行讨论,当最具有比较优势的两种请求分配完成以后,就可以对次具有比较优势的服务通过以上的步骤分配。以此类推,直到两种请求通过计算之后发现,其比较优势不足以冲抵交换带来的损失,也即处于自给自足分配结构为止。按照这种方法,对任意两个相连的节点进行类似的计算和分配,逐步使得整个系统的效用最大化,每个服务网中的客户效用最大化。本文基于新兴古典经济理论研究网格资源分配策略。每个节点既是资源提供者,又是资源消费者,超边际分析根据不同节点在处理不同请求时具有比较优势的原理,将请求分配到最具有比较优势的节点上执行。同时,考虑网络传输等代价和比较优势利益上的平衡,使节点总效用最大化。在使资源得到最有效利用的同时找到最合理的网络分工结构,达到整体帕累托最优。仿真实验证明,本文提出方法能够有效地完成资源分配,并可以根据网络条件变化动态调整分工结构。