Building a wavecache

Abstract

A microarchitecture and instruction set that supports multiple, simultaneously executing threads. The approach is disclosed in regard to its applicability in connection with a recently developed microarchitecture called “WaveScalar.” WaveScalar is a compiler that breaks a control flow graph for a program into pieces called waves having instructions that are partially ordered (i.e., a wave contains no back-edges), and for which control enters at a single point. Certain aspects of the present approach are also generally applicable to executing multiple threads on a more conventional microarchitecture. In one aspect of this approach, instructions are provided that enable and disable wave-ordered memory. Additional memory access instructions bypass wave-ordered memory, exposing additional parallelism. Also, a lightweight, interthread synchronization is employed that models hardware queue locks. Finally, a simple fence instruction is used to allow applications to handle relaxed memory consistency.

1 . A method for synchronizing a plurality of threads in a dataflow processing architecture, comprising the steps of: 
 (a) providing tags to be used in identifying each individual dynamic instance of data used when executing the thread;    (b) annotating data values used in the plurality of threads, to include a specific thread identification indicating a specific thread with which each data value is associated, the thread identification being used in tokens for the instructions employed in the plurality of threads; and    (c) providing a thread coordinate instruction that executes when a data value of a first token supplied to a first input of the thread coordinate instruction matches a thread identification of a second token supplied to a second input of the thread coordinate instruction, producing an output token having a tag of the first input, and a data value from the second input.    
   
   
       2 . The method of  claim 1 , wherein the first token is produced by a first thread that provides the first token, and the second token is produced by a second thread that is different than the first thread, the thread coordinate instruction forcing the first thread to await receipt of the second token from the second thread before continuing execution of the first thread.  
   
   
       3 . The method of  claim 1 , wherein the thread coordinate instruction is used to implement a plurality of different synchronization objects used for synchronizing interactions between the plurality of threads.  
   
   
       4 . The method of  claim 3 , wherein the synchronization objects enable at least two different threads to share a common resource at different times.  
   
   
       5 . The method of  claim 1 , further comprising the step of employing the thread coordinate instruction to implement fine-grained parallelism processing by the plurality of threads, by enabling data to be passed between the plurality of threads for processing using unordered instructions.  
   
   
       6 . A method for managing memory ordering hardware to allow storing of memory addresses and memory data comprising memory operations, so that a memory address and memory data can be supplied to the memory ordering hardware at different times, comprising the steps of: 
 (a) providing a partial store structure for temporarily storing memory addresses and memory data for memory operations, where the memory addresses and the memory data for a memory operation arrive at the partial store structure at different times;    (b) if a specific memory operation inserted into the memory ordering hardware is a memory load or a memory store, and if the memory address for the memory operation is already stored in the partial store structure, transferring the specific memory operation to the partial store structure;    (c) if a specific memory operation is a memory store, but a memory datum for the specific memory operation has not yet arrived at the memory ordering hardware, and if a partial store structure does not yet exist for the memory address of the specific memory operation, providing a new partial store structure for temporarily storing the memory store until its datum arrives at the memory ordering hardware; and    (d) once both the memory datum and the memory address for the specific memory operation have been inserted into the memory ordering hardware and temporarily stored in a partial store structure, transferring the memory datum and the memory address for all memory operations in the partial store structure to another portion of a memory system.    
   
   
       7 . The method of  claim 6 , wherein if a specific memory operation is a memory load operation or a memory store operation, but there is not an available partial store structure in the memory ordering hardware, or if the partial store structure that would otherwise be used is full, recovering from an overflow condition of the partial store structure.  
   
   
       8 . The method of  claim 7 , wherein the step of recovering from the overflow condition comprises the steps of: 
 (a) discarding the specific memory operation; and    (b) one of: 
 (i) rolling back a memory operation issued register to account for discarding the specific memory operation; and  
 (ii) allowing memory operations from more than one address to occupy a partial store structure.  
   
   
   
       9 . The method of  claim 6 , wherein if the specific memory operation is a memory load operation or a memory store operation that includes both the memory address and the memory datum, further comprising the step of transferring the memory datum and the memory address for the specific memory operation directly to another portion of the memory system, without using the partial store structure.  
   
   
       10 . The method of  claim 6 , further comprising the step of initially ordering memory operations included in a process, based upon wave number tags that are assigned to identify each individual dynamic instance of data, wherein the wave number tags are assigned by dividing a control flow graph of the process into a plurality of waves.