自動プログラミング。 パート4.自動設計プログラムの効率

目次。

前の記事

オートマトン-A2ではなく、条件付きでオートマトン実装A1を呼び出します。 元のA2はJavaScriptで記述されていますが、これらの実装を同等の条件下で調査できるようにするために、 バージョンA2をC ++にロールしました 。 彼から始めます。

（FSM ||！FSM）？

実装A1の場合と同様に、オプションA2は、テキストをブロックに分割するモジュールとテキストブロックを表示するモジュールに分かれています。

ブロックブレーカーは、関数A2 :: tDisplay :: Out_textで表されます。 彼女の分析から、私が条件付きで「非自動」と呼んでいるオプションA2は、状態図で説明されている典型的なオートマトンによって実装されていることが明らかです。

ソースの状態を強調するために、色で強調表示します。

オートマトンA2 :: tDisplay :: Out_textは、前回の記事の例に続くオートマトンの実装の別の例です。 明示的に割り当てられた2つの状態と、現在の内部状態を定義する変数（esc_mode）があります。 この変数がbool型であるという事実は、少なくともその能力を低下させません。

オプションA1の同様のオートマトンを考えてみましょう

ソースコード：オプションA1。 ブロック分割機。

これもオートマトンであり、3つの一意に区別される状態があり、それらの間の遷移が明確に登録されます。内部状態を記述する特別な変数はありませんが、プログラム構造はプログラムカウンターがこの変数であるようなものです。 いつ：

表1. プログラムカウンターの値とプログラムの現在の内部状態の対応

A2の場合、変数内部状態の役割は、bool型の変数、A1の場合はプログラムカウンター、およびそれにもかかわらず、これらは自動的に実装されるアルゴリズムと発音されます。 A2オプションはMilesマシンであることを思い出させてください。 ムーアオートマトン（オプションA1）とは異なり、出力信号（またはアクション）は楕円ではなく、遷移矢印の上、遷移条件の後のスラッシュの後に書き込まれます。

A2 :: OA。

struct tFont_item{ u1x Width; const u1x * Image; }; union { u2x Data; u1x Array[2]; }Symbol_buffer; //////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////// void printToBuffer( int lineStartX, int lineStartY, const tFont_item * symbolInfo, int minX, int maxX) { u1x bytes_Width = (symbolInfo->Width + 7) >> 3; for (int y = 0; y < Font_height; y++) { if(bytes_Width == 1) Symbol_buffer.Array[1] = *((u1x*)(symbolInfo->Image + bytes_Width * y)); else Symbol_buffer.Data = *((u2x*)(symbolInfo->Image + bytes_Width * y)); u2x bit_mask = 0x8000; for (int x = 0; x < symbolInfo->Width; x++) { bool bit = Symbol_buffer.Data & bit_mask; bit_mask = bit_mask >> 1; int lineX = lineStartX + x; int lineY = lineStartY + y; if (lineX >= minX && lineX <= maxX) { setPixelInBuffer(lineX, lineY, bit); } }//for (int x = 0; x < symbolInfo->Width; x++) }//for (int y = 0; y < Font_height; y++) };//void printToBuffer( int lineStartX, int lineStartY, tFont_item * symbolInfo, int minX, int maxX ) //////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////// void setPixelInBuffer(int x, int y, bool bit) { int bitNumber = (x & 7); int byteNumber = x >> 3; if (bit) { Line_buffer[y][byteNumber] |= (0x80 >> bitNumber); } };//void setPixelInBuffer(int x, int y, bool bit) 

この実装では、文字の分類は実行されません。したがって、 テキストブロック出力オートマトンの UAの操作は、表示される各シンボルの操作シンボル表示オートマトンへの直接呼び出しに削減されます。

しかし、オートマトンは手動実装のどこから来たのでしょうか？ A2の実装は、条件付きで非自動と呼ばれたという事実にもかかわらず、運用マシンにも基づいています。 これは最も単純なランダムビットマップマシンです。

