Skip to main content

m34 · Mapping-system software architecture: real-time pipeline, latency, data formats

Warning

Education only. Not for diagnosis, treatment or any clinical decision.

Note

Draft, stages 2 to 4 of 6. The derivations and three interactive demos are written. Each equation is checked by tests in tests/test_m34_pipeline.py, and the demos’ math is checked against the same Python model in tests/test_part6_demo_math.py. The code lab is in place too. The questions and the remaining sections follow in later stages (plan: docs/outlines/m34-outline.md). Nothing here has had expert review yet.

In 60 seconds

A mapping system is a real-time data pipeline. Many electrode channels arrive at a fixed sampling rate; a localization stream arrives at another rate, on another clock. Each processing stage adds delay, and a stage that runs close to its capacity adds a lot more: queueing delay grows without bound as the load approaches what the stage can handle. The operator sees the result on a display that refreshes on its own schedule. Good architecture keeps every buffer bounded, every delay budgeted, every sample timestamped, and stores what the system saw in a form that others can read.

From the field

Planned in the outline (docs/outlines/m34-outline.md); written in a later stage.

Derivations

Symbols used throughout. \(N\) number of channels. \(f_s\) sampling rate (Hz). \(b\) bits per sample. \(R\) data rate (bit/s). \(T\) a duration (s). \(\lambda\) arrival rate and \(\mu\) service rate of a stage (items/s). \(\rho = \lambda/\mu\) utilization. \(L\) mean number of items in a stage. \(W\) mean time an item spends in a stage (s). \(v\) catheter speed (mm/s).

A mapping system as a pipeline

Think of the system as a chain of stages, each taking items from an input buffer and passing results on: acquisition (amplifiers and analog-to-digital conversion), localization, signal processing and annotation, map building, display, and storage. Three quantities describe each stage:

  • Latency: the time from an item’s arrival to its result.
  • Throughput: how many items per second the stage can finish, at most \(\mu\).
  • Jitter: how much the latency varies from item to item.

An average hides the case that matters. A stage that is fast on average can still be late now and then, and the operator moving a catheter notices the late frames, not the average.

Key takeaways

  • Model the system as stages joined by buffers; give each stage a latency, a throughput and a jitter.
  • Design for the worst case you must tolerate, not for the mean.

Data rate and buffering

Every channel produces \(f_s\) samples per second of \(b\) bits each, so the raw data rate is

\[ R = N f_s b \tag{1}\]

plus whatever the transport adds for framing and checksums. If the consumer of a stream stalls for \(T\) seconds (a disk write, a garbage-collection pause, a busy display thread), the producer keeps writing. Nothing is lost only if the buffer between them holds at least

\[ B \ge R\,T \tag{2}\]

A full buffer must do something: drop new data, overwrite old data, or block the producer. Blocking an acquisition stage is rarely acceptable, so the choice is usually between dropping and overwriting, and it should be a design decision that is logged, not an accident.

Exact

Assumptions

  • Computes Equation 1 and Equation 2 for raw samples, with no compression or framing overhead.
  • Default: 8 channels sampled at 1 kHz with 14-bit resolution, as in each record of the Intracardiac Atrial Fibrillation Database (Intracardiac Atrial Fibrillation Database (Version 1.0.0) 2003). Session length and stall duration are illustrative inputs, not typical values.
  • What would change the result: compression, framing overhead, padding samples to whole bytes (try 16 bits), and storing maps and annotations alongside the raw signals.

Key takeaways

  • Data rate is channels × sampling rate × sample width, plus framing.
  • A buffer must cover the longest stall you design for; decide and log what happens when it is full.

Queues: why latency explodes near full load

Little’s law. For any stage that is stable over a period, the mean number of items inside it, the arrival rate and the mean time each item spends there are tied together (Little 1961):

\[ L = \lambda W \tag{3}\]

It needs no assumption about the distribution of arrivals or service times. Over a period that starts and ends with the stage empty it holds exactly (Little 2011): both sides are the total item-time spent in the stage, divided by the length of the period.

