One operation that can lead to high incidence in discrete event simulation systems is the allocation/deallocation of buffers used for hosting simulation events. In this article we present an Event-Buffer Allocator (EBA) for parallel discrete event simulation which gives rise to extremely reduced CPU cycles for handling both allocation and deallocation tasks. Additionally, EBA improves the locality of the event-buffer access operations at the level of the MMU (Memory Management Unit) of the CPU. Like common memory allocators, our solution still relies on the concept of arena, but integrates 1) a fully new mechanism for the interactions between the arena-owner thread and other concurrent threads, possibly releasing buffers to the arena and 2) a suited mapping strategy for the arena, which leads to the definite reduction of the TLB misses experienced by the CPU. Additionally, it integrates a deferred-work solution that naturally meets the allocation/deallocation pattern of event buffers—in fact the event-buffer lifetime is linked to the advancement of simulation time along the wall-clock-time axis. In this article, we compare EBA with the classical malloc implementation offered by glibc and the optimized mimalloc and tcmalloc libraries, showing its clear advantages. Also, we integrated EBA in the PARSIR (PARallel SImulation Runner) open source simulation environment, making it available to the community.

Machine Learning (ML) emerged as a powerful tool for predicting task execution times across the variety of VM types offered by Infrastructure-as-a-Service (IaaS) clouds. However, training ML models to ensure accurate predictions can often become uneconomical for users due to the high costs—in terms of both time and money—for collecting samples, especially when an IaaS cloud offers a wide choice of VM types. This paper investigates a ML model bootstrapping technique that leverages analytical modeling to reduce the cost of collecting training samples while maintaining robust performance predictions. Complementarily, the technique can be used to improve the accuracy of ML models in the case of limited availability of training samples. Experimental results highlighted the potential of the proposed technique with various workloads and with a large set of VM types, paving the way for more cost-effective ML-based performance prediction in IaaS clouds.

One of the most reliable and effective solutions against Return-Oriented Programming (ROP) attacks is the incorporation of Backward Edge Control-Flow Integrity. The most prominent implementation of this concept involves the integration of a dedicated shadow stack, which is a distinct memory structure used for saving and checking functions’ return addresses, and consequently, enforcing the control flow within a program. In this article we propose an alternative perspective to this established notion via the introduction of KSS, a Kernel Shadow Stack for user programs. Our solution not only upholds program flow but also enables determining which code block has been the origin of stack tampering. Furthermore, by placing itself at a higher privilege level, its information can no way be altered by the (attacked) user-level code. Overall, it does not only offer the support for more secure program operations, rather it also allows the analysis of program flows-an aspect that can be very relevant in software deploy phases. Beyond a kernellevel subsystem, which we developed for Linux, KSS includes an instrumentation engine and a custom loader designed to enable its usage with preexisting programs, with no need for any access to the program’s source code. Via experimental results we show how the impact of costs (in terms of CPU-cycles) inherent to the implementation of KSS can be definitely reduced in scenarios involving networking-based applications where threads classically exhibit an I/O-bound execution profile.

The paper "Transparently Mixing Undo Logs and Software Reversibility for State Recovery in Optimistic PDES" introduced a seminal hybrid rollback technique that efficiently and transparently combines checkpointing and reverse computation methods through runtime-generated undo instructions. This short abstract, which accompanies the Test of Time Award received at PADS 2025, summarises the fundamental challenges presented in the original paper and reflects on its impact in the decade after its publication.

ABSTRACT Locking plays a crucial role since it ensures synchronized access by concurrent threads to shared resources—like shared data structures to be managed in critical sections. Traditional sleep locks—based on blocking operating system services—adopt a reactive approach (e.g., upon lock release) to waking up waiting threads, which might introduce additional latency on the critical path. On the opposite side, non‐blocking locks, like spinlocks, allow threads to wait while still using CPU cycles for checking and updating the lock variable, which causes the waste of both cycles and energy. In this article, we present a new locking algorithm, called SSPA (Spin/Sleep Proactive‐Awakening)—and its implementation for Linux systems—which combines spin and sleep waiting phases via the introduction of an innovative proactive wake‐up mechanism that exploits the SoftIRQ daemon of the Linux kernel. Our solution allows threads to be awakened from their sleep phases on time to be already CPU dispatched when the lock is really released. This provides the opportunity to quickly access the critical section while at the same time enabling control over the actual amount of CPU cycles that are spent by spinning wait phases. As we show via experimental data, our solution allows exploring new trade‐offs between responsiveness and CPU/energy efficiency in concurrent applications, hence rising as an interesting alternative to literature solutions.

In this article we present Out-of-order Discrete Event Simulation (ODES), a solution for sequential style execution of DES models not following timestamp order. ODES ensures anyway the same identical simulation results as timestamp ordered execution, thanks to fully correct maintenance of the simulation model data flow. At the same time, it drastically reduces the memory boundedness—namely, the impact of cache misses and of stale CPU cycles—on the simulation model execution speed. Beyond presenting foundational concepts, we also discuss our ODES-engine implementation, based on the c programming language. Additionally, we report experimental data for comparing ODES with the classical timestamp ordered execution of simulation models according to conventional sequential simulation. The relevance of ODES compared to classical timestamp ordered sequential DES not only stands in its benefits on performance, rather ODES can also assume the role of new reference for determining the speedup achievable via parallel/distributed discrete event simulation systems, compared to the single thread execution. Also, thanks to its improvements in the interaction with RAM, ODES constitutes a new framework for effective parallel replication of simulation experiments on multi-processor/multi-core machines.

In this article we present PARSIR (PARallel SImulation Runner), a package that enables the effective exploitation of shared-memory multi-processor machines for running discrete event simulation models. PARSIR is a compile/run-time environment for discrete event simulation models developed with the C programming language. The architecture of PARSIR has been designed in order to keep low the amount of CPU-cycles required for running models. This is achieved via the combination of a set of techniques like: 1) causally consistent batch-processing of simulation events at an individual simulation object for caching effectiveness; 2) high likelihood of disjoint access parallelism; 3) the favoring of memory accesses on local NUMA (Non-Uniform-Memory-Access) nodes in the architecture, while still enabling well balanced workload distribution via work-stealing from remote nodes; 4) the use of RMW (Read-Modify-Write) machine instructions for fast access to simulation engine data required by the worker threads for managing the concurrent simulation objects and distributing the workload. Furthermore, any architectural solution embedded in the PARSIR engine is fully transparent to the application level code implementing the simulation model. We also provide experimental results showing the effectiveness of PARSIR when running the reference PHOLD benchmark on a NUMA shared-memory multi-processor machine equipped with 40 CPUs.

One way for supporting incremental checkpointing is the exploitation of classical memory protection services—in particular the mprotect (…) system call offered by Posix compliant operating systems—for intercepting memory-writes and identifying dirty pages in the address space. However, this solution involves Inter-Processor-Interrupt (IPI) and the associated handling mechanisms, which show costs that increase when scaling up the level of parallelism in the underlying hardware architecture. For HPC contexts like speculative (aka optimistic) parallel discrete event simulation, where checkpointing and state restore massively take place in order to maintain causality among the concurrent simulation objects, these costs may impact performance in a non-negligible manner. In this work, we present the design of operating system services that enable write-protection and the tracing of dirtied pages via per CPU setup of the MMU (Memory Management Unit), completely avoiding the usage of IPI and their management. Hence, we provide a solution where the cost for setting up the incremental checkpointing support of a simulation object processed by a specific thread at a given time is definitely limited, compared to the aforementioned classical case. Our design has been devised for Linux, although it can be ported to other operating systems, and has been integrated for its testing in the USE (Ultimate Share Everything) open source parallel simulation environment.

Modern malware has become increasingly sophisticated, posing a significant threat to cybersecurity. As a result, researchers and security professionals are constantly seeking more advanced methods to detect and analyze malware. Most of these methods are under the umbrella of dynamic analysis, which offers advantages over static analysis—it allows for the observation of the runtime behavior and the detection of obfuscated or encrypted code that may be used to evade detection. However, running executables in a controlled environment can be costly, often leading to a pragmatic compromise of running them with sandboxing only for a limited initial time. In this paper, we propose a different approach to dynamic executable analysis: we analyze the presence of malicious signatures in executable virtual pages of an application the moment they are materialized in RAM—possibly with a new content after an update. We specifically design and evaluate JITScanner, a Linux-oriented package based on a Loadable Kernel Module (LKM), which supports checking any executable page each time its fresh content located in RAM is accessed for instruction fetch enabling the detection of malicious updates to executable pages. The user-level component of the architecture communicates with the LKM via a scalable solution that exploits multi-processor/core technology. We also present experimental data that show the effectiveness of our solution and its promising potential.

Checkpointing techniques for speculative parallel simulation of discrete event models have been widely studied in the literature. However, there has been a very marginal attempt to exploit operating system page-protection services, which have instead been largely exploited in the context of checkpointing for fault tolerance. In this article, we discuss how these services can effectively manage simulation models with large states and write-intensive events in zones of the state layout. In particular, we present a solution where the correlation of write operations on buddy pages in the state layout can be exploited to achieve effective incremental checkpointing support, which allows scaling down the costs of operating system services. Our solution does not require any instrumentation of the simulation application code and is usable on any Posix-compliant operating system. We also discuss its integration within the USE (Ultimate-Share-Everything) open-source speculative simulation package and report some experimental data for its assessment.

Output production and predicate detection are critical in speculative parallel discrete event simulation, since they need to take place accessing past state values—which have become committed—rather than the current state of the simulation objects, which is possibly affected by causality errors related to speculative event processing. In this article, we present an architecture that enables an effective management of the access to the committed state of any simulation object while still guaranteeing: (i) minimal impact on the forward execution of the simulation in terms of synchronization (and rollback generation) and (ii) highly balanced distribution of the tasks among all the threads running the simulation application. Our architecture is devised for speculative simulation engines running on top of shared-memory parallel machines, where worker threads full share the simulation workload. We exploit kernel-level facilities—targeting the Linux operating system—and user level ones, which work together for enabling a suited wall-clock-time collocation of the threads’ activities for the access to the committed global state of the simulation. We integrated our proposal within the USE (Ultimate Share-Everything) open-source simulation platform, and provide an experimental assessment of it.

Abstract Hardware performance counters (HPCs) are facilities offered by most off‐the‐shelf CPU architectures. They are a vital support to post‐mortem performance profiling and are exploited by standard tools such as Linux or Intel V‐Tune. Nevertheless, an increasing number of application domains (e.g., simulation, task‐based high‐performance computing, or cybersecurity) are exploiting them to perform different activities, such as self‐tuning, autonomic optimization, and/or system inspection. This repurposing of HPCs can be difficult, for example, because of the overhead for extracting relevant information. This overhead might render any online or self‐tuning activity ineffective. This article discusses various practical strategies to exploit HPCs beyond post‐mortem profiling, suitable for different application contexts. The presented strategies are accompanied by a general primer on HPCs usage on Linux. We also provide reference x86 (both Intel and AMD) implementations targeting the Linux kernel, upon which we present an experimental assessment of the viability of our proposals.

Transaction Processing (TP) plays a primary role in the design and implementation of IT applications and services. Many TP systems exploit lock-based concurrency control to guarantee atomicity and isolation of transactions that access shared data. In this article, we show that transaction data access patterns, in particular the order of data accesses along the transaction execution, have a noticeable impact on how lock-based concurrency control affects performance. We show that the performance can remarkably change depending on whether transactions, or a percentage of them, access data items following some common ordering rule or not. We investigate on this aspect and its root causes through an analytical modeling approach, and with the evidence of data gathered through both simulation and the execution of real transactional workloads. Finally, we show how the findings of our study can be easily exploited for improving the performance of common transactional workloads.

