Parallel computation using limited resources
Binay Sugla · 1985
Despite the increased availability of hardware, any parallel computation must be carried out on a real system with limited resources at hand. This thesis addresses itself to the task of designing and analyzing parallel algorithms when the resources of processors, communication and time are limited. The two parts of this thesis deal with multiprocessor systems and VLSI--the two important parallel processing environments that are prevalent today. In the first part we conduct a time-processor-communication tradeoff analysis for two kinds of problems--N input, 1 output and N input, N output computations. The results of this part are: (a) The evaluation of the N-th term of a linear recurrence is shown to require time (THETA)(N/P + logP) on P processors. A constructive algorithm, which is optimal and systolic in nature, is given such that it can be mapped onto a network of P processors connected by shuffle-exchange/cube-connected cycles retaining the same time-processor tradeoff. (b) The above methods are extended to the evaluation of special arithmetic expressions of the form (((t(,1)(THETA)(,1)t(,2))(THETA)(,2)t(,3))(THETA)(,3)...), where (THETA)(,i) may be any of the four operations of +,-,*,+. In the class of the problems of second kind we study the problem of prefix computation, which is an important problem due to the number of naturally occurring computations it can model. For this problem we show that: (a) A parallel prefix circuit of N inputs and width W (viz. the maximum number of nodes at any depth) requires (OMEGA)(2('-k)NlogW) nodes if it has an extra depth of k (LESSTHEQ) logW. (b) Uniform circuit constructions for a prefix circuit whose width is at most W and extra depth k can be achieved within the optimal size as predicted by the lower bound. Finally, we give a general methodology for design of parallel algorithms which can be used to optimize a given design to a wide set of architectural variations. The second part of the thesis considers the design of parallel algorithms for the VLSI model of computation when the resource of time is severely restricted. The main result of this part is: (a) It is shown that for time of computation T, log(eta) (LESSTHEQ) T (LESSTHEQ) 2log(eta), the VLSI area required for a prefix circuit of (eta) inputs and (eta) outputs is (OMEGA)((eta)('2)2('2(log(,2)(eta)-T)) + (eta)). We call this behaviour an extreme area-time tradeoff in VLSI.