WCET (Worst-Case Execution Time) estimation on multicore architecture is particularly challenging mainly due to the complex accesses over cache shared by multiple cores. Existing analysis identifies possible contentions between parallel tasks by leveraging the partial order of the tasks or their program regions. Unfortunately, they overestimate the number of cache misses caused by a remote block access without considering the actual cache state and the number of accesses. This paper reports a new analysis for inter-core cache contention. Based on the order of program regions in a task, we first identify memory references that could be affected if a remote access occurs in a region. Afterwards, a fine-grained contention analysis is constructed that computes the number of cache misses based on the access quantity of local and remote blocks. We demonstrate that the overall inter-core cache interference of a task can be obtained via dynamic programming. Experiments show that compared to existing methods, the proposed analysis reduces inter-core cache interference and WCET estimations by$\mathbf{5 2. 3 1 \%}$and$\mathbf{8. 9 4 \%}$on average, without significantly increasing computation overhead.

Directed Acyclic Graph (DAG) models are extensively utilized across fields such as automotive, wireless communication, and deep learning, to capture the inherent functional dependencies. Topology of DAG has a significant impact on the performance of scheduling and resource management algorithms applied to it. Hence, it is imperative to generate all DAG topologies within the parameter ranges pertinent to an application domain, for impartial evaluation of such algorithms. Unfortunately, the existing DAG generators that are capable of offering full topology coverage have limited scalability and controllable parameters. This work reports open-source FT-DAG, an efficient and formally verified full-topology DAG generator that is able to control all major parameters, including the longest length, shortest length, width, jump layer, jump level, in-degree, out-degree, shape value as well as the number of nodes and edges. Experiments show that when the number of nodes is larger than 20, FT-DAG provides at least two orders of magnitude speedup compared to the state of the art and more orders to other generators. FT-DAG scales to 100 nodes in a typical industrial case study within hours.

In recent years, mobile elements (MEs) have been proposed as mechanical carriers of data to prolong the lifetime of sensor networks and to overcome network partitioning problem. A scheduling approach is proposed in Y. Gu et al., (2005) for MEs to collect periodically generated data, also called regular messages (RMs), from nearby sensor nodes with no buffer overflow. However, increased delay in message delivery with ME-based communication compared to multi-hop communication may not be tolerated in some cases. Some messages can be more urgent than others due to critical values of the sensed data. Such messages maybe required to be delivered to the ME within a specified deadline. In this paper, this new problem of differentiated message delivery (DMD) considering both regular and urgent message collection is addressed. The proposed solution incorporates multi-hop communication into the ME scheduling problem. The investigated performance metrics are the minimum required ME speed to prevent data loss and guarantee the maximum tolerated urgent message delay, as well as urgent and regular message loss rates for a given ME speed. The proposed solution is shown to perform well in terms of these metrics in various network scenarios. Furthermore, comparisons with existing ME scheduling algorithms show that the proposed solution meets the urgent message delivery requirement with a reasonable increase in ME speed.

In recent studies, using mobile elements (MEs) as mechanical carriers of data has been shown to be an effective way of prolonging sensor network life time and relaying information in partitioned networks. As the data generation rates of sensors may vary, some sensors need to be visited more frequently than others. In this paper, a partitioning-based algorithm is presented that schedules the movements of MEs in a sensor network such that there is no data loss due to buffer overflow. Simulation results show that the proposed Partitioning Based Scheduling (PBS) algorithm performs well in terms of reducing the minimum required ME speed to prevent data loss, providing high predictability in inter-visit durations, and minimizing the data loss rate for the cases when the ME is constrained to move slower than the minimum required ME speed.