PPT Slide
In the RADram system, the result matrix of the dynamic programming algorithm is computed at the memory system in parallel. This computation proceeds in parallel “wave fronts” from the top left corner of the result space. Afterwards, the processor is used to perform the “back-tracking” present in the largest-common-sub-sequence algorithm. The processor is ideal for this because of the non-regular data-dependent nature of the back-tracking step.
Dynamic Programming Largest-Common-Subsequence
For the RADram system, the sparse vector-matrix multiply algorithm is partitioned into reconfigurable and normal processing components. The reconfigurable logic is used to compute the intersection of the vector with the matrix. The processor then performs the floating point operations to compute the result. Performance gains are achieved through parallel application of the intersection computation, linearization of the memory access pattern, and compression of the processor-work stream.