Verilog is a hardware description language (HDL) that has become an industry-standard HDL of IEEE. Multithreaded discrete event simulation language (MDESL) is a Verilog-like language. Previously, we have studied the operational semantics and denotational semantics for MDESL. This article investigates the soundness and completeness of the operational semantics for MDESL based on the denotational semantics. We introduce the concepts of transitional condition and phase semantics for each transition to show the relationship between a transition and variables in the denotational model. Then, we give the definition for the soundness and completeness of the operational semantics for MDESL. Based on our definition of the operational semantics of MDESL, we investigate the detailed theoretical proof for the soundness and completeness. Finally, a practical approach complements the theoretical one. We apply the proof assistant Coq to verify the soundness and completeness of the operational semantics for MDESL. Our research demonstrates the consistency between operational and denotational semantics for MDESL through theoretical and practical approaches.

Streaming graph analysis extracts timely insights from evolving graphs, and has gained increasing popularity. In current practice of streaming graph analysis, incoming updates are simply cached in a buffer, until being applied onto existing graph structure to construct a new snapshot. Graph algorithms then work on the new snapshot to produce up-to-date analysis result. Nevertheless, we find that for widely used monotonic graph algorithms, the analysis process can be accelerated by preprocessing buffered updates. To this end, we propose GraPU, a streaming graph analytics system for monotonic graph algorithms. Before applying updates, GraPU preprocesses buffered updates in three consecutive stages: 1) Components-based Classification first identifies the effective graph data that are actually affected by current updates, by classifying the vertices involved in buffered updates according to the predetermined connected components in underlying graph; 2) In-buffer Precomputation generates the safe and profitable intermediate values that can be later merged onto underlying graph to facilitate convergence on new snapshots, by precomputing the values of vertices involved in buffered updates; 3) Hub-vertices Division eliminates the vertex-level load imbalance for analysis on new snapshots, by automatically identifying the high-degree vertices involved in updates and efficiently distributing their high-cost computation over multiple machines. After buffered updates are applied, GraPU calculates vertex values in new snapshots using the subgraph-centric model. GraPU further presents Load-factors Guided Balancing to achieve load balance at subgraph-level, by reassigning some vertices and edges among subgraphs beforehand. Our experimental result shows that, GraPU outperforms state-of-the-art KineoGraph by up to 20.43x.

Machine Learning and Data Mining (MLDM) applications, such as recommendation and topic modeling, generally represent their input data in bipartite graphs with two disjoint vertex-subsets connected only by edges between them. Despite the prevalence of bipartite graphs, existing graph partitioning frameworks have rarely sufficiently exploited their unique structures, especially the highly lopsided subset sizes and extremely skewed vertex degrees. As a result of poor partitioning quality, problems, particularly of high communication cost and severe workload imbalance, arise during subsequent computation over these bipartite graphs in distributed environments such as datacenters or HPC systems, significantly hampering the performance of MLDM applications.

Abstract The hardware description language Verilog has been standardized and widely used in industry. Multithreaded Discrete Event Simulation Language (MDESL) is a Verilog-like language and it contains a rich variety of interesting features such as the event-driven computation and shared-variable concurrency as well as the realtime feature. In this paper, we present the denotational semantics for MDESL based on UTP. First a discrete time semantic model is proposed to describe the observation-oriented semantics for MDESL. The observations record the change of variables of atomic actions over time. Then the healthy formulae are defined to denote all different behaviors of programs and the semantics of programs is expressed in terms of healthy formulae. In addition, we demonstrate some interesting properties about the MDESL programs expressing as algebraic laws and their proofs are supported by our formalized denotational semantics. Our theoretical approach is complemented by a practical one, we use the theorem proof assistant Coq to formalize the UTP-based semantics for MDESL. The correctness of the algebraic laws is also verified via the mechanical approach in Coq. Our work provides a novel way to verify the correctness of UTP-based semantics forMDESL both in a theoretical approach and in a practical approach. It is also a new attempt for the application of Coq in the mechanized semantics.

