Memory access consolidation for SIMD processing elements having access indicators

• US 7,363,472 B2
• Filed: 10/09/2001
• Issued: 04/22/2008
• Est. Priority Date: 04/09/1999
• Status: Expired due to Fees

• Current Assignee: Rambus Inc.
• Original Assignee: ClearSpeed Technology Ltd. (ZF Acquisitions Ltd.)
• Inventors: David, Russell, Atkin, Phil, Day, Tim, Williams, Dave, McConnell, Ray, Rhoades, John, Cameron, Ken, Winser, Paul, Faulds, Gordon, Greer, Trey, Stuttard, Dave, O'Dea, Eamon
• Primary Examiner(s): Huisman; David J
• Application Number:
  US09/972,797
• Publication Number:
  US 20020174318A1
• Time in Patent Office: 2,387 Days
• Field of Search: 712/4, 712/5, 712/10, 712/14, 712/16, 712/22, 712/225, 711/154, 711/150
• US Class Current: 712/225
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses
• CPC Class Codes: G06F 9/3001 Arithmetic instructions
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/30101 Special purpose registers
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/3888 controlled by a single instruction for multiple threads [SIMT] in parallel
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

A data processing apparatus includes a SIMD (Single Instruction Multiple Data) array (10) of processing elements. The processing elements are operably divided into a plurality of processing blocks, the processing blocks being operable to process respective groups of data items.

Claims

1. A method of retrieving a data item from a memory unit in a data processing apparatus comprising a SIMD (single instruction multiple data) array of processing elements, wherein the processing elements are operably divided into a plurality of processing blocks, the processing blocks being operable to process respective groups of data items and wherein the data processing apparatus includes said memory unit in which data items are stored at addresses therein, and to which the plurality of processing elements have access, the method comprising:

for each processing element in the array which requires access to the memory unit, setting an access indicator to indicate that the processing element concerned requires access to the memory unit, and storing a target address of the memory unit to which such access is required;

selecting one of the processing elements having the access indicator set, and retrieving the stored target address from that selected processing element;

transmitting the retrieved target address and transaction identification information to the processing elements in the array;

for each processing element having the access indicator set, comparing the transmitted target address with the stored target address, and it the stored and transmitted target addresses are equivalent, clearing the access indicator and storing the transaction identification information;

retrieving at least one data item stored at the transmitted target address in the memory unit;

transmitting the at least one retrieved data item and associated transaction identification information to the processing elements in the array; and

for each processing element having stored transaction identification information, comparing the stored transaction identification information with the transmitted transaction identification information, and if the stored transaction information is equivalent to the transmitted transaction information, receiving the or each retrieved data item.

2. A method of writing data items to a memory unit in a data processing apparatus comprising a SIMD (single instruction multiple data) array of processing elements, wherein the processing elements are operably divided into a plurality of processing blocks, the processing blocks being operable to process respective groups of data items, and wherein the data processing apparatus includes the memory unit in which data items are stored at addresses therein, and to which the plurality of processing elements have access the method comprising:

for each processing element in the array which requires access to the memory unit, setting an access indicator to indicate that the processing element concerned requires access to the memory unit, and storing a target address of the memory unit to which such access is required;

selecting one of the processing elements having the access indicator set, and retrieving the stored target address from that selected processing element;

transmitting the retrieved target address and transaction identification information to all the processing elements in the array;

for each processing element having the access indicator set, comparing the transmitted target address with the stored target address, and if the stored and transmitted target addresses are equivalent, clearing the access indicator and storing the transaction identification information;

transmitting transaction identification information to the processing elements in the array;

for each processing element having stored transaction identification information, comparing the stored transaction identification information with the transmitted transaction identification information, and if the stored transaction information is equivalent to the transmitted transaction information, transmitting at least one data item to be stored in the memory unit at the target address; and

storing the at least one transmitted data item at the target address in the memory unit.

3. A method as claimed in claim 2, wherein processing elements store data items at respective regions of the target memory address.

4. In a data processing apparatus, a method of retrieving a data item from a memory unit in which data items are stored at addresses therein, said data processing apparatus further comprising an array of a plurality of processing elements which have access to the memory unit, the method comprising:

for each processing element in the array which requires access to the memory unit, setting an access indicator to indicate that the processing element concerned requires access to the memory unit, and storing a target address of the memory unit to which such access is required;

selecting one of the processing elements having the access indicator set, and retrieving the stored target address from that selected processing element;

transmitting the retrieved target address and transaction identification information to the processing elements in the array;

for each processing element having the access indicator set, comparing the transmitted target address with the stored target address, and if the stored and transmitted target addresses are equivalent, clearing the access indicator and storing the transaction, identification information;

retrieving at least one data item stored at the transmitted target address in the memory unit;

transmitting the at least one retrieved data item and associated transaction identification information to the processing elements in the array; and

for each processing element having stored transaction identification information, comparing the stored transaction identification information with the transmitted transaction identification information, and if the stored transaction information is equivalent to the transmitted transaction information, receiving the at least one retrieved data item.

5. A method as claimed in claim 4, wherein retrieved data is returned in the order in which the transaction identification information is produced.

6. A method as claimed in claim 4, wherein the retrieved data is returned in the order in which it is retrieved from the memory.

7. A method of writing data items to a memory unit in a data processing apparatus including the memory unit in which data items are stored at addresses therein, and an array of a plurality of processing elements which have access to the memory unit, the method comprising:

for each processing element in the array which requires access to the memory unit, setting an access indicator to indicate that the processing element concerned requires access to the memory unit, and storing a target address of the memory unit to which such access is required;

selecting one of the processing elements having the access indicator set, and retrieving the stored target address from that selected processing element;

transmitting the retrieved target address and transaction identification information to all the processing elements in the array;

for each processing element having the access indicator set, comparing the transmitted target address with the stored target address, and if the stored and transmitted target addresses are equivalent, clearing the access indicator and storing the transaction identification information;

transmitting transaction identification information to the processing elements in the array;

for each processing element having stored transaction identification information, comparing the stored transaction identification information with the transmitted transaction identification information, and if the stored transaction information is equivalent to the transmitted transaction information, transmitting at least one data item to be stored in the memory unit at the target address; and

storing the at least one transmitted data item at the, target address in the memory unit.

8. A method as claimed in claim 7, wherein processing elements store data items at respective regions of the target memory address.

9. A data processing apparatus comprising a SIMD (single instruction multiple data) array of processing elements, data storage means for storing data items for access by the processing elements, and control means for controlling access to the storage means in accordance with a method as claimed in claim 8.