著者

伊藤 靖朗 ボルジン ジャシル 中野 浩嗣

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2002, no.70, pp.35-42, 2002-07-25

参考文献数

10

---

本論文では,文脈自由文法に対するCKYパージングを高速に行う入力依存回路によるFPGAへの実装を提案する.文脈自由文法Gと文字列xが与えられたときに,CKYパージングはGがxを導出するか否かを判定する.このCKYパージングは,xの長さがnのときに,O(n^3)時間で導出するかを判定するできることが知られている.任意の文脈自由文法Gが与えられたときに,その文法に対するCKYパージングを行うハードウェアのVelilog HDL記述を生成するハードウェアジェネレータを示す.生成された記述は,FPGAに実装され,任意の文字列xに対して,Gがxを導出するかを判定する.このFPGAは,特定の文法Gに対してのみパージングを行うので,入力依存ハードウェアであり,究極の高速化が可能である.このハードウェアの性能をタイミング解析により評価し,また,アルテラ社のFPGAを用いて動作確認を行った.結果として,ソフトウェアによるCKYパージングより約750倍高速であることがわかった.

著者

中野 浩嗣 オラリウ ステファン

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.100, no.481, pp.25-32, 2000-11-27

---

本論文では、シングルホップの1つのチャネルをもつ無線ネットワーク上にn台のステーションが存在する場合に、リーダ選択を行う省電力確率プロトコルを提案する.提案するプロトコルは、全てのステーションが台数nを知っている場合に、任意のf(f&ge;1)に対して確率1-1/fで、O(log f)時間でリーダ選択を行い、また、どのステーションも高々O(log log f+log f/log n)回の送受信を行う.どのステーションもnを知らない場合、提案するプロトコルは、平均O(log n)時間でリーダ選択を行い、また、確率1-1/fで、O(min((log n)^2+(log f)^2, f^<3/5>olg n))時間動作し、どのステーションも高々O(log n+log f)回の送受信を行う.

著者

中野 浩嗣 伊藤 靖朗 川上 賢介 重本 耕司

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. RECONF, リコンフィギャラブルシステム (ISSN:09135685)

巻号頁・発行日

vol.109, no.198, pp.79-84, 2009-09-10

被引用文献数

3

---

本稿では,単純,スケーラブル,かつポータブルで,FPGAに実装可能なTiny processing systemを提案する.このシステムは,16-bitのプロセッサ,クロスアセンブラ,クロスコンパイラを含んでいる.このシステムのソースコードは極めて少なく,16-bitのプロセッサはVerilog HDLで268行で書かれている.クロスアセンブラは38行のPerlスクリプトである.クロスコンパイラは,23行の字句解析のためのFlex文法ファイルと,90行の構文解析とコード生成のためのBison文法ファイルから構成される.よって,このTiny processing systemは容易に理解でき,機能拡張も難しくない.このシステムの教育と小型組込みシステムへの応用を示す.

著者

本田 巧 伊藤 靖朗 中野 浩嗣

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 (ISSN:09135685)

巻号頁・発行日

vol.114, no.302, pp.81-86, 2014-11-13

---

本稿では,コラッツ予想の網羅的検証のGPU実装を提案する.我々はNVIDIA Geforce GTX TITAN上を用いて実装及びその性能評価を行った.実験結果より,提案するGPU実装は1秒間に5.01×10^<11>個の64bitの自然数を検証可能であることを確認した.同様の処理をおこなうCPU実装は1秒間に1.80×10^9個の64bitの自然数の検証が可能であることより,提案するGPU実装はCPU実装と比較して278倍の高速化を実現した.

著者

林 達也 中野 浩嗣 オラリウステファン

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.89, pp.23-30, 1996-09-13

参考文献数

19

---

