Patent Description:
Computer systems often benefit from a hierarchical memory design, for example in which (at least partial) copies of the memory content can be stored (i.e., cached) at different levels within the memory hierarchy. Often, the hardware supporting the different memory levels has different capacities, costs, and access times. Generally speaking, faster and smaller memory circuits are often located closer to processor cores or other processing elements within the system, and serve as caches. Other types of memory storage devices in the processing system may be larger and less expensive but may also be relatively slow compared to those memories acting as caches.

<CIT> relates to a system comprising a cache eviction circuit and configured for selecting a policy to evict cache lines of a cache memory. In particular, it discloses a computer system comprising a processor and a memory external to the processor and storing an instruction block. Groups of instructions are cached from the instruction section of the memory to the instruction cache inside processor. The processor includes execution units, a cache memory and an interconnect. The processor may include an instruction cache and a data cache as part of the internal cache memory.

Various optional features are mentioned in the dependent claims.

The present technology may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying figures.

The use of the same reference symbols in different drawings indicates similar or identical items unless otherwise noted.

Embodiments of systems and methods for managing cache replacement processing of variable sized load units holding executable instructions and constant data are disclosed that manage loading of the instructions and data into a buffer memory such as (random access memory (RAM)) internal to a microcontroller from a memory device external to the microcontroller. The external memory device provides larger storage for applications currently running than can be buffered within memory internal to the microcontroller. Unnecessary impact on the application code and load bandwidth is avoided by the capability to process variable sized load units. The cache operation supports execution of multiple applications in the microcontroller by multiple processor cores that may be using more than one instance of the same or different operating systems, along with other types of bus masters that access instructions or the constant data in memory. The systems and methods disclosed herein are implemented in a cache control subsystem that is further referred to as Operating System Aware Task Caching (OTC).

Unlike known processor cache arrangements that are limited to processing one size of load units for cache memory, variable size load units are supported by the cache management components disclosed herein via decoupled load request and cache eviction operations. By decoupling the request and eviction operations, one complexity of variable size load units is overcome by evicting multiple load units to provide space for a larger load unit, or the inverse case in which multiple smaller units can be loaded into the free space resulting from the eviction of a larger load unit. More than one candidate for eviction is selected in case a larger load unit is requested thereby forcing multiple load units to be evicted to provide sufficient space. The multiple candidates are appropriately managed until they are actually used, as a good eviction candidate at time X may be an unsuitable candidate at time X+Y. The complexity of managing multiple eviction candidates is significantly higher when the cache content is shared between multiple bus masters (for example, processor cores) that may be executing different instructions located in different load units located within the cache.

Decoupling the eviction and request operations can also permit further optimizations of the cache behavior. For example, to optimize the contents of the large buffer memory, the most worthy data elements to be kept in the memory may be identified. Such an optimization requires one or more suitable eviction candidates to be identified in advance, which is not possible when a replacement candidate is identified on demand, as with traditional instruction caches.

As noted above, external memory can store more than one image, e.g., to support over-the-air (OTA) update of the images, where one image is holding the instructions and constant data of the applications that are concurrently executed within a microcontroller. Even providing sufficient internal memory for storing all instructions and constant data of a single image concurrently in the internal RAM of typical MCUs in addition to the RAM required for the application data may result in a RAM size that is prohibitively expensive. Before instructions of these applications can be executed within an MCU that does not employ non-volatile memory, the instructions are copied from external non-volatile memory and loaded into internal memory. An intelligent cache controller that only loads the subset of instructions and constant data that is currently in use/required by an application helps reduce the corresponding size of internal memory needed for this purpose. Such a partial buffering requires in-advance loading of the instructions to ensure their availability in time, which is distinct from traditional caches that perform on-demand loading.

While external non-volatile memory can be substantially larger than internal memory, it is usually significantly slower to access, especially the non-volatile memories suitable for an embedded system within an in-vehicle automotive environment. The situation may be compounded in a multi-core system where multiple processor cores want to access the instruction memory at the same time. This issue is viewed in light of an internal memory which may already having a limiting performance as is obvious by the need of Level <NUM>/Level <NUM> processor caches in todays embedded systems. Any slower access can present challenges to the timing requirements of an operating system that has to execute tasks in real time, especially the usual embedded systems in the automotive world that have to adhere to very stringent real-time conditions. For example, when implementing breaking, airbag or powertrain applications, an appropriate reaction to an event may be required within a few milli or micro seconds. While related problems can be overcome by preloading internal memory with instructions from the external memory before the running task actually uses them, this may still be too late when there is insufficient bandwidth for loading. When the cache already contains the needed instruction (because it has been loaded earlier and not evicted since then), such preloading can be avoided. This makes the cache replacement strategy and the appropriate management of the cache eviction candidates a prime task for the cache controller element.

As previously mentioned, to accommodate variable sized load units, a single new load unit may require replacing one or more load units already stored in the internal memory. A single replaced load unit may provide space for one or multiple new load units. Thus, a single caching or load request may trigger none (when there is sufficient space free), a single (when a replaced load unit provides sufficient space for a new load unit), or multiple cache replacement operations (otherwise). These replacement operations are further named "evictions" because there is not a real replacement of an earlier load unit by another load unit, but an eviction of a load unit to gain space for a later storage of instructions from another load unit being loaded. Since there may be multiple such load units that need to be evicted after a single load request, an appropriate management of the potential candidates for this eviction is a prime concern. Otherwise the time and effort of finding a new candidate for an eviction may cause another unwanted delay for any load operation that requiring free space.

<FIG> illustrates a timeline showing the effect of managing variable sized load units, in particular the replacement of one load unit j <NUM> that is loaded and located between two other load units load unit i <NUM> and load unit k <NUM>. The eviction of load unit j <NUM> will provide an equally sized free space <NUM>. Later loading of the load unit m <NUM>, load unit n <NUM>, and load unit p <NUM> may fill the free space <NUM> while keeping the load unit i <NUM> and load unit k <NUM> in memory unmodified. After loading these three load units the remaining free space <NUM> may not be sufficient to load a later loaded load unit q <NUM>. This basic problem is named fragmentation, and relates to the issue that there may be storage that cannot be used because it is not large enough for the next element to be stored. This form of fragmentation is referred to as external fragmentation. A usual solution for the fragmentation is the usage of equally sized allocation units, which is also referred as paging. In this case every allocation occupies an equally sized storage unit, the page. This arrangement suffers from inefficient memory use, since any storage occupies at least one storage unit. The resulting waste is called internal fragmentation.

<FIG> illustrates a block diagram of processing system <NUM> in accordance with selected embodiments of the invention that includes an operating system task aware caching (OTC) subsystem for scheduling operations with variably sized load units to be performed within processing system <NUM>. Processing system <NUM> includes microcontroller unit (MCU) <NUM> with two or more bus masters such as processor cores <NUM>, <NUM>, <NUM>, and other bus masters <NUM> such as a direct memory access bus master and/or other suitable bus masters. Processor cores <NUM>, <NUM>, <NUM> may employ their own dedicated cache devices. In the embodiment shown, processor core <NUM> is not coupled to a dedicated cache, processor core <NUM> is coupled to a single dedicated cache <NUM>, and processor core <NUM> is coupled to a hierarchy of dedicated cache <NUM>, <NUM>. Dedicated cache <NUM>, <NUM>, <NUM> can store data and instructions that are used often by respective processor cores <NUM>, <NUM>. Cache <NUM>, <NUM>, <NUM> are optional and may be available in addition to embodiments of the OTC caching subsystem disclosed herein.

Dedicated caches <NUM>, <NUM>, <NUM> are usually located in the vicinity of an associated processor core <NUM>, <NUM> and attempt to avoid the latency incurred when processor cores <NUM>, <NUM> communicate with other devices internal to the microcontroller <NUM>, such as the internal memory <NUM>. Dedicated caches <NUM>, <NUM>, <NUM> perform an on-demand loading and operate independently of OTC controller <NUM>, which uses an anticipation mechanism and the internal memory <NUM> as storage to avoid the latency and bandwidth issues when accessing the external memory <NUM>.

