WO2014056534A1

WO2014056534A1 - Context-sensitive data-cache

Info

Publication number: WO2014056534A1
Application number: PCT/EP2012/070131
Authority: WO
Inventors: Sascha Uhrig
Original assignee: Technische Universitaet Dortmund
Current assignee: Technische Universitaet Dortmund
Priority date: 2012-10-11
Filing date: 2012-10-11
Publication date: 2014-04-17
Anticipated expiration: 2015-04-11

Description

Context-sensitive Data-Cache

TU Dortmund, Germany

The present invention relates to a Context sensitive Data-Cache. Background of the Invention

Within an ever growing number of devices multi-core processors may be found. Exemplary devices are mobile phones, video game consoles, set-top boxes, but also within other devices multi-core-processors are found, such as airplanes, trains and automotives.

Typically, today's processors are equipped with a cache memory providing a higher access speed than traditional main memory. In case of a multi CPU arrangement or a multi-core processors, i.e. a processor providing two or more central processing units (CPU), having access to the same main memory by using cache memories, a writing access by a central processing unit may lead to inconsistencies towards other central processing units if no counter-measures are taken.

To overcome such problems, cache coherence protocols have been implemented. However, when the number of coherent cache memories increases, the complexity of the cache coherence protocols increases dramatically. In turn also the administrative data to be handled and to be exchanged increases thereby negatively affecting the complexity of the cache controllers and leading to an increase of the necessary size on a chip as well as to an increase of power consumption. Also, an increasing demand towards hard real-time functionality is observed within these devices. Hard real time functionality typically affords meeting of a deadline without failure. However, the known cache coherence protocols respectively the cache coherence arrangements do not allow for hard real time functionality since the data of the cache may be changed by a CPU thereby rendering it almost impossible to guarantee a runtime which is a necessary requirement within hard real-time functionality. It is an object of the invention to provide a Context-sensitive Data-Cache which circumvents the problems known from prior art arrangements.

The object is solved by a Method for a Context-sensitive Data-Cache for Multi-core- environments. There, Data of an upstream located memory is temporarily stored for quick access, whereby Data may be private Data, which is used exclusively by a respective core of said Multi-core-environment, or shared Data, which may be used by a plurality of cores of said Multi-core-environment. A use may be a reading or writing access towards the data. Shared Data is distinguished by private Data by means of an indication. A writing use of shared data is exclusive at a point in time, whereby when said exclusive use terminates the shared data is marked as invalid.

In a further embodiment, terminating exclusive use of shared data comprises write-back of the written Data towards said upstream located memory.

In yet another embodiment the indication allowing for distinguishing private Data from Shared Data is received when accessing Data.

In still a further embodiment the indication comprises a hierarchy allowing for distinguishing certain levels of shared data allowing for one of said plurality of cores of said Multi-core- environment to access shared data in nested critical regions, whereby a first critical region A comprises a nested second critical region B as if they would be private data while one or more other Cores of said Multi-core-environment are not allowed to access said data. The object is also solved by a Context-sensitive Data-Cache for Multi-core-environments. There, Data of an upstream located memory is temporarily stored for quick access, whereby Data may be private Data, which is used exclusively by a respective core of said Multi-core- environment, or shared Data, which may be used by a plurality of cores of said Multi-core- environment. A use may be a reading or writing access towards the data. The Context- sensitive Data-Cache comprises a first storage entity for storing Data, a second storage entity for storing an indication allowing for distinguishing private Data from shared Data within said first storage entity, a third storage entity for storing information whether Data within the Cache is valid or not, an Administration entity allowing to access Data within the first storage entity based on said indication stored in said second storage entity, whereby a writing use of shared data is exclusive at a point in time, whereby when said writing use terminates only the shared data are marked as invalid within the third storage entity. In a further embodiment the Administration entity instigates write-back of the written Data towards said upstream located memory on terminating writing use of shared data.

In yet another embodiment the indication allowing for distinguishing private Data from Shared Data stored in said second storage entity is received when accessing Data.

In still a further embodiment the indication stored in said second storage comprises a hierarchy allowing for distinguishing certain levels of shared data allowing for two or more Cores of said Multi-core-environment to access shared data in nested critical regions as if they would be private data while one or more other Cores of said Multi-core-environment are not allowed to access said data.

