Methods and apparatus for job scheduling in a programmable mixed-radix DFT/IDFT processor
Methods and apparatus for job scheduling in a programmable mixed-radix DFT/IDFT processor. In an exemplary embodiment, a method includes receiving a plurality of discrete Fourier transform (DFT) jobs. Each job identifies a computation of a DFT of a particular point size. The method also includes bundling selected jobs having a selected point size into a mega-job, and identifying a radix factorization for the selected point size. The radix factorization includes one or more stages and each stage identifies a radix computation to be performed. The method also includes computing, for each stage, the identified radix computations for the selected jobs in the mega-job. The radix computations for each stage are performed for the selected jobs before performing radix computations for a subsequent stage. The method also includes outputting DFT results for the selected jobs in the mega-job.
1. A method, comprising:
receiving a plurality of discrete Fourier transform (DFT) jobs, wherein each job identifies a computation of a DFT of a particular point size;
bundling selected jobs having a selected point size into a mega-job;
identifying a radix factorization for the selected point size, wherein the radix factorization includes one or more stages and each stage identifies a radix computation to be performed;
computing, for each stage, the identified radix computations for the selected jobs in the mega-job, wherein the radix computations for each stage are performed for the selected jobs before performing radix computations for a subsequent stage; and
outputting DFT results for the selected jobs in the mega-job.
2. The method of claim 1 , further comprising storing data associated with the jobs of the mega-job into one side of a ping-pong memory buffer.
3. The method of claim 2 , further comprising performing an iteration to determine a radix computation, wherein each iteration comprises:
loading the data from a source location in the one side of the ping-pong memory buffer into a vector data path pipeline;
performing the identified radix computation on the data in the vector data path pipeline;
storing a radix result of the identified radix computation back into the source location in the one side of the ping-pong memory buffer, if a current iteration is not a last iteration; and
outputting the radix result, if the current iteration is the last iteration.
4. The method of claim 3 , wherein the operation of storing the radix result comprises storing the radix result back into the source location using a vector feedback data path.
5. The method of claim 3 , further comprising generating addresses used to perform the operations of loading and storing.
6. The method of claim 3 , further comprising scaling the data from the source location to generate scaled vector data.
7. The method of claim 6 , further comprising multiplying the scaled vector data by twiddle factors.
8. The method of claim 7 , further comprising generating the twiddle factors.
9. The method of claim 3 , further comprising configuring the vector data path pipeline to carry plurality data values per clock cycle.
10. The method of claim 1 , wherein the operation of computing further comprises configuring a mixed radix engine to perform a selected one of radix3, radix4, radix5, and radix6 computations for each stage.
11. An apparatus, comprising:
a job scheduler that receives a plurality of discrete Fourier transform (DFT) jobs, wherein each job identifies a computation of a DFT of a particular point size, and wherein the job scheduler bundles selected jobs having a selected point size into a mega-job;
a state machine that identifies a radix factorization for the selected point size, wherein the radix factorization includes one or more stages and each stage identifies a radix computation to be performed;
a programmable mixed radix engine that computes, for each stage, the identified radix computations for the selected jobs in the mega-job, wherein the radix computations for each stage are performed for the selected jobs before performing the radix computations for a subsequent stage; and
an output buffer that outputs DFT results for the selected jobs in the mega-job.
12. The apparatus of claim 11 , wherein the programmable mixed radix engine performs a selected one of radix3, radix4, radix5, and radix6 computations for each stage.
13. The apparatus of claim 12 , further comprising a ping-pong memory buffer that stores data associated with the jobs of the mega-job into one side of the ping-pong memory buffer.
14. The apparatus of claim 13 , further comprising a vector data path pipeline that receives the data from a source location in the one side of the ping-pong memory buffer, and wherein the programmable mixed radix engine performs the identified radix computation on the data in the vector data path pipeline.
15. The apparatus of claim 14 , further comprising an output staging buffer that stores a radix result of the identified radix computation back into the source location in the one side of the ping-pong memory buffer, if a current iteration is not a last iteration; and that outputs the radix result, if the current iteration is the last iteration.
16. The apparatus of claim 15 , wherein the output staging buffer stores the radix result back into the source location using a vector feedback data path.
17. The apparatus of claim 16 , wherein the job scheduler generates addresses used to perform the operations of loading and storing.
18. The apparatus of claim 14 , further comprising scaling the data from the source location to generate scaled vector data.
19. The apparatus of claim 18 , further comprising multiplying the scaled vector data by twiddle factors.
20. The apparatus of claim 14 , wherein the vector data path pipeline carries twelve data values per clock cycle.