Latency Minimization of Parallel VLSI Processors for Robotics Using Integer Programming
Bumchul Kim and Michitaka Kameyama
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku University, Aoba, Aramaki, Aoba-ku, Sendai, Miyagi, 980-77 Japan
In many cases, intelligent robot systems carry out various sorts of processes where input informations of the next cycle are obtained by waiting for the results of the processing. As a result, demand is made for the development of special-purpose VLSI processors for robotics, which shorten the latency of each individual processing module to an extreme degree. In this paper, under the condition that the processing of systems is carried out step by step for each level in the data dependence graph, we present the parallel processing system with special attention paid to the parallelism within each level. Normally, in the common bus interconnection network, an enormous number of communications are required between PEs, which becomes a factor for causing the system performance to go down. However, since common buses are not only easy to reconfigure but also simple in implementation, they are considered to be suited for VLSI system. From the above, a parallel VLSI processor in which a multiple number of PEs are connected through a common bus is proposed. In the proposed system, once the performance of the PEs is determined, the latency is dependent on the number of communications between PEs. Therefore, the minimization of the latency becomes the problem of minimizing the number of communications. It will be made clear that the problem of minimizing the communications between PEs can be formulated as the integer programming and that the optimum scheduling for minimizing the latency can be carried out.