Search

Summary: Performance prediction for executing graph applications on distributed systems is a prerequisite to improve system performance. Especially for distributed systems optimized by sacrificing the accuracy of results to improve runtime performance, performance prediction can be used to determine accuracy‐related system parameters to achieve a tradeoff between the runtime and inaccuracy of results. This article presents an approach that predicts the runtime and inaccuracy of executing graph algorithms on bulk synchronous parallel (BSP)‐based systems to optimize system parameters by using an artificial neural network (ANN). The proposed approach samples different scales of subgraphs from the input graph by maintaining that the features of subgraphs are similar to the features of the input graph. Then it executes graph algorithm on each subgraph and extracts their runtime features. An ANN‐based performance prediction model is trained off‐line based on the extracted features and is used to predict the performance of executing graph algorithm on the complete input graph. We have validated the proposed approach by conducting single‐source shortest path, connected component, and PageRank on the BSP‐based distributed systems. The experimental results demonstrate that the prediction method can effectively predict the runtime and the inaccuracy with a relative error rate under 14% and under 25%, respectively, compared with the actual performance results. [ABSTRACT FROM AUTHOR]

Speculative multithreading is an effective technique to automatically parallelize sequential programs. Conventional thread partition approaches primarily include heuristic rule-based (HR-based) and machine learning-based. Heuristic rule-based approaches are effective to parallelize one type of programs and can seldom obtain the respective optimal partitions for different programs, and existing machine learning-based approaches usually use vector-based characterization to represent a program, but easily ignore control information among basic blocks and partitions along other paths except the critical path. This paper proposes a novel graph-based thread partition approach to overcome these 2 bottlenecks. Our approach characterizes programs with graphs, integrating feature and control informations, extracting good partition scheme successfully, and also applies a machine-learning algorithm to predict partition for unseen programs. Prophet, which consists of an automatic parallelization compiler and a multicore simulator, evaluates the performance of multithreaded programs. Experiment results reveal that our approach delivers a maximum performance improvement of about 55.49% on an 8 core than HR-based approach and a maximum 97.67% performance improvement over HR-based partition for SPEC2000 benchmarks. This result suggests that graph-based thread partition approach is effective for thread partition in speculative multithreading. [ABSTRACT FROM AUTHOR]

Summary: Simulated annealing (SA) is an effective method for solving unconstrained optimization problems and has been widely used in machine learning and neural network. Nowadays, in order to optimize complex problems with big data, the SA algorithm has been implemented on big data platform and obtains a certain speedup. However, the efficiency for such implementation is still limited because the conventional SA algorithm still runs with low parallelism on new platforms and the computing resource cannot be fully utilized. For these problems, this paper raised a speculative parallel SA algorithm based on Apache Spark to expand the algorithm's parallelism and enhance its efficiency. In this paper, first, the inner dependencies, which stop conventional algorithm, run in parallel, are analyzed. Then, based on the analysis, the Software Thread‐Level Speculation technique is employed to help the conventional algorithm overcome the dependencies and make it run concurrently. Finally, a new parallel SA algorithm with speculation mechanism is proposed and implemented on Apache Spark. The experiments show that, for big data problems, the proposed algorithm could achieve an optimal parallelism when comparing the traditional algorithm without speculation on Apache Spark. Moreover, the execution efficiency of simulated annealing process can be markedly enhanced by the proposed algorithm. [ABSTRACT FROM AUTHOR]

To efficiently process time-evolving graphs where new vertices and edges are inserted over time, an incremental computing model, which processes the newly-constructed graph based on the results of the computation on the outdated graph, is widely adopted in distributed time-evolving graph computing systems. In this paper, we first experimentally study how the results of the graph computation on the local graph structure can approximate the results of the graph computation on the complete graph structure in distributed environments. Then, we develop an optimization approach to reduce the response time in bulk synchronous parallel (BSP)-based incremental computing systems by processing time-evolving graphs on the local graph structure instead of on the complete graph structure. We have evaluated our optimization approach using the graph algorithms single-source shortest path (SSSP) and PageRankon the Amazon Elastic Compute Cloud(EC2), a central part of Amazon.com’s cloud-computing platform, with different scales of graph datasets. The experimental results demonstrate that the local approximation approach can reduce the response time for the SSSP algorithm by 22% and reduce the response time for the PageRank algorithm by 7% on average compared to the existing incremental computing framework of GraphTau. [ABSTRACT FROM AUTHOR]