Search

Exascale workloads are expected to incorporate data-intensive processing in close coordination with traditional physics simulations. These emerging scientific, data-analytics and machine learning applications need to access a wide variety of datastores in flat files and structured databases. Programmer productivity is greatly enhanced by mapping datastores into the application process's virtual memory space to provide a unified “in-memory” interface. Currently, memory mapping is provided by system software primarily designed for generality and reliability. However, scalability at high concurrency is a formidable challenge on exascale systems. Also, there is a need for extensibility to support new datastores potentially requiring HPC data transfer services. In this article, we present UMap , a scalable and extensible userspace service for memory-mapping datastores. Through decoupled queue management, concurrency aware adaptation, and dynamic load balancing, UMap enables application performance to scale even at high concurrency. We evaluate UMap in data-intensive applications, including sorting, graph traversal, database operations, and metagenomic analytics. Our results show that UMap as a userspace service outperforms an optimized kernel-based service across a wide range of intra-node concurrency by 1.22-1.9 ${\times}$ × . We performed two case studies to demonstrate UMap 's extensibility. First, a new datastore residing in remote memory is incorporated into UMap as an application-specific plugin. Second, we present a persistent memory allocator Metall built atop UMap for unified storage/memory.

Editor’s notes: An important role of cross-layer design is to reconcile model-implementation differences, often stemming from how the two layers are specified. This article shows how a single method and tool can support both the specification and implementation stages, resulting in better closing the “model-implementation gap.” — Samarjit Chakraborty, University of North Carolina at Chapel Hill

Funding Information: Acknowledgements. We would like to thank Stephanie Balzer, Bernardo Toninho, Nobuko Yoshida and Philip Wadler for insightful discussions. We would like also to thank the anonymous reviewers for their helpful comments and suggestions. This work is supported by NOVA LINCS (UID/CEC/04516/2019 and UIDB/04516/2020). Publisher Copyright: © 2021 Owner/Author. We develop a principled integration of shared mutable state into a proposition-as-types linear logic interpretation of a session-based concurrent programming language. While the foundation of type systems for the functional core of programming languages often builds on the proposition-as-types correspondence, automatically ensuring strong safety and liveness properties, imperative features have mostly been handled by extra-logical constructions. Our system crucially builds on the integration of nondeterminism and sharing, inspired by logical rules of differential linear logic, and ensures session fidelity, progress, confluence and normalisation, while being able to handle first-class shareable reference cells storing any persistent object. We also show how preservation and, perhaps surprisingly, progress, resiliently survive in a natural extension of our language with first-class locks. We illustrate the expressiveness of our language with examples highlighting detailed features, up to simple shareable concurrent ADTs. publishersversion published

In the era of Internet and big data, contemporary workflows become increasingly large in scale and complex in structure, introducing greater challenges for workflow modeling. Workflows are not with maximized concurrency and block-structuredness in terms of control flow, though languages supporting block-structuredness (e.g., BPEL) are employed. Existing workflow refactoring approaches mostly focus on maximizing concurrency according to dependences between activities, but do not consider the block-structuredness of the refactored workflow. It is easier to comprehend and analyze a workflow that is block-structured and to transform it into BPEL-like processes. In this paper, we aim at maximizing both concurrency and block-structuredness. Nevertheless, not all workflows can be refactored with a block-structured representation, and it is intractable to make sure that the refactored workflows are as block-structured as possible. We first define a well-formed dependence pattern of activities. The control flow among the activities in this pattern can be represented in block-structured forms with maximized concurrency. Then, we propose a greedy heuristics-based graph reduction approach to recursively find such patterns. In this way, the resulting workflow is with maximized concurrency and its block-structuredness approximates optimality. We show the effectiveness and efficiency of our approach with real-world scientific workflows.

[EN] Reversibility enables a program to be executed both forwards and backwards. This ability allows programmers to backtrack the execution to a previous state. This is essential if the computation is not deterministic because re-running the program forwards may not lead to that state of interest. Reversibility of sequential programs has been well studied and a strong theoretical basis exists. Contrarily, reversibility of concurrent programs is still very young, especially in the practical side. For instance, in the particular case of the Communicating Sequential Processes (CSP) language, reversibility is practically missing. In this article, we present a new technique, including its formal definition and its implementation, to reverse CSP computations. Most of the ideas presented can be directly applied to other concurrent specification languages such as Promela or CCS, but we center the discussion and the implementation on CSP. The technique proposes different forms of reversibility, including strict reversibility and causal-consistent reversibility. On the practical side, we provide an implementation of a system to reverse CSP computations that is able to highlight the source code that is being executed in each forwards/backwards computation step, and that has been optimized to be scalable to real systems., A preliminary version of this work was presented at the 12th Conference on Reversible Computation [31]. The authors would like to thank the anonymous reviewers for their useful comments and constructive feedback that helped them to improve this work. This work was supported in part by the EU (FEDER) and the Spanish MCI/AEI under Grant TIN2016-76843-C4-1-R and Grant PID2019-104735RB-C41, in part by the Generalitat Valenciana under Grant Prometeo/2019/098 (DeepTrust), in part by JSPS KAKENHI under Grant JP17H01722, and in part by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA 952215.

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity and authenticity of query results returned by potentially compromised providers. Prior work provides QA assurances for a limited class of queries by deploying several software-based cryptographic constructs. The constructs are often designed assuming read-only or infrequently updated databases. For dynamic datasets, the data owner is required to perform all updates on behalf of clients. Hence, for concurrent updates by multiple clients, such as for OLTP workloads, existing QA solutions are inefficient. We present ConcurDB, a concurrent QA scheme that enables simultaneous updates by multiple clients. To realize concurrent QA, we have designed several new mechanisms. First, we identify and use an important relationship between QA and memory checking to decouple query execution and verification. We allow clients to execute transactions concurrently and perform verifications in parallel using an offline memory checking based protocol. Then, to extend QA to a multi-client scenario, we design new protocols that enable clients to securely exchange a small set of authentication data even when using the untrusted provider as a communication hub. Finally, we overcome provider-side replay attacks. Using ConcurDB, we provide and evaluate concurrent QA for the full TPC-C benchmark. For updates, ConcurDB shows a 4x performance increase over existing solutions.

