Separation Set Partitioning: Algorithm to Partition Nonstrict Programs into Sequential Threads

Abstract In this paper, we propose separation set partitioning algorithm for partitioning nonstrict programs into threads using participation set and separation set and extened it to global partitioning. Separation set partitioning algorithm can merge threads which dependence set and demand set partitioning algorithm may fail to merge. It deals with certain indirect depdendences and potential indirect dependence uniformly and its time complexity is O(n 2). Experimental results show that the larger threads are made by separation set partitioning than dependence set and demand set partitioning algoritms. 1