前述のように、稼働中のマシンは、有効なパラメーターを使用して何らかのアクションを実行できる半製品です。 組み合わせパターンに縮退することができます。 それの主な要件：最大のシンプルさ、最大の効率。 これらの要件は、次に示すように矛盾します。

アルゴリズムの単純さの観点から、ランダムなビット単位の転送演算子は優れています。 それは普遍的で、文字ジェネレータの任意のピクセルを文字列バッファーの任意のピクセルにコピーできます。 この場合のOAのパラメーター化は、最も単純な制御オートマトンによって実行されます。

この例は、単純な制御ロジックを備えたほとんどのプログラムが自動的に実装されることを示しており、制御ロジックの逐次的な複雑さが発生すると自律性が現れます。 明示的なオートマトンとしてアルゴリズムを設計していない場合、プログラムを順次複雑化することにより、別のチップ、別の「松葉杖」を追加した後、「構造遷移」が発生することがあります-自動化が消え、記事2および3から非手動の例のようなものが得られます

それで、A2の純粋な形式での実装が自動であることを確認する機会がありましたが、それはどれほど効果的ですか？

A1対A2

問題の実装の有効性を比較する唯一の方法は、テストすることです。 テストには、IAR開発環境を使用します 。

最初のテスト例は、画面全体から行が消えるまで、右から左に走る行として表示されるフルスクリーンの文字列です。 物理的な出力は、データをI / Oポートに出力することでエミュレートされますが、これは最初の近似では事実です。
フォント6x9、ディスプレイ256x64。 最適化-最高速度。

 char Test_text[43]; int main( void ) { for(int i = 0; i < 42; i++) Test_text[i] = 'A' + i; Display = new tDisplay(256,64,16); for( int i = 0; i > -270 ; i-- ) { Display->Out_text(0,0,256,64,i,0, (uchar*)Test_text); } } 

IARに書き込む場合、測定方法について読むと役立つ場合があります。

（コントローラサイクルで）作業時間を測定するには、IAR C-SPYシミュレータを使用します。 コントローラーサイクルは、CTIMER1とCTIMER2の2つの特別なカウンターをカウントします。 これらは、 View-> Registerタブのデバッグモードで見つけることができるC-SPY IARデバッガー変数です。 各結果を手動で取得しないように、デバッガのマクロ機能を使用して、結果がファイルに自動的にダンプされます。

これを行うには、IARエディターでファイルを作成し、 cspy_1.macという名前で保存しました。 ファイルにマクロ関数を含むテキストを配置しました

 __var filehandle; //////////////////////////////////////////////// setup() { filehandle = __openFile("filelog1.txt", "w"); } //////////////////////////////////////////////// clear() { #CCTIMER1 = 0; } //////////////////////////////////////////////// out_data() { __fmessage filehandle , #CCTIMER1, "\n"; #CCTIMER1 = 0; } //////////////////////////////////////////////// close() { __closeFile(filehandle); } 

これはCに似た言語ですが、Cではなく、非常に単純であり、IARヘルプで詳しく説明されています。 次に、このファイルをプロジェクトに接続しました。 これを行うには、 [プロジェクト]-> [オプション]で[ デバッガ]を選択し、 [ マクロファイルを使用]チェックボックスをオンにし 、 cspy_1.macファイルを選択しました 。

図sp。1。 マクロ関数ファイルをプロジェクトに接続する

cspy_1.macで説明されているマクロ関数は、図4に示されているブレークポイントに接続されています。 sp.2。

図sp.2。 ブレークポイントを接続する

これを行うには、目的の位置にブレークポイントを配置します。 テキストの左側にある灰色のバーをダブルクリックすると、ブレークポイントが設定および削除されます。 すべてのポイントを設定したら、[表示]- > [ブレークポイント ]タブを開く必要があります

図sp.3。 カスタマイズ

関心のあるポイントを右クリックして[編集]を選択すると、[ ブレークポイントの編集]ウィンドウが表示されます

