Method and apparatus for addressing a vector of elements in a partitioned memory using stride, skip and span values

• US 7,100,019 B2
• Filed: 09/08/2003
• Issued: 08/29/2006
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Motorola Solutions, Inc.
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Essick, Raymond B. IV, Moat, Kent D., May, Philip E., Norris, James M., Lucas, Brian G.
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US10/657,793
• Publication Number:
  US 20040117595A1
• Time in Patent Office: 1,086 Days
• Field of Search: 712/4, 712/6, 712/7, 711/213, 711217-220
• US Class Current: 712/7
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 15/8061 Details on data memory access
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/345 of multiple operands or results addressing multiple banks G06F12/06
• CPC Class Codes: G06F 9/3455 using stride
• CPC Class Codes: G06F 9/3552 using wraparound, e.g. modulo or circular addressing
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3877 using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set

Abstract

A system and method for calculating memory addresses in a partitioned memory in a processing system having a processing unit, input and output units, a program sequencer and an external interface. An address calculator includes a set of storage elements, such as registers, and an arithmetic unit for calculating a memory address of a vector element dependent upon values stored in the storage elements and the address of a previous vector element. The storage elements hold STRIDE, SKIP and SPAN values and optionally a TYPE value, relating to the spacing between elements in the same partition, the spacing between elements in the consecutive partitions, the number of elements in a partition and the size of a vector element, respectively.

Claims

1. A system for addressing a vector of elements in a memory having a plurality of partitions, the system comprising:

a first storage element for storing a STRIDE value denoting the separation between elements of the vector of elements within each partition of the plurality of partitions;

a second storage element for storing a SKIP value related to the separation between the last element of the vector of elements in one partition of the plurality of partitions and the first element of the vector of elements in the next partition of the plurality of partitions;

a third storage element for storing a SPAN value denoting the number of elements the vector of elements within each partition of the plurality of partitions; and

an arithmetic unit coupled to the first, second and third storage elements and operable to calculate the address in the memory of a next element of the vector of elements from the address of a current element, the calculation comprising adding a multiple of the SKIP value to the address of the current element if the next element is in a different partition to the current element and adding a multiple of the STRIDE value to the address of the current element if the next element is in the same partition as the current element.

2. A system in accordance with claim 1, wherein the STRIDE and SKIP values denote a number of elements and further comprising:

a fourth storage element for storing a TYPE value denoting the size of each element of the vector of elements;

wherein the arithmetic unit is coupled to the fourth storage element and is operable to calculate the address in the memory of a next element of the vector of elements dependent upon the values stored in the first, second, third and fourth storage elements and the address of a current element.

3. A system in accordance with claim 1, wherein operation of the arithmetic unit is dependent upon an initial element address EA_START that is indicative of the address of the first element in the vector of elements.

4. A system in accordance with claim 3, wherein operation of the arithmetic unit is further dependent upon the number of elements LEFT_START in the first partition of the plurality of partitions.

5. A system in accordance with claim 2, wherein the system is operable to address a specified number of elements.

6. A system in accordance with claim 2, wherein the arithmetic unit is operable to receive a control instruction indicative of the TYPE, STRIDE, SKIP and SPAN values.

7. A system in accordance with claim 1, wherein the arithmetic unit is operable to receive a control instruction indicative of the address of the first element EA_START, the number of elements LEFT_START in the first partition of the plurality of partitions and the total number of elements TOTAL to be addressed.

8. A system in accordance with claim 1, wherein the arithmetic unit includes:

a first counter for counting a LEFT value indicative of the number of elements remaining in a current memory partition;

a second counter for counting a COUNT value indicative of the total number of elements still to be accessed.

9. A system in accordance with claim 8, wherein the arithmetic unit is operable to reset the first counter when the end of a partition is reached.

10. A system for addressing a vector of elements in a memory having a plurality of partitions, the system comprising:

a first storage element for storing a STRIDE value denoting the separation between elements of the vector of elements within each partition of the plurality of partitions;

a second storage element for storing a SKIP value related to the separation between the last element of the vector of elements in one partition of the plurality of partitions and the first element of the vector of elements in the next partition of the plurality of partitions;

a third storage element for storing a SPAN value denoting the number of elements the vector of elements within each partition of the plurality of partitions; and

an arithmetic unit coupled to the first, second and third storage elements and operable to calculate the address in the memory of a next element of the vector of elements dependent upon the values stored in the first, second and third storage elements and the address of a current element,

wherein the plurality of partitions includes first level partitions and second level partitions and the arithmetic unit includes;

a fourth storage element for storing a SKIP2 value related to the separation between the last element of the vector of elements in a first level partition and the first element of the vector of elements in a second level partition;

a fifth storage element for storing a SPAN2 value denoting the number of vectors in each second level partition;