Bus masters <NUM>, <NUM>, <NUM>, <NUM> and other interconnect and peripheral devices (not shown) can be operably coupled to interconnect <NUM>, which may be a single interconnect or a set of specific interconnects. Interconnect <NUM> couples bus masters <NUM>, <NUM>, <NUM>, <NUM> to communicate with bus slaves responding to access requests. Examples of bus slaves can include internal memory device <NUM>, and peripherals represented by P0 <NUM> and P1 <NUM>, which may be connected to interconnect <NUM> via peripheral bridge <NUM>. Bus masters <NUM>, <NUM>, <NUM>, <NUM> can be coupled to interconnect <NUM> via a respective map device <NUM>, <NUM>, <NUM>, <NUM>. A map device <NUM>, <NUM>, <NUM>, <NUM> observes access requests of its associated bus master <NUM>, <NUM>, <NUM>, <NUM>, and may perform a mapping of the corresponding address for access requests when required.

Internal memory device <NUM> can include multiple memory blocks, which may be organized in random access memory (RAM) banks permitting concurrent accesses to different memory banks by multiple bus masters <NUM>, <NUM>, <NUM>, <NUM>. Internal memory device <NUM> provides storage for two functions: i) a first section is designated as system memory <NUM> that is utilized for storing the data for the applications executed within the processing system <NUM>, and ii) a second section is designated as instruction cache <NUM> to hold instructions and constant data of the applications in structures referred to as temporary load units <NUM>. The sections for instruction cache <NUM> and system memory <NUM> may span multiple banks and the content of a bank can be utilized by both sections; there is no relationship between the sections for instruction cache <NUM> and system memory <NUM> and the banks.

Temporary load units <NUM> contain a copy of the instructions and/or constant data associated with a corresponding load unit <NUM> of an application within an image <NUM> in external memory <NUM>. The corresponding information about load units <NUM> of an image <NUM> may be specified, for example, in table format, that contains relevant properties for every load unit <NUM>. The relevant properties can be stored separately from the instructions and constant data contained within load units <NUM> within metadata. Metadata may alternatively be stored in a different location in external memory <NUM>.

Microcontroller <NUM> further includes OTC controller <NUM> that includes one or more load entity queues <NUM>, load manager <NUM>, address map device <NUM>, and cache replacement manager <NUM>, as well as other components that are not shown. The components of OTC controller <NUM> may be implemented as separate units that interact with other components that are also implemented separately to provide the functionality of OTC controller <NUM>. OTC controller <NUM> is operably coupled to interconnect <NUM> via one or more register interface(s) <NUM>, <NUM> as a peripheral and/or bus master to access other bus slaves, for example, internal memory <NUM>. OTC controller <NUM> or its address map device <NUM> is also operably coupled to map devices <NUM>, <NUM>, <NUM>, <NUM>, where this coupling may utilize a common communication path or a dedicated communication path <NUM>, <NUM>, <NUM>, <NUM> for every map device. In addition, or alternatively, one or more components of OTC controller <NUM> may be directly coupled to internal memory <NUM> via a direct connection <NUM> to access internal memory <NUM>. OTC controller <NUM> (or load manager <NUM> when implemented separately) can be coupled to external memory <NUM> via interface <NUM>.

Each instance of load entity queues <NUM> supports access requests from an associated bus master <NUM>, <NUM>, <NUM>, <NUM>. Load entity queues <NUM> may utilize a set of control and status registers specific to each load entity queue <NUM> in addition to common registers of OTC controller <NUM>. Both the specific and common sets of registers can be accessed from interconnect <NUM> via one of register interfaces <NUM>, <NUM>. Each load entity queue <NUM> is further coupled to cache replacement manager <NUM> and to load manager <NUM>. The interface to load manager <NUM> is used by a load entity queue <NUM> to request the loading of a load unit <NUM> from external memory <NUM>.

During processing of load units <NUM>, load entity queues <NUM> may store load unit information <NUM> to identify relevant information for at least one load unit <NUM> that is currently managed by a corresponding load entity queue <NUM>. The relevant load unit information <NUM> can be metadata reflecting information for a subset of load units <NUM> contained within an image <NUM>. Metadata for load units <NUM> can be stored along with or within image <NUM> in external memory <NUM>, and may be temporarily loaded into internal memory <NUM>. Load unit information <NUM> related to load units <NUM> being managed by load entity queue <NUM> may be read from internal memory <NUM> via bus master interface <NUM> or via direct connection <NUM> between internal memory <NUM> and OTC controller <NUM>. Load unit information <NUM> may be stored in other locations in OTC controller <NUM> in other embodiments.

Two or more different types of load entity queues <NUM> may be implemented. A first type of load entity queue <NUM> can provide the full functionality required by the most complex type of bus master type, which will be usually be a processor core <NUM>, <NUM>, <NUM>. Other types of loader entity queues <NUM> may provide only a subset or reduced form of functionality to align with specific needs of a particular bus master or provide a cost-effective implementation for bus masters implementing significantly less functionality. Load entity queues <NUM> that do not implement the full functionally are referred to as a "reduced" load entity queue <NUM>.

Load manager <NUM> is coupled to communicate directly with the load entity queue(s) <NUM>, address map device <NUM> and cache replacement manager <NUM>. Load manager <NUM> may also provide a register interface (not shown) to interconnect <NUM> to interact with software and utilize a bus master interface to access internal memory <NUM>, either through interconnect <NUM> or direct connection <NUM> to internal memory <NUM>. Load manager <NUM> communicates over interface <NUM> with external memory device <NUM> to request the content of load units <NUM> from external memory <NUM> that are stored as temporary load units <NUM> in instruction cache portion <NUM> of internal memory <NUM>.

Another element shown in OTC controller <NUM> is address map device <NUM>, which is connected to load manager <NUM> and cache replacement manager <NUM>. Upon startup of the OTC Controller <NUM> address map device <NUM> is initialized with the information about the part of the internal memory <NUM> that shall be utilized as instruction cache <NUM>. For this purpose, map device <NUM> may receive corresponding information via a register interface <NUM> or <NUM>. Map device <NUM> further receives information about the address ranges assigned to load units <NUM> within a selected image <NUM> in external memory <NUM>. Corresponding information may also be determined from metadata (not shown) that is stored together with an image <NUM> within external memory <NUM> provided via register interface <NUM> or <NUM>.

Address map device <NUM> is responsible for managing the content of the instruction cache <NUM>, in particular the memory occupied by the temporary load units <NUM> where each temporary load units <NUM> is the result of loading a load unit <NUM> into the instruction cache <NUM>, as well as any remaining free storage within the instruction cache <NUM> as needed. Address map device <NUM> is queried at least once for a free storage location when load manager <NUM> wants to store a first load unit <NUM> or a part of such a load unit in instruction cache <NUM>. When there is sufficient free storage available in instruction cache <NUM>, address map device <NUM> provides corresponding information regarding the space available to load manager <NUM>. When there is not enough free storage available, address map device <NUM> provides an eviction request to cache replacement manager <NUM>. Upon receiving such an eviction request, cache replacement manager <NUM> provides information about a temporary load unit <NUM> that is selected for eviction. The location of the load unit <NUM> selected for eviction is used by address map device <NUM> to free the storage space utilized by the load unit <NUM> selected for eviction. The free storage space can then be utilized for storing the instructions and constant data of load unit <NUM> as a temporary load unit <NUM> in instruction cache <NUM>. By providing this functionality, address map device <NUM> manages the usage of free storage space within instruction cache <NUM> to store a copy of first load unit <NUM> as temporary load unit <NUM> and to release storage space upon eviction of temporary load unit <NUM>.

Cache replacement manager <NUM> is coupled to address map device <NUM> and load entity queues <NUM>. Cache replacement manager <NUM> is queried by address map device <NUM> when address map device <NUM> determines there is insufficient storage space available in instruction cache <NUM> for a new temporary load unit <NUM>. The query may be triggered while a load request is processed by load manager <NUM> that requires storage of a temporary load unit <NUM>. A corresponding query operation is triggered when an event occurs that requires one or more temporary load units <NUM> to be evicted.

