云计算中TSP问题求解服务的定价机制

旅行商问题(TSP)是一个典型的路径优化问题,在城市交通规划、物流运输、通信网络设置等领域都存在类似的问题和应用。但是,TSP问题的求解是NP难的,当问题规模很大时,必须借助大规模并行计算环境,例如云计算平台,以较大的计算开销来获得可行解。以TSP问题为具体实例,研究云计算服务的定价机制。一般情况下,定价机制要满足公平、灵活、动态、自适应。从公平合理角度来看,影响计算服务定价的因素主要有两方面:一是求解问题的难度,包括计算时间复杂性、空间复杂性、输入输出数据规模等;二是求解服务质量,即服务契约,包括可以作为服务等级协定指标的求解精度、响应时间、资源要求等。由此,提出了一种新的云计算中的服务定价机制:CloudPricing。该机制给出了服务定价的一般和具体原则,并给出了相应的定价公式。针对TSP问题求解,进行了具体的定价实例分析,这对云计算中NP难问题求解服务的定价有参考意义。     

并行时空处理模型下的快速N-body算法

图形处理器(graphic processing unit,GPU)的最新发展已经能够以低廉的成本提供高性能的通用计算。基于GPU的CUDA(compute unified device architecture)和OpenCL(open computing language)编程模型为程序员提供了充足的类似于C语言的应用程序接口(application programming interface,API),便于程序员发挥GPU的并行计算能力。采用图形硬件进行加速计算,通过一种新的GPU处理模型——并行时间空间模型,对现有GPU上的N-body实现进行了分析,从而提出了一种新的GPU上快速仿真N-body问题的算法,并在AMD的HD Radeon 5850上进行了实现。实验结果表明,相对于CPU上的实现,获得了400倍左右的加速;相对于已有GPU上的实现,也获得了2至5倍的加速。