Two new scheduling algorithms are presented. They are used to isolate polynomial real roots on massively parallel systems. One algorithm schedules computations modeled by a pyramid DAG. This is a directed acyclic graph isomprphic to Pascal's triangle. Pyramid DAGs are scheduled so that the communication overhead is linear. The other algorithm schedules parallelizable independent tasks that have identical computing time functions in the number of processors. The two algorithms are combined to schedule a tree-search for polynomial roots; the first algorithm schedules the computations associated with each node of the tree; the second algorithm schedules the nodes on each level of the tree.
展开▼