Further advantageous embodiments are subject to the detailed description. In the following, the invention will be described in further detail with respect to the accompanying figures in which:

Fig. 1 shows a general set-up of a set-up in which the invention may be embodied,

Fig. 2 shows a state machine of a context-sensitive data-cache according to an embodiment of the invention,

Fig. 3 shows an exemplary flowchart according to an embodiment of the invention, and Fig. 4 shows an embodiment of cache data according to an embodiment of the invention.

In Figure 1 a general set-up of a set-up in which the invention may be embodied is shown.

There a plurality of processors CPU 1 ; CPU 2; CPU 3; CPU 4 may access a common data cache D-MEM.

The plurality of processors CPU 1 ; CPU 2; CPU 3; CPU 4 may be arranged within a single chip, i.e. a multi-core processors as indicated by the dashed box M-CPU, or may be arranged as separate entities. Hence, the wording of a core and a central processing unit with respect to the invention may be used in an interchanging manner. Also Multi-core- environment may be used collectively for a multiprocessor arrangement of individual central processing units or for multi-core-processors.

The data cache CDC is controlled by a cache controller CC. For ease of controlling, the cache controller CC may access certain memories intended for storing parameter pertaining to the status of certain data stored within the data-cache D-MEM such as l-MEM and/or V- MEM. A data cache stores data which may be used by and for several central processing units in contrast to an instruction cache storing instructions intended for a particular central processing unit. Even though the data cache and the further memory for storing parameter are shown as independent entities they may be integrated and may be arranged in any suitable manner. Such a data cache CDC is arranged with respect to a Central Processing Unit, i.e. in figure 1 , with respect to CPU 2. Although not particular detailed in Figure 1 , also the other CPUs CPU 1 , CPU 3 and CPU 4 may be equipped with a context sensitive data cache CDC as indicated by the dashed boxes.

Upstream to the data cache D-MEM there might be further cache or a main memory. The data-cache D-MEM temporarily stores data intended to be stored or stored in an upstream located memory MEM for quick access by one or more of said processors CPU 1 ; CPU 2; CPU 3; CPU 4.

As the invention is not limited to a particular choice of a further cache or a main memory within the following description it is assumed that the upstream located memory MEM is a main memory. Now turning to figure 3 showing an exemplary flowchart according to an embodiment of the invention, the invention will be described in further detail.

First we assume that data may be classified as private data or shared data. Private data is used exclusively by a respective core CPU 1 ; CPU 2; CPU 3; CPU 4 of said Multi-core- environment. In contrast shared Data may be used by a plurality of cores CPU 1 ; CPU 2; CPU 3; CPU 4 of said Multi-core-environment. Said differentiation is not performed in known cache controllers as such a differentiation would lead to an increased complexity leading to the known negative effects as described above. However, when analyzing typical cached data, it becomes apparent that the majority of data stored is private data, while shared data only contributes to a minor share. In addition also the usage frequency of shared data is rather low compared to private data.

A use may be any kind of reading or writing access as is shown in Figure 1 by the double sided arrows.

Λ- Thus within the invented cache-sensitive data cache D-MEM data of an upstream located memory MEM is temporarily stored for quick access in a step 100. The data may be private or shared data as previously indicated. Now, a respective core is using said data stored in the cache-sensitive data cache D-MEM in a step 200, whereby said use may be e.g. a reading access or a writing access. The exact process of how the cache controller identifies an access towards data which is temporarily stored in the cache-sensitive data cache D-MEM is of no importance for the general idea of the invention and is therefore not further detailed.

The access towards certain data as described above is then examined as to the nature of the accessed data. This may be accomplished by means of an indication \ i , l₂.

The indication l-i, l₂ may be such that it may only be distinguished between shared or private data, e.g. by means of a single binary attribute \

