Modelagem de desempenho de sistemas com paralelismo pipeline

Abstract

In an era where the parallelism is imperative (commodity clusters, multi-processor multi-core, GPGPU) the understanding of resource consumption (CPU, disk, etc.) of a parallel application, in different circunstances, is key to decision-making in capacity planning and workload management, such as: (1) how many and what types of machines are needed, in a data center cluster, to support the contracted thresholds for response time and throughput in the service level agreement (SLA)? How should system parameters be fine-tuned to increase system performance and scalability? However, traditional modeling techniques, such as Mean Value Analysis (MVA), can not be directly applied to workloads that have precedence constraints, such as the synchronizations among producers and consumers tasks of a job that present pipeline parallelism. Exact solutions, using Markov chains to represent the possible states of the system were proposed, but are not scalable since the state space grows exponentially with the increasing of the number of tasks. The methodology used is based on an approximate, but efficient, solution, proposed in a previous work, refereed as reference model. This solution uses a hierarchical model, where the highest level (software) is represented by a precedence graph and the lowest level (hardware) by a closed queuing network model. The precedence graph captures the synchronization delays and the average overlap of the execution time of tasks in the same job (intra-job) and tasks of different jobs (inter-job), while the queuing network model captures the average resource contention. The queuing network model is solved through the Approximate Mean Value Analysis technique (aMVA). To introduce the effect of the precedence rules in the aMVA algorithm, the average queue size, which usually only captures the resource contention, were inflated by overlap factors, estimated by the precedence graph. The reference model allows various types of precedence relationships, meanwhile none of its operators capture the synchronization of a pipeline and therefore it is not directly applicable to the workloads that have pipeline parallelism. Our main contribution is show how to build the precedence graph, using the primitive operators proposed in the reference model, to capture the inherent synchronization delay of pipeline parallelism. This methodology was applied in two case studies: (1) simple Business Intelligence queries (BI), which contains a pipeline in the message exchange between their operators, and (2) Online Hadoop Prototype (HOP) jobs, an extension of Hadoop (framework for parallel computing inspired by MapReduce programming model) to provides a pipeline parallelism between map and reduce tasks. The main findings were: (1) we obtained a good approximation in the validation of BI workload model, compared to a queuing netowrk simulator and an emulator of the system, achieving a maximum relative error of 11.5% for job average response time (in literature the maximum acceptable for response time is 30%), for six different scenarios, (2) we observed that the pipeline parallelism had a gain (in job response time) with a light load, i.e., before the system saturates. After the saturation, the job response time is dominated by queues delays and an increase in the pipeline parallelism, instead of increase the speedup, generates more contention, (3) we found that the performance predictions of the analytical model for jobs HOP had good accuracy for various scenarios, but some scenarios were far over-estimated, which led us to evaluate these scenarios in order to identify if there was a characteristic of the system that was not captured, or that was not well modeled. We develop specific simulators to evaluate the adopted model assumptions and we identify that the main source of errors was the premise of the reference model which assumes that the average response time of tasks are exponentially distributed. We evaluate the limitations of the model due to the implications of this assumption and introduce a new primitive operator which uses the fork/join method, previously proposed, to estimate the overlap factors. The analytical model using the fork/join method produces better performance metrics estimates, where the maximum relative error of job response time was less than 15%.