Buffer Fusion and Layout Optimization

Abstract

Buffer assignment in a contiguous area in a coarse-grained reconfigurable (CGR) array is optimized by temporarily assigning a first buffer portion and a second buffer portion to first and second physical memory units, routing connections in the contiguous area, and calculating a first cost. A list of candidates for a third physical memory unit is created, and a best cost and a best candidate are initialized. For each candidate, the first and second buffer are reassigned to the candidate, connections for data and dataflow control information in the contiguous area are routed, and a second cost is calculated. If the second cost is better than the best cost, the best cost and the best candidate are updated.

We claim: 
     
         1 . A computer-implemented method for optimizing buffer allocation within a contiguous area in an array of reconfigurable units including at least a first physical memory unit and a second physical memory unit, the method comprising:
 temporarily assigning a first buffer portion comprising at least a part of a first buffer to the first physical memory unit and a second buffer portion comprising at least a part of a second buffer to the second physical memory unit;   temporarily routing connections between the first physical memory unit, the second physical memory unit, and previously mapped reconfigurable units within the contiguous area;   using a cost function to calculate a first cost related to assigning the first buffer portion and the second buffer portion to the first physical memory unit and the second physical memory unit;   determining one or more candidate third physical memory units within the contiguous area, wherein the size of each candidate third physical memory unit is larger than the size of the first buffer portion plus the size of the second buffer portion;   initializing a best cost and initializing a best candidate physical memory unit;   for each candidate third physical memory unit:
 temporarily reassigning the first buffer portion and the second buffer portion to the candidate third physical memory unit, temporarily routing connections between the candidate third physical memory unit and previously mapped reconfigurable units within the contiguous area, and using the cost function to calculate a second cost related to assigning the first buffer portion and the second buffer portion to the candidate third physical memory unit; 
 determining if the second cost is better than the best cost; 
 updating, in response to determining that the second cost is better than the best cost, the best cost to equal the second cost, and the best candidate physical memory unit to equal the candidate third physical memory unit; and 
   creating a configuration file that assigns both the first buffer portion and the second buffer portion to the best candidate physical memory unit and storing the configuration file in a non-transitory computer readable storage medium.   
     
     
         2 . The computer-implemented method of  claim 1 , wherein:
 the array of reconfigurable units is an array of coarse-grained reconfigurable (CGR) units.   
     
     
         3 . The computer-implemented method of  claim 1 , wherein:
 the candidate third physical memory units include the first physical memory unit and/or the second physical memory unit.   
     
     
         4 . The computer-implemented method of  claim 1 , wherein:
 determining if the second cost is better than the best cost comprises determining if the second cost is less than the best cost.   
     
     
         5 . The computer-implemented method of  claim 1 , wherein:
 parameters for the cost function include at least one of:
 a weight of an edge connected to a buffer node, 
 a bandwidth of an edge connected to a buffer node, 
 a traffic density of an available routing channel between a physical memory unit and a neighbor, 
 a traffic latency in an available routing channel between a physical memory unit and a neighbor, 
 a semiconductor die area usage, or 
 an energy usage. 
   
     
     
         6 . The computer-implemented method of  claim 1 , wherein:
 the array of reconfigurable units is included in a CGR architecture (CGRA) processor;   a reconfigurable unit comprises a physical memory unit;   a physical memory unit is a pattern memory unit (PMU); and   the best cost is initialized to equal the first cost.   
     
     
         7 . A non-transitory computer readable storage medium storing computer program instructions to optimize buffer allocation in a contiguous area of an array of reconfigurable units including at least a first physical memory unit and a second physical memory unit, wherein the computer program instructions, when executed on a processor, implement a method comprising:
 temporarily assigning a first buffer portion comprising at least a part of a first buffer to the first physical memory unit and a second buffer portion comprising at least a part of a second buffer to the second physical memory unit;   temporarily routing connections between the first physical memory unit, the second physical memory unit, and previously mapped reconfigurable units within the contiguous area;   using a cost function to calculate a first cost related to assigning the first buffer portion and the second buffer portion to the first physical memory unit and the second physical memory unit;   determining one or more candidate third physical memory units within the contiguous area, wherein the size of each candidate third physical memory unit is larger than the size of the first buffer portion plus the size of the second buffer portion;   initializing a best cost and initializing a best candidate physical memory unit;   for each candidate third physical memory unit:
 temporarily reassigning the first buffer portion and the second buffer portion to the candidate third physical memory unit, temporarily routing connections between the candidate third physical memory unit and previously mapped reconfigurable units within the contiguous area, and using the cost function to calculate a second cost related to assigning the first buffer portion and the second buffer portion to the candidate third physical memory unit; 
 determining if the second cost is better than the best cost; 
 updating, in response to determining that the second cost is better than the best cost, the best cost to equal the second cost, and the best candidate physical memory unit to equal the candidate third physical memory unit; and 
 assigning both the first buffer portion and the second buffer portion to the best candidate physical memory unit. 
   
     
     
         8 . The non-transitory computer readable storage medium of  claim 7 , wherein the array of reconfigurable units is an array of coarse-grained reconfigurable (CGR) units. 
     
     
         9 . A system including one or more processors coupled to a memory, the memory loaded with computer program instructions to optimize buffer allocation in a contiguous area of an array of reconfigurable units including at least a first physical memory unit and a second physical memory unit, wherein the computer program instructions, when executed on the one or more processors, implement actions comprising:
 temporarily assigning a first buffer portion comprising at least a part of a first buffer to the first physical memory unit and a second buffer portion comprising at least a part of a second buffer to the second physical memory unit;   temporarily routing connections between the first physical memory unit, the second physical memory unit, and previously mapped reconfigurable units within the contiguous area;   using a cost function to calculate a first cost related to assigning the first buffer portion and the second buffer portion to the first physical memory unit and the second physical memory unit;   determining one or more candidate third physical memory units within the contiguous area, wherein the size of each candidate third physical memory unit is larger than the size of the first buffer portion plus the size of the second buffer portion;   initializing a best cost and initializing a best candidate physical memory unit;   for each candidate third physical memory unit:
 temporarily reassigning the first buffer portion and the second buffer portion to the candidate third physical memory unit, temporarily routing connections between the candidate third physical memory unit and previously mapped reconfigurable units within the contiguous area, and using the cost function to calculate a second cost related to assigning the first buffer portion and the second buffer portion to the candidate third physical memory unit; 
 determining if the second cost is better than the best cost; 
 updating, in response to determining that the second cost is better than the best cost, the best cost to equal the second cost, and the best candidate physical memory unit to equal the candidate third physical memory unit; and 
 assigning both the first buffer portion and the second buffer portion to the best candidate physical memory unit. 
   
     
     
         10 . The system of  claim 9 , wherein the array of reconfigurable units is an array of coarse-grained reconfigurable (CGR) units.