for shared data and unset I _! =0 for private data or vice versa or it may be such that the indication comprises a hierarchy l-i, l₂ allowing for distinguishing certain levels of shared data allowing for a core of said plurality of cores CPU 1 ; CPU 2; CPU 3; CPU 4 of said Multi-core-environment to access shared data in nested critical regions. E.g. in such a hierarchy it may be foreseen that a core, e.g. CPU 1 , may have a first critical region A and a nested second critical region B, whereby the second critical region B is comprised within the first critical region. That means, if data is accessed within a critical region B than such data needs to be written back at the latest on leaving critical region B. Data of critical region A however may stay within the context-sensitive data-cache CDC .. Then it may be foreseen that l-i may be used to indicate whether data is shared or private with respect to a first critical region A, while l₂ may be used to indicate whether data is shared or private with respect to a nested critical region B.

Irrespective of a hierarchy, a writing use of shared data is exclusive at a point in time. Once such exclusive usage of data is terminated, the shared data is marked as invalid in a step 400. Thereby it is established that any access towards such data will result in a reloading operation thereby enforcing that the data fetched from an upstream located memory is valid. Depending on the cache strategy it may be foreseen that terminating exclusive use of shared data comprises the step of writing-back of the written Data towards said upstream located memory MEM indicated as a step 300. Alternatively, it may be foreseen that any writing access towards the cache-sensitive data cache D-MEM is immediately stored in the upstream located memory 300 (write-through) if said data is marked shared.

Although in the foregoing data has been used in a general manner, it is to be understood that data and the marking of private or shared may apply to a certain amount of data according to the overall cache topology, i.e. it may pertain to cache lines or cache blocks.

In an advantageous embodiment it may be foreseen that said indication allowing for distinguishing private Data from Shared Data is received when accessing Data in step 200.

The methods described before may be embodied in a respective hardware arrangement as will be detailed in the following.

A context-sensitive data-cache CDC for multi-core-environments may comprise as shown in Fig. 1 by the dotted boxes a first storage entity for storing Data D-MEM, a second storage entity for storing an indication l-MEM allowing for distinguishing private Data from shared Data within said first storage entity, a third storage entity for storing information V-MEM whether Data within the Cache is valid or not, an Administration entity CC allowing to access Data within the first storage entity D-MEM based on said indication \ i , l₂ stored in said second storage entity l-MEM, whereby a writing use of shared data is exclusive at a point in time, whereby when said writing use terminates only the shared data are marked as invalid within the third storage entity l-MEM.

Hence, the structure of the context-sensitive data-cache is less complicated and affords less space. Consequently also the cache controller as well as the protocols is less complicate and therefore does not occupy much space. Consequently energy-efficiency is also improved by the invention.

In addition, as the structure is less complicated, timing is predictable to a level allowing for hard real time functionality. Hence, multi-core processors may now also be employed in functions that were not accessible with prior art cache systems. Therefore, cost savings may be achieved as modern processors may be used which tend to implement multi-core strategies, thereby let old stylish single-core processors become redundant. From a programmer's perspective, it may be foreseen that shared data may be accessed via a respective indication, e.g. a mutex or a semaphore. In the following a short example of a program is shown exemplarily without any binding effect towards a particular programming language:

While (true) { / / no shared-data in CDC

EnterCriticalSection(A); / / switch to shared mode

getNewWorkpackage(); / / mark all cache-misses

ExitCriticalSection(A); / / invalidate all marked data (+ write-back of data)

/ / no more shared-data in CDC

doPrivateWork(); // Cache offering normal functionality, no marking

EnterCriticalSection(B); / / switch to shared mode

updateSharedResultse(); / / mark all cache-misses

ExitCriticalSection(B); / / invalidate all marked data (+ write-back of data)

}

Now assuming in context with the above programming examples an architecture having a main memory MEM and a plurality of cores CPU 1 ; CPU 2; CPU 3; CPU 4. Each of said plurality of cores CPU 1 ; CPU 2; CPU 3; CPU 4 having assigned a respective Context- sensitive Data-Cache D-MEM. Now each core may execute its own thread, whereby each thread may operate on shared and/or private data. All threads may then have access towards a global variable shared while a variable private may be declared locally within each thread. In the following another short example of a program is shown exemplarily without any binding effect towards a particular programming language: void Snipplet( void )

