Automatic generation of cache-optimized code

• US 8,706,964 B1
• Filed: 09/28/2007
• Issued: 04/22/2014
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: Koh, David, Belge, Murat
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US11/864,578
• Time in Patent Office: 2,398 Days
• Field of Search: 711/118
• US Class Current: 711/118
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 2212/62 Details of cache specific to multiprocessor cache arrangements

Abstract

A system receives cache conditions and software information related to a software application, and automatically generates an optimal cache management scheme for the software application based on the received cache conditions and software information.

Claims

1. A non-transitory computer-readable memory device that stores instructions, the instructions comprising:

one or more instructions that, when executed by a processor, cause the processor to;

receive cache conditions and data of a software application;

determine related sections of code of the software application;

receive an input,

the input specifying;

one or more particular related sections of code of the software application, and

specific cache conditions;

determine a cache management scheme based on the cache conditions;

align the determined related sections of the code and the particular related sections of the code based on the cache management scheme to create aligned code;

group that aligned code into one or more first sections;

distribute the grouped code into one or more second sections in a memory;

receive information regarding a section of the one or more second sections,

the information being based on;

a size of the section, and

a frequency of access of the section; and

lock, based on the received information, the section in a cache for a particular period of time.

2. The non-transitory computer-readable memory device of claim 1, where the one or more instructions that cause the processor to align the determined related sections of the code and the particular related sections of the code further comprise:

one or more instructions that, when executed by the processor, cause the processor to;

automatically align the determined related sections of the code and the particular related sections of the code to cache line boundaries.

3. The non-transitory computer-readable memory device of claim 1, where the one or more instructions that cause the processor to align the determined related sections of the code and the particular related sections of the code further comprise:

one or more instructions that, when executed by the processor, cause the processor to;

automatically align the determined related sections of the code and the particular related sections of the code to cache line boundaries based on a user-specified program or data section.

4. The non-transitory computer-readable memory device of claim 1, where the one or more instructions that cause the processor to align the determined related sections of the code and the particular related sections of the code further comprise:

one or more instructions that, when executed by the processor, cause the processor to;

automatically align the determined related sections of the code and the particular related sections of the code to cache line boundaries based on at least one of;

one or more user-specified cache conditions, or

a combination of one or more user-specified cache conditions and a user-specified program or data section.

5. The non-transitory computer-readable memory device of claim 1, where the cache conditions include at least one of:

a number of levels of cache available,

a cache size for each available cache,

a cache line size for each available cache,

a cache alignment of each block of code or data,

a trip count frequency, or

a cache replacement policy, and

where the data of the software application includes at least one of;

related portions of the code and the data of the software application,

most frequently used portions of the code and the data of the software application, or

user-specified preferred portions of the code and the data.

6. The non-transitory computer-readable memory device of claim 1, where the one or more instructions that cause the processor to align the determined related sections of the code and the particular related sections of the code include:

one or more instructions that, when executed by the processor, cause the processor to;

align the determined related sections of the code and the particular related sections of the code as part of a multiple level cache management scheme.

7. A system comprising:

a device, including a processor, to;

receive software information, cache information, and optimization rules,

the software information comprising related sections of code or data of a program,

receive an input,

the input specifying;

particular related sections of the code or the data of the program, and

particular cache conditions,

generate a cache management scheme based on;

the cache information, and

the optimization rules,

align the related sections of the code and the particular related sections of the code based on the cache management scheme to create aligned code;

group that aligned code into one or more first sections;

distribute the grouped code into one or more second sections in a memory;

receive information regarding a section of the one or more second sections,

the information being based on;

a size of the section, and

a frequency of access of the section; and

lock, based on the received information, the section in a cache for a particular period of time.

8. The system of claim 7, where the cache information comprises at least one of:

a description of attributes and physical layout of physical cache elements of a computational hardware device,

information describing a type of memory used for cache,

an access type and a speed of each type of memory,

a size of each type of memory,

a number of levels of cache available,

a cache size for each available cache,

