Let $Γ$ be an arrangement of Jordan curves in the plane, i.e., simple closed curves in the plane. For any curve $γ\in Γ$, we denote the bounded region enclosed by $γ$ as $\tildeγ$. We say that $Γ$ is non-piercing if for any two curves $α, β\in Γ$, $\tildeα \,\setminus\, \tildeβ$ is connected. A non-piercing arrangement of curves generalizes a set of $2$-intersecting curves in which each pair of curves intersect in at most two points. Snoeyink and Hershberger (``Sweeping Arrangements of Curves'', SoCG '89) proved that if we are given an arrangement $Γ$ of $2$-intersecting curves and a {\em sweep} curve $γ\inΓ$, then the arrangement can be \emph{swept} by $γ$ while always maintaining the $2$-intersecting property of the curves in $Γ$. We generalize the result of Snoeyink and Hershberger to the setting of non-piercing arrangements. Given an arrangement $Γ$ of non-piercing curves, a sweep curve $γ\in Γ$, and a point $P$ in $\tildeγ$, we show that we can continuously shrink $γ$ to $P$ so that throughout the process, the arrangement remains non-piercing (except at a finite set of points in time where $γ$ crosses other curves), and $P$ lies in $\tildeγ$. We show that our arguments can be modified if $P$ lies outside $\tildeγ$, and we want to sweep $γ$ \emph{outwards} so that $P$ lies outside $\tildeγ$, and the arrangement remains non-piercing. As a second contribution, we give an alternate proof of the result of Snoeyink and Hershberger, and give several applications of our results to combinatorial and algorithmic questions including to the \emph{multi-hitting set} problem involving points and non-piercing regions.

Enhancing result-accuracy in approximate computing (AC) based real-time systems, without violating power constraints of the underlying hardware, is a challenging problem. Execution of such AC real-time applications can be split into two parts: (i)the mandatory part, execution of which provides a result of acceptable quality, followed by (ii)the optional part, that can be executed partially or fully to refine the initially obtained result in order to increase the result-accuracy, without violating the time-constraint. This article introducesDELICIOUS, a novel hybrid offline-onlinescheduling strategyfor AC real-time dependent tasks. By employing an efficientheuristic algorithm,DELICIOUSfirst generates a schedule for a task-set with an objective to maximize the results-accuracy, while respecting system-wide constraints. During execution,DELICIOUSthen introduces aprudential cache resizingthat reduces temperature of the adjacent cores, by generating thermal buffers at the turned off cache ways.DELICIOUSfurther trades off this thermal benefits by enhancing the processing speed of the cores for a stipulated duration, calledV/F Spiking, without violating the power budget of the core, to shorten the execution length of the tasks. This reduced runtime is exploited either to enhance result-accuracy by dynamically adjusting the optional part, or to reduce temperature by enabling sleep mode at the cores. While surpassing the prior art,DELICIOUSoffers 80% result-accuracy with its scheduling strategy, which is further enhanced by 8.3% in online, while reducing runtime peak temperature by 5.8°C on average, as shown by benchmark based evaluation on a 4-core based multicore.

Cyber-Physical Systems, including those in the automotive domain, are often designed by assigning to each task an appropriate criticality-based reward value which is acquired by the system on its successful execution. Additionally, each task may have multiple implementations designated as service-levels, with higher service-levels producing more accurate results and contributing to higher rewards for the system. This work proposes strategies for co-scheduling a set of periodic tasks with multiple service-levels, on homogeneous processors and system buses. The problem is modeled as a Multi-dimensional Multiple-Choice Knapsack formulation (MMCKP) with the objective of maximizing overall system level rewards. A Dynamic Programming (DP) solution is proposed to solve the MMCKP. It was observed that although the DP based solution produces optimal results, its complexity is highly sensitive to the number of tasks, processors, buses as well as to the number of task service-levels, which severely restricts scalability of the strategy. Therefore, we have also proposed a fast yet efficient heuristic algorithm called Accurate Low Overhead Level Allocator (ALOLA), which attempts to achieve the same objective. Our simulation based experimental evaluation shows that even on moderately large systems consisting of 90 tasks with 5 service-levels each, 16 processors and 4 buses, while MMCKP incurs a run-time of more than 1 hour 20 minutes and approximately 68 GB main memory, ALOLA takes only about 196 $\mu s$ (speedup of the order of 106times) and less than 1 MB of memory. Moreover, while being fast, ALOLA is also efficient being able to control performance degradations to at most 13% compared to the optimal results produced by MMCKP. We use an automated flight control system employed in modern avionic systems, a real-world application to illustrate the general applicability of our proposed scheme.