お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2016-03-02 14:05
FPGAを用いたハードウェアソーティングアルゴリズムの実装
松本直之周 昕中野浩嗣伊藤靖朗広島大MW2015-180 ICD2015-103 エレソ技報アーカイブへのリンク:MW2015-180 ICD2015-103
抄録 (和) 本稿では,$K$個のキーをクロックごとに1個ずつ入力し,ソートされたキーが1個ずつ出力されるマージソート回路$K$-sorterを設計する.この$K$-sorterを応用し,$N$個のキーの中から上位$K$個のキーを出力する回路top$K$-sorterを提案する.また,これらの回路についてメモリを効率的に使用するよう改善し,さらに$L$個のキーを同時に入力できるようにtop$K$-sorterを拡張した回路$L$-input-top$K$-sorterを提案する.提案アーキテクチャをXilinx Virtex-7 FPGAに実装したところ,メモリを効率的に使用する手法では,メモリリソースの使用量を約半分に削減することができた.また,約10億個のキーの中の上位1k個のキーを求める問題について,$L$-input-top$K$-sorterの処理時間はCPU実装と比較して約1085倍の高速化となった. 
(英) The main contribution of this paper is to design $K$-sorter which sorts $K$ keys given from the input port one by one in every clock cycle, and the resulting sorted $K$ keys are output one by one. This paper presents top$K$-sorter by applying the idea of $K$-sorter, which outputs top $K$ keys in $N$ input keys. This paper also presents improved method for $K$-sorter and top$K$-sorter using memory efficiently. In addition, this paper presents $L$-input-top$K$-sorter, an extension of top$K$-sorter. It has $L$ input ports and can receive $L$ keys at once. We have implemented our $K$-sorter and top$K$-sorter in a Xilinx Virtex-7 FPGA. The implementation results show that our methods reduce the used memory resources by half, compared with the straightforward implementation. In our implementation, $L$-input-top$K$-sorter attains a speed-up factor of 1085 over the sequential implementation on the CPU for finding top 1k keys in approximately one billion keys.
キーワード (和) ハードウェアアルゴリズム / マージソート / FPGA / ブロックRAM / 分散RAM / / /  
(英) Hardware algorithm / Merge sort / FPGA / / Distributed RAM / / /  
文献情報 信学技報, vol. 115, no. 477, ICD2015-103, pp. 37-42, 2016年3月.
資料番号 ICD2015-103 
発行日 2016-02-24 (MW, ICD) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード MW2015-180 ICD2015-103 エレソ技報アーカイブへのリンク:MW2015-180 ICD2015-103

研究会情報
研究会 ICD MW  
開催期間 2016-03-02 - 2016-03-04 
開催地(和) 広島大学 
開催地(英) Hiroshima University 
テーマ(和) マイクロ波集積回路/一般 
テーマ(英) Microwave Integrated Circuit / Microwave Technologies 
講演論文情報の詳細
申込み研究会 ICD 
会議コード 2016-03-ICD-MW 
本文の言語 日本語 
タイトル(和) FPGAを用いたハードウェアソーティングアルゴリズムの実装 
サブタイトル(和)  
タイトル(英) An Implementation of Hardware Sorting Algorithms using the FPGA 
サブタイトル(英)  
キーワード(1)(和/英) ハードウェアアルゴリズム / Hardware algorithm  
キーワード(2)(和/英) マージソート / Merge sort  
キーワード(3)(和/英) FPGA / FPGA  
キーワード(4)(和/英) ブロックRAM /  
キーワード(5)(和/英) 分散RAM / Distributed RAM  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 松本 直之 / Naoyuki Matsumoto / マツモト ナオユキ
第1著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第2著者 氏名(和/英/ヨミ) 周 昕 / Xin Zhou / シュウ セキ
第2著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第3著者 氏名(和/英/ヨミ) 中野 浩嗣 / Koji Nakano / ナカノ コウジ
第3著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第4著者 氏名(和/英/ヨミ) 伊藤 靖朗 / Yasuaki Ito / イトウ ヤスアキ
第4著者 所属(和/英) 広島大学 (略称: 広島大)
Hiroshima University (略称: Hiroshima Univ.)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2016-03-02 14:05:00 
発表時間 25 
申込先研究会 ICD 
資料番号 IEICE-MW2015-180,IEICE-ICD2015-103 
巻番号(vol) IEICE-115 
号番号(no) no.476(MW), no.477(ICD) 
ページ範囲 pp.37-42 
ページ数 IEICE-6 
発行日 IEICE-MW-2016-02-24,IEICE-ICD-2016-02-24 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会