Implementation - 2024.2 English

Vitis Libraries

Release Date
2024-11-29
Version
2024.2 English

The transform function in class BrownianBridge transform an input sequence with number size to an output sequence. The output data applies to Brownian bridge process. Based on the algorithm, each point in output sequence is generated by previously calculated point. That is to say, each loop dependents on the output of previous loop. To eliminate the loop-carried dependency, we divide the loop into seven rounds. The loop body only depends on previous round, and the loop in each round has no dependence so that the initiation interval (II) could achieve 1.

The detailed steps of our implementation is as follows:

  1. Init: calculate the value of begin and end point.
  2. Round-1: divide the sequence into two parts, calculate value of the mid-point. Now the number of sub-sequence is 2.
  3. Round-2: divide each sub-sequence into two parts, calculate the value of mid-point. Then total number of sub-sequence is 4.
  4. Round-3: divide each sub-sequence into two parts, calculate the value of mid-point. Then total number of sub-sequence is 8.
  5. \(\ldots\ldots\)
  6. Round-6: divide each sub-sequence into two parts, calculate the value of mid-point. Then total number of sub-sequence is 64.
  7. Round-7: in this round, the distance of each dependency is greater than the loop latency. So the II could achieve 1.

A more discrete description is provided in the following figures. In each round, the order of generated data is from left to right.

order of generated data

Each round shares the same hardware logic named trans_body. It gets a begin and end value from the result buffer. Then aggregate it with left_weight and right_weight to get the value of mid-point. It is presented as follows:

detailed impl