1

私はリアルタイム組み込みシステムに取り組んでいます。詳細なタイミング解析を作成しようとしています。ランタイム データを収集し、各割り込みの開始時間と停止時間を記録しました。データの各バーストは次のようになります

 ISR#  time
 -----  ----
  1     34
  end   44
  4     74
  3     80
  end   93
  end   97
  ...

私の出力チャネルは帯域幅が限られており、高精度のタイマーは 1 ワードをすぐにオーバーフローさせるため、データを 150 マイクロ秒のバーストで収集し、時間の経過とともに細流化しています。このデータから、各割り込みに費やされた時間、および呼び出しとプリエンプションの数を収集することができました。

私がやりたいことは、典型的なフレームの完全な実行シーケンスをまとめることです。これは、長さが 2 ミリ秒までです。

これはほとんど遺伝子配列の問題に似ていると思います。数千のフラグメントがあり、それぞれがフレーム全体の 7% をカバーしています。フレームの同じ部分をカバーする部分を一致させて、全期間にわたって単一の一連のイベントを構築できるように、それらを並べることができるはずです。フレームごとに多少の変動はありますが、ベストマッチ タイプのアルゴリズムでこれらを考慮できることを願っています。

だから私の質問は、この種のシーケンスを行うためにどのようなアルゴリズムが存在するのですか? DNA またはタンパク質を対象としていない既存のツールはありますか?

4

1 に答える 1

2

あなたのデータはかなりアプリケーション固有のように見えるので、実験する必要があるかもしれません。最初に、割り込み番号 (タイミング情報なし) を使用した ISR 呼び出しの順序が十分に区別されるかどうかを確認します。各バーストの最後の N 回の呼び出しを取得し、検索を実行して、最初の近くに同様のフラグメントを持つ他のバーストを見つけます。このタスクには、任意の文字列検索アルゴリズムを使用できます。返される一致が少なすぎる場合は、あいまい検索アルゴリズムを試してください。返される一致が多すぎる場合は、タイミングの類似性によって各一致を重み付けする、よりスマートな一致アルゴリズムを試してください。完全なチェーンは約 15 バーストであるのに対し、たとえば DNA シーケンスでは、何百万もの非常に短いフラグメントを一致させる必要があるため、全体としてこれはそれほど複雑ではありません。

于 2010-10-28T23:46:50.567 に答える