Scalable Parallel Algorithms for Image Processing and Computational Geometry

本研究的重点是设计、分析和实现有效的算法和范例，以解决并行计算机上的图像分析和计算几何问题。具体来说，算法被认为是一种可扩展的计算模型，它提供了一种可靠的度量，可以比较在商业上可用的中粒度并行机器上的算法之间的运行时间。这些算法通常将高效的并行数据移动操作、范式和数据缩减技术与高效的顺序算法结合起来。重点是机器人和图像处理的应用问题，包括那些涉及连通性、凸性、接近性、面积、交叉和最小面积封闭多边形的问题，仅举几例。该研究的实验部分包括移植、优化和评估一个大型系统，该系统旨在解决各种多处理器平台上x射线晶体学中的一个重要问题。

The focus of this research is on the design, analysis, and implementation of efficient algorithms and paradigms to solve problems in image analysis and computational geometry on parallel computers. Specifically, algorithms are considered for a scalable model of computation that provides a reliable metric in terms of a comparison of running times between algorithms on commercially available medium-grained parallel machines. The algorithms typically combine efficient parallel data movement operations, paradigms, and data reduction techniques, with efficient sequential algorithms. The concentration is on problems with applications to robotics and image processing, including those involving connectivity, convexity, proximity, area, intersection, and minimal-area enclosing polygons, to name a few. The experimental component of the research includes the porting, optimization, and evaluation of a large system designed to solve an important problem in x-ray crystallography, over a wide variety of multiprocessor platforms.