To enable rapid response to an eviction requirement, cache replacement manager <NUM> can store information about a set of managed eviction candidates <NUM>, which are processed when an eviction requirement is identified. Temporary load unit(s) <NUM> to be evicted from instruction cache <NUM> can be identified based on specified criteria, such as priority or other suitable criteria. The eviction process itself can be managed by address map device <NUM> as previously described herein. The set of managed eviction candidates <NUM> can be generated from eviction candidates identified by the load entity queues <NUM>. For the purpose of selecting an eviction candidate, any load entity queue <NUM> may utilize corresponding load unit information <NUM>.

External memory device <NUM> may be implemented using non-volatile memory or other suitable type(s) of memory device(s). External memory device <NUM> stores at least one image <NUM> that includes the instructions and constant data associated with at least one application program to be executed by processor core <NUM>, <NUM>, <NUM> implemented within microcontroller <NUM>. At least one image <NUM> is structured into one or multiple load units <NUM> that may be used as a unit when loading instructions and constant data from external memory <NUM>. Structuring image <NUM> into load units <NUM> can be accomplished, for example, by storing additional metadata (data about data) associated with load units <NUM> within external memory <NUM>. The metadata may be stored separately (not shown) or as part of image <NUM>. Load manager <NUM> accesses external memory <NUM> via interface <NUM> for loading a load unit <NUM> and writing the instructions and constant data included in the load unit <NUM> into the corresponding temporary load unit <NUM> within the instruction cache <NUM>. The write operation from external memory <NUM> to instruction cache <NUM> may utilize a write path <NUM> through interconnect <NUM> or direct connection <NUM> to internal memory <NUM>.

Microcontroller <NUM> and external memory device <NUM> are implemented on two different semiconductor devices, which may be within a single package or in different packages. Correspondingly the interface <NUM> between these two semiconductor devices may be a connection within a package or between two packages.

The size of the internal memory device <NUM> may be limited compared to the size of external memory device <NUM>. External memory device <NUM> can hold multiple images <NUM> and every image <NUM> can hold instructions and data for one or multiple applications executed by processor cores <NUM>, <NUM>, <NUM>. Execution of the applications is typically controlled by an operating system, and in many situations, the operating systems are required to adhere to stringent real-time conditions and are therefore referred to as real-time operating systems (RTOS). An application program that is controlled by a RTOS can use tasks to identify its units of execution. While images <NUM> holding the one or multiple applications executed by the microcontroller <NUM> may be stored in its entirety in external memory device <NUM>, image <NUM> can be divided into contiguous segments of executable code, which are referred to as load units <NUM>. A temporary copy <NUM> of the content a load unit <NUM> (holding instructions and/or constant data) can be loaded into instruction cache <NUM> for usage by a corresponding processor core <NUM>, <NUM>, <NUM> or other bus master <NUM>. As such load units <NUM> are a segment of instructions and constant data that reflects one or more complete software functions within a contiguous address range. Temporary load units <NUM> loaded into the internal memory <NUM> is operable to be executed or otherwise processed by a processor core <NUM>,<NUM>, <NUM> or used by another bus master <NUM> within microcontroller <NUM>.

Load units <NUM> can be specified by splitting the code and instructions of an application within an image <NUM> along functional boundaries along a set of contiguous address ranges. The functions may be associated with a task or shared by multiple tasks supported by at least one instance of a real-time operating system. The information about load units <NUM> can be specified in metadata, and may be produced manually during the software development process or by a tool or tool flow that automates the related generation process. Size restrictions can be defined for load units <NUM>, e.g., a minimum size of <NUM> Kbyte and a maximum size of <NUM> Kbyte. Other restrictions (e.g., an address alignment of the start or end address) are not required. A preferred order for loading a set of load units <NUM> may be defined by a load sequence that is also specified within the metadata. Any load sequence may comprise an arbitrary number of load units <NUM>.

Bus masters <NUM>, <NUM>, <NUM>, <NUM> and OTC controller <NUM> can perform their respective operations concurrently and independently of one another. For example, the loading of instructions and constant data from the external memory device <NUM> can be performed independent of the processing being performed by bus masters s <NUM>, <NUM>, <NUM>, <NUM>. This processing can be an execution of software by processor cores <NUM>, <NUM>, <NUM>, which may itself be several software threads executed on multiple processor cores <NUM>, <NUM>, <NUM> or other processing performed by any other bus master(s) <NUM>. The potential concurrency of operations is dependent on the corresponding hardware that is performing such an operation. Accessing external memory device <NUM> may be concurrent to any other operation. A potential collision may arise when accessing the internal memory <NUM>. Here a conflict between an access by one of the bus masters and an access by the OTC controller <NUM> (for example, when writing the content of a load unit read from the external memory) is possible. However, the probability of conflicts can be significantly reduced e.g., by using a multi-ported memory or by utilizing a specific memory architecture, like memory interleaving, that enables multiple concurrent accesses.

MCU <NUM> is capable of retrieving data and instructions from external memory device <NUM> to replace temporary load units <NUM> in instruction cache <NUM>. If one processor core <NUM>, <NUM>, <NUM> wants to replace a temporary load unit <NUM>, but another processor core <NUM>, <NUM>, <NUM> does not, cache replacement manager <NUM> determines which load unit <NUM> will be replaced based on information from the operating systems of processor cores <NUM>, <NUM>, <NUM> and the tasks being executed in each of processor cores <NUM>, <NUM>, <NUM>, as will be more fully described below. The size of internal memory <NUM> may be selected to accommodate smaller load units <NUM> having variable sizes while the rest of the instructions and data corresponding to portions of an application that are not planned for execution remain in external memory device <NUM>. The result is that the size of internal memory <NUM> will be smaller than otherwise needed to accommodate all of the data and instructions associated with a particular application if external memory device <NUM> were not available.

Processing system <NUM> is capable of managing a set of cache eviction candidates to enable variable sized load units <NUM> for cache management, effectively decoupling the generation of cache eviction candidates from their usage for the cache eviction. This decoupling permits a larger time span between generating a cache eviction candidate and using the cache eviction candidate, which permits a more sophisticated search for a "more optimal" candidate. In contrast, traditional Level <NUM>/Level <NUM> cache <NUM>, <NUM>, <NUM> that operate on demand have to provide the eviction candidate more or less instantly.

Referring to <FIG> and <FIG> illustrates the mapping of a virtual address into its corresponding physical address in accordance with selected embodiments of the invention that may be performed by map devices <NUM>-<NUM> for accesses by bus masters <NUM>-<NUM> and within address map device <NUM> for loading by load manager <NUM>. In this context the name "virtual address" identifies the address provided by a bus master <NUM>-<NUM> in its access request, while the name "physical address" identifies the address of the actual storage location of the requested information within a memory, e.g. the internal memory <NUM>. The following illustration utilizes an equally sized virtual address, although an artisan skilled in the art will understand that different address sizes can also be supported by the described scheme.

The intent of the address mapping scheme depicted in <FIG> is to support load units <NUM> of variable size, which may or may not be loaded within instruction cache <NUM> in internal memory <NUM>. Supporting variable sized load units <NUM> is beneficial when the criteria for forming a load unit <NUM> results in differing sizes, which is certainly the case for load units <NUM> related to application software that are structured along a functional boundary, since the size of a software function can vary greatly from a few byte to several thousand of bytes. Using variable size load units <NUM> is highly beneficial when the generation of equally sized load units causes unwanted overhead for this kind of information. For example, due to the time required for loading extra information in case of limited bandwidth, or due to wasted memory when a load unit <NUM> has to be padded to generate load units <NUM> of equal size.