The increasing performance requirements of modern applications place a significant burden on software-based packet processing. Most of today’s software input/output accelerations achieve high performance at the expense of reserving CPU resources dedicated to continuously poll the Network Interface Card. This is specifically the case with DPDK (Data Plane Development Kit), probably the most widely used framework for software-based packet processing today. The approach presented in this paper, descriptively called Metronome, has the dual goals of providing CPU utilization proportional to the load, and allowing flexible sharing of CPU resources between I/O tasks and applications. Metronome replaces DPDK’s continuous polling with an intermittent sleep&wake mode, and revolves around a new multi-threaded operation, which improves service continuity. Since the proposed operation trades CPU usage with buffering delay, we propose an analytical model devised to dynamically adapt the sleep&wake parameters to the actual traffic load, meanwhile providing a target average latency. Our experimental results show a significant reduction of the CPU cycles, improvements in power usage, and robustness to CPU sharing even when challenged with CPU-intensive applications.

The recent literature has reshuffled the architectural organization of speculative parallel discrete event simulation systems for shared-memory multi-core machines. A core aspect has been the full sharing of the workload at the level of individual simulation events, which enables keeping the rollback incidence minimal. However, making each worker thread continuously switch its execution between events destined to different simulation objects does not favor locality. In this article, we propose a workload-sharing algorithm where the worker threads can have short-term binding with specific simulation objects to favor spatial locality and caching effectiveness. Also, new bindings—carried out when a thread decides to switch its execution to other simulation objects—are based on the timeline according to which the object states have passed through the caching hierarchy. At the same time, our solution still enables the worker threads to focus their activities on the events to be processed whose timestamps are closer to the simulation commit horizon—hence we exploit temporal locality along virtual time and keep the rollback incidence minimal. In our design we exploit lock-free constructs to support scalable thread synchronization while accessing the shared event pool. Furthermore, we exploit a multi-view approach of the event pool content, which additionally favors local accesses to the parts of the event pool that are currently relevant for the thread activity. Our solution has been released as an integration within the USE open source speculative simulation platform available to the community. Furthermore, in this article we report the results of an experimental study that shows the effectiveness of our proposal.

Abstract Software transactional memory (STM) provides synchronization support to ensure atomicity and isolation when threads access shared data in concurrent applications. With STM, shared data accesses are encapsulated within transactions automatically handled by the STM layer. Hence, programmers are not requested to use code‐synchronization mechanisms explicitly, like locking. In this article, we present our experience in designing and implementing a partial abort scheme for STM. The objective of our work is threefold: (1) enabling STM to undo only part of the transaction execution in the case of conflict, (2) designing a scheme that is fully transparent to programmers, thus also allowing to run existing STM applications without modifications, and (3) providing a scheme that can be easily integrated within existing STM runtime environments without altering their internal structure. The scheme we designed is based on automated software instrumentation, which injects into the application capabilities to undo the required portions of transaction executions. Further, it can correctly undo also non‐transactional operations executed on the stack and the heap during a transaction. This capability allows programmers to write transactional code without concerns about the side effects of aborted transactions on both shared and thread‐private data. We integrated and evaluated our partial abort scheme within the TinySTM open‐source library. We analyze the experimental results we achieved with common STM benchmark applications, focusing on the advantages and disadvantages of the proposed solutions for implementing our scheme's different components. Hence, we highlight the appropriate choices and possible solutions to improve partial abort schemes further.

Common implementations of core memory allocation components handle concurrent allocation/release requests by synchronizing threads via spin-locks. This approach is not prone to scale, a problem that has been addressed in the literature by introducing layered allocation services or replicating the core allocators—the bottom-most ones within the layered architecture. Both these solutions tend to reduce the pressure of actual concurrent accesses to each individual core allocator. In this article, we explore an alternative approach to scalability of memory allocation/release, which can be still combined with those literature proposals. We present a fully non-blocking buddy system, where threads performing concurrent allocations/releases do not undergo any spin-lock based synchronization. Our solution allows threads to proceed in parallel, and commit their allocations/releases unless a conflict is materialized while handling the allocator metadata—memory fragmentation and coalescing are also carried out in a fully non-blocking manner. Conflict detection relies in our solution on atomic Read-Modify-Write (RMW) machine instructions, guaranteed to execute atomically by the processor firmware. We also provide a proof of the correctness of our non-blocking buddy system and show the results of an experimental study that outlines the effectiveness of our solution.

OpenMP has become a reference standard for the design of parallel applications. This standard is evolving quickly, thus offering new opportunities to the application programmers. However, OpenMP runtime environments are often not fully aligned with the actual requirements imposed by the evolution of such a standard. Among the main lacks, we find: (a) a limited capability to effectively cope with task priorities, and (b) the inadequacy in guaranteeing core properties while processing tasks such as the so-calledwork-conservativeness—the ability of the OpenMP runtime environment to fully exploit the underlying multi-processor/multi-core machine through the avoidance of thread-blocking phases. In this article, we present the design of extensions to the GNU OpenMP (GOMP) implementation, integrated intogcc, which allow the effective management of tasks and their priorities. Our proposal is based on a user-space library—modularly combined with the one already offered byGOMP—and an external kernel-level Linux module—offering the opportunity to exploit raising hardware facilities for task/priority management. We also provide experimental results showing the effectiveness of our proposal, achieved by running either OpenMP common benchmarks or a new benchmark application (Hashtag-Text) that we explicitly devised to stress the runtime environment in relation to the above-mentioned task/priority management aspects.

Concurrent systems, based on (distributed) multi/many-core processing units, are the nowadays reference computing architecture. The (continuously-growing) level of hardware parallelism they offer has led these platforms to play a central role at any scale, ranging from data centers, to personal (mobile) devices. Optimizing performance and/or ensuring energy efficiency when running complex software stacks on top of these systems is extremely challenging due to several aspects, like data dependencies or resource sharing (and interference) among application threads, as well as VMs. Furthermore, hardware accelerators like GPGPUs or FPGAs introduce a level of heterogeneity that can potentially offer further opportunities for combined gain in performance and energy efficiency, if correctly exploited.

Summary Multithreaded applications facilitate the exploitation of the computing power of multicore architectures. On the other hand, these applications can become extremely energy‐intensive, in contrast with the need for limiting the energy usage of computing systems. In this article, we explore the design of techniques enabling multithreaded applications to maximize their performance under a power cap. We consider two control parameters: the number of cores used by the application, and the core power state. We target the design of an autotuning power‐capping technique with minimal intrusiveness and high portability, which is agnostic about the workload profile of the application. We investigate two different approaches for building the strategy for selecting the best configuration of the parameters under control, namely a heuristic approach and a model‐based approach. Through an extensive experimental study, we evaluate the effectiveness of the proposed technique considering two different selection strategies, and we compare them with existing solutions.

DPDK (Data Plane Development Kit) is arguably today's most employed framework for software packet processing. Its impressive performance however comes at the cost of precious CPU resources, dedicated to continuously poll the NICs. To face this issue, this paper presents Metronome, an approach devised to replace the continuous DPDK polling with a sleep&wake intermittent mode. Metronome revolves around two main innovations. First, we design a microseconds time-scale sleep function, named hr_sleep(), which outperforms Linux' nanosleep() of more than one order of magnitude in terms of precision when running threads with common time-sharing priorities. Then, we design, model, and assess an efficient multi-thread operation which guarantees service continuity and improved robustness against preemptive thread executions, like in common CPU-sharing scenarios, meanwhile providing controlled latency and high polling efficiency by dynamically adapting to the measured traffic load.

Modern computing platforms are based on multi-processor/multi-core technology. This allows running applications with a high degree of hardware parallelism. However, medium-to-high end machines pose a problem related to the asymmetric delays threads experience when accessing shared data. Specifically, Non-Uniform-Memory-Access (NUMA) is the dominating technology-thanks to its capability for scaled-up memory bandwidth-which however imposes asymmetric distances between CPU-cores and memory banks, making an access by a thread to data placed on a far NUMA node severely impacting performance. In this article, we tackle this problem in the context of shared event-pool management, a relevant aspect in many fields, like parallel discrete event simulation. Specifically, we present a NUMA-aware calendar queue, which also has the advantage of making concurrent threads coordinate via a non-blocking scalable approach. Our proposal is based on work deferring combined with dynamic re-binding of the calendar queue operations (insertions/extractions) to the best suited among the concurrent threads hosted by the underlying computing platform. This changes the locality of the operations by threads in a way positively reflected onto NUMA tasks at the hardware level. We report the results of an experimental study, demonstrating the capability of our solution to achieve the order of 15% better performance compared to state-of-the-art solutions already suited for multicore environments.

A rollback operation in a speculative parallel discrete event simulator has traditionally targeted the perfect reconstruction of the state to be restored after a timestamp-order violation. This imposes that the rollback support entails specific capabilities and consequently pays given costs. In this article we propose approximated rollbacks, which allow a simulation object to perfectly realign its virtual time to the timestamp of the state to be restored, but lead the reconstructed state to be an approximation of what it should really be. The advantage is an important reduction of the cost for managing the state restore task in a rollback phase, as well as for managing the activities (i.e. state saving) that actually enable rollbacks to be executed. Our proposal is suited for stochastic simulations, and explores a tradeoff between the statistical representativeness of the outcome of the simulation run and the execution performance. We provide mechanisms that enable the application programmer to control this tradeoff, as well as simulation-platform level mechanisms that constitute the basis for managing approximate rollbacks in general simulation scenarios. A study on the aforementioned tradeoff is also presented.

Reducing the waste of resource usage (e.g., CPU-cycles) when a causality error occurs in speculative parallel discrete event simulation (PDES) is still a core objective. In this article, we target this objective in the context of speculative PDES run on top of shared-memory machines. We propose an Operating System approach that is based on the exploitation of the Inter-Processor-Interrupt (IPI) facility offered by off-the-shelf hardware chipsets, which enables cross-CPU-core control of the execution flow of threads. As soon as a thread T produces a new event placed in the past virtual time of a simulation object currently run by another thread T', our IPI-based support allows T to change the execution flow of T'---with very minimal delay---so to enable the early squash of the currently processed (and no longer consistent) event. Our solution is fully transparent to the application level code, and is coupled with a lightweight heuristic-based mechanism that determines the actual goodness of killing thread T' via the IPI (rather than skipping the IPI send) depending on the expected residual execution time of the incorrect event being processed. We integrated our proposal within the speculative open-source USE (Ultimate Share Everything) PDES package, and we report experimental results obtained by running various PDES models on top of two shared-memory hardware architectures equipped with 32 and 24 (48 Hyper-threads) CPU-cores, which demonstrate the effectiveness of our proposal.

Summary In this article, we present mutable locks, a synchronization construct with the same semantic of traditional locks (such as spin locks or sleep locks), but with a self‐tuned optimized trade‐off between responsiveness and CPU‐time usage during threads' wait phases. Mutable locks tackle the need for efficient synchronization supports in the era of multicore machines, where the run‐time performance should be optimized while reducing resource usage. This goal should be achieved with no intervention by the programmers. Our proposal is intended for exploitation in generic concurrent applications, where scarce or no knowledge is available about the underlying software/hardware stack and the workload. This is an adverse scenario for static choices between spinning and sleeping, which is tackled by our mutable locks thanks to their hybrid waiting phase and self‐tuning capabilities.

Software Transactional Memory (STM) stands as powerful concurrent programming paradigm, enabling atomicity, and isolation while accessing shared data. On the downside, STM may suffer from performance degradation due to excessive conflicts among concurrent transactions, which cause waste of CPU-cycles and energy because of transaction aborts. An approach to cope with this issue consists of putting in place smart scheduling strategies which temporarily suspend the execution of some transaction in order to reduce the transaction conflict rate. In this article, we present an adaptive model-based transaction scheduling technique relying on a Markov Chain-based performance model of STM systems. Our scheduling technique is adaptive in a twofold sense: (i) It controls the execution of transactions depending on throughput predictions by the model as a function of the current system state. (ii) It re-tunes on-line the Markov Chain-based model to adapt it-and the outcoming transaction scheduling decisions-to dynamic variations of the workload. We have been able to achieve the latter target thanks to the fact that our performance model is extremely lightweight. In fact, to be recomputed, it requires a reduced set of input parameters, whose values can be estimated via a few on-line samples related to the current workload dynamics. We also present a scheduler that implements our adaptive technique, which we integrated within the open source TinySTM package. Further, we report the results of an experimental study based on the STAMP benchmark suite, which has been aimed at assessing both the accuracy of our performance model in predicting the actual system throughput and the advantages of the adaptive scheduling policy over literature techniques.

