A data processing apparatus is provided with trace circuitry for generating a plurality of trace streams including an instruction trace stream 10 and a data trace stream 12. The instruction elements within the instruction trace stream and the data elements within the data trace stream are marked with key values KV such that a match may be made between data elements and corresponding instruction elements. When predetermined conditions are met, synchronization markers 66 are inserted in both the instruction trace stream 10 and the data trace stream 12 in order to permit a precise correlation to be made between the instruction elements and the data elements when the data is subsequently analyzed.