著者
Demaine Erik D. Okamoto Yoshio Uehara Ryuhei Uno Yushi
出版者
電子情報通信学会
雑誌
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)
巻号頁・発行日
vol.E97-A, no.6, pp.1213-1219, 2014-06-01

Shakashaka is a pencil-and-paper puzzle proposed by Guten and popularized by the Japanese publisher Nikoli (like Sudoku). We determine the computational complexity by proving that Shakashaka is NP-complete, and furthermore that counting the number of solutions is #P-complete. Next we formulate Shakashaka as an integer-programming (IP) problem, and show that an IP solver can solve every instance from Nikoli's website within a second.
著者
多田 昂介 川原 尚人 吉見 真聡 策力木格 吉永 努 Kousuke Tada Naoto Kawahara Masato Yoshimi Celimuge Wu Tsutomu Yoshinaga
出版者
電子情報通信学会
雑誌
信学技報 (ISSN:09135685)
巻号頁・発行日
vol.116, no.416, pp.37-42, 2017-01

本研究報告では,ストリームデータの結合処理を行うHandshake Join のFPGA アクセラレータをマルチノードに拡張する手法を提案し,その性能評価を報告する.マルチノード拡張は,データ通信の2 つの工夫によって実現する.FPGA 上に複数のJoin Core を実装すると共に,FPGA ボード上のDRAM を介してFPGA 間でJoin Coreを接続する仕組みを導入する.また,データ通信と結合演算をオーバラップすることで,通信に要するオーバヘッドを隠蔽する.これらのデータ配布方法の工夫により,単一のFPGA では実装できなかった大きなウインドウサイズの結合演算が可能となる.最大16 ノードでの性能評価の結果,マルチノードに拡張した場合においても,結合演算のスループットが維持されるとともに,並列化効果が得られることが確認された.