In this work, we present Autonomic CityMoS, a malleable parallel, and distributed traffic simulator engine that can automatically adapt the number of computing nodes in response to dynamic computational demands. We combine a snapshot system that enables data distribution, two predictive cost models that estimate the system speedup based on key metrics, including partitioning characteristics, and a policy that leverages these models to maintain a steady simulation pace. Autonomic CityMoS is able to effectively keep the simulation pace under varying traffic pattern flows, all without prior knowledge of traffic conditions. Although adaptation times are significant, we still observe an improvement in resource utilization compared with a run with static allocation of compute resources. The work presented in this paper should serve as an example of malleable simulation execution, where the objective is not to maximize performance but rather ensure a sustainable execution of large distributed simulation targeting to optimize the trade-off between target speed-up and overall compute resource utilization. Target applications include, but are not limited to, very large visual and interactive simulations.

The use of IoT and AI/ML to extract insights for Data-Driven Decision-Making (DDDM) in Intelligent Traffic Systems (ITS) is becoming increasingly popular. While simulation is a cost-effective and safe way to evaluate such approaches, existing simulators are often impractical due to inefficient control interfaces. In this work, we propose a Discrete-Event, Aggregating, and Relational Control Interfaces (DAR-CI) framework for achieving efficient traffic management simulations through a coupled approach. It enables a non-blocking interaction mode based on a discrete-event synchronization architecture. The overhead caused by data exchange is substantially reduced by supporting the direct retrieval of temporal metrics, data batch processing and customized in-situ aggregation. Combined with flexible, extendable, easy-to-understand, and implementation-friendly semantic specifications, we propose DAR-CI to serve as a universal tool for the traffic simulation community, taking the use and control of traffic simulation to a new level. A proof-of-concept study on the simulation of an adaptive traffic light control system demonstrates a 9.53X speedup compared to TraCI, a widely used protocol for controlling traffic simulators.

Bounding worst-case blocking delays due to lock contention is a fundamental problem in the analysis of multiprocessor real-time systems. However, virtually all fine-grained (i.e., non-asymptotic) analyses published to date make a simplifying (but impractical) assumption: critical sections must not be nested. This paper overcomes this fundamental limitation and presents the first fine-grained blocking bound for nested non-preemptive FIFO spin locks under partitioned fixed-priority scheduling. To this end, a new analysis method is introduced, based on a graph abstraction that reflects all possible resource conflicts and transitive delays.

All major real-time suspension-based locking protocols (or semaphore protocols) for global fixed-priority scheduling are reviewed and a new, unified response-time analysis framework applicable to all protocols is proposed. The newly proposed analysis, based on linear programming, is shown to be clearly preferable compared to all prior conventional approaches. Based on the new analysis, all protocols are directly compared with each other in a large-scale schedulability study. Interestingly, the Priority Inheritance Protocol (PIP) and the Flexible Multiprocessor Locking Protocol (FMLP), which are the two oldest and simplest of the considered protocols, are found to perform best.

Accurately bounding the worst-case blocking for finite job sets, a special case of the classic sporadic task model of recurrent real-time systems, using either nested FIFO-or priority-ordered locks on multiprocessors is NP-hard. These intractability results are obtained with reductions from the Multiple-Choice Matching problem. The reductions are quite general and do not depend on (1) whether the locks are spin-or suspension-based, or (2) whether global or partitioned scheduling is used, or (3) which scheduling policy is employed (as long as it is work-conserving). Further, we show that, for a special case in which the blocking analysis problem is NP-hard for FIFO- and priority-ordered locks, the problem for unordered spin locks with nested critical sections can be answered in polynomial time by solving a reach ability problem on a suitably constructed graph, although (or rather, because) unordered locks do not offer any acquisition-order guarantees. Finally, we identify several challenging open problems, pertaining both to circumventing the hardness results and to classifying the inherent difficulty of the problem more precisely.

Motivated by the widespread use of spin locks in embedded multiprocessor real-time systems, the worst-case blocking in spin locks is analyzed using mixed-integer linear programming. Four queue orders and two preemption models are studied: (i) FIFO-ordered spin locks, (ii) unordered spin locks, (iii) priority-ordered spin locks with unordered tie-breaking, and (iv) priority-ordered spin locks with FIFO-ordered tie-breaking, each analyzed assuming both preempt able and non-preempt able spinning. Of the eight lock types, seven have not been analyzed in prior work. Concerning the sole exception (non-preempt able FIFO spin locks), the new analysis is asymptotically less pessimistic and typically much more accurate since no critical section is accounted for more than once. The eight lock types are empirically compared in schedulability experiments. While the presented analysis is generic in nature and applicable to real-time systems in general, it is specifically motivated by the recent inclusion of spin locks into the AUTOSAR standard, and four concrete suggestions for an improved AUTOSAR spin lock API are derived from the results.

Many online data sets evolve over time as new entries are slowly added and existing entries are deleted or modified. Taking advantage of this, systems for incremental bulk data processing, such as Google's Percolator, can achieve efficient updates. To achieve this efficiency, however, these systems lose compatibility with the simple programming models offered by non-incremental systems, e.g., MapReduce, and more importantly, requires the programmer to implement application-specific dynamic algorithms, ultimately increasing algorithm and code complexity.

We describe a model for MapReduce computations that can be used to optimize the increasingly complex choice of resources that cloud customers purchase.