求解云计算压力测试中并行任务密度的高速算法

针对当前云计算负载压力测试过程中，对所采集数据计算并行任务密度的算法效率较低的问题，基于空间换时间的思路，使用数学分析的方法，提出了一种时间复杂度为O(n lb n)，空间复杂度为O(n)的求解并行任务密度的高速算法。实验结果表明，该算法与时间复杂度同为O(n lb n)的OpenSTA算法相比，效率约有6~8倍的提升。该算法对多个相同的并行任务密度能够解得并行时长最长者，可以准确反映负载最重的情况。该算法适合云计算进行负载均衡算法设计时，获取真实参照数据使用。

High-speed algorithm for density of parallel tasks in cloud computing load testing

During the current cloud computing load testing, in order to solve the problem of low efficiency of the algorithm for calculating the density of parallel task to the data collected, based on the idea of space for time, using the method of mathematical analysis, a high-speed algorithm for density of parallel task was proposed. Its time complexity is O(n lb n) and the space complexity is O(n). The experimental results show that, compared with the OpenSTA algorithm with the same time complexity, the increment of efficiency is about 6 to 8 times. The algorithm of multiple the same density of parallel tasks can obtain maximum duration, which can accurately reflect the situation of the heaviest load. The algorithm is applied to obtain the real reference data for the design of cloud computing load balancing algorithm.