Evaluating the performance of pipelinestructured parallel programs with skeletons and process algebra. Scalable Computing: Practice and Experience

Abstra t. We show in this paper how to evaluate the performan e of pipeline-stru tured parallel programs with skeletons and pro ess algebra. Sin e many appli ations follow some ommonly used algorithmi skeletons, we identify su h skeletons and model them with pro ess algebra in order to get relevant information about the performan e of the appli ation, and to be able to take good s heduling de isions. This on ept is illustrated through the ase study of the pipeline skeleton, and a tool whi h generates automati ally a set of models and solves them is presented. Some numeri al results are provided, proving the e a y of this approa h. Key words. Algorithmi skeletons, pipeline, high-level parallel programs, performan e evaluation, pro ess algebra, PEPA Workben h. 1. Introdu tion. One of the most promising te hni al innovations in present-day omputing is the in-vention of grid te hnologies whi h harness the omputational power of widely distributed olle tions of om-puters [8℄. Designing an appli ation for the Grid raises di ult issues of resour e allo ation and s heduling (roughly speaking, how to de ide whi h omputer does what, and when, and how they intera t). These issues are made all the more omplex by the inherent unpredi tability of resour e availability and performan e. For example, a super omputer may be required for a more important task, or the Internet onne tions required by the appli ation may be parti ularly busy