a cache line size for each available cache,

a cache alignment of each block of program,

a trip count frequency, or

a cache replacement policy.

9. The system of claim 7, where the optimization rules comprise at least one of:

information regarding one or more software components,

information regarding one or more modules, or

information regarding one or more libraries configured with optimization algorithms.

10. The system of claim 7, where the optimization rules provide a heuristic approach to generate the cache management scheme.

11. The system of claim 7, where the device is further to:

receive one or more files associated with a block diagram model, and

generate particular code based on the cache management scheme and the received one or more files.

12. The system of claim 11, where the device is further to:

receive input data structures associated with the block diagram model; and

output information associated with the program, based on the cache management scheme, the block diagram model, and the input data structures,

the output information including at least one of;

one or more source code files,

one or more linker files, or

one or more object code.

13. The system of claim 12, where

the particular code comprises a compiled and executable form of the source code files provided as a sequence of processor-readable instructions, or

the input data structures comprise at least one of:

templates,

commands,

input parameters,

configuration data,

source code, or

data and class definitions used by an automatic code generator.

14. The system of claim 11, where the block diagram model comprises a design or an algorithm provided by a technical computing environment.

15. The system of claim 11, where the device is further to:

generate one or more intermediate representations based on the cache management scheme and the block diagram model; and

generate the particular code based on the one or more intermediate representations.

16. A method comprising:

receiving cache conditions and data of a software application,

the receiving being performed by a computing device;

determining related sections of code of the software application,

the determining being performed by the computing device;

receiving an input,

the input specifying;

one or more particular related sections of code of the software application, and

specific cache conditions, and

the receiving the input being performed by the computing device;

determining a cache management scheme based on the cache conditions,

the determining the cache management scheme being performed by the computing device;

aligning the determined related sections of the code and the particular related sections of the code based on the cache management scheme to create aligned code,

the aligning being performed by the computing device;

grouping that aligned code into one or more first sections,

the grouping being performed by the computing device;

distributing the grouped code into one or more second sections in a memory,

the distributing being performed by the computing device;

receiving information regarding a section of the one or more second sections,

the information being based on;

a size of the section, and

a frequency of access of the section, and

the receiving the information being performed by the computing device; and

locking, based on the received information, the section in a cache for a particular period of time,

the locking being performed by the computing device.

17. The method of claim 16, where, when aligning the determined related sections of the code and the particular related sections of the code, the method includes:

automatically aligning the determined related sections of the code and the particular related sections of the code to cache line boundaries.

18. The method of claim 16, where, when aligning the determined related sections of the code and the particular related sections of the code, the method includes:

automatically aligning the determined related sections of the code and the particular related sections of the code as part of a multiple level cache management scheme.

19. A device comprising:

a memory to store instructions; and

a processor to execute the instructions to;

receive software information, cache information, and optimization rules,

the software information comprising related sections of code or data of a program,

receive an input,

the input specifying;

particular related sections of the code or the data of the program, and

particular cache conditions,

generate a cache management scheme based on;

the cache information, and

the optimization rules,

align the related sections of the code and the particular related sections of the code based on the cache management scheme to create aligned code;

group that aligned code into one or more first sections;

distribute the grouped code into one or more second sections in a memory;

receive information regarding a section of the one or more second sections, the information being based on;

a size of the section, and

a frequency of access of the section; and

lock, based on the received information, the section in a cache for a particular period of time.

20. The device of claim 19, where the processor is further to:

receive one or more files associated with a block diagram model, and

generate particular code based on the cache management scheme and the received one or more files.

21. The device of claim 20, where the processor is further to:

receive input data structures associated with the block diagram model; and

output information associated with the program, based on the cache management scheme, the block diagram model, and the input data structures,

the output information including at least one of;

one or more source code files,

one or more linker files, or

one or more object code.

22. The device of claim 20, where the processor is further to:

generate one or more intermediate representations based on the cache management scheme and the block diagram model; and

generate the particular code based on the one or more intermediate representations.