Algorithm for piecing together a sequence from multiple fragments

Question

I am working on a real-time embedded system. I am trying to create a detailed timing analysis. I have collected runtime data, recording the start and stop time of each interrupt. Each burst of data looks something like this

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

My output channel has limited bandwidth, and my high precision timer overflows a word very quickly, so I am collecting data in ~150 microsecond bursts, then trickling it out over time. From this data I have been able to collect the time spent in each interupt, and the number of calls and pre-emptions.

What I would like to do is put together the complete execution sequence for a typical frame, which is ~2 ms long.

It occurs to me that this is almost like a gene-sequencing problem. I have a few thousand fragments, each covering 7% of the total frame. I should be able to line them up - match the portions which cover the same part of the frame - in such a way that I can construct a single sequence of events for the whole period. There will be some frame-to-frame variations, but I am hoping that these can be accounted for in a best-match type of algorithm.

So my question is: What algorithms exist to do this kind of sequencing? Are there any existing tools not targeted to DNA or Protiens?

Answer 1

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.