3D memory based address generator for computationally efficient architectures

Patent metadata

Field	Value
Publication number	US-9203671-B2
Application number	US-201213648443-A
Country	US
Kind code	B2
Filing date	Oct 10, 2012
Priority date	Oct 10, 2012
Publication date	Dec 1, 2015
Grant date	Dec 1, 2015

Abstract

Systems and methods are disclosed for reducing memory usage and increasing the throughput in variable-size Fast Fourier Transform (FFT) architectures. In particular, 3D symmetric virtual memory is disclosed to exploit the structure inherent in variable-size FFT computations. Data samples may be written to and read from the 3D symmetric virtual memory in a specific sequence of coordinates that exploits the structure inherent in variable-size FFT computations. Memory locations in the 3D symmetric virtual memory may be mapped to memory address in a 1D buffer using an address generation circuit.

First claim

What is claimed is:

1. A system for mapping memory locations of a 3D memory to a buffer, the system comprising circuitry for:
determining a first geometric pattern for storing data in the 3D memory based on a type of computation performed using the data as input;
storing the data in the 3D memory using the determined first geometric pattern;
mapping memory locations arranged in the first geometric pattern in the 3D memory to first memory locations in the buffer;
writing data to the first memory locations in the buffer;
mapping memory locations arranged in a second geometric pattern in the 3D memory to second memory locations in the buffer, wherein the memory locations in the second geometric pattern in the 3D memory overlap with the memory locations in the first geometric pattern in the 3D memory;
reading data from the second memory locations in the buffer after writing data to the first memory locations in the buffer; and
writing data to the second memory locations in the buffer after reading data from the second memory locations in the buffer.

2. The system of claim 1 , wherein the circuitry is further operative to:
map memory locations arranged in a third geometric pattern in the 3D memory to third memory locations in the buffer, wherein the memory locations in the third geometric pattern in the 3D memory overlap with the memory locations in the second geometric pattern in the 3D memory;
read data from the third memory locations in the buffer;
write data to the third memory locations in the buffer after reading data from the third memory locations in the buffer; and
read data from the first memory locations in the buffer after writing data to the third memory locations in the buffer.

3. The system of claim 2 , wherein the:
3D memory is a symmetric cube;
first geometric pattern is a slice of the 3D memory along a first dimension of the symmetric cube;
second geometric pattern is a slice of the 3D memory along a second dimension of the symmetric cube; and
third geometric pattern is a slice of the 3D memory along a third dimension of the symmetric cube.

4. The system of claim 1 , wherein mapping memory locations arranged in the first geometric pattern in the 3D memory further comprises generating memory addresses associated with the first memory locations in the buffer based on corresponding memory locations arranged in the first geometric pattern in the 3D memory.

5. The system of claim 1 , wherein the first memory locations in the buffer and the second memory locations in the buffer are locked.

6. The system of claim 1 , wherein the second memory locations in the buffer are released in response to reading data from the second memory locations in the buffer.

7. The system of claim 2 , wherein the size of the symmetric cube is selected to store a number of data samples substantially corresponding to a size of a largest data frame.

8. The system of claim 1 , wherein the circuitry is further configured to generate a backpressure enable signal to control a rate at which data is streamed to the buffer.

9. A method for mapping memory locations of a 3D memory to a buffer, the method comprising:
determining a first geometric pattern for storing data in the 3D memory based on a type of computation performed using the data as input;
storing the data in the 3D memory using the determined first geometric pattern;
mapping memory locations arranged in the first geometric pattern in the 3D memory to first memory locations in the buffer;
writing data to the first memory locations in the buffer;
mapping memory locations arranged in a second geometric pattern in the 3D memory to second memory locations in the buffer, wherein the memory locations in the second geometric pattern in the 3D memory overlap with the memory locations in the first geometric pattern in the 3D memory;
reading data from the second memory locations in the buffer after writing data to the first memory locations in the buffer; and
writing data to the second memory locations in the buffer after reading data from the second memory locations in the buffer.

10. The method of claim 9 further comprising:
mapping memory locations arranged in a third geometric pattern in the 3D memory to third memory locations in the buffer, wherein the memory locations in the third geometric pattern in the 3D memory overlap with the memory locations in the second geometric pattern in the 3D memory;
reading data from the third memory locations in the buffer;
writing data to the third memory locations in the buffer after reading data from the third memory locations in the buffer; and
reading data from the first memory locations in the buffer after writing data to the third memory locations in the buffer.

11. The method of claim 10 , wherein the:
3D memory is a symmetric cube;
first geometric pattern is a slice of the 3D memory along a first dimension of the symmetric cube;
second geometric pattern is a slice of the 3D memory along a second dimension of the symmetric cube; and
third geometric pattern is a slice of the 3D memory along a third dimension of the symmetric cube.

12. The method of claim 9 , wherein mapping memory locations arranged in the first geometric pattern in the 3D memory further comprises generating memory addresses associated with the first memory locations in the buffer based on corresponding memory locations arranged in the first geometric pattern in the 3D memory.

13. The method of claim 9 , wherein the first memory locations in the buffer and the second memory locations in the buffer are locked.

14. The method of claim 9 , wherein the second memory locations in the buffer are released in response to reading data from the second memory locations in the buffer.

15. The method of claim 10 , wherein the size of the symmetric cube is selected to store a number of data samples substantially corresponding to a size of a largest data frame.

16. The method of claim 9 further comprising generating a backpressure enable signal to control a rate at which data is streamed to the buffer.

17. A system for generating addresses based on 3D memory for a buffer, the system comprising circuitry for:
determining a first geometric pattern for storing data in the 3D memory based on a type of computation performed using the data as input;
storing the data in the 3D memory using the determined first geometric pattern;
mapping memory locations arranged in a first geometric pattern in the 3D memory to first memory locations in the buffer;
generating memory addresses associated with the first memory locations in the buffer based on corresponding memory locations arranged in the first geometric pattern in the 3D memory;
writing data to the first memory locations in the buffer;
mapping memory locations arranged in a second geometric pattern in the 3D memory to second memory locations in the buffer;
generating memory addresses associated with the second memory locations in the buffer based on corresponding memory locations arranged in the second geometric pattern in the 3D memory; and
reading data from the second memory locations in the buffer after writing data to the first memory locations in the buffer.

18. The system of claim 17 , wherein the first memory locations in the buffer and the second memory locations in the buffer are locked.

19. The system of claim 18 , wherein the second memory locations in the buffer are released in response to reading data from the second memory locations in the buffer.

20. The system of claim 17 , wherein

Assignees

• Altera Corp

Inventors

• Xu Lei

Classifications

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title

• H04L27/263 Primary

  modification of IFFT/IDFT modulator for performance improvement · CPC title

• G06F12/06

  Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence) · CPC title

• G06F12/0623

  for memory modules · CPC title

• H04L27/2651

  Modification of fast Fourier transform [FFT] or discrete Fourier transform [DFT] demodulators for performance improvement · CPC title