Model Driven Engineering (MDE) uses models to represent the core part of the software systems. The Unified Model Language (UML) is a widely accepted standard for modeling software systems. Although UML provides numbers of concepts and diagrams to describe the system, there is still an unsolved problem that the semantics and refinement relations of models are not formally defined. In this paper, we apply the constructive type theory to formalize the class diagrams and object diagrams. A suitable subset of UML static models is identified and formally defined. The theorem assistant Coq is applied to encode the semantics of class diagrams. Moreover the refinement relations are also formalized in Coq. The whole approach is supported by tools that do not constrain the semantic definition's expressiveness and flexibility while making it machine-checkable. Our approach offers a novel way for giving a precise foundation in UML and contributes to the goal of improving the overall trustworthy software systems by combining theoretical and practical techniques.

With the rapid development of software engineering and the widely adoption of software systems in various domains, the requirement for software systems is becoming more and more complex, which results in very complex software systems. Motivated by the principle of divide and conquer, component based software development is an effective way of managing the complexity in software development. In this paper, we propose a calculus to formally describe the functional and performance specification of component based software and provide formal semantics for the proposed calculus. Then we provide a method to measure the dynamic complexity of software compositions based on the proposed calculus. Finally, we define a set of algebraic laws to manifest the complexity relations between different functionally equivalent components. We conduct a case study with a real software system and the results show that our method is able to calculate the dynamic complexity of component based systems, and the complexity can be reduced based on our algebraic laws.

In the era of 'dark silicon', modern data centers have to provision additional hardware resources to guarantee the Quality of Service (QoS) of applications in case of bursty workloads that typically occur in low frequency but high intensity. Fortunately, Computational Sprinting has proven to be an effective approach to boost the computing performance of many-core processor chips, which allows a chip to exceed its power and thermal limits temporarily by turning on all processor cores and absorbing the extra heat dissipation with novel phase-changing materials. Consequently, it offers a promising way to deal with these occasional workload bursts by unleashing the full potentials of hardware, avoiding deploying extra computing resources. In this work, we propose ESprint, a QoS-aware management system based on an effective feedback control mechanism for latency-critical applications in data centers. ESprint can perform computational sprinting by precisely scheduling core count, frequency levels, and sprinting duration, serving bursty workloads without QoS violation under the thermal constraint. Specifically, ESprint effectively predict load intensity in the next time interval, and further dynamically allocates appropriate computing resources to minimize actual power consumption. Our prototype-based evaluation results show that ESprint achieves up to 1.92x improvement on energy efficiency for typical workloads while ensuring QoS, over the non-sprinting strategy. We also explore the design space among energy efficiency, core count/frequency scaling techniques, workload characteristics, burst intensity, and QoS requirements, and draw several key insights to guide the effective use of computational sprinting in data centers.

The Unified Modeling Language (UML) provides a number of diagrams to describe the modeling system from different perspectives, which contain overlapping information about the systems.However, it does not provide any means of meticulously checking consistencies among the overlapping elements.In this study, we propose an approach for consistency checking of UML class diagrams and object diagrams using Prolog.First we formalize the model elements based on metamodel and convert the models into Prolog facts.Then we define some consistency rules that are encoded into Prolog.The Prolog's reasoning engine automatically checks the consistencies of models.In addition, we provide interfaces to query models for properties, elements and submodels.The design errors can be effectively avoided and the correctness of code-generalization can be guaranteed according to our approach.

Verilog is a hardware description language (HDL) that has been standardized and widely used in industry. Multithreaded discrete event simulation language (MDESL) is a Verilog-like language. It contains interesting features such as event-driven computation and shared-variable concurrency. This article considers how the algebraic semantics links with the operational semantics for MDESL. Our approach is from both the theoretical and practical aspects. The link is proceeded by deriving the operational semantics from the algebraic semantics. First, we present the algebraic semantics for MDESL. We introduce the concept of head normal form. Second, we present the strategy of deriving operational semantics from algebraic semantics. We also investigate the soundness and completeness of the derived operational semantics with respect to the derivation strategy. Our theoretical approach is complemented by a practical one, and we use the theorem proof assistant Coq to formalize the algebraic laws and the derived operational semantics. Meanwhile, the soundness and completeness of the derived operational semantics is also verified via the mechanical approach in Coq. Our approach is a novel way to formalize and verify the correctness and equivalence of different semantics for MDESL in both a theoretical approach and a practical approach.