Common implementations of core memory allocation components, like the Linux buddy system, handle concurrent allocation/release requests by synchronizing threads via spin-locks. This approach is not prone to scale, a problem that has been addressed in the literature by introducing layered allocation services or replicating the core allocators-the bottom most ones within the layered architecture. Both these solutions tend to reduce the pressure of actual concurrent accesses to each individual core allocator. In this article we explore an alternative approach to scalability of memory allocation/release, which can be still combined with those literature proposals. We present a fully non-blocking buddy-system, where threads performing concurrent allocations/releases do not undergo any spin-lock based synchronization. Our solution allows threads to proceed in parallel, and commit their allocations/releases unless a conflict is materialized while handling the allocator metadata. Conflict detection relies on atomic Read-Modify-Write (RMW) machine instructions. Beyond improving scalability and performance, our solution can also avoid wasting clock cycles for spin-lock operations by threads that could in principle carry out their memory allocations/releases in full concurrency.

On August 14, 2018, a new set of vulnerabilities collectively named “L1 terminal fault” were announced. Systems with microprocessors utilizing out-of-order execution could allow unauthorized disclosure of information residing in the L1data cache, by tweaking the virtual memory abstraction. The vulnerability was therein mentioned for three different scenarios. In this demo-paper, we provide practical evidence about the feasibility of the most complex “VMM” case of an attacker residing in a Virtual Machine (VM), and targeting information leakage from the host OS and other independent VMs.

Agent-Based Modeling and Simulation (ABMS) is an effective paradigm to model systems exhibiting complex interactions, also with the goal of studying the emergent behavior of these systems. While ABMS has been effectively used in many disciplines, many successful models are still run only sequentially. Relying on simple and easy-to-use languages such as NetLogo limits the possibility to benefit from more effective runtime paradigms, such as speculative Parallel Discrete Event Simulation (PDES). In this paper, we discuss a semantically-rich API allowing to implement Agent-Based Models in a simple and effective way. We also describe the critical points which should be taken into account to implement this API in a speculative PDES environment, to scale up simulations on distributed massively-parallel clusters. We present an experimental assessment showing how our proposal allows to implement complicated interactions with a reduced complexity, while delivering a non-negligible performance increase.

In this article we present Anonymous Readers Counting (ARC), a multi-word atomic (1,N) register algorithm for multi-core machines. ARC exploits Read-Modify-Write (RMW) instructions to coordinate the writer and reader threads in a wait-free manner and enables large-scale data sharing by admitting up to$(2^{32}-2)$concurrent readers on off-the-shelf 64-bit machines, as opposed to the most advanced RMW-based approach which is limited to 58 readers on the same kind of machines. Further, ARC avoids multiple copies of the register content when accessing it—this is a problem that affects classical register algorithms based on atomic read/write operations on single words. Thus it allows for higher scalability with respect to the register size. Moreover, ARC explicitly reduces the overall power consumption, via a proper limitation of RMW instructions in case of read operations re-accessing a still-valid snapshot of the register content, and by showing constant time for read operations and amortized constant time for write operations. Our proposal has therefore a strong focus on real-world off-the-shelf architectures, allowing us to capture properties which benefit both performance and power consumption. A proof of correctness of our register algorithm is also provided, together with experimental data for a comparison with literature proposals. Beyond assessing ARC on physical platforms, we carry out as well an experimentation on virtualized infrastructures, which shows the resilience of wait-free synchronization as provided by ARC with respect to CPU-steal times, proper of modern paradigms such as cloud computing. Finally, we discuss how to extend ARC for scenarios with multiple writers and multiple readers—the so called (M,N) register. This is achieved not by changing the operations (and their wait-free nature) executed along the critical path of the threads, rather only changing the ratio between the number of buffers keeping the register snapshots and the number of threads to coordinate, as well as the number of bits used for counting readers within a 64-bit mask accessed via RMW instructions—just depending on the target balance between the number of readers and the number of writers to be supported.

Common implementations of core memory allocation components handle concurrent allocation/release requests by synchronizing threads via spin-locks. This approach is not prone to scale with large thread counts, a problem that has been addressed in the literature by introducing layered allocation services or replicating the core allocators-the bottom most ones within the layered architecture. Both these solutions tend to reduce the pressure of actual concurrent accesses to each individual core allocator. In this article we explore an alternative approach to scalability of memory allocation/release, which can be still combined with those literature proposals. We present a fully non-blocking buddy-system, that allows threads to proceed in parallel, and commit their allocations/releases unless a conflict is materialized while handling its metadata. Beyond improving scalability and performance it is resilient to performance degradation in face of concurrent accesses independently of the current level of fragmentation of the handled memory blocks.

Concurrency control protocols based on read-validation schemes allow transactions which are doomed to abort to still run until a subsequent validation check reveals them as invalid. These late aborts do not favor the reduction of wasted computation and can penalize performance. To counteract this problem, we present an analytical model that predicts the abort probability of transactions handled via read-validation schemes. Our goal is to determine what are the suited points-along a transaction lifetime-to carry out a validation check. This may lead to early aborting doomed transactions, thus saving CPU time. We show how to exploit the abort probability predictions returned by the model in combination with a threshold-based scheme to trigger read-validations. We also show how this approach can definitely improve performance-leading up to 14 % better turnaround-as demonstrated by some experiments carried out with a port of the TPC-C benchmark to Software Transactional Memory.

Controlling power usage has become a core objective in modern computing platforms. In this article we present an innovative Time Warp architecture oriented to efficiently run parallel simulations under a power cap. Our architectural organization considers power usage as a foundational design principle, as opposed to classical power-unaware Time Warp design. We provide early experimental results showing the potential of our proposal.

The share-everything PDES (Parallel Discrete Event Simulation) paradigm is based on fully sharing the possibility to process any individual event across concurrent threads, rather than binding Logical Processes (LPs) and their events to threads. It allows concentrating, at any time, the computing power---the CPU-cores on board of a shared-memory machine---towards the unprocessed events that stand closest to the current commit horizon of the simulation run. This fruitfully biases the delivery of the computing power towards the hot portion of the model execution trajectory. In this article we present an innovative share-everything PDES system that provides (1) fully non-blocking coordination of the threads when accessing shared data structures and (2) fully speculative processing capabilities---Time Warp style processing---of the events. As we show via an experimental study, our proposal can cope with hard workloads where both classical Time Warp systems---based on LPs to threads binding---and previous share-everything proposals---not able to exploit fully speculative processing of the events---tend to fail in delivering adequate performance.

Along the years, Parallel Discrete Event Simulation (PDES) has been enriched with programming facilities to bypass state disjointness across the concurrent Logical Processes (LPs). New supports have been proposed, offering the programmer approaches alternative to message passing to code complex LPs' relations. Along this path we find Event &Cross-State (ECS), which allows writing event handlers which can perform in-place accesses to the state of any LP, by simply relying on pointers. This programming model has been shipped with a runtime support enabling concurrent speculative execution of LPs limited to shared-memory machines. In this paper, we present the design of a middleware layer that allows ECS to be ported to distributed-memory clusters of machines. A core application of our middleware is to let ECS-coded models be hosted on top of (low-cost) resources from the Cloud. Overall, ECS-coded models no longer demand for powerful shared-memory machines to execute in reasonable time. Thanks to our solution, we retain indeed the possibility to rely on the enriched ECS programming model while still enabling deployments of PDES models on convenient (Cloud-based) infrastructures. An experimental assessment of our proposal is also provided.

Energy consumption has become a core concern in computing systems. In this context, power capping is an approach that aims at ensuring that the power consumption of a system does not overcome a predefined threshold. Although various power capping techniques exist in the literature, they do not fit well the nature of multi-threaded workloads with shared data accesses and non-minimal thread-level concurrency. For these workloads, scalability may be limited by thread contention on hardware resources and/or data, to the point that performance may even decrease while increasing the thread-level parallelism, indicating scarce ability to exploit the actual computing power available in highly parallel hardware. In this paper, we consider the problem of maximizing the performance of multi-thread applications under a power cap by dynamically tuning the thread-level parallelism and the power state of CPU-cores in combination. Based on experimental observations, we design a technique that adaptively identifies, in linear time within a bi-dimensional space, the optimal parallelism and power state setting. We evaluated the proposed technique with different benchmark applications, and using different methods for synchronizing threads when accessing shared data, and we compared it with other state-of-the-art power capping techniques.

In state-of-the-art Software Transactional Memory (STM) systems, threads carry out the execution of transactions as non-interruptible tasks. Hence, a thread can react to the injection of a higher priority transactional task and take care of its processing only at the end of the currently executed transaction. In this article we pursue a paradigm shift where the execution of an in-memory transaction is carried out as a preemptable task, so that a thread can start processing a higher priority transactional task before finalizing its current transaction. We achieve this goal in an application-transparent manner, by only relying on Operating System facilities we include in our preemptive STM architecture. With our approach we are able to re-evaluate CPU assignment across transactions along a same thread every few tens of microseconds. This is mandatory for an effective priority-aware architecture given the typically finer-grain nature of in-memory transactions compared to their counterpart in database systems. We integrated our preemptive STM architecture with the TinySTM package, and released it as open source. We also provide the results of an experimental assessment of our proposal based on running a port of the TPC-C benchmark to the STM environment.

We present a multi-word atomic (1,N) register for multi-core machines exploiting Read-Modify-Write (RMW) instructions to coordinate the writer and the readers in a wait-free manner. Our proposal, called Anonymous Readers Counting (ARC), enables large-scale data sharing by admitting up to 2^{32}-2 concurrent readers on off-the-shelf 64-bit machines, as opposed to the most advanced RMW-based approach which is limited to 58 readers. Further, ARC avoids multiple copies of the register content while accessing it-this affects classical register's algorithms based on atomic read/write operations on single words. Thus, ARC allows for higher scalability with respect to the register size.

The increasing diffusion of shared-memory multi-core machines has given rise to a change in the design of Parallel Discrete Event Simulation (PDES) platforms. In particular, the possibility to share large amounts of memory by many worker threads has lead to a boost in the adoption of non-blocking coordination algorithms, which have been proven to offer higher scalability when compared to their blocking counterparts based on critical sections. In this article we present an innovative non-blocking algorithm for computing Global Virtual Time (GVT) - namely, the current commit horizon-in multi-thread PDES engines to be run on top of multi-core machines. Beyond being non-blocking, our proposal has the advantage of providing a logarithmic (rather than linear) number of per-thread memory operations - read/write operations of values involved in the reduction for computing the GVT value-vs the amount of threads participating in the GVT computation. This allows for keeping low the actual CPU time that is required for determining the new GVT value. We compare our algorithm with a literature solution, still based on the non-blocking approach, but entailing a linear number of memory operations, quantifying the advantages from our proposal especially for very large numbers of threads participating in the GVT computation.

Shared-memory multi-core platforms are changing the nature of Parallel Discrete Event Simulation (PDES) because of the possibility to fully share the workload of events to be processed across threads. In this context, one rising PDES paradigm - referred to as share-everything PDES - is no longer based on the concept of (temporary) biding of simulation objects to worker threads. Rather, each worker threads can - at any time - pick from a fully shared event pool an event to process which can be destined to whatever simulation object. While attention has been posed on the design of concurrent shared pools, allowing non-blocking parallel operations, the scenario where two (or more) threads pick events destined to the same simulation object still lacks adequate synchronization support. In fact, these events are currently sequentialized and processed in a critical section touching the simulation object state, thus leading threads to mutually block each other. In this article we present the design of a share-everything speculative PDES engine that prevents mutual thread blocks because of the access to a same object state. In our design, the non-blocking property is seen as a vertical attribute of the engine (not only of the event pool). This vertical view demands for innovative event-dispatching schemes and, at the same time, innovative interactions with (and management of) the fully-shared event pool, which are features that we embed in our innovative design.

