基于关系的最粗粒度划分问题的并行算法  

A Parallel Algorithm for Relational Coarsest Partition Problems

作　　者：霍红卫[1] 

机构地区：[1]西安电子科技大学计算机科学系

出　　处：《计算机工程与科学》2000年第4期40-42,共3页Computer Engineering & Science

基　　金：国家自然科学基金!资助项目 ( 6960 2 0 0 8);"九五"预研项目!资助 ( 16.1.4.2 )

摘　　要：关系最粗粒度的划分问题 RCPP在并发系统的验证方面起着重要的作用。本文提出了RCPP问题的一种有效的并行算法 ,其中假设标号转移系统中有 m个转移和 n个状态 ,利用 m/nε个CREW处理器算法所需的运行时间为 O( n1+ε) (对于任意固定的 ε<1 )。The relational coarsest partition problem(RCPP)plays a vital role in verifying concurrent systems.In this paper,an efficient parallel algorithm is presented for RCPP. The associated label transition system of the algorithm is assumed to have m transitions and n states.The algorithm's run time is O(n 1+ε ) using m/n ε CREW processors for any fixed ε<1.

关 键 词：最粗粒度划分问题 并行算法 标号转移系统 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]