図sp.4。 カスタマイズ

表示されるウィンドウに、必要な機能の名前が登録されます。 1とマークされたフィールドに登録すると、指定された関数は、停止が発生したときにのみ呼び出されます。 プログラムを停止せずに、指定された関数を呼び出すには、その名前をフィールド2に書き込む必要があります。これにより、プログラムを停止するかどうかを決定するために、停止する前にこの関数が呼び出されます。 対応するマクロ関数が1を返す場合、停止が行われます。関数が0を返すか、何も返さない場合、停止はありません。 指定されたマクロ関数は、対応するCプログラム式がブレークポイントで実行されるまで実行されます。

調査結果はグラフに示されています。

オプションA2の場合、行が実際に出力ウィンドウの端を超えて延びている場合、結果として何も表示しないためにかなりの数のサイクルが費やされることが明確にわかります。 検証オプションは可能ですが、出力するものがある場合、アルゴリズムをさらに遅くします。 オプションA1の場合、ラインがウィンドウを出ると、循環消費量は3000サイクルのオーダーの値まで低下します。 この動作は、もともとオートマトンの適切な状態を選択することでアルゴリズム自体の構造に組み込まれていました（次の記事では、A1の例を使用して開発プロセスを説明します）。追加のチェックは不要です。

最初の例では、これら2つのアルゴリズムがクリープラインモードでどのように機能するかについての一般的なアイデアを示しますが、Displayモジュールの主な用途は、画面上の任意の位置に完全に収まるテキストの通常の出力です。 メインモードでのモジュールの動作を調べるために、テスト例を使用します。

 char Test_text[32]; int main( void ) { for(int i = 0; i< 31; i++) Test_text[i] = 'A' + i; Display = new tDisplay(256,64,24); for( int j = 0; j < 31; j++) { for( int i = 0; i < 8; i++) { Display->Out_text(0,0,256,64,i,0, (uchar*)&Test_text[31-j]); } } } 

このテスト例では、0〜31文字の異なる長さの行、フォント6x9を表示しています。 各行は最初にシフトなしで表示され、次に右に1ピクセル、次に2ピクセルずつシフトして表示されます。 最大8ピクセル。 これは、画面上のさまざまな位置でのテキストの出力をシミュレートします（両方のアルゴリズムが影響を受けます）。

結果はシフト全体で平均化されます。その結果、画面上の行の初期位置に依存しない値が取得されます。

予想どおり、循環消費の値は、文字列の文字数の増加とともに直線的に増加します。 オプションA1の場合、 特定の循環消費 （シンボルあたりのサイクル）はシンボルあたり1200サイクル、オプションA2の場合は5913サイクル（最適化、リコール、最大速度）です。

総間接費は3431（A1）および16433（A2）です。 アイドルサイクルの消費に注意する価値があります 。つまり、長さ0文字の文字列が入力-118（A1）および13548（A2）サイクルに供給される場合です。 このような大きな違いは、オプションA2のラインバッファのフラッシュに関連しています。 さらに文字「\ 0」のソース文字列をチェックすることにより、空の文字列のラインバッファのクリーニングを排除し、アイドルサイクルの消費をA1に匹敵する値に減らすことができます。 ラインバッファをより詳細に検討する正当な理由があるために、意図的にこれを実行しませんでした。 小文字のバッファを使用することは、オーバーヘッドが大きくなる主要な要素です。 最初に、setPixelInBuffer関数を書き換えることにより、ラインバッファーをクリーニングする操作を排除できます。

 void setPixelInBuffer(int x, int y, bool bit) { int bitNumber = (x & 7); int byteNumber = x >> 3; if (bit) { Line_buffer[y][byteNumber] |= (0x80 >> bitNumber); } else { Line_buffer[y][byteNumber] &= ~(0x80 >> bitNumber); } };//void setPixelInBuffer(int x, int y, bool bit) 

