Scholarlink

<p>In this study, based on Estrin’s algorithm, we design and analyze scheduling strategies for evaluating sparse univariate polynomials in parallel. First, we apply Estrin’s algorithm to evaluate an univariate sparse polynomial and decompose it into tasks, forming a precedence graph known as a Complete Binary In-Tree (CBT) with varying task costs. We then algorithmically determine a theoretical lower bound on the execution time for any parallel algorithm to execute CBT tasks. To verify the accuracy of our study, we propose a Critical Path Scheduling (CPS) approach. Additionally, we formulate this problem as a binary variable optimization problem and solve it using the CPLEX Mixed Integer Programming (MIP) platform. Experiments conducted on various sparse polynomials, randomly generated, demonstrate that the theoretical execution times of the parallel algorithms corresponding to the two proposed scheduling methods are nearly identical and achieve the lower bound in 56% of the instances for CPS and 93% for MIP. In the worst case, the gap between the computed lower bound and the parallel execution time of any proposed scheduling method does not exceed two time units.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parallel evaluation of sparse polynomials; based on Estrin’s algorithm: conception and analysis of schedulings

  • 期刊论文

  • 发表日期：

    2025年10月18日

查看全文
  • Mounir Marrakchi,
  • Sirine Marrakchi,
  • Issam Troudi,
  • El Mostafa Daoudi

摘要

In this study, based on Estrin’s algorithm, we design and analyze scheduling strategies for evaluating sparse univariate polynomials in parallel. First, we apply Estrin’s algorithm to evaluate an univariate sparse polynomial and decompose it into tasks, forming a precedence graph known as a Complete Binary In-Tree (CBT) with varying task costs. We then algorithmically determine a theoretical lower bound on the execution time for any parallel algorithm to execute CBT tasks. To verify the accuracy of our study, we propose a Critical Path Scheduling (CPS) approach. Additionally, we formulate this problem as a binary variable optimization problem and solve it using the CPLEX Mixed Integer Programming (MIP) platform. Experiments conducted on various sparse polynomials, randomly generated, demonstrate that the theoretical execution times of the parallel algorithms corresponding to the two proposed scheduling methods are nearly identical and achieve the lower bound in 56% of the instances for CPS and 93% for MIP. In the worst case, the gap between the computed lower bound and the parallel execution time of any proposed scheduling method does not exceed two time units.