要素数が合計がnのソートされたk個の列をマージして新しいソート列を求める問題をkマージ問題と呼ぶ。本論文では、単純で仕事・時間量が最適な3つのPRAM上のkマージ問題を解くアルゴリズムを示す。まず、EREW?PRAM上で、O(og )時間で仕事量がO( log )のkマージアルゴリズムと、CREW?PRAMとCRCW?PRAM上でO(oglog n+log )時間で仕事量がO( log )のkマージアルゴリズムを示す。また、これらのアルゴリズムが仕事量がO( log )である限り、高速化はできないことを示す。The k-merge problem, given a collection of k,(2〓k〓n), sorted sequences of total length n, asks to merge them into a new sorted sequence. The main contribution of this work is to propose simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models. Our k-merge algorithms runs in O(log n) time and performs O(n log k) work on the EREW-PRAM. and in O(loglog n+log k) time and O(n log k) work both on the CREW-PRAM and on the CRCW-PRAM. We also prove that the computing time of these algorithms cannot be improved provided that the amount of work is bounded by O(n log k).

著者

開内 幸治 中野 浩嗣 金田 和文

雑誌

研究報告インターネットと運用技術(IOT) (ISSN:21888787)

巻号頁・発行日

vol.2017-IOT-36, no.37, pp.1-7, 2017-02-24

---

本稿では平成 28 年度電気 ・ 情報関連学会中国支部連合大会で使用するために構築した Web 投稿受付システムとそのシステム運用についてそれぞれ述べる.構築にはフォーム作成収集のためのクラウドサービスである JotForm を利用し,入力者,運用側それぞれにメリットがあるように基本的構築設計方針を定めて行った.運用時に発生したトラブルについて原因をシステム側,入力者側に分けて記述し,今後の改善点を述べる.これまで利用してきた高額な Web 投稿受付の外部委託に比べ,比較的簡易な設定作業により極めて低コストに投稿受付システムの構築と運用が行えた.

著者

船坂峻慈 中野浩嗣 伊藤靖朗

雑誌

研究報告システム・アーキテクチャ(ARC) (ISSN:21888574)

巻号頁・発行日

vol.2016-ARC-222, no.6, pp.1-6, 2016-09-29

---

データ圧縮はコンピュータエンジニアリングの分野で非常に重要である.しかし,多くの可逆圧縮と展開アルゴリズムは並列化が非常に難しい.本論文では Light Loss - Less (LLL) 圧縮と呼ぶ,新しい可逆圧縮法を提案する.この圧縮法の展開アルゴリズムは高い並列化が可能であり GPU を用いて非常に高速に処理することができる.データ展開は圧縮と比較して何度も行うためにこの圧縮法は多くのアプリケーションで応用できる.我々は LLL 展開の並列アルゴリズムを提案し GeForce GTX 1080 GPU に実装した.GPU を用いた LLL 展開の実効速度を Core i7- 4790 への逐次 CPU 実装と比較し 91.1-176 倍の高速化を達成した.また,よく知られている圧縮手法である LZSS と LZW との比較も行う.提案手法は圧縮率は同程度である一方で LZSS 展開の GPU 実装と比較して 4.30-14.1 倍,LZW 展開の GPU 実装と比較して 2.49-9.13 倍の高速化を達成した.

著者

山際 伸一 和田 耕一 中野 浩嗣 柚木 清司

出版者

筑波大学

雑誌

基盤研究(B)

巻号頁・発行日

2012-04-01

---

ストリーム指向プログラムはGPUといったメニーコアアクセラレータの普及によって、科学技術計算から産業用製品にまで利用されている。その単体性能は、チップ内における密並列によるプログラム実行により高い性能を示す。しかし、複数のアクセラレータを使った超並列計算を考慮すると、タスクの分割と通信タイミングを配慮したプログラム開発が必要になり、性能をスケーラブルに維持したままの開発が困難となる。本研究では、このようなGPUでのストリーム指向プログラムを対容積・対電力での計算能力の高密度化をねらい、自動的に複数のGPUで並列化し、スケーラブルに性能向上が可能なプログラミング基盤技術を開発する。