In contrast to this, many address mapping implementations favor a direct mapping due to its simplicity of hardware implementation. A direct address mapping replaces a subset of the address bits of the request address with a mapped subset of these address bits, thus requiring equally sized load units for the address mapping. Such a scheme permits a fast implementation, since the replacement of bits is a simple operation, the only time-consuming implementation is the search of the corresponding address mapping information for a requested virtual address. A further benefit is the reduced amount of address mapping information required to store for this scheme, which can be limited to the amount of address bits being replaced. A potential problem of this scheme that is common with other address mapping schemes is the limited amount of address mapping possibilities that can be managed concurrently within hardware. This limitation is a result of the fact that the address mapping hardware is usually in the critical path for access requests, and a large amount of mapping possibilities requires an equally large amount of comparator or search elements that process the access request concurrently. However, using a large number of hardware elements for this purpose increases the load of an access request, which will ultimately slow this request down. Due to this issue, address mapping is usually performed by a very limited number of elements that concurrently check for an appropriate address mapping information.

Corresponding address mapping hardware is often implemented as a memory management unit (MMU). There are implementations of MMUs that support variable sized address mapping (also referred to as segmented MMU) and other implementations supporting a direct address mapping (also referred to as paged MMU). Most modern systems support a page-based address mapping scheme that divides the available memory into pages that are <NUM>-<NUM> Kbyte in size. Some schemes permit more than one page size, where an actual page size is always a power of two. One of the benefits of a paged MMU is that it mitigates the problem of fragmentation of memory, because a continuous range of virtual addresses (pages) can be mapped to several non-contiguous blocks of physical memory. As such it solves the problem of external fragmentation, which may be the result of a variable sized address range replacing another variable and differently sized address range. However, a paged MMU still suffers from internal fragmentation, which is the case when not all memory within a page can be used for storing information, because the address ranges are not equal to a page size. Also, splitting an address range into multiple pages requires a larger number of address mapping elements, which is a problem for implementing fast address mapping hardware. To overcome this issue, some MMU implementations use a translation lookaside buffer (TLB) that caches a limited amount of page table entries (PTE) for performing the actual address mapping.

In <FIG>, an address mapping scheme <NUM> utilizes direct address mapping based on pages that also supports variable sized load units <NUM> in accordance with selected embodiments of the invention. The address mapping scheme <NUM> maps a "virtual address" <NUM> to a "physical address" <NUM> utilizing a page size of P bytes, where P is a power of two. In the example embodiment illustrated by <FIG>, assume the value of P is <NUM>, resulting in small pages of one kilobyte size each and corresponding to <NUM> address bits (<NUM>=<NUM>^<NUM>) to address the bytes within a page. A direct mapped address mapping leaves the intra-page address bits intact, thus the bits <NUM> to <NUM> (<NUM>) of the physical address <NUM> are equivalent to the bits <NUM> to <NUM> (<NUM>) of the virtual address <NUM>. There is often the definition of a "mappable address range" that identifies an address range that specifies the permitted set of virtual pages that can be mapped. Address bits that are specific for this address range can be checked separately to identify a valid virtual address but these bits are not relevant for the address translation. The size of the "mappable address range" specifies the number of relevant address bits for the address mapping. In the example embodiment of <FIG> this address range is <NUM> Mbyte corresponding to the address bits <NUM> to <NUM> being relevant for the address mapping. The remaining address bits (<NUM> to <NUM>) within the virtual address <NUM> can be checked using decision element <NUM> to correctly address the mappable address range. When such a check is performed, an "in range" indication <NUM> may be generated that can be used to generate an error signal (outside mappable address range) or select an alternate mapping method that can be implemented for other address ranges.

The corresponding address bits (<NUM> to <NUM>) within the physical address <NUM> may be generated, dependent on the desired address mapping scheme. In a first scheme, bits (<NUM> to <NUM>) may be directly forwarded, effectively mapping the virtual pages within the mappable address range to a physical location. In another scheme, the bits may simply be replaced with address bits representing a different address range, effectively mapping the mappable address range to another (physical) address range. The corresponding address bits (<NUM> to <NUM>) within the physical address bits <NUM> may also be generated by translating the corresponding bits in the virtual address using some hardcoded or programmed formula, for example, by adding or subtracting a value.

The address mapping scheme <NUM> depicted in <FIG> also supports mappable address ranges having a size that is not a power of two. For this purpose, a further comparator (not shown) can be implemented for the mappable address bits (e.g. <NUM> to <NUM>) to identify whether the address identified by these bits is within the mappable address range. However, the address mapping scheme in accordance with selected embodiments of this invention does not require such a comparison as mappable address ranges that are not a power of two and also a mappable address range that consists of a non-contiguous set of pages, can be handled.

The address mapping functionality can be implemented using address lookup tables <NUM> that are capable of mapping any address within a limited set of N load units, where N is a small number that will be typically below <NUM>, and can be a power of two. The example embodiment depicted in <FIG> shows the concurrent processing of N=<NUM> load units, which number has been chosen to simplify <FIG>, however additional load units may be processed. One parameter in address lookup tables <NUM> is the page size (e.g. 1Kbyte), which corresponds to several implementation specifics including the relevant address bits as previously described. A second, optional parameter in address lookup tables <NUM> is the maximum size of a load unit <NUM> in number of pages, further referred to as the parameter M. The purpose of the number of pages parameter is to limit the number of storage elements for storing the mapping information, which is required for an implementation having a reasonable size. The amount of storage elements is preferably also a power of two to permit a simpler and faster implementation. The corresponding maximum load unit size is then M-<NUM> pages. The example embodiment depicted in <FIG> shows an implementation for a maximum load unit size that requires up to M=<NUM> pages, resulting in a maximum load unit size of 7Kbyte for purposes of illustration. Other example embodiments may support load unit sizes up to, for example, M=<NUM> pages, resulting in a maximum load unit size of <NUM> Kbytes in case of a page size of 1KByte.

One implementation of an address lookup table <NUM> may utilize the lower log2(M) address bits <NUM> associated with a page as an index in a lookup table <NUM>. For the example embodiment in <FIG> this would be log2(<NUM>) = <NUM> address bits capable of addressing M=<NUM> storage elements. Using such an address mapping only requires filling the M=<NUM> storage elements in the order of these address bits and not starting with the index <NUM>. The benefit of this implementation is that the lookup operation can be a simple memory access using the <NUM> address bits (<NUM>) extracted from the virtual address <NUM> to address one of the M=<NUM> storage elements (<NUM>) that contains the mapping information. In case of a smaller load unit <NUM> only the relevant storage elements <NUM> are filled.

A second process that can be started concurrently with address mapping using address lookup tables <NUM> includes a range check <NUM>. The range check element <NUM> compares at least a portion of the relevant bits of the virtual address against the start address S and the end address E for one load unit <NUM>. Range check element <NUM> is replicated N times, once for every load unit <NUM> that can be concurrently processed. In the example embodiment depicted in <FIG>, there are four range check elements <NUM> (corresponding to the number of address lookup tables <NUM>), however any suitable number of range check elements <NUM> may be used. Range check elements <NUM> utilize the full set of address bits associated with the page portion <NUM> of virtual address <NUM>, and at least a subset of intra-page portion <NUM>, depicted together as address bit range <NUM>. Also checking a portion of the intra-page address bits <NUM> supports an arbitrary start address and end address up to byte boundary granularity for variable sized load units <NUM>. When the system architecture requires less granularity, then a corresponding amount of least significant address bits can be ignored by range check <NUM> as is also depicted in <FIG>. The result of any range check <NUM> is a single hit/no hit indication that can be combined with the result of the address lookup operation, e.g. by a replicated bit-wise AND operation <NUM> of the hit indicator with every address bit provided by the corresponding address lookup table <NUM>. As a result there may be N results generated, where only an address lookup result that is within a valid range check <NUM> actually delivers an address. All N results can be combined, e.g. by an operation <NUM> that ORs every individual bit for all results to determine a resulting mapped page address <NUM>. This result corresponds to an address mapping that can be employed on a variable sized load unit <NUM> with very high granularity (due to the range check), but this address mapping also supports direct address mapping.