{

/^* Uncritical

private++; /^* Critical ^*/

EnterCriticalSection( pCs );

shared++;

LeaveCriticalSection( pCs );

/^* Uncritical

private--;

} Now for ease of understanding no nested critical regions are assumed.

A non-critical region is a code region within which only access towards private data is allowed. In turn a critical region is a code region within which access may be made towards data which may be shared or private.

If an access outside a critical region is made, i.e. a region accessing only private data, than the context-sensitive data-cache CDC may operate as any known data-cache, i.e. it may provide cache-hits or cache-misses. Such cache may implement any convenient mechanism such as FIFO (First In First Out), LRU (Least Recently Used), LFU (Least Frequently Used), Random, Climb, Clock, Optimal, etc to import new data into the cache as a replacement to old data in the cache. Furthermore such cache may implement any convenient writing scheme, such as write-back or write-through, etc. There, no use of a cache coherence protocol is necessary.

If an access inside a critical region is made, e.g. a region that could access shared data, than the context-sensitive data-cache CDC is recognizing said access as shared. Within a critical region, a certain processor may operate like before, i.e. any kind of importing new data replacing old data and / or writing scheme may be implemented. However, on a cache-miss a respective data is marked. Depending on the implemented writing strategy, either the modified data is updated immediately (write-through) or on leaving a critical region (writeback). Afterwards, as the data is updated in upstream memory, the cache may return to private mode. Thereby it is ensured that no shared data is left in a local context-sensitive data-cache CDC but all updated data is present in upstream located memory MEM. If another access is to be made towards such a critical region, the updated data has to be fetched first from upstream located memory MEM. Now turning to an example showing nested critical regions but being based on the same assumptions as described above.

Again a non-critical region is a code region within which only access towards private data is allowed. In turn a critical region is a code region within which access may be made towards data which may be shared or private. // until here no Shared-Data in Cache,

// Cache may comprise private data

enterCriticalSection(A); // switch to shared Mode in a first level indicated e.g. by

II

doSomeWorkAI (); // mark all cache-misses (if necessary write-trough) enterCriticalSection(B); // switch to nested shared Mode in a second

// level indicated e.g. by l₂

doSomeWorkB(); // mark all cache-misses (if necessary write-trough) exitCriticalSection(B); // invalidate all marked cache lines within second level

// indicated e.g. by l₂ (if necessary write-back of data) // switch back to shared Mode

// in a first level indicated e.g. by l-i doSomeWorkA2(); // mark all cache-misses (if necessary write-trough) exitCriticalSection(A); // invalidate all marked cache lines within first level

// indicated e.g. by \^_\ (if necessary write-back of data)

// switch back to private Mode

// from here on no Shared-Data in Cache,

// Cache may comprise private data

I.e. even though there is a nested region B, by virtue of the hierarchy provided by indications l-i , l₂ it is possible to ensure that data is stored in upstream memory MEM which is modified, while data where there is no need to store said data in upstream memory MEM may stay. On exit of a nested critical region, e.g. region B in the above example, only concerned cache data of said nested region needs to be processed.

Hence, within the invention no cache-coherence-protocol needs to be implemented between different data-caches.

Turning towards a possible implementation which will be described along figure 4 and assuming a cache organization in cache lines, then with respect to nested critical regions at least a bit \i, l₂ is proposed for usage of indication of shared data, indicated as Data, with respect to each hierarchy level. Now, by means of Indication V, it may be decided whether the data in the cache CDC is a true copy of data stored in upstream memory MEM or not.

In case the CDC implements a write-through approach, on a writing access the data will be stored immediately in upstream memory MEM.

In case the CDC implements a write-back approach, on a writing access the data may be written back at a later point in time. To indicate that the data has been changed locally, an indication regarding a modification may be stored, e.g. as part of the attributes ATR. On leaving a critical region, the valid indication V as well as the indication of a modification and the indication of shared data , l₂ may be used for determining whether to write-back the cache-line to the upstream memory MEM or not

AND M AND not(l₁, OR l₂)). I.e. valid data which is modified and marked as shared data needs to be stored in upstream located memory MEM on leaving a critical region.