Go provides a new concurrency mechanism based on message-passing, which brings a series of new concurrency bugs. The existing tools are highly dependent on model-checking methods in which they take the source program as the input of model-checking tools to detect the potential concurrent bugs. However, these methods can only qualitatively obtain the concurrency of the program but not obtain the exact number of concurrency bugs in the program. Meanwhile, these approaches are not sensitive to dead codes, which are prone to false negatives. Furthermore, few works have been done on detecting WaitGroup-related bugs in Go concurrent programming, which may cause deadlock. To this end, this paper proposes a novel approach GoDetector to detect concurrent bugs. GoDetector uses a detecting algorithm and a pushdown automaton to verify the channel-related concurrent bugs and WaitGroup-related concurrent bugs separately. To support the evaluation of the tool, 30 benchmarks are collected from the existing tools. GoDetector reports 2 channel safety errors, 29 deadlocks, and 11 WaitGroup-related errors. Compared with the existing tool Godel, GoDetector has the capacity to report more concurrency bugs and fewer false positives. GoDetector also offers additional support for the detection of WaitGroup variables. The experimental results indicate that GoDetector is more efficient at detecting the concurrency in regards to accuracy and diversity.

Dynamic dataflow scheduling enables effective exploitation of concurrency while making parallel programming easier. To this end, analyzing the inherent degree of concurrency available in dataflow graphs is an important task, since it may aid compilers or programmers to assess the potential performance a program can achieve via parallel execution. However, traditional concurrency analysis techniques only work for DAGs (directed acyclic graphs), hence the need for new techniques that contemplate graphs with cycles. In this paper we present techniques to perform concurrency analysis on generic dynamic dataflow graphs, even in the presence of cycles. In a dataflow graph, nodes represent instructions and edges describe dependencies. The novelty of our approach is that we allow concurrency between different iterations of the loops. Consequently, a set of concurrent nodes may contain instructions from different loops that can be proven independent. In this work, we provide a set of theoretical tools for obtaining bounds and illustrate implementation of parallel dataflow runtime on a set of representative graphs for important classes of benchmarks to compare measured performance against derived bounds.

When mapping C programs to hardware, high-level synthesis (HLS) tools reorder independent instructions, aiming to obtain a schedule that requires as few clock cycles as possible. However, when synthesizing multithreaded C programs, reordering opportunities are limited by the presence of atomic operations (“atomics”), the fundamental concurrency primitives in C. Existing HLS tools analyze and schedule each thread in isolation. In this article, we argue that thread-local analysis is conservative, especially since HLS compilers have access to the entire program. Hence, we propose a global analysis that exploits information about memory accesses by all threads when scheduling each thread. Implemented in the LegUp HLS tool, our analysis is sensitive to sequentially consistent (SC) and weak atomics and supports loop pipelining. Since the semantics of C atomics is complicated, we formally verify that our analysis correctly implements the C memory model using the Alloy model checker. Compared with thread-local analysis, our global analysis achieves a $2.3\times $ average speedup on a set of lock-free data structures and data-flow patterns. We also apply our analysis to a larger application: a lock-free, streamed, and load-balanced implementation of Google’s PageRank, where we see a $1.3\times $ average speedup compared with the thread-local analysis.

Refactoring has become an effective approach to convert sequential programs into concurrent programs. Many refactoring algorithms and tools are proposed to assist developers in writing high-performance concurrent programs. Although researchers actively conduct surveys on refactoring, we are not aware of any survey that summarizes, categorizes and discusses concurrency-oriented refactoring. To this end, this paper presents a survey that investigates how refactoring assists with concurrent programming. To the best of our knowledge, this paper is the first survey that summarizes the state-of-the-art, concurrency-oriented refactoring. First, we design six research questions addressing the concurrent structure, programming language, performance improvement and consistency evaluation. Second, we answer these questions by examining the related papers and then present the results to show how refactoring provides support for concurrent programming after a decade of development, such as transforming the concurrent structures, supporting parallel language, and improving performance. Finally, we summarize the related works and present the future trends.

There are many paradigms available to address the unique and complex problems introduced with parallel programming. These complexities have implications for computer science education as ubiquitous multi-core computers drive the need for programmers to understand parallelism. One major obstacle to student learning of parallel programming is that there is very little human factors evidence comparing the different techniques to one another, so there is no clear direction on which techniques should be taught and how. We performed a randomized controlled trial using 88 university-level computer science student participants performing three identical tasks to examine the question of whether or not there are measurable differences in programming performance between two paradigms for concurrent programming: threads compared to process-oriented programming based on Communicating Sequential Processes. We measured both time on task and programming accuracy using an automated token accuracy map (TAM) technique. Our results showed trade-offs between the paradigms using both metrics and the TAMs provided further insight about specific areas of difficulty in comprehension.