Streaming graph analysis extracts timely insights from evolving graphs, and has gained increasing popularity. For current streaming graph analytics systems, incoming updates are simply cached in a buffer, until being applied onto existing graph structure to construct a new snapshot. Iterative graph algorithms then work on the new snapshot to produce up-to-date analysis result. Nevertheless, we find that for widely used monotonic graph algorithms, the buffered updates can be effectively preprocessed to achieve fast and accurate analysis on new snapshots.

Computational Sprinting has proven to be an effective way to boost the computing performance for bursty workloads, which allows a chip to exceed its power and thermal limits temporarily by turning on all processor cores and absorbing the extra heat dissipation with certain phase-changing materials. However, extra power available for sprinting is constrained by existing power distribution infrastructures. Using batteries alone to provide the additional power to achieve performance target not only limits the effectiveness of sprinting, but also negatively impacts the lifetime of the batteries. Leveraging renewable power supply in a green data center provides an opportunity to exploit the maximal potential of Computational Sprinting. However, the intermittent nature of renewable energy makes it very challenging. In this paper, we propose GreenSprint, a renewable energy driven approach that enables a data center to boost its computing performance efficiently by conducting computational sprinting. We present four sprinting strategies to address the challenge imposed by the intermittent and time-varying nature of renewable energy supply. We build an experimental prototype to evaluate GreenSprint on a cluster of 10 servers with a simulated solar power generator. The results show that renewable energy by itself can sustain different duration lengths of sprinting when its supply is sufficient and can improve performance by up to 4.8x for representative interactive applications. We also show the effectiveness of core-count and frequency scaling in the presence of varied renewable power and limited battery energy.

Distributed graph processing frameworks attempt to eliminate workload imbalance among computing nodes. However, this expectation is generally challenged by underlying heterogeneous nodes and fluctuating graph workloads at runtime. This paper proposes Laro, a graph processing system using dynamic graph repartitioning that collects the actual processing times from all nodes, then reconstructs a vertices distribution with minimal migration costs in every iteration. We manifest that the Variation Coefficient of processing times is a critical metric to quantitatively characterize the workload imbalance among nodes at each iteration. Laro also presents a lazy repartitioning algorithm to improve migration efficiency. Laro has been implemented by extending GPS, a popular repartitioning-featured graph processing system. Our evaluation using real-world graphs shows that, by achieving more balanced workload distributions at runtime, Laro derives maximal speedup of 1.82x and 1.41x over the static Skewed Hash and the dynamic GPS respectively.

The Unified Modeling Language (UML) is an industry standard for modeling analysis and design. However, the semantics of UML is not precisely defined and the correctness of refinement relations cannot be verified. In this study, we use the theorem proof assistant Coq to formalize and mechanize the semantics of UML-Statecharts and the refinement relations between models. Based on the mechanized semantics, the desired properties of both the semantics and the refinement relations can be described and proven as predicates and lemmas. This approach provides a promising way to obtain certified fault-free modeling and refinement.

Heterogeneous servers have long been introduced to improve energy efficiency in warehouse-scale computers(WSCs). However, running latency-critical web-services on heterogeneous servers is still challenging because the overheads of transition between such servers heavily impact overall benefits and performance. We propose Montgolfier, a runtime power management system based on a latency-aware feedback control mechanism. It consolidates wimpy and brawny servers into composite nodes to improve energy efficiency while ensuring QoS for latency-critical applications. Montgolfier effectively mitigates the effect of transition overhead between servers with dynamically load prediction and accurately provides thin-provisioned configurations in fine-grain manner for fluctuating loads. Our evaluation results show that Montgolfier reduces energy consumption by up to 34.9% without violating any QoS constraints.