PARAdeg Computation and Scheduling of Self-Cleaning SWITCH-less Program Nets

概要

論文の詳細を見る
A program net(denoted as PN) is a graph representation of a data-flow program and its parallelism has been studied through computing PARAdeg =Σ(f(z_i)T_i)/T, where f(z_i) and T_i are maximum firing number and single firing time of node z_i respectively and T is minimum firing time of PN. For a SWITCH-less PN, the numerator of PARAdeg can be efficiently computed, however the denominator is usually costed with exponential computation time. To improve this, we proposed an improved algorithm by a way of contracting nodes for self-cleaning SWITCT-less PNs with identical node firing time. However the problem for the case of arbitrary node firing time has not been studied yet. And also it is important to schedule execution of PNs by using finite processors. In this paper we first propose conditions that node contraction can be carried out for self-cleaning SWITCH-less PNs with arbitrary node firing time. Then we give scheduling methods by using PARAdeg processors to execute SWITCH-less PNs.
一般社団法人情報処理学会の論文
1996-09-04