Comparison of concurrent programming languages and correctness of program transformations in concurrency are the focus of this research. As criterion we use contextual semantics adapted to concurrency, where may -- as well as should -- convergence are observed. We investigate the relation between the synchronous pi-calculus and a core language of Concurrent Haskell (CH). The contextual semantics is on the one hand forgiving with respect to the details of the operational semantics, and on the other hand implies strong requirements for the interplay between the processes after translation. Our result is that CH embraces the synchronous pi-calculus. Our main task is to find and prove correctness of encodings of pi-calculus channels by CH's concurrency primitives, which are MVars. They behave like (blocking) 1-place buffers modelling the shared-memory. The first developed translation uses an extra private MVar for every communication.We also automatically generate and check potentially correct translations that reuse the MVars where one MVar contains the message and two additional MVars for synchronization are used to model the synchronized communication of a single channel in the pi-calculus.Our automated experimental results lead to the conjecture that one additional MVar is insufficient., In Proceedings EXPRESS/SOS 2020, arXiv:2008.12414

System analysis is a crucial activity throughout component-based architecture design. It enables detecting and correcting errors in the early stage of the system development life cycle. In this article, we consider system analysis in UML2.0 component-based architectural design phase. This is done by proposing a model-driven engineering (MDE) tool called UML2Ada. It enables the systematic translation of a UML2.0 atomic and composite component into Ada concurrent language. This, in turn, supports the validation of the source description using an Ada dynamic analysis tools such as GNATprove and ObjectAda. In addition, by using an Ada static analysis tool such as FLAVERS or INCA, the proposed tool enables the detection of the potential behavioral concurrency properties of the Ada concurrent program.

As the performance gap between processors and storage devices keeps increasing, I/O performance becomes a critical bottleneck of modern high-performance computing systems. In this paper, we propose a pattern-directed and layout-aware data replication design, named PDLA, to improve the performance of parallel I/O systems. PDLA includes an HDD-based scheme H-PDLA and an SSD-based scheme S-PDLA . For applications with relatively low I/O concurrency, H-PDLA identifies access patterns of applications and makes a reorganized data replica for each access pattern on HDD-based servers with an optimized data layout. Moreover, to accommodate applications with high I/O concurrency, S-PDLA replicates critical access patterns that can bring performance benefits on SSD-based servers or on HDD-based and SSD-based servers. We have implemented the proposed replication scheme under MPICH2 library on top of OrangeFS file system. Experimental results show that H-PDLA can significantly improve the original parallel I/O system performance and demonstrate the advantages of S-PDLA over H-PDLA.

A 50-year history of concurrency.

Much recent research has been devoted to modeling effects within type theory. Building on this work, we observe that effectful type theories can provide a foundation on which to build semantics for more complex programming constructs and program logics, extending the reasoning principles that apply within the host effectful type theory itself. Concretely, our main contribution is a semantics for concurrent separation logic (CSL) within the F* proof assistant in a manner that enables dependently typed, effectful F* programs to make use of concurrency and to be specified and verified using a full-featured, extensible CSL. In contrast to prior approaches, we directly derive the partial-correctness Hoare rules for CSL from the denotation of computations in the effectful semantics of non-deterministically interleaved atomic actions. Demonstrating the flexibility of our semantics, we build generic, verified libraries that support various concurrency constructs, ranging from dynamically allocated, storable spin locks, to protocol-indexed channels. We conclude that our effectful semantics provides a simple yet expressive basis on which to layer domain-specific languages and logics for verified, concurrent programming., ICFP 2020 camera-ready version

Positioning plays an important role in many IoT applications. Ultra-wideband (UWB)-based positioning is an alternative to GPS in indoor environments due to its multipath resilience and its accuracy and precision. In the presence of a large number of targets to localize, conventional UWB localization fails to provide a practical location update rate. UWB concurrency in conjunction with self-localization has been used in both time-based and phase-based localization making the targets to localize (tags), a relatively passive device with the sole role of receiving wireless packets and calculating its own location. More recently, phase-based concurrent angle estimation also offloaded the hardware complexity and cost to the anchors instead of the tags. In this work, our anchor-oriented approach combines inter-anchor and intra-anchor concurrency for phase-based localization but also allows time-based localization. Our experimental evaluation on a testbed consisting of Decawave platform shows that our technique is not only practical but also performant.

In order to understand the relative expressive power of larger concurrent programming languages, we analyze translations of small process calculi which model the communication and synchronization of concurrent processes. The source language SYNCSIMPLE is a minimalistic model for message passing concurrency while the target language LOCKSIMPLE is a minimalistic model for shared memory concurrency. The former is a calculus with synchronous communication of processes, while the latter has synchronizing mutable locations - called locks - that behave similarly to binary semaphores. The criteria for correctness of translations is that they preserve and reflect may-termination and must-termination of the processes. We show that there is no correct compositional translation from SYNCSIMPLE to LOCKSIMPLE that uses one or two locks, independent from the initialisation of the locks. We also show that there is a correct translation that uses three locks. Also variants of the locks are taken into account with different blocking behavior., In Proceedings EXPRESS/SOS 2021, arXiv:2108.09624. Author version at 2107.14651