The hit/no hit indicators generated by the N range check elements <NUM> can further be combined by OR operation <NUM> to identify a lookup miss. A lookup miss identifies a situation where none of the N address mapping elements can provide a valid address mapping information, which can be useful when these N elements implement a TLB function. In this case the lookup miss indication can be used to request the address mapping information for the load unit <NUM> associated with the request access address. Based on such a request, the address mapping information for the load unit <NUM> can be determined and loaded into a TLB function. In this case, the content of the address lookup tables <NUM> and the set of start and end addresses {S,E} for every load unit are the TLB information of the TLB function in some embodiments. As with other TLB functions, the start address S, the end address E, and the address mapping information for the request address are provided by an external entity.

The address mapping scheme <NUM> depicted in <FIG> enables an implementation of an address mapping functionality for variable sized load units <NUM> that utilizes a direct address mapping scheme, which combines the benefits of paged address mapping with the flexibility of a segmented MMU. It further enables an implementation of a TLB function that only records the minimum amount of information for a load unit <NUM> (the start and end address, and the address mapping information for every page). There is no need to record the linkage information between the pages used to store a load unit <NUM> within the TLB, which significantly reduces the amount of data storage required. When this address mapping scheme utilizes the lookup miss to request an update of the TLB information for the requested address, then any corresponding error handling can be managed by the entity providing this information. Furthermore, address mapping scheme <NUM> only has the notion of load units <NUM> and the pages used to store associated information, and can work with one or multiple mappable address regions and support a non-contiguous set of mappable address regions. Address mapping scheme <NUM> further fully supports a split page allocation scheme that also avoids or at least minimizes the amount of internal fragmentation, as further described herein.

Referring to <FIG> and <FIG> illustrates a block diagram of an embodiment of map device <NUM> that can be used to implement map devices <NUM>, <NUM>, <NUM>. Map device <NUM> may have different or fewer components for bus masters <NUM> that do not require all the functionality of map devices <NUM>, <NUM>, <NUM> for processor core bus masters <NUM>, <NUM>, <NUM>.

Map device <NUM> is operably coupled via interface <NUM> to present access requests by the associated bus master, e.g. bus master <NUM> for map device <NUM> or associated cache(s) e.g., cache <NUM> in <FIG>. Map device <NUM> is further operably coupled via interface <NUM> to present access requests to interconnect <NUM>. Most information associated with an access request provided by an associated bus master <NUM>, <NUM>, <NUM>, <NUM> via interface <NUM> is either passed unmodified by map device <NUM> via connection <NUM> to interface <NUM> or bypasses map device <NUM> completely. Only a portion of signals related to access address <NUM> is managed by map device <NUM> and may be later combined with other signals bypassed via connection <NUM> within combination element <NUM> to form a new, altered access address and optionally the original access address (or a portion of it that has been altered). When the processing by map device <NUM> cannot be performed in the same cycle, then combination element <NUM> can delay all other signals sent via connection <NUM> by the processing time required by map device <NUM> to insure all signals related to the modified access request are presented at the interface <NUM> at the correct time.

A first processing of the access address <NUM> by map device <NUM> is performed by decision element <NUM> to determine whether the access address is within the map address range. When the access address <NUM> is not within the map address range, output from decision element <NUM> controls multiplexer <NUM> to forward the unaltered access address to combination element <NUM>. In addition, or alternatively, decision element <NUM> may perform further checks and, dependent on the result of the additional checks, reject the access address <NUM> by generating an error response (not shown). When decision element <NUM> determines an access address is within the map address range, multiplexer <NUM> is controlled to deliver mapped address portion <NUM> to combination element <NUM>. Mapped address portion <NUM> is then combined with the unaltered access information from connection <NUM> associated with the access request.

Mapped address portion <NUM> of the access address is generated by a second processing of access address <NUM> by map device <NUM> using a multiplicity of N element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>). Map device <NUM> shows N=<NUM> such element pairs for simplicity reasons, a preferred embodiment of the invention may employ a larger amount of such element pairs that are preferably a power of two; e.g. <NUM>, <NUM>, or <NUM> such element pairs. The operation of element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) can be performed concurrently when there is no dependency between the data they are processing, and only one of element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) may deliver mapped address portion <NUM>. When there is a dependency between the data element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) are processing, then any of element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) that provide a mapped address portion <NUM> can provide the same result. Other element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) that deliver no valid result may provide a default value, e.g. an all <NUM> pattern that can be combined with a valid result by OR gates to form mapped address portion <NUM>. Any element pair (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) can process the information associated with a load unit <NUM>.

Each element of element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) can operate concurrently. The processing of element <NUM> processes a mappable address portion <NUM> that is extracted by a splitter element <NUM> from the access address <NUM> and delivered to the first element <NUM>, <NUM>, <NUM>, <NUM> of all element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>). First element <NUM>, <NUM>, <NUM>, <NUM> performs a lookup operation using mappable address portion <NUM> in address lookup tables <NUM> to determine the associated mapped address portion. For this purpose any first element <NUM>, <NUM>, <NUM>, <NUM> can employ a set of M storage elements <NUM>, where every such container element <NUM> stores the mapped address portion associated with a specific value for the mappable address portion. When the number M of container elements <NUM> is a power of two, this lookup operation can be a simple access to an embedded memory or a register bank that utilizes a corresponding set of address bits log2(M) as mappable address portion. Map device <NUM> shows M=<NUM> such storage elements <NUM> for simplicity, however additional storage elements <NUM> that are preferably a power of two; e.g. <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, or <NUM> may be used. The result of this lookup operation is forwarded by first elements <NUM>, <NUM>, <NUM>, <NUM> to respective second elements <NUM>, <NUM>, <NUM>, <NUM>.

The processing of second elements <NUM>, <NUM>, <NUM>, <NUM> can begin concurrently with processing by first elements <NUM>, <NUM>, <NUM>, <NUM>. Second elements <NUM>, <NUM>, <NUM>, <NUM> perform a range check of the access address <NUM> forwarded unaltered by the splitter <NUM> against a lower and upper address that is recorded for the associated load unit <NUM> within the second element; e.g. the element <NUM>. This range check corresponds to range check <NUM> in <FIG> and may utilize the full address provided, or only a portion of the address that does not reflect address bits associated with the mappable address range as shown in <FIG>. It may also ignore less significant address bits that are not relevant due to architectural considerations. For example, the address bits <NUM> and <NUM> are not relevant when a bus master <NUM>, <NUM>, <NUM>, 207can only perform <NUM> bit word accesses. The recorded upper and lower address boundaries of the associated load unit <NUM> may be restricted accordingly. When the range check performed by second elements <NUM>, <NUM>, <NUM>, <NUM> determines the access address is within the boundaries defined by the lower and upper address of the load unit, the result of first elements <NUM>, <NUM>, <NUM>, <NUM> is forwarded as a mapped address portion.

The management of the data utilized by the set of element pairs (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) (address map information within the N x M storage elements <NUM> (<FIG>), and the M upper and lower address boundaries) is performed by load unit manager <NUM> that receives corresponding information for a load unit <NUM>, and determines an element pair (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) to store the information associated with load unit <NUM>. Load unit manager unit <NUM> may further block or stall the operation of map device <NUM> when there is no appropriate address mapping information available for an access address or when the content of an element pair (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>), (<NUM>,<NUM>) is being updated to ensure a consistent operation. This block or stall condition can continue until the appropriate address mapping information is made available or an error condition has been determined. In the latter case, an error or abort signal (not shown) may be utilized to terminate the illegal access request. Load unit manager <NUM> is further operable to request information associated with an access address via communication interface <NUM>. For this purpose interface <NUM> is coupled to communicated with the OTC controller <NUM> via a shared or a dedicated communication channel, e.g. channel <NUM> shown in <FIG>.

Referring now to <FIG>, <FIG> and <FIG>, in <FIG> elements <NUM>-<NUM> for managing instruction cache <NUM> are shown in accordance with selected embodiments of the invention. All these elements <NUM>-<NUM> are exploited by the address mapping scheme <NUM> depicted in <FIG> to inhibit external fragmentation and avoid or at least reduce the amount of internal fragmentation. Elements <NUM>-<NUM> further support a flexible split of the available internal memory <NUM> into one or multiple cache areas <NUM>, and at least one data area <NUM>. For example, by specifying a boundary <NUM> between system memory <NUM> available for application usage and instruction cache <NUM>. The exemplary implementation of map device <NUM> as depicted in <FIG> can use elements <NUM>-<NUM> of <FIG> to optimize memory available as instruction cache <NUM> without limiting the address mapping capabilities or the corresponding system performance.

