针对GPU通用计算环境CTM纹理资源的限制,研究了一种适于CIM的单纯形方法.依据单纯形方法每次变换最多只增加一列非单位元向量和矩阵求逆运算的特征,给出GPU上系数矩阵、基逆矩阵等的压缩存储策略及在该策略下求解基逆矩阵、单纯形乘子和检验数等步骤新的计算规则.CPU主要进行迭代控制;而计算密集类任务皆由GPU完成.理论分析证明该方法比标准方法在时空复杂度上提高了一个数量级.数值实验表明该方法不仅扩大了可求解问题的规模,且在获得正确优化结果的前提下,效率比CPU版本有数百倍的提高,甚至数倍领先于MATLABR2007a.%We present a GPU-based algorithm for solving linear programming problems using simplex methods under CTM ( close to the metal) environment. Matrix-packed storage strategy and correlative computation formulas such as revised basic matrix? simplex multiplier and departing variables are brought forward, according to the fact that at most one column vector produces in each vertex changing step and the feature of reverse matrix of simplex method.CPU takes charge of the iteration and all compute-inten-sive tasks are carried out by GPU.Theory analysis proves that both space complexity and time complexity are superior to traditional method.Numerical experiments on randomly generated problems demonstrate that this method can not only get correct optimal solution, but also reach as fast as hundred times of CPU-based version; and it runs several times faster than MATLAB R2007a.
展开▼
