Parallel memories for multidimensional data access

Patent metadata

Field	Value
Publication number	US-9760770-B2
Application number	US-201313918892-A
Country	US
Kind code	B2
Filing date	Jun 14, 2013
Priority date	Apr 15, 2013
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

The subject disclosure is directed towards loading parallel memories (e.g., in one or more FPGAs) with multidimensional data in an interleaved manner such that a multidimensional patch/window may be filled with corresponding data in a single parallel read of the memories. Depending on the position of the patch, the data may be rotated horizontally and/or vertically, for example, so that the data in each patch is consistently arranged in the patch regardless of from which memory each piece of data was read. Also described is leveraging dual ported memory for multiple line reads and/or loading one part of a buffer while reading from another.

First claim

What is claimed is:

1. A method comprising:
receiving a request to process multidimensional data of an image;
based on the request, identifying a window to apply to the image, the window comprising a first dimension having a first length and a second dimension having a second length;
determining a subset of a plurality of memories to distribute the multidimensional data of the image among, the determining comprising multiplying the first length of the first dimension of the window by the second length of the second dimension of the window, wherein a number of memories in the subset of the plurality of memories is equal to a product of multiplying the first length by the second length;
loading, in an interleaved manner, the multidimensional data into the subset of the plurality of memories;
upon loading the multidimensional data, executing a parallel read of the subset of the plurality of memories;
filling a data window with the multidimensional data based on the parallel read of the subset of the plurality of memories; and
processing the multidimensional data in the data window.

2. The method of claim 1 wherein loading the multidimensional data among the subset of the plurality of memories comprises loading a part of the multidimensional data into a buffer comprising the subset of the plurality of memories.

3. The method of claim 1 wherein loading the multidimensional data comprises writing data corresponding to a first dimension of the multidimensional data to alternate memories in the subset of the plurality of memories corresponding to the first dimension of the window.

4. The method of claim 1 wherein loading the multidimensional data comprises writing data corresponding to a first dimension of the multidimensional data to alternate memories in the subset of the plurality of memories corresponding to the second dimension of the window.

5. The method of claim 1 further comprising accessing a memory of the subset of the plurality of memories based upon a section in the subset of the plurality of memories corresponding to a position of the multidimensional data in the window.

6. The method of claim 1 wherein the subset of the plurality of memories comprise dual ported memories, and wherein reading the subset of the plurality of memories comprises reading data from two addresses in a single cycle.

7. The method of claim 1 wherein the subset of the plurality of memories comprise dual ported memories, and wherein the method further comprises writing to a memory address of a memory of the subset of the plurality of memories while reading from a different or same memory address of the memory.

8. The method of claim 1 further comprising:
to ensure that outputs of the subset of memories are returned in a consistent manner, upon determining that a particular pixel in the data window is not in a predefined location, rotating pixels in the data window one or more times in a horizontal rotation until the particular pixel in the data window is in the predefined location; and
returning the data window to an original orientation after any rotating of the pixels.

9. The method of claim 1 further comprising:
to ensure that outputs of the subset of memories are returned in a consistent manner, upon determining that a particular pixel in the data window is not in a predefined location, rotating pixels in the data window one or more times in a vertical rotation until the particular pixel in the data window is in the predefined location; and
returning the data window to an original orientation after any rotating of the pixels.

10. The method of claim 1 further comprising:
to ensure that outputs of the subset of memories are returned in a consistent manner, upon determining that a particular pixel in the data window is not in a predefined location, rotating pixels in the data window one or more times in a horizontal rotation and at least once in a vertical rotation until the particular pixel in the data window location; and
returning the data window to an original orientation after any rotating of the pixels.

11. A system comprising:
a plurality of memories; and
a processor programmed to:
receive a request to process multidimensional data of an image;
based on the request, identify a window to apply to the image, the window comprising a first dimension having a first length and a second dimension having a second length;
determine a number of the plurality of memories to distribute the multidimensional data among, the determining comprising multiplying a first length of the first dimension of the window by the second length of the second dimension of the window, wherein the number of the memories is equal to a product of multiplying the first length by the second length;
load the number of memories with the multidimensional data of the image data from a multidimensional array in an interleaved manner;
executing a parallel read of the loaded number of memories;
filling a data window with the multidimensional data based on the parallel read of the number of memories; and
processing the multidimensional data in the data window.

12. The system of claim 11 wherein the number of memories are one of the following: contained in a single field programmable gate array, or distributed among a plurality of field programmable gate arrays.

13. The system of claim 11 further comprising a fetching process configured to fill a particular window at a given position relative to the multidimensional array with image data read from the number of memories in parallel.

14. The system of claim 13 further comprising an array processing component configured to receive the particular window filled by the fetching process.

15. The system of claim 13 wherein the fetching process is configured to ensure that outputs of the number of memories are returned in a consistent manner by:
determining that a particular pixel in the particular window is not in a predefined location; and
rotating pixels read from the number of memories along the dimensions of the particular window until the particular pixel is in the predefined location when providing the outputs.

16. The system of claim 15 further comprising an array processing component configured to receive the data after rotation by the fetching process.

17. The system of claim 11 wherein the processor is further programmed to load a part of the multidimensional array data into a buffer comprising the number of memories.

18. The system of claim 11 wherein the multidimensional array data comprises at least one set of image data.

19. One or more computer-readable storage media having executable instructions, which perform operations comprising:
receiving a request to process multidimensional data of an image;
based on the request, identifying a window to apply to the image, the window comprising a first dimension having a first length and a second dimension having a second length;
determining addresses in a plurality of memories to store the multidimensional data based upon a position of the window from which the multidimensional data is obtained, the window comprising image data corresponding to pixels in the image;
loading, in an interleaved manner, the multidimensional data into the plurality of memories;
filling a data window with the multidimensional data corresponding to the data window by executing a single parallel read of the plurality of memories; and
processing the multidimensional data corresponding to the filled data window.

20. The one or more computer-readab

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Eguro Kenneth Hiroshi
• Bittner Jr Ray A
• Smith George E
• Swilley Shawn Michael
• Ahmed Rehan

Classifications

• G06F2218/12

  Classification; Matching · CPC title

• H04N25/611

  Correction of chromatic aberration · CPC title

• H04N23/56

  provided with illuminating means · CPC title

• H04N23/11

  for generating image signals from visible and infrared light wavelengths · CPC title

• H04N13/254

  in combination with electromagnetic radiation sources for illuminating objects · CPC title