Smart contracts present a uniform approach for deploying distributed computation and have become a popular means to develop security critical applications. A major barrier to adoption for many applications is the public nature of existingsystems, such as Ethereum. Several systems satisfying various definitions of privacy and requiring various trust assumptions have been proposed; however, none achieved the universality and uniformity that Ethereum achieved for non-private contracts: One unified method to construct most contracts. We provide a unified security model for private smart contracts which is based on the Universal Composition (UC) model and propose a novel core protocol, KACHINA, for deploying privacy-preserving smart contracts, which encompasses previous systems. We demonstrate the KACHINA method of smart contract development, using it to construct a contract that implements privacy-preserving payments, along the lines of Zerocash, which is provably secure in the UC setting and facilitates concurrency.

The paper deals with a problem of a work scheduling of a fleet of cooperating forklifts. Their cooperation means that they can perform a given interchangeability. Unfortunately, it causes an inevitable concurrency issue, which has to be resolved in an optimal way. Since the vehicles are autonomous, there are no human operators whose experience could be a selection criteria in solving the above problem. Thus, the paper proposes a novel health-aware-based cost function which takes into account predictions concerning current operational ability of vehicle batteries. To obtain these predictions a Takagi-Sugeno approach is proposed and validated using Li-Ion battery data set provided by NASA PCoE. Finally, it is incorporated into the health-aware fault tolerant control scheme, which can tolerate inevitable delays present in such a transportation system.

The paper considers the process of compilers designing and highlight parallelism in algorithmic structures. The advantages of existing solutions in the hardware and software areas are highlighted and a new approach for creating a software and hardware compiler is designed. The requirements for our language and the peculiarities of the functioning of each component of the compiler were clearly defined. The basis of the alphabet consists of Latin upper and lower case characters, numbers and delimiters. A description of the lexical analyzer, which highlights tokens and keywords in the text of the input program is provided. Syntactic rules of language (structure of constructions) in the form of diagrams of the Bekus-Naur form and semantic requirements concerning identifiers, length of names of identifiers and labels, arithmetic operations and input/output ports are described as well. The processor compiler with natural parallel execution of instructions was developed. Performance testing and comparative analysis of the efficiency of the developed compiler has shown the advantages of the created solution.

This paper aims to study how existing trace mining methods work, and their strengths and weaknesses in the context of communication-centric system-on-chip (SoC) traces. SoC traces are unique because of the inherent concurrency, which makes SoC trace mining very challenging. We select seven well-known trace mining methods both from the hardware and software domains. We perform comprehensive experiments, and offer our understanding of the pros and cons of each mining method. We evaluate the interestingness of the mined outcomes for each tool on a benchmark trace set. This trace benchmark includes sophisticated communication traces generated synthetically and realistically. We provide a comprehensive analysis of the performance of the tools, and release the benchmark trace dataset to facilitate future works in SoC trace mining.

Serverless computing functions typically execute in the cloud. However, the high latency of accessing the cloud may require running them on edge servers, which have limited computing power and memory availability. This paper proposes a joint resource allocation and request dispatch scheme to execute serverless computing functions over edge and cloud collaboratively. This new scheme explicitly considers how to allocate server memory and operation budget for concurrent serverless computing requests considering the cold-start latency in design. The proposed scheme has been evaluated through extensive simulations. Its effectiveness has been proved by comparison with the upper-bound results.

A number of approaches have been developed for analysing information flow in concurrent programs in a compositional manner, i.e., in terms of one thread at a time. Early approaches modelled the behaviour of a given thread’s environment using simple read and write permissions on variables, or by associating specific behaviour with whether or not locks are held. Recent approaches allow more general representations of environmental behaviour, increasing applicability. This, however, comes at a cost. These approaches analyse the code in a forwards direction, from the start of the program to the end, constructing the program’s entire state after each instruction. This process needs to take into account the environmental influence on all shared variables of the program. When environmental influence is modelled in a general way, this leads to increased complexity, hindering automation of the analysis. In this paper, we present a compositional information flow analysis for concurrent systems which is the first to support a general representation of environmental behaviour and be automated within a theorem prover. Our approach analyses the code in a backwards direction, from the end of the program to the start. Rather than constructing the entire state at each instruction, it generates only the security-related proof obligations. These are, in general, much simpler, referring to only a fraction of the program’s shared variables and thus reducing the complexity introduced by environmental behaviour. For increased applicability, our approach analyses value-dependent information flow, where the security classification of a variable may depend on the current state. The resulting logic has been proved sound within the theorem prover Isabelle/HOL.

Transactional memory (TM) aims at simplifying concurrent programming via the familiar abstraction of atomic transactions. Recently, Intel and IBM have integrated hardware based TM (HTM) implementations in commodity processors, paving the way for the mainstream adoption of the TM paradigm. Yet, existing HTM implementations suffer from a crucial limitation, which hampers the adoption of HTM as a general technique for regulating concurrent access to shared memory: the inability to execute transactions whose working sets exceed the capacity of CPU caches. In this article we propose P8TM, a novel approach that mitigates this limitation on IBM’s POWER8 architecture by leveraging a key combination of hardware and software techniques to support different execution paths. P8TM also relies on self-tuning mechanisms aimed at dynamically switching between different execution modes to best adapt to the workload characteristics. In-depth evaluation with several benchmarks indicates that P8TM can achieve striking performance gains in workloads that stress the capacity limitations of HTM, while achieving performance on par with HTM even in unfavourable workloads.