Taking advantage of computing capabilities offered by modern parallel and distributed architectures is fundamental to run large-scale simulation models based on the Parallel Discrete Event Simulation (PDES) paradigm. By relying on this computing organization, it is possible to effectively overcome both the power and the memory wall, which are core limiting aspects to deliver high-performance simulations. This is even more the case when relying on the speculative Time Warp synchronization protocol, which could be particularly memory greedy. At the same time, some form of coordination, such as the computation of the Global Virtual Time (GVT), is required by Time Warp Systems. These coordination points could easily become the bottleneck of large-scale simulations, hindering an efficient exploitation of the computing power offered by large supercomputing facilities. In this paper we present ORCHESTRA, a coordination algorithm which is both wait-free and asynchronous. The nature of this algorithm allows any computing node to carry on simulation activities while the global agreement is reached, thus offering an effective building block to achieve scalable PDES. We claim that the general organization of ORCHESTRA could be adopted by different high-performance computing applications, thus paving the way to a more effective usage of modern computing infrastructures.

Software Transactional Memory (STM) allows encapsulating shared-data accesses within transactions, executed with atomicity and isolation guarantees. The assessment of the consistency of a running transaction is performed by the STM layer at specific points of its execution, such as when a read or write access to a shared object occurs, or upon a commit attempt. However, performance and energy efficiency issues may arise when no shared-data read/write operation occurs for a while along a thread running a transaction. In this scenario, the STM layer may not regain control for a considerable amount of time, thus not being able to early detect if such transaction has become inconsistent in the meantime. To tackle this problem we present an STM architecture that, thanks to a lightweight operating system support, is able to perform a fine-grain periodic (hence prompt) revalidation of running transactions. Our proposal targets Linux and x86 systems and has been integrated with the open source TinySTM package. Experimental results with a port of the TPC-C benchmark to STM environments show the effectiveness of our solution.

State recoverability is a crucial aspect of speculative Time Warp-based Parallel Discrete Event Simulation. In the literature, we can identify three major classes of techniques to support the correct restoration of a previous simulation state upon the execution of a rollback operation: state checkpointing/restore, manual reverse computation and automatic reverse computation. The latter class has been recently supported by relying either on binary code instrumentation or on source-to-source code transformation. Nevertheless, both solutions are not intrinsically meant to support a reversible execution of third-party shared libraries, which can be pretty useful when implementing complex simulation models.

Emerging share-everything Parallel Discrete Event Simulation (PDES) platforms rely on worker threads fully sharing the workload of events to be processed. These platforms require efficient event pool data structures enabling high concurrency of extraction/insertion operations. Non-blocking event pool algorithms are raising as promising solutions for this problem. However, the classical non-blocking paradigm leads concurrent conflicting operations, acting on a same portion of the event pool data structure, to abort and then retry. In this article we present a conflict-resilient non-blocking calendar queue that enables conflicting dequeue operations, concurrently attempting to extract the minimum element, to survive, thus improving the level of scalability of accesses to the hot portion of the data structure---namely the bucket to which the current locality of the events to be processed is bound. We have integrated our solution within an open source share-everything PDES platform and report the results of an experimental analysis of the proposed concurrent data structure compared to some literature solutions.

Nowadays, a plethora of techniques and methods are available to optimize the runtime behavior of complex applications, ranging from modeling/prediction tools to the employment of recognized patterns and/or knowledge-bases on the expected performance under specific workloads. However, in common scenarios, the ultimate applications' behavior may depend on features that are scarcely predictable or difficult to be taken into account when designing the applications and their own runtime optimizers. Among them, we mention the actual structure of the underlying hardware and/or virtualized platforms, as well as specific runtime dynamics such as thread correlation on data and synchronization---not much the average behavior, rather punctual effects. We believe that the environment where applications live, like operating systems and user-space runtime libraries, play a central role in coping with these features. We similarly believe that such environments must be re-staged so as to be actually effective in pursuing the performance optimization goal. In this talk, we discuss specific guidelines to re-stage the environments, based on a real experience, and we point as well to challenges that are still untackled and deserve attention by the research community.

A common approach to improve memory access in NUMA machines exploits operating system (OS) page protection mechanisms to induce faults to determine which pages are accessed by what thread, so as to move the thread and its working-set of pages to the same NUMA node. However, existing proposals do not fully fit the requirements of truly multi-thread applications with non-partitioned accesses to virtual pages. In fact, these proposals exploit (induced) faults on a same page-table for all the threads of a same process to determine the access pattern. Hence, the fault by one thread (and the consequent re-opening of the access to the corresponding page) would mask those by other threads on the same page. This may lead to inaccuracy in the estimation of the working-set of individual threads. We overcome this drawback by presenting a lightweight operating system support for Linux, referred to as multi-view address space, explicitly targeting accuracy of per-thread working-set estimation in truly multi-thread applications with non-partitioned accesses, and an associated thread/data migration policy. Our solution is fully transparent to user-space code. It is embedded in a Linux/x86_64 module that installs any required modification to the original kernel image by solely relying on dynamic patching. A motivated case study in the context of HPC is also presented for an assessment of our proposal.

The large diffusion of highly-parallel shared-memory multi-core machines has led Parallel Discrete Event Simulation (PDES) platforms to a shift towards a share-everything model. This model is based on loose coupling between simulation objects and threads, lasting (as an extreme) no more than the lifetime of individual events. Concurrent threads can therefore CPU-dispatch events destined to any object at any point in time, thus fully sharing the workload of events to be processed on a fine grain basis. This demands for efficient mechanisms to share the overall pool of pending events by enabling parallelism in insertion and extraction operations. In this article we present a lock-free event pool which also provides amortized O(1) time complexity for both insertions and extractions. It can sustain highly concurrent accesses, while not leading to noticeable performance degradation when scaling up the thread count. Experimental results demonstrate that our solution stands as a core facility capable of further raising up the pragmatical impact of such an emerging share-everything PDES paradigm.

Software Transactional Memory (STM) may suffer from performance degradation due to excessive conflicts among concurrent transactions. An approach to cope with this issue consists in putting in place smart scheduling policies which temporarily suspend the execution of some transaction in order to reduce the actual conflict rate. In this paper, we present an adaptive transaction scheduling policyrelying on a Markov Chain-based model of STM systems. The policy is adaptive in a twofold sense: (i) it schedules transactions depending on throughput predictions by the model as a function of the current system state, (ii) its underlying Markov Chain-based model is periodically re-instantiated at run-time to adapt it to dynamic variations of the workload. We also present an implementation of our adaptive transaction scheduler which has been integrated within the open source TinySTM package. The accuracy of our performance model in predicting the system throughput and the advantages of the adaptive scheduling policy over state-of-the-art approaches have been assessed via an experimental study based on the STAMP benchmark suite.

Memory access tracing is a program analysis technique with many different applications, ranging from architectural simulation to (on-line) data placement optimization and security enforcement. In this article we propose a memory access tracing approach based on static x86 binary instrumentation. Unlike non-selective schemes, which instrument all the memory access instructions, our proposal selectively instruments a subset of those instructions that are the most (or fully) representative of the actual memory access pattern. The selection of the memory access instructions to be instrumented is based on a new method, which clusters instructions on the basis of their compile/link-time observable address expressions and selects representatives of these clusters. This allows for reducing the runtime cost for running instrumented code, while still enabling high accuracy in the determination of memory accesses. The trade-off between overhead and precision of the tracing process is user-tunable, so that it can be set depending on the final objective of memory access tracing (say on-line vs off-line exploitation). Additionally, our approach can track memory access at different granularity (e.g., virtual-pages or cache line-sized buffers), thus having applications in a variety of different contexts. The effectiveness of our proposal is demonstrated via experiments with applications taken from the PARSEC benchmark suite.

A recent trend has shown the relevance of PDES paradigms where simulation objects are no longer seen as fully disjoint entities only interacting via events' scheduling. Particularly, mutual cross-state access (as a form of state sharing) can represent an approach enabling the simplification of the programmer's job. In this article, we present a multi-core oriented Time Warp platform supporting so called granular objects, where cross-state access is transparently enabled jointly with the dynamic clustering (granulation) of objects into groups depending on the volume of mutual state accesses along phases of the model execution. Each group represents an island where activities are sequentially dispatched in timestamp order. Concurrency is still preserved by enabling the optimistic execution of the different islands. Granulated objects do not pay synchronization costs due to mutual causal inconsistencies. Also, the underlying Time Warp platform does not pay memory management (e.g. memory access tracing) overheads to determine that mutual accesses are taking place within a group. Overall, the platform transparently (and dynamically) determines a well-suited granulation of the overall model state, and a corresponding level of concurrency, depending on the actual state access pattern by the simulation code. As far as we know, this is the first study where the problem of clustering Time Warp simulation objects is addressed for the case of in-place cross-object state accesses by the application code, and where dynamic granulation of multiple objects in a larger one is supported in a fully transparent manner. We integrated our proposal in the open source ROOT-Sim platform.

In this article we introduce GMU, a genuine partial replication protocol for transactional systems, which exploits an innovative, highly scalable, distributed multiversioning scheme. Unlike existing multiversion-based solutions, GMU does not rely on any global logical clock, which may represent a contention point and a major impairment to system scalability. Also, GMU never aborts read-only transactions and spares them from undergoing distributed validation schemes. This makes GMU particularly efficient in presence of read-intensive workloads, as typical of a wide range of real-world applications. GMU guarantees the Extended Update Serializability (EUS) isolation level. This consistency criterion is particularly attractive as it is sufficiently strong to ensure correctness even for very demanding applications (such as TPC-C), but is also weak enough to allow efficient and scalable implementations, such as GMU. Further, unlike several relaxed consistency models proposed in literature, EUS shows simple and intuitive semantics, thus being an attractive consistency model for ordinary programmers. We integrated GMU in a popular open source in-memory transactional data grid, namely Infinispan. On the basis of a wide experimental study performed on heterogeneous platforms and using industry standard benchmarks (namely TPC-C and YCSB), we show that GMU achieves almost linear scalability and that it introduces reduced overhead, with respect to solutions ensuring non-serializable semantics, in a wide range of workloads.

This article presents an innovative runtime support for speculative parallel processing of discrete event simulation models on multi-core architectures, which exploits Hardware-Transactional-Memory (HTM) facilities for the purpose of state recoverability. In this proposal, the speculative updates on the state of the simulation model are executed as concurrent HTM-based transactions that are also in charge of detecting whether the update is consistent with the advancement of logical-time along model execution. Our proposal is fully transparent to the application code. Hence, our HTM-based run-time support can host conventionally developed discrete event models relying on the concept of event-handlers to be dispatched by an underlying simulation engine. Experimental data show that our proposal provides 75% to 92% of the ideal speedup on an Intel Haswell based platform (equipped with 4 physical cores and HTM support) for discrete event models with event granularity ranging between 2 and 12 microseconds. The data also show that these same models cannot be executed efficiently on top of a last generation parallel discrete event simulation platform employing software-based recoverability.

The rollback operation is a fundamental building block to support the correct execution of a speculative Time Warp-based Parallel Discrete Event Simulation. In the literature, several solutions to reduce the execution cost of this operation have been proposed, either based on the creation of a checkpoint of previous simulation state images, or on the execution of negative copies of simulation events which are able to undo the updates on the state. In this paper, we explore the practical design and implementation of a state recoverability technique which allows to restore a previous simulation state either relying on checkpointing or on the reverse execution of the state updates occurred while processing events in forward mode. Differently from other proposals, we address the issue of executing backward updates in a fully-transparent and event granularity-independent way, by relying on static software instrumentation (targeting the x86 architecture and Linux systems) to generate at runtime reverse update code blocks (not to be confused with reverse events, proper of the reverse computing approach). These are able to undo the effects of a forward execution while minimizing the cost of the undo operation. We also present experimental results related to our implementation, which is released as free software and fully integrated into the open source ROOT-Sim (ROme OpTimistic Simulator) package. The experimental data support the viability and effectiveness of our proposal.