A first element of this management is the split of the (virtual) address range occupied by a load unit <NUM> into multiple pages of equal size, as depicted in the upper left of <FIG>. In a preferred embodiment this page size is defined by a hardware parameter and is small enough to enable a fine granular address mapping, e.g. <NUM> Kbyte, but larger than the cache line of a traditional L1 or L2 cache (which is usually in the range of <NUM>-<NUM> byte). The start address of any such page is naturally aligned, e.g. by using a start address having bit <NUM>:<NUM> set to zero for a <NUM> kByte page. Because there is no limitation to the start or end address of a temporary load unit <NUM>, any temporary load unit <NUM> may start or end anywhere within such a page, which is depicted at the first page <NUM> and the last page <NUM> of temporary load unit <NUM> shown. Any page that is not a first or last page is further named a middle page 53X and any middle page 53X is always assigned completely to a single temporary load unit <NUM>. The content of any of the equally sized pages, when loaded from the external memory <NUM>, can be stored into a memory page within instruction cache <NUM>. The location of the memory pages can be dispersed over instruction cache <NUM> as is depicted in internal memory <NUM> of <FIG> to show an exemplary sequence of memory pages <NUM>,<NUM>, <NUM>, <NUM>, <NUM>, <NUM>. This split of a load unit into multiple equally sized pages eliminates any possibility of external fragmentation.

The start address and the end address of temporary load units <NUM> can be freely selected in accordance with the needs of the application associated with a temporary load unit <NUM>. In addition, no size limitation is imposed on a temporary load unit <NUM>, however such a limitation may be a result of the implementation of map devices <NUM>-<NUM>, as shown in the exemplary map device <NUM> depicted in <FIG>. Therefore, a potential limitation of the size of a temporary load unit <NUM> is considered an optional, non-essential limitation that may be used to optimize the hardware implementation. A size limit that is large enough to not become limiting may be chosen.

A second element of instruction cache management is a split page feature, which requires every temporary load unit <NUM> to be the same or larger in size as a single memory page. This limit ensures that any memory page is assigned to either exactly one or a maximum of two load units. For the intended use case of an instruction cache <NUM> that is structured along one or multiple function boundaries, it is always possible to combine more functions to form a larger temporary load unit <NUM> that fulfills this requirement. <FIG> depicts an example of a split page <NUM> that is shared between a first temporary load unit <NUM> (LUa) and a second temporary load unit <NUM> (LUb). It is important to note that the split unit definition corresponds to pages within the mappable address range.

Using this limitation, any first or last page of a temporary load unit <NUM> may be shared with another temporary load unit <NUM>, resulting in two page types: a full page that is not shared between temporary load units <NUM> but assigned to a single temporary load unit <NUM> or not assigned at all, and a split page that is shared between a temporary load unit <NUM> and another temporary load unit <NUM> or an unassigned area. This page type classification is assigned to every page within the mappable address range that defines the complete set of virtual addresses that can be mapped.

Another attribute used to manage space in instruction cache <NUM> is a load status of a page, which corresponds to the assignment of a memory page within internal memory <NUM> to receive the content of the associated temporary load unit(s) <NUM>. Any full page is either loaded or not loaded. Any split page may hold the content associated with one or both temporary load units <NUM> or no content. A full page that is not loaded and a split page that has not loaded any temporary load unit <NUM> is not assigned to any memory page in instruction cache <NUM>. All other combinations of page type and page status are mapped to exactly one memory page within internal memory <NUM>. Of these only a split page having only one of its two assigned temporary load units <NUM> loading is partially loaded. Any full page that is loaded and any split page having the content of both temporary load units <NUM> loaded is completely occupied. This optimizes the amount of memory that is not usable due to internal fragmentation.

<FIG> further illustrates potential states <NUM> of a full and a split page dependent on its load status. These states are: a full page that is either i) not loaded (shown in solid black in the figure, as per the legend) or ii) loaded (shown in solid white in the figure, as per the legend), or a split page (shown as partly solid black, and partly in solid white) where iii) both temporary load units <NUM> are not loaded, iv) only the first temporary load unit <NUM> is loaded, v) only the second temporary load unit <NUM> is loaded, or vi) both temporary load units <NUM> are loaded. The special case where a page is not assigned to a temporary load unit <NUM> is equivalent to a full page not loaded, and any split page where a single temporary load unit <NUM> only occupies a part of this page and the other part is unassigned is equivalent to case iii) when the single temporary load unit <NUM> is not loaded or case iv) or v) when the single temporary load unit <NUM> is loaded. The above list assumes split pages are utilized by instances of temporary load unit <NUM> in adjacent address ranges, which is a result of the minimum size limit.

The benefit of the split page features is the significant reduction of internal fragmentation. At a minimum every split page is used at least <NUM>% when there is only one temporary load unit <NUM> loaded, every time both temporary load units <NUM> assigned to a split page have been loaded then there is no internal fragmentation at all. Furthermore all management information associated with a physical memory page can be stored uniquely for every memory page; there is no requirement to record extra information for the corresponding information associated with two temporary load units <NUM> assigned to a split page. This is possible because there is dedicated information for a full page, and also a split page can exploit this scheme by defining the assignment of the associated information to either the temporary load unit <NUM> at the upper address or the temporary load unit <NUM> at the lower address. When the information associated with the other temporary load unit <NUM> is requested for a split page, then this data can be extracted by either requesting the information for the previous physical memory page (in case of an assignment to the upper address temporary load unit <NUM>) or for the following physical memory page (in case of an assignment to the lower address temporary load unit <NUM>). This permits the storage of unique information, also in case of a split page.

Referring now to <FIG>, information <NUM> for cache management is shown in accordance with selected embodiments of the invention. Functionally, the cache management information <NUM> represents three essential aspects and a beneficial aspect for every page that are detailed below, and may further include optional information, e.g. a load unit identifier <NUM>.

A first aspect of the cache management information <NUM> is address mapping information <NUM>, which identifies the address or offset of the memory page in the internal memory <NUM> (<FIG>) that holds the content of a page in the mappable address range. Every page in the mappable address range may be mapped to a physical location in internal memory <NUM>, which requires a corresponding number of storage elements for recording this information: <MAT>.

Table A <NUM> implemented in internal memory <NUM> provides a corresponding number of words, thus that the part of the virtual address that corresponds to the page (e.g. segment <NUM> in <FIG>) can be used as index <NUM> to address the words 62x of internal memory <NUM>. Any storage element within this table can at least contain the set of address bits required to identify the memory page in internal memory <NUM> to which this page is being mapped. The corresponding information may omit the intra page bits (e.g. segment <NUM> of virtual address <NUM> in <FIG>) and higher order address bits that are not mapped (e.g. segment <NUM> of virtual address <NUM> in <FIG>), thus only holding the mapped address portion (e.g. segment <NUM> of physical address <NUM> in <FIG>). When physical RAM implementing internal memory <NUM> can be addressed by a smaller number of address bits, then the size of the mapped physical address portion (e.g. segment <NUM> of physical address <NUM> in <FIG>) may be smaller than the corresponding portion of virtual address <NUM> (e.g. segment <NUM> of virtual address <NUM> in <FIG>). Using such a dense encode, every word 62x of instruction cache <NUM> may require only a subset of the bits required to form a physical address that is required to be used when mapping a virtual address.

Additional elements of cache management information <NUM> include page type <NUM> that identifies either a full or a split page, and load status <NUM> that identifies either a loaded, a not loaded or a partially loaded page. In case of a partially loaded page, it may be required to identify whether the upper or lower part of the page is loaded. Corresponding information can be made available for every page within the mappable address range. Combining the information associated with these additional elements with the address mapping information <NUM> within the Table A <NUM> may also permit usage of special encodings of the address mapping information <NUM> to reflect special combinations of page type and load status instead of a complete encoding of all states, which may save space.

