Data allocation into multiple memories for concurrent access

A compiler executable on a central processing unit (CPU) and stored in a Computer Software Storage Medium that allocates data over a plurality of memories for concurrent access, said compiler comprising:

• A) a set of computer instructions stored in a computer software storage medium for transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions;
• B) a set of computer instructions stored in the computer software storage medium for selectively merging vertices of the transformed graph to form a merged graph;
• and
• C) a set of computer instructions stored in the computer software storage medium for allocating data to the plurality of memories utilizing the merged graph;
• D) wherein a computer program generated by the compiler is stored on a non-volatile storage medium encoded in a machine readable format.

A system for allocating data over a plurality of memories for concurrent access, said system comprising:

• A) means for transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions, at least one of the line graph and the transformed graph stored in a volatile memory;
• B) means for selectively merging vertices of the transformed graph to form a merged graph;
• and
• C) means for allocating data to the plurality of memories utilizing the merged graph.

A method of allocating data over a plurality of memories for concurrent access, said method comprising the steps of:

• A) transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions;
• B) selectively merging vertices of the transformed graph to form a merged graph;
• C) allocating data to the plurality of memories utilizing the merged graph;
• and
• D) applying clique partitioning to the merged graph to form a final graph.

A method of allocating data over a plurality of memories for concurrent access, said method comprising the steps of:

• A) transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions;
• B) selectively merging vertices of the transformed graph by selecting merging candidates based on cycle cost criteria to form a merged graph;
• and
• C) allocating data to the plurality of memories utilizing the merged graph.

A method of allocating data over a plurality of memories for concurrent access, said method comprising the steps of:

• transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions;
• selectively merging vertices of the transformed graph by selecting merging candidates based on execution profiling information to form a merged graph;
• and
• allocating data to the plurality of memories utilizing the merged graph.

A method of allocating data over a plurality of memories for concurrent access, said method comprising the steps of:

• transforming a line graph into a transformed graph to remove edges corresponding to definitions reaching multiple uses and edges corresponding to uses reached by multiple definitions, at least one of the line graph and the transformed graph stored in a volatile memory;
• selectively merging vertices of the transformed graph to form a merged graph;
• and
• allocating data to the plurality of memories utilizing the merged graph.