Independent from the write strategy, data indicated as valid V and as shared data \-_\, l₂ is marked as invalid and not shared on leave of a critical region (V_new=V₀|_d AND not(l₁ OR l₂)). Such process may easily be adopted in parallel for all cache-lines thereby reducing respectively eliminating possible overhead. Thereafter all cache-lines having a set invalid indication V and a corresponding indication of shared data \^_\, l₂ shall be deleted. The process may be similar to that of the Write-T rough strategy.

Fig.2 shows a state machine of a context-sensitive data-cache according to an embodiment of the invention. There a signal towards a state change is issued once a core is starting to operate on shared data respectively terminates access towards shared data. I.e. once a core starts executing critical code portions accessing shared data, the cache changes into a SHARED state. If now a cache-miss is detected for any reason, e.g. the data is not yet loaded, the respective data is loaded from upstream located memory MEM into the context- sensitive data-cache CDC.

A marked , l₂ and as changed indicated V data-block will then be processed according to the write strategy. I.e. on changing the state towards NON-SHARED the respective changed data is stored within main memory MEM and the respective data-block is invalidated and/or deleted. As no other core is allowed to operate on the data as long as it is marked shared and accessed by another core, cache coherence is guaranteed. Furthermore, as„shared" data may only be within a critical region, any access, in particular the first access, within a critical region will lead to a cache-miss leading to an updated data.

Claims

Method for a Context-sensitive Data-Cache (D-MEM) for Multi-core-environments, whereby Data of an upstream located memory (MEM) is temporarily stored (100) for quick access, whereby Data may be private Data, which is used exclusively by a respective core (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core-environment, or shared Data, which may be used by a plurality of cores (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core-environment, whereby use (200) may be a reading or writing access towards the data, whereby shared Data is distinguished by private Data by means of an indication (l-i , l₂), whereby a writing use of shared data is exclusive at a point in time, whereby when said exclusive use terminates (400) the shared data is marked as invalid.

Method according to claim 1 , characterized in that terminating exclusive use of shared data comprises write-back (300) of the written Data towards said upstream located memory (MEM).

Method according to any one of claims 1 or 2, characterized in that said indication allowing for distinguishing private Data from Shared Data is received (200) when accessing Data.

Method according to any one of claims 1 to 3, characterized in that said indication comprises a hierarchy (l-i , l₂) allowing for distinguishing certain levels of shared data allowing for one of said plurality of cores (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core-environment to access shared data in nested critical regions, whereby a first critical region A comprises a nested second critical region B,.

Context-sensitive Data-Cache (D-MEM) for Multi-core-environments, whereby Data of an upstream located memory (MEM) is temporarily stored for quick access, whereby Data may be private Data, which is used exclusively by a respective core (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core-environment, or shared Data, which may be used by a plurality of cores (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core- environment, whereby use may be a reading or writing access towards the data, comprising:

• a first storage entity for storing Data (D-MEM), • a second storage entity for storing an indication (l-MEM) allowing for distinguishing private Data from shared Data within said first storage entity,

• a third storage entity for storing information (V-MEM) whether Data within the Cache is valid or not,

• an Administration entity (CC) allowing to access Data within the first storage entity (D-MEM) based on said indication (l-i , l₂) stored in said second storage entity (l-MEM), whereby a writing use of shared data is exclusive at a point in time, whereby when said writing use terminates only the shared data are marked as invalid within the third storage entity (l-MEM).

Context-sensitive Data-Cache for Multi-core-environments according to claim 5, characterized in that said Administration entity (CC) instigates write-back of the written Data towards said upstream located memory (MEM) on terminating writing use of shared data.

Context-sensitive Data-Cache for Multi-core-environments according to any one of claims 5 or 6, characterized in that said indication (l-i , l₂) allowing for distinguishing private Data from Shared Data stored in said second storage (l-MEM) entity is received when accessing Data.

Context-sensitive Data-Cache (CDC) for Multi-core-environments according to any one of claims 5 to 7, characterized in that said indication l₂) stored in said second storage (l-MEM) comprises a hierarchy allowing for distinguishing certain levels of shared data allowing for one of said plurality of cores (CPU 1 ; CPU 2; CPU 3; CPU 4) of said Multi-core-environment to access shared data in nested critical regions, whereby a first critical region A comprises a nested second critical region B.