Memory addressing techniques

• US 20050206649A1
• Filed: 12/20/2002
• Published: 09/22/2005
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Aspen Technology (Telefonaktiebolaget LM Ericsson)
• Inventors: Whitaker, Martin
• Granted Patent: US 7,750,916 B2
• Time in Patent Office: Days
• US Class Current: 345/571
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/3895 for complex operations, e.g. multidimensional or interleaved address generators, macros

Abstract

A method of generating a stream non-contiguous memory addresses representing contiguous points in logical space is described. The method comprises: generating initialising parameters describing the contiguous points in the logical space; configuring a memory address engine with the initialising parameters; performing an algorithm in the memory address engine according to the initialising parameters to produce a plurality of non-contiguous memory addresses; and collating the non-contiguous memory addresses into the stream of memory addresses for output to a data memory. The present invention has particular application to SIMD processing techniques where there are a plurality of memory address engines.

Claims

1. A method of generating a stream of non-contiguous memory addresses representing contiguous points in logical space, the method comprising:

Generating initializing parameters describing the contiguous points in the logical space;

Configuring a memory address engine with the initializing parameters;

Performing an algorithm in the memory address engine according to the initializing parameters to produce a plurality of non-contiguous memory addresses; and

Collating the non-contiguous memory addresses into the stream of memory addresses for output to a data memory;

2. The method of claim 1, wherein the generating step enables viewing of a logical plane of data taken at an angle through a volume of data.

3. The method of claim 2, wherein the generating step enables viewing of a portion of the logical plane of data.

4. The method of claim 1, wherein the performing step comprises:

calculating memory addresses progressively for each data point on a row in a logical plane of the logical space; and

repeating the above calculation for the number of rows in the logical plane.

5. The method of claim 4, wherein the generating step comprises:

generating initialization parameters relating to an initial data point in the logical plane, unit increases for each of the column and rows of the logical plane and the column and row limits for the required data in the logical plane; and

the configuring step comprises;

specifying the co-ordinates of the initial data point in the logical plane;

specifying a column vector for a unit increase in each column of the logical plane;

specifying a row vector for a unit increase in each row of the logical plane; and

specifying the column limits (ColLimitL, ColLimitH) and the row limits (RowLimitL, RowLimitH) for the required data in the logical plane.

6. The method of claim 5, wherein the step of specifying the co-ordinates of the initial data point on the logical plane is carried out using Cartesian co-ordinates (xInit, yInit, zInit).

7. The method of claim 5, wherein the steps of specifying the column vector and the row vector are carried out using Cartesian co-ordinates (ColIncr(x,y,z), RowIncr(x,y,z)).

8. The method of claim 1, further comprising outputting the collated stream of memory addresses to a memory store.

9. The method of claim 1, wherein the performing step further comprises checking whether a generated memory address is accessible to the memory address engine.

10. The method of claim 9 wherein the performing step further comprises comparing a generated memory address to that of a predetermined range of memory addresses accessible to the memory address engine.

11. The method of claim 9, wherein the performing step further comprises returning a null result if the generated memory address is not accessible to the memory address engine.

12. The method of claim 1, wherein there are a plurality of memory address engines and the configuring step further comprises configuring at least one additional memory address engine with the generated initializing parameters, and the performing step is carried out in each of the at least one additional memory address engines to produce the plurality of non-contiguous memory addresses.

13. The method of claim 12, wherein the performing step incorporates determining whether a generated memory address is accessible to a neighboring memory address engine.

14. The method of claim 12, wherein the performing step further comprises calculating a memory address on behalf of a neighboring memory address engine.

15. The method of claim 14, further comprising routing data returned from a memory store associated with a respective memory address engine as though it had been returned from a respective memory store of a neighboring memory address engine.

16. The method of claim 15, wherein the routing step further comprises excluding memory address data from being routed to the neighboring memory address engine.

17. The method of claim 15, further comprising synchronizing the data transfer of the memory address engine with that of its neighboring memory address engine.

18. A memory address engine arranged to accept initializing parameters describing contiguous points in logical space set by an external controller, the memory address engine comprising:

an address generator arranged to generate a plurality of non-contiguous memory addresses according to at least one algorithm implemented on the initializing parameters; and

collation means arranged to collate non-contiguous memory addresses into a stream of output memory addresses for output to a data memory.

19. The memory address engine of claim 18, wherein the algorithm is implemented in hardware as part of the address generator.

20. The memory address engine of claim 18, wherein the address generator comprises:

means for calculating memory addresses progressively for each data point on a row in a logical plane of the logical space; and

means for repeating the above calculation for the number of rows in the logical plane.

21. The memory address engine of claim 18, wherein the address generator is arranged to process received initialization parameters describing an initial data point in the logical plane, a column vector for a unit increase in each column of the logical plane, a row vector for a unit increase in each row of the logical plane, and the column and row limits for the required data in the logical plane.

22. The memory address engine of claim 21, wherein the address generator is arranged to process at least some initialization parameters specified in Cartesian co-ordinates.

23. The memory address engine of claim 18, further comprising access means for determining whether a generated memory address is accessible to the memory address engine.

24. The memory address engine of claim 23, wherein the access means is arranged to compare a generated memory address to that of a predetermined range of memory addresses accessible to the memory address engine.

25. The memory address engine of claim 23, wherein the access means is arranged to return a null result if the generated memory address is not accessible to the memory address engine.

26. The memory address engine of claim 23, wherein the access means is arranged determine whether a generated memory address is accessible to a neighboring memory address engine.

27. The memory address engine of claim 26, wherein the access means is arranged to calculate a memory address on behalf of a neighboring memory address engine.

28. The memory address engine of claim 18, wherein the address generator comprises an associative processor.

29. The memory address engine of claim 18, wherein the address generator comprises an array of associative processors.

30. The memory address engine of claim 28, wherein the associative processor(s) comprise one or more associative string processors.

33. The memory address network of claim 31, wherein the at least first and second memory address engines comprise a memory address engine according to claim 18

31. A memory address processing system comprising:

at least a first and a second memory address engine;

a first and a second primary data stores associated with the respective memory address engines;

a first and a second secondary data store associated with the respective memory address engines;

a databus connecting each memory address engine with its associated primary and secondary data stores; and

a data router associated with each memory address engine, the data router associated with the first memory address engine being arranged to route data from the first secondary data store of the first memory address engine to a second primary data store of the second memory address engine upon instruction.

32. The memory address network of claim 31, wherein the instruction for the data router associated with the first memory address engine is sent from the first memory address engine.

34. A router for use with a memory address processing system comprising a plurality of memory address engines, the router being arranged upon instruction from a first memory address engine to direct data from a memory store associated to the first memory address engine to a memory store associated to a second memory address engine.

35. The router of claim 34, wherein the first and second memory addressing engines are logically connected together as neighboring memory addressing engines.

36. A router as claimed in claim 34, wherein only memory data from the memory store associated with the first memory engine is directed to the memory store associated to a second memory address engine.