講演抄録/キーワード |
講演名 |
2005-08-22 13:00
Acyclic Well-StructuredデータフロープログラムネットのMaxPARAdegの近似計算について ○高井智博・山口真悟・葛 崎偉・田中 稔(山口大) |
抄録 |
(和) |
本稿では、SWITCH-nodeをもつデータフロープログラムネットのサブクラスの一つであるAcyclic Well-Structuredネットの最大並列度$MaxPARAdeg$の近似計算について議論する。まず、Acyclic Well-Structuredネットの定義を示し、その諸性質を明らかにする。次に、Acyclic Well-Structuredネットの$MaxPARAdeg$を計算する問題に取り組む。この問題は手に負えない(intractable)ことが知られているため、我々はその近似計算アルゴリズムを提案する。そして提案したアルゴリズムによって、150個のAcyclic Well-Structuredネットの$MaxPARAdeg$を計算し、その値と真値を比較することによって提案したアルゴリズムを評価する。その結果は提案したアルゴリズムが計算時間を大幅に削減する一方、高精度な近似値を求められることを示している。 |
(英) |
This paper discusses approximate computation of the maximum degree of parallelism, denoted $MaxPARAdeg$, for a subclass of dataflow program nets with SWITCH-nodes, called acyclic well-structured nets. We first show the definition and properties of acyclic well-structured nets. It is intractable to compute $MaxPARAdeg$ for acyclic well-structured nets. Thus we propose an approximate algorithm to compute $MaxPARAdeg$. Finally, we evaluate the approximate algorithm by comparing its approximate values with exact values of $MaxPARAdeg$ for 150 acyclic well-structured nets. The results show that our approximate algorithm is reasonable from the viewpoint of accuracy and computation time. |
キーワード |
(和) |
データフロープログラム / プログラムネット / 並列度 / SWITCH-node / 近似アルゴリズム / / / |
(英) |
data-flow program / program net / parallel degree / SWITCH-node / approximate algorithm / / / |
文献情報 |
信学技報, vol. 105, 2005年8月. |
資料番号 |
|
発行日 |
2005-08-15 (CST) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|