(return back to recipe list)









  1. System to model and assumptions
  2. Typical solution
  3. Possible analysis
  4. Case study




System to model and assumptions

In this recipe, we describe an architecture where computing units have shared hardware resources such as a cache unit.

We assume an uniprocessor system with one level of direct-mapped instruction cache that consists of independent stricly periodic tasks. A task has an associated control flow graph (CFG) described by the attribute CFG_Name. This CFG is used to compute a task's cache access profile, which is required to run any cache related preemption delay (CRPD) analyses implemented in Cheddar.

Typical solution

Here is a simplified example of this recipe (which can be downloaded here): 
package Cache_Analysis

public 
    with Cheddar_Multicore_Properties;
    with Cheddar_Transformation_Properties;
    with memory_units;

    processor CPU_01
    end CPU_01;

    processor implementation CPU_01.Core_01
    subcomponents
        L1_Instruction_Cache : memory memory_units::Cache.impl {
        Memory_Size => 1024Bytes;
        Cheddar_Multicore_Properties::Line_Size => 16Bytes;
        Cheddar_Multicore_Properties::Cache_Type => Instruction_Cache;  	    
        Cheddar_Multicore_Properties::Cache_Level => 1;
        Cheddar_Multicore_Properties::Associativity => 1;
        Cheddar_Multicore_Properties::Cache_Size => 1024;
        Cheddar_Multicore_Properties::Block_Reload_Time => 1 us .. 2 us;
        };
    properties
        Scheduling_Protocol=>(POSIX_1003_HIGHEST_PRIORITY_FIRST_PROTOCOL);	
    end CPU_01.Core_01;	
    ------------------------------------------------
    system Cache_benchmark
    end Cache_benchmark;

    system implementation Cache_benchmark.impl
    subcomponents
        Hard : processor CPU_01.Core_01;
        Soft : process Malardalen.impl;
    properties
        Actual_Processor_Binding => (reference (Hard)) applies to Soft;
        Cheddar_Transformation_Properties::Exported_Attribute_Time_Units => MicroSecond;
    end Cache_benchmark.impl;
        
    process Malardalen
    end Malardalen;

    process implementation Malardalen.impl
    subcomponents
        Bs : thread Task_Bs;
        Fac : thread Task_Fac;
        Fibcall : thread Task_Fibcall;
        InsertSort : thread Task_InsertSort;
    end Malardalen.impl;

    thread Task_Bs
    properties
        period => 1000us;
        Dispatch_Protocol => Periodic;
        Compute_Execution_Time => 76us..76us;
        Deadline => 1000us;
        Cheddar_Multicore_Properties::CFG_Name => "CFG_bs";
        Cheddar_Multicore_Properties::CFG_Relocatable => True;
        Cheddar_Multicore_Properties::Text_Memory_Start_Address => 0;
    end Task_Bs;

    thread Task_Fac
    properties
        period => 1500us;
        Dispatch_Protocol => Periodic;
        Compute_Execution_Time => 125us..125us;
        Deadline => 1500us;
        Cheddar_Multicore_Properties::CFG_Name => "CFG_fac";
        Cheddar_Multicore_Properties::CFG_Relocatable => True;
        Cheddar_Multicore_Properties::Text_Memory_Start_Address => 0;
    end Task_Fac;

    thread Task_Fibcall
    properties
        period => 1500us;
        Dispatch_Protocol => Periodic;
        Compute_Execution_Time => 300us..300us;
        Deadline => 1500us;
        Cheddar_Multicore_Properties::CFG_Name => "CFG_fibcall";
        Cheddar_Multicore_Properties::CFG_Relocatable => True;
        Cheddar_Multicore_Properties::Text_Memory_Start_Address => 0;
    end Task_Fibcall;

    thread Task_InsertSort
    properties
        period => 2000us;
        Dispatch_Protocol => Periodic;
        Compute_Execution_Time => 450us..450us;
        Deadline => 2000us;
        Cheddar_Multicore_Properties::CFG_Name => "CFG_insertsort";
        Cheddar_Multicore_Properties::CFG_Relocatable => True;
        Cheddar_Multicore_Properties::Text_Memory_Start_Address => 0;
    end Task_InsertSort;

