伽罗瓦连接不动点的并行算法

The parallel algorithm of computing fixpoints of Galois commections

为了提高伽罗瓦连接所有不动点的计算速度和效率,在计算伽罗瓦连接不动点的串行算法(CbO)基础上,通过处理所有不动点的不相交子集方法,将串行算法并行化,启动P个处理器同时并行运行,使每个处理器都并行地计算它的所有不动点,证明了此算法的正确性,并分析了它的渐近式复杂性。实验给出了算法在各种数据集上的效率及可扩展性,表明PCbO并行算法效率优于其串行算法。

In order to improve speed and efficiency of computing fixpoints of Galois connections,based on the serial algorithm of computing fixpoints of Galois connection, by processing disjoint subset of the fixpoints method, this paper parallels the serial algorithm, and has P independent processors running in parallel, so that every processor parallelly compute its fixpoints. It proves the correctness of the parallel algorithm, and analyze its asymptotic complexity. The experiment provides the scalability and efficiency of the algorithm on various data sets. The experiment results show that PCbO parallel algorithm is more efficient than the serial algorithm.