Date: Tuesday 25 March 2014
Time: 11:30 - 13:00
Location / Room: Konferenz 4

Chair:
Benny Akesson, CTU Prague, CZ

Co-Chair:
Marco Di Natale, Scuola Superiore Sant'Anna, IT

The papers in this session deal with analysis and management of memory hierarchies for complex real-time systems, both from the deterministic and the probabilistic point of view.

Time	Label	Presentation Title Authors
11:30	2.6.1	(Best Paper Award Candidate) ON THE CORRECTNESS, OPTIMALITY AND PRECISION OF STATIC PROBABILISTIC TIMING ANALYSIS Speakers: Sebastian Altmeyer1 and Robert Davis2 1University of Amsterdam, NL; 2University of York, GB Abstract In this paper, we investigate Static Probabilistic Timing Analysis (SPTA) for single processor systems that use a cache with an evict-on-miss random replacement policy. We show that previously published formulae for the probability of a cache hit can produce results that are optimistic and unsound when used to compute probabilistic Worst-Case Execution Time (pWCET) distributions. We investigate the correctness, optimality, and precision of different approaches to SPTA. We prove that one of the previously published formulae for the probability of a cache hit is optimal with respect to the limited information that it uses. We improve upon this formulation by using extra information about cache contention. To investigate the precision of various approaches to SPTA, we introduce a simple exhaustive method that computes a precise pWCET distribution, albeit at the cost of exponential complexity. Further, we integrate this precise approach, applied to small numbers of frequently accessed memory blocks, with imprecise analysis of other memory blocks, to form a combined approach that improves precision, without significantly increasing its complexity. The performance of the various approaches are compared on benchmark programs.
12:00	2.6.2	WCET-CENTRIC DYNAMIC INSTRUCTION CACHE LOCKING Speakers: Huping Ding1, Yun Liang2 and Tulika Mitra1 1School of Computing, National University of Singapore, SG; 2Center for Energy-efficient Computing and Applications, School of EECS, Peking University, CN Abstract Cache locking is an effective technique to improve timing predictability in real-time systems. In static cache locking, the locked memory blocks remain unchanged throughout the program execution. Thus static locking may not be effective for large programs where multiple memory blocks are competing for few cache lines available for locking. In comparison, dynamic cache locking overcomes cache space limitation through time-multiplexing of locked memory blocks. Prior dynamic locking technique partitions the program into regions and takes independent locking decisions for each region. We propose a flexible loop-based dynamic cache locking approach. We not only select the memory blocks to be locked but also the locking points (e.g., loop level). We judiciously allow memory blocks from the same loop to be locked at different program points for WCET improvement. We design a constraint-based approach that incorporates a global view to decide on the number of locking slots at each loop entry point and then select the memory blocks to be locked for each loop. Experimental evaluation shows that our dynamic cache locking approach achieves substantial improvement of WCET compared to prior techniques.
12:30	2.6.3	MINIMIZING STACK MEMORY FOR HARD REAL-TIME APPLICATIONS ON MULTICORE PLATFORMS Speakers: Chuansheng Dong and Haibo Zeng, McGill University, CA Abstract Multicore platforms are increasingly used in real-time embedded applications. In the development of such applications, an efficient use of RAM memory is as important as the effective scheduling of software tasks. Preemption Threshold Scheduling is a well-known technique for controlling the degree of preemption, possibly improving system schedulability, and allowing savings in stack space. In this paper, we target at the optimal mapping of tasks to cores and the assignment of the scheduling parameters for systems scheduled with preemption thresholds. We formulate the optimization problems using Mixed Integer Linear Programming framework, and propose an efficient heuristic as an alternative. We demonstrate the efficiency and quality of both approaches with extensive experiments using random systems as well as two industrial case studies.
12:45	2.6.4	TIME-PREDICTABLE EXECUTION OF MULTITHREADED APPLICATIONS ON MULTICORE SYSTEMS Speakers: Ahmed Alhammad and Rodolfo Pellizzoni, University of Waterloo, CA Abstract In multicore systems, contention for access to main memory between application threads complicates timing analysis and may lead to pessimistic bounds on execution time. This is particularly problematic for real-time applications, which require provable bounds on worst-case performance. In this work, we employ a predictable execution model to schedule memory accesses performed by application threads without relying on unpredictable hardware arbiters. In addition, we statically schedule application's threads with the objective to minimize the application's makespan. Our experimental evaluation on 4-core system with NAS Parallel Benchmarks indicates that the proposed execution scheme yields an aggregated improvement of 21% over contention execution in which application's threads uncontrollably accessing the main memory.
13:00		End of session Lunch Break in Exhibition Area Sandwich lunch