Fast stable matching algorithm using asynchronous parallel programming model

作     者：Verdier, Francois Merigot, Alain Zavidovique, Bertrand 

作者机构：Universite de Cergy-Pontoise Cergy-Pontoise France 

出 版 物：《Computer Architectures for Machine Perception, Proceedings (CAMP)》 (Comput Archit Mach Percept CAMP Proc)

年 卷 期：2000年

页      面：131-135页

核心收录：

主　　题：Parallel algorithms 

摘      要：This paper presents some results of programming efficient matching algorithms on a new asynchronous parallel programming model. Matching algorithms are widely used in Image Processing when considering high-level treatments. Pattern Analysis, Database Search, 2D and 3D reconstruction all need matching algorithms to perform. Experiments we done were mainly oriented towards a particular matching problem: the Stable Marriage algorithm. Different implementations of this algorithm have been done on a massively parallel asynchronous model. This model relies on a network of asynchronously communicating processors leading to very fast SIMD treatments. The asynchronous model and implementations of the matching algorithm are presented. An example of Image Processing problem is also used for illustration purpose and supports the architectural discussion and results.