各種ソート回路のハードウェア化と ハード/ソフト最適分割化の検討 立命館大学 理工学部　電子情報デザイン学科 高性能計算研究室 Ｂ４　松田　英亮 ２００9/02/27(金) ～で～高性能～が発表します

研究背景 研究目的 ・各種ソートのハード/ソフト最適分割の検討 ・システムLSIの高集積化により、扱うデータ量の増加 ・ハード・ソフトの最適分割の必要性 ・データ量の多い処理の高速化の必要性 研究目的 ・クイックソート回路・バブルソート回路の実現 ・各種ソートのハード/ソフト最適分割の検討 ～背景は～扱う～必要性が増しています～高速化の必要性も求められて～目的～

クイックソートのアルゴリズム ９ ７ ５ ２ １１ １０ ３ １ 7 ２未満を検索 ３未満を検索 ３以上を検索 軸要素(pivot) 交換 ２以上を検索 7 ９以上を検索 ９未満を検索 ５以上を検索 ５未満を検索 １１以上を検索 １１未満を検索

クイックソートのモジュール内でのデータの動き Stack_address 1 3 consent address_right request address_right Memory 9 1 8 6 3 9 1 8 8 3 6 address_left data_left data_pivot address_pivot address_right data_right Read_left Read_pivot Read_right 8 address_left data_pivot data_pivot address_right data_left data_right address_pivot Compare_big Compare_small left_data right_data left_address right_address enable1 enable2 Write_and_Swap pivot_change1 pivot_change2 address_left address_right data_left data_right reflexive address_pivot return

バブルソートのアルゴリズム ３ ９ ７ ０ ５ ２ １１ １０ １ 右端まで繰り返す 最大の値が右端にくる 右端の１つ前まで繰り返す 比較 右端まで繰り返す 最大の値が右端にくる 右端の１つ前まで繰り返す ココまで ・・・ １～３を繰り返す ３ ソート完了

Compare_and_exchange バブルソートのモジュール内でのデータの動き Memory 9 1 A 2 ……………….…… ……………….…… 3D 7 3E 3F 3F 4 data1 address1 data1 address1 data2 address2 data2 address2 Compare_and_exchange

クイックソートの負荷割合と分割パターン 1985 1560[clk] 1439 1971 46 780000[clk] 分類 ハード ソフト 回路規模 クロック数 A Memory, Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address 1985 1560[clk] B Memory Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address 1439 × C Memory, Stack_address, Write_and_swap Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, 1971 D Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap Memory, Stack_address 46 E Memory, Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address 780000[clk]

クイックソートの負荷割合と分割パターン 分類 ハード ソフト 回路規模 クロック数 A Memory, Comapre_and_exchange 968 2070[clk] B Memory Compare_and_exchange 955 × C Memory, Stack_address 13 D Memory, Compare_and_exchange 828000[clk]

まとめ 今後の課題 ・Microblaze上でのハード/ソフト分割パターンの実測値の測定と検証 ・クイックソート回路・バブルソート回路の作成 それぞれソフトウェアの約500倍、400倍の速度向上 ・各種ソートのハード/ソフト最適分割化の検討 回路規模と処理速度のトレードオフを考慮した分割案の提案 今後の課題 ・Microblaze上でのハード/ソフト分割パターンの実測値の測定と検証 ・他のソート回路での実測値の測定と検証