2021/05/25 by Martens, Jan, Groote, Jan Friso, Haak, Lars van den +2
#D1.3 #Data Structures and Algorithms (cs.DS) #Distributed #F2.0 #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2105.11788
The most efficient way to calculate strong bisimilarity is by calculation the relational coarsest partition on a transition system. We provide the first linear time algorithm to calculate strong bisimulation using parallel random access machines (PRAMs). More precisely, with n states, m transitions and |Act|≤ m action labels, we provide an algorithm on max(n,m) processors that calculates strong bisimulation in time O(n+|Act|) and space O(n+m). The best-known PRAM algorithm has time complexity O(nlog n) on a smaller number of processors making it less suitable for massive parallel devices such as GPUs. An implementation on a GPU shows that the linear time-bound is achievable on contemporary hardware.