The order according to which the different tasks are carried out within a Time Warp platform has a direct impact on performance, given that event processing is speculative, thus being subject to the possibility of being rolled-back. It is typically recognized that not-yet-executed events having lower timestamps should be given higher CPU-schedule priority, since this contributes to keep low the amount of rollbacks. However, common Time Warp platforms usually execute events as atomic actions. Hence control is bounced back to the underlying simulation platform only at the end of the current event processing routine. In other words, CPU-scheduling of events resembles classical batch-multitasking scheduling, which is recognized not to promptly react to variations of the priority of pending tasks (e.g. associated with the injection of new events in the system). In this article we present the design and implementation of a time-sharing Time Warp platform, to be run on multi-core machines, where the platform-level software is allowed to take back control on a periodical basis (with fine grain period), and to possibly preempt any ongoing event processing activity in favor of dispatching (along the same thread) any other event that is revealed to have higher priority. Our proposal is based on an ad-hoc kernel module for Linux, which implements a fine grain timer-interrupt mechanism with lightweight management, which is fully integrated with the modern top/bottom-half timer-interrupt Linux architecture, and which does not induce any bias in terms of relative CPU-usage planning across Time Warp vs non-Time Warp threads running on the machine. Our time-sharing architecture has been integrated within the open source ROOT-Sim optimistic simulation package, and we also report some experimental data for an assessment of our proposal.

It is well known that Time Warp may suffer from large usage of memory, which may hamper the efficiency of the memory hierarchy. To cope with this issue, several approaches have been devised, mostly based on the reduction of the amount of used virtual memory, e.g., by the avoidance of checkpointing and the exploitation of reverse computing. In this article we present an orthogonal solution aimed at optimizing the latency for memory access operations when running Time Warp systems on Non-Uniform Memory Access (NUMA) multi-processor/multi-core computing systems. More in detail, we provide an innovative Linux-based architecture allowing per simulation-object management of memory segments made up by disjoint sets of pages, and supporting both static and dynamic binding of the memory pages reserved for an individual object to the different NUMA nodes, depending on what worker thread is in charge of running that simulation object along a given wall-clock-time window. Our proposal not only manages the virtual pages used for the live state image of the simulation object, rather, it also copes with memory pages destined to keep the simulation object's event buffers and any recoverability data. Further, the architecture allows memory access optimization for data (messages) exchanged across the different simulation objects running on the NUMA machine. Our proposal is fully transparent to the application code, thus operating in a seamless manner. Also, a free software release of our NUMA memory manager for Time Warp has been made available within the open source ROOT-Sim simulation platform. Experimental data for an assessment of our innovative proposal are also provided in this article.

Disjoint-Access Parallelism (DAP) is considered one of the most desirable properties to maximize the scalability of Transactional Memory (TM). This paper investigates the possibility and inherent cost of implementing a DAP TM that ensures two properties that are regarded as important to maximize efficiency in read-dominated workloads, namely having invisible and wait-free read-only transactions. We first prove that relaxing Real-Time Order (RTO) is necessary to implement such a TM. This result motivates us to introduce Witnessable Real-Time Order (WRTO), a weaker variant of RTO that demands enforcing RTO only between directly conflicting transactions. Then we show that adopting WRTO makes it possible to design a strictly DAP TM with invisible and wait-free read-only transactions, while preserving strong progressiveness for write transactions and an isolation level known in literature as Extended Update Serializability. Finally, we shed light on the inherent inefficiency of DAP TM implementations that have invisible and wait-free read-only transactions, by establishing lower bounds on the time and space complexity of such TMs.

Classical approaches to performance prediction rely on two, typically antithetic, techniques: Machine Learning (ML) and Analytical Modeling (AM). ML takes a black box approach, whose accuracy strongly depends on the representativeness of the dataset used during the initial training phase. Specifically, it can achieve very good accuracy in areas of the features' space that have been sufficiently explored during the training process. Conversely, AM techniques require no or minimal training, hence exhibiting the potential for supporting prompt instantiation of the performance model of the target system. However, in order to ensure their tractability, they typically rely on a set of simplifying assumptions. Consequently, AM's accuracy can be seriously challenged in scenarios (e.g., workload conditions) in which such assumptions are not matched.

We present the design and implementation of an autonomic state manager (ASM) tailored for integration within optimistic parallel discrete event simulation (PDES) environments based on the C programming language and the executable and linkable format (ELF), and developed for execution on ×86_64 architectures. With ASM, the state of any logical process (LP), namely the individual (concurrent) simulation unit being part of the simulation model, is allowed to be scattered on dynamically allocated memory chunks managed via standard API (e.g., malloc/free). Also, the application programmer is not required to provide any serialization/ deserialization module in order to take a checkpoint of the LP state, or to restore it in case a causality error occurs during the optimistic run, or to provide indications on which portions of the state are updated by event processing, so to allow incremental checkpointing. All these tasks are handled by ASM in a fully transparent manner via (A) runtime identification (with chunk-level granularity) of the memory map associated with the LP state, and (B) runtime tracking of the memory updates occurring within chunks belonging to the dynamic memory map. The co-existence of the incremental and non-incremental log/restore modes is achieved via dual versions of the same application code, transparently generated by ASM via compile/link time facilities. Also, the dynamic selection of the best suited log/ restore mode is actuated by ASM on the basis of an innovative modeling/optimization approach which takes into account stability of each operating mode with respect to variations of the model/environmental execution parameters.

In this article we exploit a combination of analytical and Machine Learning (ML) techniques in order to build a performance model allowing to dynamically tune the level of concurrency of applications based on Software Transactional Memory (STM). Our mixed approach has the advantage of reducing the training time of pure machine learning methods, and avoiding approximation errors typically affecting pure analytical approaches. Hence it allows very fast construction of highly reliable performance models, which can be promptly and effectively exploited for optimizing actual application runs. We also present a real implementation of a concurrency regulation architecture, based on the mixed modeling approach, which has been integrated with the open source Tiny STM package, together with experimental data related to runs of applications taken from the STAMP benchmark suite demonstrating the effectiveness of our proposal.

In this article we tackle transparent parallelization of Discrete Event Simulation (DES) models to be run on top of multi-core machines according to speculative schemes. The innovation in our proposal lies in that we consider a more general programming and execution model, compared to the one targeted by state of the art PDES platforms, where the boundaries of the state portion accessible while processing an event at a specific simulation object do not limit access to the actual object state, or to shared global variables. Rather, the simulation object is allowed to access (and alter) the state of any other object, thus causing what we term cross-state dependency. We note that this model exactly complies with typical (easy to manage) sequential-style DES programming, where a (dynamically-allocated) state portion of object A can be accessed by object B in either read or write mode (or both) by, e.g., passing a pointer to B as the payload of a scheduled simulation event. However, while read/write memory accesses performed in the sequential run are always guaranteed to observe (and to give rise to) a consistent snapshot of the state of the simulation model, consistency is not automatically guaranteed in case of parallelization and concurrent execution of simulation objects with cross-state dependencies. We cope with such a consistency issue, and its application-transparent support, in the context of parallel and optimistic executions. This is achieved by introducing an advanced memory management architecture, able to efficiently detect read/write accesses by concurrent objects to whichever object state in an application transparent manner, together with advanced synchronization mechanisms providing the advantage of exploiting parallelism in the underlying multi-core architecture while transparently handling both cross-state and traditional event-based dependencies. Our proposal targets Linux and has been integrated with the ROOT-Sim open source optimistic simulation platform, although its design principles, and most parts of the developed software, are of general relevance.

In this paper we explore machine-learning approaches for dynamically selecting the well suited amount of concurrent threads in applications relying on Software Transactional Memory (STM). Specifically, we present a solution that dynamically shrinks or enlarges the set of input features to be exploited by the machine-learner. This allows for tuning the concurrency level while also minimizing the overhead for input-features sampling, given that the cardinality of the input-feature set is always tuned to the minimum value that still guarantees reliability of workload characterization. We also present a fully heedged implementation of our proposal within the TinySTM open source framework, and provide the results of an experimental study relying on the STAMP benchmark suite, which show significant reduction of the response time with respect to proposals based on static feature selection.

Global Virtual Time (GVT) is a powerful abstraction used to discriminate what events belong (and what do not belong) to the past history of a parallel/distributed computation. For high performance simulation systems based on the Time Warp synchronization protocol, where concurrent simulation objects are allowed to process their events speculatively and causal consistency is achieved via rollback/recovery techniques, GVT is used to determine which portion of the simulation can be considered as committed. Hence it is the base for actuating memory recovery (e.g. of obsolete logs that were taken in order to support state recoverability) and nonrevocable operations (e.g. I/O). For shared memory implementations of simulation platforms based on the Time Warp protocol, the reference GVT algorithm is the one presented by Fujimoto and Hybinette [1]. However, this algorithm relies on critical sections that make it non-wait-free, and which can hamper scalability. In this article we present a waitfree shared memory GVT algorithm that requires no critical section. Rather, correct coordination across the processes while computing the GVT value is achieved via memory atomic operations, namely compare-and-swap. The price paid by our proposal is an increase in the number of GVT computation phases, as opposed to the single phase required by the proposal in [1]. However, as we show via the results of an experimental study, the wait-free nature of the phases carried out in our GVT algorithm pays-off in reducing the actual cost incurred by the proposal in [1].

In this article, we introduce TAS (Transactional Auto Scaler), a system for automating the elastic scaling of replicated in-memory transactional data grids, such as NoSQL data stores or Distributed Transactional Memories. Applications of TAS range from online self-optimization of in-production applications to the automatic generation of QoS/cost-driven elastic scaling policies, as well as to support for what-if analysis on the scalability of transactional applications. In this article, we present the key innovation at the core of TAS, namely, a novel performance forecasting methodology that relies on the joint usage of analytical modeling and machine learning. By exploiting these two classically competing approaches in a synergic fashion, TAS achieves the best of the two worlds, namely, high extrapolation power and good accuracy, even when faced with complex workloads deployed over public cloud infrastructures. We demonstrate the accuracy and feasibility of TAS’s performance forecasting methodology via an extensive experimental study based on a fully fledged prototype implementation integrated with a popular open-source in-memory transactional data grid (Red Hat’s Infinispan) and industry-standard benchmarks generating a breadth of heterogeneous workloads.

Edge computing is a powerful tool to face the challenging performance requirements of modern Internet applications. By replicating applications' data and logic across a large number of geographically distributed servers, edge computing platforms allow to achieve significant enhancements of the proximity between clients and contents, and of the system scalability. These platforms reveal highly effective when handling requests entailing read-only access to the application data, as these requests can be autonomously served by some edge server typically located closer to the client than the origin site. However, in contexts where end users can trigger transactional manipulations of the application state (e.g., e-Commerce, auctions or financial applications), the corresponding update requests typically need to be redirected to the origin transactional data sources, thus, nullifying any performance benefit arising from data replication and client proximity. To cope with this issue, in this paper, we present a parallel invocation protocol, which exploits the path-diversity along the end-to-end interaction toward the origin sites by concurrently routing transactional requests toward multiple-edge servers. Request processing is finally carried out by a single-edge server, adaptively selected as the most responsive one depending on current system conditions. The proposed edge server selection scheme does not require coordination among (geographically distributed) edge server instances, thus, being very light and scalable. The benefits from our protocol in terms of both reduced and more predictable end-to-end latency are quantified via an extended simulation study.

We investigate the feasibility of systematic speculative processing in the context of Optimistic Atomic Broadcast (OAB) based replication of database systems. Specifically, we present the design and prototypal implementation of a fully speculative version of the Postgre SQL open source relational database, together with experimental results showing performance advantages over non-speculative replication.

Optimistic synchronization is considered an effective means for supporting Parallel Discrete Event Simulations. It relies on a speculative approach, where concurrent processes execute simulation events regardless of their safety, and consistency is ensured via proper rollback mechanisms, upon the a-posteriori detection of causal inconsistencies along the events' execution path. Interactions with the outside world (e.g. generation of output streams) are a well-known problem for rollback-based systems, since the outside world may have no notion of rollback. In this context, approaches for allowing the simulation modeler to generate consistent output rely on either the usage of ad-hoc APIs (which must be provided by the underlying simulation kernel) or temporary suspension of processing activities in order to wait for the final outcome (commit/rollback) associated with a speculatively-produced output.

