| 講演名 | 2005-01-27 SWITCH-nodeを持つデータフロープログラムネットの並列度の計算について(コンカレントシステム, 一般) 渡邊 達哉, 山口 真悟, 葛 崎偉, 田中 稔, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では、SWITCH-nodeを持つデータフロープログラムネットの並列度PARAdegの計算について議論する。まず、PARAdegを拡張した並列度Max/Ave/MinPARAdegを定義する。そして、SWTICH-lessネットをサブクラスに分類し、各サブクラスにおいて、拡張した並列度の計算法やその計算量について議論する。次に、SWITCH-nodeを持つプログラムネットのサブクラスとしてwell-structuredネットを定義し、その性質を示す。そして、非循環well-structuredネットのMaxPARAdegの計算がNP完全であることを証明し、SWITCH-nodeを持つネットのMaxPARAdegの計算は手に負えないことを示す。 |
| 抄録(英) | This paper discusses computation of the degree of parallelism, denoted as PARAdeg, residing in data-flow program nets with SWITCH-nodes. We first give definitions of extended PARAdegs, named Max/Ave/MinPARAdeg. Then we classify SWITCH-less nets into sub classes. For each sub class, we discuss the method of computing the extended PARAdegs and its time complexity. Next, we give the definition of well-structured nets, which is a sub class of program nets with SWITCH-nodes, and show its property. Then we prove that computation problem of MaxPARAdeg of acyclic well-structured nets is NP-complete. As a result, we can say that computation of MaxPARAdeg of program nets with SWITCH-nodes is intractable. |
| キーワード(和) | データフロープログラム / プログラムネット / 並列度 / SWITCH-node / NP完全 |
| キーワード(英) | data-flow program / program net / PARAdeg / SWITCH-node / NP-complete |
| 資料番号 | CST2004-40 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2005/1/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | SWITCH-nodeを持つデータフロープログラムネットの並列度の計算について(コンカレントシステム, 一般) |
| サブタイトル（和） | |
| タイトル（英） | On Computation of PARAdeg of Data-Flow Program Nets with SWITCH-nodes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | データフロープログラム / data-flow program |
| キーワード(2)（和/英） | プログラムネット / program net |
| キーワード(3)（和/英） | 並列度 / PARAdeg |
| キーワード(4)（和/英） | SWITCH-node / SWITCH-node |
| キーワード(5)（和/英） | NP完全 / NP-complete |
| 第 1 著者 氏名（和/英） | 渡邊 達哉 / Tatsuya WATANABE |
| 第 1 著者 所属（和/英） | 山口大学大学院理工学研究科 Graduate School of Science and Engineering, Yamaguchi University |
| 第 2 著者 氏名（和/英） | 山口 真悟 / Shingo YAMAGUCHI |
| 第 2 著者 所属（和/英） | 山口大学工学部 Faculty of Engineering, Yamaguchi University |
| 第 3 著者 氏名（和/英） | 葛 崎偉 / Qi-Wei GE |
| 第 3 著者 所属（和/英） | 山口大学教育学部 Faculty of Education, Yamaguchi University |
| 第 4 著者 氏名（和/英） | 田中 稔 / Minoru TANAKA |
| 第 4 著者 所属（和/英） | 山口大学工学部 Faculty of Engineering, Yamaguchi University |
| 発表年月日 | 2005-01-27 |
| 資料番号 | CST2004-40 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 593 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |