Patent ID: 7447722
Filing Date: 2008-11-04
Classification: G06F

Abstract:
1. A method of operating a processing apparatus to convolve input data representing time samples by a convolution function to generate data representing filtered time samples, for high speed, low latency computing using both local memory and non-local memory data accesses the processing apparatus including at least one processor and a local memory, the at least one processor capable of accessing a memory subsystem including the local memory, the convolution function partitioned into a plurality of smaller convolution functions represented in the frequency domain by a set of respective filters, the method comprising: (a) retrieving at successive time frame blocks of the sampled input data, and converting the blocks of sampled input data into blocks of frequency domain inputs such that at a current time frame, the memory subsystem includes a current block of frequency domain inputs and one or more previous blocks of frequency domain inputs corresponding to one or more respective previous time frames, each block of frequency domain inputs including inputs at a set of frequency bins; (b) computing as frequency domain outputs at the set of frequency bins the convolution of the sampled input data with the convolution function, wherein at a current time frame for each frequency bin, the frequency domain output is formed from the product of the current input and a first filter and one or more products of one or more previous inputs with one or more corresponding filters, such that each previous input has a corresponding filter for contributing to the present output, the computing comprising at the current time frame: for a first set of one or more frequency bins, while a particular filter is in the local memory for the at least one frequency bin of the first set, such that at the first future time frame, the product of the second input with the particular filter has been pre-computed for determining the output at the first future time frame for the first set of one or more frequency bins, wherein the frequency bins are partitioned into partitions of the frequency bins comprising at least the first set of one or more frequency bins and at least a second set a second set of one or more frequency bins different from the one or more bins of the first set, wherein at the current time frame, the method includes applying a first execution phase for the first set of one or more frequency bins, including the computing of the one or more products for contributing to the output at the current time frame, and the pre-computing the one or more products for contributing to the output at the first future time frame, wherein the method further comprises: at the first future time frame for the first set of one or more frequency bins, applying a second execution phase comprising combining one or more products computed at the first future time frame with one or more products pre-computed before the first future time frame to form the output at the first future time frame for the first set of one or more frequency bins, at the first future time frame for the second set of one or more frequency bins, applying the first execution phase comprising computing one or more products for contributing to the output at the first future time frame; and pre-computing one or more products for contributing to the output at a second future time frame that is after the first future time frame, such at any time frame, different execution phases are carried out by the at least one processor on different sets of frequency bins in order to spread the work load of the at least one processor.