In Parallel Discrete Event Simulation (PDES), the simulation model is partitioned into a set of distinct Logical Processes (LPs) which are allowed to concurrently execute simulation events. In this work we present an innovative approach to load-sharing on multi-core/multiprocessor machines, targeted at the optimistic PDES paradigm, where LPs are speculatively allowed to process simulation events with no preventive verification of causal consistency, and actual consistency violations (if any) are recovered via rollback techniques. In our approach, each simulation kernel instance, in charge of hosting and executing a specific set of LPs, runs a set of worker threads, which can be dynamically activated/deactivated on the basis of a distributed algorithm. The latter relies in turn on an analytical model that provides indications on how to reassign processor/core usage across the kernels in order to handle the simulation workload as efficiently as possible. We also present a real implementation of our load-sharing architecture within the ROme OpTimistic Simulator (ROOT-Sim), namely an open-source C-based simulation platform implemented according to the PDES paradigm and the optimistic synchronization approach. Experimental results for an assessment of the validity of our proposal are presented as well.

In this article we introduce GMU, a genuine partial replication protocol for transactional systems, which exploits an innovative, highly scalable, distributed multiversioning scheme. Unlike existing multiversion-based solutions, GMU does not rely on a global logical clock, which represents a contention point and can limit system scalability. Also, GMU never aborts read-only transactions and spares them from distributed validation schemes. This makes GMU particularly efficient in presence of read-intensive workloads, as typical of a wide range of real-world applications. GMU guarantees the Extended Update Serializability (EUS) isolation level. This consistency criterion is particularly attractive as it is sufficiently strong to ensure correctness even for very demanding applications (such as TPC-C), but is also weak enough to allow efficient and scalable implementations, such as GMU. Further, unlike several relaxed consistency models proposed in literature, EUS has simple and intuitive semantics, thus being an attractive, scalable consistency model for ordinary programmers. We integrated the GMU protocol in a popular open source in-memory transactional data grid, namely Infinispan. On the basis of a large scale experimental study performed on heterogeneous experimental platforms and using industry standard benchmarks (namely TPC-C and YCSB), we show that GMU achieves linear scalability and that it introduces negligible overheads (less than 10%), with respect to solutions ensuring non-serializable semantics, in a wide range of workloads.

Traditionally, Logical Processes (LPs) forming a simulation model store their execution information into disjoint simulations states, forcing events exchange to communicate data between each other. In this work we propose the design and implementation of an extension to the traditional Time Warp (optimistic) synchronization protocol for parallel/distributed simulation, targeted at shared-memory/multicore machines, allowing LPs to share parts of their simulation states by using global variables. In order to preserve optimism's intrinsic properties, global variables are transparently mapped to multi-version ones, so to avoid any form of safety predicate verification upon updates. Execution's consistency is ensured via the introduction of a new rollback scheme which is triggered upon the detection of an incorrect global variable's read. At the same time, efficiency in the execution is guaranteed by the exploitation of non-blocking algorithms in order to manage the multi-version variables' lists. Furthermore, our proposal is integrated with the simulation model's code through software instrumentation, in order to allow the application-level programmer to avoid using any specific API to mark or to inform the simulation kernel of updates to global variables. Thus we support full transparency. An assessment of our proposal, comparing it with a traditional message-passing implementation of variables' multi-version is provided as well.

One of the problems of Software-Transactional-Memory (STM) systems is the performance degradation that can be experienced when applications run with a non-optimal concurrency level, namely number of concurrent threads. When this level is too high a loss of performance may occur due to excessive data contention and consequent transaction aborts. Conversely, if concurrency is too low, the performance may be penalized due to limitation of both parallelism and exploitation of available resources. In this paper we propose a machine-learning based approach which enables STM systems to predict their performance as a function of the number of concurrent threads in order to dynamically select the optimal concurrency level during the whole lifetime of the application. In our approach, the STM is coupled with a neural network and an on-line control algorithm that activates or deactivates application threads in order to maximize performance via the selection of the most adequate concurrency level, as a function of the current data access profile. A real implementation of our proposal within the TinySTM open-source package and an experimental study relying on the STAMP benchmark suite are also presented. The experimental data confirm how our self-adjusting concurrency scheme constantly provides optimal performance, thus avoiding performance loss phases caused by non-suited selection of the amount of concurrent threads and associated with the above depicted phenomena.

Recent advances in the field of replicated, fault tolerant transactional systems make systematic use of Optimistic Atomic Broadcast (OAB) group communication primitives in order to coordinate the replicas. According to this scheme, the replicas gain information on the existence of transactional requests before a final and global agreement is reached on the transaction serialization order. Hence, speculative processing schemes can be exploited in order to maximize the overlap between local computation and distributed coordination activities. In this article we present ASAP, an innovative Aggressive SpeculAtive Protocol, which exhibits the following two peculiarities: (A) it allows speculating along different transaction serialization orders, thus increasing the likelihood of successful overlap between local processing and coordination in case of mismatches between the optimistic and the final delivery sequence of incoming requests, (B) it speculates along chains of conflicting transactions, tracking data dependencies among transactions via an innovative concurrency control mechanism, which allows determining in a timely fashion the alternative serialization orders to be speculatively explored. Via a simulation study in the context of Software Transactional Memory systems we show ASAP can achieve robust performance independently of the likelihood of reorder between optimistic and final deliveries, providing remarkable performance improvements (enhancing the maximum sustainable throughput up to a 2x factor) with respect to state of the art speculative replication protocols.

This paper introduces SPECULA, a novel replication protocol for Software Transactional Memory (STM) systems that seeks maximum overlap between transaction execution and replica synchronization phases via speculative processing techniques. By removing the replica synchronization phase from the critical path of execution of transactions, SPECULA allows threads to speculatively pipeline the execution of both transactional and/or non-transactional code. The core of SPECULA is a multi-version concurrency control algorithm that supports speculative transaction processing while ensuring the strong consistency criteria that are desirable in non-sand-boxed environments like STMs. Via an experimental study, based on a fully-fledged prototype and on both synthetic and standard STM benchmarks, we demonstrate that SPECULA can achieve speedups of up to one order of magnitude with respect to state-of-the-art non-speculative replication techniques.

In this work we present OSARE, an active replication protocol for transactional systems that combines the usage of Optimistic Atomic Broadcast with a speculative concurrency control mechanism in order to overlap transaction processing and replica synchronization. OSARE biases the speculative serialization of transactions towards an order aligned with the optimistic message delivery order. However, due to the lock-free nature of its concurrency control algorithm, at high concurrency levels, namely when the probability of mismatches between optimistic and final deliveries is higher, OSARE explores additional alternative transaction serialization orders in a lightweight and opportunistic fashion. A simulation study we carried out in the context of Software Transactional Memory systems shows that OSARE achieves robust performance also in scenarios characterized by non-minimal likelihood of reorder between optimistic and final deliveries, providing remarkable speed-up with respect to state of the art speculative replication protocols.

In this paper, we address reliability issues in three-tier systems with stateless application servers. For these systems, a framework called e-Transaction has been recently proposed, which specifies a set of desirable end-to-end reliability guarantees. In this article, we propose an innovative distributed protocol providing e-Transaction guarantees in the general case of multiple, autonomous back-end databases (typical of scenarios with multiple parties involved within a same business process). Differently from existing proposals coping with the e-Transaction framework, our protocol does not rely on any assumption on the accuracy of failure detection. Hence, it reveals suited for a wider class of distributed systems. To achieve such a target, our protocol exploits an innovative scheme for distributed transaction management (based on ad hoc demarcation and concurrency control mechanisms), which we introduce in this paper. Beyond providing the proof of protocol correctness, we also discuss hints on the protocol integration with conventional systems (e.g., database systems) and show the minimal overhead imposed by the protocol.

We present an implementation of the Lowest- Timestamp-First (LTF) algorithm for the identification of the next Logical Process (LP) to be dispatched in context where the optimistic simulation kernel conforms the best-practice of keeping separate event lists for the hosted LPs. The implementation provides low-overhead, constant-time dispatching. We release our implementation within the open source ROOT-Sim optimistic simulation platform. Experimental data are also reported supporting the effectiveness of our proposal.

In this paper we investigate the problem of speculative processing in a replicated transactional system layered on top of an optimistic atomic broadcast service. We consider a realistic model in which transactions' read/write sets are not known a-priori, and transactions' data access patterns may vary depending on the observed snapshot. We formalize a set of correctness and optimality properties aimed at ensuring that transactions are not activated on inconsistent snapshots, as well as the minimality and completeness of the set of explored serialization orders. Finally, an optimal speculative transaction replication protocol is presented.

Pervasive Grid applications solve complex tasks in distributed environments relying on centralized and decentralized nodes interconnected by wireless and wired networks. Examples of such applications are Emergency Management and Intelligent Transportation. In previous works we introduced the ASSISTANT programming model as a support for easy and effective development of pervasive Grid applications. In this work we extend ASSISTANT in order to support fault tolerance. This is done by providing constructs enabling and controlling replication. Via these constructs, the application programmers can express replication strategies, which are automatically managed by the ASSISTANT run-time support in terms of replica consistency. We also report some experimental results showing reduced performance overheads for the classical case of replica consistency relying on a-priori agreement on the processing order of input streams in case of a flood emergency management application.

In this paper we address state recoverability in optimistic simulation systems by presenting an autonomic log/restore architecture. Our proposal is unique in that it jointly provides the following features: (i) log/restore operations are carried out in a completely transparent manner to the application programmer, (ii) the simulation-object state can be scattered across dynamically allocated non-contiguous memory chunks, (iii) two differentiated operating modes, incremental vs non-incremental, coexist via transparent, optimized run-time management of dual versions of the same application layer, with dynamic selection of the best suited operating mode in different phases of the optimistic simulation run, and (iv) determination of the best suited mode for any time frame is carried out on the basis of an innovative modeling/optimization approach that takes into account stability of each operating mode vs variations of the model execution parameters.

Software Transactional Memories (STMs) are emerging as a potentially disruptive programming model. In this paper we are address the issue of how to enhance dependability of STM systems via replication. In particular we present AGGRO, an innovative Optimistic Atomic Broadcast-based (OAB) active replication protocol that aims at maximizing the overlap between communication and processing through a novel AGGRessively Optimistic concurrency control scheme. The key idea underlying AGGRO is to propagate dependencies across uncommitted transactions in a controlled manner, namely according to a serialization order compliant with the optimistic message delivery order provided by the OAB service. Another relevant distinguishing feature of AGGRO is of not requiring a-priori knowledge about read/write sets of transactions, but rather to detect and handle conflicts dynamically, i.e. as soon (and only if) they materialize. Based on a detailed simulation study we show the striking performance gains achievable by AGGRO (up to 6x increase of the maximum sustainable throughput, and 75% response time reduction) compared to literature approaches for active replication of transactional systems.

We define the problem of speculative processing in a replicated transactional system layered on top of an optimistic atomic broadcast service. A realistic model is considered in which transactions' read and write sets are not a priori known and transactions' data access patterns may vary depending on the observed snapshot. We formalize a set of correctness and optimality properties ensuring the minimality and completeness of the set of explored serialization orders within the replicated transactional system.

In parallel discrete event simulation techniques, the simulation model is partitioned into objects, concurrently executing events on different CPUs and/or multiple CPU-Cores.In such a context, run-time supports for logical time synchronization across the different simulation objects play a central role in determining the effectiveness of the specific parallel simulation environment. In this paper we present an experimental evaluation of the memory management capabilities offered by the ROme OpTimistic Simulator (ROOT-Sim). This is an open source parallel simulation environment transparently supporting optimistic synchronization via recoverability (based on incremental log/restore techniques) of any type of memory operation affecting the state of simulation objects, i.e., memory allocation, deallocation and update operations. The experimental study is based on a synthetic benchmark which mimics different read/write patterns inside the dynamic memory map associated with the state of simulation objects. This allows sensibility analysis of time and space effects due to the memory management subsystem while varying the type and the locality of the accesses associated with event processing.

