1

我正在开发一个实时嵌入式系统。我正在尝试创建详细的时序分析。我收集了运行时数据，记录了每个中断的开始和停止时间。每次爆发的数据看起来像这样

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

我的输出通道的带宽有限，而且我的高精度计时器很快就会溢出一个字，所以我在大约 150 微秒的突发时间内收集数据，然后随着时间的推移将其逐出。从这些数据中，我能够收集每次中断所花费的时间，以及调用和抢占的数量。

我想做的是将典型帧的完整执行序列放在一起，大约 2 毫秒长。

我突然想到，这几乎就像一个基因测序问题。我有几千个片段，每个片段占总帧的 7%。我应该能够将它们排列起来——匹配覆盖框架相同部分的部分——这样我就可以在整个期间构建一个单一的事件序列。会有一些帧到帧的变化，但我希望这些可以在最佳匹配类型的算法中得到解释。

所以我的问题是：有哪些算法可以进行这种排序？有没有不针对 DNA 或 Protiens 的现有工具？

4

1 回答 1

2

Your data seems fairly application-specific, so you may just have to experiment. First see if the order of ISR invocations with interrupt numbers (without timing information) discriminates sufficiently; just take the final N calls of each burst and do a search to find any other bursts with similar fragments near the beginning. You can use any string search algorithm for this task. If too few matches are returned, try a fuzzy search algorithm. If too many matches are returned, try a smarter matching algorithm that also weighs each match by the similarity of timings. Overall this shouldn't be too complicated, since a complete chain is just about 15 bursts, whereas for example in DNA sequencing you need to match up millions of very short fragments.

于 2010-10-28T23:46:50.567 回答