1辺が1から10までの正方形のレイアウトパズル [Puzzle]
探索プログラムを作るより、手を使って解いた方が速そうだったのでエクセル上で考えてみました。
探索プログラム作るより手で解いた方が速い? https://t.co/q6rmAFQH0H pic.twitter.com/eteVhjrYLr
— skyriver (@wcinp) September 11, 2024
上記のメッセージへのリプライで書いたように面積が 405 の長方形に収めることができます。また、この面積が最小であることを演繹的に証明することもできそうです。
しかし、それ程凝らない作りであれば探索プログラムを作るのも割合簡単なので作ってみました。枝刈りのロジックを殆ど実装していない状態ではありますが、今時のパソコンであれば直ぐに全探索できるだろうという予測に反して意外にも全探索を完了するのに20分弱掛かりました。
★追記 2024/09/14 {
高速化してみました。今、使える実行環境が貧弱なノートPC(Celeron(R) 1.10GHz、RAM 4GB)で変更前のプログラムの実行時間が以前測定した20分弱から35分になったので通常使用しているディスクトップPCより1.8倍遅いと言うことになります。高速化した結果、上記と同様の条件での探索時間は35秒でした。最小面積の解をカウントしない場合(serchでのリカーシブコールの条件式を等号無しの不等式のみにする)の実行時間は11秒程度でした。下記のソースもアップデートしました。
}
★追記 2024/09/16 {
配置可能かのチェックロジックをx/y軸を分離し、y軸の判断処理をx軸ループ外に配置することで高速化しました。
上記と同様のノートPCでの実行時間が15秒になりました(解をカウントせずserchのみの処理であれば7秒)。下記のソースもアップデートしました。
}
探索プログラムを実行時の画面キャプチャを貼っておきます。スクリプトで実行前後に時刻を表示しています。
全探索の結果として10個の正方形が収まる長方形の最小面積は 405 で、この盤面では同じ面積の回答が 1,073,184 通りあることも判りました。
探索プログラムの実行結果 |
|
※変更 2024/09/14 |
プログラムを作ったのでこのパズルの一般的な名称があるのか「PuzzleSquareJP」のサイトで探してみましたが見当たりませんでした(掲載数が膨大にあるので最初の10ページくらいしかチェックしていません^^;)。
ソースも貼っておきます。
正方形配置パズルの探索プログラム(C言語)
|
★変更 Ver0.02 2024/09/14 | |
★追記 2024/09/12
上記の探索では1辺が10の正方形の位置は固定なので10の正方形が中心の位置にあるものしか探索できていません。
試しに10の正方形が左下にある場合を探索してみた結果が下図になります。
10の正方形が左下の場合の探索結果 |
|
★変更 2024/09/13 下記の記述を修正しました
上図の探索は10の正方形を左下に固定した場合であり、10の正方形が下側(縦並び)と左側(横並び)の場合のカウント結果です。10の正方形が上側(縦並び)と右側(横並び)の場合も考慮するとこの探索結果の2倍の解があることになります。
従って10の正方形が中心にある場合と合わせると解の総数は下記の値になります。
4,017,384 ( = 1,472,100 x 2 + 1,073,184 )通り
★追記 2024/09/18
16までの正方形を最小の長方形に配置する探索を単純に行うととてつもなく時間が掛かります。何時間かかけて見つけた解(size:1520 = 40 x 38)が下図です。
16サイズまでの正方形の配置例(最小の長方形ではない) |
|
サイズ15までの最小解を見る(全てをチェックしたわけではないのですが)と最大の正方形は端に配置されているものが含まれることから、格納する長方形の角に最大の正方形を固定して探索することにします(この条件で最小解が得られるという保証はないのですが・・)
それでも探索時間が膨大にかかるので下記の高速化手法を考えました。
- スキャンサイズの最小化
最小四角形へ配置する探索で既知の最小面積は上図の 1520(40x38)のほぼ正方形なので盤面サイズを40x38,41x37~76x20とyをデクリメントしxをその時点での長方形の最小面積をyで割った値にして全探索します。結果的に格納する長方形をほぼ正方形から長~い長方形までを全探索することになります。
- 幅1ギャップでの枝刈り
幅が1のギャップには最後に配置するサイズ1の正方形しか入れることができず殆どがデッドスペースになります。この幅1のギャップの総面積が(スキャン長方形のサイズ - 正方形の面積の総和)を超えた場合はその先の探索を打ち切って枝刈りするようにしました。
上記を実装した探索プログラムを実行した結果が下図になります。図中の x マークは上記の幅1のギャップです。最小面積は 1512(54 x 28)で実行時間は1時間29分でした。
16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.03) |
|
- Ver0.03では未チェックだった正方形の対角線上の幅1ギャップのチェックを追加
- 大きい正方形の配置から配置しているが、次の正方形の探索条件を「配置探索対象正方形のサイズが3以上で幅1ギャップ以外の空きスペースが4個以上またはサイズが2以下」の条件に変更
- 解を発見した場合、同じサイズの長方形の探索を中断
得られた最小解は今までと同様に size = 1512, ( 54 x 28 ) です。記念として探索結果を貼っておきます(クリックすると実行開始から終了までの画面表示が見えます)。
16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.04) |
|
今回の最適化と実行環境をノートPCからディスクトップ(Win11要求仕様未達の古いPC)に変更したことで探索時間は 59分17秒 となり、下記の目標を達成できました。^^
上記で次の探索へ進む条件での「空きスペースが4個以上」の部分が、サイズ3の正方形の探索(次の探索のサイズ2の正方形の面積が4なので))のみを考慮しているようでしっくりきませんでした。もっと汎用的に考えれば、幅1のギャップは最後に配置するサイズ1の正方形のみが使用可能なので全てのサイズの正方形の配置探索に適応できるように次探索へ進む条件を「幅1のギャップの総面積が(スキャン中の長方形の面積 - 全正方形の面積の総和 + 1)以下」に変更しました。
その結果、下図(クリックで表示範囲拡大)に示すように探索時間は 45分51秒 になりました。
16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.04改) |
|
}
16までの正方形の最小四角形配置の探索は時間が掛かるので途中で中断しましたが1時間程度で全探索できるものが作れればすごいかも https://t.co/knawODhgx9 pic.twitter.com/IAbX5peZIl
— skyriver (@wcinp) September 16, 2024
★追記 2024/09/21
1辺が1~13の13個の正方形を最小面積の長方形へ配置する方法を探索してみました。プログラム作成当初は結果がでるまでかなり時間が掛かっていましたが、今では4秒程度で最小面積=836(38 x 22)の解が得られます。
1辺の長さが1~NのN個の正方形を最小面積の長方形内への配置方法を探索するある程度高速なプログラムができたのでN=13の場合を探索してみた
— skyriver (@wcinp) September 21, 2024
当初は結果が出るまでにかなり時間が掛かっていたけれど今では4秒程度で最小面積=836(38 x 22)の解が得られる pic.twitter.com/6VrBvTjDh7
★追記 2024/09/24
旧Twiiterのタイムラインで情報提供頂き、Wolfram Demonstrations Project の「Tightly Packed Squares」のページで本パズルで1辺が3~32までの探索結果を表示するデモが見れます(ソースも開示されている模様)。1辺が33以上は未だに未解決のようなので興味のある人は挑戦してみては如何でしょうか?
CH32V203で遊ぶ(その6)クロックアップ [CH32V]
今回はレジスタ直書込みによる高速化と CH32V203 のクロックアップによる変貌ぶりについて記録して置きたいと思います。
1.はじめに
以前から認識はしていたのですが、CH32V203 は今回使用している開発環境(MounRiver Studio)のディフォルト設定では外部クロックを使用する設定になっていて、今回のように外部クロックを接続していない状態では内部クロックを使って 8MHz で動作します。
言わばこの大リングボール養成ギブスを付けた状態で今までグラフィック描画の高速化を試みてきました。今回はレジスタの直たたきによる高速化を行った後に、クロックアップにより羊の皮を脱ぎ捨てた CH32C203 の真の実力について記載します。
2.レジスタ直接制御による高速化
サンプルプログラムの記述に従ってC言語で開発するとペリフェラルのステータス確認の度にサブルーチンコールし、サブルーチンの中では対応ビットをANDチェック後の状態(ゼロか否か)により、リターン値を設定するようなまどろっこしい処理になってしまいます。特にライン描画のような繰り返し回数が多い処理ではなるべくステップ数の少ない実装にしたいものです。
そこでステータスの確認とデータの書き込みをレジスタ直アクセスにしてみました。レジスタのアドレスやステータスのビットの定義についてはディバッガでトレースすれば容易に確認でき、これらは ch32v20x.h や ch32v20x_spi.h のファイル内で定義されています。
参考として SPI1 関連のレジスタとステータスレジスタのビット構成を下表に示します。
SPI1 関連レジスタ |
|
SPI1 ステータス |
|
下図がレジスタ直制御対応前と対応後のロジアナ波形です。SPI のデータ出力の間隔が短くなり、高速化できていることが判ります。末尾の「4.まとめ」に記載しているようにレジスタを直接制御することで前回の記事に掲載した 512 個の線分を描画するテストプログラムの実行時間は従来の処理から 16% 程速くなりました。
レジスタ直制御対応前のSPI波形 |
|
レジスタ直制御対応後のSPI波形 |
|
3.クロックアップ
下図は CH32V203 のクロック系の構成図で、これを見ると HSI(内部クロック)の 8MHz を PLL で18倍まで逓倍したものを SYSCLK にすることができます。
CH32V203 のクロック構成 |
|
今まではディフォルト設定で SYSCLK は 8MHz で、言わばこの大リーグボール養成ギブスを付けた状態で色々高速化を試みてきました。高速化の対処も一通りやった感があるので、この辺で CH32V203 の羊の皮を取り去り本来の実力を見てみたいと思います。
クロックの設定は system_ch32v20x.c の下記の部分の define 設定を変更することで簡単にできました。
system_ch32v20x.c |
---|
/* * Uncomment the line corresponding to the desired System clock (SYSCLK) frequency (after * reset the HSI is used as SYSCLK source). * If none of the define below is enabled, the HSI is used as System clock source. */ //#define SYSCLK_FREQ_HSE HSE_VALUE //#define SYSCLK_FREQ_48MHz_HSE 48000000 //#define SYSCLK_FREQ_56MHz_HSE 56000000 //#define SYSCLK_FREQ_72MHz_HSE 72000000 /////#define SYSCLK_FREQ_96MHz_HSE 96000000 //#define SYSCLK_FREQ_120MHz_HSE 120000000 //#define SYSCLK_FREQ_144MHz_HSE 144000000 //#define SYSCLK_FREQ_HSI HSI_VALUE //#define SYSCLK_FREQ_48MHz_HSI 48000000 //#define SYSCLK_FREQ_56MHz_HSI 56000000 //#define SYSCLK_FREQ_72MHz_HSI 72000000 //#define SYSCLK_FREQ_96MHz_HSI 96000000 //#define SYSCLK_FREQ_120MHz_HSI 120000000 #define SYSCLK_FREQ_144MHz_HSI 144000000 |
sysclk が従来の 8MHz から一挙に 144MHz にアップし、SPI のプリスケーラーは2に設定しているので SPI のクロックも 4MHz から 72MHz に変わることになります。流石に SPI のプリスケーラーの設定は変更が必要と思っていましたが、なんとそのままで動作しました。
こうなると私の安いロジアナ(サンプリングの上限が100MSa/s)では波形を確認できません。最高サンプリング 1GSa/s のオシロで観測した SPI の CLK(水色)とデータ(黄色)が下図です。プローブが安物のせいか波形が綺麗には見えませんが、カーソルで示しているように確かに 72MHz 程度のクロックが出ているようです。ブレッドボード環境でこの周波数で動作していることもすごいですね。
SPI CLK(水色) と MOSI(黄色) |
|
4.まとめ
数回に渡り、高速化検討をしてきましたが、高速化を一通りやった感があるので今回はクロックを 8MHZ から一挙に上限の 144MHz にアップし、CH32V203 の羊の皮を脱がせて真の実力を見てみたところグラフィック描画はとんでもない速さになりました^^
120円の CPU でこの速さはとてつもないと思います。接続した TFT 液晶 MSP2807 もすごいですね。
最後に今回の高速化対応での線分描画時間の測定結果を下表に示します。
No | method | time[s] | speed ratio |
---|---|---|---|
1 | Before | 13.109 | 1.00 |
2 | Register direct | 11.304 | 1.16 |
3 | Clockup(144MHz) | 0.626 | 20.94 |
X(旧Twitter)に投稿したメッセージに添付した動画を貼っておきます。
MounRiverを使ってCH32V203のソフトを作って遊び中
— skyriver (@wcinp) August 4, 2024
TFT液晶MSP2807(320 x 240 dot)での描画の高速化を行ってきましたが最後にCH32Vのクロックアップを行い羊の皮を剥がしてみました
真の姿はとんでもないです^^
これで120円とは驚きですねhttps://t.co/FF7nfdSYCU#CH32V203 #MounRiver #MSP2807 pic.twitter.com/TUWMRXexxq
[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
CH32V203で遊ぶ(その5)高速なライン描画法 [CH32V]
ディバッガで追ってみると速度のネックはライン描画アルゴリズムよりもドット描画自体にあり、SPI や PIO での I/O 制御部がC言語での標準な制御方法ではまどろっこしい程の処理なのでレジスタ直書きやアセンブラ化すればかなり速くなりそうです。
今回はライン描画処理の高速化を検討する中で、上記のような I/O 制御自体の高速化では無く、ライン描画アルゴリズム自体の高速化を思い付いた(以降、傾き予測法(Slope prediction method)と記す)ので記録しておきたいと思います。
尚、後で気が付きましたが「ポケコン(G850)高速ライン描画」の記事でも引用していた「ラインルーチンの高速化の手法」のページにライン描画の高速化について判り易くまとめられていて、ここにダブルステップの手法が書かれていますが評価結果として高速化はできなかったとの結論でした。今回提案する傾き予測法は本ページの末尾にまとめたように実際に高速化への効果が確かめられた描画法です。
1.今回のお品書き
ライン描画手法について下記の内容を記載します。
- 標準的なライン描画処理
- 両端からの同時描画
- 今回提案の傾き予測法
2.高速ライン描画手法
以降にライン描画の各手法について記載します。
2-1.標準的なライン描画処理
高速化のために整数だけの処理でラインを描画する手法でブレゼンハムのアルゴリズムとして広く知られています。
下記のソースはネット上のソースを参照せずに独自に起こしたものですが、ブレゼンハムのアルゴリズムと同等の処理になっています。
高速化の観点からループ内での条件分岐を最小限にするために傾きの大きさにより場合分けし、二つのループ処理に分割しています。PSET は1ピクセルを描画する外部処理です。
標準的なライン描画処理(C言語)
|
・2024/08/16 中心部のポイントが乱れる場合がある問題に対処 | |
2-2.両端からの同時描画
上記の改良版でラインが中心点から見て点対称なので始点側と同時に終点側も描画することでループ回数を1/2にして高速化しています。ループ終了後の PSET は始点~終点間の距離が偶数の場合、中心のポイントの描画が欠落してしまうことに対する対処です。
両端からの同時描画(C言語)
|
・2024/08/16 中心部のポイントが乱れる場合がある問題に対処 | |
2-3.今回提案の傾き予測法
上記の描画では傾きが1(45°)以下の場合と1より大きい場合の二通りに場合分けして処理しましたが、傾き予測法では傾きの大きさによりループ処理を更に2分割します。
下図に示すように傾きの大きさと移動方向の条件により、次の移動方向を決定できるケースがあり、これを利用して高速化しています。前述の両端からの描画手法も併用します。
- 傾きが 0 ~ 0.5 の場合
縦移動/横移動 は1/2以下なので下図の上側の緑色の■のように縦移動直後は必ず横移動になります。
- 傾きが 0.5 ~ 1.0 の場合
縦移動/横移動 は1/2以上なので下図の下側の緑色の■のように横移動直後は必ず縦移動になります。
傾き予測法での予測方法 |
|
例えば、上記の「標準的なライン描画処理」において単純にループ内で2ドット分の進みを処理すれば、ループ回数が 1/2 になるので for ループのための条件ジャンプの比率が1/2になり効果は少ないですが若干高速化します(ループ処理の展開による高速化)。逆に言うと1回のループ処理で多くのドットを処理してもそれに比例して条件分岐が増えれば高速化できません(当然処理量が比例して多くなっても高速化できません)。従って高速化するためには上図のようにループ内の条件ジャンプの増加を抑えつつ、より多くのドットを処理するようにする必要があります。
傾き予測法によるライン描画処理(C言語)
|
・Ver 0.02 2024/08/03 中心部のポイントが描画されない場合がある問題に対処し、下記の実行時間も再測定 | ・Ver 0.02a 2024/08/16 中心部のポイントが乱れる場合がある問題に対処 ・Ver 0.02b 2024/09/04 傾きが0.5以上で線が太くなる問題に対処 |
★追記 2024/08/06 {
上記は速度優先で同様な処理が2カ所にありましたが、速度低下を最小限にしてコードを短くしたバージョンを追記します。
傾き予測法によるライン描画処理[shorter code ver](C言語)
|
・Ver 0.03a 2024/08/16 中心部のポイントが乱れる場合がある問題に対処 | ・Ver 0.03b 2024/09/04 傾きが0.5以上で線が太くなる問題に対処 |
3.各ライン描画法の評価
上述のライン描画法の評価環境として、前回の記事でも使用した CH32V203(8MHz動作)に TFT液晶 MSP2807(320 x 240 dot)を接続した環境を使いました。評価方法としては事前に乱数で生成した 512 本のラインデータに従ってライン描画処理を実行した際の時間を計測しました。時間計測は systick タイマの内部カウンタだけでも計測できそうでしたが、今回は systick を使った 1ms 毎の割込み処理でインクリメントするカウンタ値で時間を計測しています。コンパイル時のオプティマイズはディフォルトのままの -Os(サイズ優先)です。
下図は評価時の LCD 表示です。
ライン描画法評価時の LCD 画面 |
|
計測結果を下表に示します。
No. | method | time[s] |
---|---|---|
1 | 標準的なライン描画 | 13.185 |
2 | 両端からの同時描画 | 13.121 |
3 | 今回提案の傾き予測法 | 13.109 |
上記の表では殆ど時間差が無いように見えますが、冒頭で書いたようにドット描画処理(PSET)が重いので PSET を何もしないダミー関数にし、ライン描画アルゴリズムの処理自体の時間を計測し直した結果が下表です。
No. | method | time[s] | speed ratio |
---|---|---|---|
1 | 標準的なライン描画 | 0.200 | 1.00 |
2 | 両端からの同時描画 | 0.124 | 1.61 |
3 | 今回提案の傾き予測法 | 0.112 | 1.79 |
期待通り、今回提案の傾き予測法は標準的なライン描画より約 1.8 倍速いという結果になりました。
[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
CH32V203で遊ぶ(その4)DMAで高速描画 [CH32V]
1.今回の目標
2.8インチTFT液晶 MSP2807(320 x 240 dot)への連続したデータ書き込み処理部分を DMA 機能を使って高速化します。
2.方針
下記の変更/追加を行います。
- SPI のクロックアップ
SPI のクロックは従来 2MHz でしたが上限の 4MHz にアップします
- 連続データ書き込み処理の DMA 化
LCD への連続したデータ書き込みが発生する塗りつぶし処理(画面クリア含む)を DMA 機能で実現します
- 塗りつぶし機能追加
円と四角形の塗りつぶし機能を実装します
3.対処内容
以下に対処した内容について記載します。DMA を利用すると言っても DMA の設定の追加と LCD へのデータ書き込み部分のコードを若干変更するだけなので本記事の内容がスカスカになってしまうのを防ぐためにデータシートからの引用等を含め、CH32V203 の DMA 機能自体の説明もある程度記載します。
3-1.SPI のクロックアップ
SPI の初期化の時のプリスケーラの設定を変更するだけです。簡単ですね。
SPI_InitStructure.SPI_BaudRatePrescaler = SPI_BaudRatePrescaler_2; // 16:500kHz |
3-2.連続データ書き込み処理の DMA 化
今回使用している CPU(CH32V203)のブロック図を下図に示します。DMA 機能は左上の部分にあり、8チャンネル構成で FLASH, SRAM 及びペリフェラルのバスに接続されています。機能としてはメモリ to メモリ、メモリ to ペリフェラル及び ペリフェラル to メモリの高速なデータ転送を実現します。
CPU(CH32V203)のブロック図 |
|
ペリフェラルと言ってもそれを制御するペリフェラル用のレジスタは下図のようにメモリにマッピングされています。
CPU(CH32V203)のメモリマップ |
|
周辺機器とのインターフェースにはそれぞれ固有の機能があるので DMA 側も各機能に合わせてカスタマイズされている関係上、DMA のチャンネルとペリフェラルは下図のように対応付けされています。
DMA リクエストマッピング |
|
この対応付けを表にしたものが下表になります。今回は LCD 通信の送信(SPI1_TX)を DMA 化するので DMA の チェンネル3を使用することになります。
DMA チャンネル vs ペリフェラル対応表 |
|
一つの DMA チャンネルで複数のリクエストに対応している関係上、下記の様にリクエスト要求側でリクエストを有効にする設定が必要になります。
SPI_I2S_DMACmd(SPI1, SPI_I2S_DMAReq_Tx, ENABLE); |
DMA の制御レジスタのビット構成を下図に示します。あとはサンプルソースを参照して設定することで容易に動作しました。
DMA 制御レジスタ |
|
唯一悩ましかったのが次の点でした。
今回は LCD の画面消去等の塗りつぶし(2バイトデータの連続書込み)が DMA 対象であり、この場合のペリフェラルサイズ(PSIZE)とメモリサイズ(MSIZE)の設定で悩みました。SPI 側のデータサイズはバイトに設定していて、書き込みデータはメモリ上に2バイトデータで存在するので
- PSIZE : DMA_PeripheralDataSize_Byte
- MSIZE : DMA_MemoryDataSize_HalfWord
参考として DMA 設定部分のソースを以下に貼っておきます。ppadr と memadr の型が uint32_t になっていて、これは void * の方が妥当だと思いますがサンプルのままで弄っていません。
DMA 初期化部分のソース |
|
連続書込み部分のソースは下記になります。DMA での1回の転送データ数は 0xffff 個が上限(0x0000 設定時は転送しない)なので転送数が 0xffff より大きい場合は分割して転送するようにしています。ループ内に if 文を入れれば一つのループにできますが速度優先で二つのループにしています(実質的な速度は殆ど変わらないとは思いますが)。
DMA での連続書込み部分のソース |
|
下図は DMA 化前の画面クリア時(0x0000の連続書込み)のロジアナ波形です。SPI 出力間に隙間時間がかなりあります。
DMA 対応前の画面クリア時のロジアナ波形 |
|
下図は DMA 化後のロジアナ波形です。隙間なく SPI 出力されています。
DMA 対応後の画面クリア時のロジアナ波形 |
|
3-3.塗りつぶし機能追加
上記の DMA 化した連続書込み処理を利用して、円と四角形の塗りつぶし描画処理を追加しました。
4.まとめ
SPI のクロックが MHz レベルになるとマイコンのソフト処理では流石に転送と転送の間に隙間時間が発生してしまいます。このため多くのマイコンが DMA 機能を有しており、効率よくテータ転送ができるようになっています。
今回の LCD 表示での塗りつぶし処理も DMA 機能を使用することで隙間時間なく転送できるようになり、処理時間を短縮出来ました。
更に LCD コントローラの書き込み対象の四角形範囲を指定できる機能により、四角形の塗りつぶしはかなり高速化しました。
また、今回は使用していませんが、DMA の転送中間時点と転送終了時点で割込みを発生できるので、LCD 書込みと並行して別の処理をすることもソフトウェア次第で可能になります。
最後に DMA 化後のデモ画面を貼っておきます。
DMA 描画デモ画面例 |
|
X(旧Twitter)のメッセージに添付した動画も貼っておきます。
MounRiverを使って秋月さんで安価に購入できるCH32V203のソフトを作って遊び中
— skyriver (@wcinp) July 26, 2024
SPI接続の2.8インチTFT液晶 MSP2807(320 x 240 dot)で画面消去に時間が掛かっていたのでDMA化してみた
DMAを利用した円と四角形の塗りつぶしもそれなりの速度になりましたhttps://t.co/LDWbbwEtS3#CH32V203 #MounRiver pic.twitter.com/gWsia4OSkM
[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
CH32V203で遊ぶ(その3)USART割込みでLiDAR接続(その2)高速化 [CH32V]
しかし、秋月電子通商さんで¥120で購入できる CH32C203(clockは144MHz)で処理していて LiDAR からの最大8個の測位データが含まれる通信データの塊(package)を5個中1個の割合でした処理できていませんでした。今回はこの処理を高速化してもっと多くの package を処理できるようにしたいと思います。下の写真は開発環境で CH32V203 を取り付けたブレッドボードにLCD(MSP2807、320 x 240 dot)と LiDAR を接続しています。
開発環境 |
|
1.今回の目標
C言語レベルでの最適化を行い LiDAR から送信されてくる package をなるべく多く処理できるようにします。
2.高速化項目
具体的な高速化ポイントは下記のとおりです。
- 三角関数をテーブルにして、整数演算処理化する
- RISC-V は LiDAR からのデータと同様、リトルエンディアンなので LiDAR からの受信データからデータ抽出をせず直接使用する
- LiDAR からの package 受信バッファをダブルバッファ化して高速化する
2-1.三角関数のテーブル化と整数演算処理化
三角関数テーブルとしてが sin の値を0~90度の区間分持つことにしました。この sin テーブルのデータ形式は LiDAR からのデータ形式及び受信データ表示用のLCDの解像度(320 x 240)を考慮し、下記のようにしました。
- 角度分解能
LiDAR からの角度データは dgree の64倍で送られてきます。sin テーブルの角度に関しては dgree の4倍とし、LiDAR のデータ内の角度からの変換はシフト処理のみでできるようにしました。テーブル要素数は 90 x 4 で 360 要素の配列を持つことになります。
- テーブル要素の値
メモリを節約し配列要素は1バイトとし、値がゼロの場合は 0x0100 とみなすようにします。配列上は角度0の場合もゼロの値になりますが、角度0の場合は配列を参照せずに結果はゼロと判断するようにしました。
配列用データの生成は下記の BASIC プロフラムで行いました。
1' create sin table Ver 0.01 2024/07/10 by skyriver 100 DELTA=90*4 110 PRINT "const uint8_t SinTable[] = {"; 120 FOR I=0 to DELTA - 1 130 IF (I MOD 8)=0 THEN PRINT:PRINT CHR$(9); 140 PRINT "0x";RIGHT$( "00" + HEX$(INT(SIN(I/DELTA*3.14159/2)*256+0.5)), 2);","; 150 NEXT 160 PRINT:PRINT "};" |
作成した sin テーブルのソースは下記になります。
sin テーブルのソース |
|
上記の sin テーブルを持つことで LiDAR からのデータ処理を浮動小数点を使わず、全て整数処理で行うことができるようになり、かなり高速化できました。
下図は従来からの浮動小数点演算処理時のロジアナ波形の再掲ですが、5個の package 中、1個だけ処理ができています。マーカー0がデータ抽出+1ポイント描画の時間でマーカー1が1ポイントの時間なのでデータ抽出には 1ms 程の時間が掛かっていることになります。この package では8個のポイントを描画しています。
浮動小数点演算での処理(従来方式) |
|
下図は整数演算処理化した改善版のロジアナ波形です。3 package 中1個の package が処理できるようになったので処理率は従来の20%から33%に改善されました。SpiClk が発生している部分がLCD描画している箇所ですが、従来は8回の描画に隙間が見えましたが、高速化したことにより、隙間が見えなくなっています(マーカー1の部分)。マーカー0の部分は LiDAR のデータから必要なデータを抜き取っている部分ですが、800us 程の時間が掛かっていることが判ります。
整数演算で高速化した処理(改善版) |
|
2-2.データ抽出処理の高速化
今回使用している CH32V203 は 32 ビット RISC-V をベースに設計されていて、LiDAR からのデータと同様にリトルエンディアンです。従来の処理では LiDAR からのデータの受信バッファからバイト単位でデータを抜き取り、シフト処理でワードデータ等を抽出していました。高速化のために受信バッファ内のポインタをキャストすることでデータ抽出を行わず直接参照するようにしました。
高速化後のロジアナ波形が下図になります。マーカー0がデータ抽出処理ですが、前述のロジアナ波形では 800us 程度かかっていたデータ抽出処理が 71us 程度に高速化できました。尚、ロジアナ波形の最後に追加した"receiving"はLiDARからのデータを割込み処理で受信中であることを示すディバッグのための信号です。受信データ処理中は LiDAR からのデータを受信できていないことが判ります。
データ抽出部改善後 |
|
2-3.ダブルバッファ化
LiDAR からのデータを受信するための受信バッファをダブルバッファー化し、処理中でも LiDAR から出力されるデータを受信できるようにすることで受信待ち時間を最小にして高速化しました。
下図がダブルバッファー化後のロジアナ波形です。処理が追い付かず稀に未処理の package が発生していますが、package の処理率はほぼ100%に改善できました。
ダブルバッファー化後 |
|
3.まとめ
最近弄りだした120円の32ビットマイコンの CH32V203 に4年前に購入し、お蔵入りしていた格安の LiDAR を繋いでデータ抽出し、LCD上にリアルタイムで表示できるようになりました。
CPUパフォーマンスの関係で初めは LiDAR からのデータの20%程度しか表示処理できませんでしたが、今回高速化の改善を行った結果、LiDAR からのデータのほぼ100%を処理し表示できるようになりました。
ネット上で見かける LiDAR データの表示は M5Stack(32bit 240MHz デュアルコア)等の例が多く、数百円レベルのマイコンでの例は見かけません。
今回は秋月電子通商さんで120円で購入できるCH32V203(32bit 144MHz)を使って下の写真のように LiDAR からのデータをLCDに表示できるようになりました。
「非力なマイコンで工夫をしてパフォーマンスを引き出す」というのはマイコン弄りの醍醐味の一つではないでしょうか?
LiDAR データのLCD表示例 |
|
★追記 2024/07/21
X(旧Twitter)に投稿したメッセージに添付した動画を貼っておきます。
LiDARからのデータを120円のCPU(CH32V203)で処理することに挑戦しました
— skyriver (@wcinp) July 21, 2024
処理を最適化した結果LiDARからのデータのほぼ100%を処理しLCD表示できるようになりました
非力な CPU で工夫をしてパフォーマンスを引き出すのはCPU弄りの醍醐味ですね^^https://t.co/mc6IKRRJT9#CH32V203 #MounRiver #LiDAR pic.twitter.com/2Tw9gIEt0N
X(旧Twitter)で最近話題になっている安価な小型の LiDAR が着荷したので試してみました。「UnknownLiDARMini_M5StackCore2」を参考にさせて頂き、従来のソフトウェアを若干変更することで120円マイコン(CH32V203)で LCD にデータをリアルタイムで表示できました。
新 LiDAR(表面) |
|
新 LiDAR(裏面) |
|
新 LiDAR の試験環境 |
|
[TOP] [ 前へ ] 連載記事一覧[ 次へ ]