Abstract:
Data is allocated into multiple memories with selective variable replication for maximizing performance by minimizing concurrent memory access conflicts. Requirements for concurrent access are summarized in a transformed concurrent access graph. Graph vertices are merged to disallow variable replication. All potential graph merges that cause a reduction in machine cycle time are identified. The ratios of saved cycles/memory cost in bytes are then computed for each potential merge. The potential merges are then sorted by their saved cycles/bytes ratio. Finally, potential merges resulting in replicated variables are selected based on their cycles/bytes ratios until a predefined memory target size is achieved. Either graph coloring or clique partitioning can be used to allocate variables into memory banks.

Description:
FIELD OF THE INVENTION 
     The present invention generally relates to compilers, and more specifically to allocating data over multiple memories for concurrent memory accesses. 
     BACKGROUND OF THE INVENTION 
     Programmable digital signal processors (DSPs) often use multiple data memory banks to facilitate the exploitation of parallelism in accessing operands from memory. To utilize this capability, however, the data must be properly partitioned and distributed among different memory banks. 
     To illustrate the importance of data partitioning on execution performance, consider an N th  order FIR (finite impulse response) filter algorithm executed by a hypothetical DSP similar to the Motorola DSP560001. This hypothetical DSP has two data-memory banks that can each be accessed once every clock cycle. But to fetch the elements of arrays A (the data) and B (the filter coefficients) in parallel, the arrays must be stored in separate memory banks. Conversely, if the arrays are stored in the same memory bank, the elements of the arrays would have to be fetched sequentially, and the execution of the code would be slowed down. The ability to access multiple memory banks in parallel with other operations is fundamental to most DSPs. However, failure to properly distribute the data among the memory banks can limit the exploitation of such parallelism and can therefore degrade execution performance. 
     Data partitioning is currently performed manually by the programmer, who must typically resort to the use of assembler directives or compiler pragmas to control the partitioning of data in a program. As programs become larger and more sophisticated, it becomes very difficult to partition data manually and to ensure that the partitioning results in optimal execution performance. Automatic data partitioning is therefore becoming a necessity, especially with the current trend towards a heavier reliance on high-level languages to program DSPs. Automatic data partitioning relieves the programmer from this task and helps improve performance across an entire program. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features and advantages of the present invention will be more clearly understood from the following detailed description taken in conjunction with the accompanying FIGS. where like numerals refer to like and corresponding parts and in which: 
     FIG. 1 is a block diagram of a Digital Signal Processor (DSP) with dual memory banks; 
     FIG. 2 is an example program that uses multiple concurrent data accesses; 
     FIG. 3 is a graph that illustrates the concurrent access relationships in the example program shown in FIG. 2; 
     FIG. 4 is a block diagram that illustrates allocation of array variables into dual memory banks with replication of one of the variables; 
     FIG. 5 is a block diagram of a example program for illustrating a concurrent access graph; 
     FIG. 6 is a concurrent access graph for the example program shown in FIG. 5; 
     FIG. 7 is a flowchart illustrating construction of a concurrent access graph; 
     FIG. 8 is an example program and its associated concurrent access graph illustrating a problem with a variable use reached by two definitions; 
     FIG. 9 is an example program and its associated concurrent access graph illustrating a problem with a variable definition reaching two uses of that variable; 
     FIG. 10 is a sample concurrent access graph; 
     FIG. 11 is a line graph of the sample concurrent access graph shown in FIG. 10; 
     FIG. 12 is a concurrent access graph in which a single variable definition reaches two uses of that single variable; 
     FIG. 13 is a line graph the concurrent access graph shown in FIG. 12 altered by removal of an edge; 
     FIG. 14 is a flow chart illustrating a method of cost based merging vertices of a line graph; 
     FIG. 15 is a flow chart illustrating a method of cost based merging vertices of a line graph subject to a maximum memory size constraint; 
     FIG. 16 is a flow chart illustrating a method of finding a list of merges that cause cycle time reduction as referenced in FIGS. 14 and 15; and 
     FIG. 17 is a block diagram illustrating a General Purpose Computer. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 is a block diagram of a Digital Signal Processor (DSP) with dual memory banks. The DSP 100 contains a central processing unit (CPU) 101 coupled to program memory 102 that supplies instructions to the CPU 101, and two data memory banks 103, 104. Digital Signal Processors (DSPs) 100 commonly use dual data memory banks to double the memory system&#39;s bandwidth. This increases effective memory bandwidth by allowing multiple simultaneous accesses to distinct memory banks. Programmers must assign concurrently-accessed global variables and arrays to different memory banks to achieve performance. Making effective use of dual memory banks is a difficult task, especially for high level language compilers. 
     This invention presents a method to perform that task automatically. This method allocates data into multiple memory banks such that concurrent access can be made. This method also automatically selects variables for duplication, enhancing concurrent access opportunities with minimal impact on cost. 
     Replication is a technique to enhance concurrent access opportunities. Suppose arrays A and B are concurrently accessed in one instruction, array B and C are accessed concurrently in a second instruction and arrays A and C are accessed concurrently in a third instruction. In order to satisfy all three concurrent-access requirements, three memory banks are necessary. However, if one has duplicate copies of one of the arrays, e.g., array A, then all three array accesses may be performed. However, duplication must be made carefully to avoid excessive memory size costs and to avoid overheads for maintaining coherence between multiple copies of the array. 
     FIGS. 2, 3 and 4 illustrate this example. FIG. 2 is an example program that uses multiple concurrent data accesses. FIG. 3 is a graph that illustrates the concurrent access relationships in the example program shown in FIG. 2. FIG. 4 is a block diagram that illustrates allocation of array variables into dual memory banks with replication of one of the variables. In FIG. 4, copies of variable A (A 1  and A 2 ) are stored in both memory banks 401, 402. 
     The algorithm allocates variables into one of the memory banks. Because memory banks are single-ported, variables that are accessed concurrently, either for reading or writing, by some instruction cannot be allocated in the same memory bank. The requirements for concurrent memory access are generated by the compiler assuming multi-ported memory banks. The goal of the algorithm is to satisfy those access requirements. In case conflict-free allocation is not possible, even after replication, the schedule is altered to perform the memory accesses sequentially instead of concurrently, thus impacting performance. 
     An instruction &#34;x:=y+z&#34; is a definition of variable &#34;x&#34; and a use of variables &#34;y&#34; and &#34;z.&#34; If there is a possible execution path in the program such that the value of variable &#34;x&#34; defined at instruction M1 may be used as an operand for some operation in instruction M2 the definition of &#34;x&#34; in M1 is said to reach M2. 
     FIG. 5 is a block diagram of a example program for illustrating a concurrent access graph. This is a graph that captures all the relationships of concurrent access of the variables in the program. FIG. 6 is a concurrent access graph for the example program shown in FIG. 5. FIG. 5 illustrates definitions and uses. Instruction 1 (501) defines a value for variable a that reaches Instruction 2 (502). In the concurrent access graph (500) this is indicated by an edge labeled &#34;a&#34; between nodes labeled 1 and 2. Similarly, Instruction 1 (501) also defines a value for variable &#34;b&#34; that reaches Instruction 3 (503). Again, in the concurrent access graph (FIG. 6) this is indicated by an edge labeled &#34;b&#34; between nodes labeled 1 and 3. 
     The example of FIG. 5 indicates a situation where replication is needed to ensure concurrent access. It this example, one notices that replication of variable &#34;c&#34; would allow for the required concurrent accesses. In this example, extra memory positions (to store the two copies of variable &#34;c&#34;) are used to avoid lengthening the schedule and performing the memory accesses sequentially. 
     The key idea is to operate on a concurrent access graph that represents concurrent-access constraints. A graph-coloring algorithm is applied to the modified graph (This is similar to the graph-coloring representation of access constraints used in optimizing compilers). 
     A graph G(V,E) having a set of vertices V corresponding to the instructions in the program and edges E between those instructions is constructed. For each &#34;store&#34; of a variable X (array or global variable) in the program, we construct edges labeled X between the instruction containing the STORE and all instructions that contain LOADs of X reached by the STORE. (In compiler terminology, we add an edge between each DEFINITION of variable X and all possible USEs of X). 
     Graph G summarizes the requirements for concurrent access: whenever two edges with distinct labels (variable names) share a vertex, it indicates that the corresponding variables must be allocated into different memory banks to allow concurrent access. 
     A concurrent access graph G (FIG. 6) is constructed having a vertex for each instruction Mi in the program. If there is a possible execution path in the program such that variable &#34;v&#34; defined at instruction M1 is used as an operand for some operation in instruction M2, Graph G has an edge labeled &#34;v&#34; between vertex M1 and vertex M2. 
     The relationship of concurrent-access to variables in memory banks is captured in Graph G by edges that share vertices: if variables &#34;x&#34; and &#34;y&#34; are concurrently accessed by some instruction M, then Graph G has two edges labeled &#34;x&#34; and &#34;y&#34; emanating from the vertex labeled M. 
     To construct graph G, &#34;reaching definitions&#34; flow analysis is performed (FIG. 7). A definition of variable &#34;v&#34; in instruction M that reaches instruction N creates in Graph G an edge labeled &#34;v&#34; between the vertex labeled N and the vertex labeled M. 
     Because graph G summarizes the requirements for concurrent access, it seems that applying edge coloring to graph G could be used to assign variables into memory banks. However, the edge-coloring method has two important drawbacks shown below. 
     Edge coloring of a graph is an assignment of colors to the edges in the graph such that no two edges which have a common vertex are assigned the same color. Each color corresponds to a memory bank. If two variables &#34;X&#34; and &#34;Y&#34; share a vertex in graph G, they are assigned distinct colors and thus located in distinct memory banks. Thus, variables that are concurrently LOADed or STOREd in the same instruction receive different colors by an edge coloring algorithm. Therefore, an allocation created via edge-coloring satisfies the single-ported memory bank constraints, allowing concurrent access from multiple single-ported memory banks as required by the program, provided that the number of colors used is less than or equal to the number of memory banks. If there are more colors than memory banks, this means that the concurrent access requirements cannot be satisfied and the program schedule must be changed by performing some of the accesses sequentially. 
     However, naive application of edge coloring, as described, creates a problem. FIG. 9 is an example program and its associated concurrent access graph illustrating a problem with a variable definition reaching two uses of that variable. Suppose a STORE in instruction &#34;I&#34; 92 reaches two LOADs in instructions &#34;J&#34; 94 and &#34;K&#34; 96, respectively. According to the above, the two corresponding edges would be allocated distinct colors, thus implying in un-necessary replication of the variable. 
     A similar problem happens when a use of a variable is reached by multiple definitions. FIG. 8 is an example program and its associated concurrent access graph illustrating a problem with a variable use reached by two definitions. There would be an edge from each definition to the use, and each edge would be assigned distinct colors thus generating unnecessary copies. This makes simple edge-coloring method as presented above only applicable for the case of straight line programs. For example, assume that distinct branches of an if-then-else statement assign new values to variable a and the variable is later used at the rejoin. In FIG. 8, the &#34;then&#34; side (Instruction labeled I 82) creates a value for &#34;A&#34; and the &#34;else&#34; since (Instruction labeled J 84) creates a different value. In the simple edge-coloring method, each pair {definition, use} of &#34;A&#34; generates an edge in Graph G. Because the edges share the vertex labeled I 82, the corresponding variables are allocated into two distinct memory banks. Consequently, the definition of &#34;A&#34; in Instruction I 82 is stored in one memory bank, and the definition of &#34;A&#34; in Instruction J 84 side is written into another memory bank. When program execution reaches the use of &#34;A&#34; at the rejoin point (Instruction K 86) it is not known which memory bank holds the proper value of variable &#34;A&#34;, since it depends on past history of the execution of the program. 
     To solve these problems, we operate on the LINE GRAPH of G. FIG. 10 is an example concurrent access graph G. FIG. 11 is a line graph L(G) of the example concurrent access graph G shown in FIG. 10. The line graph L(G) of a graph G is a graph which has a vertex corresponding to each edge of G. Vertices of L(G) are connected if and only if the corresponding edges of G share a vertex. Vertex-coloring of L(G) corresponds to Edge-coloring of G. (Vertex coloring of a graph G is an assignment of colors to vertices such that no adjacent vertices receive the same color). As before, note that different colors correspond to different memories. Before Vertex Coloring is applied, L(G) is transformed in two ways: 
     1. Edges between vertices corresponding to a definition of a variable reaching multiple uses are removed. FIG. 12 is a concurrent access graph G&#39; in which a single variable definition reaches two uses of that single variable. FIG. 13 is a line graph L(G&#39;) of the concurrent access graph shown in FIG. 12 altered by removal of an edge. This edge removal allows the possibility of all uses of the definition receiving the same color (which implies the variable is stored in one memory bank). However, it is still possible to have distinct colors for each use, which means that the variable might be duplicated, if necessary, to allow concurrent access; and 
     2. Edges between vertices corresponding to multiple definitions of a variable reaching one use are removed. 
     Note that, after steps (1) and (2) above, L(G&#39;) is 2-colorable. 
     The Method proceeds by merging those vertices in L(G&#39;) that correspond to the same variable. It works in two kinds of vertices: 
     1. merging vertices corresponding to multiple definitions of a variable that reach the same use (those are edges previously removed in step 1 above); and 
     2. merging vertices labeled with the same variable name. 
     The merge is performed as long as 2-colorability is maintained. 
     Avoiding a merge may imply duplicating that variable, if distinct edges labeled with that variable name receive different colors, i.e., are assigned to different memory banks. 
     The cost of a potential merge has two components: cycle cost and bytes. &#34;Cycle cost&#34; refers to program schedule impact of a potential merge. If a variable is replicated, all definitions (STOREs) of that variable must write to all copies of the variable in the memory banks. This may take multiple cycles if the memory ports are otherwise occupied. Similarly, the &#34;bytes&#34; component of the cost refers to the extra memory space required to store the variable in case it is replicated. For dual memory systems, the cycle cost of a merge is defined as -1 if all definitions of the variable are found in instructions that have N-1 other memory accesses, where N is the number of memory accesses that can be made concurrently. For dual memory systems, this means that all stores to the variable are one of a possible two memory accesses in the instruction. In that case, the merge will save one cycle in the execution of the program because, if the variable were replicated, one extra cycle for another memory access would be necessary. Similarly, the cost of a merge is +1 for all other cases. Also, the cost of a merge may be set to infinite if the resulting graph after that merge is no longer 2-colorable, for two memory banks, or N-colorable for N memory banks. 
     FIG. 14 is a flow chart illustrating a method of cost based merging vertices of a line graph. The method starts by finding minimum cost cycles for L(G&#39;), step 140. These are all the merges that cause a cycle time reduction. Finally, all merges that have a negative cycle cost are performed, step 142. 
     FIG. 15 is a flowchart illustrating a method of cost based merging vertices of a line graph subject to a maximum memory size constraint. The method starts by finding minimum cost cycles for L(G&#39;), step 140. These are all the merges that cause a cycle time reduction. Then, a cycles/bytes ratio is computed for each potential merge, step 152. The potential merges are then sorted by their cycles/bytes ratios, step 154. A &#34;while&#34; loop is then entered that starts by testing whether a memory threshold has been exceeded, step 156. As long as the memory threshold is not being exceeded, step 156, the potential merge with the smallest cycles/bytes ratio is removed, step 158, and the loop repeats starting with the test at step 156. Otherwise, the method is complete. 
     FIG. 16 is a flow chart illustrating a method of finding a list of merges that cause cycle time reduction as referenced in box 140 of FIG. 14 and box 150 of FIG. 15. A &#34;while&#34; loop is entered and a check is made for more potential merges, step 160. As long as there are more potential merges, step 160, the loop is executed the next potential merge. Memory and cycle costs are computed for the current potential merge, step 162. Then, a test is made whether the cycle cost is negative, step 164. If the cycle cost is negative, step 164, indicating a potentially beneficial program speedup, the potential merge is added to a list of potential merges, step 166. In either case, regardless of whether the cycle cost is negative, step 164, the loop repeats, starting with the test for more potential merges, step 160. When no more potential merges are found, step 160, the routine is done. 
     One way to prioritize the order in which merges are performed is to incorporate execution profile information. Edges are weighted by the execution count of the instruction generating the edge. In the absence of profile information, one may prioritize concurrent-access inside loops. In this case edges generated by instructions inside loops are weighted with the loop nesting depth. The algorithm is first applied only considering edges with the highest weight, then successively proceeding to edges of lower weight. It is possible to consider ignoring edges whose weight is below a given threshold. This allows for an algorithmic tradeoff between performance and cost (in memory size) due to data replication. 
     FIG. 17 is a block diagram illustrating a General Purpose Computer 20. The General Purpose Computer 20 has a Computer Processor 22, and Memory 24, connected by a Bus 26. Memory 24 is a relatively high speed machine readable medium and includes Volatile Memories such as DRAM, and SRAM, and Non-Volatile Memories such as, ROM, FLASH, EPROM, EEPROM, and bubble memory. Also connected to the Bus are Secondary Storage 30, External Storage 32, output devices such as a monitor 34, input devices such as a keyboard (with mouse) 36, and printers 38. Secondary Storage 30 includes machine readable media such as hard disk drives, magnetic drum, and bubble memory. External Storage 32 includes machine readable media such as floppy disks, removable hard drives, magnetic tape, CD-ROM, and even other computers, possibly connected via a communications line. The distinction drawn here between Secondary Storage 30 and External Storage 32 is primarily for convenience in describing the invention. As such, it should be appreciated that there is substantial functional overlap between these elements. Computer software such as compilers that utilize this invention, compiled code generated by such compiler, and other user programs can be stored in a Computer Software Storage Medium, such as memory 24, Secondary Storage 30, and External Storage 32. Executable versions of computer software 33, including such compilers and their generated code, can be read from a Non-Volatile Storage Medium such as External Storage 32, Secondary Storage 30, and Non-Volatile Memory and loaded for execution directly into Volatile Memory, executed directly out of Non-Volatile Memory, or stored on the Secondary Storage 30 prior to loading into Volatile Memory for execution. 
     Those skilled in the art will recognize that modifications and variations can be made without departing from the spirit of the invention. Therefore, it is intended that this invention encompass all such variations and modifications as fall within the scope of the appended claims. 
     Claim elements and steps herein have been numbered and/or lettered solely as an aid in readability and understanding. As such, the numbering and/or lettering in itself is not intended to and should not be taken to indicate the ordering of elements and/or steps in the claims.