Graph synthesis for reconfigurable multicomputer systems

Abstract

In this thesis, a graph synthesis problem is studied for reconfigurable multicomputer systems. There are several limitations to reduce the interprocessor communication overheads for the multicomputer system with the fixed interconnection topology. Therefore, we investigate the performance of reconfigurable multicomputer systems and compare it with that of popular multicomputer systems with fixed interconnection topologies. This comparison shows the worth of reconfigurable multicomputer systems. For the graph synthesis, an efficient heuristic graph synthesis algorithm and a simulated annealing algorithm for reconfigurable multicomputer systems are presented. And the performances of our algorithms are compared with other algorithms. Simulation results prove that the performance of reconfigurable multicomputer systems is superior to that of fixed multicomputer systems. As an implementation of a reconfigurable multicomputer system, a distributed operating system. Trollius is modified and proted to a reconfigurable multicomputer system, KAPAC. KAPAC is a static reconfigurable multicomputer system with 34 processors. Trollius is modified to reconfigure an interconnection topology of KAPAC in execution of a job, by adding the reconfiguration facility to Trollius. To validate the modified reconfigurable Trollius, several real problems are implemented on KAPAC. The result shows the validity of dynamic reconfiguration.