ただし、この場合は加速ではなく、文字ごとにアルゴリズムが約1.5倍（6x9フォントの場合）遅くなります。これは、ラインバッファーのクリーニング時にすべての「白」ピクセルが一度に出力され、このバージョンでは各「白」ピクセルが個別に表示されるためです グラフ写真 この場合に判明する画像を表示します。

これは、2〜4 kbのRAMボリュームを備えたマイクロコントローラーにとっては非常に無駄です。 これは、同じコントローラーに60 kbのROMが含まれており、tDisplayモジュールのプログラムコードが同じ2 kbのコード-3.2％を占めるという事実にもかかわらずです。 基本的な入出力機能（実行中の行と仮想出力ウィンドウの効果的な実装が既に含まれています）の3.2％は非常に許容できますが、1つのテキスト出力操作のRAMの41.5％は重大な費用です。 4 KBのRAMでより堅牢なmsp430f2616を使用しても、20％はまだ小さくありません。

私たちはmspについて話しているので、省エネについて言うのは場違いではありません。 これは、バッテリー駆動のデバイスでの使用に最適な、最も控えめなパワーマイクロコントローラーの1つです。 プログラムの速度を複数回上げると、全体として作業が高速化されるだけでなく（パフォーマンスが常に重要になるわけではありません）、 バッテリー電力を直接節約し 、マイクロコントローラーがほとんどの時間スリープモードになり、作業時間を延ばすことができます。繰り返し充電。

オプションA1は、ラインバッファなしのスキームに従って設計されています。 つまり、このモジュールは何倍も高速であるだけでなく、何十倍も少ないRAMを必要とします。 A1で使用されるマシンには、高速と経済の2つのサブ実装があります。 経済的なものは、約60バイトのRAMで動作します。 疑問が自然に発生します：おそらくA1オプションは、コードのサイズでA2オプションに負けますか？ 実際、最大速度の最適化（ただし、サイズの最適化が実行される）では、特性によって次の図が得られます。

表2.ソフトウェアモジュールの比較特性

比較のために、6x9フォントの場合、256文字すべてのグリフが定義されている文字ジェネレーターのサイズは3344バイトです。

フォントサイズの増加に伴い、特定の循環消費量がどのように増加するかを分析しましょう。 図 図14は、フォント6x9、8x16、および16x24の特定の循環消費量のグラフを示しています。これは、オプションA2のCA値が面積に比例し、オプションA1のCA値が文字の高さに比例することを示します。 これを強調するために、x軸はオプションA2の文字の領域と、A1の行の文字の高さを示しています。

A2と比較したオプションA1（以下、高速のすべての数値）の特定の循環消費量は、6x9フォントで4.9、8x16フォントで6.4倍、16x24で9.2倍であり、平均して文字列長が0..31文字の場合、オプションA1はより大きく表示されますパフォーマンスは、6x9フォントで4.6倍、8x16で5.8倍、16x24で7.9倍です。

未来への展望。

この一連の記事の範囲をはるかに超える重要な問題を提案させてください。 テストモジュールには最大速度の最適化がありました。 これらの実装を最適化する方法を知りたいです。 図 図15は、両方のオプションの異なるフォントについて、文字列の長さに応じた最適化係数（最適化されていないものと最適化されたものの比率）を示しています。

両方のバリアントの「削減」の程度は小さいことがわかります。これは、良い実装と悪い実装の両方について話していないことを意味します。 OA + UA。 ただし、圧縮オプションA2の1.4倍でも、オプションA1のみの圧縮オプション1.15倍よりも5〜8倍遅いことに注意してください。 オプティマイザーの主なツールであるインライン挿入関数、ループの最適化、短いループの展開など、これは驚くべきことではありません。 すなわち 標準の構造プログラミング構造を最適化します。 しかし、プログラムの基になっているオートマトン（図16）の最適化と同様に、アルゴリズムの最適化は生産性の大幅な向上をもたらします。これが今日の記事のライトモチーフです。

