Ingram Stephen, Munzner Tamara, Olano Marc
Department of Computer Science, University of British Columbia, Vancouver, Canada.
IEEE Trans Vis Comput Graph. 2009 Mar-Apr;15(2):249-61. doi: 10.1109/TVCG.2008.85.
We present Glimmer, a new multilevel algorithm for multidimensional scaling designed to exploit modern graphics processing unit (GPU) hardware. We also present GPU-SF, a parallel, force-based subsystem used by Glimmer. Glimmer organizes input into a hierarchy of levels and recursively applies GPU-SF to combine and refine the levels. The multilevel nature of the algorithm makes local minima less likely while the GPU parallelism improves speed of computation. We propose a robust termination condition for GPU-SF based on a filtered approximation of the normalized stress function. We demonstrate the benefits of Glimmer in terms of speed, normalized stress, and visual quality against several previous algorithms for a range of synthetic and real benchmark datasets. We also show that the performance of Glimmer on GPUs is substantially faster than a CPU implementation of the same algorithm.
我们展示了Glimmer，一种用于多维缩放的新型多级算法，旨在利用现代图形处理单元（GPU）硬件。我们还展示了GPU-SF，它是Glimmer使用的基于力的并行子系统。Glimmer将输入组织成一个层次结构，并递归地应用GPU-SF来合并和细化这些层次。该算法的多级特性降低了陷入局部最小值的可能性，而GPU并行性提高了计算速度。我们基于归一化应力函数的滤波近似为GPU-SF提出了一个鲁棒的终止条件。针对一系列合成和真实基准数据集，我们展示了Glimmer在速度、归一化应力和视觉质量方面相对于几种先前算法的优势。我们还表明，Glimmer在GPU上的性能比同一算法的CPU实现要快得多。