a first counter for counting a LEFT value indicative of the number of elements remaining in a current first level memory partition;

a second counter for counting a LEFT2 value indicative of the number of elements remaining in a current second level memory partition; and

a third counter for counting a COUNT value indicative of the total number of elements still to be accessed.

11. A processing system operable to access a partitioned memory, the processing system comprising:

a processing unit having a plurality of functional elements;

an external interface;

an input unit coupled to the processing unit and the external interface and operable to retrieve a vector of elements from the memory via the external interface and pass them to the processing unit, the input unit having a set of input storage elements for storing STRIDE, SKIP and SPAN values and an input arithmetic unit operable to calculate the address in the memory of a next element of the vector of elements dependent upon the STRIDE, SKIP and SPAN values and the address of a current element;

an output unit coupled to the processing unit and the external interface and operable to retrieve a result value from the processing unit and pass it to the external interface; and

a program sequencer coupled to and operable to control the processing unit, the input unit and the output unit;

wherein the STRIDE value denotes the separation between elements of the vector of elements within each partition of the partitioned memory, the SPAN value denotes the number of elements the vector of elements within each partition of the plurality of partitions, and the SKIP value denotes the separation between the last element of the vector of elements in one partition of the partitioned memory and the first element of the vector of elements in the next partition of the partitioned memory and

wherein the input arithmetic unit is operable to calculate the address the next element of the vector of elements from the address of a current element by adding a multiple of the SKIP value to the address of the current element if the next element is in a different partition to the current element and adding a multiple of the STRIDE value to the address of the current element if the next element is in the same partition as the current element.

12. A processing system in accordance with claim 11, wherein the input unit has an additional input storage element for storing a TYPE value and wherein the input arithmetic unit is operable to calculate the address in the memory of a next element of the vector of elements from the address of a current element by adding the product of the TYPE value with the SKIP value to the address of the current element if the next element is in a different partition to the current element and adding the product of the TYPE value with the STRIDE value to the address of the current element if the next element is in the same partition as the current element.

13. A processing system in accordance with claim 11, wherein the output unit is operable to store a vector of elements received from the processing unit to the memory via the external interface, the output unit having a set of output storage elements to store TYPE, STRIDE, SKIP and SPAN values and an output arithmetic unit operable to calculate the address in the memory of a next element of the vector of elements dependent upon the TYPE, STRIDE, SKIP and SPAN values and the address of a current element.

14. A processing system in accordance with claim 11, wherein the external interface is a memory interface and further comprising a memory unit coupled to the memory interface.

15. A method for accessing a vector of elements in a memory having a plurality of partitions, comprising:

accessing the memory at an element address in a partition;

stepping a first counter; and

if a second counter indicates that at least one vector element remains in the partition;

incrementing the element address by a first amount; and

stepping the second counter;

otherwise;

incrementing the element address by a second amount; and

resetting the second counter to indicate the number of elements of the vector of elements in a partition.

16. A method in accordance with claim 15, wherein the first amount is a product of the size of an element and the number of memory elements between adjacent vector elements in a partition.

17. A method in accordance with claim 15, wherein the first amount is a difference between consecutive vector element addresses in a partition.

18. A method in accordance with claim 15, wherein the second amount is a product of the size of an element and the number of elements between last element of one partition and the first element of the next partition.

19. A method in accordance with claim 15, wherein the second amount is a difference between the last vector element address in one partition and the first vector element address in the next partition.

20. A method in accordance with claim 15, wherein the element address is initialized as the address of the first element in a partition and wherein the first counter is initialized to indicate the number of elements of the vector of elements in the first partition of the plurality of partitions, thereby allowing memory access to begin part way through the first partition.

21. A method in accordance with claim 15, wherein accessing the memory at the element address in a partition comprises reading a value of appropriate size stored at the element address.

22. A method in accordance with claim 15, wherein accessing the memory at the element address in a partition comprises storing a value of appropriate size at the element address.

23. A method in accordance with claim 15, wherein the first counter, the second counter and the element address are not re-initialized if the memory access is interrupted and resumed before all of the elements of the vector have been accessed.

24. A method in accordance with claim 15, wherein the first amount and the second amount are set to default values unless otherwise specified.

25. A method for accessing a vector of elements in a memory having a plurality of first and second level partitions, comprising:

accessing the memory at an element address in a first level and second level partition of the plurality of first and second level partitions;

stepping a first counter;

incrementing the element address by a first amount; and

if a second counter indicates that at least one vector element remains in the first level partition;

stepping the second counter;

otherwise;

incrementing the element address by a second amount;

resetting the second counter to indicate the number of elements of the vector of elements in the next first level partition; and

if a third counter indicates that at least one vector element remains in the second level partition;

stepping the third counter;

otherwise;

incrementing the element address by a third amount;

resetting the third counter to indicate the number of elements of the vector of elements in the next second level partition.