The Internet of Things (IoT) is envisioned as a distributed network formed by many end devices, e.g., the motes of wireless sensor network (WSN). These important IoT end devices enable ubiquitous sensing of environments and provide reliable services for mission-critical applications. However, programs running on WSN devices are typically interrupt-driven and prone to interrupt-induced concurrency bugs, which are primarily caused by erroneous interleavings among interrupt procedure instances (IPIs) (namely, executions of interrupt processing logic). In this paper, we use a set of dynamic bug patterns to characterize the concurrency bugs due to buggy access-interleavings among IPIs to shared resources, including shared memory locations and shared communication channels. By matching the above bug patterns, a dynamic analysis approach called disclosing and locating concurrency bugs of interrupt-driven IoT programs based on dynamic bug patterns (Daemon) is proposed to automatically detect and locate concurrency bugs in WSN programs. A GUI tool of Daemon is developed. As the empirical studies exhibit, the tool can discover concurrency bugs effectively and locate the buggy source lines visually.

Concurrency bugs widely exist and severely threaten system availability. Techniques that help recover from concurrency-bug failures during production runs are highly desired. This paper proposes BugTM, an approach that applies transactional memory techniques for concurrency-bug recovery in production runs. Requiring no knowledge about where are concurrency bugs, BugTM uses static analysis and code transformation to enable BugTM-transformed software to recover from a concurrency-bug failure by rolling back and re-executing the recent history of a failure thread. BugTM is instantiated as three schemes that have different trade-offs in performance and recovery capability: BugTM$_H$H uses existing hardware transactional memory (HTM) support, BugTM$_S$S leverages software transactional memory techniques, and BugTM$_{\mathrm{HS}}$ HS is a software-hardware hybrid design. BugTM greatly improves the recovery capability of state-of-the-art techniques with low run-time overhead and no changes to OS or hardware, while guarantees not to introduce new bugs.

FreeST is an experimental concurrent programming language. Based on a core linear functional programming language, it features primitives to fork new threads, and for channel creation and communication. A powerful type system of context-free session types governs the interaction on channels. The compiler builds on a novel algorithm for deciding type equivalence of context-free session types. This abstract provides a gentle introduction to the language and discusses the validation process and runtime system., Comment: In Proceedings PLACES 2019, arXiv:1904.00396

Abstrect Many optimum designs of tribological components are highly time-constrained before final productions. It is well-known that the process of a complex simulated design can be considerably accelerated by using some form of parallel computing. Also, for many tribological models additional assumptions can be relaxed with stricter design constrains, if the execution can be speeded up. In this study, the concurrent computing for tribological design is proposed, which is to perform parallel computing using the multitasking capability of today's operating system. In the concurrent computing a master program, which manages the process of the optimization, is used to launch a number of standalone slave programs (air bearing models) in a quick succession. And the operating system (MS-Windows) of the computer manages the parallel execution of the slave programs. Other than the standard programming language (Fortran 95) this approach uses none of the general parallel programming paradigms or directives, such as message passing interface, OpenMP, or coding using graphics processing units. In this study, the algorithm for the multiobjective optimization is group inching fortification method and the concurrent computing is executed in the algorithm-level. High parallel computing speedups are obtained in the simulated bearing designs. The approach can also be applied in using commercial general-purpose packages for modelling and self-coded methods for optimum design of tribological components or systems.

This paper is a contribution to exploring and analyzing space-improvements in concurrent programming languages, in particular in the functional process-calculus CHF. Space-improvements are defined as a generalization of the corresponding notion in deterministic pure functional languages. The main part of the paper is the O(n*log n) algorithm SpOptN for offline space optimization of several parallel independent processes. Applications of this algorithm are: (i) affirmation of space improving transformations for particular classes of program transformations; (ii) support of an interpreter-based method for refuting space-improvements; and (iii) as a stand-alone offline-optimizer for space (or similar resources) of parallel processes., In Proceedings WPTE 2018, arXiv:1902.07818

More than 75% of recent Java projects include some form of concurrent programming. Due to complex interactions between multi-threads, concurrent programs are often harder to understand and test than single threaded programs. To facilitate understanding and testing of concurrent programs, we developed a new profiling method called TCP (Thread Control Profiling). Outputs of TCP presents frequencies of control dependence, which includes thread creation, thread synchronization, interruption, and so on, of the executed thread. TCP first performs static analysis of detailed concurrency syntax and semantics of Java to construct the profiling graph model TCDG (Thread Control Dependence Graph). TCDG is then used for instrumentation and for generating profiles. We have evaluated TCP using a case study and a few experiments. The case study shows that TCP method can effectively prioritize test cases for testing concurrent programs. One experiment shows that outputs from TCP facilitate developers’ understanding of concurrent code. Other experiments evaluate various possible overheads introduced by the TCP method. Results show that TCP can provide rich and useful information with reasonable costs.

