Systolic similarity estimation with two-dimensional sliding window
A systolic array implemented in circuitry of an integrated circuit, includes a processing element array having processing elements arranged in a vertical direction and a horizontal direction, first loaders communicatively coupled to the processing element array to load samples A m,n from at least one external memory to the processing element array, and second loaders communicatively coupled to the processing element array to load samples B k,l from the at least one external memory to the processing element array. Each row of the samples A m,n is loaded one row at a time to a single processing element along the horizontal direction, and each row of the samples B k,l is loaded one row at a time to a single processing element along the vertical direction, wherein pairing between the samples A m,n and B k,l in the horizontal direction and the vertical direction enables data reuse to reduce bandwidth usage of the external memory.
1. A systolic array implemented in circuitry of an integrated circuit, comprising:
a processing element array, comprising processing elements arranged in a vertical direction and a horizontal direction;
first loaders communicatively coupled to the processing element array to load samples A m,n from at least one external memory to the processing element array; and
second loaders communicatively coupled to the processing element array to load samples B k,l from the at least one external memory to the processing element array, wherein each row of the samples A m,n is loaded one row at a time to a single processing element along the horizontal direction, and each row of the samples B k,l is loaded one row at a time to a single processing element along the vertical direction, wherein pairing between the samples A m,n and B k,l in the horizontal direction and the vertical direction enables data reuse to reduce bandwidth usage of the external memory, wherein a first row of the samples A m,n are loaded n times to a first row of the processing element array with delayed data transfer across the first row of the processing element array.
2. The systolic array of claim 1 , wherein the processing element array computes sum of absolute differences (SAD).
3. The systolic array of claim 1 , wherein the first loaders load the samples A m,n via a first-in-first-out (FIFO) method.
4. The systolic array of claim 1 , wherein the first loaders load non-zero samples A m,n while the second loaders load the B k,l samples having a row index equal to a corresponding row index of the non-zero sample A m,n and a column index equal to corresponding column index of the non-zero sample A m,n .
5. The systolic array of claim 4 , wherein once the row of the samples B k,l is processed by the single processing element, the row of the samples B k,l is deleted from the systolic array.
6. The systolic array of claim 4 , wherein the samples A m,n comprise a sparse matrix and the samples B k,l comprise a dense matrix.
7. The systolic array of claim 4 , wherein the samples A m,n with zero values are padded.
8. A systolic array implemented in circuitry of an integrated circuit, comprising:
a plurality of processing elements, wherein each of the plurality of processing elements receives a first data stream comprising a row of a first dataset having samples A m,n and a second data stream comprising a row of a second dataset having samples B k,l over a plurality of computing cycles that output a plurality of values to construct a two-dimensional sliding window, wherein each of the plurality of processing elements comprises:
a first circuitry to compute an absolute value of an intrapair between the first data stream and the second data stream;
a second circuitry to compute a difference between row indices m and k of the samples A m,n and the samples B k,l , wherein the difference provides an indication of a correspondence between the intrapair and the two-dimensional sliding window; and
an accumulator array to accumulate computed results from the first circuitry based on the indication.
9. The systolic array of claim 8 , wherein the two-dimensional sliding window comprises a two-dimensional array, wherein each element of the two-dimensional array comprises a sum of absolute difference (SAD) based on comparison between the first and second datasets.
10. The systolic array of claim 8 , wherein the first data stream is received according to a first data transfer scheme and the second data stream is received according to a second data transfer scheme.
11. The systolic array of claim 10 , wherein the first data transfer scheme comprises delaying data transfer by one sample between directly adjacent processing elements every time the first data stream is transferred to a different processing element cross a row of the plurality of processing elements.
12. The systolic array of claim 10 , wherein the first dataset comprises a sparse matrix and the first data transfer scheme comprises transferring the first data stream via a first-in-first-out (FIFO) method.
13. The systolic array of claim 10 , wherein the first dataset comprises a sparse matrix and the first data transfer scheme comprises transferring only non-zero samples A m,n .
14. The systolic array of claim 13 , wherein the second data transfer scheme comprises transferring a first row of the samples B k,l , wherein the first row of the samples B k,l have a row index and a column index equal to a first corresponding row index and a first corresponding column index of the non-zero samples A m,n .
15. The systolic array of claim 14 , wherein the second data transfer scheme comprises:
replacing the first row of the samples B k,l with a second row of the samples B k,l , wherein the second row of the samples B k,l have a row index and a column index equal to a second corresponding row index and a second corresponding column index of the non-zero samples A m,n .
16. A method to determine similarity between two datasets, comprising:
loading samples A m,n of a first dataset via a first data loading scheme, one row at a time, to a processing element of a systolic array comprising an array of processing elements, one processing element at a time;
loading samples B k,l of a second dataset via a second data loading scheme, in conjunction with loading the samples A m,n to the processing element, one row at a time and one processing element at a time, wherein the second data loading scheme comprises:
loading a first row of the samples B k,l , wherein the first row of the samples B k,l have a row index and a column index equal to a first corresponding row index and a first corresponding column index of the samples A m,n ; and
replacing the first row of the samples B k,l with a second row of the samples B k,l , wherein the second row of the samples B k,l have a row index and a column index equal to a second corresponding row index and a second corresponding column index of the samples A m,n ; and
computing a sum of absolute difference (SAD) value at each processing element.
17. The method to determine similarity between two datasets of claim 16 , wherein the first data loading scheme comprises delaying data transfer by one sample between directly adjacent processing elements every time the samples A m,n are loaded to a different processing element cross a row of the array of processing elements.
18. The method to determine similarity between two datasets of claim 16 , wherein the first corresponding row index and the first corresponding column index of the samples A m,n comprises the first corresponding column index of non-zero samples of the samples A m,n .
19. The method to determine similarity between two datasets of claim 18 , wherein the second corresponding row index and the second corresponding column index of the samples A m,n comprise the second corresponding row index and the second corresponding column index of non-zero samples of the samples A m,n .
20. The method to determine similarity between two datasets of claim 16 , wherein the samples A m,n comprise only non-zero samples.