A single-server queue. Now assume random arrivals (a Poisson process at rate \(\lambda\)) and random service times (exponential, rate \(\mu\)): the “M/M/1” queue. In steady state, the rate of moving from \(n\) to \(n + 1\) items equals the rate of moving back, \(\lambda p_n = \mu p_{n+1}\), so the probability of \(n\) items is \(p_n = (1 - \rho)\rho^n\) for \(\rho < 1\). Its mean is

\[ L = \frac{\rho}{1 - \rho} \tag{4}\]

and Little’s law turns it into the mean time in the stage:

\[ W = \frac{L}{\lambda} = \frac{1}{\mu - \lambda} \tag{5}\]

With no load, \(W = 1/\mu\), the bare service time. At load \(\rho\) it is \(1/(1 - \rho)\) times larger: twice as large at half load, ten times at 90%, and without bound as \(\rho \to 1\). Real stages are not exactly M/M/1; with other service-time distributions the numbers change, but delay still rises steeply as utilization approaches one (checked by simulation in the tests).

Simulation

Assumptions

  • Model: one first-in-first-out stage with random (Poisson) arrivals at rate λ and service times with mean 1/μ drawn from an Erlang distribution of shape k. k = 1 gives exponential service times, the M/M/1 case of Equation 5; larger k means more regular service.
  • Simulated item by item: 80,000 items, the first 10% discarded as start-up, with a fixed random seed so the picture is repeatable. Times are in units of the mean service time, so no product values are assumed.
  • Buffer capacity counts the items in the stage, including the one in service; a full stage drops new arrivals. At the maximum capacity drops are rare and the formula line applies.
  • What would change the result: burstier arrivals (worse), several servers in parallel, priorities, or service times that depend on load.

Key takeaways

  • \(L = \lambda W\) holds for any stable stage; use it to size buffers from rates and delays.
  • Queueing delay grows like \(1/(1 - \rho)\): leave headroom on every stage that is on the real-time path.

The latency budget

The end-to-end latency is the sum of what each stage adds, processing \(T_{\text{proc},i}\) and queueing \(T_{\text{queue},i}\), plus the wait for the display. A result that becomes ready at a random moment waits for the next screen refresh, on average half a frame period \(T_{\text{frame}}\) and at most a whole one:

\[ \bar T_{\text{e2e}} = \sum_i \left( T_{\text{proc},i} + T_{\text{queue},i} \right) + \tfrac12 T_{\text{frame}}, \qquad T_{\text{e2e}}^{\max} = \sum_i \left( T_{\text{proc},i} + T_{\text{queue},i} \right) + T_{\text{frame}} \tag{6}\]

Filters are stages too. A linear-phase FIR filter with \(M\) taps has symmetric coefficients, so its frequency response is \(e^{-i\omega (M-1)/2}\) times a real amplitude: every frequency is delayed by the same number of samples. In seconds,

\[ \tau = \frac{M - 1}{2 f_s} \tag{7}\]

Longer filters give sharper frequency responses but add delay. Module m04 covers the filters themselves.

Key takeaways

  • Write the latency budget down, stage by stage, with a mean and a worst case.
  • The display adds up to one frame; a linear-phase filter adds \((M - 1)/(2 f_s)\).

Timing and alignment

Electrograms and catheter positions come from different streams. If the position used for a point is read \(\Delta t\) too late or too early while the catheter moves at speed \(v\), the point lands about

\[ \lvert \Delta x \rvert = v\, \lvert \Delta t \rvert \tag{8}\]

away from where the signal was recorded. Timing errors come from fixed offsets between clocks, from clock drift, and from the delays of the previous section if they are not removed with timestamps.

Positions are also sampled, usually more slowly than electrograms, so the position at an electrogram’s timestamp is interpolated. For linear interpolation between samples \(h\) seconds apart, the error is at most

\[ \lvert x(t) - \hat x(t) \rvert \le \frac{h^2}{8} \max \lvert \ddot x \rvert \tag{9}\]

where \(\ddot x\) is the acceleration of the catheter. Faster sampling helps quadratically.

Approximate model

