Loading...
Please wait, while we are loading the content...
Similar Documents
Node-Degree Requirements for Time-Optimal Execution of a Class of Parallel Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Author | Sethu, Harish Wagh, Meghanad D. |
| Copyright Year | 1999 |
| Abstract | In this paper, we consider the time-optimal execution of a class of parallel algorithms based on the principle of divide-and-conquer. We use a computational model of this class of algorithms which incorporates both communication and the associated computation overheads that are unavoidable in a divide-and-conquer methodology. We consider the time-optimal implementation of this class of parallel algorithms on a generic network topology and derive properties of the node-degree requirements of the processors in the topology. We say that a processor is assigned a problem of size n if it is assigned the task of the root node in the computational tree graph for a problem of size n. We obtain a recursive analytical expression for C(n) as a function of n, defined as the lower bound on the node-degree of a processor assigned to solve, in optimal time, a problem of size n. We prove several interesting properties of C(n) as a function of n, including its well-behaved but non-monotonic nature. In this paper, we lay the groundwork based on which one may derive algorithms for complete analytical characterization of C(n), and therefore, optimal partitioning strategies for time-optimal execution with minimal connectivity requirements. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ece.drexel.edu/CCL/papers/pdcs99-node-degree.pdf |
| Alternate Webpage(s) | http://www.lehigh.edu/~mdw0/pdf/node-degree.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