end Cache_Analysis;
This model assume the following definition from package memory_units (from here):: 
package memory_units
public 	
	memory Cache
	end Cache;

	memory implementation Cache.impl
	end Cache.impl;
	
	...
The model above contains a processor component (called CPU_01). The processor has a single core unit (called Core_01) and a cache (called L1_Instruction_Cache). The solution models 4 threads : Task_Bs, Task_Fac, Task_Fibcall, and Task_InsertSort. They are programs taken from the Malardalen benchmark.

Each thread is defined as periodic, with a deadline, a priority and an execution time. Execution time of thread is defined by a time interval, with a worst case and a best case specified with the Compute_Execution_Time property. All those properties are defined inside the process component: notice the applies to to make reference to the thread at which the property value has to be assigned.

Each task has an associated control flow graph (CFG) stored in an external file with the name given by the attribute CFG_Name. Cheddar has an analysis feature which allows the computation of a task's cache access profile by using its CFG. If a CFG is relocatable (CFG_Relocatable => True), it can be placed at any address in the memory. Otherwise, the CFG must be placed at the address specified by the attribute Text_Memory_Start_Address.

Cache AADL properties



Cheddar proposes a set of properties allowing the designer to express most of the usual cache units characteristics but also data related to CFG: 
    -- Cache properties
    -- 
	
    Supported_Addressing_Type : type enumeration (
      Virtual_Addressing, Physical_Addressing);	
    Addressing_Type : Cheddar_Multicore_Properties::Supported_Addressing_Type applies to (memory, system);
	
    Supported_Cache_Type : type enumeration (
        Data_Cache, 
        Instruction_Cache, 
        Unified_Cache);
    Cache_Type : Cheddar_Multicore_Properties::Supported_Cache_Type applies to (memory, system);
    
    Cache_Level : aadlinteger applies to (memory, system);

    Cache_Size : aadlinteger applies to (memory, system);

    Line_Size : size applies to (memory, system);    

    Associativity : aadlinteger applies to (memory, system);

    Block_Reload_Time : Time_Range applies to (memory, system);        

    Supported_Replacement_Policy_Type : type enumeration (
        Random, LRU, LRR, FIFO);
    Replacement_Policy_Type : Cheddar_Multicore_Properties::Supported_Replacement_Policy_Type applies to (memory, system);
                              
    Supported_Coherence_Protocol_Type : type enumeration (
        Private_Cache, 
        Shared_Cache, 
        Private_Invalid_Cache, 
        Private_MSI, 
        Private_MESI);
    Coherence_Protocol_Type : Cheddar_Multicore_Properties::Supported_Coherence_Protocol_Type applies to (memory, system);

    Supported_Write_Policy_Type : type enumeration (
        Write_Back,
        No_Allocated_Write_Through, 
        Allocated_Write_Through,
        Write_Through);
    Write_Policy_Type : Cheddar_Multicore_Properties::Supported_Write_Policy_Type applies to (memory, system);                  

	
    -- CFG properties
    --    

    CFG_Name : aadlstring applies to (thread);

    CFG_Relocatable : aadlboolean applies to (thread);

    Text_Memory_Start_Address : aadlinteger applies to (thread);    

    UCBs : list of aadlinteger applies to (thread);     

    ECBs : list of aadlinteger applies to (thread);
Properties applied to cache memory unit: Properties applied to thread:

Possible analysis

Cache interference in Cheddar is based on the concepts of Cache Related Preemption Delay (CRPD). The bounds on the CRPD are computed by using :
     - Useful Cache Block [LEE 98]
     - Evicting Cache Block[BUS 95]
The following process is required to run the CRPD analyses implemented in Cheddar.



Case study



donner au moins 1 exercice (voire 2 exercice, ca serait parfait!








(return back to recipe list)