講演名	1995/4/21 確率的手法によるCRCW PRAM間の模倣について 藤原 俊幸, 岩本 宙造, 岩間 一雄,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)	ARBITRARY型(及びPRIORITY型)のCRCW PRAMの1ステップの動作は,COMMON型でΘ(/)ステップで模倣できることは知られている。しかし,確率的手法を用いた場合,本質的により高速な模倣が可能か否かは未解決であった。本稿では,失敗確率をn^<-c>に抑えたO(/+loglog n)ステップの確率的模倣を示す。ここで,m=n/kは模倣されるPRAMにおいて同時書込みが行なわれるメモリセルの数である。m≤/のとき,本結果はO(loglog n)ステップの模倣となる。
抄録(英)	It is known that one step of ARBITRARY (PRIORITY also) CRCW PRAMs is simulated by Θ(/) steps of COMMON CRCW PRAMs, but it was Open whether there is an essentially faster simulation if randomization is allowed. This paper presents a randomized simulation of O(/+loglog n) steps with error rate n^<-c>, where m=n/k is the number of different memory cells to which some processor in the simulated PRAM attempts to write. When m≤/, this bound can be written as O(loglog n).
キーワード(和)	並列ランダムアクセス機械 / 並列アルゴリズム / 模倣 / 確率的手法
キーワード(英)	PRAMs / parallel algorithms / simulation / randomized methods
資料番号
発行日

研究会情報
研究会	COMP
開催期間	1995/4/21(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Theoretical Foundations of Computing (COMP)
本文の言語	JPN
タイトル（和）	確率的手法によるCRCW PRAM間の模倣について
サブタイトル（和）
タイトル（英）	Randomized Simulations Between CRCW PRAMs
サブタイトル（和）
キーワード(1)（和/英）	並列ランダムアクセス機械 / PRAMs
キーワード(2)（和/英）	並列アルゴリズム / parallel algorithms
キーワード(3)（和/英）	模倣 / simulation
キーワード(4)（和/英）	確率的手法 / randomized methods
第 1 著者 氏名（和/英）	藤原 俊幸 / Toshiyuki Fujiwara
第 1 著者 所属（和/英）	九州大学工学部情報工学科 Department of Computer Science and Communication Engineering Kyushu University
第 2 著者 氏名（和/英）	岩本 宙造 / Chuzo Iwamoto
第 2 著者 所属（和/英）	九州大学工学部情報工学科 Department of Computer Science and Communication Engineering Kyushu University
第 3 著者 氏名（和/英）	岩間 一雄 / Kazuo Iwama
第 3 著者 所属（和/英）	九州大学工学部情報工学科 Department of Computer Science and Communication Engineering Kyushu University
発表年月日	1995/4/21
資料番号
巻番号（vol）	vol.95
号番号（no）	13
ページ範囲	pp.-
ページ数	9
発行日