Assumptions

  • Model: the tip moves at constant speed on a circle of radius 10 mm; location is sampled every \(h\) and linearly interpolated; each point’s position is read \(\Delta t\) away from its true time.
  • The bound in the readout is \(v\lvert\Delta t\rvert\) (Equation 8) plus the chord error \(h^2 v^2/(8r)\) from Equation 9 with \(\lvert\ddot x\rvert = v^2/r\) on a circle.
  • Speed, offset, sampling interval and radius are illustrative inputs. TODO(source): typical catheter speeds and location update rates, for realistic defaults.
  • What would change the result: clock drift (an offset that grows with time), cardiac and respiratory motion, and localization noise.

Key takeaways

  • Timestamp every sample at the source, on a common clock, and align streams by timestamp, not by arrival order.
  • A timing error becomes a position error of \(v\,\Delta t\); interpolation adds at most \(h^2 \max\lvert\ddot x\rvert/8\).

Storing what the system saw

A mapping session produces several kinds of data: the chamber geometry as a triangle mesh; the acquired points, each with a position, a time and annotations such as activation time and voltage; the electrograms behind each point, with their sampling rate, gain and units; and ablation or event records. Exports from commercial systems are stored in proprietary formats that are hard to access and use storage inefficiently (Williams et al. 2021).

OpenEP defines an open data structure for this content, with code to parse and analyze it. Parsing clinical datasets took 400 ± 162 s per patient, and the OpenEP data were two orders of magnitude smaller than the compressed clinical data (20.5 ± 8.7 Mb versus 1.46 ± 0.77 Gb) (Williams et al. 2021). For signals alone, PhysioNet’s WFDB format stores samples with their sampling rate, gains and units in a header (Goldberger et al. 2000); the m03 code lab reads one.

Key takeaways

  • Store geometry, points, annotations and raw signals together, with units, sampling rates and timestamps.
  • Prefer open, documented formats; record the software version that produced every derived value.

Clinical correlate

NotePending clinical review

Planned in the outline. Requires sign-off by an EP physician.

Visual summary

Planned in the outline.

How experts think

Planned in the outline.

Cheat sheet

Planned in the outline.

Interview questions

Planned in the outline.

Code lab

The lab rebuilds this module’s results in code, so you can see where each one comes from and break it on purpose. It runs in a few seconds.

Part What you do Data
A Generate an 8-channel stream from the m03 electrogram model, quantize it to 14 bits in 16-bit words, and measure stored versus information rate (Equation 1) synthetic
B Push blocks through a ring buffer while the consumer stalls; find the smallest buffer that loses nothing (Equation 2) and how spare capacity sets the recovery time synthetic
C Check Little’s law and the single-server queue by discrete-event simulation (Equation 3, Equation 5) synthetic
D Align a location stream with electrogram timestamps; measure the misregistration, then remove it with a common clock (Equation 8, Equation 9) synthetic
E Store the session in an OpenEP-style structure and in WFDB format, and read both back synthetic

Each part ends with checks: lines that pass with the code as given. If you change something and a check fails, that is information, not an error to hide.

Self-check

Planned in the outline.

Literature figures

Planned in the outline.

Further reading

Planned in the outline.

References

Goldberger, A. L., L. A. Amaral, L. Glass, et al. 2000. “PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals.” Circulation 101 (23): e215–20. https://doi.org/10.1161/01.cir.101.23.e215.
Intracardiac Atrial Fibrillation Database (Version 1.0.0). 2003. PhysioNet. https://doi.org/10.13026/C23S33.
Little, John D. C. 1961. “A Proof for the Queuing Formula: L = \(\lambda\) W.” Operations Research 9 (3): 383–87. https://doi.org/10.1287/opre.9.3.383.
Little, John D. C. 2011. “Little’s Law as Viewed on Its 50th Anniversary.” Operations Research 59 (3): 536–49. https://doi.org/10.1287/opre.1110.0940.
Williams, Steven E. et al. 2021. “OpenEP: A Cross-Platform Electroanatomic Mapping Data Format and Analysis Platform for Electrophysiology Research.” Frontiers in Physiology 12: 646023. https://doi.org/10.3389/fphys.2021.646023.