Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes(Concurrent Systems,<Special Section>Concurrent/Hybrid Systems: Theory and Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2006-11-01

著者

• Ge Q‐w

  Yamaguchi Univ. Yamaguchi‐shi Jpn

• Ge Qi-wei

  Faculty Of Education Yamaguchi University

• Yamaguchi S

  Graduate School Of Science And Engineering Yamaguchi University

• Tanaka M

  Graduate School Of Science And Engineering Yamaguchi University

• YAMAGUCHI Shingo

  Graduate School of Science and Engineering, Yamaguchi University

• TANAKA Minoru

  Graduate School of Science and Engineering, Yamaguchi University

• TAKAI Tomohiro

  Graduate School of Science and Engineering, Yamaguchi University

• WATANABE Tatsuya

  Fujitsu System Solutions, Ltd.

• Takai Tomohiro

  Graduate School Of Engineering Osaka Prefecture University

• Takai Tomohiro

  Graduate School Of Science And Engineering Yamaguchi University

• Yamaguchi Shingo

  Graduate School Of Science And Engineering Yamaguchi University

• Watanabe Tatsuya

  Fujitsu System Solutions Ltd.

• Ge Qi‐wei

  Faculty Of Education Yamaguchi University

• Tanaka Minoru

  Graduate School Of Science And Engineering Yamaguchi University

• Yamaguchi Shingo

  Yamaguchi Univ. Ube‐shi Jpn

関連論文

• 20 Development and Demonstration of CAD/CFD/Optimizer Integrated Simulation-Based Design Framework by Using High-Fidelity Viscous Free-Surface RaNS Equation Solver
• An Optimal Two-Processor Scheduling for a Class of Program Nets via a Hybrid Priority List (特集 並列処理)
• Modelling and simulation of signal transductions in an apoptosis pathway by using timed Petri nets
• A Flexible and Efficient Workflow Change Type : Selective Shift(Papers Selected from ITC-CSCC 2004)
• Modeling and Performance Evaluation on Change Time for Migrate Dynamic Workflow Changes(Special Section on Papers Selected from ITC-CSCC 2002)
• WF-Net Based Modeling and Soundness Verification of Interworkflows(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
• Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
• Performance Evaluation on Worst Change Time of Flush and SCO Dynamic Changes for State Machine WF-Nets(Papers Selected from 2005 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2005))
• Dead Problem of Program Nets(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
• Monosyllable intelligibility improved by spectral equalization of spoken sound presented in the water : Influence of the shape of voice spectrum
• Computation Methods of Maximum Throughput for MG/SMWF-Nets with Conflict-Free Resources(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
• Performance Evaluation on Transient Time of Dynamic Workflow Changes(Special Section on Concurrent Systems Technology)
• Differential intensity sensitivity of the ear for underwater pure tones
• Performance Evaluation on Change Time of Dynamic Workflow Changes (Special Section on Concurrent Systems Technology)
• Practical Methods of Evaluating the Underwater Insulation Effect of a Single Wall
• An Efficient Search Method Based on Dynamic Attention Map by Ising Model(Image Recognition and Understanding)
• Estimation of Camera Rotation Using Quasi Moment Features (Special Section of Papers Selected from ITC-CSCC'99)
• Investigation on Effective Turbulence Models for Predicting Tanker Stern Flows
• A Fast Projection Algorithm for Adaptive Filtering
• Cooperative and Competitive Network Suitable for Circuit Realization
• Controlling Initial State of Cooperative and Competitive Cellular Neural Networks
• A practical method for estimating the headway distribution based on the observed data of the number of flowing vehicles : Gamma distribution model
• Box Puzzling Problem Solver by Hysteresis Neural Networks(Special Section on Nonlinear Theory and its Applications)
• Hysteresis Neural Networks for N-Queens Problems (Special Section on Nonlinear Theory and Its Applications)
• Subjective Assessment of the Desired Echo Return Loss for Subband Acoustic Echo Cancellers
• Parallel Degree of Well-Structured Workflow Nets
• Delay Time Determination for the Timed Petri Net Model of a Signaling Pathway Based on Its Structural Information
• MceSim : A Multi-Car Elevator Simulator
• A Model Checking Method of Soundness for Workflow Nets
• On Verification of Token Self-Cleanness of Data-Flow Program Nets (Special Section of Papers Selected from JTC-CSCC'95)
• Performance Evaluation of a Two-Processor Scheduling Method for Acyclic SWITCH-less Program Nets(Papers Selected from ITC-CSCC 2004)
• A New Proposal to Two-Processor Scheduling Problem for SWITCH-less Program Nets(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
• An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes(Special Section on Papers Selected from ITC-CSCC 2001)
• A Two-Processor Scheduling Method for a Class of Program Nets with Unity Node Firing Time (Special Section on Concurrent Systems Technology)
• A Method of Finding Legal Sequence Number for a Class of Extended Series-Parallel Digraphs (Special Section on Discrete Mathematics and Its Applications)
• Polynomial Time Verification of Behavioral Inheritance for Interworkflows Based on WfMC Protocol
• An Effective Dynamic Priority List for 2-Processor Scheduling of Program Nets(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
• Incorporation of Cycles and Inhibitory Arcs into the Timed Petri Net Model of Signaling Pathway

もっと見る 閉じる

スポンサーリンク