# US 2021/0083869 A1 · An apparatus and method for aligning corresponding elements in multiple streams of elements

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0083869 A1
- Document ID: US20210083869A1
- Status: Published application
- Kind: A1
- Application number: 16/772,311
- Filed: 2018-12-19
- Published: 2021-03-18
- Earliest claimed: 2018-01-30
- Assignees: Arm Limited
- Applicants: Arm Limited
- Inventors: Alasdair GRANT
- Web page: https://patentgrep.com/patent/US20210083869A1

## CPC

- H04L 9/0869: {involving random numbers or seeds}
- G06F 7/582: {Pseudo-random number generators}
- G06F 11/3636: {by tracing the execution of the program}
- H04L 9/3236: {using cryptographic hash functions}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus and method are described for aligning corresponding elements in multiple streams of elements. An apparatus is provided comprising both first generation circuitry to generate a first stream comprising first elements and second generation circuitry to generate a second stream comprising second elements. The first generation circuitry is arranged to insert a first element in the first stream to identify each occurrence of a corresponding second element in the second stream. Key generation circuitry is used to generate, for each instance of the first element to be included within the first stream, an associated key value determined from a set of key values, the set of key values being insufficient to allow unique key values to be generated for each instance of the first element. The first generation circuitry is then arranged to indicate within the first stream the associated key value for each instance of the first element. By such an approach, subsequent analysis of a sequence of key values associated with a corresponding sequence of instances of the first element within the first stream enables alignment between a first element in the first stream and its corresponding second element in the second stream. This provides a very efficient mechanism for allowing alignment between individual elements in the first stream and corresponding individual elements in the second stream to be achieved, in a manner that alleviates bandwidth constraints in relation to the first stream.

## Claims

### Claim 1

An apparatus comprising:
first generation circuitry to generate a first stream comprising first elements;
second generation circuitry to generate a second stream comprising second elements;
the first generation circuitry being arranged to insert a first element in the first stream to identify each occurrence of a corresponding second element in the second stream;
key generation circuitry to generate, for each instance of the first element to be included within the first stream, an associated key value determined from a set of key values, where the set of key values is insufficient to allow unique key values to be generated for each instance of the first element;
wherein the first generation circuitry is arranged to indicate within the first stream the associated key value for each instance of the first element, such that subsequent analysis of a sequence of key values associated with a corresponding sequence of instances of the first element within the first stream enables alignment between a first element in the first stream and its corresponding second element in the second stream.

### Claim 2 (depends on 1)

An apparatus as claimed in claim 1, wherein the second stream contains identifier information in association with each second element sufficient to enable determination of the associated key value generated by the key generation circuitry for the corresponding first element.

### Claim 3 (depends on 2)

An apparatus as claimed in claim 2, further comprising counter circuitry to generate a counter value to form the identifier information, and the key generation circuitry is coupled to the counter circuitry in order to generate each key value from a current counter value.

### Claim 4 (depends on 3)

An apparatus as claimed in claim 3, wherein the key generation circuitry is arranged to apply a hash function to the current counter value in order to generate a corresponding key value.

### Claim 5 (depends on 2)

An apparatus as claimed in claim 2, wherein the identifier information comprises the associated key value.

### Claim 6 (depends on 1)

An apparatus as claimed in claim 1, wherein the key generation circuitry is a pseudo random number generator such that the sequence of key values within the first stream are pseudo random.

### Claim 7 (depends on 1)

An apparatus as claimed in claim 1, wherein the key generation circuitry is arranged to generate key values from the set such that a sequence of a specified number ‘s’ of key values repeats only after ‘p’ key values have been generated, where p>s.

### Claim 8 (depends on 7)

An apparatus as claimed in claim 7, wherein:
p=bs−1
where b is the number of key values in the set.

### Claim 9 (depends on 7)

An apparatus as claimed in claim 7, wherein the key generation circuitry comprises a linear feedback shift register (LFSR).

### Claim 10 (depends on 1)

An apparatus as claimed in claim 1, wherein both the first generation circuitry and the second generation circuitry are arranged to periodically issue a synchronisation value within the respective first and second streams to enable a coarse alignment of the first and second streams, and analysis of the sequence of key values enables exact alignment between a first element in the first stream and its corresponding second element in the second stream following the coarse alignment.

### Claim 11 (depends on 10)

