A Task Scheduling Algorithm for the Parallel Expression Evaluation in a Reconfigurable Fully Digit On-line Network*
Hong- lin Yeh · 2005
In this paper, we present a task scheduling algorithm which accounts for digit-level pipelines of on-line arithmetic units when a limited number of heterogeneous on-line arithmetic units can be connected totally with each other and the network is reconfigurable during the execution. In on-line arithmetic, an arithmetic unit can be reused after the completion of its computing process while its result is available digit by digit during the computation. Thus, a new criterion, called the maximal delay is introduced to take into account additional precedence constraints based on the on-line delay. 1 I n t r o d u c t i o n In on-line arithmetic, the results as well as the operands flow through the operators serially, digit by digit, most significant digit first. This digit flow makes it possible to introduce parallelism between sequential operations by overlapping them in a digit-pipelined fashion. Thus, chaining on-line arithmetic units for a long sequence of arithmetic operations may be significantly faster than in other conventional digitparallel environment.Ill In a fully digit on-line network, the successive operations can be overlapped by using their incomplete results.J2] The interconnection bandwidth is drastically reduced to only one digit(e.g, two bits in a radix-2 redundant system). Simpler layouts and lower circuit areas in VLSI implementation are possible. Recently, some digit on-line networks for special numerical computations have been designed in [3, 4]. In such a system, the arithmetic units are statically connected each other. Here we deal with the on-line arithmetic units, in which the floating-point computations are performed digit-serially for both the exponent and the mantissa.[5] We assume that the network is dynamically reconfigurable for the evaluation of general expressions. An on-line computation is characterized by the on-line delay, i.e. the value 6 such that (i + 6) digits of the operands are required to generate the i-th digit of the result. Let the on-line period p be the time needed to generate a digit of the result. Then, the computation time equals to (6+ L)p where L denote the number of digits to represent a number. If n operations whose on-line delays are denoted by 61, * This work is partially supported by the PRC Architectures Nouvelles de Machines of the French Minist~re de l'Education Nationale and the Centre National de la Recherche Scientifique.