SSブログ
English Version
前の5件 | -

１辺が1から10までの正方形のレイアウトパズル　[Puzzle]

　旧Twitterのタイムラインで1辺が１から１０までの１０個の正方形を傾けずにできるだけ面積の小さい長方形内に並べるというパズルを見かけました。

　探索プログラムを作るより、手を使って解いた方が速そうだったのでエクセル上で考えてみました。



　上記のメッセージへのリプライで書いたように面積が 405 の長方形に収めることができます。また、この面積が最小であることを演繹的に証明することもできそうです。

　しかし、それ程凝らない作りであれば探索プログラムを作るのも割合簡単なので作ってみました。枝刈りのロジックを殆ど実装していない状態ではありますが、今時のパソコンであれば直ぐに全探索できるだろうという予測に反して意外にも全探索を完了するのに２０分弱掛かりました。

★追記　2024/09/14　{
　高速化してみました。今、使える実行環境が貧弱なノートＰＣ（Celeron(R) 1.10GHz、RAM 4GB）で変更前のプログラムの実行時間が以前測定した20分弱から35分になったので通常使用しているディスクトップＰＣより１．８倍遅いと言うことになります。高速化した結果、上記と同様の条件での探索時間は３５秒でした。最小面積の解をカウントしない場合（serchでのリカーシブコールの条件式を等号無しの不等式のみにする）の実行時間は１１秒程度でした。下記のソースもアップデートしました。
}
★追記　2024/09/16　{
　配置可能かのチェックロジックをｘ／ｙ軸を分離し、ｙ軸の判断処理をｘ軸ループ外に配置することで高速化しました。
　上記と同様のノートＰＣでの実行時間が１５秒になりました（解をカウントせずserchのみの処理であれば７秒）。下記のソースもアップデートしました。
｝
　探索プログラムを実行時の画面キャプチャを貼っておきます。スクリプトで実行前後に時刻を表示しています。
　全探索の結果として１０個の正方形が収まる長方形の最小面積は 405 で、この盤面では同じ面積の回答が 1,073,184 通りあることも判りました。

探索プログラムの実行結果
※変更　2024/09/14

　プログラムを作ったのでこのパズルの一般的な名称があるのか「PuzzleSquareJP」のサイトで探してみましたが見当たりませんでした（掲載数が膨大にあるので最初の１０ページくらいしかチェックしていません^^;）。

　ソースも貼っておきます。

正方形配置パズルの探索プログラム（C言語） 
/***********************************************
  square layout puzzle solver
   1..10 square are layouted minimun Rectangle
  Ver 0.01 2024/09/12 by skyriver
  Ver 0.02 2024/09/14 08:50 faster
  Ver 0.03 2024/09/15 21:00 faster
 ***********************************************/

#include <stdio.h>

#define MAXSQUARE   10
#define SUMAREA     (MAXSQUARE*(MAXSQUARE+1)*(MAXSQUARE*2+1)/6)
#define SOLCOUNT    1  // 0:not count solusions


#define MAXBOARDX    (MAXSQUARE * 4)
#define MAXBOARDY    (MAXSQUARE * 4)

    #if 01
#define FIRST_XPOS   (MAXBOARDX / 3 + 2)
#define FIRST_YPOS   (MAXBOARDY / 3 + 2)
    #else
#define FIRST_XPOS  ( MAXSQUARE - 3)
#define FIRST_YPOS  (MAXBOARDY - MAXSQUARE - 6)
    #endif


typedef struct {
    int x;
    int y;
} Point_t;

typedef struct {
    Point_t min;
    Point_t max;
} Reqt_t;

Reqt_t  Square[ MAXSQUARE + 1 ];
char    Board[ MAXBOARDY ][ MAXBOARDX ];

//int MinSize = 406;    // answer area size
int MinSize = (int)(SUMAREA*1.08);  // answer area size
int Size;           // work
int SolCnt;         // answer counter


void DelSquare( int size, int xpos, int ypos )
{
    for( int y = ypos; y < ypos + size; y++ ) {
        for( int x = xpos; x < xpos + size; x++ ) {
            Board[ y ][ x ] = 0;
        }
    }
}


void FillSquare( int size, int xpos, int ypos )
{
    for( int y = ypos; y < ypos + size; y++ ) {
        for( int x = xpos; x < xpos + size; x++ ) {
            Board[ y ][ x ] = size;
        }
    }
}


void disp( Reqt_t req )
{
    Reqt_t *spnt;
    printf(
        "\n\narea size = %3d, ( %2d x %2d ) "
        ,MinSize
        ,req.max.x - req.min.x + 1
        ,req.max.y - req.min.y + 1
    );
    spnt = &Square[ 0 ];
    for( int ssize = 1; ssize < MAXSQUARE; ssize++ ) {
        spnt++;
        FillSquare( ssize, spnt->min.x, spnt->min.y );
    }
    for( int y = 0; y < MAXBOARDY; y++ ) {
        printf( "\n%2d : ", y );
        for( int x = 0; x < MAXBOARDX; x++ ) {
            int c;
            c = Board[y][x];
            if( c == 0 ) {
                c = '.';
            }
            else if( c > 9 ) {
                c += 'A' - 10;
            } else {
                c += '0';
            }
            putchar( c );
        }
    }
    spnt = &Square[ 0 ];
    for( int ssize = 1; ssize < MAXSQUARE; ssize++ ) {
        spnt++;
        DelSquare( ssize, spnt->min.x, spnt->min.y );
    }
}


// size <- size of square
// area <- area value of rectangle
// req <- min & max point of rectangle
void search( int sqsize, Reqt_t req )
{
    int *ckpnt;
    Reqt_t nreq;
    int chky[ MAXSQUARE ];  // outside flag for y

    for( int y = 0; y < MAXBOARDY - sqsize; y++ ) {
        int yen = y + sqsize - 1;
        Reqt_t *spnt = &Square[ MAXSQUARE ];
        ckpnt = &chky[ 0 ];
        for( int sq = MAXSQUARE - sqsize; sq; sq--, spnt--, ckpnt++ ) {
            *ckpnt = ( y <= spnt->max.y && y + sqsize > spnt->min.y ) ? 0 : 1;
        }
        Square[ sqsize ].min.y = y;
        Square[ sqsize ].max.y = yen;
        nreq.min.y = y < req.min.y ? y : req.min.y;
        nreq.max.y = yen > req.max.y ? yen : req.max.y;
        for( int x = 0; x < MAXBOARDX - sqsize; x++ ) {
            int checkx = 1;
            spnt = &Square[ MAXSQUARE ];
            ckpnt = &chky[ 0 ];
            for( int sq = MAXSQUARE - sqsize; sq; sq--, spnt--, ckpnt++ ) {
                if( *ckpnt == 0 && x <= spnt->max.x && x + sqsize > spnt->min.x ) {
                    checkx = 0;
                    break;
                }
            }
            if( checkx != 0 ) {
                int xen = x + sqsize - 1;
                Square[ sqsize ].min.x = x;
                Square[ sqsize ].max.x = xen;
                nreq.min.x = x < req.min.x ? x : req.min.x;
                nreq.max.x = xen > req.max.x ? xen : req.max.x;
                Size = (nreq.max.x - nreq.min.x + 1) * (nreq.max.y - nreq.min.y + 1);
#if SOLCOUNT
                if( Size <= MinSize ) {
                    if( sqsize != 1 ) {
                        search( sqsize - 1, nreq );
                    } else {
                        if( Size == MinSize ) {
                            SolCnt++;
                        } else {
                            MinSize = Size;
                            SolCnt = 1;
                            disp( nreq );
                        }
                    }
                }
#else
                if( Size < MinSize ) {
                    if( sqsize != 1 ) {
                        search( sqsize - 1, nreq );
                    } else {
                        MinSize = Size;
                        disp( nreq );
                    }
                }
#endif
            }
        }
    }
}


int main( int argc, char *argv[] )
{
    Reqt_t req;
    printf( "\nSquare layout puzzle solver Ver 0.03\n size:%d\n", MAXSQUARE );
    req.min.x = FIRST_XPOS;
    req.min.y = FIRST_YPOS;
    req.max.x = FIRST_XPOS + MAXSQUARE - 1;
    req.max.y = FIRST_YPOS + MAXSQUARE - 1;
    Square[ MAXSQUARE ] = req;
    FillSquare( MAXSQUARE, FIRST_XPOS, FIRST_YPOS );
    search( MAXSQUARE - 1, req );
    printf( "\ncomplete searching.\nsame area size answer are %d.\n", SolCnt );
    return( 0 );
}
★変更　Ver0.02　2024/09/14



★追記　2024/09/12
　上記の探索では１辺が１０の正方形の位置は固定なので１０の正方形が中心の位置にあるものしか探索できていません。
　試しに１０の正方形が左下にある場合を探索してみた結果が下図になります。

１０の正方形が左下の場合の探索結果

★変更　2024/09/13　下記の記述を修正しました

　上図の探索は１０の正方形を左下に固定した場合であり、１０の正方形が下側（縦並び）と左側（横並び）の場合のカウント結果です。１０の正方形が上側（縦並び）と右側（横並び）の場合も考慮するとこの探索結果の２倍の解があることになります。

　従って１０の正方形が中心にある場合と合わせると解の総数は下記の値になります。

　　 4,017,384 ( = 1,472,100 x 2 + 1,073,184 )通り


★追記　2024/09/18
　16までの正方形を最小の長方形に配置する探索を単純に行うととてつもなく時間が掛かります。何時間かかけて見つけた解（size:1520 = 40 x 38）が下図です。

16サイズまでの正方形の配置例（最小の長方形ではない）


　サイズ15までの最小解を見る（全てをチェックしたわけではないのですが）と最大の正方形は端に配置されているものが含まれることから、格納する長方形の角に最大の正方形を固定して探索することにします（この条件で最小解が得られるという保証はないのですが・・）

　それでも探索時間が膨大にかかるので下記の高速化手法を考えました。
  1. スキャンサイズの最小化
    　最小四角形へ配置する探索で既知の最小面積は上図の 1520(40x38)のほぼ正方形なので盤面サイズを40x38,41x37～76x20とｙをデクリメントしｘをその時点での長方形の最小面積をｙで割った値にして全探索します。結果的に格納する長方形をほぼ正方形から長～い長方形までを全探索することになります。

  2. 幅１ギャップでの枝刈り
    　幅が１のギャップには最後に配置するサイズ１の正方形しか入れることができず殆どがデッドスペースになります。この幅１のギャップの総面積が（スキャン長方形のサイズ　－　正方形の面積の総和）を超えた場合はその先の探索を打ち切って枝刈りするようにしました。

　上記を実装した探索プログラムを実行した結果が下図になります。図中の x マークは上記の幅１のギャップです。最小面積は 1512（54 x 28）で実行時間は1時間29分でした。

16サイズまでの正方形の配置の探索プログラム実行画面(Ver0.03)



★追記　2024/09/20　探索状態を観察し、次の高速化を行いました。

  • Ver0.03では未チェックだった正方形の対角線上の幅１ギャップのチェックを追加
  • 大きい正方形の配置から配置しているが、次の正方形の探索条件を「配置探索対象正方形のサイズが3以上で幅１ギャップ以外の空きスペースが4個以上またはサイズが２以下」の条件に変更
  • 解を発見した場合、同じサイズの長方形の探索を中断

　得られた最小解は今までと同様に size = 1512, ( 54 x 28 )　です。記念として探索結果を貼っておきます（クリックすると実行開始から終了までの画面表示が見えます）。

16サイズまでの正方形の配置の探索プログラム実行画面（Ver0.04）


　今回の最適化と実行環境をノートPCからディスクトップ（Win11要求仕様未達の古いPC）に変更したことで探索時間は 59分17秒 となり、下記の目標を達成できました。^^


★追記　2024/09/21　次の探索に進む条件を見直し高速化　{

　上記で次の探索へ進む条件での「空きスペースが4個以上」の部分が、サイズ３の正方形の探索（次の探索のサイズ２の正方形の面積が４なので））のみを考慮しているようでしっくりきませんでした。もっと汎用的に考えれば、幅１のギャップは最後に配置するサイズ１の正方形のみが使用可能なので全てのサイズの正方形の配置探索に適応できるように次探索へ進む条件を「幅１のギャップの総面積が（スキャン中の長方形の面積　－　全正方形の面積の総和　＋　１）以下」に変更しました。
　その結果、下図（クリックで表示範囲拡大）に示すように探索時間は 45分51秒 になりました。

16サイズまでの正方形の配置の探索プログラム実行画面（Ver0.04改）

}




★追記　2024/09/21
　１辺が１～１３の１３個の正方形を最小面積の長方形へ配置する方法を探索してみました。プログラム作成当初は結果がでるまでかなり時間が掛かっていましたが、今では４秒程度で最小面積＝836（38 x 22）の解が得られます。




★追記　2024/09/24
　旧Twiiterのタイムラインで情報提供頂き、Wolfram Demonstrations Project の「Tightly Packed Squares」のページで本パズルで1辺が３～３２までの探索結果を表示するデモが見れます（ソースも開示されている模様）。1辺が３３以上は未だに未解決のようなので興味のある人は挑戦してみては如何でしょうか？


タグ：正方形 パズル PUZZLE
2024-09-12 17:00  nice!(0)  コメント(0) 

CH32V203で遊ぶ（その６）クロックアップ　[CH32V]

　前回の記事で CH32V203 に TFT 液晶 MSP2807（320 x 240 dot）を接続した環境でのライン描画の高速化から端を発して新たな高速ライン描画法を提案しました。
　今回はレジスタ直書込みによる高速化と CH32V203 のクロックアップによる変貌ぶりについて記録して置きたいと思います。


１．はじめに
　以前から認識はしていたのですが、CH32V203 は今回使用している開発環境（MounRiver Studio）のディフォルト設定では外部クロックを使用する設定になっていて、今回のように外部クロックを接続していない状態では内部クロックを使って 8MHz で動作します。
　言わばこの大リングボール養成ギブスを付けた状態で今までグラフィック描画の高速化を試みてきました。今回はレジスタの直たたきによる高速化を行った後に、クロックアップにより羊の皮を脱ぎ捨てた CH32C203 の真の実力について記載します。


２．レジスタ直接制御による高速化
　サンプルプログラムの記述に従ってＣ言語で開発するとペリフェラルのステータス確認の度にサブルーチンコールし、サブルーチンの中では対応ビットをＡＮＤチェック後の状態（ゼロか否か）により、リターン値を設定するようなまどろっこしい処理になってしまいます。特にライン描画のような繰り返し回数が多い処理ではなるべくステップ数の少ない実装にしたいものです。
　そこでステータスの確認とデータの書き込みをレジスタ直アクセスにしてみました。レジスタのアドレスやステータスのビットの定義についてはディバッガでトレースすれば容易に確認でき、これらは ch32v20x.h や ch32v20x_spi.h のファイル内で定義されています。
　参考として SPI1 関連のレジスタとステータスレジスタのビット構成を下表に示します。

SPI1 関連レジスタ

SPI1 ステータス


　下図がレジスタ直制御対応前と対応後のロジアナ波形です。SPI のデータ出力の間隔が短くなり、高速化できていることが判ります。末尾の「４．まとめ」に記載しているようにレジスタを直接制御することで前回の記事に掲載した 512 個の線分を描画するテストプログラムの実行時間は従来の処理から 16% 程速くなりました。

レジスタ直制御対応前のSPI波形

レジスタ直制御対応後のSPI波形



３．クロックアップ
　下図は CH32V203 のクロック系の構成図で、これを見ると HSI（内部クロック）の 8MHz を PLL で１８倍まで逓倍したものを 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 のプリスケーラーは２に設定しているので SPI のクロックも 4MHz から 72MHz に変わることになります。流石に SPI のプリスケーラーの設定は変更が必要と思っていましたが、なんとそのままで動作しました。
　こうなると私の安いロジアナ（サンプリングの上限が100MSa/s）では波形を確認できません。最高サンプリング 1GSa/s のオシロで観測した SPI の CLK（水色）とデータ（黄色）が下図です。プローブが安物のせいか波形が綺麗には見えませんが、カーソルで示しているように確かに 72MHz 程度のクロックが出ているようです。ブレッドボード環境でこの周波数で動作していることもすごいですね。

SPI CLK（水色） と MOSI（黄色）



４．まとめ
　数回に渡り、高速化検討をしてきましたが、高速化を一通りやった感があるので今回はクロックを 8MHZ から一挙に上限の 144MHz にアップし、CH32V203 の羊の皮を脱がせて真の実力を見てみたところグラフィック描画はとんでもない速さになりました^^
　120円の CPU でこの速さはとてつもないと思います。接続した TFT 液晶 MSP2807 もすごいですね。

　最後に今回の高速化対応での線分描画時間の測定結果を下表に示します。

Nomethodtime[s]speed ratio
1Before13.1091.00
2Register direct11.3041.16
3Clockup(144MHz)0.62620.94


　X（旧Twitter）に投稿したメッセージに添付した動画を貼っておきます。




[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
タグ：Twitter CH32V203 高速ライン描画 BlogCH32V203 MounRiver Studio MSP2807
2024-08-04 13:50  nice!(0)  コメント(0) 

CH32V203で遊ぶ（その５）高速なライン描画法　[CH32V]

　前回の記事では DMA での高速転送機能によって TFT液晶 MSP2807（320 x 240 dot）での塗りつぶし処理を高速化したことについて書きました。この時のデモ表示を見ているとラインの描画が目で見えるほど遅いので何とか高速化できないものか考えてみました。
　ディバッガで追ってみると速度のネックはライン描画アルゴリズムよりもドット描画自体にあり、SPI や PIO での I/O 制御部がＣ言語での標準な制御方法ではまどろっこしい程の処理なのでレジスタ直書きやアセンブラ化すればかなり速くなりそうです。
　今回はライン描画処理の高速化を検討する中で、上記のような I/O 制御自体の高速化では無く、ライン描画アルゴリズム自体の高速化を思い付いた（以降、傾き予測法(Slope prediction method)と記す）ので記録しておきたいと思います。
　尚、後で気が付きましたが「ポケコン（G850）高速ライン描画」の記事でも引用していた「ラインルーチンの高速化の手法」のページにライン描画の高速化について判り易くまとめられていて、ここにダブルステップの手法が書かれていますが評価結果として高速化はできなかったとの結論でした。今回提案する傾き予測法は本ページの末尾にまとめたように実際に高速化への効果が確かめられた描画法です。


１．今回のお品書き
　ライン描画手法について下記の内容を記載します。
  1. 標準的なライン描画処理
  2. 両端からの同時描画
  3. 今回提案の傾き予測法
最後にまとめとして上記手法の評価結果を記載します。


２．高速ライン描画手法
　以降にライン描画の各手法について記載します。


　２－１．標準的なライン描画処理
　高速化のために整数だけの処理でラインを描画する手法でブレゼンハムのアルゴリズムとして広く知られています。
　下記のソースはネット上のソースを参照せずに独自に起こしたものですが、ブレゼンハムのアルゴリズムと同等の処理になっています。
　高速化の観点からループ内での条件分岐を最小限にするために傾きの大きさにより場合分けし、二つのループ処理に分割しています。PSET は１ピクセルを描画する外部処理です。

標準的なライン描画処理（Ｃ言語） 
void LineStd( int16_t xst, int16_t yst, int16_t xen, int16_t yen )
{
    int16_t x,y,difx,dify;
    int16_t err, xtail, ytail;

    LcdXPos = xen;
    LcdYPos = yen;
    difx = abs( xen - xst ) << 1;
    dify = abs( yen - yst ) << 1;
    if( ( (difx >= dify) && (xen > xst) )
     || ( (difx < dify) && (yen > yst) ) ) {
        x = xst;
        y = yst;
        xtail = xen;
        ytail = yen;
    } else {
        x = xen;
        y = yen;
        xtail = xst;
        ytail = yst;
    }
    if( difx >= dify ) {
        int16_t dy;

        dy = ytail > y ? 1 : -1;
        err = difx >> 1;
        for( ; x <= xtail; x++ ) {
            PSET( x, y );
            err += dify;
            if( err >= difx ) {
                err -= difx;
                y += dy;
            }
        }
    } else {
        int16_t dx;

        dx = xtail > x ? 1 : -1;
        err = dify >> 1;
        for( ; y <= ytail; y++ ) {
            PSET( x, y );
            err += difx;
            if( err >= dify ) {
                err -= dify;
                x += dx;
            }
        }
    }
}
・2024/08/16　中心部のポイントが乱れる場合がある問題に対処



　２－２．両端からの同時描画
　上記の改良版でラインが中心点から見て点対称なので始点側と同時に終点側も描画することでループ回数を１／２にして高速化しています。ループ終了後の PSET は始点～終点間の距離が偶数の場合、中心のポイントの描画が欠落してしまうことに対する対処です。

両端からの同時描画（Ｃ言語） 
void LineBoth( int16_t xst, int16_t yst, int16_t xen, int16_t yen )
{
    int16_t x,y,difx,dify;
    int16_t err, xtail, ytail;

    LcdXPos = xen;
    LcdYPos = yen;
    difx = abs( xen - xst ) << 1;
    dify = abs( yen - yst ) << 1;
    if( ( (difx >= dify) && (xen > xst) )
     || ( (difx < dify) && (yen > yst) ) ) {
        x = xst;
        y = yst;
        xtail = xen;
        ytail = yen;
    } else {
        x = xen;
        y = yen;
        xtail = xst;
        ytail = yst;
    }
    if( difx >= dify ) {
        int16_t dy;

        dy = ytail > y ? 1 : -1;
        err = difx >> 1;
        for( ; x < xtail; x++, xtail-- ) {
            PSET( x, y );
            PSET( xtail, ytail );
            err += dify;
            if( err >= difx ) {
                err -= difx;
                y += dy;
                ytail -= dy;
            }
        }
        if( x == xtail ) {
            PSET( x, y );
        }
    } else {
        int16_t dx;

        dx = xtail > x ? 1 : -1;
        err = dify >> 1;
        for( ; y < ytail; y++, ytail-- ) {
            PSET( x, y );
            PSET( xtail, ytail );
            err += difx;
            if( err >= dify ) {
                err -= dify;
                x += dx;
                xtail -= dx;
            }
        }
        if( y == ytail ) {
            PSET( x, y );
        }
    }
}
・2024/08/16　中心部のポイントが乱れる場合がある問題に対処



　２－３．今回提案の傾き予測法
　上記の描画では傾きが１（４５°）以下の場合と１より大きい場合の二通りに場合分けして処理しましたが、傾き予測法では傾きの大きさによりループ処理を更に２分割します。
　下図に示すように傾きの大きさと移動方向の条件により、次の移動方向を決定できるケースがあり、これを利用して高速化しています。前述の両端からの描画手法も併用します。

  • 傾きが 0 ～ 0.5 の場合
    　縦移動／横移動 は１／２以下なので下図の上側の緑色の■のように縦移動直後は必ず横移動になります。

  • 傾きが 0.5 ～ 1.0 の場合
    　縦移動／横移動 は１／２以上なので下図の下側の緑色の■のように横移動直後は必ず縦移動になります。

傾き予測法での予測方法


　例えば、上記の「標準的なライン描画処理」において単純にループ内で2ドット分の進みを処理すれば、ループ回数が 1/2 になるので for ループのための条件ジャンプの比率が１／２になり効果は少ないですが若干高速化します（ループ処理の展開による高速化）。逆に言うと１回のループ処理で多くのドットを処理してもそれに比例して条件分岐が増えれば高速化できません（当然処理量が比例して多くなっても高速化できません）。従って高速化するためには上図のようにループ内の条件ジャンプの増加を抑えつつ、より多くのドットを処理するようにする必要があります。

傾き予測法によるライン描画処理（Ｃ言語） 
// draw line Ver 0.02b
void LcdLine( int16_t xst, int16_t yst, int16_t xen, int16_t yen )
{
    int16_t x,y,difx,dify,until;
    int16_t err, xtail, ytail;

    LcdXPos = xen;
    LcdYPos = yen;
    difx = abs( xen - xst ) << 1;
    dify = abs( yen - yst ) << 1;
    if( ( (difx >= dify) && (xen > xst) )
     || ( (difx < dify) && (yen > yst) ) ) {
        x = xst;
        y = yst;
        xtail = xen;
        ytail = yen;
    } else {
        x = xen;
        y = yen;
        xtail = xst;
        ytail = yst;
    }
    if( difx >= dify ) {
        int16_t dy;

        dy = ytail > y ? 1 : -1;
        err = difx >> 1;
        until = x + (difx>>1) + ( (difx&1) ? 0 : -1);
        if( difx >= (dify<<1) ) {       // slope:[0,0.5]
            for( ; x < until; x++, xtail-- ) {
                PSET( x, y );
                PSET( xtail, ytail );
                err += dify;
                if( err >= difx ) {
                    err += dify - difx;
                    x++;
                    xtail--;
                    y += dy;
                    ytail -= dy;
                    PSET( x, y );
                    PSET( xtail, ytail );
                }
            }
        } else {            // slope:(0.5,1]
            for( ; x < until; x++, xtail-- ) {
                PSET( x, y );
                PSET( xtail, ytail );
                err += dify;
                if( err >= difx ) {
                    err -= difx;
                    y += dy;
                    ytail -= dy;
                } else {
                    x++;
                    xtail--;
                    PSET( x, y );
                    PSET( xtail, ytail );
                    err += dify - difx;
                    y += dy;
                    ytail -= dy;
                }
            }
        }
        for( ; x <= xtail; x++ ) {
            PSET( x, y );
            err += dify;
            if( err >= difx ) {
                err -= difx;
                y += dy;
            }
        }
    } else {
        int16_t dx;

        dx = xtail > x ? 1 : -1;
        err = dify >> 1;
        until = y + (dify>>1) + ( (dify&1) ? 0 : -1);
        if( dify >= (difx<<1) ) {
            for( ; y < until; y++, ytail-- ) {
                PSET( x, y );
                PSET( xtail, ytail );
                err += difx;
                if( err >= dify ) {
                    err += difx - dify;
                    x += dx;
                    xtail -= dx;
                    y++;
                    ytail--;
                    PSET( x, y );
                    PSET( xtail, ytail );
                }
            }
        } else {
            for( ; y < until; y++, ytail-- ) {
                PSET( x, y );
                PSET( xtail, ytail );
                err += difx;
                if( err >= dify ) {
                    err -= dify;
                    x += dx;
                    xtail -= dx;
                } else {
                    y++;
                    ytail--;
                    PSET( x, y );
                    PSET( xtail, ytail );
                    err += difx - dify;
                    x += dx;
                    xtail -= dx;
                }
            }
        }
        for( ; y <= ytail; y++ ) {
            PSET( x, y );
            err += difx;
            if( err >= dify ) {
                err -= dify;
                x += dx;
            }
        }
    }
}
・Ver 0.02 2024/08/03　中心部のポイントが描画されない場合がある問題に対処し、下記の実行時間も再測定
・Ver 0.02a 2024/08/16　中心部のポイントが乱れる場合がある問題に対処
・Ver 0.02b 2024/09/04　傾きが0.5以上で線が太くなる問題に対処


★追記　2024/08/06　{
　上記は速度優先で同様な処理が２カ所にありましたが、速度低下を最小限にしてコードを短くしたバージョンを追記します。

傾き予測法によるライン描画処理[shorter code ver]（Ｃ言語） 
// draw line Ver 0.03b
void LcdLine( int16_t xst, int16_t yst, int16_t xen, int16_t yen )
{
    int16_t x,y,difx,dify,until;
    int16_t err, xtail, ytail,dy;
    int16_t *px,*py,*pxtail, *pytail;

    LcdXPos = xen;
    LcdYPos = yen;
    difx = abs( xen - xst ) << 1;
    dify = abs( yen - yst ) << 1;
    if( ( (difx >= dify) && (xen > xst) )
     || ( (difx < dify) && (yen > yst) ) ) {
        x = xst;
        y = yst;
        xtail = xen;
        ytail = yen;
    } else {
        x = xen;
        y = yen;
        xtail = xst;
        ytail = yst;
    }
    if( difx >= dify ) {
        px = &x;
        py = &y;
        pxtail = &xtail;
        pytail = &ytail;
    } else {
        int16_t tmp;

        px = &y;
        py = &x;
        pxtail = &ytail;
        pytail = &xtail;
        tmp = difx;
        difx = dify;
        dify = tmp;
    }
    dy = *pytail > *py ? 1 : -1;
    err = difx >> 1;
    until = *px + (difx>>1) + ( (difx&1) ? 0 : -1);
    if( difx >= (dify<<1) ) {       // slope:[0,0.5]
        for( ; *px < until; (*px)++, (*pxtail)-- ) {
            PSET( x, y );
            PSET( xtail, ytail );
            err += dify;
            if( err >= difx ) {
                err += dify - difx;
                (*px)++;
                (*pxtail)--;
                *py += dy;
                *pytail -= dy;
                PSET( x, y );
                PSET( xtail, ytail );
            }
        }
    } else {            // slope:(0.5,1]
        for( ; *px < until; (*px)++, (*pxtail)-- ) {
            PSET( x, y );
            PSET( xtail, ytail );
            err += dify;
            if( err >= difx ) {
                err -= difx;
                *py += dy;
                *pytail -= dy;
            } else {
                (*px)++;
                (*pxtail)--;
                PSET( x, y );
                PSET( xtail, ytail );
                err += dify - difx;
                *py += dy;
                *pytail -= dy;
            }
        }
    }
    for( ; *px <= *pxtail; (*px)++ ) {
        PSET( x, y );
        err += dify;
        if( err >= difx ) {
            err -= difx;
            *py += dy;
        }
    }
}
・Ver 0.03a 2024/08/16　中心部のポイントが乱れる場合がある問題に対処
・Ver 0.03b 2024/09/04　傾きが0.5以上で線が太くなる問題に対処
}


３．各ライン描画法の評価
　上述のライン描画法の評価環境として、前回の記事でも使用した CH32V203（8MHz動作）に TFT液晶 MSP2807（320 x 240 dot）を接続した環境を使いました。評価方法としては事前に乱数で生成した 512 本のラインデータに従ってライン描画処理を実行した際の時間を計測しました。時間計測は systick タイマの内部カウンタだけでも計測できそうでしたが、今回は systick を使った 1ms 毎の割込み処理でインクリメントするカウンタ値で時間を計測しています。コンパイル時のオプティマイズはディフォルトのままの -Os（サイズ優先）です。

　下図は評価時の LCD 表示です。

ライン描画法評価時の LCD 画面


　計測結果を下表に示します。

No.methodtime[s]
1標準的なライン描画13.185
2両端からの同時描画13.121
3今回提案の傾き予測法13.109


　上記の表では殆ど時間差が無いように見えますが、冒頭で書いたようにドット描画処理（PSET）が重いので PSET を何もしないダミー関数にし、ライン描画アルゴリズムの処理自体の時間を計測し直した結果が下表です。

No.methodtime[s]speed ratio
1標準的なライン描画0.2001.00
2両端からの同時描画0.1241.61
3今回提案の傾き予測法0.1121.79


　期待通り、今回提案の傾き予測法は標準的なライン描画より約 1.8 倍速いという結果になりました。


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
タグ：CH32V203 高速ライン描画 線分描画アルゴリズム 高速化 BlogCH32V203 MounRiver Studio 傾き予測法 線分発生アルゴリズム 線分の描画
2024-08-01 15:27  nice!(0)  コメント(0) 

CH32V203で遊ぶ（その４）DMAで高速描画　[CH32V]

　「CH32V203で遊ぶ（その１）SPIでLCD」の記事の末尾に追記したように SPI インターフェースを使って 2.8インチTFT液晶 MSP2807（320 x 240 dot）に描画できるようになりましたが、画面クリアに時間が掛かることから DMA を使って高速化したのでメモっておきたいと思います。


１．今回の目標
　2.8インチTFT液晶 MSP2807（320 x 240 dot）への連続したデータ書き込み処理部分を DMA 機能を使って高速化します。


２．方針
　下記の変更／追加を行います。
  1. SPI のクロックアップ
    　SPI のクロックは従来 2MHz でしたが上限の 4MHz にアップします

  2. 連続データ書き込み処理の DMA 化
    　LCD への連続したデータ書き込みが発生する塗りつぶし処理（画面クリア含む）を DMA 機能で実現します

  3. 塗りつぶし機能追加
    　円と四角形の塗りつぶし機能を実装します


３．対処内容
　以下に対処した内容について記載します。DMA を利用すると言っても DMA の設定の追加と LCD へのデータ書き込み部分のコードを若干変更するだけなので本記事の内容がスカスカになってしまうのを防ぐためにデータシートからの引用等を含め、CH32V203 の DMA 機能自体の説明もある程度記載します。


　３－１．SPI のクロックアップ
　SPI の初期化の時のプリスケーラの設定を変更するだけです。簡単ですね。


SPI_InitStructure.SPI_BaudRatePrescaler = SPI_BaudRatePrescaler_2; // 16:500kHz



　３－２．連続データ書き込み処理の DMA 化
　今回使用している CPU（CH32V203）のブロック図を下図に示します。DMA 機能は左上の部分にあり、８チャンネル構成で FLASH, SRAM 及びペリフェラルのバスに接続されています。機能としてはメモリ to メモリ、メモリ to ペリフェラル及び ペリフェラル to メモリの高速なデータ転送を実現します。

CPU（CH32V203）のブロック図


　ペリフェラルと言ってもそれを制御するペリフェラル用のレジスタは下図のようにメモリにマッピングされています。

CPU（CH32V203）のメモリマップ


　周辺機器とのインターフェースにはそれぞれ固有の機能があるので ＤＭＡ 側も各機能に合わせてカスタマイズされている関係上、ＤＭＡ のチャンネルとペリフェラルは下図のように対応付けされています。

DMA リクエストマッピング


　この対応付けを表にしたものが下表になります。今回は LCD 通信の送信（SPI1_TX）を DMA 化するので DMA の チェンネル３を使用することになります。

DMA チャンネル vs ペリフェラル対応表


　一つの DMA チャンネルで複数のリクエストに対応している関係上、下記の様にリクエスト要求側でリクエストを有効にする設定が必要になります。


SPI_I2S_DMACmd(SPI1, SPI_I2S_DMAReq_Tx, ENABLE);



　DMA の制御レジスタのビット構成を下図に示します。あとはサンプルソースを参照して設定することで容易に動作しました。

DMA 制御レジスタ


　唯一悩ましかったのが次の点でした。
　今回は LCD の画面消去等の塗りつぶし（2バイトデータの連続書込み）が DMA 対象であり、この場合のペリフェラルサイズ（PSIZE)とメモリサイズ（MSIZE）の設定で悩みました。SPI 側のデータサイズはバイトに設定していて、書き込みデータはメモリ上に２バイトデータで存在するので
  • PSIZE : DMA_PeripheralDataSize_Byte
  • MSIZE : DMA_MemoryDataSize_HalfWord
と設定したところ、メモリ上のデータの１バイト目だけしか転送されませんでした。最終的には PSIZE を HalfWord に変更し、かつ DMA 使用時は SPI のデータサイズも 16bit に変更することでうまく動作するようになりました。

　参考として DMA 設定部分のソースを以下に貼っておきます。ppadr と memadr の型が uint32_t になっていて、これは void * の方が妥当だと思いますがサンプルのままで弄っていません。

DMA 初期化部分のソース 
// init Dma
void DMA_Tx_Init(DMA_Channel_TypeDef *DMA_CHx, uint32_t ppadr, uint32_t memadr, uint16_t bufsize)
{
	DMA_InitTypeDef DMA_InitStructure = {0};

	RCC_AHBPeriphClockCmd(RCC_AHBPeriph_DMA1, ENABLE);
	DMA_DeInit(DMA_CHx);

	DMA_InitStructure.DMA_PeripheralBaseAddr = ppadr;
	DMA_InitStructure.DMA_MemoryBaseAddr = memadr;
	DMA_InitStructure.DMA_DIR = DMA_DIR_PeripheralDST;
	DMA_InitStructure.DMA_BufferSize = bufsize;
	DMA_InitStructure.DMA_PeripheralInc = DMA_PeripheralInc_Disable;
	DMA_InitStructure.DMA_MemoryInc = DMA_MemoryInc_Disable;	// nenory not incriment
	DMA_InitStructure.DMA_PeripheralDataSize = DMA_PeripheralDataSize_HalfWord;
	DMA_InitStructure.DMA_MemoryDataSize = DMA_MemoryDataSize_HalfWord;
	DMA_InitStructure.DMA_Mode = DMA_Mode_Normal;
	DMA_InitStructure.DMA_Priority = DMA_Priority_VeryHigh;
	DMA_InitStructure.DMA_M2M = DMA_M2M_Disable;
	DMA_Init(DMA_CHx, &DMA_InitStructure);
}


　連続書込み部分のソースは下記になります。DMA での１回の転送データ数は 0xffff 個が上限（0x0000 設定時は転送しない）なので転送数が 0xffff より大きい場合は分割して転送するようにしています。ループ内に if 文を入れれば一つのループにできますが速度優先で二つのループにしています（実質的な速度は殆ど変わらないとは思いますが）。

DMA での連続書込み部分のソース 
// write same data
//  data <- write data
//  len <- how many data
void LcdWrFill( uint16_t data, uint32_t len )
{
	LcdWrDotCmd();			// send mem write command(on SpiCs)
#ifndef USE_DMA	// not USE DMA
	while( len-- ) {
		LcdWrWord( data );
	}
	LcdCsOff();
#else
	SPI_InitStructure.SPI_DataSize = SPI_DataSize_16b;	// 16bit mode msbfirst
	SPI_Init( LCD_SPI, &SPI_InitStructure );

	while( LCD_SPIWRSTS() == RESET ) {}	// wait until can write
	PrevSort = DATA;
	while( LCD_SPIWRBSY() == SET ) {}	// wait until write complete
	LCD_BSET( LCD_CMD );
	while( len > 0xffff ) {
		DMA_Tx_Init( DMA1_Channel3, (u32)&SPI1->DATAR, (uint32_t)&data, 0xffff );
		DMA_Cmd(DMA1_Channel3, ENABLE);
		len -= 0xffff;
		while(!DMA_GetFlagStatus(DMA1_FLAG_TC3)) {};
	}
	if( len ) {
		DMA_Tx_Init( DMA1_Channel3, (u32)&SPI1->DATAR, (uint32_t)&data, (uint16_t)len );
		DMA_Cmd(DMA1_Channel3, ENABLE);
		while(!DMA_GetFlagStatus(DMA1_FLAG_TC3)) {};
	}
	LcdCsOff();
	SPI_InitStructure.SPI_DataSize = SPI_DataSize_8b;	// 8bit mode msbfirst
	SPI_Init( LCD_SPI, &SPI_InitStructure );
#endif
}


　下図は DMA 化前の画面クリア時（0x0000の連続書込み）のロジアナ波形です。SPI 出力間に隙間時間がかなりあります。

DMA 対応前の画面クリア時のロジアナ波形


　下図は DMA 化後のロジアナ波形です。隙間なく SPI 出力されています。

DMA 対応後の画面クリア時のロジアナ波形



　３－３．塗りつぶし機能追加
　上記の DMA 化した連続書込み処理を利用して、円と四角形の塗りつぶし描画処理を追加しました。


　４．まとめ
　SPI のクロックが MHz レベルになるとマイコンのソフト処理では流石に転送と転送の間に隙間時間が発生してしまいます。このため多くのマイコンが DMA 機能を有しており、効率よくテータ転送ができるようになっています。
　今回の LCD 表示での塗りつぶし処理も DMA 機能を使用することで隙間時間なく転送できるようになり、処理時間を短縮出来ました。
　更に LCD コントローラの書き込み対象の四角形範囲を指定できる機能により、四角形の塗りつぶしはかなり高速化しました。
　また、今回は使用していませんが、DMA の転送中間時点と転送終了時点で割込みを発生できるので、LCD 書込みと並行して別の処理をすることもソフトウェア次第で可能になります。

　最後に DMA 化後のデモ画面を貼っておきます。

DMA 描画デモ画面例


　X（旧Twitter）のメッセージに添付した動画も貼っておきます。



[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]
タグ：SPI DMA 高速化 BlogCH32V203 CH32V203 Twitter MounRiver Studio
2024-07-26 23:31  nice!(0)  コメント(0) 

CH32V203で遊ぶ（その３）USART割込みでLiDAR接続（その２）高速化　[CH32V]

　前回の記事の末尾に追記したように以前格安で購入した LiDAR は不安定要素が残存するもののセンスしたデータをきれいに描画できるようになりました。
　しかし、秋月電子通商さんで￥１２０で購入できる CH32C203（clockは144MHz）で処理していて LiDAR からの最大８個の測位データが含まれる通信データの塊（package）を５個中１個の割合でした処理できていませんでした。今回はこの処理を高速化してもっと多くの package を処理できるようにしたいと思います。下の写真は開発環境で CH32V203 を取り付けたブレッドボードにＬＣＤ（MSP2807、320 x 240 dot）と LiDAR を接続しています。

開発環境



１．今回の目標
　Ｃ言語レベルでの最適化を行い LiDAR から送信されてくる package をなるべく多く処理できるようにします。


２．高速化項目
　具体的な高速化ポイントは下記のとおりです。
  1. 三角関数をテーブルにして、整数演算処理化する
  2. RISC-V は LiDAR からのデータと同様、リトルエンディアンなので LiDAR からの受信データからデータ抽出をせず直接使用する
  3. LiDAR からの package 受信バッファをダブルバッファ化して高速化する


　２－１．三角関数のテーブル化と整数演算処理化
　三角関数テーブルとしてが sin の値を０～９０度の区間分持つことにしました。この sin テーブルのデータ形式は LiDAR からのデータ形式及び受信データ表示用のＬＣＤの解像度（320 x 240）を考慮し、下記のようにしました。
  • 角度分解能
    　LiDAR からの角度データは dgree の６４倍で送られてきます。sin テーブルの角度に関しては dgree の４倍とし、LiDAR のデータ内の角度からの変換はシフト処理のみでできるようにしました。テーブル要素数は 90 x 4 で 360 要素の配列を持つことになります。
  • テーブル要素の値
    　メモリを節約し配列要素は１バイトとし、値がゼロの場合は 0x0100 とみなすようにします。配列上は角度０の場合もゼロの値になりますが、角度０の場合は配列を参照せずに結果はゼロと判断するようにしました。

　配列用データの生成は下記の 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 table 0-90 degree : 360 values
 *  Ver 0.01 2024/07/20 by skyriver
 */

#define SINDEGPAR	(4)	// Angles are digit fixed point degree

const uint8_t SinTable[] = {
	 0x00,0x01,0x02,0x03,0x04,0x06,0x07,0x08
	,0x09,0x0A,0x0B,0x0C,0x0D,0x0F,0x10,0x11
	,0x12,0x13,0x14,0x15,0x16,0x17,0x19,0x1A
	,0x1B,0x1C,0x1D,0x1E,0x1F,0x20,0x21,0x23
	,0x24,0x25,0x26,0x27,0x28,0x29,0x2A,0x2B
	,0x2C,0x2E,0x2F,0x30,0x31,0x32,0x33,0x34
	,0x35,0x36,0x37,0x38,0x3A,0x3B,0x3C,0x3D
	,0x3E,0x3F,0x40,0x41,0x42,0x43,0x44,0x45
	,0x47,0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E
	,0x4F,0x50,0x51,0x52,0x53,0x54,0x55,0x57
	,0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F
	,0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67
	,0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F
	,0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77
	,0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F
	,0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87
	,0x88,0x89,0x8A,0x8A,0x8B,0x8C,0x8D,0x8E
	,0x8F,0x90,0x91,0x92,0x93,0x94,0x95,0x96
	,0x96,0x97,0x98,0x99,0x9A,0x9B,0x9C,0x9D
	,0x9E,0x9E,0x9F,0xA0,0xA1,0xA2,0xA3,0xA4
	,0xA5,0xA5,0xA6,0xA7,0xA8,0xA9,0xAA,0xAA
	,0xAB,0xAC,0xAD,0xAE,0xAF,0xAF,0xB0,0xB1
	,0xB2,0xB3,0xB3,0xB4,0xB5,0xB6,0xB7,0xB7
	,0xB8,0xB9,0xBA,0xBA,0xBB,0xBC,0xBD,0xBD
	,0xBE,0xBF,0xC0,0xC0,0xC1,0xC2,0xC3,0xC3
	,0xC4,0xC5,0xC6,0xC6,0xC7,0xC8,0xC8,0xC9
	,0xCA,0xCA,0xCB,0xCC,0xCC,0xCD,0xCE,0xCE
	,0xCF,0xD0,0xD0,0xD1,0xD2,0xD2,0xD3,0xD4
	,0xD4,0xD5,0xD5,0xD6,0xD7,0xD7,0xD8,0xD9
	,0xD9,0xDA,0xDA,0xDB,0xDB,0xDC,0xDD,0xDD
	,0xDE,0xDE,0xDF,0xDF,0xE0,0xE0,0xE1,0xE2
	,0xE2,0xE3,0xE3,0xE4,0xE4,0xE5,0xE5,0xE6
	,0xE6,0xE7,0xE7,0xE8,0xE8,0xE8,0xE9,0xE9
	,0xEA,0xEA,0xEB,0xEB,0xEC,0xEC,0xED,0xED
	,0xED,0xEE,0xEE,0xEF,0xEF,0xEF,0xF0,0xF0
	,0xF1,0xF1,0xF1,0xF2,0xF2,0xF2,0xF3,0xF3
	,0xF3,0xF4,0xF4,0xF4,0xF5,0xF5,0xF5,0xF6
	,0xF6,0xF6,0xF7,0xF7,0xF7,0xF8,0xF8,0xF8
	,0xF8,0xF9,0xF9,0xF9,0xF9,0xFA,0xFA,0xFA
	,0xFA,0xFB,0xFB,0xFB,0xFB,0xFC,0xFC,0xFC
	,0xFC,0xFC,0xFC,0xFD,0xFD,0xFD,0xFD,0xFD
	,0xFE,0xFE,0xFE,0xFE,0xFE,0xFE,0xFE,0xFE
	,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF
	,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00
	,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
};


　上記の sin テーブルを持つことで LiDAR からのデータ処理を浮動小数点を使わず、全て整数処理で行うことができるようになり、かなり高速化できました。

　下図は従来からの浮動小数点演算処理時のロジアナ波形の再掲ですが、５個の package 中、１個だけ処理ができています。マーカー０がデータ抽出＋１ポイント描画の時間でマーカー１が1ポイントの時間なのでデータ抽出には 1ms 程の時間が掛かっていることになります。この package では８個のポイントを描画しています。

浮動小数点演算での処理（従来方式）


　下図は整数演算処理化した改善版のロジアナ波形です。３ package 中１個の package が処理できるようになったので処理率は従来の２０％から３３％に改善されました。SpiClk が発生している部分がＬＣＤ描画している箇所ですが、従来は８回の描画に隙間が見えましたが、高速化したことにより、隙間が見えなくなっています（マーカー１の部分）。マーカー０の部分は LiDAR のデータから必要なデータを抜き取っている部分ですが、800us 程の時間が掛かっていることが判ります。

整数演算で高速化した処理（改善版）



　２－２．データ抽出処理の高速化
　今回使用している CH32V203 は 32 ビット RISC-V をベースに設計されていて、LiDAR からのデータと同様にリトルエンディアンです。従来の処理では LiDAR からのデータの受信バッファからバイト単位でデータを抜き取り、シフト処理でワードデータ等を抽出していました。高速化のために受信バッファ内のポインタをキャストすることでデータ抽出を行わず直接参照するようにしました。

　高速化後のロジアナ波形が下図になります。マーカー０がデータ抽出処理ですが、前述のロジアナ波形では 800us 程度かかっていたデータ抽出処理が 71us 程度に高速化できました。尚、ロジアナ波形の最後に追加した"receiving"はLiDARからのデータを割込み処理で受信中であることを示すディバッグのための信号です。受信データ処理中は LiDAR からのデータを受信できていないことが判ります。

データ抽出部改善後



　２－３．ダブルバッファ化
　LiDAR からのデータを受信するための受信バッファをダブルバッファー化し、処理中でも LiDAR から出力されるデータを受信できるようにすることで受信待ち時間を最小にして高速化しました。
　下図がダブルバッファー化後のロジアナ波形です。処理が追い付かず稀に未処理の package が発生していますが、package の処理率はほぼ１００％に改善できました。

ダブルバッファー化後



３．まとめ
　最近弄りだした１２０円の３２ビットマイコンの CH32V203 に４年前に購入し、お蔵入りしていた格安の LiDAR を繋いでデータ抽出し、ＬＣＤ上にリアルタイムで表示できるようになりました。
　ＣＰＵパフォーマンスの関係で初めは LiDAR からのデータの２０％程度しか表示処理できませんでしたが、今回高速化の改善を行った結果、LiDAR からのデータのほぼ１００％を処理し表示できるようになりました。
　ネット上で見かける LiDAR データの表示は M5Stack（32bit 240MHz デュアルコア）等の例が多く、数百円レベルのマイコンでの例は見かけません。
　今回は秋月電子通商さんで１２０円で購入できるＣＨ３２Ｖ２０３（32bit 144MHz）を使って下の写真のように LiDAR からのデータをＬＣＤに表示できるようになりました。
　「非力なマイコンで工夫をしてパフォーマンスを引き出す」というのはマイコン弄りの醍醐味の一つではないでしょうか？

LiDAR データのＬＣＤ表示例


★追記　2024/07/21
　X（旧Twitter）に投稿したメッセージに添付した動画を貼っておきます。




★追記　2024/07/24
　X（旧Twitter）で最近話題になっている安価な小型の LiDAR が着荷したので試してみました。「UnknownLiDARMini_M5StackCore2」を参考にさせて頂き、従来のソフトウェアを若干変更することで１２０円マイコン（CH32V203）で LCD にデータをリアルタイムで表示できました。


新 LiDAR（表面）


新 LiDAR（裏面）


新 LiDAR の試験環境




[TOP] [ 前へ ] 連載記事一覧[ 次へ ]

タグ：MounRiver Studio CH32V203 LIDAR UART BlogCH32V203 USART 割込み処理 高速化
2024-07-21 23:05  nice!(0)  コメント(0) 
前の5件 | -

連載記事

Z80チップサイズCP/Mボード
GAL使用のZ80コンパクトボード
MC68KチップサイズCP/M-68Kボード
ポケコン（G850）用拡張基板
DIP IC13個構成の自作8bitCPU
レトロマイコン86ボードの構想
3チップ構成Pic24CPM-68Kマイコン
GALを使った最小構成のZ80マイコン
3チップ構成Pic24CPMマイコン
PIC24FJで４足ロボットの製作
独自言語 (picle) on PIC24FJ
PIC24FJ64GAでＧＡＭＥ言語
OneBitLoader （ブートローダー）
デジタル式定電流放電器
カッティングマシンでプリント基板製作
ロボット掃除機LAQULITO
赤外線での制御
1bitシリアル通信

PIC24FJ
PIC16F886

お勧め記事

開発作品公開ページ