Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes

Shingo YAMAGUCHI  Tomohiro TAKAI  Tatsuya WATANABE  Qi-Wei GE  Minoru TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.11   pp.3207-3215
Publication Date: 2006/11/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.11.3207
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Concurrent/Hybrid Systems: Theory and Applications)
Category: Concurrent Systems
program nets,  parallel degree,  computation complexity,  NP-completeness,  

Full Text: PDF(428.7KB)>>
Buy this Article

This paper deals with computation of parallel degree, PARAdeg, for (dataflow) program nets with SWITCH-nodes. Ge et al. have given the definition of PARAdeg and an algorithm of computing PARAdeg for program nets with no SWITCH-nodes. However, for program nets with SWITCH-nodes, any algorithm of computing PARAdeg has not been proposed. We first show that it is intractable to compute PARAdeg for program nets with SWITCH-nodes. To do this, we define a subclass of program nets with SWITCH-nodes, named structured program nets, and then show that the decision problem related to compute PARAdeg for acyclic structured program nets is NP-complete. Next, we give a heuristic algorithm to compute PARAdeg for acyclic structured program nets. Finally, we do experiments to evaluate our heuristic algorithm for 200 acyclic structured program nets. We can say that the heuristic algorithm is reasonable, because its accuracy is more than 96% and the computation time can be greatly reduced.