A trace-data processing device comprises an input to receive source-specific trace data streams comprising trace messages carrying execution-flow information on a program execution flow performed by a source device under test or under observation, hereinafter DUT. A trace-data processing unit (526, 1100) derives from the trace data stream runtime information associated with the program execution flow performed by the DUT. The trace-data processing unit comprises a message-distribution stage (1104), a plurality of parallel message-processing stages (1106.1, . . . 1106.N), and a result consolidation stage (1108) connected with the message-processing stages. The message-distribution stage (1104) distributes the received trace data stream (T1′) over the message-processing stages in the form of respective trace data sequences. The message-processing stages (1106.1, . . . 1106.N) generate from the trace data sections runtime information sequences. The result-consolidation stage (1108) composes runtime information data representing an at least partial reconstruction of the program execution flow performed by the DUT.