APART (A Posteriori Active ReplicaTion) is a recently proposed active replication protocol specifically tailored for multi-tier data acquisition systems. It ensures consistency of middle-tier sink replicas by means of an a-posteriori synchronization phase based on reconciliation, which is activated only in case replicas react to an input message from the sensors by generating an output event destined to the back-end tier. This paper enhances APART via a novel non-blocking synchronization scheme which prevents replicas from stalling while waiting for the outcome of an on-going synchronization phase. Contrarily, replicas are allowed to optimistically process data from the sensors, and to immediately propagate any output event towards the back-end tier. The removal of the blocking synchronization phase from the critical path gives rise to striking performance gains via an effective overlapping of event processing and synchronization. On the other hand, system consistency is ensured by enhancing the back-end tier synchronization logic in order to filter out optimistically produced output events that are incompatible with the reconciled state trajectory.

Multi-instance-precommit (MIP) has been recently presented as an innovative transaction management scheme in support of reliability for Atomic Transactions in multitier (e.g. Web-based) systems. With this scheme, fail-over of a previously activated transaction can be supported via simple retry logics, which do not require knowledge about whether, and on which sites, the original transaction was precommitted. Mutual deadlock between the original and the retried transaction are prevented via MIP facilities, which also support reconciliation mechanisms for at-most-once transaction execution semantic. In this article we present an extension of the open source PostgreSQL database system in order to support MIP. The extension is based on the exploitation of PostgreSQL native multiversion concurrency control scheme. We also present an experimental evaluation based on the TPC-W benchmark, aimed at quantifying the relative overhead of MIP facilities on transaction execution latency, system throughput and storage usage.

Simulation is becoming an increasingly important technique for what-if analysis in the context of (real-time) decision making applications. Consequently, quick delivery of simulation outputs to end-users (or applications) is a core objective. One approach for high performance simulation consists of exploiting parallel techniques, where the simulation model is partitioned into objects (or logical processes), concurrently executing events on different CPUs and/or multiple CPU-cores. For this type of simulation systems,a further run-time improvement arose from the exploitation of event uncertainty, both in time and space, which has lead to more flexible synchronization protocols. Although this approach can provide significant performance gains, one drawback is the risk of less reliable simulation results due to potential bias induced by the mechanisms for resolving the uncertainty, which are sometimes exclusively targeted to run-time effectiveness. In this article we focus on space uncertain simulation events in optimistic parallel simulation and introduce a mechanism that, compared to previous approaches, allows trading-off execution speed vs reliability of simulation results. In other words, our target is the achievement of high performance while controlling, at the same time, the bias introduced by space uncertainty on the simulation output.

The Markov modulated Poisson process (MMPP) has been shown to well describe the flow of incoming traffic in networked systems, such as the Grid and the WWW. This makes the MMPP/M/1 queue a valuable instrument to evaluate and predict the service level of networked servers. In a recent work we have provided an approximate solution for the response time distribution of the MMPP/M/1 queue, which is based on a weighted superposition of M/M/l queues (i.e. a hyper-exponential process). In this article we address the tradeoff between the accuracy of this approximation and its computational cost. By jointly considering both accuracy and cost, we identify the scenarios where such approximate solution could be effectively used in support of network servers (dynamic) configuration and evaluation strategies, aimed at ensuring the agreed dependability levels in case of, e.g., request redirection due to faults.

This paper proposes APART (a posteriori active replication), a novel active replication protocol specifically tailored for multi-tier data acquisition systems. Unlike existing active replication solutions, APART does not rely on a-priori coordination schemes determining a same schedule of events across all the replicas, but it ensures replicas consistency by means of an a-posteriori reconciliation phase. The latter is triggered only in case the replicated servers externalize their state by producing an output event towards a different tier. On one hand, this allows coping with non-deterministic replicas, unlike existing active replication approaches. On the other hand, it allows attaining striking performance gains in the case of silent replicated servers, which only sporadically, yet unpredictably, produce output events in response to the receipt of a (possibly large) volume of input messages. This is a common scenario in data acquisition systems, where sink processes, which filter and/or correlate incoming sensor data, produce output messages only if some application relevant event is detected. Further, the APART replica reconciliation scheme is extremely lightweight as it exploits the cross-tier communication pattern spontaneously induced by the application logic to avoid explicit replicas coordination messages.

In this paper we study how to reuse checkpoints taken in an uncorrelated manner during the forward execution phase in an optimistic simulation system in order to construct global consistent snapshots which are also committed (i.e. the logical time they refer to is lower than the current GVT value). This is done by introducing a heuristic-based mechanism relying on update operations applied to local committed checkpoints of the involved logical processes so to eliminate mutual dependencies among the final achieved state values. The mechanism is lightweight since it does not require any form of (distributed) coordination to determine which are the checkpoint update operations to be performed. At the same time it is likely to reduce the amount of checkpoint update operations required to realign the consistent global state exactly to the current GVT value, taken as the reference time for the snapshot. Our proposal can support, in a performance effective manner, termination detection schemes based on global predicates evaluated on a committed and consistent global snapshot, which represent an alternative as relevant as classical termination check only relying on the current GVT value. Another application concerns interactive simulation environments, where (aggregate) output information about committed and consistent snapshots needs to be frequently provided, hence requiring lightweight mechanisms for the construction of the snapshots.

The high-level-architecture (HLA) is an IEEE standard for the interoperability and integration of (autonomous) simulation packages and applications (termed federates in the HLA context). It is based on a middleware-level component referred to as run-time-infrastructure (RTI) offering a set of interoperability services to the overlying simulation software. Time-management is the suite of services allowing synchronized execution among the federates, which, according to the HLA specification, covers pure conservative and pure optimistic synchronization schemes. In this paper we provide the design and implementation of a software layer, we refer to as risk-free-speculator (RFS), which supports an optimistic oriented intermediate approach to synchronization embedding the aggressiveness property of optimistic systems, but discarding risk. This is done in a totally transparent manner to the overlying applications, and does not even require any modification of the underlying RTI. The effectiveness of RFS has been tested against simulated demonstration exercises using the Joint Semi-Automated Forces (JSAF) simulation program.

In this article we present the implementation of an environment supporting Lévy's optimal reduction for the λ-calculus on parallel (or distributed) computing systems. In a similar approach to Lamping's, we base our work on a graph reduction technique, known as directed virtual reduction , which is actually a restriction of Danos-Regnier virtual reduction. The environment, which we refer to as PELCR (parallel environment for optimal lambda-calculus reduction), relies on a strategy for directed virtual reduction, namely half combustion . While developing PELCR we adopted both a message aggregation technique, allowing reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors. We also present an experimental study demonstrating the ability of PELCR to definitely exploit the parallelism intrinsic to λ-terms while performing the reduction. We show how PELCR allows achieving up to 70--80% of the ideal speedup on last generation multiprocessor computing systems. As a last note, the software modules have been developed with the C language and using a standard interface for message passing, that is, MPI, thus making PELCR itself a highly portable software package.

A recently proposed abstraction, called e-transaction (exactly-once transaction), specifies a set of properties capturing end-to-end reliability aspects for three-tier Web-based systems. In this paper we propose a distributed protocol ensuring the e-transaction properties for the general case of multiple, autonomous back-end databases. The key idea underlying our proposal consists in distributing, across the back-end tier, some recovery information reflecting the transaction processing state. This information is manipulated at low cost via local operations at the database side, with no need for any form of coordination among asynchronous replicas of the application server within the middle-tier. Compared to existing solutions, our protocol has therefore the distinguishing features of being both very light and highly scalable. The latter aspect makes our proposal particularly attractive for the case of very high degree of replication of the application access point, with distribution of the replicas within infrastructures geographically spread on public networks over the Internet (e.g., application delivery networks), namely, a configuration that also provides the advantages of reduced user perceived latency and increased system availability

In this paper we explore active replication in the context of advanced simulation systems, with the aim of improving the timeliness for the production of simulation output. Our proposal is framed by the high-level-architecture (HLA), i.e. the middleware based standard for interoperability of simulation packages. It results in the design and implementation of an active replication management layer (ARML) targeted to SMP computing systems, which supports the execution of (diversity-based) active replicas of a same simulation package in a totally transparent manner

In this paper we explore active replication based on software diversity for improving the responsiveness of simulation systems. Our proposal is framed by the high-level-architecture (HLA), namely the emerging standard for interoperability of simulation packages, and results in the design and implementation of an active replication management layer (ARML), which supports the execution of multiple software diversity-based replicas of a same simulator in a totally transparent manner. Beyond presenting the replication framework and the design/implementation of ARML, we also report the results of an experimental evaluation on a case study, quantifying the benefits from our proposal in terms of execution speed

Response time is a key factor of any e-commerce application, and a set of solutions have been proposed to provide low response time despite network congestions or failures. Being them mostly based on caching of Web objects and replication of DBMS managed data at the edges, or at intermediate points, of the Web infrastructure, they reveal effective when handling client requests only performing read access to application data. However, any update request typically needs to be redirected to the origin DBMSs, hence not taking advantage from data replication and related client proximity. In order to alleviate the effects of network congestions or failures, we have proposed a multi-path protocol that increases the likelihood for the update request to be processed along a responsive (e.g. failure free) network path in between the client location and the origin DBMS sites. In this paper we present an extensive simulation study of the effects of such a multi-path approach on the client perceived response time. The study relies on both Brite generated network topologies and the NLANR graph. Also, well known realistic TCP models are used to capture the effects of network delays during both normal and anomalous (i.e. packet loss affected) operation mode

In this paper we address reliability issues in Web-based transactional systems. We are interested in the category of systems characterized by stateless application servers. For these systems, a framework called e-Transaction has been recently proposed, which specifies a set of desirable end-to-end reliability guarantees. Within this framework we propose an innovative distributed protocol providing those reliability guarantees in the general case of multiple, autonomous back-end databases (typical of scenarios with multiple parties involved within a same business process). Compared to existing proposals coping with the e-Transaction framework, our protocol adopts a weaker approach to failure detection, i.e. it does not rely on any assumption on the accuracy of failure detection. Hence it reveals suited for a wider class of distributed systems, including those systems where the level of asynchrony makes stronger approaches to failure detection not feasible in practice. To achieve such a target, our protocol exploits an innovative scheme for distributed transaction management (based on ad-hoc demarcation and concurrency control mechanisms), which we introduce in this paper. We also provide hints on the protocol integration with conventional systems (e.g. database systems)

Magic state manager (MASM) is recently developed software architecture for completely transparent checkpointing/recovery in support of optimistic synchronization in the high level architecture. In the original design, MASM relies on: (i) user level machine dependent modules; (ii) patches for specific versions of the LINUX kernel; and (iii) static linking of specific application libraries, all of them required for performing ad-hoc, low level memory management operations associated with optimistic synchronization requirements. In this paper, we propose a complete re-engineering of this software architecture which allows all those memory management tasks to be carried out through user level, machine independent modules, with the additional advantage of avoiding the need for static linking of specific application libraries, thus achieving portability of MASM across different UNIX systems and different computer architectures.

A content delivery network (CDN) is composed by a set of "reverse proxies" placed in proper geographical locations which provide caching and content distribution services to third party Web sites. Client requests are dispatched to one of the cache nodes that constitute the proxy by using content-aware and state-aware switching. Different distributions are generally believed to be more representative of the general traffic behavior; the classical Markovian model well captures the peculiarities of high intensity traffic during the busiest periods. The Markov chain is finite since, it admits a maximum amount of concurrently processed requests and derive the asymptotic state probabilities of the model of the CDN which can be finally used to configure the CDN with proper parameters to sustain the requested service levels, and thus to meet the SLA for each service class.

The e-transaction abstraction is a recent formalization of end-to-end reliability properties for three-tier systems. In this work, we present a protocol ensuring the e-transaction guarantees in case the back-end tier consists of a centralized database. Our proposal addresses the case of stateless application servers, and is both simple and effective since 1) it does not employ any distributed commit protocol and 2) does not require coordination among the replicas of the application server.