このことから、広範囲にわたる結論を引き出すことができます。コードオプティマイザーの進化経路の1つは、アルゴリズムのオートマトンへの変換と、結果のオートマトンの最適化に関連しています。 ただし、例A2には非常に原始的なオートマトンが存在するため、それらをさらに最適化する場所はありません。 A2と比較した場合のアルゴリズムA1の大幅な効率は、 運用オートマトンを構築するための根本的に異なるスキームの使用によるものです。 したがって、オプションA2の効率を高めるには、オプションA2の構造を最適化せずに、A1からOAを取得する必要があります。 「自動化された」コード最適化には、おそらく次のものが含まれます。

1. OA RefとUA Refへのソースコードの自動分割。 ほとんどの場合、行動の分析、パターンの検索になります。 この場合のオートマトンは、誰によっても取得されませんが、データベース内にあり、したがって分類できるオートマトンです。 したがって、OAの動作を説明するには、何らかの標準が必要です。 状態図と遷移図は原則として同じ動作を説明しているだけですが、直観では1つの状態図と遷移だけでは十分ではないことを示唆しています。

ソースコード内のオペレーティングマシンの自動認識と分類は、状態図（たとえば、IAR visualStateを作成する）に従ってマシンコードを生成するよりも実装が難しく、したがって、開発ツールは1は除外され、開発は2から開始されます。

2.データベースで利用可能なOAのセットから最も効果的なOAの検索は、おそらくエンジンでトレーニングされたニューラルネットワークに基づいて、検索エンジンによって実行されます。 すなわち データベースで利用可能な既製のセットから最適なソリューションを選択します。 データベース内の既製のソリューションは、プログラマーや、たとえば遺伝的アルゴリズムを使用してオペレーティングマシンを「マイニング」する特別に訓練されたプログラムによって「初期蓄積」の時代に開発されると想定されています。

3.選択したOAに対応する制御マシンをセットアップします。 オートマトンをコードに変換します。

上記の手順の後、追加のコード最適化を実行できます（今日と同じことを最適化と呼びます）。

前述のことは、操作オートマトンを記述するための標準が必要であることを意味します。 記述はすでにコードの形式で格納されているため、論理スキーム（VHDL）の意味ではなく、彼ができることとその適用性（動作の記述）のメタ情報のセット、オートマトンを自動的に検索できるようにするメタ情報の意味で-パートナー、たとえば、このAAをドッキングできるAA。 状態と遷移図は、間違いなくそのような記述の要素の1つです。

上記のように、これは、家族によって分類され、上記の説明とともに提供された、以前に開発された標準の特定のライブラリを意味します。 このライブラリのオペレーティングマシンは、たとえばCまたはアセンブラで既製になります。 各OAは適切な制御オートマトンに対応し、状態図の形式で保存されます。

オペレーティングマシンは特定のタスクとプラットフォームに合わせて調整された非常に効率的なソリューションであるため、このようなスキーム（つまり、コードの形のOAと図の形のUA）が望ましいです。 一方で、このOAの特性は、制御オートマトンによって設定される外部パラメーター（厳密に指定された制限内）によって変化する可能性があります。

制御オートマトンは、基本的にフィードバックループの動作を記述するモデルです。 回路設計者は、アンプに特定のフィードバックを設定することで、増幅素子自体の設計を妨げることなくパラメーターの変更を実現できます。 同様に、オートマトンでは、AA-操作オートマトンのフィードバック（各OAに厳密に指定された制限内）を調整することにより、操作部分を変更せずにオートマトン全体のプロパティを変更することができます。

したがって、ライブラリに格納されている制御オートマトンはまだ既製のモジュールではなく、必要な動作を取得するように構成できます。また、接続された抵抗とコンデンサのフィードバックチェーンがそれぞれオペアンプから積分器を作成するように、1つのタイプのUAがOAのさまざまな変更に適していますオペアンプの特性のばらつきに依存します。 , .

:

. , .

, . . , . , , , . , , . , , CortexM3

CortexM3

– . — . 1 , .