A third aspect of the cache management information <NUM> is page linkage <NUM>, which can be used for two purposes: a) to link all available free pages and b) to link all pages assigned to a temporary load unit <NUM>. The linkage of all available free pages avoids the need to search for free pages; only the next page in the free list needs to be determined. The linkage of all pages assigned to a load unit avoids the need to determine pages during the eviction of a temporary load unit <NUM>. Since both aspects are mutually exclusive the same linkage information can be used for both requirements. Because both aspects are only of interest for memory pages within the internal memory <NUM>, storing this data in a second table tableB <NUM> may permit further savings.

Instruction cache <NUM> is smaller than the size of the mappable address range. Therefore there is a high likelihood that there are significantly less memory pages in instruction cache <NUM> than in the mappable address range. Since page linkage information <NUM> is only required for the pages in instruction cache <NUM>, the memory implementing Table B <NUM> can also be significantly smaller. Also for Table B <NUM> a corresponding part of the (in this case physical) address can be used to the corresponding word to determine the storage location associated with a memory page. Furthermore, the content of every word 63x within Table B <NUM> may also be a dense encoding that only records (physical) address bits of interest, equivalent to the storage within Table A <NUM>. This content can then be used as a link pointer <NUM> to determine the next (physical) memory page for every word that has a corresponding linkage.

Alternative encodings of the cache management information <NUM> are also possible, also a combined storage by collapsing Table A <NUM> and Table B <NUM> (or its contents) into a single, differently encoded table. It is further possible to use an incomplete encoding of the above information or to use alternative sources to determine related data. For example, it is possible to determine the usage of a split page from a list of all temporary load units <NUM> by querying the start addresses. Any such encodings are possible but may result in some performance impact or a less optimal amount of storage required for this information.

Referring to <FIG>,<FIG>, and <FIG> illustrates a flowchart of a method <NUM> for managing instruction cache <NUM> including related interactions between load manager <NUM>, address map device <NUM>, and cache replacement manager <NUM>, in accordance with selected embodiments of the invention. Method <NUM> depicts initialization of the corresponding management information by address map device <NUM>, the assignment of one or more memory pages within instruction cache <NUM> to a temporary load unit <NUM>, and the release of memory pages assigned to a temporary load unit <NUM> by evicting a selected temporary load unit <NUM>.

When OTC controller <NUM> is enabled, address map device <NUM> performs initialization process <NUM>, which may be performed under software control by writing related control registers that provide the information required by initialization process <NUM>. The main purpose of initialization process <NUM> is to record corresponding information in storage elements <NUM> managed by map devices <NUM>-<NUM>. The table(s) <NUM>, <NUM> depicted in <FIG> can be used to store the initialization information.

Initialization process <NUM> includes two functions that can performed by address map device <NUM> independently and in any order or concurrently: a) the specification of instruction cache <NUM> and b) the specification of the page type for every page within the mappable address range. The specification of instruction cache <NUM> utilizes one or more address ranges within internal memory <NUM> that can be specified e.g. by software via register programming. Initialization process <NUM> then assigns every memory page within an address range to the list of free pages in process <NUM>. The second process <NUM> specifies the page type for every page within the mappable address range, for example, by a repeated specification of the address range assigned to a temporary load unit <NUM> by software via register programming. The address range can be utilized to determine whether every page is a full or a split page when the address range of the page is assigned to more than one temporary load unit <NUM>. Process <NUM> also marks every such page as being unassigned, which reflects that the content of this page has not yet been loaded into internal memory <NUM>. Since both processes <NUM> and <NUM> operate on a different data set, the set of memory pages within the internal memory <NUM>, and the set of (virtual) pages within the mappable address range, they can be performed independently unless the internal tables recording both data sets have been combined.

The assignment of memory pages to a temporary load unit <NUM> is performed by address map device <NUM> upon request by load manager <NUM> while the content of a load unit <NUM> is being loaded from the external memory <NUM>. When there is no ongoing load operation, load manager <NUM> waits for a load request <NUM>, which may be provided at any time by a load entity queue <NUM>. Upon receiving such a request, the load manager will perform the load operation <NUM>, which reads the content of a requested load unit <NUM> from the external memory <NUM>, usually within an internal buffer. Every time the content for one page in the virtual memory of the requested load unit <NUM> has been loaded by process <NUM>, load manager <NUM> will request the storage location for this page from address map device <NUM>. Upon receiving the appropriate storage location in form of a memory page within instruction cache <NUM>, load manager <NUM> stores the content loaded into this memory page within process <NUM>. The next page is loaded by continuing process <NUM> until load manager <NUM> determines that temporary load unit <NUM> has been completely loaded in process <NUM>. Direct storage of the content loaded from the external memory <NUM> into a memory page is also possible by determining the memory page for performing the storage before starting/continuing the load operation itself.

Specific processing may be required in process <NUM> when the loaded content of a first or last page of a temporary load unit <NUM> is to be stored within a memory page of instruction cache <NUM>. When such a page is a full page, then no special processing is required. When such a page is a split page, then only a portion of this page is assigned to the requested load unit, and only this portion may be written with the loaded content. Therefore process <NUM> may only write the upper part of a split page when this is the first page of a temporary load unit <NUM>, and the lower part of a split page when this is the last page of a temporary load unit <NUM>. Any part of the split page that is not related to the requested load unit, but either unassigned or assigned to another temporary load unit <NUM> is not be modified by process <NUM>.

Corresponding processing by address map device <NUM> is depicted at the right side of <FIG>. When load manager <NUM> requests a storage location for the content that has been loaded, address map device <NUM> first checks whether this page is a split page in process <NUM> and whether this page has already been loaded in process <NUM>. Since only the first and the last page of a temporary load unit <NUM> can be a split page, both processes <NUM> and <NUM> can be omitted for any other page of a temporary load unit <NUM>, which is depicted as optional using dashed lines. In this case processing unconditionally continues with process <NUM> to determine the next free page that can be assigned to a temporary load unit <NUM>. In case of a split page that has already been loaded, it is not required to determine a free page, but the loaded content can be stored into the part of this split page that has not yet been loaded and is assigned to the requested load unit. When process <NUM> results in filling the other (not yet assigned) part of a split page, then the corresponding memory page will be basically a full page that is assigned to two temporary load units <NUM>. This can be achieved by storing the loaded content into the selected memory page as has already been described in process <NUM>.

In any other case address map device <NUM> can determine a free page in process <NUM> by retrieving the next page from the list of free pages generated by process <NUM>. When there is a free page available, as determined in process <NUM>, processing can continue with process <NUM> as has been already described earlier. When there is no free page available, e.g. because the list of free pages is empty, then address map device <NUM> requests a temporary load unit <NUM> to be evicted in process <NUM> from cache replacement manager <NUM>. Upon such a request, cache replacement manager <NUM> determines a temporary load unit <NUM> to be evicted and provides the temporary load unit <NUM> to be evicted in process <NUM>. The address map device <NUM> then evicts the corresponding temporary load unit <NUM> from instruction cache <NUM> and marks all pages associated solely with the evicted temporary load unit as free. The free pages are then added to the list of free pages in process <NUM>.

Processing then continues by determining a free page within the process <NUM>.

There are two special cases for the described processes that are related to the management of split pages. A first special case occurs when the first or last page of the temporary load unit <NUM> to be evicted is a split page that is also assigned to another load unit that has been loaded. In this case the process <NUM> does not mark this page as a free page, but changes the state of the page from a full page to a partially loaded page that is still assigned to the other loaded unit. Thus the corresponding eviction operation may provide less free pages than are occupied by the evicted temporary load unit <NUM>. A second special case occurs when the eviction of the temporary load unit <NUM> in process <NUM> does not provide any free pages. This can occur when there are only two split pages assigned to the temporary load unit <NUM> to be evicted, and both pages are also assigned to another temporary load unit <NUM> that has been loaded. In this case only the state of these memory pages is changed from a full page to a partially loaded page, but none of these two pages is a free page after the eviction. In this case another iteration of the eviction processing is required.

