Dynamic Load Balancing Technique for Modified PrefixSpan on a Grid Environment with Distributed Worker Model.
Makoto Takaki, Keiichi Tamura, Hajime Kitakami · Parallel and Distributed Processing Techniques and Applications · 2006
In order to extract the frequent sequence patterns that can become a motif in amino acid sequences at high speed, we are working on developing the parallel processing of the Modified PrefixSpan method on a grid environment. The Modified PrefixSpan method has two characteristics: One is an extreme load imbalance and the other is the inability to estimate the load of the task. In this study, the distributed worker model is applied to the parallel processing of the Modified PrefixSpan method on a grid environment. Moreover, in this paper, we propose Cache-based Multicast Stealing (CMS), which combines the multicast stealing and Cachebased Random Stealing technique. The distributed worker model has enough scalability to endure an increase in the number of PC clusters. CMS can reduce the overhead generated by the communication delay.