We develop a new intermediate weak memory model, IMM, as a way of modularizing the proofs of correctness of compilation from concurrent programming languages with weak memory consistency semantics to mainstream multi-core architectures, such as POWER and ARM. We use IMM to prove the correctness of compilation from the promising semantics of Kang et al. to POWER (thereby correcting and improving their result) and ARMv7, as well as to the recently revised ARMv8 model. Our results are mechanized in Coq, and to the best of our knowledge, these are the first machine-verified compilation correctness results for models that are weaker than x86-TSO.

With the development of virtualization technologies, containers are widely used to provide a light-weight isolated runtime environment. Compared with virtual machines, containers can achieve high-resource utilization and provide a more convenient way of sharing, but there are significant security challenges due to potential resource contention among services. When the regular services that share the storage system with the key services are over-used, a lot of resources may be preempted, which breakdowns the whole system and delays other services. This paper addressed the performance isolation in fierce resource competition situations, that is, when different services (latency-sensitive services and throughput-first services) are deployed on a host machine using container technology. We proposed PINE, a performance isolation optimization solution in container environments, which can adaptively allocate the storage resource for each service according to their performance behaviors through dynamical resource management and I/O concurrency configuration. The experimental results show that PINE can effectively optimize the performance of the running services and achieve the optimal result in a relatively short time.

Process models are used to describe or verify the correctness of business processes before their implementation by enterprise information systems. With the development of data mining technologies, a lot of event logs generated from such systems can be used to check conformance of business processes and process models. For models containing a choice with concurrency structure, although the model repaired by the existing method can replay the event log, it is quite different from the business process. Therefore, we propose a model repair method based on logic Petri net. First, we give an algorithm to find the position of the deviation. Then, we add directed arcs from a place to a transition or from a transition to a place via logic Petri nets. Finally, we repair the model by adding logic transitions with logic functions. The repaired model can efficiently enhance conformance dimensions, such as simplicity and precision. The correctness and effectiveness of the method are verified by experimental results.

Field Programmable Gate Arrays (FPGAs) are emerging as suitable platforms for implementing embedded control systems. FPGAs offer advantages such as high performance and concurrent computing which makes them attractive in many embedded applications. As reconfigurable devices, they can be used to build the hardware and software components of an embedded system on a single chip. Traditional FPGA design flows and tools, requiring the use of Hardware Description Languages (HDLs), are in a different domain than standard control system design tools such as MATLAB/Simulink. This paper illustrates development of FPGA-based controllers by utilizing popular tools such as MATLAB/Simulink available for the design and development of control systems. The capability of DSP Builder is extended by developing a custom library of control system building blocks that facilitates rapid development of FPGA-based controllers in the familiar Matlab/Simulink environment. As a case study, this paper presents how the tools can be utilized to develop a FPGA-based controller for a laboratory scale air levitation system.

Kotlin Coroutines are generalised subroutines that can suspend and resume execution freely. They exhibit lower overhead than Java Virtual Machine (JVM) Threads, making them suitable for asynchronous applications in resource-constrained environments. This paper analyses the performance of Kotlin Coroutines framework on Android and measures its benefits over JVM Threads-based concurrency framework RxJava using a novel benchmarking methodology for reliable and reproducible results. It also highlights the performance improvements enabled by Kotlin Coroutines in real-world projects by comparing two Model-View-Intent (MVI) architecture libraries MvRx (by Airbnb), and Vector (by author Chauhan, K) based on RxJava and Coroutines, respectively.

Serverless computing has emerged as a compelling new paradigm of cloud computing models in recent years. It promises the user services at large scale and low cost while eliminating the need for infrastructure management. On cloud provider side, flexible resource management is required to meet fluctuating demand. It can be enabled through automated provisioning and deprovisioning of resources. A common approach among both commercial and open source serverless computing platforms is workload-based auto-scaling, where a designated algorithm scales instances according to the number of incoming requests. In the recently evolving serverless framework Knative a request-based policy is proposed, where the algorithm scales resources by a configured maximum number of requests that can be processed in parallel per instance, the so-called concurrency. As we show in a baseline experiment, this predefined concurrency level can strongly influence the performance of a serverless application. However, identifying the concurrency configuration that yields the highest possible quality of service is a challenging task due to various factors, e.g. varying workload and complex infrastructure characteristics, influencing throughput and latency. While there has been considerable research into intelligent techniques for optimizing auto-scaling for virtual machine provisioning, this topic has not yet been discussed in the area of serverless computing. For this reason, we investigate the applicability of a reinforcement learning approach, which has been proven on dynamic virtual machine provisioning, to request-based auto-scaling in a serverless framework. Our results show that within a limited number of iterations our proposed model learns an effective scaling policy per workload, improving the performance compared to the default auto-scaling configuration., 8 pages, 7 figures

Function-as-a-Service (FaaS) is a compelling technology that allows users to run functions in an event-driven way without concerns about server management. Container-based virtualization enables functions to run in a lightweight and isolated run-time environment, but frequent function executions accompanied with container initialization (cold starts) make the platform busy and unresponsive. For performance sake, warm starts, which is to execute functions on already initialized containers, are encouraged, and thus FaaS platforms make efforts to schedule functions to warm containers.From our experience operating an on-premise FaaS platform, we found that the existing scheduler showed poor performance and unstable behavior against multi-tenant and highly concurrent workloads. This paper proposes a novel FaaS scheduling algorithm, named FPCSch, that schedules Function-Pulling-Containers instead of scheduling functions to containers. As FPCSch lets containers continuously pull functions of the same type, cold starts decrease dramatically. Our evaluations show that Apache OpenWhisk equipped with FPCSch has many desirable features for FaaS platforms; (1) quite stable throughput against the multi-tenant workloads mixed by the increasing numbers of function types, (2) growing throughput for increasing concurrency, (3) uniformly load-balancing resource-intensive workloads, and (4) nearly proportional performance for scale-out.