An apparatus as claimed in claim 10, wherein:
the key generation circuitry is arranged to generate key values from the set such that a sequence of a specified number ‘s’ of key values repeats only after ‘p’ key values have been generated, where p>s; and
following the coarse alignment of the first and second streams based on the synchronisation value, then once a sequence of s key values have been observed in the first stream, alignment can be achieved between a first element in the first stream and its corresponding second element in the second stream.

### Claim 12 (depends on 10)

An apparatus as claimed in claim 10, wherein the synchronisation value is a global timestamp value.

### Claim 13 (depends on 1)

An apparatus as claimed in claim 1, further comprising:
processing circuitry to execute a sequence of instructions in order to perform data processing operations;
wherein:
the first generation circuitry forms first trace generation circuitry to generate, as the first stream, a first trace stream of trace elements, the trace elements in the first trace stream comprising at least the first elements; and
the second generation circuitry forms second trace generation circuitry to generate, as the second stream, a second trace stream of trace elements, the trace elements in the second trace stream comprising at least the second elements.

### Claim 14 (depends on 13)

An apparatus as claimed in claim 13, wherein:
the second trace generation circuitry comprises sampling circuitry triggered by the processing circuitry to sample data held in one or more storage elements, and to output the sampled data as the second element within the second trace stream; and
the sampling circuitry is arranged to issue a sampling event indication to the first trace generation circuitry when the sampling circuitry is triggered to sample the data, so as to cause the first trace generation circuitry to provide within the first trace stream, as the corresponding first element, a data sampling event.

### Claim 15 (depends on 14)

An apparatus as claimed in claim 14, wherein the first trace generation circuitry is coupled to an event bus to receive event indications, the sampling circuitry being arranged to issue the sampling event indication to the first trace generation circuitry over the event bus.

### Claim 16 (depends on 15)

An apparatus as claimed in claim 15, wherein the key generation circuitry is associated with the sampling circuitry, and the sampling circuitry is arranged to use a plurality of bits of the event bus to provide an event indication to the first trace generation circuitry that identifies both presence of the sampling event and the key value for that sampling event.

### Claim 17

A diagnostic apparatus comprising:
a first interface to receive a first stream of elements;
a second interface to receive a second stream of elements; and
analysis circuitry to perform an alignment operation in respect of the first and second streams;
the first stream containing a first element to identify each occurrence of a corresponding second element in the second stream, and providing in association with each instance of the first element an associated key value determined from a set of key values, where the set of key values is insufficient to allow unique key values to be generated for each instance of the first element; and
wherein the analysis circuitry is arranged to analyse a sequence of key values associated with a corresponding sequence of instances of the first element within the first stream in order to determine alignment between a first element in the first stream and its corresponding second element in the second stream.

### Claim 18 (depends on 17)

A diagnostic apparatus as claimed in claim 17, wherein the second stream contains identifier information in association with each second element and the analysis circuitry uses the identifier information to determine the associated key value used for the corresponding first element.

### Claim 19 (depends on 18)

An apparatus as claimed in claim 18, wherein the identifier information comprises a counter value generated by counter circuitry, and the analysis circuitry comprises key generation circuitry to generate an associated key value for each counter value.

### Claim 20

A method of operating an apparatus to generate multiple streams of elements, comprising:
generating a first stream comprising first elements;
generating a second stream comprising second elements;
during generation of the first stream, inserting a first element in the first stream to identify each occurrence of a corresponding second element in the second stream;
generating, for each instance of the first element to be included within the first stream, an associated key value determined from a set of key values, where the set of key values is insufficient to allow unique key values to be generated for each instance of the first element; and
indicating within the first stream the associated key value for each instance of the first element, such that subsequent analysis of a sequence of key values associated with a corresponding sequence of instances of the first element within the first stream enables alignment between a first element in the first stream and its corresponding second element in the second stream.

### Claim 21

A method of operating a diagnostic apparatus to analyse multiple streams, comprising:
receiving a first stream of elements;
receiving a second stream of elements; and
performing an alignment operation in respect of the first and second streams;
the first stream containing a first element to identify each occurrence of a corresponding second element in the second stream, and providing in association with each instance of the first element an associated key value determined from a set of key values, where the set of key values is insufficient to allow unique key values to be generated for each instance of the first element; and
during said alignment operation, analysing a sequence of key values associated with a corresponding sequence of instances of the first element within the first stream in order to determine alignment between a first element in the first stream and its corresponding second element in the second stream.