By now it should be appreciated that in some embodiments, a processing system comprises a microcontroller device and an external memory device external to the microcontroller device. The external memory device is coupled to the microcontroller device and stores one or more application codes. Each of the application codes comprises one or more load units, and the load units include executable instructions and/or data. The microcontroller device includes bus masters configured to execute the application codes, a random access memory (RAM) device internal to the microcontroller device and coupled to the bus masters via an interconnect. The RAM device is configured to store copies of a subset of the load units. An address mapping device is coupled to an access path from the bus master to the RAM device. The address mapping device is configured to modify a portion of an access request from a bus master that represents an address of the requested information. A cache controller device is coupled to the RAM device and the external memory device. The cache controller device is configured to partition a copy of a second one of the load units into one or more segments, wherein the segments have a length up to a page size of the RAM device. The cache controller device can further load the segments into one or more of the pages with available space in the RAM device, and maintain a record of the one or more pages into which the segments were loaded.

In another aspect, the size of each of the load units can be equal to or larger than a size of a single page in the RAM device.

In another aspect, two or more of the load units can have different sizes.

In another aspect, a start address of at least one of the segments in a page of the RAM device may not be a first address of the page.

In another aspect, the cache controller device can be further configured to evict a previously loaded copy of one of the load units from the RAM device to create available space in one or more pages in the RAM device.

In another aspect, the cache controller device is further configured to allocate one segment associated with one of the load units to one of the pages, wherein the one segment occupies all of the one of the pages. The cache controller device can allocate one segment associated with one of the load units to one of the pages, wherein the one segment occupies only a first or second portion of the one of the pages and a remaining portion of the one of the pages is available as free space, and allocate two segments associated with two different load units to one of the pages.

In another aspect, the cache controller can be further configured to assign a load status to each page in the RAM device, the load status indicating one of: a page is available when no segment of one of the load units has been loaded into the page, the page is "in use" when at least one segment of one of the load units allocated to the page has been loaded into the page, and a page is available for storing additional content when a segment of one of the load units has been loaded into the page and there is additional space available to store a segment of another one of the load units.

In another aspect, the processing system can further comprise a first mapping table that specifies a physical location within the RAM device for at least some of the one or more pages that may receive at least one segment of a load unit.

In another aspect, one of the first mapping table or a second mapping table includes load status information that indicates whether: i) content of a page is not loaded, ii) the page holds a single segment and is loaded, iii) the page holds two segments and the two segments are loaded, iv) the page holds two segments and only one of the two segments associated with a lower part of addresses within the page is loaded, or v) the page holds two segments and only one of the two segments associated with an upper part of addresses within the page is loaded.

In another aspect, the mapping table can further include information to link all pages assigned to segments associated with a specified load unit in the RAM device.

In other embodiments, a method of managing variable size load units of application codes in a processing system comprises identifying pages of a random access memory (RAM) device to store copies of load units from an external memory device upon request by a bus master in the processing system. The RAM device is internal to an integrated circuit device that includes the bus masters, and the external memory device is external to the integrated circuit device. The bus masters executes the application codes, and each of the application codes comprises one or more load units that include executable program instructions. At least some of the load units have different sizes from one another. A page type indicator is determined for an identified page, wherein a first page type indicates whether the identified page is a split page to store a segment of each of two different load units.

In another aspect, each of the load units can be at least a page long. The method can further comprise storing segments of one of the load units in one of: a portion of a split page, and a page that is not a split page, and maintaining a list of pages storing the segments of the one of the load units.

In another aspect, the method further comprises, when a request for a first load unit is received, reading contents of the requested first load unit from the external memory, splitting contents of the first load unit into one or more segments, and requesting a storage location for one segment of the requested first load unit in the RAM device. When the storage location is a split page, and a portion of the split page is already occupied by a second load unit, a remaining portion of the split page is used to store the one segment. Otherwise, when the storage location is not a split page, a free page in the RAM device is determined, usage of the determined free page as storage for the one segment is recorded, and the one segment in the determined page of the RAM device is loaded.

In another aspect, the method can further comprise, when a request for one of the load units is received, reading contents of the requested load unit from the external memory, requesting a storage location for one page of the requested load unit in the RAM device, determining a free page in the RAM device, loading the one page in the free page of the RAM device, and recording the storage location for the one page.

In another aspect, the method can further comprise, when the free page is a split page, assigning the at least a segment of one of the two load units to the split page, wherein an upper part of the split page is used to store a first page of the one of the two load units and a lower part of the split page is used to store a last page of the one of the two load units.

In another aspect, the method can further comprise determining a load status for each of the pages to indicate whether a page is loaded, not loaded, upper partially loaded, and lower partially loaded.

In another aspect, the method can further comprise updating linkage information for the one of more pages to indicate one of: assignment of a free page to store one of the one or more segments of a load unit, assignment of a split page to become a first or a last page storing at least one of the one or more segments of a load unit, and assignment of page assigned to a load unit being evicted to become a free page.

In another aspect, the method can further comprise, in response to the request by the bus master, using a portion of a virtual address in the request to determine whether a requested address is within a map address range of the identified pages.

In another aspect, the method can further comprise, in response to the request by the bus master, comparing a portion of the virtual address to a start and end address of a load unit to map the load unit to a physical address in the RAM device.

In another aspect, the method can further comprise, in response to a request by a bus master, using a first portion of a virtual address in the request to determine whether a requested address is within a map address range of the identified pages, using a second portion of the virtual address in the request to determine the storage location of the corresponding page and use this as a mapped address, and using a third portion of the virtual address that may overlap with the first and second portion of the virtual address, comparing the third portion to a start and end address of a load unit to identify correctness of using the mapped page address to determine the mapped address for the request by the bus master.

Although the described exemplary embodiments disclosed herein are directed to methods and systems which may be applied to Systems and methods for managing cache replacement, the present invention is not necessarily limited to the example embodiments illustrate herein, and various embodiments of the circuitry and methods disclosed herein may be implemented with other devices and circuit components. Thus, the particular embodiments disclosed above are illustrative only and should not be taken as limitations upon the present invention, as the invention may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. Accordingly, the foregoing description is not intended to limit the invention to the particular form set forth, but on the contrary, is intended to cover such alternatives, modifications and equivalents as may be included within the spirit and scope of the invention as defined by the appended claims so that those skilled in the art should understand that they can make various changes, substitutions and alterations without departing from the spirit and scope of the invention in its broadest form.

Claim 1:
A processing system (<NUM>) comprising:
a microcontroller device (<NUM>);
an external memory device (<NUM>) external to the microcontroller device, the external memory device coupled to the microcontroller device and storing one or more application codes, wherein each of the application codes comprises one or more load units (<NUM>), and the load units include executable instructions and/or data;
the microcontroller device including:
bus masters (<NUM>, <NUM>, <NUM>, <NUM>) configured to execute the application codes;
a random access memory, RAM, device internal to the microcontroller device and coupled to the bus masters via an interconnect, the RAM device configured to store copies of a subset of the load units;
an address mapping device (<NUM>, <NUM>, <NUM>, <NUM>) coupled to an access path from the bus masters to the RAM device, the address mapping device configured to modify a portion of an access request from a bus master that represents an address of the requested information;
a cache controller device coupled to the RAM device and the external memory device, the cache controller device configured to:
partition a copy of one of the load units into one or more segments, wherein the segments have a length up to a page size of the RAM device;
load the segments into one or more of the pages with available space in the RAM device;
maintain a record of the one or more pages into which the segments were loaded,
wherein the cache controller device is further configured to perform each following operation independently of one another:
allocate one segment associated with one of the load units to one of the pages, wherein the one segment occupies all of the one of the pages;
allocate one segment associated with one of the load units to one of the pages, wherein the one segment occupies only a first or second portion of the one of the pages and a remaining portion of the one of the pages is available as free space; and
allocate two segments associated with two different load units to one of the pages.