各種ソート回路のハードウェア化と ハード/ソフト最適分割化の検討 立命館大学 理工学部 電子情報デザイン学科 高性能計算研究室 Ｂ４ 松田 英亮 ２００9/02/27(金) 1 研究背景 ・システムLSIの高集積化により、扱うデータ量の増加 ・ハード・ソフトの最適分割の必要性 ・データ量の多い処理の高速化の必要性 研究目的 ・クイックソート回路・バブルソート回路の実現 ・各種ソートのハード/ソフト最適分割の検討 2 クイックソートのアルゴリズム 軸要素(pivot) ３以上を検索 １ ９ ７ ３ ３未満を検索 ５ ２ １１ １０ 交換 ９以上を検索 ２以上を検索 １ ２未満を検索 ３ ２ ５ 7 ５以上を検索 ３以上を検索 １ ９未満を検索 ２ ３未満を検索 ３ １１ ９ 交換 ５ ２ ３ １０ ５未満を検索 １１以上を検索 ５ 7 ９ １１未満を検索 １０ １１ 交換 ７ ９ １１以上を検索 １１未満を検索 １０ １１ １０ １１ クイックソートのモジュール内でのデータの動き 0 1 Stack_address request 0 9 data_left address_left Read_left address_left data_left consent address_right 0 1 3 6 3 1Memory 8 8 data_pivot address_pivot Read_pivot 8 data_pivot Compare_ big left_data left_address address_left data_left reflexive address_right 6 9 data_right address_right Read_right data_pivot address_pivot address_right data_right Compare_ small right_data right_address enable1 pivot_change1 3 enable2 Write_and_Swap pivot_change2 address_right data_right address_pivot return バブルソートのアルゴリズム １ １ ９ ７ ０ ５ ２ １１ １０ 比較 ココまで 右端まで繰り返す ２ １ ７ ０ ５ ２ ９ １０ １１ 最大の値が右端にくる ３ １ ７ ０ ５ ２ ９ １０ １１ 比較 ココまで 右端の１つ前まで繰り返す ・ ・ ・ ０ １ ２ ５ １～３を繰り返す ７ ソート完了 ９ １０ １１ バブルソートのモジュール内でのデータの動き 9 0 0 1 A 2 ……………….…… Memory data1 address1 3D 7 3E3F 4 3F data1 address1 data2 address2 Compare_and_exchange data2 address2 クイックソートの負荷割合と分割パターン メモリー 16% 左入出力 5% スタックメモリー 31% 右入出力 5% ピボット入出力 5% 比較１ 9% スワップ・書き 込み 20% 分類 A ハード Memory, Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address B Memory C Memory, Stack_address, Write_and_swap D Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap E 比較２ 9% ソフト 回路規模 クロック数 1985 1560[clk] 1439 × 1971 × Memory, Stack_address 46 × Memory, Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address 0 780000[clk] Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, Write_and_swap, stack_address Raed_left, Read_right, Read_pivot, Compare_big, Compare_small, 7 クイックソートの負荷割合と分割パターン 分類 ハード A Memory, Comapre_and_exchange B Memory C Compare_and_exchange D ソフト 回路規模 クロック数 968 2070[clk] Compare_and_exchange 955 × Memory, Stack_address 13 × Memory, Compare_and_exchange 0 828000[clk] まとめ ・クイックソート回路・バブルソート回路の作成 それぞれソフトウェアの約500倍、400倍の速度向上 ・各種ソートのハード/ソフト最適分割化の検討 回路規模と処理速度のトレードオフを考慮した分割案の提案 今後の課題 ・Microblaze上でのハード/ソフト分割パターンの実測値の 測定と検証 ・他のソート回路での実測値の測定と検証 9
© Copyright 2024 ExpyDoc