Realizing flow security in a concurrent environment is extremely challenging, primarily due to non-deterministic nature of execution. The difficulty is further exacerbated from a security angle if sequential threads disclose control locations through publicly observable statements like print, sleep, delay, etc. Such observations lead to internal and external timing attacks. Inspired by previous works that use classical Hoare style proof systems for establishing correctness of distributed (real-time) programs, in this paper, we describe a method for finding information leaks in concurrent programs through the introduction of leaky assertions at observable program points. Specifying leaky assertions akin to classic assertions, we demonstrate how information leaks can be detected in a concurrent context. To our knowledge, this is the first such work that enables integration of different notions of non-interference used in functional and security context. While the approach is sound and relatively complete in the classic sense, it enables the use of algorithmic techniques that enable programmers to come up with leaky assertions that enable checking for information leaks in sensitive applications., 5 pages, 2 figures; accepted paper for the 43rd International Conference on Software Engineering (ICSE 2021), Track: New Ideas and Emerging Results (NIER)

It is an ongoing challenge to efficiently use parallelism with today’s multi- and many-core processors. Scalability becomes more crucial than ever with the rapidly growing number of processing elements in many-core systems that operate in data centres and embedded domains. Guaranteeing scalability is often ensured by using fully-strict fork/join concurrency, which is the prevalent approach used by concurrency platforms like Cilk. The runtime systems employed by those platforms typically resort to lock-based synchronisation due to the complex interactions of data structures within the runtime. However, locking limits scalability severely. With the availability of commercial off-the-shelf systems with hundreds of logical cores, this is becoming a problem for an increasing number of systems.This paper presents Nowa, a novel wait-free approach to arbitrate the plentiful concurrent strands managed by a concurrency platform’s runtime system. The wait-free approach is enabled by exploiting inherent properties of fully-strict fork/join concurrency, and hence is potentially applicable for every continuation-stealing runtime system of a concurrency platform. We have implemented Nowa and compared it with existing runtime systems, including Cilk Plus, and Threading Building Blocks (TBB), which employ a lock-based approach. Our evaluation results show that the wait-free implementation increases the performance up to 1.64× compared to lock-based ones, on a system with 256 hardware threads. The performance increased by 1.17× on average, while no but one benchmark exhibited performance regression. Compared against OpenMP tasks using Clang’s libomp, Nowa outperforms OpenMP by 8.68× on average.

Microservices Architecture is a popular pattern used for building complex IT systems in an incremental, sustainable, and scalable fashion. However, compared with traditional monolithic solution architectures, it introduces a higher degree of concurrency which might result in subtle bugs arising, such as race conditions, deadlocks, and lack of data consistency. I shall illustrate this using a worked example of an automated insurance claims payment service which exhibits a bug whereby a particular claim might be settled twice. I shall use the CSP formal modelling language and the FDR refinement checker to prove some results about this bug and how to fix it.

Transactions are a simple, yet powerful, abstraction that aims at masking programmers from the complexity of having to ensure correct and efficient synchronization of concurrent code. Originally introduced in the domain of database systems, transactions have recently garnered significant interest in the broader domain of concurrent programming, via the Transactional Memory (TM) paradigm. Nowadays, hardware supports for TM are provided in commodity CPUs (e.g., by Intel and IBM) and, at the software level, TM has been integrated in mainstream programming languages, such as C/C++ and Java. In this talk I will present the novel challenges and research opportunities that arise in the area of TM due to the emergence of two recent hardware trends, namely Non-Volatile Memory (NVM) and heterogeneous computing architectures. On the front of NVM, I will focus on the problem of how to allow the execution of transactions over NVM using unmodified commodity hardware TM (HTM) implementations. However, the reliance of commodity HTM implementations on CPU caches raises a crucial problem when applications access data stored in NVM from within a HTM transaction. Since CPU caches are volatile in today's systems, HTM implementations do not guarantee that the effects of a hardware transaction are atomically transposed to PM when the transaction commits --- although such effects are immediately visible to subsequent transactions. In this talk, I will overview somoe recent approaches to tackle this problem and present experimental results highlighting the existence of several bottlenecks that hinder the scalability of existing solutions. Next, I will show how these limitations can be addressed by presenting SPHT. SPHT introduces a novel commit logic that considerably mitigates the scalability bottlenecks of previous alternatives, providing up to 2.6x/2.2x speedups at 64 threads in, resp., STAMP/TPC-C. Moreover, SPHT introduces a novel approach to log replay that employs cross-transaction log linking and a NUMA-aware parallel background replayer. In large persistent heaps, the proposed approach achieves gains of 2.8x. On the front of heterogeneous computing, I will present the abstraction of Heterogeneous Transactional Memory (HeTM). HeTM provides programmers with the illusion of a single memory region, shared among the CPUs and the (discrete) GPU(s) of a heterogeneous system, with support for atomic transactions. Besides introducing the abstract semantics and programming model of HeTM, I will present the design and evaluation of a concrete implementation of the proposed abstraction, which we named Speculative HeTM (SHeTM). SHeTM makes use of a novel design that leverages speculative techniques that aim at hiding the large communication latency between CPUs and discrete GPUs and at minimizing inter-device synchronization overhead.