The notion of spatial uncertainty indicates the lack of exact knowledge about where, within the simulated space, an event actually occurs. In one of our previous works, we have shown how to exploit spatial uncertainty to reduce the synchronization cost in optimistic simulation, in terms of amount of rollback. In this paper we show how to exploit spatial uncertainty also for reducing the expected cost of simulation events during forward computation, thus achieving further reduction of the wall-clock time for the simulation model execution. The application of this proposal to optimistic simulation of a Personal Communication System (PCS) is also presented, together with experimental results supporting the claim of increased execution speed of the simulation system.

Quality-of-service (QoS) provisioning in the Internet has been a topic of active research in the last few years. However, due to both financial and technical reasons, the proposed solutions are not commonly employed in practice. As a consequence, the Internet architecture is still mainly oriented to a best effort delivery model, which does not provide any guarantee neither on the message delivery latency, nor on the probability that a service residing at some host becomes temporarily unreachable due to network congestion. We address this issue by presenting an innovative, application level protocol tailored for Web transactional applications, which attempts to reduce the impact of network congestion on the latency experienced by the end-users. The intuition underlying our proposal is to exploit the intrinsic potential of parallelism commonly exhibited by application service provider (ASP) infrastructures, where the application access point is replicated over a large number of geographically distributed edge servers. At this purpose, we allow privileged classes of users to concurrently contact multiple, replicated access points so to increase the probability to timely reach at least one of them and to promptly activate the application business logic for the interaction with a back-end database system. We complete our proposal with an efficient mechanism that prevents multiple, undesired updates on the back-end database and, at the same time, strongly limits the additional load on the ASP infrastructure due to the increased amount of requests from the privileged users.

Checkpointing and Communication Library (CCL) is recently developed software in support of optimistic parallel discrete event simulation on myrinet clusters. Beyond low latency message delivery functionalities, CCL also offers non-blocking checkpointing functionalities supported by a programmable PCI DMA engine on board of myrinet cards. CCL employs resynchronization functionality between PCI DMA activities and CPU activities to maintain the consistency of checkpointed information (i.e. to prevent the CPU from updating information that still needs to be copied through DMAing). If re-synchronization is invoked before the checkpoint operation is completed, simulation activities carried out by the CPU may be forced to wait for checkpoint completion. Since data copy through the PCI DMA is slower than what achievable with the CPU, in pathological situations a re-synchronization period may last more than a whole checkpoint operation performed by the CPU, thus nullifying the potential benefit from offloading checkpointing from the CPU. This paper tackles such an issue by presenting the design and implementation of a handoff mechanism of checkpoint operations between PCI (Peripheral Component Interconnect) DMA (direct memory access)and CPU to enhance the effectiveness of checkpointing functionalities offered by CCL. Although a checkpoint operation is initially entrusted to the PCI DMA, whenever re-synchronization forces the simulation application to wait for its completion, the checkpoint operation is dynamically switched to the CPU, namely the fastest available device, since its timely completion has become a performance critical task for the simulation application.

Checkpointing and Communication Library (CCL) is a recently developed software implementing CPU offloaded checkpointing functionalities in support of optimistic parallel simulation on myrinet clusters. Specifically, CCL implements a non-blocking execution mode of memory-to-memory data copy associated with checkpoint operations, based on data transfer capabilities provided by a programmable DMA engine on board of myrinet network cards. Re-synchronization between CPU and DMA activities must sometimes be employed for several reasons, such as maintenance of data consistency, thus adding some overhead to (otherwise CPU cost-free) non-blocking checkpoint operations. In this paper we present a cost model for non-blocking checkpointing and derive a performance effective re-synchronization semantic which we call minimum cost re-synchronization MC. With this semantic, an occurrence of re-synchronization either commits an on-going DMA based checkpoint operation (causing suspension of CPU activities) or aborts the operation (with possible increase in the expected rollback cost due to a reduced amount of committed checkpoints) on the basis of a minimum overhead expectation evaluated through the cost model. We have implemented MC within CCL, and we also report experimental results demonstrating the performance benefits from this optimized re-synchronization semantic, in terms of increase in the execution speed, for a Personal Communication System (PCS) simulation application.

Describes a nonblocking checkpointing mode in support of optimistic parallel discrete event simulation. This mode allows real concurrency in the execution of state saving and other simulation specific operations (e.g, event list update, event execution) with the aim of removing the cost of recording state information from the completion time of the parallel simulation application. We present an implementation of a C library supporting nonblocking checkpointing on a myrinet based cluster, which demonstrates the practical viability of this checkpointing mode on standard off-the-shelf hardware. By the results of an empirical study on classical parameterized synthetic benchmarks, we show that, except for the case of minimal state granularity applications, nonblocking checkpointing allows improvement of the speed of the parallel execution, as compared to commonly adopted, optimized checkpointing methods based on the classical blocking mode. A performance study for the case of a personal communication system (PCS) simulation is additionally reported to point out the benefits from nonblocking checkpointing for a real world application.

In this paper we present a communication layer for Myrinet based clusters, designed to efficiently support preemptive rollback operations in optimistic parallel simulation. Beyond standard low latency message delivery functionalities, this layer also embeds functionalities for allowing the overlying simulation application to efficiently track whether an incoming message will actually produce causality inconsistency of the currently executed simulation event upon its receipt at the application level. Exploiting these functionalities, awareness of the inconsistency precedes the message receipt at the application level, thus allowing timely event execution interruption for activating rollback procedures. Experimental results on a standard simulation benchmark show that the layer we implement allows a strong reduction of the rollback overhead which, in its turn, yields strong performance improvements (up to 33%), especially in case of large parallelism in the simulation model execution.

The benefits of Web caching can be improved by systems of cooperative cache servers that share their cached documents. The increasing number of Web cache servers over the Internet makes the scalability of the cooperation protocol a major issue to be addressed. In this paper, we propose the Two-Tier Cooperation (2TC) protocol, which is specifically designed for systems of dozens or hundreds of cache servers with no centralized control. 2TC embeds two classical cooperation approaches for distributed Web caching systems, namely informed cooperation (IC) and query cooperation (QC), that are applied within different subsets of cache servers in the system. IC is applied within subsets of close servers and lets them cooperate through mutual exchange of state information related to their cache content. QC lets more distant cache servers cooperate through query/reply messages to locate documents within the global cache. Thanks to the use of IC among close cache servers, QC can explore the cache content of several cache servers through a single query message. High scalability arises as few queries explore the cache content of many cache servers and state information is exchanged within small groups of close cache servers. We report experimental results based on real traces that compare a prototype implementation of 2TC with classical protocols of the informed and query classes. The results point out a strong reduction (up to 50%) of the amount of transferred information to manage cooperation. This overhead reduction is achieved with no performance degradation in terms of latency and cache hit rate.

Whether it is for audit or for recovery purposes, data checkpointing is an important problem of transaction systems. Actually, transactions establish dependence relations on data checkpoints taken by data object managers. So, given an arbitrary set of data checkpoints (including at least a single data checkpoint from a data manager, and at most a data checkpoint from each data manager), an important question is the following one: ‘Can these data checkpoints be members of a same consistent global checkpoint?’ This paper answers this question by providing a necessary and sufficient condition suited to transaction systems. Moreover, to show its usefulness, two non-intrusive data checkpointing protocols are designed from this condition.

Recent papers have shown that the performance of Time Warp simulators can be improved by appropriately selecting the positions of checkpoints, instead of taking them on a periodic basis. In this paper, we present a checkpointing technique in which the selection of the positions of checkpoints is based on a checkpointing-recovery cost model. Given the current state S, the model determines the convenience of recording S as a checkpoint before the next event is executed. This is done by taking into account the position of the last taken checkpoint, the granularity (i.e., the execution time) of intermediate events, and using an estimate of the probability that S will have to be restored due to rollback in the future of the execution. A synthetic benchmark in different configurations is used for evaluating and comparing this approach to classical periodic techniques. As a testing environment we used a cluster of PCs connected through a Myrinet switch coupled with a fast communication layer specifically designed to exploit the potential of this type of switch. The obtained results point out that our solution allows faster execution and, in some cases, exhibits the additional advantage that less memory is required for recording state vectors. This possibly contributes to further performance improvements when memory is a critical resource for the specific application. A performance study for the case of a cellular phone system simulation is finally reported to demonstrate the effectiveness of this solution for a real world application.

In this paper we present a parallel implementation of L evy's optimal reduction for the -calculus [11].In a similar approach to Lamping's one in [10], we base our work on a graph reduction technique known as directed virtual reduction [3] which is actually a restriction of Danos-Regnier virtual reduction [4].The parallel implementation relies on a strategy for directed virtual reduction, namely half combustion, which w e introduce in this paper.We e m bed in the implementation both a message aggregation technique, allowing a reduction of the communication overhead, and a fair policy for distributing dynamically originated load among processors.The aggregation technique is mandatory as the granularity of the computation is ne.Through this technique we o btain a linear speedup close to 80% of the ideal one on a shared memory multiprocessor.This result points out the viability of parallel implementations for optimal reduction.

Sharing cached documents among cooperative Web proxies is an effective solution to reduce Web traffic and alleviate network bottlenecks. This paper aims at comparing the performance of two cooperation protocols which follow opposite approaches: the Internet Cache Protocol (ICP) and the Full Informed Protocol (FIP). The former activates information exchange among proxies on client demand; the latter guarantees that any proxy is kept informed about the cache content of all the other cooperative proxies. The performance comparison is carried out through analytical models determining under which conditions one protocol outperforms the other. Our analysis shows that ICP is often preferable to FIP, thus pointing out that the client demand based approach is an effective solution for proxy cooperation.

This paper presents an index-based checkpointing algorithm for distributed systems with the aim of reducing the total number of checkpoints while ensuring that each checkpoint belongs to at least one consistent global checkpoint (or recovery line). The algorithm is based on an equivalence relation defined between pairs of successive checkpoints of a process which allows us, in some cases, to advance the recovery line of the computation without forcing checkpoints in other processes. The algorithm is well-suited for autonomous and heterogeneous environments, where each process does not know any private information about other processes and private information of the same type of distinct processes is not related (e.g., clock granularity, local checkpointing strategy, etc.). We also present a simulation study which compares the checkpointing-recovery overhead of this algorithm to the ones of previous solutions.

Discrete event simulation is a methodology to study the behavior of complex systems. Its drawback is that, in order to get reliable results, simulations usually have to be run over a long stretch of time. This time requirement could decrease through the usage of parallel or distributed computing systems. In this paper, we analyze the Time Warp synchronization protocol for parallel discrete event simulation and present an analytical model evaluating the upper bound on the completion time of a Time Warp simulation. In our analysis, we consider the case of a simulation model with homogeneous logical processes, where "homogeneous" means they have the same average event routine time and the same state saving cost. Then we propose a methodology to determine when it is time-convenient to use a Time Warp synchronized simulation, instead of a sequential one, for a simulation model with features matching those considered in our analysis. We give an answer to this question without the need to preliminary generate the simulation code. Examples of methodology usage are reported for the case of both a synthetic benchmark and a real world model.

A useless checkpoint corresponds to the occurrence of a checkpoint and communication pattern called Z-cycle. A recent result shows that ensuring a computation without Z-cycles is a particular application of a property, namely Virtual Precedence (VP), defined on an interval-based abstraction of a computation. We first propose a taxonomy of communication-induced checkpointing protocols based on the way they ensure the VP property. Then we derive a sufficient condition ensuring no Z-cycles in a distributed computation. This condition defines a checkpoint and communication pattern, namely suspect Z-cycle, such that if no suspect Z-cycle exists in a distributed computation then no Z-cycle exists. We present finally a communication-induced checkpointing protocol that avoids useless checkpoints by preventing on-the-fly the formation of suspect Z-cycles and discuss its performance with respect to other protocols.

The paper presents an index based checkpointing algorithm for distributed systems with the aim of reducing the total number of checkpoints while ensuring that each checkpoint belongs to at least one consistent global checkpoint (or recovery line). The algorithm is based on an equivalence relation defined between pairs of successive checkpoints of a process which allows, in some cases, to advance the recovery line of the computation without forcing check points in other processes. This protocol shows good performance, especially in autonomous environments, where each process does not have any private information about other processes.