Parallel arithmetic expression evaluation on reconfigurable meshes
Authors:
B. Pradeep and C. Siva Ram Murthy
Affiliation:
a Centre for Development of Advanced Computing, 2/1 Brunton Road, Bangalore 560025, India
b Department of Computer Science and Engineering, Indian Institute of Technology, Madras 600036, India
Abstract:
In this paper we present an O(log n) time parallel algorithm for arithmetic expression evaluation, on an n × n processor array with reconfigurable bus system, where n is the sum of the number of operators and constants in the expression. The basic technique involved here is leaves-cutting (rake operation), as in the case of PRAM model algorithms available in the literature for this problem. The input to our algorithm is assumed to be the binary tree associated with a given expression (also known as expression tree with n number of nodes). Our algorithm is faster compared to the previous best time for expression evaluation on mesh connected computers which is O(√n).