Go is a statically typed programming language designed for efficient and reliable concurrent programming. For this purpose, Go provides lightweight goroutines and recommends passing messages using channels as a less error-prone means of thread communication. Go has become increasingly popular in recent years and has been adopted to build many important infrastructure software systems. However, a recent empirical study shows that concurrency bugs, especially those due to misuse of channels, exist widely in Go. These bugs severely hurt the reliability of Go concurrent systems. To fight Go concurrency bugs caused by misuse of channels, this paper proposes a static concurrency bug detection system, GCatch, and an automated concurrency bug fixing system, GFix. After disentangling an input Go program, GCatch models the complex channel operations in Go using a novel constraint system and applies a constraint solver to identify blocking bugs. GFix automatically patches blocking bugs detected by GCatch using Go’s channel-related language features. We apply GCatch and GFix to 21 popular Go applications, including Docker, Kubernetes, and gRPC. In total, GCatch finds 149 previously unknown blocking bugs due to misuse of channels and GFix successfully fixes 124 of them. We have reported all detected bugs and generated patches to developers. So far, developers have fixed 125 blocking misuse-of-channel bugs based on our reporting. Among them, 87 bugs are fixed by applying GFix’s patches directly.

Almost all applications stop scaling at some point; those that don't are seldom performant when considering time to solution on anything but aspirational/unicorn resources. Recognizing these tradeoffs as well as greater user functionality in a near-term exascale computing era, we present libEnsemble, a library aimed at particular scalability- and capability-stretching uses. libEnsemble enables running concurrent instances of an application in dynamically allocated ensembles through an extensible Python library. We highlight the structure, execution, and capabilities of the library on leading pre-exascale environments as well as advanced capabilities for exascale environments and beyond.

BPEL (Business Process Execution Language) is a classical Web service composition process language. In this situation, it is also known as WS-BPEL or BPEL4WS. However, BPEL is lack of formal analysis and verification methods. In order to solve this problem, a serial of rules to convert the BPEL to Petri net model are presented in this study, which enable the more intuitive and rigorous mathematical description of service composition process, and also facilitate the analysis and verification to the composite services.

Multi-threaded libraries, including the ones advertised as thread-safe, may contain concurrency bugs,and worse, may not include relevant test cases that can drive the program execution towards bug-prone interleavings. Also, the effectiveness of dynamic verification, a prominent concurrency bug detection technique, depends critically on the availability of relevant test cases. Generating such test cases automatically to assist dynamic verification is, therefore, a significant problem. Among hard-to-detect concurrency bugs in multi-threaded Java libraries are communication deadlocks, which occur due to the incorrect usage of wait() and notify() communication primitives. In this work, we present a novel technique to systematically synthesize multi-threaded test cases to expose communication deadlocks. We model these deadlocks as global constraints over the events of two sequential program traces of the library APIs. The task of predicting the relevance of combining two sequential program traces is delegated to an SMT solver. We implement our technique in a prototype tool named Revelio, and evaluate it on fifteen classes of popular multi-threaded Java libraries. We find that Reveliois able to synthesize precise tests exposing communication deadlocks, which the state-of-the-art tools cannot.

Due to the variability of IT applications, the back-end databases usually run the mixed OLTP workload, which comprises a variety of transactions. Some of these transactions are high-conflict and others are low-conflict. Furthermore, high-conflict transactions may contend on different groups of data stored in the database. Without precise admission control, too many transactions with conflict on the same group of records are simultaneously executed by the OLTP engine, and this will lead to the well-known problem of data-contention thrashing. Under mixed OLTP workloads, conflicting transactions would be blocked for a long time or rolled back finally, and other transactions have not enough opportunity to be processed.To achieve the optimal performance for each kind of transaction, we design a discriminative admission control mechanism for shared-everything database, referred to as DAC. DAC can quickly identify and classify high-conflict transactions according to the set of records they try to access, which is defined as a conflict zone. DAC makes admission control over OLTP transactions with the conflict zone as the granularity. By adaptively adjusting the transaction concurrency level for each zone, transaction blocking and waiting among the same kind of high-conflict transactions can be alleviated. Furthermore, thread resources are released to make the execution of low-conflict transactions less affected. We evaluate DAC using a main-memory database prototype and a classical disk-based database system. Experimental results demonstrate that DAC can help OLTP engine significantly improve the performance under mixed OLTP workloads.

This paper describes the AGV scheduling system based on mqtt protocol. The traditional AGV scheduling system uses TCP protocol to communicate with nodes directly, which takes up the resources of the system operation greatly when there are many nodes. This system is developed twice based on opentcs platform, and an AGV scheduling system based on mqtt communication protocol is designed. Redis database is used to cache mqtt subscription messages, and a b/s based management system is developed to analyze user requests to create transport tasks and visual factory overview. It provides various ways to create transportation tasks, connect ERP and MES systems to realize automatic scheduling function; intelligent equipment installed in station provides users with request operation function; in case of emergency, administrators can quickly create transportation tasks through management system. The result of the test proves that the communication line connected with mqtt server is needed to exchange all data with multiple nodes.